/*
								+---------------------------------+
								|                                 |
								|   ***   Huffman coder 2   ***   |
								|                                 |
								|  Copyright  © -tHE SWINe- 2006  |
								|                                 |
								|            Huffman.h            |
								|                                 |
								+---------------------------------+
*/

#pragma once
#ifndef __HUFFMAN_CODER_2_INCLUDED
#define __HUFFMAN_CODER_2_INCLUDED

/**
 *	@file Huffman.h
 *	@date 2006
 *	@author -tHE SWINe-
 *	@brief simple Huffman coder
 *
 *	@date 2006-08-23
 *
 *	passed code revision
 *
 *	added code which repairs codes, assigned by CHuffNode so they are sorted by both
 *	length and value
 *	moved CHuffNode inside CHuffmanCoder which looks odd, but it seems to be the only
 *	possible way to get the thing compiled under linux/g++
 *	also added a few dirty defines which make g++ compile it, but CHuffmanCoder is no
 *	longer template class then ... need some help with templates from some g++ guru
 *
 *	@date 2006-09-05
 *
 *	passed code revision
 *
 *	removed CHuffNode class, written smaller (and possibly faster) function that does
 *	the same job (bool CHuffmanCoder::Create_Tree()) now it should be compilable as
 *	template even under linux/g++
 *	rewritten int CHuffmanCoder::n_Code_Num() (returns number of different symbols) to
 *	int CHuffmanCoder::n_Code_Num(int n_code_length = -1) (returns number of different
 *	symbols if n_code_length == -1 or number of different symbols with codes with
 *	length n_code_length)
 *	renamed to "Huffman coder 2" (but filename remains "Huffman.h")
 *
 *	@date 2009-05-23
 *
 *	removed all instances of std::vector::reserve and replaced them by stl_ut::Reserve_*
 *
 *	@date 2012-06-19
 *
 *	Moved multiple inclusion guard before file documentation comment.
 *
 */

#if defined(_MSC_VER) && !defined(__MWERKS__)
#pragma warning(disable:4786)
#endif
// disable warning C4786 "identifier was truncated to '255' characters in the debug information"

#include "NewFix.h"

#include <vector>
#include "StlUtils.h"

#if defined(_MSC_VER) && !defined(__MWERKS__) && !defined(for) && _MSC_VER <= 1200
#define for if(0) {} else for
#endif // _MSC_VER && !__MWERKS__ && !for && _MSC_VER <= 1200
// msvc 'for' scoping hack

/*
 *	template <class TSymbolType>
 *	class CSymbolCompare
 *		- simple template to fill-in code for symbol comparison
 *		- this variant is suitable for simple TSymbolType types (such as int, ...)
 */
template <class TSymbolType>
class CSymbolComparer {
public:
	inline int operator()(const TSymbolType &r_t_symbol_0, const TSymbolType &r_t_symbol_1)
	{
		if(r_t_symbol_0 > r_t_symbol_1)
			return 1;
		if(r_t_symbol_0 < r_t_symbol_1)
			return -1;
		return 0;
	}
};

/*
 *	template <class TSymbolPtrType>
 *	class CSymbolPtrCompare
 *		- simple template to fill-in code for symbol comparison
 *		- this variant is suitable for complex / big TSymbolType types
 *		  (TSymbolPtrType is pointer ro TSymbolType) in cases when it's better to
 *		  store pointers to objects of TSymbolType instead of objects themselves
 *		  
 */
template <class TSymbolPtrType>
class CSymbolPtrComparer {
public:
	inline int operator()(const TSymbolPtrType p_symbol_0, const TSymbolPtrType p_symbol_1)
	{
		if(*p_symbol_0 > *p_symbol_1)
			return 1;
		if(*p_symbol_0 < *p_symbol_1)
			return -1;
		return 0;
	}
};

/*
 *	template <const int n_max_code_bit_num = 16, class TSymbolType = unsigned char>
 *	class CHuffmanCoder
 *		- Huffman coder template class
 *		- n_max_code_bit_num is maximal length of generated codes
 *		- TSymbolType is type of processed symbols
 *		- intended use of this class is to insert all the symbols being compressed
 *		  (sorted list of distinct symbols with their frequencies is maintained)
 *		  after all symbols have been inserted, binary tree is created to determine
 *		  symbol codes. finaly, there are functions for accessing the tree (to write
 *		  huffman table) and for translating symbols (to write bit-stream)
 */
