471,337 Members | 1,058 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes and contribute your articles to a community of 471,337 developers and data experts.

Design Patterns: State

weaknessforcats
9,208 Expert Mod 8TB
Design Patterns State

Often computer software operates based on a condition called a state. These states traditionally have been implemented using a switch statement. The cases of the switch represent the various states. The example below might be used to read a disc file

Expand|Select|Wrap|Line Numbers
  1. int state = 1;
  2. switch (state)
  3. {
  4.      case 1:
  5.          //open the file
  6.          state = 2;
  7.          break;
  8.       case 2;
  9.          //read a record from the file
  10.          if end of file
  11.          {
  12.              state = 4;
  13.              break;
  14.          }
  15.          state =3;
  16.          break;
  17. ......case 3:
  18. ........ //displays the record
  19.          state = 2;
  20.          break;
  21.        case 4:
  22.          //close the file
  23.          state = 0;
  24.          break;
  25. }
  26.  
In the above switch the user sets the initial state to open the file. Once the file is opened, the state variable is changed to the state for reading the file. The read state checks for end of file and if the end of file is not reached the state is changed to the display state. The display state displays the record and then sets the state back to the read state to read the file for the next record. In the read state, if the end of file was reached, the state is changed to the close the file. When the file is closed, the state is changed to no-state and the switch is exited.

Note that all that is required is that each case (state) has to know the following state.

Here is the above switch used to read a text file from the disc. Assume the disc file contains:

This is the
easiest thing I have
ever seen

The code would be:
Expand|Select|Wrap|Line Numbers
  1. int main()
  2. {
  3.     fstream input;
  4.     int state = 1;
  5.     char buffer[256];
  6.     while (state)
  7.     {
  8.         switch (state)
  9.         {
  10.              case 1:
  11.              //open the file
  12.              input.open("c:\\scratch\\instructor\\input.txt", ios::in);
  13.              state = 2;
  14.              break;
  15.          case 2:
  16.              //read a record from the file
  17.             input.getline(buffer, 256);
  18.              if (input.eof() == true)
  19.              {
  20.                  state = 4;
  21.                  break;
  22.              }
  23.              state = 3;\
  24.              break;
  25.         case 3:
  26.             //displays the record
  27.              cout << buffer << endl;
  28.              state = 2;
  29.              break;
  30.         case 4:
  31.              //close the file
  32.             input.close();
  33.             state = 0;
  34.             break;
  35.         }  //end of switch
  36.     } //end of while
  37. }
  38.  
The user sets the initial state and then writes a loop that continues as long as a state (a case in the switch statement) exists. Each case performs its action and then changes the state to the successor state.

Try this code yourself. Compile and run it until you see how the cases work together.

Limitations
The limitations of the switch method (a form of go-to programming) are that the switch needs to be changed if any states need to be added or removed. Further, the user of the switch needs to know about the states. That is, there is no context. Everything is done right up front with no encapsulation.

With a large base of installed software, changing the switch will result is a requirement to re-install the user base. That is, the ripple caused by the change has the proportions of a tsunami.

The Object-Oriented Approach Part 1

What really happens with the switch is that the processing changes based on the state. In the object-oriented world a change of behavior implies a different type of object. In this case, what is needed is an object that appears to change its type based on its internal state.

This object is called the context object and it contains the state, and the request for what to do. The user merely creates the context object and passes in a request for service.

To illustrate this, the example below will implement the switch in an object-oriented manner.

Expand|Select|Wrap|Line Numbers
  1. int main()
  2. {
  3.     FileRead context;
  4.     context.Request("c:\\scratch\\instructor\\input.txt");
  5.     context.Process();
  6.  
  7. } //end of main
  8.  
First, a context object is created followed by submitting a request for service. In this case, the request is the name of the disc file to read. Then, the context object is asked to process the request. The result will be the disc records displayed on the screen.

There is nothing here about states. The user is freed from this burden.

The context class is:
Expand|Select|Wrap|Line Numbers
  1. class FileRead
  2. {
  3.     private:
  4.         State* CurrentState;
  5.         fstream TheFile;
  6.         string request;
  7.     public:
  8.         FileRead();
  9.         ~FileRead();
  10.         void Request(string name);
  11.         void Process();
  12.         void ChangeState(State* theNewState);
  13.         fstream& GetFileStream();
  14. };
  15.  
The context object contains its internal state as CurrentState. It is this member that needs to change type as the context object processes a request. Since this is a file reading context object, it also contains the file stream and a request which is used to pass information to the CurrentState. The meaning of this request will vary based on the type of the CurrentState. There is a method to receive a request for service and a method to process that request.There is a method to change the internal state by changing the type of object pointed at by the CurrentState. Finally, there is a method to return a reference to the file stream.

