Boolean Text Search Queries and their Processing

//
// ACMachine.hpp
//

#ifndef AHO_CORASICK_MACHINE_HPP_INCLUDED
#define AHO_CORASICK_MACHINE_HPP_INCLUDED

#include <string>

#include <queue>
#include <hash_map>
#include <algorithm>
#include <set>


class Expression;
struct ACPMMachineState;

typedef std::pair< std::wstring, Expression* > Match;
typedef std::set< Match > MatchList;

typedef stdext::hash_map< wchar_t, ACPMMachineState* > StatesHash;
typedef std::queue< ACPMMachineState* > StatesQueue;


struct ACPMMachineState {
    ACPMMachineState();
    ACPMMachineState( const ACPMMachineState* parent, wchar_t character );

	/* Character, associated with this state*/
    wchar_t character_;

	/* Child states */
    StatesHash transitions_;

	/* For acceptance states - contains patterns, associated with this state */
    MatchList output_;

	/* Parent state */
    const ACPMMachineState* parent_;

	/* Failure transition state */
    ACPMMachineState* failure_;
};

class ACPMMachine {
public:
    ACPMMachine();
	~ACPMMachine();

	/* Adds a string to the prefix tree */
    void addPattern( const std::wstring& pattern, Expression* associatedObject );

	/* Computes failure transitions for each state */
    void computeStates();

	/* Changes current FSM state */
    bool feedCharacter( wchar_t );

	/* Returns list of patterns associated with current state*/
    const MatchList& getCurrentMatch() const;

	/* Resets current state to root state*/
    void reset();
    
private:
    ACPMMachine( const ACPMMachine& );
    ACPMMachine& operator= ( const ACPMMachine& );

private:
    static ACPMMachineState* FindTransition ( ACPMMachineState* state, wchar_t character );
    static void AddTransition ( ACPMMachineState* from, ACPMMachineState* to );
private:
    ACPMMachineState* currentState_;
    ACPMMachineState* root_;
}; 

#endif // AHO_CORASICK_MACHINE_HPP_INCLUDED