template <const int n_max_code_bit_num = 16, class TSymbolType = unsigned char,
	class _CSymbolComparer = CSymbolComparer<TSymbolType> >
class CHuffmanCoder {
protected:
	struct TFrequency {
		const TSymbolType t_symbol; // valid for leaf nodes only
		int n_frequency;

		unsigned int n_code_word;
		unsigned int n_code_length;

		int n_code_length_order; // qsort we are using is unstable so if it's necessary to
		// sort frequencies by code length, there is offen more symbols with the same code
		// length. but as code length is used as index of huffman table, any variance can't
		// be afforded, so right after huffman tree creation n_code_length_order is filled
		// so qsort would always give the same results

		TFrequency(const TSymbolType &r_t_symbol)
			:t_symbol(r_t_symbol), n_frequency(1), n_code_word(0), n_code_length((unsigned int)-1)
		{}
	};
	typename std::vector<TFrequency*> m_symbol_freq_table;
	int m_n_sort_key;
	bool m_b_symbol_codes_dirty_flag;
	typename std::vector<TFrequency*> m_p_symbol_code_table[n_max_code_bit_num];

	enum {
		sort_Symbol,
		sort_CodeLength,
		sort_CodeLength_Order,
		sort_Frequency_Desc
	};

public:
	/*
	 *	CHuffmanCoder()
	 *		- default constructor
	 */
	CHuffmanCoder()
		:m_n_sort_key(sort_Symbol), m_b_symbol_codes_dirty_flag(true)
	{
	}

	/*
	 *	~CHuffmanCoder()
	 *		- default destructor
	 */
	~CHuffmanCoder()
	{
		Reset_SymbolFrequencies();
	}

	/*
	 *	bool operator =(const CHuffmanCoder &r_huff_coder)
	 *		- operator = (copy the object)
	 *		- returns true on success or false in case there was not enough memory
	 */
	bool operator =(const CHuffmanCoder &r_huff_coder)
	{
		if(&r_huff_coder == this)
			return true;
		// handle self-assignment

		Reset_SymbolFrequencies();
		// free itself

		m_symbol_freq_table.clear();
		if(!stl_ut::Reserve_N(m_symbol_freq_table, r_huff_coder.m_symbol_freq_table.size()))
			return false;
		// alloc

		for(typename std::vector<TFrequency*>::const_iterator
		   p_freq = r_huff_coder.m_symbol_freq_table.begin();
		   p_freq < r_huff_coder.m_symbol_freq_table.end(); p_freq ++) {
			TFrequency *p_freq_struct;
			if(!(p_freq_struct = new(std::nothrow) TFrequency((*p_freq)->t_symbol))) {
				for(typename std::vector<TFrequency*>::iterator p_freq2 = m_symbol_freq_table.begin();
				   p_freq2 < m_symbol_freq_table.end(); p_freq2 ++)
					delete *p_freq2;
				return false;
			}
			p_freq_struct->n_frequency = (*p_freq)->n_frequency;
			p_freq_struct->n_code_word = (*p_freq)->n_code_word;
			p_freq_struct->n_code_length = (*p_freq)->n_code_length;
			p_freq_struct->n_code_length_order = (*p_freq)->n_code_length_order;
			m_symbol_freq_table.push_back(p_freq_struct);
		}

		m_n_sort_key = r_huff_coder.m_n_sort_key;
		m_b_symbol_codes_dirty_flag = r_huff_coder.m_b_symbol_codes_dirty_flag;

		if(!m_b_symbol_codes_dirty_flag) {
			for(int i = 0; i < n_max_code_bit_num; i ++)
				m_p_symbol_code_table[i].clear();
			// clean tiny lists

			for(typename std::vector<TFrequency*>::iterator p_freq = m_symbol_freq_table.begin();
			   p_freq < m_symbol_freq_table.end(); p_freq ++) {
				int n_index = (*p_freq)->n_code_length - 1;
				if(!stl_ut::Reserve_1More(m_p_symbol_code_table[n_index]))
					return false;
				m_p_symbol_code_table[n_index].push_back(*p_freq);
			}
			// fill tiny lists
		}

		return true;
	}