The implementation of these methods might be as follows:
Expand|Select|Wrap|Line Numbers
  1. FileRead::FileRead() : CurrentState(0)
  2. {
  3.  
  4. }
  5. void FileRead::Process()
  6. {
  7.     ChangeState(new OpenState);
  8.     string token;
  9.     while (CurrentState)
  10.     {
  11.         CurrentState->DoProcess(this->request, *this, token);
  12.     }
  13. }
  14. void FileRead::ChangeState(State* theNewState)
  15. {
  16.     delete CurrentState;
  17.     CurrentState = theNewState;
  18. }
  19. fstream& FileRead::GetFileStream()
  20. {
  21.         return this->TheFile;
  22. }
  23. void FileRead::Request(string name)
  24. {
  25.     this->request = name;
  26. }
  27. FileRead::~FileRead()
  28. {
  29.     delete CurrentState;
  30. }
  31.  
The actual states are a polymorphic hierarchy with State as the base class. The State class has a virtual destructor signaling that it can be used as a polymorphic base class. The only method is a process method that receives the request, the context object, and the token.
Expand|Select|Wrap|Line Numbers
  1. class State
  2. {
  3.    public:
  4.       virtual ~State(); //a signal that it's OK to derive from this class.
  5.  
  6.       //the derived object's process
  7.       virtual void DoProcess(string& request, FileRead& context, string& token) = 0;
  8. };
  9. State::~State()
  10. {
  11.     //nothing to do
  12. }
  13.  
  14.  
These are the derived classes for the various states. The DoProcess method is an override of the State base class DoProcess method. The override is private in the derived classes forcing the call to come from a State pointer or reference. These derived states are not to be used directly.

There is a token argument that can be used as needed to pass information from state to state as the request is processed.
Expand|Select|Wrap|Line Numbers
  1. class OpenState :public State
  2. {
  3.     private:
  4.         virtual void DoProcess(string& request, FileRead& context, string& token);
  5.  
  6. };
  7. class ReadState :public State
  8. {
  9.     private:
  10.         virtual void DoProcess(string& request, FileRead& context, string& token);
  11.  
  12. };
  13. class DisplayState :public State
  14. {
  15.     private:
  16.         virtual void DoProcess(string& request, FileRead& context, string& token);
  17.  
  18. };
  19. class ExitState :public State
  20. {
  21.     private:
  22.         virtual void DoProcess(string& request, FileRead& context, string& token);
  23.  
  24. };
  25.  
These are the DoProcess implementations of the various states. You can see how the request varies in its meaning based on the state. OpenState sees the request as the file name to open. ReadState sees it as a way to return the record read.
Expand|Select|Wrap|Line Numbers
  1.  
  2. void OpenState::DoProcess(string& request, FileRead& context, string& token)
  3. {
  4.     context.GetFileStream().open(request.c_str(), ios::in);
  5.     context.ChangeState(new ReadState);
  6. }
  7. void ReadState::DoProcess(string& request, FileRead& context, string& token)
  8. {
  9.     char buffer[256];
  10.     context.GetFileStream().getline(buffer, 256);
  11.     if (context.GetFileStream().eof() == true)
  12.     {
  13.          context.ChangeState(new ExitState);
  14.          return;
  15.     }
  16.     request = buffer;
  17.     token = buffer;
  18.     context.ChangeState(new DisplayState);
  19.  
  20. }
  21. void DisplayState::DoProcess(string& request, FileRead& context, string& token)
  22. {
  23.     if (token.size())
  24.     {
  25.         cout << token << endl;
  26.     }
  27.     context.ChangeState(new ReadState);
  28. }
  29. void ExitState::DoProcess(string& request, FileRead& context, string& token)
  30. {
  31.     context.GetFileStream().close();
  32.     request.erase();
  33.     token.erase();
  34.     context.ChangeState(0);
  35. }
  36.  
You should be able to assemble these code samples and be able to read and display any text file with records of 256 bytes or less.

With a little improvement, the 256 byte limit could be removed. Then states could be added to write to the file. The display could be removed. The final product would be an object that could read and write any file.

The Object-Oriented Approach Part 2
As often happens, requirements change. The above example displays the records read from the file with one record per line. The new requirement asks that each individual word of each record be displayed on a separate line.

To accommodate this requirement, some new states need to be added. In addition, existing states may have new successor states.

To process a record into words, two states have been added. One, the WhiteSpace state, removes leading whitespace characters. The second, the WordState, breaks a word off the record and stores in the token.

These new classes look like:
Expand|Select|Wrap|Line Numbers
  1. class WhiteSpaceState :public State
  2. {
  3.     private:
  4.         virtual void DoProcess(string& request, FileRead& context, string& token);
  5.  
  6. };
  7. class WordState :public State
  8. {
  9.     private:
  10.         virtual void DoProcess(string& request, FileRead& context, string& token);
  11.  
  12. };
  13.  
