#pragma once
typedef vector<DWORD> CDWordVector;
typedef vector<DWORD_PTR> CPDWordVector;

class CIntSet : CDWordVector
{
public:
	CIntSet(int initDim = 0);	// starting size
	int Find(int value, int start = 0);
	void Append(int value);
	void Append(CIntSet& iset);
	int size() const 
		{ return (int) CDWordVector::size(); }	// this takes care of bogus compiler error in VC++ (fixed in SP3)
	int at( size_type i ) const
		{ return ( int ) CDWordVector::at( i ); }	// this takes care of bogus compiler error in VC++ (fixed in SP3)
		
	CIntSet(const CIntSet &src);
	CIntSet &operator=(const CIntSet &src);
};
		
class CFAQuery 
{
public: 
	virtual BOOL ToStatesForEvent( int nFrom, TCHAR chOnInput, CIntSet& ToSet) = 0; 
	virtual int GetAcceptState() = 0; 
};

class CFABuild 
{
public: 
	virtual int NewState() = 0;
	virtual void AddTransition( int nSourceState, TCHAR chEvent, int nTargetState ) = 0;
	virtual void AddEmptyTransition( int nSourceState, int nTargetState ) = 0;
	virtual void SetAcceptState( int nAcceptState ) = 0;
}; 

enum { eSTARTSTATE = 0,
		eINVALIDSTATE = -1 };
		
#define EMPTYEVENT _T('\0')
#define ANYEVENT   _T('\1')

// Use of the envelope/letter idiom -- methods overridden by this 
// class are implemented by delegating to the letter class. 
class CFiniteAutomaton : protected CFAQuery
{
public:
	CFiniteAutomaton(CFAQuery&);
	virtual ~CFiniteAutomaton() {;}
		
	//methods overridden from base class. 
	virtual BOOL ToStatesForEvent(int nFrom, TCHAR chOnInput, CIntSet& ToSet);
	virtual int GetAcceptState(); 
		
private:
	CFAQuery *pFaQuery;
};
		
// the CAutomatonState class acts as an iterator for tracking 
// the state in input matching functions.
class CAutomatonState
{
	friend class CFiniteAutomaton;
		
public:
	virtual ~CAutomatonState();
		
	CAutomatonState(CFiniteAutomaton *parent, int startState);
		
	// Users are allowed to copy and assign iterators, though
	CAutomatonState(const CAutomatonState &src); 
	CAutomatonState &operator=(const CAutomatonState &src);
		
	virtual BOOL IsAccept();
	virtual BOOL IsValid();
		
	// Accepts an event and uses the state machine to move onto the 
	// next state Returns true if the state is non-terminal, ie not 
	// accept, and valid.
	virtual BOOL NextState(TCHAR chEvent);
		
private:
		
	CFiniteAutomaton *m_pParent;
	// current state is a set of states in a 
	// non-deterministic automaton
	CIntSet m_CurrentState;
		
	// Helper method to do the non-deterministic transitions
	void PerformTransitionSet(TCHAR chEvent); 
	void TraverseEvents(CIntSet &Source, CIntSet &Target, TCHAR chEvent);
};

#define MAXTRANS	4096
		
class CSimpleFA : public CFAQuery, public CFABuild 
{
public: 
	//Constructor
	CSimpleFA();
		
	//overridden from CFAQuery 
	virtual BOOL ToStatesForEvent(int nFrom, TCHAR chOnInput, CIntSet& ToSet);
	virtual int GetAcceptState(); 
		
	//overridden from CFABuild
	virtual int NewState();
	virtual void AddTransition(int nSourceState, TCHAR chEvent, int nTargetState);
	virtual void AddEmptyTransition(int nSourceState, int nTargetState);
	virtual void SetAcceptState(int nAcceptState);
		
private:
	//the tuple that defines a single transition. 
	struct STrans
	{
		int m_nFrom;
		int m_nTo;
		TCHAR m_ch;
	};
		
	//the number of states in the FA.
	int m_nStates;
		
	//the array of transitions.
	STrans m_Trans[MAXTRANS];
		
	//the number of transitions in the FA. 
	int m_nTrans;
		
	// the accepting state.
	int m_nAccState;
		
};
		
// uses the envelope/letter idiom to hide implementation -- the 
// letter never changes. methods overridden from base class are
// implemented by delegating them to a contained letter class.
class CRegExp : protected CFABuild 
{
public:
	CRegExp( CFABuild &Build ); 
	~CRegExp();
		
	void SetBuild( CFABuild *pBuild ); 
	CFABuild* GetBuild() const;
		
	// converts the given regular expression to a finite automaton. 
	// The finite automaton data is stored in the CFABuild instance 
	// owned by this object.
	void ConvertToFiniteAutomaton( LPCTSTR regexp );
		
protected:
	//methods overridden from CFABuild
	virtual int NewState();
	virtual void AddTransition( int nSourceState, TCHAR chEvent, int nTargetState );
	virtual void AddEmptyTransition( int nSourceState, int nTargetState );
	virtual void SetAcceptState( int nAcceptState );
		
private:
		
	// Converts a TCHARacter from an escape code to corresponding 
	// ASCII value
	TCHAR TranslateCh( TCHAR ch );
		
	// Determines whether the passed TCHARacter is in any way 
	// 'special', that is whether or not it is a meta-TCHARacter 
	// controlling the meaning of the regular expression string 
	BOOL SpecialChar( TCHAR ch );
		
	// Connects subexpression automaton to main automaton
	void ConnectSubExpr( int& outerFromState, int innerFromState, int innerToState, int& outerToState, BOOL& orOperatorFound );
		
	// Sub-expression stack members -- the structure used to hold 
	// the parent sub-expression information
	struct CSubExpState
	{
			int m_nS1;
			int m_nS2;
			int m_nS3;
			BOOL m_b1;
		
			CSubExpState( int i, int j, int k, BOOL b )
				: m_nS1( i ), m_nS2( j ), m_nS3( k ), m_b1( b ) {}
	};
	//	- save the parent sub-expression 
	void Push( int nS1, int nS2, int nS3, BOOL b1 );
	//	- restore the parent sub-expression 
	void Pop( int &nS1, int &nS2, int &nS3, BOOL &b1 );
	//	- the stack storage
	CPDWordVector m_SubExpStack;
		
private:
	//the contained letter class instance. 
	CFABuild* m_pBuild;
};		

BOOL RegExpStrCmp( CFiniteAutomaton &fa, LPCTSTR pszSearchText, int &nMatchLen );