	inline int n_Max_Code_Bit_Num() const
	{
		return n_max_code_bit_num;
	}

	/*
	 *	void Reset_SymbolFrequencies()
	 *		- clear symbol frequency table (ie. undefine symbols as well)
	 */
	void Reset_SymbolFrequencies()
	{
		for(typename std::vector<TFrequency*>::iterator p_freq = m_symbol_freq_table.begin();
		   p_freq < m_symbol_freq_table.end(); p_freq ++)
			delete *p_freq;
		m_symbol_freq_table.clear();
		m_b_symbol_codes_dirty_flag = true;
	}

	/*
	 *	bool Set_SymbolFrequencies(const TSymbolType *p_symbol, const int *p_symbol_frequency,
	 *		int n_symbol_num)
	 *		- directly set symbol frequencies. in case specified symbols are present in current
	 *		  symbol frequency table, their frequencies are adjusted, otherwise new frequency table
	 *		  entries are created, with proper frequencies set
	 *		- return true on success, false in case of memory problems
	 */
	bool Set_SymbolFrequencies(const TSymbolType *p_symbol, const int *p_symbol_frequency,
		int n_symbol_num)
	{
		if(n_symbol_num)
			m_b_symbol_codes_dirty_flag = true;

		for(const TSymbolType *p_end = p_symbol + n_symbol_num; p_symbol < p_end; p_symbol ++) {
			bool b_found_equal;
			TFrequency t_tmp_node(*p_symbol);
			typename std::vector<TFrequency*>::iterator p_freq = p_FindEqualNext(&t_tmp_node,
				b_found_equal, sort_Symbol);

			if(b_found_equal)
				(*p_freq)->n_frequency = *p_symbol_frequency; // it was found, just set frequency
			else {
				if(!stl_ut::Reserve_1More(m_symbol_freq_table))
					return false;
				TFrequency *p_symbol_freq;
				if(!(p_symbol_freq = new(std::nothrow) TFrequency(*p_symbol)))
					return false;
				p_symbol_freq->n_frequency = *p_symbol_frequency; // set frequency
				m_symbol_freq_table.insert(p_freq, p_symbol_freq);
				// it wasn't found, create new node and insert it on such a position
				// so the symbol frequency table remains sorted
			}
		}
		// insert all distinct symbols in the symbol frequency table, count symbol frequencies,
		// keeping the symbol frequency table sorted by symbol value

		return true;
	}

	/*
	 *	bool Insert_Symbols(const TSymbolType *p_symbol, int n_symbol_num)
	 *		- insert specified symbols into the symbol frequency table. in case specified symbols
	 *		  are present current symbol frequency table, their frequencies are incremented,
	 *		  otherwise new frequency table entries are created, with frequency 1 set
	 *		- may be called repeatedly, or combined with call(s) to Set_SymbolFrequencies()
	 *		- return true on success, false in case of memory problems
	 */
	bool Insert_Symbols(const TSymbolType *p_symbol, int n_symbol_num)
	{
		if(n_symbol_num)
			m_b_symbol_codes_dirty_flag = true;

		for(const TSymbolType *p_end = p_symbol + n_symbol_num; p_symbol < p_end; p_symbol ++) {
			bool b_found_equal;
			TFrequency t_tmp_node(*p_symbol);
			typename std::vector<TFrequency*>::iterator p_freq = p_FindEqualNext(&t_tmp_node,
				b_found_equal, sort_Symbol);

			if(b_found_equal)
				(*p_freq)->n_frequency ++; // it was found, just increase frequency
			else {
				TFrequency *p_symbol_freq;
				if(!(p_symbol_freq = new(std::nothrow) TFrequency(*p_symbol)))
					return false;
				m_symbol_freq_table.insert(p_freq, p_symbol_freq);
				if(m_symbol_freq_table.empty())
					return false;
				// it wasn't found, create new node and insert it on such a position
				// so the symbol frequency table remains sorted
			}
		}
		// insert all distinct symbols in the symbol frequency table, count symbol frequencies,
		// keeping the symbol frequency table sorted by symbol value

		return true;
	}

