src/simplestates.py

   1 #!/usr/bin/env python
   2 # -*- coding: iso-8859-1 -*-
   3
   4 # ============================================================
   5 # simplestates.py: Generic state machine class using iterators
   6 # ============================================================
   7 #
   8 # :Version:   0.2
   9 # :Date:      2006-12-01
  10 # :Copyright: 2006 Guenter Milde.
  11 #             Released under the terms of the GNU General Public License
  12 #             (v. 2 or later)
  13 #
  14 # Detailled documentation of this class and the design rationales (including
  15 # tested variants) is available in the file simplestates-test.py.txt
  16 # ::
  17
  18 """Simple generic state machine class using iterators
  19
  20 Usage
  21 =====
  22
  23 Example: A two-state machine sorting numbers in the categories
  24          "< 3" and ">= 3".
  25
  26 Preparation
  27 -----------
  28
  29 Import the basic class::
  30
  31 >>> from simplestates import SimpleStates
  32
  33 Subclass and add state handlers:
  34
  35 >>> class StateExample(SimpleStates):
  36 ...    def high_handler_generator(self):
  37 ...        result = []
  38 ...        for token in self.data_iterator:
  39 ...            if token <= 3:
  40 ...                self.state = "low"
  41 ...                yield result
  42 ...                result = []
  43 ...            else:
  44 ...                result.append(token)
  45 ...        yield result
  46 ...    def low_handler_generator(self):
  47 ...        result = []
  48 ...        for token in self.data_iterator:
  49 ...            if token > 3:
  50 ...                self.state = "high"
  51 ...                yield result
  52 ...                result = []
  53 ...            else:
  54 ...                result.append(token)
  55 ...        yield result
  56
  57
  58 Set up an instance of the StateExample machine with some test data::
  59
  60 >>> testdata = [1, 2, 3, 4, 5, 4, 3, 2, 1]
  61 >>> testmachine = StateExample(testdata, state="low")
  62
  63 >>> print [name for name in dir(testmachine) if name.endswith("generator")]
  64 ['high_handler_generator', 'low_handler_generator']
  65
  66
  67 Running
  68 -------
  69
  70 Iterating over the state machine yields the results of state processing::
  71
  72 >>> for result in testmachine:
  73 ...     print result,
  74 ...
  75 [1, 2, 3] [5, 4] [2, 1]
  76
  77 For a correct working sort algorithm, we would expect::
  78
  79   [1, 2, 3] [4, 5, 4] [3, 2, 1]
  80
  81 However, to achieve this a backtracking algorithm is needed. See iterqueue.py
  82 and simplestates-test.py for an example.
  83
  84
  85 The `__call__` method returns a list of results. It is used if you call
  86 an instance of the class::
  87
  88 >>> testmachine()
  89 [[1, 2, 3], [5, 4], [2, 1]]
  90
  91 """
  92
  93 # Abstract State Machine Class
  94 # ============================
  95 #
  96 # ::
  97
  98 class SimpleStates:
  99     """generic state machine acting on iterable data
 100
 101     Class attributes:
 102
 103       state -- name of the current state (next state_handler method called)
 104       state_handler_generator_suffix -- common suffix of generator functions
 105                                         returning a state-handler iterator
 106     """
 107     state = 'start'
 108     state_handler_generator_suffix = "_handler_generator"
 109
 110 # Initialisation
 111 # --------------
 112 #
 113 # * sets the data object to the `data` argument.
 114 #
 115 # * remaining keyword arguments are stored as class attributes (or methods, if
 116 #   they are function objects) overwriting class defaults (a neat little trick
 117 #   I found somewhere on the net)
 118 #
 119 #   ..note: This is the same as `self.__dict__.update(keyw)`. However,
 120 #           the "Tutorial" advises to confine the direct use of `__dict__`
 121 #           to post-mortem analysis or the like...
 122 #
 123 # ::
 124
 125     def __init__(self, data, **keyw):
 126         """data   --  iterable data object
 127                       (list, file, generator, string, ...)
 128            **keyw --  all remaining keyword arguments are
 129                       stored as class attributes
 130         """
 131         self.data = data
 132         for (key, value) in keyw.iteritems():
 133             setattr(self, key, value)
 134
 135
 136
 137
 138
 139 # Iteration over class instances
 140 # ------------------------------
 141 #
 142 # The special `__iter__` method returns an iterator. This allows to use
 143 # a  class instance directly in an iteration loop.  We define it as is a
 144 # generator method that sets the initial state and then iterates over the
 145 # data calling the state methods::
 146
 147     def __iter__(self):
 148         """Generate and return an iterator
 149
 150         * ensure `data` is an iterator
 151         * convert the state generators into iterators
 152         * (re) set the state attribute to the initial state
 153         * pass control to the active states state_handler
 154           which should call and process self.data_iterator.next()
 155         """
 156         self.data_iterator = iter(self.data)
 157         self._initialize_state_generators()
 158         # now start the iteration
 159         while True:
 160             yield getattr(self, self.state)()
 161
 162 # a helper function generates state handlers from generators. It is called by
 163 # the `__iter__` method above::
 164
 165     def _initialize_state_generators(self):
 166         """Generic function to initialize state handlers from generators
 167
 168         functions whose name matches `[^_]<state>_handler_generator` will
 169         be converted to iterators and their `.next()` method stored as
 170         `self.<state>`.
 171         """
 172         suffix = self.state_handler_generator_suffix
 173         shg_names = [name for name in dir(self)
 174                       if name.endswith(suffix)
 175                       and not name.startswith("_")]
 176         for name in shg_names:
 177             shg = getattr(self, name)
 178             setattr(self, name[:-len(suffix)], shg().next)
 179
 180 # Use instances like functions
 181 # ----------------------------
 182 #
 183 # To allow use of class instances as callable objects, we add a `__call__`
 184 # method::
 185
 186     def __call__(self):
 187         """Iterate over state-machine and return results as a list"""
 188         return [token for token in self]
 189
 190 # Command line usage
 191 # ==================
 192 #
 193 # running this script does a doctest::
 194
 195 if __name__ == "__main__":
 196     import doctest
 197     doctest.testmod()