| SFiniteStateMachine( const StateType & StartState, const SFiniteStateMachineProxy & ProxyMachine ); |
Теперь очередь за реализацией описанных выше идей. Запишем конструктор автомата для рассматриваемого примера полностью.
| SFiniteStateMachine FirstMachine( “empty”,(SFiniteStateMachineProxy() << (SStatesListProxy() << “empty” << “number” << “identifier” << “unknown”) <<(STransitionsProxy(letter) << “identifier” << “unknown” << “identifier” << “unknown”) <<(STransitionsProxy(digit) << “number” << “number” << “identifier” << “unknown”))); |
На конструктор SFiniteStateMachine будет возложена задача проверки начального состояния. Оно должно быть в списке состояний.
Путем форматирования текста уже удалось придать аргументам конструктора вид таблицы. Однако это еще не все. При описании автомата были опущены все детали, связанные с шаблонами. На практике это означает, что при конструировании также придется указывать типы, что дополнительно “замусорит” текст. Несмотря на проблемы, связанные с препроцессором, он здесь поможет. Запись аргументов конструктора станет примерно такой:
| FSMBEGIN( “empty” )FSMSTATES “empty” << “number” << “identifier” << “unknown”FSMEVENT(letter) “identifier” << “unknown” << “identifier” << “unknown”FSMEVENT(digit) “number” << “number” << “identifier” << “unknown”FSMEND |
Такая запись уже приемлема для повседневного использования.
Реализация должна включать ряд вспомогательных элементов, в частности, исключения. Автомат будет выдавать их в случае ошибки в описании состояний и переходов. При разработке своего класса исключений можно воспользоваться наследованием от класса стандартного исключения. Это даст возможность указать в блоке catch только ссылку на базовый стандартный класс исключений. Свой класс исключений можно определить так:
| class SStateMachineException : public std::exception{ private: const std::string Message; public: SStateMachineException( const std::string & Msg ) : Message( Msg ) {} SStateMachineException( const char * Msg ) : Message( Msg ) {} virtual ~SStateMachineException() throw() {} virtual const char * what( void ) const throw() { return Message.c_str(); }private: SStateMachineException();}; |
В основной программе, использующей класс автомата, можно будет написать так:
| . . .try{ . . . создание и использование автомата . . .}catch ( std::exception & Exception ){ // Поймаем и стандартное исключение и исключение, сгенерированное автоматом} |
Вернемся к конструкторам. Поскольку они имеют дело со списками переменной длины, то для сохранения элементов логично воспользоваться контейнерами, предоставляемыми библиотекой STL ([3]). Для хранения одномерного списка воспользуемся контейнером vector, а для таблицы переходов – вектором векторов:
| std::vector< std::vector<StateType> > Transitions; |
Алгоритмы STL помогут находить событие в списке событий:
| std::vector<EventType>::const_iterator k( std::find( Events.begin(), Events.end(), EntryEvent ) ); |
Поскольку контейнер vector поддерживает operator [], то для поиска состояния, в которое необходимо совершить переход, в таблице переходов можно воспользоваться подобной конструкцией:
| NewState = Transitions[ EventIndex ] [ StateIndex ]; |
где соответствующие индексы могут быть вычислены с помощью алгоритма STL distance:
| inline int GetStateIndex( const StateType & State ) const{ return std::distance( States.begin(), std::find( States.begin(), States.end(), State ) );} |
Разумеется, класс автомата должен будет иметь функцию, принимающую и обрабатывающую событие. Существует два варианта. Первый – это функция, второй – перегрузка какого-либо оператора. Для придания дополнительной гибкости реализуем оба варианта:
| SFiniteStateMachine & AcceptEvent( const EventType & Event ){ . . .} |
и
| inline SFiniteStateMachine & operator << ( const EventType & Event ){ return AcceptEvent( Event ); } |
Перегрузка operator << даст возможность использовать автомат в таком стиле:
| // Принять события Event1, Event2 и Event3MyMachine << Event1 << Event2 << Event3; |
Остается вопрос: что делать, если придет событие, для которого у автомата нет описания переходов? Возможны варианты: просто проигнорировать такое событие, сгенерировать исключение или сделать что-то, определяемое пользователем. Воспользуемся идеей стратегий ([4]) и включим в число аргументов шаблона функтор, который будет определять нужную стратегию поведения. Такой подход вполне соответствует требованию 5. При этом можно задать стратегию по умолчанию – например, генерировать исключение. Теперь заголовок шаблона выглядит так:
| template <class SState, class SEvent, class SUnknownEventStrategy = SThrowStrategy<SEvent> >class SFiniteStateMachine { . . . }; |
В числе заготовленных стратегий есть и стратегия игнорирования неизвестного события:
| template <class SEvent>class SIgnoreStrategy{ public: inline void operator() ( const SEvent & ) const { return; }}; |
Если понадобятся другие действия, всегда можно написать собственный функтор по образу и подобию SIgnoreStrategy и передать его шаблону.
Многие источники, описывающие конечные автоматы, упоминают о возможности вызова функций при входе и выходе из состояния. Такую возможность легко предоставить, используя тот же подход стратегий. Функции входа и выхода из состояний удобно определять для класса, представляющего конкретное состояние. Вспоминая о требовании 5, дадим возможность гибкого управления такой возможностью. Предполагая, что функции класса состояния будут называться OnEnter и OnExit, можно написать несколько готовых функторов: не вызывающий ни одну из функций, вызывающий только OnEnter, вызывающий только OnExit и вызывающий обе функции.
| template <class SState, class SEvent>class SEmptyFunctor{ public: inline void operator() ( SState & From, const SEvent & Event, SState & To ) { return; }};template <class SState, class SEvent>class SOnEnterFunctor{ public: inline void operator() ( SState & From, const SEvent & Event, SState & To ) { To.OnEnter( From, Event ); }};template <class SState, class SEvent>class SOnExitFunctor{ public: inline void operator() ( SState & From, const SEvent & Event, SState & To ) { From.OnExit( Event, To ); }};template <class SState, class SEvent>class SOnMoveFunctor{ public: inline void operator() ( SState & From, const SEvent & Event, SState & To ) { From.OnExit( Event, To ); To.OnEnter( From, Event ); }}; |
Стратегию по умолчанию (не вызывать никакую функцию) можно передать в качестве аргумента шаблона. Стратегия вызова функций, скорее всего, будет меняться чаще, чем стратегия действий при неизвестном событии. Поэтому ее имеет смысл поместить в списке аргументов перед стратегией реакции на неизвестное событие:
| template <class SState, class SEvent, class SFunctor = SEmptyFunctor<SState,SEvent>, class SUnknownEventStrategy = SThrowStrategy<SEvent> >class SFiniteStateMachine { . . . }; |
Еще один вопрос, связанный с событиями, состоит в том, что событие может быть сгенерировано внутри функции, вызываемой при выходе или входе в состояние. Для обработки таких событий надо соответствующим образом спроектировать функцию, принимающую событие. С учетом таких “внутренних” событий, надо предусмотреть очередь, в которую будут помещаться события. Код, который обрабатывает переходы, должен будет делать это до тех пор, пока очередь не опустеет. В качестве контейнера, подходящего для хранения событий, воспользуемся deque из STL. Поскольку нам нужны только вставка элементов в начало и исключение из конца контейнера, без произвольного доступа, контейнер deque подойдет лучше всего.
Осталось совсем немного. Иногда нужно привести автомат в исходное состояние. Как и в случае с событиями предусмотрим два варианта: обычная функция и перегруженный operator <<. Для перегруженного operator << нужно определить специальный манипулятор:
| enum SMachineManipulator { ResetMachine = 0};. . .inline SFiniteStateMachine & operator << ( SMachineManipulator Manipulator ) { if ( Manipulator == ResetMachine ) return Reset(); return *this; } |
Теперь можно будет написать так:
| // Принять событие Event1 и сбросить автомат в начальное состояниеMyMachine << Event1 << RestMachine; |
Результатом работы автомата является состояние, в которое он перешел. Для получения текущего состояния напишем функцию и перегрузим оператор вывода в поток класса автомата:
| inline StateType GetCurrentState( void ) const { return CurrentState; }template <class SState, class SEvent, class SFunctor, class SUnknownEventStrategy >ostream &operator<< (ostream & Stream, const SFiniteStateMachine<_SState, _SEvent, _SFunctor,_SUnknownEventStrategy> & Machine ){ return Stream << Machine.GetCurrentState(); } |
Теперь, если для класса состояния определен оператор вывода в поток, можно написать такой фрагмент кода:
| MyMachine << Event1 << RestMachine;cout << MyMachine; // Эквивалентно cout << MyMachine.GetCurrentState(); |
Как уже говорилось, для сокращения времени набора кода и удобочитаемости определены несколько макросов. Они требуют предварительного определения подстановки для типов событий и состояний. Требование связано с тем, что использование вложенных директив препроцессора невозможно. Шаблон же использует Proxy классы, которым также нужны сведения о типах. Поэтому для использования макросов придется сделать так:
| #define FSMStateType string // Типсостояния#define FSMEventType int // Типсобытия. . .#undef FSMStateType#undef FSMEventType |
Альтернатива есть: полностью указывать все типы.
Осталось поместить шаблон в пространство имен. После этого им можно пользоваться.
Напишем код для решения поставленной в начале статьи задачи.
| #include <iostream>#include <string>using namespace std;#include "FiniteStateMachine.h"using namespace FSM;// Определимтипдлясобытийenum Events { letter = 0, digit = 1 };int main( int argc, char ** argv ){ #define FSMStateType string #define FSMEventType Events SFiniteStateMachine< StateType, EventType, SEmptyFunctor<StateType,EventType>, SThrowStrategy<EventType> > MyMachine( FSMBEGIN( "empty" ) FSMSTATES "empty" << "number" << "identifier" << "unknown" FSMEVENT(letter) "identifier" << "unknown" << "identifier" << "unknown" FSMEVENT(digit) "number" << "number" << "identifier" << "unknown" FSMEND ); #undef FSMStateType #undef FSMEventType cout << "StartState is: " << MyMachine << endl; MyMachine << digit << digit << letter; cout << "The 'unknown' state is expected. Current state is: " << MyMachine << endl;// Внимание: круглые скобки в следующей строке обязательны. Они обеспечат // правильный порядок выполнения операторовcout << "Reset the machine. Current state is: " << (MyMachine << ResetMachine) << endl; MyMachine << letter << digit << letter; cout << "The 'identifier' state is expected. Current state is: " << MyMachine << endl;return 0;} |
В примере намеренно опущены такие детали, как обработка исключений и введение функций, вызываемых при входе и выходе из состояния. Чтобы продемонстрировать возможность определения стратегий пользователя, в конструкторе MyMachine указаны все параметры, включая параметры по умолчанию.