	/*
	 *	bool Build_HuffmanTree()
	 *		- build huffman tree and assign symbols their codes
	 *		- return false in case there was not enough free memory or log2(count of leaf nodes)
	 *		  is greater than n_max_code_bit_num (any tree will be taller than n_max_code_bit_num),
	 *		  otherwise true
	 */
	bool Build_HuffmanTree()
	{
		if(!m_b_symbol_codes_dirty_flag)
			return true;

		Sort_FrequencyList(sort_Frequency_Desc);
		// make sure the symbol frequency table is sorted by code length

		TFrequency t_all_ones(m_symbol_freq_table.front()->t_symbol);
		t_all_ones.n_frequency = 0;
		if(!stl_ut::Reserve_1More(m_symbol_freq_table))
			return false;
		m_symbol_freq_table.push_back(&t_all_ones);
		// no symbol is allowed to be all ones and last symbol in the table will be the one

		if(!Create_Tree()) {
			m_symbol_freq_table.erase(m_symbol_freq_table.end() - 1);
			return false;
		}
		m_symbol_freq_table.erase(m_symbol_freq_table.end() - 1);
		// create tree, the effect is codeword length is assigned to every symbol

		Sort_FrequencyList(sort_CodeLength);
		// make sure the symbol frequency table is sorted by code length

		for(int i = 0; i < n_max_code_bit_num; i ++)
			m_p_symbol_code_table[i].clear();
		// clean tiny lists

		{int n_index = 0, n_code_word = 0;
		for(typename std::vector<TFrequency*>::iterator p_freq = m_symbol_freq_table.begin();
		   p_freq < m_symbol_freq_table.end(); p_freq ++) {
			(*p_freq)->n_code_length_order = n_index ++;
			if(p_freq > m_symbol_freq_table.begin() &&
			   (*p_freq)->n_code_length != (*(p_freq - 1))->n_code_length)
				n_code_word <<= (*p_freq)->n_code_length - (*(p_freq - 1))->n_code_length;
			(*p_freq)->n_code_word = n_code_word ++;

			int n_index = (*p_freq)->n_code_length - 1;
			if(!stl_ut::Reserve_1More(m_p_symbol_code_table[n_index]))
				return false;
			m_p_symbol_code_table[n_index].push_back(*p_freq);
		}}
		// assign indices to sort by, repair assigned codes (the tree assign good codes,
		// but when ordered by code length, they are not ordered by code value)

		m_b_symbol_codes_dirty_flag = false;

		return true;
	}
	// build huffman tree, in worst case it will have n_max_code_bit_num levels
	// and as much leaf nodes as there is TCodeType possible values
	// sort symbol frequencies by their code length

	/*
	 *	int n_Code_Num(int n_code_length = -1)
	 *		- if n_code_length == -1, return number of distinct symbols
	 *		  in the symbol frequency table (and thereby number of codes)
	 *		- otherwise, n_code_length has to be number in range 1 to
	 *		  n_max_code_bit_num
	 *		- return value is number of codes
	 *		- in case n_code_length is in range 1 to n_max_code_bit_num and
	 *		  it's necessary to re-assign symbol codes, function may return
	 *		  -1 if there is not enough memory for Huffman tree
	 */
	int n_Code_Num(int n_code_length = -1)
	{
		if(n_code_length == -1)
			return m_symbol_freq_table.size();
		else /*if(n_code_length >= 1 && n_code_length <= n_max_code_bit_num)*/ {
			if(m_b_symbol_codes_dirty_flag && !Build_HuffmanTree())
				return -1;
			return m_p_symbol_code_table[n_code_length - 1].size();
		} /*else
			return -1;*/
	}

