Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

libs/msm/doc/HTML/examples/ParsingDigits.cpp

// Copyright 2010 Christophe Henry
// henry UNDERSCORE christophe AT hotmail DOT com
// This is an extended version of the state machine available in the boost::mpl library
// Distributed under the same license as the original.
// Copyright for the original version:
// Copyright 2005 David Abrahams and Aleksey Gurtovoy. Distributed
// under the Boost Software License, Version 1.0. (See accompanying
// file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

#define FUSION_MAX_VECTOR_SIZE 20

#include <boost/msm/back/state_machine.hpp>
#include "char_event_dispatcher.hpp"
#include <boost/msm/front/state_machine_def.hpp>
#include <boost/msm/front/functor_row.hpp>
#include <boost/timer.hpp>

namespace msm = boost::msm;
namespace mpl = boost::mpl;
using namespace msm::front;

#include <iostream>
#ifdef WIN32
#include "windows.h"
#else
#include <sys/time.h>
#endif

// events
struct end_sub {template <class Event> end_sub(Event const&){}};
struct other_char {};
struct default_char {};
struct eos {};


namespace test_fsm // Concrete FSM implementation
{
    // Concrete FSM implementation 
    struct parsing_ : public msm::front::state_machine_def<parsing_>
    {
        // no need for exception handling or message queue
        typedef int no_exception_thrown;
        typedef int no_message_queue;

        struct Waiting : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Waiting" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Waiting" << std::endl;}
        };
        struct Digit1 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit1" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit1" << std::endl;}
        };
        struct Digit2 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit2" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit2" << std::endl;}
        };
        struct Digit3 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit3" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit3" << std::endl;}
        };
        struct Digit4 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit4" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit4" << std::endl;}
        };
        struct MinusChar1 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar1" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar1" << std::endl;}
        };
        struct Digit5 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit5" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit5" << std::endl;}
        };
        struct Digit6 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit6" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit6" << std::endl;}
        };
        struct Digit7 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit7" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit7" << std::endl;}
        };
        struct Digit8 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit8" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit8" << std::endl;}
        };
        struct MinusChar2 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar2" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar2" << std::endl;}
        };
        struct Digit9 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit9" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit9" << std::endl;}
        };
        struct Digit10 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit10" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit10" << std::endl;}
        };
        struct Digit11 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit11" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit11" << std::endl;}
        };
        struct Digit12 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit12" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit12" << std::endl;}
        };
        struct MinusChar3 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: MinusChar3" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: MinusChar3" << std::endl;}
        };
        struct Digit13 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit13" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit13" << std::endl;}
        };
        struct Digit14 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit14" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit14" << std::endl;}
        };
        struct Digit15 : public msm::front::state<>  
        {
            // optional entry/exit methods
            //template <class Event,class FSM>
            //void on_entry(Event const&,FSM& ) {std::cout << "entering: Digit15" << std::endl;}
            //template <class Event,class FSM>
            //void on_exit(Event const&,FSM& ) {std::cout << "leaving: Digit15" << std::endl;}
        };
        //struct Start : public msm::front::state<> {};
        struct Parsed : public msm::front::state<> {};
        //struct Failed : public msm::front::state<> {};

        // the initial state of the player SM. Must be defined
        typedef Waiting initial_state;
        // transition actions
        struct test_fct
        {
            template <class FSM,class EVT,class SourceState,class TargetState>
            void operator()(EVT const& ,FSM&,SourceState& ,TargetState& )
            {
                std::cout << "Parsed!" << std::endl;
            }
        };

        // guard conditions


        // Transition table for parsing_
        struct transition_table : mpl::vector<
            //    Start         Event                Next      Action                Guard
            //    +-------------+-------------------+---------+---------------------+----------------------+
              Row < Waiting     , digit             , Digit1                                                >,
              Row < Digit1      , digit             , Digit2                                                >,
              Row < Digit2      , digit             , Digit3                                                >,
              Row < Digit3      , digit             , Digit4                                                >,
              Row < Digit4      , event_char<'-'>   , MinusChar1                                            >,
              Row < MinusChar1  , digit             , Digit5                                                >,
              Row < Digit5      , digit             , Digit6                                                >,
              Row < Digit6      , digit             , Digit7                                                >,
              Row < Digit7      , digit             , Digit8                                                >,
              Row < Digit8      , event_char<'-'>   , MinusChar2                                            >,
              Row < MinusChar2  , digit             , Digit9                                                >,
              Row < Digit9      , digit             , Digit10                                               >,
              Row < Digit10     , digit             , Digit11                                               >,
              Row < Digit11     , digit             , Digit12                                               >,
              Row < Digit12     , event_char<'-'>   , MinusChar3                                            >,
              Row < MinusChar3  , digit             , Digit13                                               >,
              Row < Digit13     , digit             , Digit14                                               >,
              Row < Digit14     , digit             , Digit15                                               >,
              Row < Digit15     , eos               , Parsed                                                >,
              Row < Parsed      , eos               , Waiting                                               >
            //    +---------+-------------+---------+---------------------+----------------------+
        > {};


        // Replaces the default no-transition response.
        template <class FSM,class Event>
        void no_transition(Event const& e, FSM&,int state)
        {
            std::cout << "no transition from state " << state
                << " on event " << typeid(e).name() << std::endl;
        }
    };
    typedef msm::back::state_machine<parsing_> parsing;
}

