13
\$\begingroup\$

I have beginner knowledge of C++ and using that and some self dummy design I came up with the above implementation. The FiniteStateMachine here first asks for the states that are to be added, then transitions are added. A transition is own by a States (from the state). Once the machine in prepared, acceptInput is called to accept/reject the input.

#include<iostream>
#include<vector>
using namespace std;

class Input {
   private:
      string data;
   public:
      Input(string data): data(data){}
      Input(const Input &ip) {
         data = ip.getData();
      }
      string getData() const {
         return this->data;
      }
};
class State;
class Transition {
   private:
      Input ip;
      State *to;
   public:
      Transition(Input ip,State *to): ip(ip),to(to){}
      Input getInput() {
         return this->ip;
      }
      const State* getTransitionState() {
         return this->to;
      }
};

class State {
   private:
     string label;
     bool isStart;
     bool isEnd;
     vector<Transition> transitions;
   public:
     State(string label="",bool isStart=false,bool isEnd=false): 
       label(label),isStart(isStart),isEnd(isEnd) {}
     State(const State &s) {
        this->label = s.getLabel();
     }
     string transit(Input ip) {
        for(vector<Transition>::iterator it = transitions.begin(); it<transitions.end(); ++it) {
           if((*it).getInput().getData()==ip.getData())
              return (*it).getTransitionState()->getLabel();
        }
        return string("");
     }
     string getLabel() const {
        return this->label;
     }
     void addTransition(Transition t) {
        this->transitions.push_back(t);
     }
};

class StateMachine {
   private:
      vector<State> states;
      int currentStateIndex;
      Input *currentInput;
      void consumeInput();
   public:
      void addState();
      void acceptInput();
      void addTransition();
};

void StateMachine::addTransition() {
   string start,end;
   string inputLabel;
   cout << "Enter the start state of the transition \n";
   cin >> start;
   cout << "Enter the endstate of the transition \n";
   cin >> end;
   cout << "Enter the input label of the transition\n";
   cin >> inputLabel;
   vector<State>::iterator sit=states.end(), eit=states.end();
   for(vector<State>::iterator it = states.begin(); it<states.end(); ++it) {
      if((*it).getLabel()==start) {
         sit = it;
      }
      if((*it).getLabel()==end) {
         eit = it;
      }
      if(sit!=states.end()&&eit!=states.end()) {
         break;
     }
   }
   if(sit==states.end()||eit==states.end()) {
      cout << "Both the states not present\n";
      return;
   }
   Transition t(Input(inputLabel),&(*eit));
   (*sit).addTransition(t);
}

void StateMachine::addState() {
   string stateLabel;
   cin >> stateLabel;
   for(vector<State>::iterator it = states.begin(); it<states.end(); ++it) {
      if((*it).getLabel()==stateLabel) {
         cout << "a state with label "+stateLabel+" already present" << std::endl;
         return;
      }
   }
   char isStart,isEnd;
   cout << "Is a start state ? y/n" << std::endl;
   cin >> isStart;
   cout << "Is a end state ? y/n" << std::endl;
   cin >> isEnd;
   State s(stateLabel,isStart=='y',isEnd=='y');
   this->states.push_back(s);
   if(isStart=='y') {
      this->currentStateIndex = states.size()-1;
   }
}
void StateMachine::acceptInput() {
   string inputLabel;
   cin >> inputLabel;
   string nextStateLabel = this->states[this->currentStateIndex].transit(Input(inputLabel));
   vector<State>::iterator it = states.begin();
   for(; it<states.end(); ++it) {
      if((*it).getLabel()==nextStateLabel) {
         this->currentStateIndex = it-states.begin();
         cout << "current state is "+nextStateLabel<<std::endl;
         break;
      }
   }
   if(it==states.end())
      cout << "no transition for the input form currentState" << std::endl;
}


