C++ code for state machine

Question

This was an interview question to be coded in C++:

Write code for a vending machine: Start with a simple one where it just vends one type of item. So two state variables: money and inventory, would do.

My answer:

I would use a state machine which has about 3-4 states. Use an enum variable to indicate the state and use a switch case statement, where each case has the operations to be done corresponding to each state and stay in a loop to move from one state to another.

The next question:

But using a switch case statement does not "scale well" for more states being added and modifying existing operations in a state. How are you going to deal with that problem?

I couldn't answer this question at that time. But later thought, I can probably:

• have different functions for different states (each function corresponding to a state)
• have an std::map from (string, function) where string indicates state to call the corresponding state function.
• The main function has a string variable (starting in initial state), and calls the function corresponding to that variable in a loop. Each function does the operations needed and returns the new state to the main function.

My questions are:

• What is the problem with switch-case statements with respect to scalability in the context of large scale software systems?
• If so is my solution (which currently I feel is a bit more modular than having long linear code) going to resolve the problem?

The interview question is expecting answers from C++ idioms and design patterns for large scale software systems.

Just

I think they expected you to use the State Design Pattern... – Machiavelli

Answer 1

I was thinking in a more OO approach, using the State Pattern:

The Machine:

// machine.h
#pragma once

#include "MachineStates.h"

class AbstractState;

class Machine {
  friend class AbstractState;

public:
  Machine(unsigned int _stock);
  void sell(unsigned int quantity);
  void refill(unsigned int quantity);
  unsigned int getStock();
  ~Machine();

private:
  unsigned int stock;
  AbstractState *state;
};


// --------

// machine.cpp
#include "Machine.h"
#include "MachineStates.h"

Machine::Machine(unsigned int _stock) {
  stock = _stock;
  state = _stock > 0 ? static_cast<AbstractState *>(new Normal())
                    : static_cast<AbstractState *>(new SoldOut());
}

Machine::~Machine() { delete state; }

void Machine::sell(unsigned int quantity) { state->sell(*this, quantity); }

void Machine::refill(unsigned int quantity) { state->refill(*this, quantity); }

unsigned int Machine::getStock() { return stock; }

The States:

// MachineStates.h
#pragma once

#include "Machine.h"
#include <exception>
#include <stdexcept>

class Machine;

class AbstractState {
public:
  virtual void sell(Machine &machine, unsigned int quantity) = 0;
  virtual void refill(Machine &machine, unsigned int quantity) = 0;
  virtual ~AbstractState();

protected:
  void setState(Machine &machine, AbstractState *st);
  void updateStock(Machine &machine, unsigned int quantity);
};

class Normal : public AbstractState {
public:
  virtual void sell(Machine &machine, unsigned int quantity);
  virtual void refill(Machine &machine, unsigned int quantity);
  virtual ~Normal();
};

class SoldOut : public AbstractState {
public:
  virtual void sell(Machine &machine, unsigned int quantity);
  virtual void refill(Machine &machine, unsigned int quantity);
  virtual ~SoldOut();
};

// --------

// MachineStates.cpp
#include "MachineStates.h"

AbstractState::~AbstractState() {}

void AbstractState::setState(Machine &machine, AbstractState *state) {
  AbstractState *aux = machine.state;
  machine.state = state;
  delete aux;
}

void AbstractState::updateStock(Machine &machine, unsigned int quantity) {
  machine.stock = quantity;
}

Normal::~Normal() {}

void Normal::sell(Machine &machine, unsigned int quantity) {
  unsigned int currStock = machine.getStock();
  if (currStock < quantity) {
    throw std::runtime_error("Not enough stock");
  }

  updateStock(machine, currStock - quantity);

  if (machine.getStock() == 0) {
    setState(machine, new SoldOut());
  }
}

void Normal::refill(Machine &machine, unsigned int quantity) {
  int currStock = machine.getStock();
  updateStock(machine, currStock + quantity);
}

SoldOut::~SoldOut() {}

void SoldOut::sell(Machine &machine, unsigned int quantity) {
  throw std::runtime_error("Sold out!");
}

void SoldOut::refill(Machine &machine, unsigned int quantity) {
  updateStock(machine, quantity);
  setState(machine, new Normal());
}

I'm not used to program in C++, but this code apparently compiles against GCC 4.8.2 clang@11.0.0 and Valgrind shows no leaks, so I guess it's fine. I'm not computing money, but I don't need this to show you the idea.

To test it:

// main.cpp
#include "Machine.h"
#include "MachineStates.h"
#include <iostream>
#include <stdexcept>

