[Summary view] [Print] [Text view]

   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-2007 Zend Technologies USA Inc. (http://www.zend.com)
  18   * @license    http://framework.zend.com/license/new-bsd     New BSD License
  19   */
  20  
  21  
  22  /** Zend_Search_Lucene_FSMAction */
  23  require_once $CFG->dirroot.'/search/Zend/Search/Lucene/FSMAction.php';
  24  
  25  /** Zend_Search_Exception */
  26  require_once $CFG->dirroot.'/search/Zend/Search/Exception.php';
  27  
  28  
  29  /**
  30   * Abstract Finite State Machine
  31   *
  32   * Take a look on Wikipedia state machine description: http://en.wikipedia.org/wiki/Finite_state_machine
  33   *
  34   * Any type of Transducers (Moore machine or Mealy machine) also may be implemented by using this abstract FSM.
  35   * process() methods invokes a specified actions which may construct FSM output.
  36   * Actions may be also used to signal, that we have reached Accept State
  37   *
  38   * @category   Zend
  39   * @package    Zend_Search_Lucene
  40   * @copyright  Copyright (c) 2005-2007 Zend Technologies USA Inc. (http://www.zend.com)
  41   * @license    http://framework.zend.com/license/new-bsd     New BSD License
  42   */
  43  abstract class Zend_Search_Lucene_FSM
  44  {
  45      /**
  46       * Machine States alphabet
  47       *
  48       * @var array
  49       */
  50      private $_states = array();
  51  
  52      /**
  53       * Current state
  54       *
  55       * @var integer|string
  56       */
  57      private $_currentState = null;
  58  
  59      /**
  60       * Input alphabet
  61       *
  62       * @var array
  63       */
  64      private $_inputAphabet = array();
  65  
  66      /**
  67       * State transition table
  68       *
  69       * [sourceState][input] => targetState
  70       *
  71       * @var array
  72       */
  73      private $_rules = array();
  74  
  75      /**
  76       * List of entry actions
  77       * Each action executes when entering the state
  78       *
  79       * [state] => action
  80       *
  81       * @var array
  82       */
  83      private $_entryActions =  array();
  84  
  85      /**
  86       * List of exit actions
  87       * Each action executes when exiting the state
  88       *
  89       * [state] => action
  90       *
  91       * @var array
  92       */
  93      private $_exitActions =  array();
  94  
  95      /**
  96       * List of input actions
  97       * Each action executes when entering the state
  98       *
  99       * [state][input] => action
 100       *
 101       * @var array
 102       */
 103      private $_inputActions =  array();
 104  
 105      /**
 106       * List of input actions
 107       * Each action executes when entering the state
 108       *
 109       * [state1][state2] => action
 110       *
 111       * @var array
 112       */
 113      private $_transitionActions =  array();
 114  
 115      /**
 116       * Finite State machine constructor
 117       *
 118       * $states is an array of integers or strings with a list of possible machine states
 119       * constructor treats fist list element as a sturt state (assignes it to $_current state).
 120       * It may be reassigned by setState() call.
 121       * States list may be empty and can be extended later by addState() or addStates() calls.
 122       *
 123       * $inputAphabet is the same as $states, but represents input alphabet
 124       * it also may be extended later by addInputSymbols() or addInputSymbol() calls.
 125       *
 126       * $rules parameter describes FSM transitions and has a structure:
 127       * array( array(sourseState, input, targetState[, inputAction]),
 128       *        array(sourseState, input, targetState[, inputAction]),
 129       *        array(sourseState, input, targetState[, inputAction]),
 130       *        ...
 131       *      )
 132       * Rules also can be added later by addRules() and addRule() calls.
 133       *
 134       * FSM actions are very flexible and may be defined by addEntryAction(), addExitAction(),
 135       * addInputAction() and addTransitionAction() calls.
 136       *
 137       * @param array $states
 138       * @param array $inputAphabet
 139       * @param array $rules
 140       */
 141      public function __construct($states = array(), $inputAphabet = array(), $rules = array())
 142      {
 143          $this->addStates($states);
 144          $this->addInputSymbols($inputAphabet);
 145          $this->addRules($rules);
 146      }
 147  
 148      /**
 149       * Add states to the state machine
 150       *
 151       * @param array $states
 152       */
 153      public function addStates($states)
 154      {
 155          foreach ($states as $state) {
 156              $this->addState($state);
 157          }
 158      }
 159  
 160      /**
 161       * Add state to the state machine
 162       *
 163       * @param integer|string $state
 164       */
 165      public function addState($state)
 166      {
 167          $this->_states[$state] = $state;
 168  
 169          if ($this->_currentState === null) {
 170              $this->_currentState = $state;
 171          }
 172      }
 173  
 174      /**
 175       * Set FSM state.
 176       * No any action is invoked
 177       *
 178       * @param integer|string $state
 179       * @throws Zend_Search_Exception
 180       */
 181      public function setState($state)
 182      {
 183          if (!isset($this->_states[$state])) {
 184              throw new Zend_Search_Exception('State \'' . $state . '\' is not on of the possible FSM states.');
 185          }
 186  
 187          $this->_currentState = $state;
 188      }
 189  
 190      /**
 191       * Get FSM state.
 192       *
 193       * @return integer|string $state|null
 194       */
 195      public function getState()
 196      {
 197          return $this->_currentState;
 198      }
 199  
 200      /**
 201       * Add symbols to the input alphabet
 202       *
 203       * @param array $inputAphabet
 204       */
 205      public function addInputSymbols($inputAphabet)
 206      {
 207          foreach ($inputAphabet as $inputSymbol) {
 208              $this->addInputSymbol($inputSymbol);
 209          }
 210      }
 211  
 212      /**
 213       * Add symbol to the input alphabet
 214       *
 215       * @param integer|string $inputSymbol
 216       */
 217      public function addInputSymbol($inputSymbol)
 218      {
 219          $this->_inputAphabet[$inputSymbol] = $inputSymbol;
 220      }
 221  
 222  
 223      /**
 224       * Add transition rules
 225       *
 226       * array structure:
 227       * array( array(sourseState, input, targetState[, inputAction]),
 228       *        array(sourseState, input, targetState[, inputAction]),
 229       *        array(sourseState, input, targetState[, inputAction]),
 230       *        ...
 231       *      )
 232       *
 233       * @param array $rules
 234       */
 235      public function addRules($rules)
 236      {
 237          foreach ($rules as $rule) {
 238              $this->addrule($rule[0], $rule[1], $rule[2], isset($rule[3])?$rule[3]:null);
 239          }
 240      }
 241  
 242      /**
 243       * Add symbol to the input alphabet
 244       *
 245       * @param integer|string $sourceState
 246       * @param integer|string $input
 247       * @param integer|string $targetState
 248       * @param Zend_Search_Lucene_FSMAction|null $inputAction
 249       * @throws Zend_Search_Exception
 250       */
 251      public function addRule($sourceState, $input, $targetState, $inputAction = null)
 252      {
 253          if (!isset($this->_states[$sourceState])) {
 254              throw new Zend_Search_Exception('Undefined source state (' . $sourceState . ').');
 255          }
 256          if (!isset($this->_states[$targetState])) {
 257              throw new Zend_Search_Exception('Undefined target state (' . $targetState . ').');
 258          }
 259          if (!isset($this->_inputAphabet[$input])) {
 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              throw new Zend_Search_Exception('Rule for {state,input} pair (' . $sourceState . ', '. $input . ') is already defined.');
 268          }
 269  
 270          $this->_rules[$sourceState][$input] = $targetState;
 271  
 272  
 273          if ($inputAction !== null) {
 274              $this->addInputAction($sourceState, $input, $inputAction);
 275          }
 276      }
 277  
 278  
 279      /**
 280       * Add state entry action.
 281       * Several entry actions are allowed.
 282       * Action execution order is defined by addEntryAction() calls
 283       *
 284       * @param integer|string $state
 285       * @param Zend_Search_Lucene_FSMAction $action
 286       */
 287      public function addEntryAction($state, Zend_Search_Lucene_FSMAction $action)
 288      {
 289          if (!isset($this->_states[$state])) {
 290              throw new Zend_Search_Exception('Undefined state (' . $state. ').');
 291          }
 292  
 293          if (!isset($this->_entryActions[$state])) {
 294              $this->_entryActions[$state] = array();
 295          }
 296  
 297          $this->_entryActions[$state][] = $action;
 298      }
 299  
 300      /**
 301       * Add state exit action.
 302       * Several exit actions are allowed.
 303       * Action execution order is defined by addEntryAction() calls
 304       *
 305       * @param integer|string $state
 306       * @param Zend_Search_Lucene_FSMAction $action
 307       */
 308      public function addExitAction($state, Zend_Search_Lucene_FSMAction $action)
 309      {
 310          if (!isset($this->_states[$state])) {
 311              throw new Zend_Search_Exception('Undefined state (' . $state. ').');
 312          }
 313  
 314          if (!isset($this->_exitActions[$state])) {
 315              $this->_exitActions[$state] = array();
 316          }
 317  
 318          $this->_exitActions[$state][] = $action;
 319      }
 320  
 321      /**
 322       * Add input action (defined by {state, input} pair).
 323       * Several input actions are allowed.
 324       * Action execution order is defined by addInputAction() calls
 325       *
 326       * @param integer|string $state
 327       * @param integer|string $input
 328       * @param Zend_Search_Lucene_FSMAction $action
 329       */
 330      public function addInputAction($state, $inputSymbol, Zend_Search_Lucene_FSMAction $action)
 331      {
 332          if (!isset($this->_states[$state])) {
 333              throw new Zend_Search_Exception('Undefined state (' . $state. ').');
 334          }
 335          if (!isset($this->_inputAphabet[$inputSymbol])) {
 336              throw new Zend_Search_Exception('Undefined input symbol (' . $inputSymbol. ').');
 337          }
 338  
 339          if (!isset($this->_inputActions[$state])) {
 340              $this->_inputActions[$state] = array();
 341          }
 342          if (!isset($this->_inputActions[$state][$inputSymbol])) {
 343              $this->_inputActions[$state][$inputSymbol] = array();
 344          }
 345  
 346          $this->_inputActions[$state][$inputSymbol][] = $action;
 347      }
 348  
 349      /**
 350       * Add transition action (defined by {state, input} pair).
 351       * Several transition actions are allowed.
 352       * Action execution order is defined by addTransitionAction() calls
 353       *
 354       * @param integer|string $sourceState
 355       * @param integer|string $targetState
 356       * @param Zend_Search_Lucene_FSMAction $action
 357       */
 358      public function addTransitionAction($sourceState, $targetState, Zend_Search_Lucene_FSMAction $action)
 359      {
 360          if (!isset($this->_states[$sourceState])) {
 361              throw new Zend_Search_Exception('Undefined source state (' . $sourceState. ').');
 362          }
 363          if (!isset($this->_states[$targetState])) {
 364              throw new Zend_Search_Exception('Undefined source state (' . $targetState. ').');
 365          }
 366  
 367          if (!isset($this->_transitionActions[$sourceState])) {
 368              $this->_transitionActions[$sourceState] = array();
 369          }
 370          if (!isset($this->_transitionActions[$sourceState][$targetState])) {
 371              $this->_transitionActions[$sourceState][$targetState] = array();
 372          }
 373  
 374          $this->_transitionActions[$sourceState][$targetState][] = $action;
 375      }
 376  
 377  
 378      /**
 379       * Process an input
 380       *
 381       * @param mixed $input
 382       * @throws Zend_Search_Exception
 383       */
 384      public function process($input)
 385      {
 386          if (!isset($this->_rules[$this->_currentState])) {
 387              throw new Zend_Search_Exception('There is no any rule for current state (' . $this->_currentState . ').');
 388          }
 389          if (!isset($this->_rules[$this->_currentState][$input])) {
 390              throw new Zend_Search_Exception('There is no any rule for {current state, input} pair (' . $this->_currentState . ', ' . $input . ').');
 391          }
 392  
 393          $sourceState = $this->_currentState;
 394          $targetState = $this->_rules[$this->_currentState][$input];
 395  
 396          if ($sourceState != $targetState  &&  isset($this->_exitActions[$sourceState])) {
 397              foreach ($this->_exitActions[$sourceState] as $action) {
 398                  $action->doAction();
 399              }
 400          }
 401          if (isset($this->_inputActions[$sourceState]) &&
 402              isset($this->_inputActions[$sourceState][$input])) {
 403              foreach ($this->_inputActions[$sourceState][$input] as $action) {
 404                  $action->doAction();
 405              }
 406          }
 407  
 408  
 409          $this->_currentState = $targetState;
 410  
 411          if (isset($this->_transitionActions[$sourceState]) &&
 412              isset($this->_transitionActions[$sourceState][$targetState])) {
 413              foreach ($this->_transitionActions[$sourceState][$targetState] as $action) {
 414                  $action->doAction();
 415              }
 416          }
 417          if ($sourceState != $targetState  &&  isset($this->_entryActions[$targetState])) {
 418              foreach ($this->_entryActions[$targetState] as $action) {
 419                  $action->doAction();
 420              }
 421          }
 422      }
 423  
 424      public function reset()
 425      {
 426          if (count($this->_states) == 0) {
 427              throw new Zend_Search_Exception('There is no any state defined for FSM.');
 428          }
 429  
 430          $this->_currentState = $this->_states[0];
 431      }
 432  }
 433