/**
 * Finite Automata Demo.
 *
 * Defines the class Automaton, where:
 *   The states are unsigned ints (0, 1, ...);
 *   The initial state is 0;
 *   The alphabet includes all chars;
 *   Each state may have moves (transitions) associated with some chars;
 *       Undefined moves send the automaton to a "dead" state.
 *
 * Author: Erel Segal
 * Created: 2010-12
 */

#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
using namespace std;

typedef unsigned int State;
typedef map<char,State> Moves; // Moves === Transitions


class Automaton {
	vector<Moves> myMoves; // myMoves[i] = moves from state i
	unordered_set<State> myAcceptingStates; 
	
protected:
	
	bool run(const char* str, ostream* out=NULL) const {
		State state = 0;
		if (out) *out << '"' << str << '"' << ": ";
		for (; *str; ++str) {
			char c=*str;
			if (out) *out << state << " -"  << c << "-> ";

			/* Move to next state */
			const Moves* movesFromCurrentState = &myMoves[state];
			Moves::const_iterator it = movesFromCurrentState->find(c);
			if (it==movesFromCurrentState->end()) {
				if (out) *out << "DEAD";
				return false;
			}
			state = it->second;
		}
		if (myAcceptingStates.count(state)) {
			if (out) *out << state << ": ACCEPT";
			return true;
		} else {
			if (out) *out << state << ": REJECT";
			return false;
		}
	}
	
public:
	Automaton(int nStates): myMoves(nStates) {}

	Automaton& addMove(State from, char c, State to) {
		myMoves[from][c] = to;
		return *this;
	}
	
	Automaton& addAccepting(State s) {
		myAcceptingStates.insert(s);
		return *this;
	}

	bool accepts(const char* s) const { return run(s,NULL); }

	const Automaton& simulate(const char* s) const { run(s,&cout); cout<<endl; return *this; }
	
	const Automaton& assert(const char* s, bool expected) const {
		bool actual = run(s, NULL);
		if (actual != expected) {
			cerr << '"' << s << '"';
			if (actual && !expected)
				cerr << " should be rejected but was accepted:\n\t";
			else
				cerr << " should be accepted but was rejected:\n\t";
			run(s, &cerr);
		}
		return *this;
	}
};  // class Automaton


void testEven() {
	Automaton evenAB(2);
	cout << endl << "Detect even-length strings over {a,b}: "<<endl;
	evenAB.addMove(0, 'a', 1).addMove(0, 'b', 1)
	      .addMove(1, 'a', 0).addMove(1, 'b', 0)
	      .addAccepting(0);
	evenAB.assert("",true)
	      .assert("a",false).assert("b",false)
	      .assert("ab",true).assert("ba",true).assert("aa",true).assert("bb",true)
	      .assert("abba",true)
	      .assert("cc",false);
	evenAB.simulate("")
	      .simulate("a")
	      .simulate("ab")
	      .simulate("bab")
	      .simulate("babbbbbb")
	      .simulate("babacaca")
	      ;
}

void testPrefix() {
	Automaton prefix(4);
	cout << endl << "Detect strings that start with abc:"<<endl;
	prefix.addMove(0,'a',1).addMove(1,'b',2).addMove(2,'c',3)
	      .addMove(3,'a',3).addMove(3,'b',3).addMove(3,'c',3)
	      .addAccepting(3);
	prefix.assert("",false).assert("a",false).assert("ab",false).assert("abc",true)
	      .assert("abca",true).assert("abcb",true).assert("abcc",true).assert("abcba",true)
	      .assert("aabc",false).assert("babc",false).assert("cabc",false).assert("abcabc",true)
	      .assert("abb",false).assert("abbc",false);
	prefix.simulate("ab")
	      .simulate("abc")
	      .simulate("abcabababcbc")
	      .simulate("abbabcabcabc")
	      ;
}

void testSuffix() {
	Automaton suffix(4);
	cout << endl << "Detect strings that end with abc:"<<endl;
	suffix.addMove(0,'a',1).addMove(1,'b',2).addMove(2,'c',3)
	      .addMove(0,'b',0).addMove(0,'c',0)
	      .addMove(1,'a',1).addMove(1,'c',0)
	      .addMove(2,'a',1).addMove(2,'b',0)
	      .addMove(3,'a',1).addMove(3,'b',0).addMove(3,'c',0)
	      .addAccepting(3);
	suffix.assert("",false).assert("a",false).assert("ab",false).assert("abc",true)
	      .assert("abca",false).assert("abcb",false).assert("abcc",false).assert("abcba",false)
	      .assert("aabc",true).assert("babc",true).assert("cabc",true).assert("abcabc",true)
	      .assert("abb",false).assert("abbc",false);
	suffix.simulate("ab")
	      .simulate("abc")
	      .simulate("bbbabababcbcabc")
	      .simulate("abcabcabcabb")
	      ;
}

int main() {
	testEven();
	testPrefix();
	testSuffix();
}