int main() {
  Machine m(10), m2(0);

  m.sell(10);
  std::cout << "m: "
            << "Sold 10 items" << std::endl;

  try {
    m.sell(1);
  } catch (std::exception &e) {
    std::cerr << "m: " << e.what() << std::endl;
  }

  m.refill(20);
  std::cout << "m: "
            << "Refilled 20 items" << std::endl;

  m.sell(10);
  std::cout << "m: "
            << "Sold 10 items" << std::endl;
  std::cout << "m: "
            << "Remaining " << m.getStock() << " items" << std::endl;

  m.sell(5);
  std::cout << "m: "
            << "Sold 5 items" << std::endl;
  std::cout << "m: "
            << "Remaining " << m.getStock() << " items" << std::endl;

  try {
    m.sell(10);
  } catch (std::exception &e) {
    std::cerr << "m: " << e.what() << std::endl;
  }

  try {
    m2.sell(1);
  } catch (std::exception &e) {
    std::cerr << "m2: " << e.what() << std::endl;
  }

  return 0;
}

A little bit of Makefile:

CC = clang++
CFLAGS = -g -Wall -std=c++17

main: main.o Machine.o MachineStates.o
    $(CC) $(CFLAGS) -o main main.o Machine.o MachineStates.o

main.o: main.cpp Machine.h MachineStates.h
    $(CC) $(CFLAGS) -c main.cpp

Machine.o: Machine.h MachineStates.h

MachineStates.o: Machine.h MachineStates.h

clean:
    $(RM) main

Then run:

make main
./main

Output is:

m: Sold 10 items
m: Sold out!
m: Refilled 20 items
m: Sold 10 items
m: Remaining 10 items
m: Sold 5 items
m: Remaining 5 items
m: Not enough stock
m2: Not enough stock

Now, if you want to add a Broken state, all you need is another AbstractState child:

diff --git a/Machine.cpp b/Machine.cpp
index 935d654..6c1f421 100644
--- a/Machine.cpp
+++ b/Machine.cpp
@@ -13,4 +13,8 @@ void Machine::sell(unsigned int quantity) { state->sell(*this, quantity); }
 
 void Machine::refill(unsigned int quantity) { state->refill(*this, quantity); }
 
+void Machine::damage() { state->damage(*this); }
+
+void Machine::fix() { state->fix(*this); }
+
 unsigned int Machine::getStock() { return stock; }
diff --git a/Machine.h b/Machine.h
index aa983d0..706dde2 100644
--- a/Machine.h
+++ b/Machine.h
@@ -12,6 +12,8 @@ public:
   Machine(unsigned int _stock);
   void sell(unsigned int quantity);
   void refill(unsigned int quantity);
+  void damage();
+  void fix();
   unsigned int getStock();
   ~Machine();
 
diff --git a/MachineStates.cpp b/MachineStates.cpp
index 9656783..d35a53d 100644
--- a/MachineStates.cpp
+++ b/MachineStates.cpp
@@ -13,6 +13,16 @@ void AbstractState::updateStock(Machine &machine, unsigned int quantity) {
   machine.stock = quantity;
 }
 
