git.roojs.org Git - web.mtrack/blob - inc/lib/Zend/Search/Lucene/FSM.php

   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-2009 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 16971 2009-07-22 18:05:45Z mikaelkael $
  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-2009 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