Finite State Machine

#ifndef FSM_H_
#define FSM_H_

#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <iterator>

using namespace std;

namespace jst {

    namespace parsers {

    /**
     * classic FSM tuple
     * q0   start state
     * Q    set of states
     * F    subset of accepting states in Q
     * Σ   input alphabet
     * δ   state transition function
     */
    template<typename State, typename Input, typename Payload>
    class FSM {

    public:

        struct Action {
            virtual void action(FSM<State, Input, Payload>& fsm) = 0;
        };

        typedef set<State> state_set;
        typedef set<Input> input_set;
        typedef map<string, Action*> transducer_map;

    private:

        typedef vector< vector< pair<State, Action*> > > transition_table;

    public:

        /**
         * q starting state, p starting payload, Q legal states, F accepting states, Σ legal input, A transducer actions, Ad optional default action, Aa optional accepting action, Ar optional rejecting action
         */
        FSM(State q, Payload p, state_set& Q, state_set& F, input_set& Σ, transducer_map& A, Action* Ad = 0, Action* Aa = 0, Action* Ar = 0):
            q0(q),
            q(q0),
            P0(p),
            P(P0),
            Q(Q),
            F(F),
            Σ(Σ),
            A(A),
            Ad(Ad),
            Aa(Aa),
            Ar(Ar),
            δ(vector<vector< pair<State, Action*> > >(Q.size(), vector< pair<State, Action*> >(Σ.size(),pair<State, Action*>(q0, 0)))) {}

        /**
         * specify transitions
         * r1 start state, a the input, r2 target state, At optional transducer action fired on state change
         */
        void  add(State r1, Input a, State r2, string t) {
            δ[distance(Q.begin(), Q.find(r1))][distance(Σ.begin(), Σ.find(a))] = pair<State, Action*>(r2, A[t]);
        }

        Payload& payload() {
            return(P);
        }

        bool process(input_set& w) {
            for(typename input_set::const_iterator ai = w.begin(); ai != w.end(); ++ai)
                doTransition(q,*ai);
            if(F.find(q) != F.end())
                return(accepts());
            else
                return(rejects());
        }

        void reset() {
            q =q0;
            P = P0;
        }

        const State state() const {
            return q;
        }

        string toString() const {
            stringstream ss;
            ss << "FSM intially " << q0 << " currently " << q << (F.find(q) != F.end() ?"(accepting)" :"(rejecting)") << " payload " << P << endl << "legal states: ";
            for(typename state_set::iterator i = Q.begin(); i != Q.end(); ++i)
                ss << *i << " ";
            ss << endl << "accepting states: ";
            for(typename state_set::iterator i = F.begin(); i != F.end(); ++i)
                ss << *i << " ";
            ss << endl << "legal inputs: ";
            for(typename input_set::iterator i = Σ.begin(); i != Σ.end(); ++i)
                ss << *i << " ";
            ss << endl << "transition table:" << endl;
            for(int i = 0; i < Q.size(); ++i) {
                for(int j = 0; j < Σ.size(); ++j) {
                    ss << δ[i][j].first << " ";
                }
                ss << endl;
            }
            return(ss.str());
        }

        virtual ~FSM() {}

protected:

        bool accepts() {
            if(Aa)
                Aa->action(*this);
            return(true);
        }

        bool defaults() {
            if(Ad)
                Ad->action(*this);
            return(false);
        }

        void doTransition(State r, Input a) {
            typename state_set::const_iterator ri = Q.find(r);
            typename input_set::const_iterator ai = Σ.find(a);
            if(ri != Q.end() && ai != Σ.end()) {
                pair<State, Action*> qA = δ[distance(Q.begin(), ri)][distance(Σ.begin(), ai)];
                q = qA.first;
                if(qA.second)
                    qA.second->action(*this);
            }
            else
                defaults();
        }

        bool rejects() {
            if(Ar)
                Ar->action(*this);
            return(false);
        }

private:

        State q0;
        State q;
        Payload P0;
        Payload P;

        state_set& Q;
        state_set& F;
        input_set& Σ;
        transducer_map& A;

        Action* Ad;
        Action* Aa;
        Action* Ar;

        transition_table δ;// Q column Σ row table defines δ


    };

    }

}

#endif /* FSM_H_ */