+void AbstractState::damage(Machine &machine) {
+  setState(machine, new Broken());
+};
+
+void AbstractState::fix(Machine &machine) {
+  setState(machine, machine.stock > 0
+                        ? static_cast<AbstractState *>(new Normal())
+                        : static_cast<AbstractState *>(new SoldOut()));
+};
+
 Normal::~Normal() {}
 
 void Normal::sell(Machine &machine, unsigned int quantity) {
@@ -33,6 +43,10 @@ void Normal::refill(Machine &machine, unsigned int quantity) {
   updateStock(machine, currStock + quantity);
 }
 
+void Normal::fix(Machine &machine) {
+  throw std::runtime_error("If it ain't broke, don't fix it!");
+};
+
 SoldOut::~SoldOut() {}
 
 void SoldOut::sell(Machine &machine, unsigned int quantity) {
@@ -43,3 +57,17 @@ void SoldOut::refill(Machine &machine, unsigned int quantity) {
   updateStock(machine, quantity);
   setState(machine, new Normal());
 }
+
+void SoldOut::fix(Machine &machine) {
+  throw std::runtime_error("If it ain't broke, don't fix it!");
+};
+
+Broken::~Broken() {}
+
+void Broken::sell(Machine &machine, unsigned int quantity) {
+  throw std::runtime_error("Machine is broken! Fix it before sell");
+}
+
+void Broken::refill(Machine &machine, unsigned int quantity) {
+  throw std::runtime_error("Machine is broken! Fix it before refill");
+}
diff --git a/MachineStates.h b/MachineStates.h
index b117d3c..3921d35 100644
--- a/MachineStates.h
+++ b/MachineStates.h
@@ -11,6 +11,8 @@ class AbstractState {
 public:
   virtual void sell(Machine &machine, unsigned int quantity) = 0;
   virtual void refill(Machine &machine, unsigned int quantity) = 0;
+  virtual void damage(Machine &machine);
+  virtual void fix(Machine &machine);
   virtual ~AbstractState();
 
 protected:
@@ -22,6 +24,7 @@ class Normal : public AbstractState {
 public:
   virtual void sell(Machine &machine, unsigned int quantity);
   virtual void refill(Machine &machine, unsigned int quantity);
+  virtual void fix(Machine &machine);
   virtual ~Normal();
 };
 
@@ -29,5 +32,13 @@ class SoldOut : public AbstractState {
 public:
   virtual void sell(Machine &machine, unsigned int quantity);
   virtual void refill(Machine &machine, unsigned int quantity);
+  virtual void fix(Machine &machine);
   virtual ~SoldOut();
 };
+
+class Broken : public AbstractState {
+public:
+  virtual void sell(Machine &machine, unsigned int quantity);
+  virtual void refill(Machine &machine, unsigned int quantity);
+  virtual ~Broken();
+};
diff --git a/main b/main
index 26915c2..de2c3e5 100755
Binary files a/main and b/main differ
diff --git a/main.cpp b/main.cpp
index 8c57fed..82ea0bf 100644
--- a/main.cpp
+++ b/main.cpp
@@ -39,11 +39,34 @@ int main() {
     std::cerr << "m: " << e.what() << std::endl;
   }
 
+  m.damage();
+  std::cout << "m: "
+            << "Machine is broken" << std::endl;
+  m.fix();
+  std::cout << "m: "
+            << "Fixed! In stock: " << m.getStock() << " items" << std::endl;
+
   try {
     m2.sell(1);
   } catch (std::exception &e) {
     std::cerr << "m2: " << e.what() << std::endl;
   }
 
+  try {
+    m2.fix();
+  } catch (std::exception &e) {
+    std::cerr << "m2: " << e.what() << std::endl;
+  }
+
+  m2.damage();
+  std::cout << "m2: "
+            << "Machine is broken" << std::endl;
+
+  try {
+    m2.refill(10);
+  } catch (std::exception &e) {
+    std::cerr << "m2: " << e.what() << std::endl;
+  }
+
   return 0;
 }

To add more products, you must have a map of products and its respective in-stock quantity and so on...

The final code can be found in this repo.

Machiavelli

Also the machine should be initialized to Normal or SoldOut state based on the quantity, not always Normal by default. – Thyratron

Worth noting that if you try and compile this using C++17 in Visual Studio 2017, it produces an error C2446 ":": no conversion from 'SoldOut*' to Normal*'. If you remove the ternary in Machine's constructor and simply initialize the mState variable in the constructor's body (or initialize it in Machine's header) it'll be fine. – Tommietommy

@Tommietommy well, that seems odd. I don't use C++ professionally, but to my understanding, since mState is of type AbstractState and both Normal and SoldOut extend it, there shouldn't be a problem. About your suggestion to initialize it in the header file, if you could point me to a code snippet, I'd be glad to update the answer. – Machiavelli

@HenriqueBarcelos, I'm only speculating (because it might just be an MSVC thing), but I think a ternary operator requires both results to be of the same type (regardless of whether the left hand side variable is of a compatible type with both). You have to use an if statement in the constructor to initialize it properly. As for the header initialization, that would only allow us to initialize it to nullptr, Normal, or SoldOut explicitly (no ternary and no if statement, so essentially give it a default state). – Tommietommy

I updated the answer and the code should now compile without errors. Looks like compilers were updated shortly after I wrote the initial answer and now require explicit casting with ternary operators. – Machiavelli

Answer 2

Consider using tables instead of switch statements. One column could be the transition criteria and another column is the destination state.

This scales nicely because you don't have to change the table processing function; just add another row to the table.

+------------------+---------------------+---------------+
| Current state ID | transition criteria | Next state ID |
+------------------+---------------------+---------------+
|                  |                     |               |
+------------------+---------------------+---------------+

In my code at work, we use a column of function pointers rather than the "Next state ID". The table is a separate file with accessor functions defined. There is one or more include statements to resolve each function pointer.

Edit 1: Example of separate table files.

table.h

#ifndef TABLE_H
#define TABLE_H

struct Table_Entry
{
    unsigned int  current_state_id;
    unsigned char transition_letter;
    unsigned int  next_state_id;
};

Table_Entry const *    table_begin(void);
Table_Entry const *    table_end(void);

#endif // TABLE_H

table.cpp:

#include "table.h"

static const Table_Entry    my_table[] =
{
    //  Current   Transition     Next
    //  State ID    Letter     State ID
    {    0,          'A',        1}, // From 0 goto 1 if letter is 'A'.
    {    0,          'B',        2}, // From 0 goto 2 if letter is 'B'.
    {    0,          'C',        3}, // From 0 goto 3 if letter is 'C'.
    {    1,          'A',        1}, // From 1 goto 1 if letter is 'A'.
    {    1,          'B',        3}, // From 1 goto 3 if letter is 'B'.
    {    1,          'C',        0}, // From 1 goto 0 if letter is 'C'.
};

static const unsigned int  TABLE_SIZE =  
    sizeof(my_table) / sizeof(my_table[0]);


Table_Entry const *
table_begin(void)
{
    return &my_table[0];
}


Table_Entry const *
table_end(void)
{
    return &my_table[TABLE_SIZE];
}  

state_machine.cpp

#include "table.h"
#include <iostream>

using namespace std;  // Because I'm lazy.

void
Execute_State_Machine(void)
{
    unsigned int current_state = 0;
    while (1)
    {
        char transition_letter;
        cout << "Current state: " << current_state << "\n";
        cout << "Enter transition letter: ";
        cin >> transition_letter;
        cin.ignore(1000, '\n'); /* Eat up the '\n' still in the input stream */
        Table_Entry const *  p_entry = table_begin();
        Table_Entry const * const  p_table_end =  table_end();
        bool state_found = false;
        while ((!state_found) && (p_entry != p_table_end))
        {
            if (p_entry->current_state_id == current_state)
            {
                if (p_entry->transition_letter == transition_letter)
                {
                    cout << "State found, transitioning"
                         << " from state " << current_state
                         << ", to state " << p_entry->next_state_id
                         << "\n";
                    current_state = p_entry->next_state_id;
                    state_found = true;
                    break;
                }
             }
             ++p_entry;
         }
         if (!state_found)
         {
             cerr << "Transition letter not found, current state not changed.\n";
         }
    }
}

Sickening

Please could you give more details of how you are going to code this table in the separate file with accessor functions. If possible, by taking a small example state machine: 3 states(A, B, C); A(), B(), C() are the functions that have the operations needed to be done in each. – Just

This is a C state machine using I/O streams, not a C++ state machine. – Whin

@Sanhadrin: Why is it not C++? I'll admit it is not object oriented, but it is compatible with both C and C++. Is it because I'm not using function objects, or the std::map structure? I explicitly use a table because the table can be compiled as static data and doesn't have to be initialized like an std::map. – Sickening

I've spent a lot of time on trying all kinds of types of state machines, but a transition table just works the best in almost every problem I have with them. +1 for a really nice piece of code there! – Afterburning

I don't agree with statements like "this is not C++". Sorry, if it compiles with a standards-compliant compiler, then it is C++ code. End of story. You can say it's not OO, but the beauty of C++ is that it doesn't force any one paradigm down your throat. – Parasitology

@Parasitology "but the beauty of C++ is that it doesn't force any one paradigm down your throat" in general I agree. But your statement sounds like "it is C back-compatible -- that's the beauty" I just disagree. I don't see any beauty in this code as a C++ developer. Bad code formatting, hardcoded values, nested ifs. Sorry but this code is far from a beautiful one IMHO. Of course, it solves the problem, and generally speaking it is C++, but I don't see C++-ness here. Sorry :) – Pardoner