	/*
	 *	int n_Code_Num(int n_code_length = -1) const
	 *		- if n_code_length == -1, return number of distinct symbols
	 *		  in the symbol frequency table (and thereby number of codes)
	 *		- otherwise, n_code_length has to be number in range 1 to
	 *		  n_max_code_bit_num
	 *		- return value is number of codes
	 *		- in case n_code_length is in range 1 to n_max_code_bit_num and
	 *		  it's necessary to re-assign symbol codes, function returns -1
	 */
	int n_Code_Num(int n_code_length = -1) const
	{
		if(n_code_length == -1)
			return m_symbol_freq_table.size();
		else /*if(n_code_length >= 1 && n_code_length <= n_max_code_bit_num)*/ {
			if(m_b_symbol_codes_dirty_flag)
				return -1;
			return m_p_symbol_code_table[n_code_length - 1].size();
		} /*else
			return -1;*/
	}

	/*
	 *	int n_Code(int n_index)
	 *		- return code with index n_index (codes are sorted by their lengths in ascending order)
	 *		- in case huffman tree was not built yet, do so automatically
	 *		- return -1 if there was not enough memory, otherwise return the code
	 */
	int n_Code(int n_index) // code of n_index-th leaf node
	{
		if(m_b_symbol_codes_dirty_flag && !Build_HuffmanTree())
			return -1;
		// need tree so code lengths are valid

		Sort_FrequencyList(sort_CodeLength_Order);
		// make sure the symbol frequency table is sorted by code length

		return m_symbol_freq_table[n_index]->n_code_word;
	}

	/*
	 *	int n_Code(int n_index, int n_code_length)
	 *		- return code with index n_index in group of codes with length n_code_length
	 *		  (codes are sorted by their lengths in ascending order; index is local)
	 *		- n_code_length has to be in range 1 to n_max_code_bit_num
	 *		- in case huffman tree was not built yet, do so automatically
	 *		- return -1 if there was not enough memory, otherwise return the code
	 */
	int n_Code(int n_index, int n_code_length)
	{
		if(m_b_symbol_codes_dirty_flag && !Build_HuffmanTree())
			return -1;
		// need tree so code lengths are valid

		Sort_FrequencyList(sort_CodeLength_Order);
		// make sure the symbol frequency table is sorted by code length

		return m_p_symbol_code_table[n_code_length - 1][n_index]->n_code_word;
	}

	/*
	 *	int n_Code_Length(int n_index)
	 *		- return length of code with index n_index
	 *		  (codes are sorted by their lengths in ascending order)
	 *		- in case huffman tree was not built yet, do so automatically, return -1 if there
	 *		  was not enough memory, otherwise return code length
	 */
	int n_Code_Length(int n_index) // num of significant code bits
	{
		if(m_b_symbol_codes_dirty_flag && !Build_HuffmanTree())
			return -1;
		// need tree so code lengths are valid

		Sort_FrequencyList(sort_CodeLength_Order);
		// make sure the symbol frequency table is sorted by code length

		return m_symbol_freq_table[n_index]->n_code_length;
	}

	/*
	 *	const TSymbolType *p_Code_Symbol(int n_index)
	 *		- return symbol, code with index n_index was assigned to
	 *		  (codes are sorted by their lengths in ascending order)
	 *		- in case huffman tree was not built yet, do so automatically
	 *		- return 0 if there was not enough memory
	 */
	const TSymbolType *p_Code_Symbol(int n_index)
	{
		if(m_b_symbol_codes_dirty_flag && !Build_HuffmanTree())
			return 0;
		// need tree so code lengths are valid

		Sort_FrequencyList(sort_CodeLength_Order);
		// make sure the symbol frequency table is sorted by code length

		return &m_symbol_freq_table[n_index]->t_symbol;
	}

	/*
	 *	const TSymbolType *p_Code_Symbol(int n_index, int n_code_length)
	 *		- return symbol, code with index n_index in group of codes with
	 *		  length n_code_length, was assigned to (codes are sorted by
	 *		  their lengths in ascending order; index is local)
	 *		- n_code_length has to be in range 1 to n_max_code_bit_num
	 *		- in case huffman tree was not built yet, do so automatically
	 *		- return 0 if there was not enough memory
	 */
	const TSymbolType *p_Code_Symbol(int n_index, int n_code_length)
	{
		if(m_b_symbol_codes_dirty_flag && !Build_HuffmanTree())
			return 0;
		// need tree so code lengths are valid

		Sort_FrequencyList(sort_CodeLength_Order);
		// make sure the symbol frequency table is sorted by code length

		return &m_p_symbol_code_table[n_code_length - 1][n_index]->t_symbol;
	}

