jQuery in Action, 3rd edition
The moose likes OO, Patterns, UML and Refactoring and the fly likes Finite state machine implementation Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login

Win a copy of Java Interview Guide this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Engineering » OO, Patterns, UML and Refactoring
Bookmark "Finite state machine implementation" Watch "Finite state machine implementation" New topic

Finite state machine implementation

Federico Minarelli

Joined: Jan 16, 2010
Posts: 29
Hi everybody! I would like to ask your suggestions on how to best solve the following problem.

I have to implement something which actually is a finite state machine, in which the transitions are driven by several messages (unfortunately such messages don't share any common interface, and they have each a lot of fields whose values can lead to different states). The problem is very similar to that exposed in the chapter of "Head 1st Design Patterns" explaining the State pattern. The biggest difference with such example is that, in my case, I will have really a lot of States each driven by a different value of a message's field.

For example, consider that the state machine models a RescueTaxi (that is not actually my case, but I tried to make an example which could be as similar as possible to mine). By "rescue taxi" I mean a taxi which can also act as an ambulance (I used a bit of fantasy here! ). Possible incoming messages for a RescueTaxi are TransportOrder with fields [StartPosition, DestinationPosition, ID, Status={Startable, Started, Cancelled}], which represent an Order for a Taxi to drive a passeger from X to Y, EmergencyOrder [StartPosition, DestinationPosition, ID, Status={Startable, Started, Cancelled}, Priority={High, Low, Medium}] and so on. (Please ignore the fact that the messages in this example are almost identical, in the real case they share only a few fields, and I have no control over such messages). Now, my RescueTaxi state machine can have a lot of states, for example:
-Initial (Taxi is parked somewhere and waits for an order)
- TransportOrderStartableReceived (taxi sends an ACK for the order or decides to refuse the job)
- TransportOrderStartedReceived (taxi can now drive towards its StartPosition)
- TransportOrderCancelled (taxi is notified about the Transport Order's cancellation and drives back to the parking (Initial state))
- EmergencyOrderStartableReceived((taxi sends an ack for the emergency order)
- EmergencyOrderStartedLowPriorityReceived (taxi can drive at normal speed towards its start postion)
- EmergencyOrderStartedMediumPriorityReceived (taxi is allowed to drive fast to the start position, but without using the alarm)
- EmergencyOrderStartedHighPriorityReceived (taxi is allowed drive fast towards its start position and to switch the alarm on), etc..

Now, if I follow the State pattern alone, I will need all the above mentioned states (and much more!).. On the other side, in general, building a State hierarchy is not a solution: i.e. imagine that the RescueTaxi has to react differently to an EmergencyOrder 's cancellation (e.g according to the priority and the current state it can decide to drive the patient to its destination): in such case, having just an EmergencyOrderStartedReceived state would lead to something like a switch (priority) {} to choose which will be the next state (thus erasing the benefits of the State pattern)...

My question is hence: what would be in your opinion a good solution to this kind of problems?

Thank you very much!
Federico Minarelli

Joined: Jan 16, 2010
Posts: 29
hi all!
I think I solved my problem but I´d kindly like to ask your suggestions about another point. "Head 1st Design Pattern" suggests to implement the "State Pattern" by defining a State interface:

And each class implementing State looks something like this:

The FSM looks like this:

Now, I`d like to distinguish between Transitory States and Final States (states which cannot be leaved). Imagine the FSM represents a computation: it would be nice to store the computation`s result into a FinalState (eg: Success/Error).. Hence, a FinalState would be similar to a State, with the addition of 2 more methods:

Let`s imagine for a moment that something like this would be the solution:

The FSM should have now 2 new States:

The method StateAImpl#onEventY() would now look like this:

And finally, a client of the FSM would have to do something like this:

Now my question: what do you think of this design? I think it could be done much better: both the use of the instanceof operator (inheritance) and the if (fsm.getCurrentState().equals(fsm.getSuccessState()){} (what if I have 1000 final states possible?) are for me "bad smells".. The problem is: until now I couldn't find a better solution.. May you help me with new ideas please?

Thanks a lot! Bye,
I agree. Here's the link: http://aspose.com/file-tools
subject: Finite state machine implementation
It's not a secret anymore!