// The basic representation of the finite state acceptor consists of
// states and transitions.

class State;
class Transition;

// The set of transitions from a state is more conveniently
// represented as a list of transition pairs comprising of an
// input character and the destination state.

class TransitionList : public list<Transition *> {
public:
	Transition *findTrigger(char);
};

// A basic FSA state consists of a state identity, a set of transitions
// and for the case of a final node, the associated token.  Each state
// instance is assigned a new identity name in its constructor by
// incrementing the nextStateId counter.

class State {
private:
	int _id;
	LexRule *_associatedToken;
public:
	TransitionList transitions;
	LexRule *associatedToken() { return _associatedToken; }
	void associateWith(LexRule *r) { _associatedToken = r; }
	int id() { return _id; }
	State() : transitions()
	{
	    _id = nextStateId++; _associatedToken = 0;
	}
	virtual void print(void);
private:
	static int nextStateId;
};

// A transition from a state is represented by a trigger symbol and a
// reference to the destination state.

class Transition {
public:
	static const int NOCHAR;
	static int minChar, maxChar;
private:
	char _trigger;
	State *_destination;
public:
	char trigger() { return _trigger; }
	State *destination() { return _destination; }
	Transition(char c, State* dest);
	void print(void);
};

// The class fsaState is derived from the State class, but with the
// functionality to compute lambda closures (via getClosure()).

class fsaState;

// The closure set is represented by the fsaStateList class.

class fsaStateList : public list<fsaState *> {
public:
	fsaState *findFinalState(void);
};

class fsaState : public State {
public:
	static fsaStateList stateSet;
	static fsaState *initialState;
	void getClosure(fsaStateList *);
	static void makeFsa();
	// The use of the dummy variable is a workaround since
	// gcc cannot take the following syntax:
	// fsaState() : State() {  stateSet.append(this); }
	fsaState() : State() { fsaState *dummy = this; stateSet.append(dummy); }
};

// The dfsaState allows the representation of a deterministic FSA.  Each
// instance is associated with a closure set of the states from the
// non-deterministic machine, and from there, completeMachine() allows
// for subsequent transitions to be filled in.

class dfsaState;

// The dfsaStateList class holds a list of dfsaState instances.  The
// member function matchClosure() searches for a dfsaState instance with
// a closure equal to that of the target.  This allows existing states
// to be distinguished from new states.

class dfsaStateList : public list<dfsaState *> {
public:
	dfsaState *matchClosure(fsaStateList *target);
};

class dfsaState : public State {
	void completeMachine();
public:
	static dfsaStateList stateSet;
	static dfsaState *initialState;
	static void makeDfsa();
	fsaStateList *closure;
	dfsaState(fsaStateList *c);
};

// The odfsaState allows the representation of a optimised deterministic
// FSA.  Each instance is associated with a partition set of the states
// from the deterministic machine, and from there, checkPartition()
// confirms that each partition is consistent.  When a partition fails
// the consistency test, it is repartitioned via spliting itself.

class odfsaState;

// The odfsaStateList class holds a list of odfsaState instances.  The
// member function matchConstituents() searches for an odfsaState
// instance whose constituents contain the target.

class odfsaStateList : public list<odfsaState *> {
public:
	odfsaState *matchConstituents(dfsaState *);
};

class odfsaState : public State {
public:
	static odfsaStateList stateSet;
	static odfsaState *initialPartition;
	static odfsaState *nonfinalPartition;
	static odfsaState *finalPartition;
	static void optimiseDfsa(void);
	dfsaStateList *constituents;
	bool checkPartition(void);
	void includeTransitions(void);
	virtual void print(void);
	odfsaState() : State() {
		constituents = new dfsaStateList();
		odfsaState *dummy = this; stateSet.append(dummy);
	}
};