	/*
	 *	int n_Code_Symbol_Frequency(int n_index)
	 *		- return frequency of symbol, code with index n_index was assigned to
	 *		  (codes are sorted by their lengths in ascending order)
	 *		- in case huffman tree was not built yet, do so automatically, return -1 on failure
	 */
	int n_Code_Symbol_Frequency(int n_index)
	{
		if(m_b_symbol_codes_dirty_flag && !Build_HuffmanTree())
			return -1;
		// need tree so code lengths are valid

		Sort_FrequencyList(sort_CodeLength_Order);
		// make sure the symbol frequency table is sorted by code length

		return m_symbol_freq_table[n_index]->n_frequency;
	}

	/*
	 *	bool TranslateSymbol(const TSymbolType &r_t_symbol, int &r_n_code_word,
	 *		int &r_n_code_bit_num)
	 *		- translate symbol r_t_symbol to code word r_n_code_word with r_n_code_bit_num
	 *		  significant bits, aligned to LSB
	 */
	bool TranslateSymbol(const TSymbolType &r_t_symbol, int &r_n_code_word, int &r_n_code_bit_num)
	{
		if(m_b_symbol_codes_dirty_flag && !Build_HuffmanTree())
			return false;
		// need tree so code lengths are valid

		typename std::vector<TFrequency*>::iterator p_symbol_freq;
		if(!*(p_symbol_freq = p_FindEqual(r_t_symbol)))
			return false;
		// try to find record with required symbol

		r_n_code_word = (*p_symbol_freq)->n_code_word;
		r_n_code_bit_num = (*p_symbol_freq)->n_code_length;

		return true;
	}

protected:
	void Sort_FrequencyList(int n_sort_key)
	{
		if(m_n_sort_key == n_sort_key)
			return;
		int (*p_CmpFunc)(const void *p_a, const void *p_b);
		if(n_sort_key == sort_Symbol)
			p_CmpFunc = n_CmpSymbolFunc;
		else if(n_sort_key == sort_CodeLength_Order)
			p_CmpFunc = n_CmpLengthOrderFunc;
		else if(n_sort_key == sort_Frequency_Desc)
			p_CmpFunc = n_CmpFreqDescFunc;
		else /*if(n_sort_key == sort_CodeLength)*/
			p_CmpFunc = n_CmpLengthFunc;
		m_n_sort_key = n_sort_key;
		qsort(&m_symbol_freq_table[0], m_symbol_freq_table.size(),
			sizeof(TFrequency*), p_CmpFunc);
	}

	static int n_CmpSymbolFunc(const void *p_a, const void *p_b)
	{
		const TFrequency *p_freq_a = *(const TFrequency**)p_a;
		const TFrequency *p_freq_b = *(const TFrequency**)p_b;
		return _CSymbolComparer()(p_freq_a->t_symbol, p_freq_b->t_symbol);
	}

	static int n_CmpLengthFunc(const void *p_a, const void *p_b)
	{
		const TFrequency *p_freq_a = *(const TFrequency**)p_a;
		const TFrequency *p_freq_b = *(const TFrequency**)p_b;
		if(p_freq_a->n_code_length > p_freq_b->n_code_length)
			return 1;
		if(p_freq_a->n_code_length < p_freq_b->n_code_length)
			return -1;
		return 0;
	}

	static int n_CmpLengthOrderFunc(const void *p_a, const void *p_b)
	{
		const TFrequency *p_freq_a = *(const TFrequency**)p_a;
		const TFrequency *p_freq_b = *(const TFrequency**)p_b;
		if(p_freq_a->n_code_length_order > p_freq_b->n_code_length_order)
			return 1;
		if(p_freq_a->n_code_length_order < p_freq_b->n_code_length_order)
			return -1;
		return 0;
	}

	static int n_CmpFreqDescFunc(const void *p_a, const void *p_b)
	{
		const TFrequency *p_freq_a = *(const TFrequency**)p_a;
		const TFrequency *p_freq_b = *(const TFrequency**)p_b;
		if(p_freq_a->n_frequency > p_freq_b->n_frequency)
			return -1;
		if(p_freq_a->n_frequency < p_freq_b->n_frequency)
			return 1;
		return 0;
	}

