/// @file substringparser.hpp
/// A flexible parser which can creates a symbol dictionary of substrings
///
/// @remarks
///  This is a general purpose class which is designed to be used with any
///   compressor that wants to parse files and count occurrences of certain
///   characters/words/Substrings.  Parameters can be set to regulate how
///   symbols are extracted.  Several utility functions are provided so that
///   this class can by default do much of the work in parsing files and
///   pruning dictionaries.
///
/// @author mouser
/// @date   2003.07.29
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// recursive header protection
#ifndef Octane_SubstringParserH
#define Octane_SubstringParserH
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// application includes
#include "../parser.hpp"
#include "../../bitio/bitio.hpp"
// system includes
#include <vector>
#include <set>
#include <assert.h>
using namespace std;
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// Different types of parsing modes (greedy is fastest and usually not
//  significantly worse than LFF (longest substring first).  Deep is super
//  slow and not noticeably better.
#define Dictionary_ParseMode_GREEDY		0
#define Dictionary_ParseMode_LFF		1
#define Dictionary_ParseMode_DEEP		2
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// What kind of precision should we use for the weights? int should be fine.
typedef unsigned int TSubStrParserWeight;
#define TSubStrParserWeight_MAX	UINTMAX

// Biggest substring we will ever parser
#define SubStrHuff_BiggestSubStringLen 100
//---------------------------------------------------------------------------





//---------------------------------------------------------------------------
/// The SubString Symbol class represents the primitive symbols used by the
/// SubString parser.  Each symbol can hold an arbitrary string of character,
/// and is annotated with a 'weight' which stores the frequency of that
/// substring during the construction of the symbol table.  Symbols also
/// contain a numerical index which allows each symbol to report its
/// symbol id (position in the symbol vector), which is how parsers interact
/// with other components of statistical coding (by symbol id #).
class SubstringSymbol
{
protected:
	/// Frequency of the symbol, as calculated during a 'training' phase
	TSubStrParserWeight weight;
	/// Value represented by the symbol (i.e. the character, word, or Substring).
	std::string value;
	/// Each symbol keeps track of its position in symbol vector.
	int symbolvectorpos;
public:
	// Constructor and destructor
	SubstringSymbol () {weight=0;value="";}
	SubstringSymbol (const std::string &invalue, TSubStrParserWeight inweight=0) {weight=inweight; value=invalue;}
	~SubstringSymbol () {;}
public:
	/// The comparison operator used to order the priority queue.
	bool operator>( const SubstringSymbol * &a ) const {return weight > (a->get_weight());}
public:
	/// Returns the current weight (frequency) of the symbol.
	TSubStrParserWeight get_weight() const {return weight;}
	/// Increment weight/frequency of symbol.
	void increment_weight(int increment) {weight+=increment;}
	/// Set weight of symbol.
	void set_weight(TSubStrParserWeight val) {weight=val;}
	/// Get pointer to string value of symbol.
	std::string* get_valuep() {return &value;}
	/// Get string value of symbol (i.e. the text of the symbol).
	std::string& get_value() {return value;}
	/// Get length of symbol string.
	int get_valuelen() {return (int)(value.length());}
	/// Set value of symbol string.
	void set_value(const std::string &invalue) {value=invalue;}
	/// Return the symbol id # (the position of the symbol in the symbol vector).
	int get_symbolvectorpos() {return symbolvectorpos;};
	/// Set the symbol id #.
	void set_symbolvectorpos(int inpos) {symbolvectorpos=inpos;};
public:
	/// Returns true if this is a "primitive" protected symbol and should not be pruned.
	/// used for things like insisting that the ascii characters are never pruned from symbol set even though they are not used during training.
	bool dontprune() {if (value.length()<=1) return true; else return false;}
	/// Returns the actual memory used by this symbol (uses string.capacity).
	unsigned int get_memoryused() const {return (unsigned int)(sizeof(this)+value.capacity());}
	/// The parser may evaluate the quality of its symbol set by estimating the "cost" of the symbolset
	/// even in the absence of any specified coding and compression strategy;
	/// it calculates the cost of each symbol as the inverse of frequency, lower is better.
	double get_cost() {return 1.0/(1.0+weight);};
};


