Design Pattern problem involving N states and transitions between them

Question

I have a problem at hand and I am not getting which design pattern to use. The problem goes as such:

I have to build a system which has 'N' states and my system has to do a transition from any state to any other state depending on some conditions. Ex: On condition 1, movement from State 1 to 3 and on condition 2 from state 1 to 4.

Even the transition from one state to other state can be done on 2 or more different conditions.

For example, transition from State 1 to state 3 can be done when:
condition 1 : "Its a Sunday"
condition 2: "Its Raining"
condition 3: "Its Raining and Sunday"
In each condition, the processing at State 3 can be different.

I hope I was able to understand the problem legibly. Kindly help.

Thanks a lot

Answer 1

Its clearly a case of a finite-state-machine but its better to combine the conditions rather than create a new condition for each combination. I didn't like the Java example for State pattern on Wikipedia as states know about other states which wouldn't make sense in a lot of scenarios. A transition table that keeps a track of the from state, applicable condition(s), and to state, helps take care of that problem.

My two cents for an object oriented-finite-state-machine. There are improvements you could do on the OO front, but it gets the idea across.

class Transition {
    State from;
    Set<Condition> conditions;
    State to;
}

class State {
    String state;
}

class Condition {
    String condition;
}

The state machine can be constructed with the above types. There is no error checking, but you could throw an exception or something if no next state is found for some conditions.

class StateMachine {
    List<Transition> transitions;
    State current;

    StateMachine(State start, List<Transition> transitions) {
        this.current = start;
        this.transitions = transitions;
    }

    void apply(Set<Condition> conditions) {
        current = getNextState(conditions);
    }

    State getNextState(Set<Condition> conditions) {
        for(Transition transition : transitions) {
            boolean currentStateMatches = transition.from.equals(current);
            boolean conditionsMatch = transition.conditions.equals(conditions);
            if(currentStateMatches && conditionsMatch) {
                return transition.to;
            }
        }
        return null;
    }
}

And a test run:

Edit: With some more transitions and new states based on your comment:

State one = new State("one");
State two = new State("two");
State three = new State("three");

Condition sunday = new Condition("Sunday");
Condition raining = new Condition("Raining");
Condition notSunday = new Condition("Not Sunday");
Condition notRaining = new Condition("Not Raining");

List<Transition> transitions = new ArrayList<Transition>();
transitions.add(one, new Set(sunday), three);
transitions.add(one, new Set(sunday), two); // <<--- Invalid, cant go to two and three
transitions.add(one, new Set(raining), three);
transitions.add(one, new Set(sunday, raining), three);
transitions.add(one, new Set(notSunday, notRaining), three);

StateMachine machine = new StateMachine(one, transitions);
System.out.print(machine.current); // "one"
machine.apply(new Set(sunday, raining));
System.out.print(machine.current); // "three

I had a bitter experience with using a state machine for a fairly large project. The problem was with composite states. Just like the composite condition you mentioned (sunday and raining), there could technically be composite states which could further be broken down into unit states. This may or may not be the case in your situation, but still worth mentioning. If that is the case, it's best to modify the classical finite state machine and use a set of states instead of a single state to represent the from and to states. If your N is large, this will help keep sanity levels intact. Think hotmail folders vs gmail tags. The transition table would then be presented as

Transition(Set<State> from, Set<Condition> conditions, Set<State> to)

Answer 2

This sounds like the typical use for a finite state machine

in short, the state machine describes the various states in which your system can be, and under which conditions it can go from state to state. A state machine is described exactly as your English description. And it can be formally described using state diagrams

in code you could make a state machine like this:

 enum State { Init, ShowMenu, ShowMsg, DisplayVideo, Exit };
 State state = State.Init;

 while (state != State.Exit)
 {
      switch(state)
      {
           case State.Init:
                init();
                state = State.ShowMenu;
                break;
           case State.ShowMenu:
                if(lastMenuItemSelected==1) state = State.ShowMsg;
                if(lastMenuItemSelected==2) state = State.DisplayVideo;
                break;
           case State.ShowMsg:
                ....
                break;
           ....
 }

I'm not sure if I got the exact syntax correct for Java...I'm more into C#

Answer 3

won't the state pattern do the work?

Answer 4

As others have said a state machine can be modelled in procedureal code with a switch or in OO code with the state pattern, which is probably what you were after.

However a 3rd way is to actually code it as a graph, with states as nodes and conditions as directed edges. The visitor pattern can then be used to apply the graph to different uses. this would lend itself particularly well to designs where the states and/or the transitions could be user defined, but would probably be more memory intensive then the hard coded state machines described in the other answers.

Answer 5

State design pattern works on the concept of state change. Entire process life-cycle can be divided in multiple phases.With completion of each phase process exits from one state and enters in to another state.

For example In JSF framework entire web request response lifecycle is divided in six phases:

After completion of every phase process exits from a state and enters into another state. For example after RestoreValuePhase we can say ViewRestored as exit state and RequestApply as entering state .

So to implement State design pattern It is required to divide entire process in such a way that It can be processed in multiple phases with every phase exit defining a state change.

Now let's understand this with below code.

Any project lifecycle can be divided in multiple phases like

requirementAssessment
Design
Development
QualityAssessment
Deploy
Closure

So these are the phases used in below example

Rules :

1. We need to define a class where we can store the current state of the process. NextPhase class in below code is doing that.

2. We need to define an Interface wherein we can provide the contact method that would be implemented in each phase.In below code ProjectPhase is doing that.

Learn more about State design pattern here -- State Design Pattern

http://efectivejava.blogspot.in/2013/09/java-state-design-patten-oops-state.html?utm_source=BP_recent

Answer 6

The first thing I noticed about your example was that State 3 = (State 1 == true && State 2 == true). This will not scale very well as more possible states become involved. If you are only considering whether it is raining or whether it is Sunday, you can have an enumeration like this, with 4 possible types:

enum State { CLEAR_OTHER_DAY, RAINING_OTHER_DAY, CLEAR_SUNDAY, RAINING_SUNDAY }

This would allow you to state conditions cleanly in a switch block when it is time to code. But if you have to also consider whether it is warm outside, you have to add 4 more values to that enum to capture all possible conditions. And later in your project, your code may need to capture more conditions than you currently envision.

As for a design pattern, the State pattern and its Java example on Wikipedia look like a good place to start.

Wikipedia's example has a StateContext class with a method called setState that takes in a name. I thought about suggesting that you add the state determination logic here, but that would make your StateContext class need to get too close to the implementation details of your other classes. It would be better to put a method for determining the system's state in a class that would easily know the conditions for going from one state to another. This way, if your project needs to change in the future and you either have more states to keep track of or different conditions, you only need to maintain the logic in one place.