	/*
	 *	std::vector<TFrequency*>::iterator p_FindEqualNext(const TFrequency *p_symbol_freq,
	 *		bool &r_b_equal, int n_sort_key)
	 *		- find position in symbol frequency table where to insert symbol
	 *		- in case record with equal symbol was found, it's returned and r_b_equal is set to true
	 *		- in case it was not found, position in the symbol frequency table where record with
	 *		  r_t_symbol should be inserted is returned (front on empty table or position
	 *		  of record with nearest greater symbol to r_t_smybol) and r_b_equal is set to false
	 */
	typename std::vector<TFrequency*>::iterator p_FindEqualNext(const TFrequency *p_symbol_freq,
		bool &r_b_equal, int n_sort_key)
	{
		if(m_symbol_freq_table.empty()) {
			r_b_equal = false;
			return m_symbol_freq_table.begin();
		}

		Sort_FrequencyList(n_sort_key);
		// make sure the symbol frequency table is sorted by the right key

		int (*p_CmpFunc)(const void *p_a, const void *p_b);
		if(n_sort_key == sort_Symbol)
			p_CmpFunc = n_CmpSymbolFunc;
		else if(n_sort_key == sort_CodeLength_Order)
			p_CmpFunc = n_CmpLengthOrderFunc;
		else if(n_sort_key == sort_Frequency_Desc)
			p_CmpFunc = n_CmpFreqDescFunc;
		else /*if(n_sort_key == sort_CodeLength)*/
			p_CmpFunc = n_CmpLengthFunc;

		typename std::vector<TFrequency*>::iterator p_cur =
			m_symbol_freq_table.begin();
		_ASSERTE(!m_symbol_freq_table.empty()); // caught above
		const size_t n_freq_table_size = m_symbol_freq_table.size();
		const size_t n_freq_table_size1 = m_symbol_freq_table.size() - 1;
		size_t n_cur = min((m_symbol_freq_table.size() + 1) / 2, n_freq_table_size1);
		p_cur += n_cur;
		_ASSERTE(p_cur >= m_symbol_freq_table.begin());
		_ASSERTE(p_cur < m_symbol_freq_table.end());
		size_t n_max_step = (m_symbol_freq_table.size() + 1) / 2; // 2012-05-21 fix
		while(1) {
			int n_comparison;
			if(!(n_comparison = p_CmpFunc(&*p_cur, &p_symbol_freq))) {
				r_b_equal = true;
				return p_cur; // found equal
			} else if(n_comparison > 0) {
				// cur > symbol, move left

				if(p_cur == m_symbol_freq_table.begin()) {
					r_b_equal = false;
					return p_cur;
				}
				// we are left-most, we failed to find the symbol

				size_t n_cur2 = max(n_cur, n_max_step) - n_max_step;
				p_cur -= n_cur - n_cur2;
				n_cur = n_cur2;
				_ASSERTE(p_cur >= m_symbol_freq_table.begin());
				// jump to front
			} else if(n_comparison < 0) {
				// cur < symbol, move right

				if(p_cur == m_symbol_freq_table.end() - 1) {
					r_b_equal = false;
					return m_symbol_freq_table.end();
				}
				// we are right-most, we failed to find the symbol

				if(p_CmpFunc(&*(p_cur + 1), &p_symbol_freq) > 0) {
					r_b_equal = false;
					return p_cur + 1;
				}
				// cur + 1 > symbol, we need to place it between cur and cur + 1

				size_t n_cur2 = min(n_cur + n_max_step, n_freq_table_size1);
				p_cur += n_cur2 - n_cur;
				n_cur = n_cur2;
				_ASSERTE(p_cur < m_symbol_freq_table.end());
				// jump to back
			}
			n_max_step /= 2;
			if(!n_max_step)
				n_max_step ++;
			// divide step, but keep non-zero
		};
	}