int main() {
   StateMachine sm;
   sm.addState();
   sm.addState();
   sm.addTransition();
   sm.addTransition();
   sm.addTransition();
   sm.addTransition();
   while(1) {
      sm.acceptInput();
   }
   return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I really recommend consistent use of spaces around certain operators. cout << "current state is " + nextStateLabel << std::endl; \$\endgroup\$ – Almo Oct 6 '17 at 20:34
14
\$\begingroup\$

using namespace std

Don't use using namespace std. It's considered bad practice.

Consistency

Use a consistent coding style. You use std::endl and cout, and states and this->states.

public first, private last

This is a matter of personal preference, but you are usually more interested in how you can access your class. That's why the public section is usually put first, and the private section is usually put last.

Minimize IO in your functions

Your StateMachine needs user input for setup. But that's hard to test. Instead, try to provide an interface that's easy to use:

bool StateMachine::addState(std::string label, bool startState, bool endState) {
    for(auto & state : states) {
        if(state.getLabel() == label) {
            return false;
        }
    }
    states->emplace_back(label, startState, endState);
    // ...
}

Now we can add our own states easily if we want to:

StateMachine sm;

sm.addState("example1", true, false);
sm.addState("example2", false, false);
sm.addState("example3", false, false);
sm.addState("example4", false, true);

We can still use user input:

std::string label;
char isStart, isEnd;

std::cin >> label >> isStart >> isEnd;

sm.addState(label, isStart, isEnd);

So we lost no functionality at all.

Prefer range-based for-loops

See above for an example. They are much more convenient to work with if you don't need the index or the iterator of a specific element. You need a compiler that understands C++11 or higher, though.

Documentation and comments

Comments and documentation often feel like a nuisance, but they will help to to remember what you had in mind when you wrote the program. Also, whitespace is your friend. Compare

void StateMachine::acceptInput() {
   string inputLabel;
   cin >> inputLabel;
   string nextStateLabel = this->states[this->currentStateIndex].transit(Input(inputLabel));
   vector<State>::iterator it = states.begin();
   for(; it<states.end(); ++it) {
      if((*it).getLabel()==nextStateLabel) {
         this->currentStateIndex = it-states.begin();
         cout << "current state is "+nextStateLabel<<std::endl;
         break;
      }
   }
   if(it==states.end())
      cout << "no transition for the input form currentState" << std::endl;
}

to

void StateMachine::acceptInput(std::string inputLabel) {
   std::string nextStateLabel = states[currentStateIndex].transit(Input(inputLabel));

   for(auto it = states.begin(); it != states.end(); ++it) {
      if(it->getLabel() == nextStateLabel) {
         // This is our new state.
         currentStateIndex = it - states.begin();

         std::cout << "current state is " << nextStateLabel << std::endl;

         return;
      }
   }
   std::cout << "no transition for the input form currentState" << std::endl;
}

It's a little bit easier to read, right? Note that you can replace (*it).foo with it->foo. Also, you can always return whenever a function has done its job. Just keep in mind that you should use RAII.

Hide implementation details

At no point does a user actually need to know that there is a Transition or a State. You can hide all those implementation details. All they need is a clean interface in StateMachine:

class StateMachine {
   public:
      typedef std::string state_label;

      bool addState(state_label name);
      bool addTransition(state_label start, state_label stop, std::string input);

      bool acceptsInput(std::string input);
   private:
      ...
};
\$\endgroup\$
  • \$\begingroup\$ Using using namespace is perfectly fine. But doing using namespace std;, that is considered bad practice. It really depends on the namespace that you are importing. \$\endgroup\$ – Rakete1111 Oct 6 '17 at 18:05
  • 2
    \$\begingroup\$ @Rakete1111 It depends on the place mostly, IMHO. If you use using namespace in a header, you suddenly polluted all other files that include that header. using namespace at a global scope isn't recommended. It's is perfectly fine in a small scope, e.g. in the body of a function and for code-golfing. \$\endgroup\$ – Zeta Oct 6 '17 at 18:27
  • \$\begingroup\$ using namespace std is not recommended. Only std, not any other. Yes, it depends on the location, but it also depends on the namespace. using namespace std::string_literals; is perfectly fine in a source file at global scope. \$\endgroup\$ – Rakete1111 Oct 6 '17 at 18:29
  • \$\begingroup\$ @Rakete1111 I'm pretty sure that using namespace boost isn't recommended either :). Regardless, I've changed the first section of my answer. By the way, for others who read this conversation, see github.com/isocpp/CppCoreGuidelines/blob/master/… ("only" is important here) and github.com/isocpp/CppCoreGuidelines/blob/master/…. \$\endgroup\$ – Zeta Oct 6 '17 at 18:34
  • \$\begingroup\$ Thank you very much for your valuable time to review the code @Zeta. All of your comments have improved the code quality. Could you please also give your comments from the design perspective? Is it a good way to design a simple finite state machine. Of course there are some issues from completion perspective so ignore for that now. \$\endgroup\$ – Abhinav Agarwal Oct 8 '17 at 3:28
4
\$\begingroup\$

Zeta's answer is excellent. I'd like to point out a few additional things.

First, remember that you can use = default to implement a boilerplate constructor, such as the copy constructor for Input. As the code changes in the future, this will reduce the chance that you forget to copy a newly-added field.

Second, Input is probably an unnecessary class. Here's my reasoning:

  1. Encapsulation gives you a way to enforce constraints. For example, if you had to be ensure that the length of the input string was always an even length, then it would make sense to encapsulate a general purpose string in a class with methods to maintain that constraint. Your Input class doesn't appear to have any such constraints--any string is a legitimate input.

  2. Encapsulation lets you hide the representation of the object behind an interface. For example, a Rectangle class in a drawing program might use two coordinates or one coordinate plus a height and width. The user of the class shouldn't care what the underlying representation is, and the provider of the class should be able to change the representation without affecting the caller.
    In the case of Input, the representation is uninteresting and (effectively) exposed through the API. Yes, in theory the inner representation could be something other than a std::string and the constructor and accessor could be converting back and forth, but it's not and that seems unlikely.

  3. Encapsulation lets you provide a restricted API. A std::string has an expansive API, and one might argue that it's more than a user of StateMachine needs. But Input isn't restricting that API--it just hands the original std::string back to the user.

  4. Encapsulation allows you to give something a meaningful name. This is the one benefit I see of the existing Input class. But, given that you don't need a class for the other benefits, a simpler way to do this would be typedef std::string Input;.

Finally, I think it's worth emphasizing and generalizing one of Zeta's comments: Separate the user interface from the "business" logic. The StateMachine class should give you the inner workings of a state machine and nothing more. Putting UI inside the class violates the single-responsibility principle. Following the single-responsibility principle makes code easier to test (through automation) and makes it more re-usable. If StateMachine didn't have the console I/O built into it, then it would be easy to re-use it a graphical UI program or in a network server that responds to client requests.

\$\endgroup\$
  • \$\begingroup\$ Regarding the = default for the copy constructor, you don't even need to do that; you can just remove it altogether and the compiler will generate a copy constructor for you \$\endgroup\$ – Justin Oct 8 '17 at 0:18
  • \$\begingroup\$ Thanks for reviewing the code. The issue you raised about Input class is valid. I decided to encapsulate input as a class from future perspective but in current design it is not fruitful, I agree. Also please comment about the overall design. \$\endgroup\$ – Abhinav Agarwal Oct 8 '17 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.