@Pardoner You have parsed my comment incorrectly. Nowhere did I say that this code is beautiful (which in any event is an extremely subjective judgement). Nor did I ever equate backwards compatibility with beauty. My main point is that--whether you like it or not--it is technically C++ code. To label it otherwise is an objective error of fact. My secondary point is that the multi-paradigm nature of C++ is (in my subjective opinion) one of its virtues. – Parasitology

@chill Well, sorry for misunderstanding. BTW I liked the answer and find it useful at least for its lightweight though it looks more like written for embedded systems :) – Pardoner

Answer 3

I once wrote a state machine in C++, where I needed the same transition for a lot of state pairs (source → target pairs). I want to illustrate an example:

4 -> 8   \
5 -> 9    \_ action1()
6 -> 10   /
7 -> 11  /

8 -> 4   \
9 -> 5    \_ action2()
10 -> 6   /
11 -> 7  /

What I came up with was a set of (transition criteria + next state + "action" function to be called). To keep things general, both the transition criteria and the next state were written as functors (lambda functions):

typedef std::function<bool(int)> TransitionCriteria;
typedef std::function<int(int)>  TransitionNewState;
typedef std::function<void(int)> TransitionAction;   // gets passed the old state

This solution is nice if you have a lot of transitions which apply for a lot of different states as in the example above. However, for each "step", this method requires to linearly scan the list of all different transitions.

