Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Coding the Driver
In addition to coding the individual states as classes, you also need to create a driver for the class. Like the states, the driver is derived from a class in the framework. Here’s a sample driver; first, the class definition:
class Calculator : public FSMDriver {
public:
queue<CalcStackItem *> PostFixQueue;
stack<char> OperatorStack;
FSMState<Calculator> *start;
Calculator();
void Run(char *chars, FSMState<Calculator> *StartState);
double Perform();
};
This class includes special members for the particular state machine I’m building, a calculator. It also includes an overloaded Run method that actually runs the state machine (although all it really does is call the Run method in the base class and catch exceptions for invalid states). Finally, it includes a Perform method that does the final calculation. Of course, I’m only showing the declarations for the functions. Listing 1 shows the entire code for the Calculator state machine; after that, I’ll show the base classes that make this all work.
Listing 1 The custom state and driver classes.
#include <string>
#include <iostream>
#include "fsm.hpp"
#include <stack>
#include <queue>
#include <exception>
#include <math.h>
using namespace std;
struct CalcStackItem {
enum {number, op} itemtype;
double numbervalue;
char opchar;
CalcStackItem(double anumbervalue) {
itemtype = number;
numbervalue = anumbervalue;
}
CalcStackItem(char aopchar) {
itemtype = op;
opchar = aopchar;
}
};
// Your own driver class that contains
// data available to the state objects.
class Calculator : public FSMDriver {
public:
queue<CalcStackItem *> PostFixQueue;
stack<char> OperatorStack;
FSMState<Calculator> *start;
Calculator();
void Run(char *chars, FSMState<Calculator> *StartState);
double Perform();
};
// State: Start
class StartState : public FSMState<Calculator> {
public:
StartState(Calculator *adriver) : FSMState<Calculator>(adriver, "StartState") { }
void OnEntry() {
cout << driver->getCharString() << endl;
}
FSMStateBase *HandleEvent() {
if (isIn("01234567890.")) {
return driver->getState("NumberEntryState");
}
}
};
// State: NumberEntry
class NumberEntryState : public FSMState<Calculator> {
protected:
string accum;
public:
NumberEntryState(Calculator *adriver) :
FSMState<Calculator>(adriver, "NumberEntryState") { }
void OnEntry() {
Append();
}
FSMStateBase *HandleEvent() {
if (isIn("01234567890.Ee")) {
Append();
return this;
}
else if (isIn("+-*/")) {
ParseAndPush();
return driver->getState("OperatorState");
}
else if (isIn("=")) {
ParseAndPush();
return driver->getState("EqualsState");
}
else {
return driver->getState("ErrorState");
}
}
void Append() {
accum += Current;
}
void ParseAndPush() {
double x = strtod(accum.c_str(), NULL);
accum = "";
driver->PostFixQueue.push(new CalcStackItem(x));
}
};
// State: Operator
class OperatorState : public FSMState<Calculator> {
protected:
string accum;
map<char,int> OpOrder;
public:
OperatorState(Calculator *adriver) : FSMState<Calculator>(adriver, "OperatorState") {
OpOrder[’+’] = 0;
OpOrder[’-’] = 0;
OpOrder[’*’] = 1;
OpOrder[’/’] = 1;
}
void OnEntry() {
if (driver->OperatorStack.size() == 0) {
driver->OperatorStack.push(Current);
}
else {
while (driver->OperatorStack.size() > 0 &&
(OpOrder[driver->OperatorStack.top()]) >= (OpOrder[Current])) {
driver->PostFixQueue.push(
new CalcStackItem(driver->OperatorStack.top()));
driver->OperatorStack.pop();
}
driver->OperatorStack.push(Current);
}
}
FSMStateBase *HandleEvent() {
if (isIn("01234567890.")) {
return driver->getState("NumberEntryState");
}
else {
return driver->getState("ErrorState");
}
}
};
// State: Equals
class EqualsState : public FSMState<Calculator> {
public:
EqualsState(Calculator *adriver) : FSMState<Calculator>(adriver, "EqualsState") { }
void OnEntry() {
// Finish up grabbing the operators
while (driver->OperatorStack.size() > 0) {
char op = driver->OperatorStack.top();
driver->OperatorStack.pop();
driver->PostFixQueue.push(new CalcStackItem(op));
}
cout << driver->Perform() << endl;
driver->OperatorStack.empty();
driver->PostFixQueue.empty();
}
FSMStateBase *HandleEvent() {
if (isIn("01234567890.")) {
return driver->getState("NumberEntryState");
}
else {
return driver->getState("ErrorState");
}
}
};
// State: Error
class ErrorState : public FSMState<Calculator> {
public:
ErrorState(Calculator *adriver) : FSMState<Calculator>(adriver, "ErrorState") { }
void OnEntry() {
cout << " Syntax Error" << endl;
}
FSMStateBase *HandleEvent() {
return NULL;
}
};
Calculator::Calculator() : FSMDriver() {
start = new StartState(this);
new NumberEntryState(this);
new OperatorState(this);
new EqualsState(this);
new ErrorState(this);
}
void Calculator::Run(char *chars, FSMState<Calculator> *StartState) {
try {
FSMDriver::Run(chars, StartState);
}
catch (StateNameException e) {
cout << "Invalid state name: " << e.getMessage() << endl;
}
}
double Calculator::Perform() {
stack<double> holder;
CalcStackItem *item;
double result;
while (PostFixQueue.size() > 0) {
item = PostFixQueue.front();
PostFixQueue.pop();
if (item->itemtype == CalcStackItem::number) {
holder.push(item->numbervalue);
}
else {
double second = holder.top();
holder.pop();
double first = holder.top();
holder.pop();
switch (item->opchar) {
case ’+’:
result = first + second;
break;
case ’-’:
result = first - second;
break;
case ’*’:
result = first * second;
break;
case ’/’:
result = first / second;
break;
}
holder.push(result);
}
}
result = holder.top();
return result;
}
int main(int argc, char *argv[])
{
Calculator calc;
calc.Run("10+5-3*2=2*3*4=", calc.start);
cout << "===============" << endl;
calc.Run("2*2+3*4=", calc.start);
cout << "===============" << endl;
calc.Run("1+2q", calc.start);
cout << "===============" << endl;
calc.Run("6.02e23/153.25=", calc.start);
cout << "===============" << endl;
return 0;
}
The classes in this file include those that I already mentioned, plus a few other state class that I described in the earlier table.
Now for the framework. This code is actually not very long, but is divided between a header file and a code file. Listing 2 shows the header file.
Listing 2 The state machine header file, fsm.hpp.
#include <string>
#include <map>
class StateNameException {
protected:
std::string msg;
public:
explicit StateNameException(const std::string& amsg) : msg(amsg) {};
std::string getMessage() const { return msg; }
};
class FSMStateBase;
class FSMDriver {
private:
std::map<char *, FSMStateBase *> States;
protected:
char Current;
char *CharString;
FSMStateBase *CurrentState;
public:
~FSMDriver();
void addState(FSMStateBase *state, char *name) {
States[name] = state;
}
char *getCharString() { return CharString; }
virtual void Run(char *chars, FSMStateBase *StartState);
FSMStateBase *getState(char *name) {
FSMStateBase *res = States[name];
if (res != NULL) {
return res;
}
else {
throw StateNameException(name);
}
}
};
class FSMStateBase {
protected:
friend class FSMDriver;
FSMStateBase() {}
virtual void OnEntry() = 0;
virtual FSMStateBase *HandleEvent() = 0;
char Current;
};
template <typename T>
class FSMState : public FSMStateBase {
protected:
T *driver;
char *name;
friend class FSMDriver;
FSMState(T *adriver, char *aname) : name(aname), driver(adriver) {
driver->addState(this, name);
}
bool isIn(char* str) {
return (memchr (str, Current, strlen(str)) >= str);
}
public:
virtual void OnEntry() {}
virtual FSMStateBase *HandleEvent() {}
};
Listing 3 shows the code file, which contains a couple of the methods for the FSMDriver class:
Listing 3 The code for the state machine, fsm.cpp.
#include "fsm.hpp"
FSMDriver::~FSMDriver() {
// Collect the garbage
std::map<char *, FSMStateBase *>::iterator iter = States.begin();
while (iter != States.end()) {
FSMStateBase *state = iter->second;
delete state;
iter++;
}
}
void FSMDriver::Run(char *chars, FSMStateBase *StartState) {
int i;
int len = strlen(chars);
CharString = chars;
FSMStateBase *NextState;
CurrentState = StartState;
StartState->OnEntry();
for (i=0; i < len; i++) {
Current = chars[i];
CurrentState->Current = Current;
NextState = CurrentState->HandleEvent();
if (NextState == NULL) {
return;
}
if (NextState != CurrentState) {
CurrentState = NextState;
CurrentState->Current = Current;
CurrentState->OnEntry();
}
}
}
The header file contains four classes:
- StateNameException is a small exception class. When the driver encounters a name of a state that doesn’t exist, it throws an exception of this class.
- FSMDriver is the main driver class. To use it, your best bet is to derive a new class from it, as I did in the preceding example; then call addState, passing instances of your state classes. Finally, call its Run method, passing the string of events along with the starting class.
- FSMStateBase is the base class for all states. It actually serves as a "technicality" because I wanted to create my state class as a template, wherein the template parameter is the driver class. But the driver class contains a map of the state classes, which makes a bit of a circular chicken-and-egg problem. To fix the problem, I started with a non-template base class for the states, FSMStateBase. The driver uses this base class for its members, and the template class is derived from this class, thus solving the problem.
- FSMState is the base of all the states; as I mentioned, it’s a template that’s derived from the FSMStateBase class. This class includes a pointer to the driver class.
Before moving on, I want to explain just a tad more about the FSMState class being a template class. The reason I made it a template is so that when you derive your classes from it, you can specify your own driver class, thus alleviating the need to do a dangerous downcast. What do I mean by that? Suppose I didn’t use the templates, and instead had two classes like this:
class FSMDriver2 {
public:
int value;
};
class FSMState2 {
public:
FSMDriver2 *driver;
};
Now suppose that you derive a class from each of these—your own driver class and a state class:
class MyDriver : public FSMDriver2 {
public:
int somedata;
};
class MyState1 : public FSMState2 {
void foo() {
driver->somedata = 10;
driver->value = 20;
}
};
Your driver class contains some data specific to your own state machine. That’s where the problem comes in. Look at how I’m trying to access the data in the state class:
driver->somedata = 10;
That won’t work. You’ll get a compile error because, as far as the compiler is concerned, the driver member points to an instance of the base FSMDriver2 class, even though most likely you created an instance of your derived class and stored its address in the driver variable, like so:
void test() {
MyDriver dr;
MyState1 st;
st.driver = &dr;
}
Really, the driver instance does have a somedata member. But the compiler doesn’t know that. To fix this, you could do a downcast, like so:
class MyState1 : public FSMState2 {
void foo() {
((MyDriver *)driver)->somedata = 10;
}
};
But that’s considered a dangerous practice because the compiler will create code that forces a cast, even if driver ends up pointing to some class other than MyDriver (that is, to some other class derived from FSMDriver2). Of course, in this code, we know what driver points to, but nevertheless, doing such a cast is considered poor coding practice. You could also use the static_cast operator in C++, but the effect will be pretty much the same.
In addition to being bad coding style, such casts also make the code more cumbersome to use; frankly, it would be a pain to always have to cast the driver member each time you use it. Instead, I decided on an alternative approach—a template. If I use a template, I could simply specify the type when I create the class, and then from there easily access the members. Thus, the short example would turn into this:
class FSMDriver2 {
public:
int value;
};
template<typename T>
class FSMState2 {
public:
T *driver;
};
class MyDriver : public FSMDriver2 {
public:
int somedata;
};
class MyState1 : public FSMState2<MyDriver> {
void foo() {
driver->somedata = 10;
driver->value = 20;
}
};
void test() {
MyDriver dr;
MyState1 st;
st.driver = &dr;
}
This code compiles and runs. And the cool thing is that I can access members of both my own driver class plus its base class, FSMDriver2, without having to do any casts, as you can see in the foo member function of the state class. And further, since my state class is derived from a template class but is not itself a template class, I don’t need to use templates when I put the class to use, as the test function shows. This template approach is exactly what I did in the framework.
Now I want to give more details about the other template issue, where I created a base class. Continuing with these short sample classes, suppose I want to put a map inside the FSMDriver2 class containing instances of the state classes, something like this:
class FSMDriver2 {
public:
int value;
std::map<char *, FSMState2<T> *> States;
};
Of course, this won’t compile, because T doesn’t mean anything inside the FSMDriver2 class. You could fiddle with the class and try it make it work, like this:
template<typename T>
class FSMDriver2 {
public:
int value;
std::map<char *, FSMState2<T> *> States;
};
You would just use the same T here as you do in your state classes. But let’s stop there. The reason this won’t work is that the T parameter in this template is ultimately going to be a class derived from FSMDriver2, the very class that’s using T. What a mess. If you search the Web, you might find various workarounds for this problem, but I like the following solution. Instead of trying to coerce the compiler to accept this, remove the templates at this level by making a non-template base class, and use that class inside the driver class:
class FSMStateBase2 {
int somethingorother;
};
class FSMDriver2 {
public:
int value;
std::map<char *, FSMStateBase2 *> States;
};
template<typename T>
class FSMState2 : public FSMStateBase2 {
public:
T *driver;
};
Now the driver contains a map of states, while the state is a template with the driver as an argument. These three classes compile fine, and this is exactly the approach I used in the real state machine code.