1 <?php

     2 /**

     3  * Zend Framework

     4  *

     5  * LICENSE

     6  *

     7  * This source file is subject to the new BSD license that is bundled

     8  * with this package in the file LICENSE.txt.

     9  * It is also available through the world-wide-web at this URL:

    10  * http://framework.zend.com/license/new-bsd

    11  * If you did not receive a copy of the license and are unable to

    12  * obtain it through the world-wide-web, please send an email

    13  * to license@zend.com so we can send you a copy immediately.

    14  *

    15  * @category   Zend

    16  * @package    Zend_Search_Lucene

    17  * @copyright  Copyright (c) 2005-2010 Zend Technologies USA Inc. (http://www.zend.com)

    18  * @license    http://framework.zend.com/license/new-bsd     New BSD License

    19  * @version    $Id: FSM.php 20096 2010-01-06 02:05:09Z bkarwin $

    20  */

    21 

    22 /** Zend_Search_Lucene_FSMAction */

    23 require_once 'Zend/Search/Lucene/FSMAction.php';

    24 

    25 /**

    26  * Abstract Finite State Machine

    27  *

    28  * Take a look on Wikipedia state machine description: http://en.wikipedia.org/wiki/Finite_state_machine

    29  *

    30  * Any type of Transducers (Moore machine or Mealy machine) also may be implemented by using this abstract FSM.

    31  * process() methods invokes a specified actions which may construct FSM output.

    32  * Actions may be also used to signal, that we have reached Accept State

    33  *

    34  * @category   Zend

    35  * @package    Zend_Search_Lucene

    36  * @copyright  Copyright (c) 2005-2010 Zend Technologies USA Inc. (http://www.zend.com)

    37  * @license    http://framework.zend.com/license/new-bsd     New BSD License

    38  */

    39 abstract class Zend_Search_Lucene_FSM

    40 {

    41     /**

    42      * Machine States alphabet

    43      *

    44      * @var array

    45      */

    46     private $_states = array();

    47 

    48     /**

    49      * Current state

    50      *

    51      * @var integer|string

    52      */

    53     private $_currentState = null;

    54 

    55     /**

    56      * Input alphabet

    57      *

    58      * @var array

    59      */

    60     private $_inputAphabet = array();

    61 

    62     /**

    63      * State transition table

    64      *

    65      * [sourceState][input] => targetState

    66      *

    67      * @var array

    68      */

    69     private $_rules = array();

    70 

    71     /**

    72      * List of entry actions

    73      * Each action executes when entering the state

    74      *

    75      * [state] => action

    76      *

    77      * @var array

    78      */

    79     private $_entryActions =  array();

    80 

    81     /**

    82      * List of exit actions

    83      * Each action executes when exiting the state

    84      *

    85      * [state] => action

    86      *

    87      * @var array

    88      */

    89     private $_exitActions =  array();

    90 

    91     /**

    92      * List of input actions

    93      * Each action executes when entering the state

    94      *

    95      * [state][input] => action

    96      *

    97      * @var array

    98      */

    99     private $_inputActions =  array();

   100 

   101     /**

   102      * List of input actions

   103      * Each action executes when entering the state

   104      *

   105      * [state1][state2] => action

   106      *

   107      * @var array

   108      */

   109     private $_transitionActions =  array();

   110 

   111     /**

   112      * Finite State machine constructor

   113      *

   114      * $states is an array of integers or strings with a list of possible machine states

   115      * constructor treats fist list element as a sturt state (assignes it to $_current state).

   116      * It may be reassigned by setState() call.

   117      * States list may be empty and can be extended later by addState() or addStates() calls.

   118      *

   119      * $inputAphabet is the same as $states, but represents input alphabet

   120      * it also may be extended later by addInputSymbols() or addInputSymbol() calls.

   121      *

   122      * $rules parameter describes FSM transitions and has a structure:

   123      * array( array(sourseState, input, targetState[, inputAction]),

   124      *        array(sourseState, input, targetState[, inputAction]),

   125      *        array(sourseState, input, targetState[, inputAction]),

   126      *        ...

   127      *      )

   128      * Rules also can be added later by addRules() and addRule() calls.

   129      *

   130      * FSM actions are very flexible and may be defined by addEntryAction(), addExitAction(),

   131      * addInputAction() and addTransitionAction() calls.

   132      *

   133      * @param array $states

   134      * @param array $inputAphabet

   135      * @param array $rules

   136      */

   137     public function __construct($states = array(), $inputAphabet = array(), $rules = array())

   138     {

   139         $this->addStates($states);

   140         $this->addInputSymbols($inputAphabet);

   141         $this->addRules($rules);

   142     }

   143 

   144     /**

   145      * Add states to the state machine

   146      *

   147      * @param array $states

   148      */

   149     public function addStates($states)

   150     {

   151         foreach ($states as $state) {

   152             $this->addState($state);

   153         }

   154     }

   155 

   156     /**

   157      * Add state to the state machine

   158      *

   159      * @param integer|string $state

   160      */

   161     public function addState($state)

   162     {

   163         $this->_states[$state] = $state;

   164 

   165         if ($this->_currentState === null) {

   166             $this->_currentState = $state;

   167         }

   168     }

   169 

   170     /**

   171      * Set FSM state.

   172      * No any action is invoked

   173      *

   174      * @param integer|string $state

   175      * @throws Zend_Search_Exception

   176      */

   177     public function setState($state)

   178     {

   179         if (!isset($this->_states[$state])) {

   180             require_once 'Zend/Search/Exception.php';

   181             throw new Zend_Search_Exception('State \'' . $state . '\' is not on of the possible FSM states.');

   182         }

   183 

   184         $this->_currentState = $state;

   185     }

   186 

   187     /**

   188      * Get FSM state.

   189      *

   190      * @return integer|string $state|null

   191      */

   192     public function getState()

   193     {

   194         return $this->_currentState;

   195     }

   196 

   197     /**

   198      * Add symbols to the input alphabet

   199      *

   200      * @param array $inputAphabet

   201      */

   202     public function addInputSymbols($inputAphabet)

   203     {

   204         foreach ($inputAphabet as $inputSymbol) {

   205             $this->addInputSymbol($inputSymbol);

   206         }

   207     }

   208 

   209     /**

   210      * Add symbol to the input alphabet

   211      *

   212      * @param integer|string $inputSymbol

   213      */

   214     public function addInputSymbol($inputSymbol)

   215     {

   216         $this->_inputAphabet[$inputSymbol] = $inputSymbol;

   217     }

   218 

   219 

   220     /**

   221      * Add transition rules

   222      *

   223      * array structure:

   224      * array( array(sourseState, input, targetState[, inputAction]),

   225      *        array(sourseState, input, targetState[, inputAction]),

   226      *        array(sourseState, input, targetState[, inputAction]),

   227      *        ...

   228      *      )

   229      *

   230      * @param array $rules

   231      */

   232     public function addRules($rules)

   233     {

   234         foreach ($rules as $rule) {

   235             $this->addrule($rule[0], $rule[1], $rule[2], isset($rule[3])?$rule[3]:null);

   236         }

   237     }

   238 

   239     /**

   240      * Add symbol to the input alphabet

   241      *

   242      * @param integer|string $sourceState

   243      * @param integer|string $input

   244      * @param integer|string $targetState

   245      * @param Zend_Search_Lucene_FSMAction|null $inputAction

   246      * @throws Zend_Search_Exception

   247      */

   248     public function addRule($sourceState, $input, $targetState, $inputAction = null)

   249     {

   250         if (!isset($this->_states[$sourceState])) {

   251             require_once 'Zend/Search/Exception.php';

   252             throw new Zend_Search_Exception('Undefined source state (' . $sourceState . ').');

   253         }

   254         if (!isset($this->_states[$targetState])) {

   255             require_once 'Zend/Search/Exception.php';

   256             throw new Zend_Search_Exception('Undefined target state (' . $targetState . ').');

   257         }

   258         if (!isset($this->_inputAphabet[$input])) {

   259             require_once 'Zend/Search/Exception.php';

   260             throw new Zend_Search_Exception('Undefined input symbol (' . $input . ').');

   261         }

   262 

   263         if (!isset($this->_rules[$sourceState])) {

   264             $this->_rules[$sourceState] = array();

   265         }

   266         if (isset($this->_rules[$sourceState][$input])) {

   267             require_once 'Zend/Search/Exception.php';

   268             throw new Zend_Search_Exception('Rule for {state,input} pair (' . $sourceState . ', '. $input . ') is already defined.');

   269         }

   270 

   271         $this->_rules[$sourceState][$input] = $targetState;

   272 

   273 

   274         if ($inputAction !== null) {

   275             $this->addInputAction($sourceState, $input, $inputAction);

   276         }

   277     }

   278 

   279 

   280     /**

   281      * Add state entry action.

   282      * Several entry actions are allowed.

   283      * Action execution order is defined by addEntryAction() calls

   284      *

   285      * @param integer|string $state

   286      * @param Zend_Search_Lucene_FSMAction $action

   287      */

   288     public function addEntryAction($state, Zend_Search_Lucene_FSMAction $action)

   289     {

   290         if (!isset($this->_states[$state])) {

   291             require_once 'Zend/Search/Exception.php';

   292             throw new Zend_Search_Exception('Undefined state (' . $state. ').');

   293         }

   294 

   295         if (!isset($this->_entryActions[$state])) {

   296             $this->_entryActions[$state] = array();

   297         }

   298 

   299         $this->_entryActions[$state][] = $action;

   300     }

   301 

   302     /**

   303      * Add state exit action.

   304      * Several exit actions are allowed.

   305      * Action execution order is defined by addEntryAction() calls

   306      *

   307      * @param integer|string $state

   308      * @param Zend_Search_Lucene_FSMAction $action

   309      */

   310     public function addExitAction($state, Zend_Search_Lucene_FSMAction $action)

   311     {

   312         if (!isset($this->_states[$state])) {

   313             require_once 'Zend/Search/Exception.php';

   314             throw new Zend_Search_Exception('Undefined state (' . $state. ').');

   315         }

   316 

   317         if (!isset($this->_exitActions[$state])) {

   318             $this->_exitActions[$state] = array();

   319         }

   320 

   321         $this->_exitActions[$state][] = $action;

   322     }

   323 

   324     /**

   325      * Add input action (defined by {state, input} pair).

   326      * Several input actions are allowed.

   327      * Action execution order is defined by addInputAction() calls

   328      *

   329      * @param integer|string $state

   330      * @param integer|string $input

   331      * @param Zend_Search_Lucene_FSMAction $action

   332      */

   333     public function addInputAction($state, $inputSymbol, Zend_Search_Lucene_FSMAction $action)

   334     {

   335         if (!isset($this->_states[$state])) {

   336             require_once 'Zend/Search/Exception.php';

   337             throw new Zend_Search_Exception('Undefined state (' . $state. ').');

   338         }

   339         if (!isset($this->_inputAphabet[$inputSymbol])) {

   340             require_once 'Zend/Search/Exception.php';

   341             throw new Zend_Search_Exception('Undefined input symbol (' . $inputSymbol. ').');

   342         }

   343 

   344         if (!isset($this->_inputActions[$state])) {

   345             $this->_inputActions[$state] = array();

   346         }

   347         if (!isset($this->_inputActions[$state][$inputSymbol])) {

   348             $this->_inputActions[$state][$inputSymbol] = array();

   349         }

   350 

   351         $this->_inputActions[$state][$inputSymbol][] = $action;

   352     }

   353 

   354     /**

   355      * Add transition action (defined by {state, input} pair).

   356      * Several transition actions are allowed.

   357      * Action execution order is defined by addTransitionAction() calls

   358      *

   359      * @param integer|string $sourceState

   360      * @param integer|string $targetState

   361      * @param Zend_Search_Lucene_FSMAction $action

   362      */

   363     public function addTransitionAction($sourceState, $targetState, Zend_Search_Lucene_FSMAction $action)

   364     {

   365         if (!isset($this->_states[$sourceState])) {

   366             require_once 'Zend/Search/Exception.php';

   367             throw new Zend_Search_Exception('Undefined source state (' . $sourceState. ').');

   368         }

   369         if (!isset($this->_states[$targetState])) {

   370             require_once 'Zend/Search/Exception.php';

   371             throw new Zend_Search_Exception('Undefined source state (' . $targetState. ').');

   372         }

   373 

   374         if (!isset($this->_transitionActions[$sourceState])) {

   375             $this->_transitionActions[$sourceState] = array();

   376         }

   377         if (!isset($this->_transitionActions[$sourceState][$targetState])) {

   378             $this->_transitionActions[$sourceState][$targetState] = array();

   379         }

   380 

   381         $this->_transitionActions[$sourceState][$targetState][] = $action;

   382     }

   383 

   384 

   385     /**

   386      * Process an input

   387      *

   388      * @param mixed $input

   389      * @throws Zend_Search_Exception

   390      */

   391     public function process($input)

   392     {

   393         if (!isset($this->_rules[$this->_currentState])) {

   394             require_once 'Zend/Search/Exception.php';

   395             throw new Zend_Search_Exception('There is no any rule for current state (' . $this->_currentState . ').');

   396         }

   397         if (!isset($this->_rules[$this->_currentState][$input])) {

   398             require_once 'Zend/Search/Exception.php';

   399             throw new Zend_Search_Exception('There is no any rule for {current state, input} pair (' . $this->_currentState . ', ' . $input . ').');

   400         }

   401 

   402         $sourceState = $this->_currentState;

   403         $targetState = $this->_rules[$this->_currentState][$input];

   404 

   405         if ($sourceState != $targetState  &&  isset($this->_exitActions[$sourceState])) {

   406             foreach ($this->_exitActions[$sourceState] as $action) {

   407                 $action->doAction();

   408             }

   409         }

   410         if (isset($this->_inputActions[$sourceState]) &&

   411             isset($this->_inputActions[$sourceState][$input])) {

   412             foreach ($this->_inputActions[$sourceState][$input] as $action) {

   413                 $action->doAction();

   414             }

   415         }

   416 

   417 

   418         $this->_currentState = $targetState;

   419 

   420         if (isset($this->_transitionActions[$sourceState]) &&

   421             isset($this->_transitionActions[$sourceState][$targetState])) {

   422             foreach ($this->_transitionActions[$sourceState][$targetState] as $action) {

   423                 $action->doAction();

   424             }

   425         }

   426         if ($sourceState != $targetState  &&  isset($this->_entryActions[$targetState])) {

   427             foreach ($this->_entryActions[$targetState] as $action) {

   428                 $action->doAction();

   429             }

   430         }

   431     }

   432 

   433     public function reset()

   434     {

   435         if (count($this->_states) == 0) {

   436             require_once 'Zend/Search/Exception.php';

   437             throw new Zend_Search_Exception('There is no any state defined for FSM.');

   438         }

   439 

   440         $this->_currentState = $this->_states[0];

   441     }

   442 }

   443