added kdenlive
[feisty_meow.git] / nucleus / library / processes / state_machine.h
1 #ifndef STATE_MACHINE_CLASS
2 #define STATE_MACHINE_CLASS
3
4 /*****************************************************************************\
5 *                                                                             *
6 *  Name   : state_machine                                                     *
7 *  Author : Chris Koeritz                                                     *
8 *                                                                             *
9 *******************************************************************************
10 * Copyright (c) 1992-$now By Author.  This program is free software; you can  *
11 * redistribute it and/or modify it under the terms of the GNU General Public  *
12 * License as published by the Free Software Foundation; either version 2 of   *
13 * the License or (at your option) any later version.  This is online at:      *
14 *     http://www.fsf.org/copyleft/gpl.html                                    *
15 * Please send any updates to: fred@gruntose.com                               *
16 \*****************************************************************************/
17
18 #include <basis/contracts.h>
19 #include <timely/time_stamp.h>
20
21 namespace processes {
22
23 class state_machine_override_array;
24 class state_machine_state_array;
25
26 //! Monitors objects with multiple states and the transitions between states.
27 /*!
28   A state machine is a computational abstraction for any control process
29   that has discrete states and transitions between the states.
30   As used here, the "state_machine" is a base class for objects that can be
31   manipulated by the "transition_map" class.  Your transition map must be
32   validated and you must use it to reset() your state_machine object before
33   any activity can occur.  (One aspect of validation is that all states must be
34   reachable from the user-specified starting state.  The other requirements
35   are documented below for transition_map.) Once validation is done, the
36   transition map manages the machine through the various states that are
37   defined and applies trigger values to modify the current state when asked
38   to do so.  It also applies any defined timed transitions automatically.
39   This implementation of state machines is configured once (by defining the
40   transition_map object), but then the machines can be run repeatedly (via
41   the state_machine object).
42 */
43
44 class state_machine : public virtual basis::root_object
45 {
46 public:
47   state_machine();
48     //!< sets up the machine in a blank state.
49
50   state_machine(const state_machine &to_copy);
51     //!< copies the machine provided in "to_copy".
52
53   virtual ~state_machine();
54
55   DEFINE_CLASS_NAME("state_machine");
56
57   state_machine &operator =(const state_machine &to_copy);
58     //!< assigns this to a copy of the machine provided in "to_copy".
59
60   virtual int update();
61     //!< this is the main implementation function provided by derived classes.
62     /*!< this is implemented by derived classes that want to perform an action
63     when the state machine is pulsed (see below in transition_map), which is
64     why it is not pure virtual; a state machine might still be useful as a
65     state tracking object rather than needing to implement extended
66     functionality.  this function is invoked whenever the state changes due to
67     a timed, range based or simple transition.  one must be careful when
68     servicing this transition not to enmesh oneself in a snarled invocation
69     situation; if make_transition or time_slice or pulse are invoked from this
70     update function and conditions are right for another transition, then the
71     update function will be re-entered recursively.  if the value returned
72     from update is non-zero, it is used to pulse the state machine again as a
73     new trigger value (this is safer than explicitly calling one of the
74     transition causing functions).  note that this assumes that zero is an
75     invalid trigger.  if your triggers include zero as a valid value, don't
76     try returning it through update; use pulse to force the triggering to
77     accept the invalid trigger instead. */
78
79   int current() const { return _current; }
80     //!< returns the current state.
81     /*!< NOTE: a zero value for a state means that it is uninitialized. */
82
83   int last() const { return _last; }
84     //!< returns the last active state.
85
86   int trigger() const { return _trig; }
87     //!< returns the trigger that caused this state.
88     /*!< this is only meaningful when the transition was caused by a range
89     transition.  if it was, then ranged() will return true. */
90
91   enum transition_types { SIMPLE, RANGE, TIMED };
92     //!< the three types of transitions supported.
93
94   bool simple() const { return _type == SIMPLE; }
95     //!< returns true if the last transition was a simple type.
96   bool ranged() const { return _type == RANGE; }
97     //!< returns true if the last transition was a ranged type.
98   bool timed() const { return _type == TIMED; }
99     //!< returns true if the last transition was a timed type.
100
101   void set_state(int new_current, int new_last, int trigger,
102           transition_types type);
103     //!< sets the current state to "new_current" and the previous state to "new_last".
104     /*!< the "trigger" causing the transition, if any, will be stored also.
105     the "type" of transition is stored also.  the time stamp for time spent in
106     the current state is reset.  be very careful with this; if the two states
107     do not conform to the legal transitions in your map, then the state
108     machine will not behave properly. */
109
110   timely::time_stamp start() const;
111     //!< start time for the current state.
112     /*!< this records how long we've been in this state. */
113
114   void set_name(const basis::astring &name);
115     //!< sets the name to be printed in any debugging information for "this".
116
117   basis::astring get_name() const;
118     //!< retrieves the object's current name.
119
120   void override_timing(int current, int next, int duration);
121     //!< modifies the recorded timing for timed transitions.
122     /*!< this overrides the transition_map's time-out value for the transition
123     between the states "current" and "next".  a time-out of "duration"
124     will be used instead of whatever was specified when the map was set
125     up.  to erase an override, use zero as the "duration". */
126
127   int duration_override(int current, int next) const;
128     //!< reports if there's a duration override for a timed transition.
129     /*!< this returns the amount of time that this particular state_machine is
130     allowed to exist in the "current" state before progressing to the "next"
131     state.  this has nothing to do with the transition_map; it is valid only
132     for this state_machine object.  zero is returned if no override exists. */
133
134 private:
135   friend class transition_map;
136     //!< manager buddy object.
137   int _current;  //!< the current state of the state machine.
138   int _last;  //!< the previous state for the state machine.
139   int _trig;  //!< the last trigger value, if _ranged is true.
140   transition_types _type;  //!< what kind of transition just occurred.
141   timely::time_stamp *_start;  //!< the time this state started.
142   basis::astring *_name;  //!< the name this state_machine reports itself as.
143   state_machine_override_array *_overrides;  //!< the timing overrides.
144
145   int duration_index(int current, int next) const;
146     //!< finds the index of a duration override in our list.
147     /*!< this locates the duration override specified for the transition
148     between "current" and "next".  it returns the index of that override, or
149     a negative number if the override is not found. */
150 };
151
152 //////////////
153
154 //! The transition_map manages state machines and causes state changes to occur.
155 /*!
156   The transition_map is a heavyweight class that is a repository for all
157   information about transitions and which manages pushing the state machines
158   through the proper states.
159
160   The transition_map guarantees these characteristics:
161
162     0) the below characteristics are checked (in validate) and no state
163        machine object is allowed to operate until they are satisfied,
164
165     1) the machine starts in the specified starting state,
166
167     2) the current state is always one that has been added and approved,
168
169     3) transitions are allowed between states only if the transition has
170        been added and approved,
171
172     4) the update() function is invoked every time the machine hits a
173        transition between states (even if it is a transition to the same
174        state),
175
176     5) range transitions are non-intersecting within one state,
177 *** 5 is unimplemented ***
178
179     6) all states are reachable from the starting state by some valid
180        transition, and
181
182     7) each state has no more than one timed transition.
183
184   if any of these conditions are violated, then validate() will fail.
185   the machine will also not operate properly (at all) until the conditions
186   are satisfied by validate().  the states and transitions should
187   thus be carefully examined before turning them into a state machine....
188 */
189
190 class transition_map : public virtual basis::root_object
191 {
192 public:
193   transition_map();
194   virtual ~transition_map();
195
196   // informational functions...
197
198   DEFINE_CLASS_NAME("transition_map");
199
200   bool valid() const { return _valid; }
201     //!< returns true if the transition_map is valid and ready for operation.
202     /*!< once the validate() call has succeeded and valid() is true, no more
203     configuration functions (see below) may be called until the reconfigure()
204     function is invoked. */
205
206   int states() const;
207     //!< returns the current number of states.
208
209   // validation functions...
210
211   enum outcomes {
212     OKAY = basis::common::OKAY,
213     DEFINE_OUTCOME(BAD_START, -49, "The start state has not been properly "
214         "specified"),
215     DEFINE_OUTCOME(OVERLAPPING_RANGES, -50, "The ranges overlap for two "
216         "transitions from a state"),
217     DEFINE_OUTCOME(UNREACHABLE, -51, "There is an unreachable state in the map")
218   };
219   basis::outcome validate(int &examine);
220     //!< checks to that all required transition conditions are satisfied.
221     /*!< OKAY is returned if they are and the map is then ready to operate.
222     other outcomes are returned if one or more of the conditions are not met:
223     BAD_START means that the starting state is badly specified.
224     OVERLAPPING_RANGES means that one state has two transitions that do not
225     have mutually exclusive ranges.  UNREACHABLE means that a state is not
226     reachable from the starting state.  for all of these cases, the "examine"
227     parameter is set to a state related to the problem. */
228
229   void reconfigure();
230     //!< puts the transition_map back into an unvalidated state.
231     /*!< this allows the characteristics of the map to be changed.  validate()
232     must be called again before resuming operation using this map. */
233
234   // configuration functions...
235
236   // NOTE: all of the functions below will fail if the transition_map has
237   // already been validated previously and reconfigure() has not been called.
238
239   // NOTE: a zero value for a state means that it is uninitialized.  thus, zero
240   // is never allowed as a value for a state or a transition endpoint.  zero is
241   // grudgingly allowed as a trigger value, although that interferes with the
242   // state_machine object's update() method.
243
244   bool add_state(int state_number);
245     //!< registers a legal state in the transition_map.
246     /*!< no action will be taken for any state until it is registered.  the
247     operation returns true for successful registration and false for errors
248     (such as when a state is already registered or is invalid). */
249
250   bool set_start(int starting_state);
251     //!< assigns a state as the first state.
252     /*!< if the "starting_state" does not already exist, it is an error and
253     false is returned. */
254
255   bool add_simple_transition(int current, int next);
256     //!< adds a transition between "current" and "next".
257     /*!< it is an error to use either an invalid "current" state or an invalid
258     "next" state.  these errors are detected during the validate() function.
259     this type of transition is unspecialized--it does not respond to triggers
260     and does not occur due to timing.  to make a state_machine undergo this
261     transition, make_transition() must be used. */
262     
263   bool add_range_transition(int current, int next, int low, int high);
264     //!< adds a transition that listens to triggers in the pulse() method.
265     /*!< this uses "low" and "high" as the inclusive range of triggers that
266     will cause a transition to the "next" state when a state_machine is pulsed
267     in the "current" state.  it is erroneous for these trigger values to
268     intersect with other values in the same "current" state. */
269   bool add_timed_transition(int current, int next, int duration);
270     //!< adds a transition that occurs after a timeout with no other activity.
271     /*!< adds a timed transition to the "next" state when the "current" state
272     has lasted "duration" milliseconds.  this relies on the time_slice function
273     being called periodically, with appropriate regularity for the specified
274     "duration" (e.g., if one's time-out is 100 ms, then one might want to call
275     time_slice() every 20 ms or so to ensure that the transition is at most 20
276     ms late in firing.  NOTE: this is not an argument for calling time_slice()
277     as fast as possible; it is an argument for realizing that the "duration"
278     must be carefully considered to meet one's timing deadlines). */
279
280   // transition functions...
281
282   // NOTE: all of these actions will fail if the transition_map has not been
283   // validated yet.
284
285   bool make_transition(state_machine &m, int next);
286     //!< changes the state to the "next" listed for "m" given the current state.
287     /*!< it is an error to make a transition that has not been specified
288     through an add_X() transition function (false is returned).  if the
289     transition succeeds, then the current_state will be "next". */
290
291   bool pulse(state_machine &m, int trigger);
292     //!< applies a "trigger" to possibly cause a range transition.
293     /*!< this causes the state_machine to accept the "trigger" as input and
294     perform at least one traversal of the transition_map.  if the trigger
295     value is found in one of the range transitions for the current state, then
296     the next state specified in that transition becomes the current state and
297     the update() function is invoked (and true is returned).  if the trigger
298     is not found in any range transition, then false is returned. */
299
300   bool time_slice(state_machine &m);
301     // allows the transition_map to process any timed transitions that may be
302     // required for the state_machine "m".  the return value is true if such
303     // a transition was found.
304
305   bool reset(state_machine &m);
306     // resets the state_machine to the starting state in the transition_map.
307     // the update function is NOT invoked at the time of the reset.  true is
308     // returned if the reset was successful; it would fail if the transition
309     // map has not been validated yet.
310
311 private:
312   bool _valid;  //!< records whether we've been validated or not.
313   int _start_state;  //!< remembers the default starting state.
314   state_machine_state_array *_state_list;
315     //!< the list of transitions between states.
316
317   bool check_overlapping(int &examine);
318     //!< a validation function that looks for erroneous range transitions.
319     /*!< this returns true if there are no overlapping ranges found in the
320     range transitions for each state. */
321
322   bool check_reachability(int &examine);
323     //!< returns true if all states are reachable from the starting state.
324
325   int state_index(int state_id) const;
326     //!< returns the index of "state_id" in states, if it exists.
327
328   int transition_index(int state_index, int next, int &start);
329     //!< locates a transition into "next" for a state in our list.
330     /*!< returns the index of a transition between the state at "state_index"
331     and the "next" state by starting the search at index "start".  if there
332     is no matching transition from the "start" index on in the transition
333     list, then a negative number is returned.  "start" is updated to point
334     to the index just after a found transition, or to some random number if
335     the index is not found. */
336
337   bool check_states();
338     //!< returns false if the current machine is hosed up.
339
340   // disallowed functions for now:
341   transition_map(const transition_map &);
342   transition_map &operator =(const transition_map &);
343 };
344
345 } //namespace.
346
347 #endif
348