/// Greater operator for comparing weights of symbol pointers.
/// We need to make a special Greater<> classes used during sorting, since
///  our collection stl elements are built from pointers, and the default sort
///  will be done on pointer addresses instead of weights if we don't.
template< class T >
class TSubstringSymbolWeightGreater
	{
	public:
		bool operator() (const T& pLeft, const T& pRight) const
			{ return pLeft->get_weight()>pRight->get_weight(); }
	};


/// Greater operator for comparing strings of symbol pointers alphabetically.
/// We need to make a special Greater<> classes used during sorting, since
///  our collection stl elements are built from pointers, and the default sort
///  will be done on pointer addresses instead of weights if we don't.
template< class T >
class TSubstringSymbolStringGreater
	{
	public:
		bool operator() (const T& pLeft, const T& pRight) const
			{ return pLeft->get_value()<pRight->get_value(); }
	};
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
/// The SubstringParser class is a flexible parser, which uses arbitrarily
///  long substrings of text as symbols.
/// It can be configured to build a symbol set using only whole words, or with
///  substrings that are not affected by word boundary (max symbol length can be set).
/// Various input parsing strategies can be used, from greedy (fastest) to
///  longest first, to near optimal (slowest).
/// Various heuristics for pruning the symbol set can be applied, which can be
///  used to get the symbol set down to a desired size.
/// @ingroup Parsers
class SubstringParser : public OctaneParser
{
protected:
	/// Typedef for stl set of symbols (used for fast alphabetical lookup)
	typedef std::set< SubstringSymbol* , TSubstringSymbolStringGreater<SubstringSymbol*> > TSymbolSetTYPE;
	/// Typedef for stl vector of symbols (used for fast lookup by id#)
	typedef std::vector< SubstringSymbol* > TSymbolVectorTYPE;
	/// STL set of symbols (used for fast alphabetical lookup)
	TSymbolSetTYPE symbolset;
	/// STL vector of symbols (used for fast lookup by id#)
	TSymbolVectorTYPE symbolvector;
	/// STL set iterator - this is a non-local variable to eliminate cost of building it on stack on every local function
	TSymbolSetTYPE::iterator symbolset_pos;
	/// Stl vector iterator - this is a non-local variable to eliminate cost of building it on stack on every local function
	TSymbolVectorTYPE::iterator symbolvector_pos;
	/// Current window buffer for parsing, filled as we read input characters
	char inputbufferstr[SubStrHuff_BiggestSubStringLen] ;
	/// Length of input window buffer
	int inputbufferlen;
	/// The parser needs to return an end-of-symbol character before finishing reading the stream, so we need to track whether we sent an EOS yet.
	/// @todo this is an odd responsibility for the parser to have to deal with, so we should probably find a way to eliminate this.
	bool senteos;
protected:
	// Encoding parameters which govern how dictionary is built (see SetDefaultDictionaryBuildingParameters implementation for descriptions)
	/// The dictionary will never be allowed to get bigger than this size (smaller will also increase building speed)
	///  when this size is exceeded, we will eliminate all symbols with frequencies of smaller than some small #
	unsigned int Parameter_MaxSymbols_DuringBuild;
	/// After the entire training file is parsed, we will repeat pruning steps to reduce it to a *maximum* of this many entries
	///  the actual symbols kept may be smaller depending on other pruning parameters
	unsigned int Parameter_MaxSymbols_Final;
	/// How many characters is largest (sub)string stored in dictionary
	int Parameter_MaxSubstringSize;
	/// Only store characters and whole words?
	bool Parameter_OnlyCodeWholeWords;
	/// Store Substrings that span words (i.e. they contain multiple words)
	bool Parameter_SpanWordBoundaries;
	// When encoding single lines, each line must end with an end-of-stream (EOS) symbol
	//  but if we train on a file, which is large and has only one EOS at end of file
	//  then the freq. of EOS will be very low (1), so here we can say to count a pretend EOS
	//  whenever we see a CR.
	bool Parameter_CountCRsAsEOTs;
	/// Minimum count for a word or Substring in order to even consider leaving it in the dictionary
	unsigned int Parameter_PruneMinimumWeight;
	/// We can either use a greedy search to find longest Substring starting with first char or we can use smarter but slower heuristics
	int Parameter_ParseMode;
	/// We can either use a smart search using stl find_lower_bound() to find longest Substring or we can search starting at biggest string backwards
	bool Parameter_UseSmartLookup;
	/// How many iterations should we recompress to test heuristic symbolset cost, if any
	///  this tests the currently built symbol set to 'reencode' the input stream and calculates actual usage counts and then reprunes.
	bool Parameter_PruneReCalculations;
protected:
	/// Keeps track of how many symbols have we created for fast replies
	int symbolcount;
	/// Keeps track of end of stream symbol number for fast replies
	int endofstreamsymbolnum;
	/// Stores last bitreader , so that we can rewind when we want to reparse and check our heuristic symbolset costs
	bitreader *current_bitreaderp;
	/// Stores last bitreader starting position before parsing, so that we can rewind when we want to reparse and check our heuristic symbolset costs
	size_t start_bitreaderposition;
public:
	//---------------------------------------------------------------------------
	/// Constructor
	SubstringParser();
	/// Destructor
	~SubstringParser();
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// PARSER PUBLIC API - PREPARATIONS FOR PARSING
	virtual bool CreateSymbolSetUsingStream(bitreader &from);
	virtual bool IsReadyToParse() {if (symbolcount>0) return true; else return false;};
	virtual bool RewindAnyBufferedInput(bitreader &from);
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// PARSER PUBLIC API - MAIN PARSING FUNCTIONS
	/// Synchronize state for a new stream - this is called every time a new stream is parsed, to allow parser to get into 'start' state,
	virtual void SynchronizeStateForNewStream();
	virtual int GetSymbolCount() {return symbolcount;};
	virtual bool ParseNextSymbolFromInput(bitreader &from, int &symbolnum);
	virtual bool WriteSymbolText(bitwriter &to, int symbolnum,bool &isendofstreamsymbol);
	virtual string LookupSymbolText(int symbolnum) {assert(symbolnum<(int)(symbolvector.size()));return symbolvector[symbolnum]->get_value();};
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// OCTANE PUBLIC API - AUXILIARY FUNCTIONS - these are supported by all derived classes
	virtual void ShowDebuggingInfo();
	virtual unsigned int GetMemoryUsed();
	virtual unsigned int GetDiskspaceUsed(bool fortempdecompressiononly);
	virtual std::string GetParametersInformation();
	virtual void SetDefaultParameters();
	virtual bool SetParameter(const std::string &parametername,const std::string &parametervalue);
	virtual bool SaveState(bitwriter &to,bool fortempdecompressiononly);
	virtual bool LoadState(bitreader &from);
	//---------------------------------------------------------------------------
public:
	//---------------------------------------------------------------------------
	// OCTANE PARSER PUBLIC API - AUXILIARY FUNCTIONS - symbol helpers
	int GetSetSymbolCount() {return (int)(symbolset.size());};
	int LookupSymbolNumberFromText(string wordstring);
	//---------------------------------------------------------------------------
private:
	// save and load state information
	/// Save complete state info (the entire symbolset and parameters).
	/// @return true on success.
	bool SaveSymbols(bitwriter &to);
	/// Load complete state info (the entire symbolset and parameters).
	/// @return true on success.
	bool LoadSymbols(bitreader &from);
private:
	// symbol manipulation
	/// Add the ascii characters 0-255 to the symbol set, in addition to the end-of-stream symbol
	void AddPrimitiveCharacterSubstringSymbols();
	/// Lookup a symbol based on its text and Increase the frequency of the symbol.
	/// The symbol will be created if it doesn't already exist.
	/// @return true on success.
	bool UpdateValueStringInSymbolSet(const string &stringvalue,int increment);
	/// Add all substrings contained in a window are added to dictionary (based on parameters defining which substrings to add).
	void AddSubstringsFromSlidingWindowString(string &slidingwindowstring);
	/// Create a new symbol and add it to symbol set with specific starting frequency.
	SubstringSymbol* AddSymbol(const std::string &stringvalue, const TSubStrParserWeight weightvalue) {SubstringSymbol* p=new SubstringSymbol(stringvalue,weightvalue);if (p!=NULL) symbolset.insert(p);return p;}
private:
	// internal save/load helper functions
	/// Save parameters to stream.
	/// @return true on success.
	bool SaveParameters(bitwriter &to);
	/// Load parameters from stream.
	/// @return true on success.
	bool LoadParameters(bitreader &from);
	/// Save symbol to stream.
	/// @return true on success.
	bool ReadSubstringSymbol(bitreader &from);
	/// Load symbol from stream.
	/// @return true on success.
	bool WriteSubstringSymbol(SubstringSymbol *SubstringSymbolp,bitwriter &to);
private:
	/// Reset weights on all symbols, in preparation for reparsing.
	void ResetWeights();
private:
	// Prune symbols from the set
	/// Engage pruning routine, calls various other pruning steps.
	void PruneSymbolSet();
	/// Eliminate least frequent symbols in order to achieve a target symbol set size.
	void PruneSymbolSet_ReduceSizeTo(unsigned int targetsize);
	/// Eliminate all symbols with frequency counts below some threshold.
	void PruneSymbolSet_WeightThreshold(TSubStrParserWeight thresholdweight);
	/// Eliminate all symbols whose string values are proper prefixes of other symbols with equal frequencies
	void PruneSymbolSet_RemoveRedundantPrefixes();
	/// Re-parse the training file and compute heuristic costs of encoding and recompute symbol weight given current symbols.
	/// This is necessary because after adding symbols and pruning, the frequency counts change due to interactions.
	double ReParseFileReComputeCosts(bool updateweights);
private:
	/// A heuristic cost computation that returns a cost of the symbol (just inverse of frequency).
	/// This is used to help decide the heuristic cost of a symbol set on a whole file.
	double GetSymbolCost(SubstringSymbol* symbolnodep) {return symbolnodep->get_cost();};
private:
	// Internal encoding and finding symbols to encode
	/// Given an input string window(buffer), pick out the symbol corresponding to leftmost string, according to parsing rules.
	/// @return symbol pointer or NULL if no symbol could be found (which would be considered an error)
	SubstringSymbol* FindNextSymbolToEncode(char *inputqueuestr,int inputqueuestrlen);
	/// Use simple greedy mode to choose longest leftmost symbol from input buffer
	/// @return symbol pointer or NULL if no symbol could be found (which would be consider an error)
	/// @see FindNextSymbolToEncode
	SubstringSymbol* FindNextSymbolToEncode_Greedy(char *inputqueuestr,int inputqueuestrlen);
	/// After choosing a symbol to encode, this eats it from he input window buffer (and optionally displays some debugging info)
	int SwallowSymbolFromInputQueueStr(SubstringSymbol *symbolp,char *inputqueuestr,int inputqueuestrlen,bool debugmode);
	/// Calculate the heuristic cost of parsing a window of text, using current parsing mode.
	/// This is used to optimally parse an input string by finding best way to divide it up into symbols.
	double CalculateEncodeCost(char *inputqueuestr,int inputqueuestrlen);
private:
	/// build a vector of symbols for easy random access
	void BuildSymbolVector();
private:
	/// Free data held by the class.
	void FreeData();
	/// Free symbol data held by the class.
	void FreeData_Symbols();
};
//---------------------------------------------------------------------------





//---------------------------------------------------------------------------
#endif
//---------------------------------------------------------------------------