#ifndef WIN32
long mtime(struct timeval& tv1,struct timeval& tv2)
{
    return (tv2.tv_sec-tv1.tv_sec) *1000000 + ((tv2.tv_usec-tv1.tv_usec));
}
#endif

// This declares the statically-initialized char_event_dispatcher instance.
template <class Fsm>
const msm::back::char_event_dispatcher<Fsm>
msm::back::char_event_dispatcher<Fsm>::instance;

struct Parser
{
    Parser():p(){p.start();}
    void new_char(char c)
    {
        typedef msm::back::char_event_dispatcher<test_fsm::parsing> table;
        table::instance.process_event(p,c);
    }
    void finish_string(){p.process_event(eos());}
    void reinit(){p.process_event(eos());}
    test_fsm::parsing p;
};

void msm_match(const char* input)
{
    test_fsm::parsing p;
    p.start();

    int j=0;
    while(input[j])
        //for (size_t j=0;j<len;++j)
    {
        switch (input[j])
        {
        case '0':
            p.process_event(char_0());
            break;
        case '1':
            p.process_event(char_1());
            break;
        case '2':
            p.process_event(char_2());
            break;
        case '3':
            p.process_event(char_3());
            break;
        case '4':
            p.process_event(char_4());
            break;
        case '5':
            p.process_event(char_5());
            break;
        case '6':
            p.process_event(char_6());
            break;
        case '7':
            p.process_event(char_7());
            break;
        case '8':
            p.process_event(char_8());
            break;
        case '9':
            p.process_event(char_9());
            break;
        case '-':
            p.process_event(event_char<'-'>());
            break;
        default:
            p.process_event(default_char());
            break;
        }
        ++j;
    }
    p.process_event(eos());
    p.process_event(eos());
}

double time_match(const char* text)
{
    boost::timer tim;
    int iter = 1;
    int counter, repeats;
    double result = 0;
    double run;
    do
    {
        tim.restart();
        for(counter = 0; counter < iter; ++counter)
        {
            msm_match( text);
        }
        result = tim.elapsed();
        iter *= 2;
    } while(result < 0.5);
    iter /= 2;

    // repeat test and report least value for consistency:
    for(repeats = 0; repeats < 10; ++repeats)
    {
        tim.restart();
        for(counter = 0; counter < iter; ++counter)
        {
            msm_match( text);
        }
        run = tim.elapsed();
        result = (std::min)(run, result);
    }
    return result / iter;
}
int main()
{
    // for timing
#ifdef WIN32
    LARGE_INTEGER res;
    ::QueryPerformanceFrequency(&res);
    LARGE_INTEGER li,li2;
#else
    struct timeval tv1,tv2;
    gettimeofday(&tv1,NULL);
#endif

    test_fsm::parsing p;
    p.start();
    const char* input = "1234-5678-1234-456";
    size_t len = strlen(input);
    // for timing
#ifdef WIN32
    ::QueryPerformanceCounter(&li);
#else
    gettimeofday(&tv1,NULL);
#endif
    for (int i=0;i<1000;++i)
    {
        int j=0;
        while(input[j])
        //for (size_t j=0;j<len;++j)
        {
            switch (input[j])
            {
            case '0':
                p.process_event(char_0());
                break;
            case '1':
                p.process_event(char_1());
                break;
            case '2':
                p.process_event(char_2());
                break;
            case '3':
                p.process_event(char_3());
                break;
            case '4':
                p.process_event(char_4());
                break;
            case '5':
                p.process_event(char_5());
                break;
            case '6':
                p.process_event(char_6());
                break;
            case '7':
                p.process_event(char_7());
                break;
            case '8':
                p.process_event(char_8());
                break;
            case '9':
                p.process_event(char_9());
                break;
            case '-':
                p.process_event(event_char<'-'>());
                break;
            default:
                p.process_event(default_char());
                break;
            }
            ++j;
        }
        p.process_event(eos());
        p.process_event(eos());
    }
#ifdef WIN32
    ::QueryPerformanceCounter(&li2);
#else
    gettimeofday(&tv2,NULL);
#endif
#ifdef WIN32
    std::cout << "msm(1) took in s:" << (double)(li2.QuadPart-li.QuadPart)/res.QuadPart <<"\n" <<std::endl;
#else
    std::cout << "msm(1) took in us:" <<  mtime(tv1,tv2) <<"\n" <<std::endl;
#endif

    Parser parse;
    // for timing
#ifdef WIN32
    ::QueryPerformanceCounter(&li);
#else
    gettimeofday(&tv1,NULL);
#endif
    for (int i=0;i<1000;++i)
    {
        for (size_t j=0;j<len;++j)
        {
            parse.new_char(input[j]);
        }
        parse.finish_string();
        parse.reinit();
    }
#ifdef WIN32
    ::QueryPerformanceCounter(&li2);
#else
    gettimeofday(&tv2,NULL);
#endif
#ifdef WIN32
    std::cout << "msm(2) took in s:" << (double)(li2.QuadPart-li.QuadPart)/res.QuadPart <<"\n" <<std::endl;
#else
    std::cout << "msm(2) took in us:" <<  mtime(tv1,tv2) <<"\n" <<std::endl;
#endif
    std::cout << "msm(3) took in s:" << time_match(input) <<"\n" <<std::endl;
    return 0;
}