/// @file substringparser.cpp
/// 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
//---------------------------------------------------------------------------

//---------------------------------------------------------------------------
// Application includes
#include "substringparser.hpp"
// System includes
#include <iostream>
#include <iomanip>
#include <string>
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
SubstringParser::SubstringParser()
{
	// constructor
	// initialize default dictionary-building parameters
	SetDefaultParameters();
	// initialize our current symbol count and end-of-stream-symbol
	symbolcount=0;
	endofstreamsymbolnum=-1;
	// initialize input buffer pos
	inputbufferlen=0;
	senteos=false;
}

SubstringParser::~SubstringParser()
{
	// destructor frees the SubstringSymbols in symbolset
	FreeData();
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// OCTANE PUBLIC API - AUXILIARY FUNCTIONS
bool SubstringParser::SaveState(bitwriter &to,bool fortempdecompressiononly)
{
	// save state
	// return true on success
	bool bretv;
	bretv=SaveParameters(to);
	if (bretv)
		bretv=SaveSymbols(to);
	return bretv;
}

bool SubstringParser::LoadState(bitreader &from)
{
	// load state
	// return true on success
	bool bretv;
	bretv=LoadParameters(from);
	if (bretv)
		bretv=LoadSymbols(from);
	return bretv;
}


unsigned int SubstringParser::GetMemoryUsed()
	{
	// return memory used by this data structure
	unsigned int memoryused=sizeof(this);

	// this returns the size of the symbolset, as it would take up on disk if saved in straightforward way
	//  memory usage will be almost identical.
	memoryused+=sizeof(symbolset);
	// write entries in compact binary form
	for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
		{
		memoryused+=sizeof(*symbolset_pos);
		memoryused+=(*symbolset_pos)->get_memoryused();
		}
	// for vector
	for (symbolvector_pos=symbolvector.begin();symbolvector_pos!=symbolvector.end();++symbolvector_pos)
		memoryused+=sizeof(*symbolvector_pos);
	
	return memoryused;
	}


unsigned int SubstringParser::GetDiskspaceUsed(bool fortempdecompressiononly)
{
	// this returns the size of the symbolset, as it would take up on disk if saved in straightforward way
	//  memory usage will be almost identical.
	unsigned int memoryused=0;

	// byte for file type (see WriteSymbolSet routine)
	memoryused+=1;
	
	// write entries in compact binary form
	for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
		{
		// length of the string
		memoryused+=1;
		// write string
		memoryused+=(unsigned int)(((*symbolset_pos)->get_valuep())->length());
		// weight of symbol
		memoryused+=sizeof(unsigned short int);
		}

	// end-of-header
	memoryused+=1;
	return memoryused;
}




void SubstringParser::ShowDebuggingInfo()
{
	// show some debugging info
	using namespace std;
	string bitset_string;
	string value;

	// size of tree is
	std::cout << " Memory used by SubStringParser: " << GetMemoryUsed() << " bytes ("<< (unsigned int)(GetSetSymbolCount())<<" elements).\n";
	
	// show the dictionary sorted alphabetically
	if (symbolset.size()>0)
		{
		cout << "Symbol Set - Sorted Alphabetically ("<<(unsigned int)(symbolset.size())<<" entries)\n";
		cout << " " << setiosflags(ios::left) << setw(Parameter_MaxSubstringSize) << "symboltext" << " " << setw(10) << "frequency\n";
		cout << " " << setiosflags(ios::left) << setw(Parameter_MaxSubstringSize) << "----------" << " " << setw(10) << "---------\n";
		for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
			{
			value=(*symbolset_pos)->get_value();
			NiceifyHighAsciiString(value);
			cout << " " << setiosflags(ios::left) << setw(Parameter_MaxSubstringSize) << value << " " << setw(10) << (*symbolset_pos)->get_weight() << "\n";
			}
		cout << "\n";
		}
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// OCTANE PUBLIC API - AUXILIARY FUNCTIONS
	
string SubstringParser::GetParametersInformation()
{
	// show user available variables and their current values
	// ATTN: this has not been converted from cout to string
	string returnstring;
	cout << setiosflags(ios::left) << setw(17) << "maxbuildsymbols" << setiosflags(ios::left) << " " << setw(10) << Parameter_MaxSymbols_DuringBuild << " " << "parsing dictionary pruned to not exceed this size" << endl;
	cout << setiosflags(ios::left) << setw(17) << "maxsymbols" << setiosflags(ios::left) << " " << setw(10) << Parameter_MaxSymbols_Final << " " << "final dictionary pruned to reach this size" << endl;
	cout << setiosflags(ios::left) << setw(17) << "maxSubstring" << setiosflags(ios::left) << " " << setw(10) << Parameter_MaxSubstringSize << " " << "max size of Substrings in dictionary" << endl;
	cout << setiosflags(ios::left) << setw(17) << "onlywords" << setiosflags(ios::left) << " " << setw(10) << Parameter_OnlyCodeWholeWords << " " << "only add whole word symbols? (bool)" << endl;
	cout << setiosflags(ios::left) << setw(17) << "spanwords" << setiosflags(ios::left) << " " << setw(10) << Parameter_SpanWordBoundaries << " " << "encode symbols that span words? (bool)" << endl;
	cout << setiosflags(ios::left) << setw(17) << "crends" << setiosflags(ios::left) << " " << setw(10) << Parameter_CountCRsAsEOTs << " " << "count CRs as end-of-stream symbols? (bool)" << endl;
	cout << setiosflags(ios::left) << setw(17) << "minweight" << setiosflags(ios::left) << " " << setw(10) << Parameter_PruneMinimumWeight << " " << "minimum threshold weight for final pruning" << endl;
	cout << setiosflags(ios::left) << setw(17) << "smartlookup" << setiosflags(ios::left) << " " << setw(10) << Parameter_UseSmartLookup << " " << "when true, use lower_bound stl dictionary search" << endl;
	cout << setiosflags(ios::left) << setw(17) << "parsemode" << setiosflags(ios::left) << " " << setw(10) << Parameter_ParseMode << " " << "parse heuristic (0=greedy 1=lff 2=deep&slow)" << endl;
	cout << setiosflags(ios::left) << setw(17) << "recalculations" << setiosflags(ios::left) << " " << setw(10) << Parameter_PruneReCalculations << " " << "recalculate symbol costs during pruning?" << endl;
	return returnstring;
}


bool SubstringParser::SetParameter(const std::string &parametername,const std::string &parametervalue)
{
	// generic function for user-interactive modification of parameters
	// (see SetDefaultDictionaryBuildingParameters implementation for descriptions)
	// return true if we know this variable and use it
	bool bretv=false;
	if (parametername=="maxbuildsymbols")
		bretv=ParseParameter(parametervalue,Parameter_MaxSymbols_DuringBuild);
	else if (parametername=="maxsymbols")
		bretv=ParseParameter(parametervalue,Parameter_MaxSymbols_Final);
	else if (parametername=="maxSubstring")
		bretv=ParseParameter(parametervalue,Parameter_MaxSubstringSize);
	else if (parametername=="onlywords")
		bretv=ParseParameter(parametervalue,Parameter_OnlyCodeWholeWords);
	else if (parametername=="spanwords")
		bretv=ParseParameter(parametervalue,Parameter_SpanWordBoundaries);
	else if (parametername=="crends")
		bretv=ParseParameter(parametervalue,Parameter_CountCRsAsEOTs);
	else if (parametername=="minweight")
		bretv=ParseParameter(parametervalue,Parameter_PruneMinimumWeight);
	else if (parametername=="smartlookup")
		bretv=ParseParameter(parametervalue,Parameter_UseSmartLookup);
	else if (parametername=="parsemode")
		bretv=ParseParameter(parametervalue,Parameter_ParseMode);
	else if (parametername=="recalculations")
		bretv=ParseParameter(parametervalue,Parameter_PruneReCalculations);
	return bretv;
}


void SubstringParser::SetDefaultParameters()
{
	// encoding parameters that govern how dictionary is built

	// 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 #
	Parameter_MaxSymbols_DuringBuild=200000;

	// 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
	Parameter_MaxSymbols_Final=2000;

	// how many characters is largest (sub)string stored in dictionary
	Parameter_MaxSubstringSize=12;
	//	Parameter_MaxSubstringSize=3;
	//	Parameter_MaxSubstringSize=1;

	// only store characters and whole words?
	//	Parameter_OnlyCodeWholeWords=false;
	Parameter_OnlyCodeWholeWords=false;

	// store Substrings that span words (i.e. they contain multiple words)
	Parameter_SpanWordBoundaries=false;

	// minimum count for a word or Substring in order to even consider leaving it in the dictionary
	Parameter_PruneMinimumWeight=10;

	// 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.
	//Parameter_CountCRsAsEOTs=false;
	Parameter_CountCRsAsEOTs=true;

	// 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
	Parameter_UseSmartLookup=true;

	// we can either use a greedy search to find longest Substring starting with first char or we can use smarter but slower heuristics
	Parameter_ParseMode=Dictionary_ParseMode_GREEDY;

	// should we recompute symbol costs during pruning? (this actually employs the dictionary set and calculates actual usage counts and then reprunes)
	Parameter_PruneReCalculations=true;
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// PARSER PUBLIC API - PREPARATIONS FOR PARSING
	
bool SubstringParser::RewindAnyBufferedInput(bitreader &from)
{
	// let go of any buffered stream - this is an odd function that can be called be compressor if it wants to hand
	//  off the input stream to a new parser or otherwise access the input bitstream from after last symbol parsed.
	//  it is necessary because some parsers can read-ahead in input buffer, and so must rewind the bitstream.
	// we have to implement this since we do a read-ahead.  note this wouldn't be called in normal circumstances,
	//  just if compressors wants us to stop prematurely and hand off the job to someone else.
	// return true on success

	// the number of characters we have read ahead in buffer is inputbufferlen
	from.seek_bit(from.tell_bit()-(inputbufferlen*8));
	return true;
}

void SubstringParser::SynchronizeStateForNewStream()
{
	// synchronize state for a new stream
	// this MUST be called before beginning a new parsing stream
	// reset input buffer and end-of-stream sent flag
	inputbufferlen=0;
	senteos=false;
}

bool SubstringParser::CreateSymbolSetUsingStream(bitreader &from)
{
	// scan a file and add its "tokens" into our symbol set
	string valuestring;
	string slidingwindowstring;
	unsigned char c;
	bool slidingwindowfull=false;
	string eotstring=string("");
	
	// clear any existing symbols
	FreeData_Symbols();
	// create primitive characters
	AddPrimitiveCharacterSubstringSymbols();
	
	// save the current bitreader and bitreader position for reparsing during pruning
	current_bitreaderp = &from;
	start_bitreaderposition = from.tell_bit();

	// now parse the file
	while (!from.empty())
		{
		// grab a character
		c=from.get_byte();

		// add the character to our window
		slidingwindowstring+=c;

		// trim lefthand side if it is too big
		if (!slidingwindowfull)
			{
			// we keep a sliding window which is slightly bigger than the maxSubstring, to account for delimiter boundaries
			if ((int)(slidingwindowstring.length())>Parameter_MaxSubstringSize+5)
				{
				// set the flag saying from now on, we are full
				slidingwindowfull=true;
				}
			}
		if (slidingwindowfull)
			{
			// trim leftmost character
			slidingwindowstring.erase(0,1);
			}

		// now add the appropriate Substrings of slidingwindowstring to our dictionary SymbolSet
		AddSubstringsFromSlidingWindowString(slidingwindowstring);

		// 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
		if (c==13 && Parameter_CountCRsAsEOTs)
			{
			// increment frequency for EOS
			UpdateValueStringInSymbolSet(eotstring,1);
			}

		if (symbolset.size()>Parameter_MaxSymbols_DuringBuild)
			{
			// periodically we may have to prune away lowest frequency symbols in order to keep dictionary manageable
				// how many should we remove - we don't want to remove just one since that would result in many repetitive calls here
			//  so we just pick some fraction to remove
			PruneSymbolSet_ReduceSizeTo(((unsigned int)(symbolset.size())/5)+1);
			}
		}

	// now final pruning
	PruneSymbolSet();

	// and now build the vector for fast random access
	BuildSymbolVector();
	
	// return success
	return true;
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// Parser API

bool SubstringParser::ParseNextSymbolFromInput(bitreader &from, int &symbolnum)
{
	// grab an input stream symbol and set its INDEX (in symbol vector) for symbolnum
	// return false after EOS
	unsigned char c;
	int maxSubstringlen=Parameter_MaxSubstringSize;
	SubstringSymbol *symbolp;
	// note that inputbufferlen are preserved across calls, and inputbufferstr[] is preserved state info

	// try to fill up the inputqueue to Parameter_MaxSubstringSize size, or as much as we got
	current_bitreaderp=&from;
	while (inputbufferlen<maxSubstringlen && !from.empty())
		{
		// add the character
		c=from.get_byte();
		inputbufferstr[inputbufferlen]=c;
		// increment character positions
		++inputbufferlen;
		}
	
	if (inputbufferlen==0)
		{
		// no more symbols left - BUT the question now is, do we return an EOS symbol, or false for no symbols left
		if (senteos)
			{
			// we already sent an EOS so from now on any requests for a symbol returns false saying no more symbols available
			return false;
			}
		else
			{
			// we are going to drop down to return the EOS signal, but we set flag so we don't do it again
			senteos=true;
			}
		}

	// ok now we have a block of up to Parameter_MaxSubstringSize bytes from the left of the inputstr
	// now find the longest leftmost (prefix) Substring in our dictionary and encode it, and shift inputqueuestr to the left with remaining bytes
	//  and return the new inputqueuestr with remaining bytes, and return length of remaining bytes.
	symbolp=FindNextSymbolToEncode(inputbufferstr,inputbufferlen);
//	symbolp=FindNextSubstringSymbolpFromInputQueueStr(inputbufferstr,inputbufferlen);

	symbolnum=symbolp->get_symbolvectorpos();
	inputbufferlen=SwallowSymbolFromInputQueueStr(symbolp,inputbufferstr,inputbufferlen,false);
	return true;
}


bool SubstringParser::WriteSymbolText(bitwriter &to, int symbolnum,bool &isendofstreamsymbol)
{
	// write the symbol indexed by symbolnum
	// sets isendofostreamsymbol to true or false depending on if the symbol written is the EOS symbol
	// return true on success

	SubstringSymbol *symbolp=symbolvector[symbolnum];
	int valuelength=(int)((symbolp->get_valuep())->length());
	to.write((symbolp->get_valuep())->c_str(),valuelength);

	// set EOS flag
	isendofstreamsymbol=(symbolnum==endofstreamsymbolnum);

	// return success
	return true;
}
//---------------------------------------------------------------------------














//---------------------------------------------------------------------------
// Internal functions for freeing data structure

void SubstringParser::FreeData()
{
	// free symbolset - this will key any SubstringSymbol nodes
	FreeData_Symbols();
}

void SubstringParser::FreeData_Symbols()
{
	// free set,vector and symbols
	
	// we only want to free the symbols once, even if they are in both set and vector
	for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
		{
		// delete the pointed to node
		delete (*symbolset_pos);
		}

	// clear main symbolset
	symbolset.clear();

	// and now rebuild the vector, which will clear it
	BuildSymbolVector();
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// Internal Helper functions for saving and loading state

bool SubstringParser::SaveParameters(bitwriter &to)
{
	// write parameter settings
	to.put(Parameter_MaxSymbols_DuringBuild);
	to.put(Parameter_MaxSymbols_Final);
	to.put(Parameter_MaxSubstringSize);
	to.put(Parameter_OnlyCodeWholeWords);
	to.put(Parameter_SpanWordBoundaries);
	to.put(Parameter_PruneMinimumWeight);
	to.put(Parameter_CountCRsAsEOTs);
	to.put(Parameter_UseSmartLookup);
	to.put(Parameter_ParseMode);
	to.put(Parameter_PruneReCalculations);
	return true;
}


bool SubstringParser::LoadParameters(bitreader &from)
{
	// read parameter settings
	from.get(Parameter_MaxSymbols_DuringBuild);
	from.get(Parameter_MaxSymbols_Final);
	from.get(Parameter_MaxSubstringSize);
	from.get(Parameter_OnlyCodeWholeWords);
	from.get(Parameter_SpanWordBoundaries);
	from.get(Parameter_PruneMinimumWeight);
	from.get(Parameter_CountCRsAsEOTs);
	from.get(Parameter_UseSmartLookup);
	from.get(Parameter_ParseMode);
	from.get(Parameter_PruneReCalculations);
	return true;
}


bool SubstringParser::SaveSymbols(bitwriter &to)
{
	// write the symboldset to file
	// return true on success
	unsigned char valuelength;

	// write entries in compact binary form
	for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
		WriteSubstringSymbol((*symbolset_pos),to);

	// write an end-of-header in case we want to add this header as prefix of another file
	// we use a string-length==255 to mean end of table (no strings ever allowed greater than 254 characters)
	valuelength=255;
	to.put(valuelength);

	// return success
	return true;
}


bool SubstringParser::LoadSymbols(bitreader &from)
{
	// load a previously saved dictionary from file
	bool bretv=true;
	bool bretv2;

	// read dictionary
	while (!from.empty())
		{
		// read length of the string, as an unsigned car
		bretv2=ReadSubstringSymbol(from);
		if (!bretv2)
			break;
		}

	// and now build the vector for fast random access
	BuildSymbolVector();

	// return true on success
	return bretv;
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// Internal Parsing
bool SubstringParser::WriteSubstringSymbol(SubstringSymbol *SubstringSymbolp,bitwriter &to)
{
	// SubstringSymbol reader/writer - derived classes will take these over if necessary
	// return true on success
	TSubStrParserWeight weightvalue;
	unsigned int weightvalue_uint;
	unsigned char valuelength;

	// write length of the string, as an unsigned int
	valuelength=(int)(((*symbolset_pos)->get_valuep())->length());
	to.put(valuelength);
	// write string
	to.write(((*symbolset_pos)->get_valuep())->c_str(),valuelength);
	// get weight of symbol
	weightvalue=(*symbolset_pos)->get_weight();
	// SubstringSymbols should be writable as unsigned ints, but we dynamic cast in case, which will throw an exception if not
	weightvalue_uint=static_cast<unsigned int>(weightvalue);
	to.put(weightvalue_uint);

	// return success
	return true;
}

bool SubstringParser::ReadSubstringSymbol(bitreader &from)
{
	// virtual SubstringSymbol reader/writer - derived classes will take these over if necessary
	// return false when we hit end
	unsigned int weightvalue_uint;
	unsigned char valuelength;
	char valuestr[256];
	std::string valuestring;
	
	from.get(valuelength);
	if (valuelength>=255)
		{
		// all done
		return false;
		}
	// read string
	from.read(valuestr,valuelength);
	valuestring=string(valuestr,valuelength);
	// read weight
	from.get(weightvalue_uint);
	// now add the symbol SubstringSymbol
	AddSymbol(valuestring,(TSubStrParserWeight)weightvalue_uint);
	return true;
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// Internal symbol construction

void SubstringParser::AddPrimitiveCharacterSubstringSymbols()
	{
	// Push every possible character as SubstringSymbol into the set
	string valuestring;
	char valuestr[20];

	for ( int i = 0 ; i < 256 ; i++ )
		{
		// form the string value of this (just the dictionary character or word)
		valuestr[0]=i;valuestr[1]='\0';
		valuestring=string(valuestr,1);
		// create a new SubstringSymbol node with this character, with a count of 1 (if you try to add a weight of 0 you will mess up the tree since sums must be strictly increasing)
		UpdateValueStringInSymbolSet(valuestring,1);
		}

	// we are going to use the empty string "" as our EOS (or End of Encoding) symbol, and record its number
	valuestring="";
	UpdateValueStringInSymbolSet(valuestring,1);
	}


bool SubstringParser::UpdateValueStringInSymbolSet(const string &stringvalue,int increment)
{
	// add a symbol as a SubstringSymbol with 0 count
	// return false on a FAILURE to add the symbol (ran out of memory)
	bool bretv=true;

	// use a static local variable to reduce memory allocation-deallocation thrashing, and use it for searching
	static SubstringSymbol searchSubstringSymbol("",1);
	// now we use this searchSubstringSymbol for searching
	searchSubstringSymbol.set_value(stringvalue);

	// look it up
	symbolset_pos=symbolset.find(&searchSubstringSymbol);
	// if its not found, create it
	if (symbolset_pos==symbolset.end())
		{
		// create the SubstringSymbol and add it, with weight = increment
		AddSymbol(stringvalue,increment);
		}
	else
		{
		// we found it, so increment its count
		(*symbolset_pos)->increment_weight(increment);
		}

	// return false on failure
	return bretv;
}

void SubstringParser::ResetWeights()
{
	// reset weights for every symbol
	for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
		(*symbolset_pos)->set_weight(0);
}
//---------------------------------------------------------------------------



//---------------------------------------------------------------------------
// Internal symbol construction

void SubstringParser::AddSubstringsFromSlidingWindowString(string &slidingwindowstring)
{
	// According to our parameters, increment frequency counts (adding symbols when needed) of some Substrings from our sliding window
	// The way we do this is, our primary character is the rightmost one; thats the one that will be different on each call.
	// If we want to do standard huffman on characters, we would simply update the frequency of the rightmost character.
	// Alternatively, we have various other parameters which can govern which Substrings we track.
	// Some of many settings can generate HUGE trees and sets, but these trees will eventually be pruned of least-useful entries.
	// Note this procedure is the most convoluted one in the file, because it deals with various parameters
	//  which regulate what kinds of Substrings from the input stream get tokenized.

	string valuestring;
	bool bretv;
	int len=(int)(slidingwindowstring.length());
	unsigned char c,c2;
	int leftpos,rightpos,curpos;
	bool delimiteronborder;

	// first add the rightmost character, by incrementing its usage count by 1
	valuestring=slidingwindowstring.substr(len-1,1);
	bretv=UpdateValueStringInSymbolSet(valuestring,1);

	// if the string length is only one character, then we are done.
	if (len==1)
		return;

	// reset flag which helps us prevent from adding a keyword which ends in a delimiter
	delimiteronborder=false;

	if (Parameter_OnlyCodeWholeWords)
		{
		// we only want to store full words, so if we have not hit a new word boundary, then return
		c=slidingwindowstring[len-1];
		c2=slidingwindowstring[len-2];
		if (len<3)
			{
			// too small to be on a word boundary
			return;
			}
		if (!IsNonWordCharacter(c) && !IsNonWordCharacter(c2))
			{
			// we are within a word
			return;
			}
		if (IsNonWordCharacter(c) && IsNonWordCharacter(c2))
			{
			// we are within a word
			return;
			}
		// start end pointer at last non-delimiter
		rightpos=len-2;
		}
	else
		{
		// start end position at last character
		rightpos=len-1;
		}

	// set flag to tell us whether the new character is a delimiter and shouldn't be coded on the end of a real word
	if (IsNonWordCharacter(slidingwindowstring[rightpos]))
		{
		// other than adding delimiters as their own characters (done above), we don't want to code them as part of a word
		// so we set a flag here saying that we are only going to move leftward to catch a sequence of delimiters as a Substring, and NOT
		// allows a Substring which has delimiters on the *borders* of words
		delimiteronborder=true;
		}
	else
		delimiteronborder=false;

	// set left pos
	leftpos=rightpos-Parameter_MaxSubstringSize;
	if (leftpos<0)
		leftpos=0;

	// start walking backwards from right to left and add Substrings to dictionary
	//  always encoding from curpos to end (rightpos)
	for (curpos=rightpos-1;curpos>leftpos;--curpos)
		{
		c=slidingwindowstring[curpos];
		if (delimiteronborder && IsNonWordCharacter(c))
			{
			if (Parameter_OnlyCodeWholeWords && curpos>leftpos)
				{
				// since we only code words, we don't want to code this Substring of delimiters yet
				continue;
				}
			// because we are parsing a string of delimiters, we want to just drop through to write out this Substring
			}
		else if (IsNonWordCharacter(c) || delimiteronborder)
			{
			if (IsNonWordCharacter(c) && IsNonWordCharacter(slidingwindowstring[curpos+1]))
				{
				// we have hit a series of delimiters to the left of a word, so we've already encoded the non-delimiter-bordered stuff to our right
				// so we don't want to encode it again.
				continue;
				}
			if (Parameter_OnlyCodeWholeWords || delimiteronborder)
				{
				// we found a new word (or sequence of words), so encode it
				valuestring=slidingwindowstring.substr(curpos+1,rightpos-curpos);
				//cout << "type 1 word: "<<valuestring<< endl;
				bretv=UpdateValueStringInSymbolSet(valuestring,1);
				if (delimiteronborder)
					{
					// we just finished writing out a string of delimiters bordered on left by non-delimiter, so we stop now
					break;
					}
				else if (!Parameter_SpanWordBoundaries)
					{
					// since we don't span word boundaries, we are done
					break;
					}
				else
					{
					// let it continue to look for next whole word
					continue;
					}
				}
			else if (!Parameter_SpanWordBoundaries)
				{
				// we hit a word boundary, so we are done
				break;
				}
			else if (IsNonWordCharacter(c) && !delimiteronborder)
				{
				// we don't want to let any word Substring start with a delimiter (or end with one, which is checked above)
				// actually i think by the time we drop down to here this is always true
				continue;
				}
			}
		else if (delimiteronborder)
			{
			// our rightmost character was a delimiter so we wont consider any non-delimiters words to the left of it
			break;
			}
		else if (Parameter_OnlyCodeWholeWords)
			{
			// we are in the middle of a word, so we do nothing
			continue;
			}

		// update the Substring
		valuestring=slidingwindowstring.substr(curpos,(rightpos-curpos)+1);
		bretv=UpdateValueStringInSymbolSet(valuestring,1);
		}
}
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// Internal Parsing

int SubstringParser::SwallowSymbolFromInputQueueStr(SubstringSymbol *symbolp,char *inputqueuestr,int inputqueuestrlen,bool debugmode)
{
	// find which symbol to encode
	if (symbolp==NULL)
		{
		// no match found
		return -1;
		}

	// debugmode shows the sub-string used for encoding
	if (debugmode)
		cout << symbolp->get_value() << "*";

	// shift inputqueuestrlen
	int writepos=0;
	for (int pos=(int)((symbolp->get_valuep())->length());pos<inputqueuestrlen;++pos)
		{
		inputqueuestr[writepos]=inputqueuestr[pos];
		++writepos;
		}
	inputqueuestrlen=writepos;

	// return length of shifted inputqueuestr
	return inputqueuestrlen;
}


SubstringSymbol* SubstringParser::FindNextSymbolToEncode(char *inputqueuestr,int inputqueuestrlen)
{
	// ok now we have a block of up to Parameter_MaxSubstringSize bytes from the left of the inputstr
	// now find the longest leftmost (prefix) Substring in our dictionary and encode it, and shift inputqueuestr to the left with remaining bytes.
	// return the new inputqueuestr with remaining bytes, and return length of remaining bytes.
	SubstringSymbol *symbolnodep = 0;

	if (Parameter_ParseMode==Dictionary_ParseMode_GREEDY || inputqueuestrlen<=2)
		{
		// GREEDY PARSE
		// find biggest matching prefix in symbol dictionary - this should never fail unless the dictionary is not built at all,
		//  since the dictionary is supposed to contain every character, so at least the leftmost character should match
		symbolnodep = FindNextSymbolToEncode_Greedy(inputqueuestr,inputqueuestrlen);
		}
	else if (Parameter_ParseMode==Dictionary_ParseMode_LFF)
		{
		// SMARTER HEURISTIC PARSE (slower than greedy, but *maybe* better)
		int bestindex=inputqueuestrlen;
		int bestscore=-1;
		for (int index=0;index<=inputqueuestrlen-1;++index)
			{
			// find length of the string beginning at index
			// early stop if we know we cant do better
			if (bestscore>=inputqueuestrlen-index)
				break;
			symbolnodep = FindNextSymbolToEncode_Greedy(&inputqueuestr[index],inputqueuestrlen-index);
			if (symbolnodep==NULL)
				break;
			if (bestscore==-1 || symbolnodep->get_valuelen()>bestscore)
				{
				bestscore=symbolnodep->get_valuelen();
				bestindex=index;
				}
			}
		// now that we found the longest Substring, parse the string BEFORE it
		if (bestindex==0)
			bestindex=inputqueuestrlen;
		symbolnodep = FindNextSymbolToEncode_Greedy(inputqueuestr,bestindex);
		}
	else if (Parameter_ParseMode==Dictionary_ParseMode_DEEP)
		{
		// SMARTER HEURISTIC PARSE (slower than greedy, but *maybe* better)
		double encodecost;
		double bestscore;
		int longestlen=inputqueuestrlen;
		int bestindex=longestlen;
		bool firstscore=true;
		do
			{
			bestscore=-1;
			longestlen=bestindex;
			for (int index=1;index<=longestlen;++index)
				{
				// find cost if we encode based on split at index
				encodecost=CalculateEncodeCost(inputqueuestr,index);
   				if (index<longestlen)
	      			encodecost+=CalculateEncodeCost(&inputqueuestr[index],longestlen-index);
				// update our tracking of best score
				if (firstscore || encodecost<=bestscore)
					{
					bestscore=encodecost;
					bestindex=index;
					firstscore=false;
					}
				}
			} while (bestindex!=longestlen);
		// and do the search with this limit (note we could have asked CalculateEncodeCost to return best found first match
		symbolnodep = FindNextSymbolToEncode_Greedy(inputqueuestr,bestindex);
		}
	else
		{
		// unknown parse mode
		cout << "ERROR: unknown parse mode "<<Parameter_ParseMode<<"."<<endl;
		}

	return symbolnodep;
	}


SubstringSymbol* SubstringParser::FindNextSymbolToEncode_Greedy(char *inputqueuestr,int inputqueuestrlen)
{
	// find biggest matching prefix in symbol dictionary - this should never fail unless the dictionary is not built at all,
	//  since the dictionary is supposed to contain every character, so at least the leftmost character should match
	// return a pointer to the symbol, or NULL if there is some error and we cant find one.

	// there are several ways to do this dictionary search within the SymbolSet, which is a binary tree
	// one way is to start with full string and gradually shorten it until we get an exact match
	// another is to ask the stl set to find the nearest match, and search back from there for shortest exact match
	int originputqueuestrlen=inputqueuestrlen;
	string inputstring;

	// use a static local variable to reduce memory allocation-deallocation thrashing
	static SubstringSymbol searchSubstringSymbol("",1);

	// convert char * to string, using exactly inputqueuestrlen, regardless of any '\0'
	if (inputqueuestrlen==0)
		inputstring="";
	else
		inputstring=string(inputqueuestr,inputqueuestrlen);

	// truncate it to max length of any symbol, incase caller sometimes passes more
	if (inputqueuestrlen>Parameter_MaxSubstringSize)
		{
		inputqueuestrlen=Parameter_MaxSubstringSize;
		inputstring=inputstring.substr(0,inputqueuestrlen);
		}

	// now we use this searchSubstringSymbol for searching
	searchSubstringSymbol.set_value(inputstring);

	// find the longest Substring, using a smarter use of stl lower_bound instead of find()
	if (Parameter_UseSmartLookup)
		{
		// smarter method (22:00 seconds on a test, about 3x faster than slow method below
		//  ATTN: can we simplify this?
		int len;
		int index;
		string teststring;
		for (;;)
			{
			symbolset_pos=symbolset.lower_bound(&searchSubstringSymbol);
			//teststring=(*symbolset_pos)->get_value();
			//len=(int)(teststring.length());
			//cout << "lowerbound for '"<<inputstring<<"' = '" << teststring <<"' (len="<<len<<")."<<endl;;
			// check for error
			if (symbolset_pos==symbolset.end())
				{
				cout << "ERROR: unexpectedly didn't find any match for a string that started out "<<originputqueuestrlen<<" characters (we hit "<<inputqueuestrlen<<").  last char was "<<(int)inputqueuestr[0]<<"."<<endl;
				return NULL;
				}

			// if we have an exact match we are done
			teststring=(*symbolset_pos)->get_value();
			len=(int)(teststring.length());
			if (teststring==inputstring)
				break;

			// try one previous
			--symbolset_pos;
			teststring=(*symbolset_pos)->get_value();
			len=(int)(teststring.length());
			if (len<inputqueuestrlen)
				{
				// shorten main string to match
				inputqueuestrlen=len;
				inputstring=inputstring.substr(0,inputqueuestrlen);
				}
			// if we have an exact match we are done
			if (teststring==inputstring)
				break;

			// if not, find the last character they agree on and find next bound
			len=(int)(teststring.length());
			for (index=0;index<len;++index)
				{
				if (teststring[index]!=inputstring[index])
					break;
				}
			// now shorten it and try again
		    inputqueuestrlen=index;
		    if (inputqueuestrlen==0)
				{
				cout << "ERROR: unexpectedly truncated search string that started out "<<originputqueuestrlen<<" characters (we hit "<<inputqueuestrlen<<").  last char was "<<(int)inputqueuestr[0]<<"."<<endl;
		    	inputstring="";
		    	}
			else
				inputstring=inputstring.substr(0,inputqueuestrlen);
			searchSubstringSymbol.set_value(inputstring);
			}
		}
	else
		{
		// dumb method (67:00 seconds on a test, about 3x slower than smart method)
		for(;;)
			{
			symbolset_pos=symbolset.find(&searchSubstringSymbol);
			if (symbolset_pos!=symbolset.end())
				{
				// we found an exact match
				break;
				}
			// not found, so shorten string by removing rightmost character
			--inputqueuestrlen;
			if (inputqueuestrlen<=0)
				{
				cout << "ERROR: unexpectedly didn't find any match for a string that started out with "<<originputqueuestrlen<<" characters (we hit "<<inputqueuestrlen<<").  last char was "<<(int)inputqueuestr[0]<<"."<<endl;
				return NULL;
				}
			// decrease length of Substring currently being searched for and continue
			inputstring=inputstring.substr(0,inputqueuestrlen);
			searchSubstringSymbol.set_value(inputstring);
			}
		}

	// return the pointer
	return *symbolset_pos;
}


double SubstringParser::CalculateEncodeCost(char *inputqueuestr,int inputqueuestrlen)
{
	// try to find the optimal cost of encoding the string, using currently selected methods
	//  and return its cost, ASSUMING that we start by parsing longest matching leftmost substr
	SubstringSymbol* symbolnodep;
	double cost=0;

	// start by greedy parse of biggest leftmost substr
	symbolnodep = FindNextSymbolToEncode_Greedy(inputqueuestr,inputqueuestrlen);
	if (symbolnodep==NULL)
		{
		// no match found - this should never happen
		cout << "$no match found."<<endl;
		return 99999;
		}

	// add cost of initial Substring
	cost+=GetSymbolCost(symbolnodep);

	// advance pointer
	inputqueuestr+=symbolnodep->get_valuelen();
	inputqueuestrlen-=symbolnodep->get_valuelen();

	// now the remainder of the string could be done smart or greedy
	if (Parameter_ParseMode!=Dictionary_ParseMode_GREEDY && inputqueuestrlen>2)
		{
		// SMARTER HEURISTIC PARSE (slower than greedy, but *maybe* better)
		int bestindex=inputqueuestrlen;
		double bestscore=0;
		double encodecost;
		bool firstscore=true;
		for (int index=1;index<=inputqueuestrlen;++index)
			{
			// find cost if we encode based on split at index
			encodecost=CalculateEncodeCost(inputqueuestr,index);
   			if (index<inputqueuestrlen)
      			encodecost+=CalculateEncodeCost(&inputqueuestr[index],inputqueuestrlen-index);
			// update our tracking of best score
			if (firstscore || encodecost<bestscore)
				{
				bestscore=encodecost;
				bestindex=index;
				firstscore=false;
				}
			}
		// now set cost to best cost found
		cost+=bestscore;
		}
	else if (inputqueuestrlen>0)
		{
		// GREEDY PARSE cost
		cost+=CalculateEncodeCost(inputqueuestr,inputqueuestrlen);
		}
	else
		{
		// nothing left to score
		}

	// now return cost
	return cost;
}
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// Internal Pruning functions

void SubstringParser::PruneSymbolSet_WeightThreshold(TSubStrParserWeight thresholdweight)
{
	// remove all weights below some threshold set by parameter
	// this is a fast and easy step that will remove almost the entire current symbol set :)
	TSymbolSetTYPE::iterator nextsymbolpos;
	TSubStrParserWeight weight;
	int index=0;

	// First simplest pruning operation - simply remove all symbols which don't have some threshold count
	for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();)
		{
		++index;
		nextsymbolpos=symbolset_pos;
		++nextsymbolpos;
		// only show non-zero weights (i.e. symbols used at least once)
		if (!((*symbolset_pos)->dontprune()))
			{
			weight=(*symbolset_pos)->get_weight();
			if (weight<thresholdweight)
				{
				// delete this symbol
				delete (*symbolset_pos);
				symbolset.erase(symbolset_pos);
				}
			}
		// advance pointer
		symbolset_pos=nextsymbolpos;
		}
}


void SubstringParser::PruneSymbolSet_RemoveRedundantPrefixes()
{
	// some Substring symbols are simply prefixes of others, with no independent occurrences
	//  for example the Substring "supercomput" is a redundant Substring of "supercomputer"
	//  so we can remove those with no cost.
	TSymbolSetTYPE::iterator nextsymbolpos;
	TSymbolSetTYPE::iterator lastsymbolpos;
	TSubStrParserWeight weight,lastweight;
	string lastvalue;
	int lastvaluelen;

	lastweight=0;
	for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();)
		{
		nextsymbolpos=symbolset_pos;
		++nextsymbolpos;
		// some symbols (like primitive characters, cannot be pruned)
		if ((*symbolset_pos)->dontprune())
			lastweight=0;
		else
			{
			weight=(*symbolset_pos)->get_weight();
			if (weight==lastweight && weight!=0)
				{
				// got a candidate for pruning, IFF our prior string is a proper prefix of us
				lastvaluelen=(int)(lastvalue.length());
				if (((*symbolset_pos)->get_value()).compare(0,lastvaluelen,lastvalue.c_str(),lastvaluelen)==0)
					{
					// yes it is, so kill our last value
					delete *lastsymbolpos;
					symbolset.erase(lastsymbolpos);
					}
				}
			// remember last symbol details
			lastweight=weight;
			lastvalue=(*symbolset_pos)->get_value();
			lastsymbolpos=symbolset_pos;
			}
		// advance pointer
		symbolset_pos=nextsymbolpos;
		}
}


void SubstringParser::PruneSymbolSet_ReduceSizeTo(unsigned int targetsize)
{
	// we have exceeded our maximum # of symbols allowed during build process, so reduce the size
	//  this is done quite inefficiently, but we can worry about that later, or not, since its not in a time-critical place
	// ATTN: a smarter way would be to sort by weight and pop off smallest weights.
	if (symbolset.size()<targetsize)
		return;

	for (int count=2;count<10000;++count)
		{
		// remove all removable symbols with a weight < count and then check set size again
		PruneSymbolSet_WeightThreshold((TSubStrParserWeight)count);
		if (symbolset.size()<=targetsize)
			break;
		}
}


void SubstringParser::PruneSymbolSet()
{
	// we need to reduce the size of the dictionary SymbolSet by pruning symbols we think are not worth the coding space
	//  having silly symbols increases our cost in two main ways:
	//   1) cost in memory needed to store the dictionary in memory and time needed to search dictionary
	//   2) cost incurred due to the fact that the more words in dictionary, the more bits needed to encode other symbols.
	//      this is a very serious issue and suggests the dictionary should be as small as possible.
	// the bitreader is passed so that we can reparse the input in order to test our created symbol set.

	// display info
	cout << endl << "Total symbols in dictionary before pruning: " << GetSetSymbolCount() << endl;

	// remove weights below a threshold
	PruneSymbolSet_WeightThreshold(Parameter_PruneMinimumWeight);
	cout << "After Stage 1 Pruning (removed scores below "<<Parameter_PruneMinimumWeight<<"), symbols: " << GetSetSymbolCount() << endl;

	// remove redundant prefixes
	PruneSymbolSet_RemoveRedundantPrefixes();
	cout << "After Stage 2 Pruning (removed redundant prefixes), symbols: " << GetSetSymbolCount() << endl;

	// pre-capping recompression
	if (Parameter_PruneReCalculations)
		{
		// now actually re-compress the file using current symbol set to get better real-world weight counts, and repeat prunings
		ReParseFileReComputeCosts(true);
		PruneSymbolSet_WeightThreshold(Parameter_PruneMinimumWeight);
		PruneSymbolSet_RemoveRedundantPrefixes();
		// some info for user
		cout << "After pre-ceil pre-compression, re-evaluation, and repruning, symbols: " << GetSetSymbolCount() << endl;
		}

	// finally, cap symbol count.  there are smart and dumb ways this can be done
	PruneSymbolSet_ReduceSizeTo(Parameter_MaxSymbols_Final);
	cout << "After Stage 3 Pruning (killed worst scores to reach target), symbols: " << GetSetSymbolCount() << endl;

	// more recompression loops after capping
	if (Parameter_PruneReCalculations)
		{
		// now actually re-compress the file using current symbol set to get better real-world weight counts, and repeat prunings
		ReParseFileReComputeCosts(true);
		PruneSymbolSet_WeightThreshold(Parameter_PruneMinimumWeight);
		PruneSymbolSet_RemoveRedundantPrefixes();
		cout << "After re-compression, re-evaluation, and repruning, symbols: " << GetSetSymbolCount() << endl;
		}
}
//---------------------------------------------------------------------------




//---------------------------------------------------------------------------
// For reparsing and recomputing scores

double SubstringParser::ReParseFileReComputeCosts(bool updateweights)
{
	// USING the current symbolset we have just created, reparse it and recalculate the 'cost'
	//  and frequency of each symbol.
	// This is useful because as we create and modify(prune) the symbolset, the symbols interact
	//  and effect frequencies, so its helpful to reparse the input and recalculate frequencies.
	// return sum cost of parsed symbols IFF updateweights == false

	// First we need to rebuild the symbol vector before we can parse
	BuildSymbolVector();

	int symbolnum;
	SubstringSymbol *symbolp;
	double totalcost=0;

	// reset input bitreader to where we started dictionarizing
	current_bitreaderp->seek_bit(start_bitreaderposition);

	// reset weights if we are recalculating them
	if (updateweights)
		ResetWeights();

	// loop through input grabbing symbols
	// ATTN: are we properly updating weights?
	while (ParseNextSymbolFromInput(*current_bitreaderp,symbolnum))
		{
		symbolp=symbolvector[symbolnum];
		if (updateweights)
			{
			// we can be run in a mode to actually update weights while encoding
			if (updateweights)
				{
				// note this will not change priority queue, and is therefore somewhat skidding on what is 'allowed' by stl
				//  but we use this purposefully so that we are modifying the weights while preserving current priority queue.
				symbolp->increment_weight(1);
				// we need to also keep track of CRs for EOS's if appropriate
				if (Parameter_CountCRsAsEOTs && strchr(symbolp->get_valuep()->c_str(),13)!=NULL)
					{
					symbolp=FindNextSymbolToEncode_Greedy("",0);
					if (symbolp!=NULL)
						symbolp->increment_weight(1);
					}
				}
			}
		else
			totalcost+=symbolp->get_cost();
		}

	// return success
	return totalcost;
}
//---------------------------------------------------------------------------


//---------------------------------------------------------------------------
// Internal symbol construction

void SubstringParser::BuildSymbolVector()
{
	// build a vector of symbol pointers, for efficient random access
	// clear any existing vector
	symbolvector.clear();
	// add symbols from set
	int index=0;
	for (symbolset_pos=symbolset.begin();symbolset_pos!=symbolset.end();++symbolset_pos)
		{
		// add symbol to vector
		symbolvector.push_back(*symbolset_pos);
		// tell symbol what number it is
		(*symbolset_pos)->set_symbolvectorpos(index++);
		}
	// now we need to update our count of how many symbols we have
	symbolcount=(int)(symbolvector.size());
	// and record the symbol representing the end-of-stream (EOS is "")
	endofstreamsymbolnum=LookupSymbolNumberFromText(string(""));
}


int SubstringParser::LookupSymbolNumberFromText(string wordstring)
{
	// return the number of a symbol in the parsing symbolset (or -1 if not found)
	static SubstringSymbol searchSubstringSymbol("",1);
	// now we use this searchSubstringSymbol for searching
	searchSubstringSymbol.set_value(wordstring);
	symbolset_pos=symbolset.find(&searchSubstringSymbol);
	// if its not found, return -1
	if (symbolset_pos==symbolset.end())
		return -1;
	// otherwise return its index symbol number
	return ((*symbolset_pos)->get_symbolvectorpos());
}
//---------------------------------------------------------------------------