For the examples above, there would be two such transitions:

struct Transition {
    TransitionCriteria criteria;
    TransitionNewState newState;
    TransitionAction action;

    Transition(TransitionCriteria c, TransitionNewState n, TransitionAction a)
        : criteria(c), newState(n), action(a) {}
};
std::vector<Transition> transitions;

transitions.push_back(Transition(
    [](int oldState){ return oldState >= 4 && oldState < 8; },
    [](int oldState){ return oldState + 4; },
    [](int oldState){ std::cout << "action1" << std::endl; }
));
transitions.push_back(Transition(
    [](int oldState){ return oldState >= 8 && oldState < 12; },
    [](int oldState){ return oldState - 4; },
    [](int oldState){ std::cout << "action2" << std::endl; }
));

Reagan

Answer 4

I don't know whether that would have gotten you through the interview, but I'd personally refrain from coding any state machine by hand, especially if it's in a professional setting. State machines are a well researched problem, and there exist well tested open source tools which often produce superior code to what you will produce yourself by hand, and they also help you with diagnosing problems with your state machine by eg. being able to generate state diagrams automatically.

My goto tools for this kind of problem are:

• Ragel
• SMC

Cinchona

Have you also tried stateforge ? It is now open source. Disclaimer, I'm the author. – Fabron

The link above for SMC should be https://sourceforge.net/projects/smc/ – Griffin

I apologize; the original answer SMC link seemed dead when I clicked on it. Works now. – Griffin

SMC links are broken – Papistry

Answer 5

I've written plenty of state machines using these methods. But when I wrote Cisco's Transceiver Library for the Nexus 7000 (a $117,000 switch) I used a method I invented in the 80's. That was to use a macro which makes the state machine look more like multi-tasking blocking code. The macros are written for C but I have used them with small modifications for C++ when I worked for DELL. You can read more about it here: https://www.codeproject.com/Articles/37037/Macros-to-simulate-multi-tasking-blocking-code-at

Templeton

Answer 6

#include <stdio.h>
#include <iostream>

using namespace std;
class State;

enum state{ON=0,OFF};
class Switch {
    private:
        State* offState;
        State* onState;
        State* currState;
    public:
        ~Switch();
        Switch();
        void SetState(int st);
        void on();
        void off();
};
class State{
    public:
        State(){}
        virtual void on(Switch* op){}
        virtual void off(Switch* op){} 
};
class OnState : public State{
    public:
    OnState(){
        cout << "OnState State Initialized" << endl;
    }
    void on(Switch* op);
    void off(Switch* op);
};
class OffState : public State{
    public:
    OffState(){
        cout << "OffState State Initialized" << endl;
    }
    void on(Switch* op);
    void off(Switch* op);
};
Switch::Switch(){
    offState = new OffState();
    onState = new OnState();
    currState=offState;
}
Switch::~Switch(){
    if(offState != NULL)
        delete offState;
    if(onState != NULL)
        delete onState;
}
void Switch::SetState(int newState){
    if(newState == ON)
    {
        currState = onState;
    }
    else if(newState == OFF)
    {
        currState = offState;
    }
}
void Switch::on(){
    currState->on(this);
}
void Switch::off(){
    currState->off(this);
}
void OffState::on(Switch* op){
    cout << "State transition from OFF to ON" << endl;
    op->SetState(ON);
}
void OffState::off(Switch* op){
    cout << "Already in OFF state" << endl;
}
void OnState::on(Switch* op){
    cout << "Already in ON state" << endl;
}
void OnState::off(Switch* op){
    cout << "State transition from ON to OFF" << endl;
    op->SetState(OFF);
}
int main(){
    Switch* swObj = new Switch();
    int ch;
    do{
        switch(ch){
            case 1:     swObj->on();
                    break;
            case 0:     swObj->off();
                    break;
            default :   cout << "Invalid choice"<<endl;
                    break;
        }
        cout << "Enter 0/1: ";
        cin >> ch;  
    }while(true);`enter code here`
    delete swObj;
    return 0;
}

Dulci