src/simplestates.py

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