	/*
	 *	std::vector<TFrequency*>::iterator p_FindEqual(const TSymbolType &r_t_symbol)
	 *		- find record with symbol, equal to r_t_symbol and return pointer to it
	 *		- in case such a record is not in the symbol frequency table, return 0
	 */
	typename std::vector<TFrequency*>::iterator p_FindEqual(const TSymbolType &r_t_symbol)
	{
		Sort_FrequencyList(sort_Symbol);
		// make sure the symbol frequency table is sorted by smybol

		TFrequency t_freq(r_t_symbol), *p_freq = &t_freq;
		return m_symbol_freq_table.begin() + ((const TFrequency**)bsearch(&p_freq,
			&m_symbol_freq_table[0], m_symbol_freq_table.size(), sizeof(TFrequency*),
			n_CmpSymbolFunc) - &m_symbol_freq_table[0]);
		// use (possibly better optimized) std library binary search function
	}

	/*
	 *	bool Create_Tree()
	 *		- create huffman tree, fill-in symbol lengths (source data from m_symbol_freq_table)
	 *		- return true on success or false on failure
	 */
	bool Create_Tree()
	{
		if(m_symbol_freq_table.size() > (1 << n_max_code_bit_num))
			return false;
		// too much symbols

		typename std::vector<TFrequency*>::const_iterator p_stack[(n_max_code_bit_num + 1) * 2];
		int p_level[n_max_code_bit_num + 1];
		int n_stack_level = 0;

		int n_level = 0;
		for(typename std::vector<TFrequency*>::const_iterator p_front = m_symbol_freq_table.begin(),
		   p_back = m_symbol_freq_table.end() - 1;;) {
			int n_symbol_num = p_back - p_front + 1;
			if(n_symbol_num == 1) {
				(*p_front)->n_code_length = n_level;
				// assign code length

				if(!n_stack_level)
					break;

				_ASSERTE(!(n_stack_level & 1) && n_stack_level >= 2);

				p_back = p_stack[-- n_stack_level];
				p_front = p_stack[-- n_stack_level];
				n_level = p_level[n_stack_level / 2];
				// pop

				continue;
			}
			// in case we have a single symbol, we have leaf node

			_ASSERTE(n_symbol_num);

			int n_levels_left = n_max_code_bit_num - n_level;
			_ASSERTE(n_levels_left > 0);

			int n_max_subnode_symbol_num = 1 << (n_levels_left - 1);
			// calc maximal number of symbols each subnode can get

			typename std::vector<TFrequency*>::const_iterator p_front_pivot, p_back_pivot;
			int n_balance = 0;
			if(n_symbol_num > n_max_subnode_symbol_num) {
				p_front_pivot = p_back - n_max_subnode_symbol_num;
				p_back_pivot = p_front + n_max_subnode_symbol_num;

				for(typename std::vector<TFrequency*>::const_iterator p_freq = p_front;
				   p_freq < p_front_pivot; p_freq ++)
					n_balance += (*p_freq)->n_frequency;
				for(typename std::vector<TFrequency*>::const_iterator p_freq = p_back;
				   p_freq > p_back_pivot; p_freq --)
					n_balance -= (*p_freq)->n_frequency;
				// calc fixed balance (given by bounds)
			} else {
				p_front_pivot = p_front;
				p_back_pivot = p_back;
			}
			// find front and back pivot bounds

			while(p_front_pivot < p_back_pivot - 1) {
				if(abs(n_balance + (*p_front_pivot)->n_frequency) <
				   abs(n_balance - (*p_back_pivot)->n_frequency))
					n_balance += (*(p_front_pivot ++))->n_frequency;
				else
					n_balance -= (*(p_back_pivot --))->n_frequency;
			}
			_ASSERTE(p_front_pivot == p_back_pivot - 1);
			// find (best) balanced pivot within bounds

			p_level[n_stack_level / 2] = ++ n_level;
			p_stack[n_stack_level ++] = p_back_pivot;
			p_stack[n_stack_level ++] = p_back;
			// store second interval (p_back_pivot - p_back) in stack for further processing

			p_back = p_front_pivot;
			// move onto first interval (p_front - p_front_pivot)
		}
		// t_odo - find pivot and recursively subdivide the tree,
		// writing code lengths into m_symbol_freq_table items

		return true;
	}
};

#endif // !__HUFFMAN_CODER_2_INCLUDED