The DoProcess methods look like:
Expand|Select|Wrap|Line Numbers
  1.  
  2. void WhiteSpaceState::DoProcess(string& request, FileRead& context, string& token)
  3. {
  4.                 while (isspace(request[0]) )
  5.     {
  6.         request.erase(0,1);
  7.     }
  8.  
  9.     if (request.size())
  10.     {
  11.         context.ChangeState(new WordState);
  12.     }
  13.     else
  14.     {
  15.         context.ChangeState(new ReadState);
  16.         return;
  17.     }
  18.  
  19.  
  20. }
  21.  
  22. void WordState::DoProcess(string& request, FileRead& context, string& token)
  23. {
  24.     token.erase();
  25.     while (request.size() && !isspace(request[0]))
  26.     {
  27.         token +=request[0];
  28.         request.erase(0, 1);
  29.     }
  30.  
  31.     //This is the successor state
  32.     context.ChangeState (new DisplayState);
  33. }
  34.  
The WhiteSpaceState::DoProcess determines if there is a request. If not, the state is changed to the ReadState. Otherwise, leading whitespace characters are removed from the request and the state is changed to the WordState.

The WordState::DoProcess will place the word in the token. It simply does a character-by-character move until it encounters a whitespace character. With the word in the token, the state is changed to the DisplayState so the word can be displayed on the screen.

To support these new states, some existing states now have new successor states. Shown below are the DoProcess methods that need to be changed. ReadState::DoProcess now has a WhiteSpaceState successor so the record (the request) and be processed into words (tokens). DisplayState::DoProcess also has a successor state of WhiteSpaceState to get the next token.

Shown below are the methods from the first example with the old states commented out and the new states added.

Expand|Select|Wrap|Line Numbers
  1. void ReadState::DoProcess(string& request, FileRead& context, string& token)
  2. {
  3.     char buffer[256];
  4.     context.GetFileStream().getline(buffer, 256);
  5.     if (context.GetFileStream().eof() == true)
  6.     {
  7.          context.ChangeState(new ExitState);
  8.          return;
  9.     }
  10.     request = buffer;
  11.     token = buffer;
  12.     context.ChangeState(new WhiteSpaceState);
  13.     //context.ChangeState(new DisplayState);
  14.  
  15. }
  16. void DisplayState::DoProcess(string& request, FileRead& context, string& token)
  17. {
  18.     if (token.size())
  19.     {
  20.         cout << token << endl;
  21.     }
  22.     context.ChangeState(new WhiteSpaceState);
  23.     //context.ChangeState(new ReadState);
  24.  
  25. }
  26.  
Notice that in adding these states, there was no change to the FileRead class at all. That means there was no change in main() either. Besides that, the only changes in the existing states were to identify new successor states. The new word breakout capability was accomplished by changing only two lines of code in the original application. The rest of the word breakout requirement was implemented with new code.

By hiding the details of the various states in derived classes, a high degree of encapsulation is achieved. This reduces the ripple caused by a change.

Using Handles
This examples in this article use pointers since pointer syntax is commonly understood. However, it is recommended in a real application that handles be used. You should refer to the article on Handles in the C/C++ Articles section.

Further Information
Refer to the book Design Patterns by Erich Fromm, et al, Addison-Wesley 1994.

This article shows only the conceptual basis of the State pattern but not motivations and ramifications of using this pattern.

Copyright 2007 Buchmiller Technical Associates North Bend WA USA
Jun 9 '07 #1
4 14370
Banfa
9,065 Expert Mod 8TB
I think there is an inefficiency in WhiteSpaceState::DoProcess. If checks request and selects a new state and then processes request. This means if the line ends in white space that the code has to go through the states

WordState
DisplayState
ReadState

to consume the white space and read the next line.

If WhiteSpaceState::DoProcess processed request and then selected it's state it would proceed directly to ReadState without going through the intervening states.

I am however finding the article very useful thank you
Feb 21 '08 #2
weaknessforcats
9,208 Expert Mod 8TB
Yes, but the idea of a State machine is that each state only knows the following state. Therefore, WhiteSpaceState only knows to hand control to WordState. It doesn't know about the other states. There is no uber view. True, some extra states get processed if the line ends in whitespace.

But, on the other hand, the state machine is relentless and the logic steps are finite. This allows you to change the machine and add or remove states. And if ReadState goes away and is replaced by something other state(s), WhiteSpaceState doesn't ned to know about that.
Feb 21 '08 #3
Banfa
9,065 Expert Mod 8TB
This argument would hold water if WhitesSpaceState did not already transition to ReadState in some circumstances, I am merely suggesting altering the order of the already existing code and logic in WhiteSpaceState not adding to it :D
Feb 21 '08 #4
weaknessforcats
9,208 Expert Mod 8TB
I agree. I have altered the WhitespaceState::DoProcess to process the request and then select the follow-on state.
Mar 4 '08 #5

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

4 posts views Thread by Tony Ha | last post: by
13 posts views Thread by John Salerno | last post: by
22 posts views Thread by Krivenok Dmitry | last post: by
2 posts views Thread by LarryTheSoftwareGuy | last post: by
10 posts views Thread by vital | last post: by
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.