I recently decided to take some time to learn about the new features in C++11 while working on a project at home. C++11 has added some really nice features such as native thread support, regular expressions, safe pointer types, and variadic templates. While working on my project, I found myself needing a flexible class which would allow me to express a finite state machine (FSM) without excessive sub-classing. I also wanted to be able to select the types for states and events (transitions), which lead me down the path of developing a state machine template class. I wanted to be able to make defining a FSM as easy as the tradition C state table driven model but with better lookup times. Additionally, the class should support event callbacks should you choose to define one. The following example shows a state machine which uses std::string as the state and event. These could easily be replaced by an enum of states and enum of events.
#include "state_machine.h"
typedef state_machine<std::string,std::string> str_state_machine;
void my_enter_radio(str_state_machine::state_ptr state){
std::cout << __FUNCTION__ << " leaving [" << state->get_id() << "]" << std::endl;
}
void my_exit_radio(str_state_machine::state_ptr state){
std::cout << __FUNCTION__ << " leaving [" << state->get_id() << "]" << std::endl;
}
void my_enter_cdplayer(str_state_machine::state_ptr state){
std::cout << __FUNCTION__ << " entering [" << state->get_id() << "]" << std::endl;
}
void my_exit_cdplayer(str_state_machine::state_ptr state){
std::cout << __FUNCTION__ << " entering [" << state->get_id() << "]" << std::endl;
}
void my_event_action(str_state_machine::state::event_ptr event,
str_state_machine::state_ptr current_state,
str_state_machine::state_ptr next_state)
{
if( current_state == next_state )
std::cout << "Action: [" << event->get_id() << "] " << "No State Change" << std::endl;
else
std::cout << "Action: [" << event->get_id() << "] " << current_state->get_id() << " --> " << next_state->get_id() << std::endl;
}
int main() {
str_state_machine fsm;
// Setup state transitions for radio
fsm.add_state("radio")
->bind_entry_action(my_enter_radio)
->bind_exit_action(my_exit_radio)
->add_event("switch_radio");
fsm.add_state("radio")->add_event("switch_cd","cdplayer")->bind_action(my_event_action);
fsm.add_state("radio")->add_event("next")->bind_action(my_event_action);
fsm.add_state("radio")->add_event("previous")->bind_action(my_event_action);
// Setup state transitions
fsm.add_state("cdplayer")
->bind_entry_action(my_enter_cdplayer)
->bind_exit_action(my_exit_cdplayer)
->add_event("switch_cd");
fsm.add_state("cdplayer")->add_event("switch_radio","radio")->bind_action(my_event_action);
fsm.add_state("cdplayer")->add_event("next")->bind_action(my_event_action);
fsm.add_state("cdplayer")->add_event("previous")->bind_action(my_event_action);
fsm.dump_state_table();
fsm.next_state("next");
fsm.next_state("previous");
fsm.next_state("switch_cd");
fsm.next_state("next");
fsm.next_state("previous");
fsm.next_state("switch_radio");
fsm.next_state("next");
fsm.next_state("previous");
}
Code language: PHP (php)
This code results in the following output:
This output shows the all of the states and events as well as if the state is an accepted state or a terminal state. Accepted state can be used for pattern parsing and terminal state means there are no transitions out of that state. The bottom half of the output shows the callbacks function output. The callbacks can be implemented in multiple functions or a single function depending on one’s needs.
The event callback function has the following definition:
void my_event_action(state_machine<states,events>::state::event_ptr event,
state_machine<states,events>::state_ptr current_state,
state_machine<states,events>::state_ptr next_state);
Code language: CSS (css)
The entry/exit callback function has the following definition:
void my_enter_exit_function(state_machine<states,events>::state_ptr state);
Code language: HTML, XML (xml)
Lookup times are improved by relying on std::set<state> and std::set<event> which are internally nested. The only the state_machine class can create instances of the state_machine::state class and only the std_machine::state class can crate instances of the state_machine::state::event class.
template <typename state_id_type,typename event_id_type>
class state_machine {
private:
struct _state_comparer;
public:
typedef state_machine<state_id_type,event_id_type>* state_machine_ptr;
// State Class Definition
class state {
friend state_machine;
typedef state* state_ptr;
struct _event_comparer;
public:
// Transition Class Definition
class event {
friend state;
typedef event* event_ptr;
// Public Member Functions
public:
// Returns the current event id
event_id_type get_id() const;
// Returns the state transition associated with the event
state_ptr get_state() const;
// Return true if action has been defined
bool has_action() const;
// Bind action to this event
void bind_action(std::function<void(event_ptr,state_ptr,state_ptr)> action);
// Private Member Functions
private:
event(event_id_type event_id, state_ptr target_state);
~event();
// Private Types
private:
event_id_type _id;
state_ptr _state;
std::function<void(event_ptr,state_ptr,state_ptr)> _action;
};
typedef event* event_ptr;
// Private Member Type Definitions
private:
struct _event_comparer {
bool operator()(const event_ptr lhs, const event_ptr rhs) const {
return rhs->_id < lhs->_id;
}
};
typedef std::set<event_ptr,_event_comparer> event_set;
// Public Member Functions
public:
state_id_type get_id() const;
bool is_accepted() const;
bool is_terminal() const;
// Creates a null next event
event_ptr add_event(event_id_type event_id);
event_ptr add_event(event_id_type event_id, state_id_type next_state, bool accepted = false);
event_ptr get_event(event_id_type event_id) const;
bool has_entry_action() const;
bool has_exit_action() const;
state_ptr bind_entry_action(std::function<void(state_ptr/*current_state*/)> entry_action);
state_ptr bind_exit_action(std::function<void(state_ptr/*next_state*/)> exit_action);
const event_set& get_events() const;
// Private Member Function
private:
state(state_machine* parent, state_id_type state_id, bool accepted);
~state();
void _do_action(event_ptr event);
typename event_set::const_iterator _find_event(event_id_type event_id) const;
typename event_set::iterator _find_event(event_id_type event_id);
// Private Types
private:
state_machine* _parent; // Pointer to parent
state_id_type _id;
bool _accepted;
event_set _events;
std::function<void(state_ptr/*current_state*/)> _entry_action;
std::function<void(state_ptr/*next_state*/)> _exit_action;
};
typedef state* state_ptr;
// Private Member Type Definitions
private:
struct _state_comparer {
bool operator()(const state_ptr lhs, const state_ptr rhs) const {
return rhs->_id < lhs->_id;
}
};
typedef std::set<state_ptr,_state_comparer> state_set;
// Public Member Functions
public:
state_machine();
~state_machine();
state_ptr add_state(state_id_type state_id, bool accepted = false);
state_ptr get_state(state_id_type state_id) const;
state_ptr get_current_state() const;
state_ptr get_initial_state() const;
state_ptr next_state(event_id_type event_id) throw(std::runtime_error);
state_ptr reset();
const state_set& get_states() const;
void dump_state_table();
// Private Member Functions
private:
typename state_set::const_iterator _find_state(state_id_type state_id) const;
typename state_set::iterator _find_state(state_id_type state_id);
// Private Types
private:
state_set _states;
state_ptr _initial;
state_ptr _current;
public:
};
Code language: PHP (php)
Hope this simple state machine can help someone from having to recreate the wheel. You can download the source here.