C++ state design pattern with multiple state machines

Question

Hi, I have a C++ state machine implemented using the State design pattern. Each state is implemented as a nested friend class of the context class.

class Context {
public:
  /* The Context class' user calls process1() to get it to perform an action */
  void process1();

private:
  class IState;

  void switchState( IState *newState );

  class IState {
    virtual void doProcess( Context &context ) = 0;
  };

  class StateA : public Context::IState {
    void doProcess( Context &context );
  };
  friend class StateA;

  class StateB : public Context::IState {
    void doProcess( Context &context );
  };
  friend class StateB;
  .
  .
  .
  class StateJ : public Context::IState {
    void doProcess( Context &context );
  };
  friend class StateJ;
};

Currently, a successful iteration of the state machine runs from Context::StateA to Context::StateJ when Context::process1() is called but some of the states contain internal logic to determine whether to loop back to an earlier state. So a typical execution will look like:

StateA
StateB
StateC
StateD
StateE
StateC
StateD
StateE
StateF
StateG
StateH
StateI
StateJ

The internal logic to determine next state is currently being implemented by the respective state itself by storing data in the context object. What I need to do now is add a Context::process2() option that significantly differs in the order of execution of states. Of course, this can be done using flags that are set in the context object but I was wondering if there is better way to implement this; maybe even use this method to rewrite the handling of state switches within Context::process2().

The Visitor design pattern might do the trick but I'm not sure whether its intended for implementing state machines. When using Visitor, process1() could contain all logic for the order of execution of states and then just call each state in that order. Similarly, process2() would handle all of its own logic.

Thanks in advance for your answers.

• Ashish.

EDIT:

To those of you that replied saying I should be creating a separate state machine, the reason I'm looking to avoid that is because the code for the states used by the second state machine is identical to those in the first; only the progression is different.

The second state machine will go through the following state transitions:

StateA
StateB
StateC
StateJ

So I'm trying to eliminate duplicated code.

Answer 1

This snippet is not compiling.

private:
    class IState;
    void switchState( IState *newState );

    class IState {
        virtual void doProcess( Context &context ) = 0;
    };

BTW, you can rely on template specialization for the doProcess() implemetation of the various States like that:

class Context
{
public:
    class IState;
    void switchState( IState *newState );

    class IState {
        virtual void doProcess( Context &context ) = 0;
    };

    template<typename T>
    class StateA : public Context::IState {
    public:
        void doProcess( Context &context );
    };

    template<typename T>
    class StateB : public Context::IState {
    public:
        void doProcess( Context &context );
    };

    template<typename T>
    class StateJ : public Context::IState {
    public:    
        void doProcess( Context &context );
    };

public:
    /* The Context class' user calls process1() to get it to perform an action */
    template<typename T>
    void process()
    {
        StateA<T> a;
        a.doProcess(*this);
    }
};

struct Process1
{
};

struct Process2
{
};

void main(int, char **)
{
    Context c;
    c.process<Process1>();
    c.process<Process2>();
}

Moreover, you get a generic State machine, provided you keep the samenumber of states.

Answer 2

I assume that in your code, switchState is invoked by the individual states when it's time to transition to something else. Something like this:

void StateA::doProcess(Context& context) {
   context.switchState(new StateB()); // NOTE: potential leak!
}

Is this the case?

If so, one thing you might consider is having the states return transition objects that abstractly represent a control point in your state graph. You then have the Context run a loop which executes the states, retrieves the resulting transitions, and maps the transitions to the appropriate next states for whatever process you have. The transition map can be set up differently for each process method that you have.

Pros:

• States don't have to know about each other. The transition is their declaration to the world of what they've done. It's up to the context to route between the states in appropriate ways. This could make the states reusable across different Context objects, for example.
• Allows the idea of "same structure, slightly different behavior" by allowing the context to essentially maintain the same state graph, but plug in a slightly different state with a compatible transition interface as the target of a particular transition.

Cons:

• Adds an extra layer of stuff to set up. Transition mapping code is mostly boilerplate. Tools to generate the boilerplate may help.
• Doesn't help you if you really want to do something radically different in the two processes which the states don't have the right transitions to support – but then, you're trying to reuse at the wrong level – you probably want different state objects at that point.

EDIT: Sample code is up at http://pastebin.com/eBauP060 .

Answer 3

Holy crap. Why use C++ classes for this? A giant graph of goto statements would be cleaner code.

Answer 4

Kudos for trying to do something difficult, do it right, and make it DRY!

As tomekszpakowicz pointed out, if you have different transitions between states, then you have different state machines. Each "process" you refer to sounds like a different state machine to me.

If you specify transitions within the states, then you'll need separate states for each machine. If you want to reuse code in the states, then extract common functionality out of the states and into reusable state representations.

If you specify transitions outside of the states, then the states themselves can be reused from one machine to another; you'll just need to specify different transitions for each state. You may find that you have to dynamically build the state machine--that is, at compile time, you have a bunch of states and transitions that are available to the machines. In the build routine of the machine, you can wire all that together by creating the instances of the states and transitions. (All of this is kind of hard, imo.)

Answer 5

You might want to use one or combination of several techniques to reduce duplication. For example:

1. If you have some complicated processing within each state event handler methods, move this processing to Context.

   Or even better, create third class X (I don't know how to call it. Maybe Driver? Any suggestions? Or maybe this class should be called Context, and Context should be called SomeStateMachine?) which will contain all common data and methods that change it.

   Then within each state's doProcess method you will only:

   • Check input

   • Call the right method of X

   • Change state, possibly based on return value from previous step.

   This way your state machine will be responsible only for calling right method and switching to right state. All the rest will be somewhere else.

2. Instead of switching states like this:

   context.switchState(new StateB());
   

   make your states stateless---no instance fields, only methods. Then create set of static instances within Context, one for each IState subclass. That way you avoid allocating all those object's:

   context.switchState(&Context::StateBInstance);
   

   Now even better. You can create fields in Context holding IState instances. Which instance will be decided during state machine construction. This'll let you wire up your state machine at runtime.

   void Context::Context()
   {
     theStateThatComesAfterA = &StateBInstance;
     // [...]
   }
   
   
   void AnotherContext::AnotherContext()
   {
     theStateThatComesAfterA = &StateCInstance;
     // [...]
   }
   
   
   void StateA::doProcess(Context& context)
   {
     context.DoSomething();
     // [...]
     context.switchState(context.theStateThatComesAfterA);
   }
   

---

One final note. Don't get carried away in this generalization thing. Remember. Sometimes similarities within code indicate repetition that should be eliminated. But quite often we look too hard and generalize based on purely accidental similarity of two concepts. Then, when during evolution of the design those concept start to diverge, it is very hard to change the code because of strong coupling of unrelated things.

In general this is designer's call. You need to look at your particular requirements and constraints, and choose right techniques. That's why this state machine design pattern (and many others) is a design pattern, not a library class.