// HuffmanImpl.h

/*
 * (c) Markus Lumpe, 2007
 *	v 1.1
 */

#include <sstream>
#include <fstream>
#include <iomanip>

#include "Huffman.h"

////////////////////////////////////////////////////////////////////////////////////
// I/O primitives

void writeBinaryCStr( ostream& aOS, char* aValue )
{
	aOS.write( aValue, strlen( aValue ) );
}

void writeBinaryInt( ostream& aOS, int aValue )
{
	aOS.write( (char*)&aValue, sizeof( int ) );
}

void writeBinaryLong( ostream& aOS, long aValue )
{
	aOS.write( (char*)&aValue, sizeof( long ) );
}

template <class T>
void writeBinaryHuffmanLength( ostream& aOS, int aValue )
{
	int lSize = HuffmanCode<T>::getMaxSize();
	byte* lBuffer = new byte[lSize];
	
	for ( int i = 0; i < lSize; i++ )
	{
		lBuffer[i] = aValue & 0xff;
		aValue >>= 8;
	}
	
	aOS.write( (char*)lBuffer, lSize );
	delete lBuffer;
}

void writeBinaryHuffmanCode( ostream& aOS, const HuffmanBitCode& aCode )
{
	int lLength = aCode.size();
	int lSize = (lLength / 8) + (lLength % 8 == 0 ? 0 : 1);
	aOS.write( (char*)aCode.getBits(), lSize );
}

void readBinaryCStr( istream& aIS, string& aValue, int aMaxLength )
{	
	char* lBuffer = new char[aMaxLength];
	
	aIS.read( lBuffer, aMaxLength );
	aValue = string(lBuffer);
	delete lBuffer;
}

void readBinaryInt( istream& aIS, int& aValue )
{
	aIS.read( (char*)&aValue, sizeof( int ) );
}

void readBinaryLong( istream& aIS, long& aValue )
{
	aIS.read( (char*)&aValue, sizeof( long ) );
}

template <class T>
void readBinaryHuffmanLength( istream& aIS, int& aValue )
{
	int lCodeLength = HuffmanCode<T>::getMaxLength();
	int lSize = 0;
	
	while ( lCodeLength )
	{
		lSize++;
		lCodeLength >>= 8;	
	}
	
	byte* lBuffer = new byte[lSize];
	aIS.read( (char*)lBuffer, lSize );
	
	int lValue = 0;
	for ( int i = lSize - 1; i >= 0; i-- )
	{
		lValue <<= 8;
		lValue |= lBuffer[i];
	}
	
	delete lBuffer;
	aValue = lValue;
}

void readBinaryHuffmanCode( istream& aIS, HuffmanBitCode& aCode, int aCodeLength )
{
	int lSize = (aCodeLength / 8) + (aCodeLength % 8 == 0 ? 0 : 1);
	byte* lBuffer = new byte[lSize];

	aIS.read( (char*)lBuffer, lSize );
	HuffmanBitCode lCode( lBuffer, aCodeLength );
	delete lBuffer;
	aCode = lCode;
}

////////////////////////////////////////////////////////////////////////////////////
// HuffmanException

HuffmanException::HuffmanException( string aMessage )
{
	fMessage = aMessage;	
}
	
HuffmanException::HuffmanException( int aLine, string aFileName, string aMessage )
{
	stringstream lSS;
	
	lSS << "In " << aFileName << " at line " << aLine << ": " << aMessage;
	fMessage = lSS.str();
}

string HuffmanException::getMessage()
{
	return fMessage;	
}

////////////////////////////////////////////////////////////////////////////////////
// HuffmanBitCode

void HuffmanBitCode::extend( int aToCodeLength )
{
	int lNumberOfBytes = (aToCodeLength / 8) + (aToCodeLength % 8 == 0 ? 0 : 1); 
	byte* lBitArray = NULL;

	if ( lNumberOfBytes )
	{	
	 	lBitArray = new byte[lNumberOfBytes];
	
		for ( int i = 0; i < lNumberOfBytes; i++ )
			lBitArray[i] = 0;
	
		if ( fBitArray )
		{
			int lBytesToCopy = (fCodeLength / 8) + (fCodeLength % 8 == 0 ? 0 : 1);
			for ( int i = 0; i < lBytesToCopy; i++ )
				lBitArray[i] = fBitArray[i];
		}
	}
		
	delete fBitArray;
	fBitArray = lBitArray;
	fCodeLength = aToCodeLength;
}

void HuffmanBitCode::copy( byte aBitArray[], int aCodeLength )
{
	fBitArray = NULL;
	fCodeLength = aCodeLength;

	if ( aCodeLength )
	{
		int lByteLength = (aCodeLength / 8) + (aCodeLength % 8 == 0 ? 0 : 1); 
		fBitArray = new byte[lByteLength];
	
		for ( int i = 0; i < lByteLength; i++ )
			fBitArray[i] = aBitArray[i];
	}	
}

HuffmanBitCode::HuffmanBitCode()
{
	fBitArray = NULL;
	fCodeLength = 0;
}

HuffmanBitCode::HuffmanBitCode( byte aBitArray[], int aCodeLength )
{
	copy( aBitArray, aCodeLength );	
}

void HuffmanBitCode::copy( const HuffmanBitCode& aCode )
{
	copy( aCode.fBitArray, aCode.fCodeLength );
}

HuffmanBitCode::HuffmanBitCode( const HuffmanBitCode& aBitCode )
{
	copy( aBitCode );
}

HuffmanBitCode& HuffmanBitCode::operator=( const HuffmanBitCode& aBitCode )
{
	copy( aBitCode );
	return *this;
}

HuffmanBitCode::~HuffmanBitCode()
{
	delete fBitArray;
}

HuffmanBitCode::iterator::iterator()
{
	fCode = NULL;
	fIndex = 0;	
}

HuffmanBitCode::iterator::iterator( HuffmanBitCode* aCode )
{
	fCode = aCode;
	fIndex = 0;	
}

HuffmanBitCode::iterator::iterator( HuffmanBitCode* aCode, unsigned int aPosition )
{
	fCode = aCode;
	fIndex = aPosition;	
}
		
int HuffmanBitCode::iterator::operator*() const
{
	if ( fIndex < fCode->size() )
		return (*fCode)[fIndex];
	else
		throw HuffmanException( "Invalid iterator!" );
}

HuffmanBitCode::iterator& HuffmanBitCode::iterator::operator++()
{
	fIndex++;
	return *this;	
}

HuffmanBitCode::iterator HuffmanBitCode::iterator::operator++(int)
{
	iterator lTemp = *this;
	fIndex++;
	return lTemp;	
}

bool HuffmanBitCode::iterator::operator==( const iterator& aOther ) const
{
	return (fCode == aOther.fCode) && (fIndex == aOther.fIndex);
}

bool HuffmanBitCode::iterator::operator!=( const iterator& aOther ) const
{
	return !(*this == aOther);
}

HuffmanBitCode::iterator HuffmanBitCode::iterator::end()
{
	return iterator( fCode, fCode->fCodeLength );	
}

HuffmanBitCode::iterator HuffmanBitCode::iterator::next()
{
	return iterator( fCode, fIndex + 1 );	
}

HuffmanBitCode::iterator HuffmanBitCode::begin()
{
	return iterator( this );
}

HuffmanBitCode::iterator HuffmanBitCode::end()
{
	return iterator( this, fCodeLength );
}

byte* HuffmanBitCode::getBits() const
{
	return fBitArray;	
}

unsigned int HuffmanBitCode::size() const
{
	return (unsigned int)fCodeLength;	
}

int HuffmanBitCode::lengthInByte() const
{
	return (fCodeLength / 8) + (fCodeLength % 8 == 0 ? 0 : 1); 
}

void HuffmanBitCode::add0()
{
	if ( (fCodeLength % 8) == 0 )
		extend( fCodeLength + 1 );
	else
		fCodeLength++;
}

void HuffmanBitCode::add1()
{
	int lCodeLength = fCodeLength;
	
	if ( (fCodeLength % 8) == 0 )
		extend( fCodeLength + 1 );
	else
		fCodeLength++;

	int lByteIndex = lCodeLength / 8;
	int lBitIndex = lCodeLength % 8;
	fBitArray[lByteIndex] |= (1 << (7 - lBitIndex));
}

int HuffmanBitCode::at( unsigned int aIndex ) const
{
	if ( (aIndex >= 0) && (aIndex < fCodeLength) )
	{
		int lByteIndex = aIndex / 8;
		int lBitIndex = aIndex % 8;
		return fBitArray[lByteIndex] & (1 << (7 - lBitIndex)) ? 1 : 0;
	}
	else
		throw HuffmanException( "Index out of range!" ); 		
}

int HuffmanBitCode::operator[]( unsigned int aIndex ) const
{
	return at( aIndex );
}

bool operator<( const HuffmanBitCode& aLeft, const HuffmanBitCode& aRight )
{
	if ( aLeft.size() == aRight.size() )
	{
		for ( unsigned int i = 0; i < aLeft.size(); i++ )
		{
			if ( aLeft[i] < aRight[i] )
				return true;	
		}
		return false;
	}
	return 	aLeft.size() < aRight.size();
}

ostream& operator<<( ostream& aOS, const HuffmanBitCode& aCode )
{
	for ( unsigned int i = 0; i < aCode.size(); i++ )
	{
		if ( aCode[i] )
			aOS << "1";
		else
			aOS << "0";	
	}	
	return aOS;
}

////////////////////////////////////////////////////////////////////////////////////
// IHuffmanElement<T>

template <class T>
ostream& operator<<( ostream& aOS, const IHuffmanElement<T>* aElement )
{
	// aElement not NULL
	if ( aElement )
	{
		// determine the correct << operator	
		if ( typeid(*aElement) == typeid(HuffmanLeaf<T>) )
			aOS << *(HuffmanLeaf<T>*)(aElement);
		else
			aOS << (HuffmanNode<T>*)(aElement);
	}
	return aOS;
}

////////////////////////////////////////////////////////////////////////////////////
// HuffmanCode<T>

template <class T> unsigned int HuffmanCode<T>::fMaxLength = 8 * sizeof(T);
template <class T> unsigned int HuffmanCode<T>::fMaxSize = sizeof(T);

template <class T>
HuffmanCode<T>::HuffmanCode()
{
	fMappedCharacter = init<T>();
}

template <class T>
HuffmanCode<T>::HuffmanCode( T aMappedCharacter )
{
	fMappedCharacter = aMappedCharacter;

	// build initial Huffman code
	int lLength = 8 * sizeof(T);
	while ( lLength-- )
	{
		if ( aMappedCharacter & 0x1 )
			fCode.add1();
		else
			fCode.add0();
		aMappedCharacter >>= 1;
	}
}

template <class T>
HuffmanCode<T>::HuffmanCode( T aMappedCharacter, HuffmanBitCode aCode )
{
	fMappedCharacter = aMappedCharacter;
	fCode = aCode;
}

template <class T>
T HuffmanCode<T>::getMappedCharacter() const
{
	return fMappedCharacter;	
}

template <class T>
const HuffmanBitCode HuffmanCode<T>::getCode() const
{
	return fCode;	
}

template <class T>
void HuffmanCode<T>::setMaxLength( unsigned int aMaxLength )
{
	fMaxLength = aMaxLength;
	int lSize = 0;
	
	while ( aMaxLength )
	{
		lSize++;
		aMaxLength >>= 8;	
	}
	fMaxSize = lSize;
}

template <class T>
unsigned int HuffmanCode<T>::getMaxLength()
{
	return fMaxLength;	
}

template <class T>
unsigned int HuffmanCode<T>::getMaxSize()
{
	return fMaxSize;	
}

template <class T>
void HuffmanCode<T>::setHuffmanMapping( HuffmanBitCode aCode )
{
	if ( aCode.size() <= fMaxLength )
		fCode = aCode;
	else
		throw HUFFMAN_EXCEPTION( "Huffman mapping too long." );
}

template <class T>
bool operator<( const HuffmanCode<T>& aLeft, const HuffmanCode<T>& aRight )
{
	HuffmanCode<T> lLeft = aLeft;	
	HuffmanCode<T> lRight = aRight;
	
	return lLeft.getMappedCharacter() < lRight.getMappedCharacter();	
}

template <class T>
ostream& operator<<( ostream& aOS, const HuffmanCode<T>& aCode )
{
	HuffmanCode<T> lCode = aCode;
	HuffmanBitCode lBitCode = aCode.getCode();
	
	aOS << "[" << hex << (long)lCode.getMappedCharacter() << "," <<
		 		  dec << lBitCode.size() << "," << lBitCode << "]";
	return aOS;	
}

////////////////////////////////////////////////////////////////////////////////////
// HuffmanLeaf<T>

template <class T>
HuffmanLeaf<T>::HuffmanLeaf( T aCharacter, long aFrequency ) : fCharacter(aCharacter)
{
	fFrequency = aFrequency;
	fDegree = 0; // mark leave degree
}

template <class T>
HuffmanLeaf<T>::HuffmanLeaf( HuffmanCode<T> aCode )
{
	fCharacter = aCode;
	fFrequency = 0; // cannot be used 
	fDegree = 0;	
}

template <class T>
T HuffmanLeaf<T>::getCharacter() const
{
	return fCharacter.getMappedCharacter();	
}

template <class T>
long HuffmanLeaf<T>::getFrequency() const
{
	return fFrequency;	
}

template <class T>
long HuffmanLeaf<T>::getDataSize() const
{
	return getFrequency() * fCharacter.getCode().size();	
}

template <class T>
long HuffmanLeaf<T>::getDictionarySize() const
{
	long lCodeLength = fCharacter.getCode().size();
	lCodeLength = (lCodeLength / 8) + (lCodeLength % 8 == 0 ? 0 : 1); 
	
	return sizeof(T) + HuffmanCode<T>::getMaxSize() + lCodeLength;
}

template <class T>
int HuffmanLeaf<T>::getDegree() const
{
	return fDegree;	
}

template <class T>
const HuffmanBitCode HuffmanLeaf<T>::getCode() const
{
	return fCharacter.getCode();	
}

template <class T>
void HuffmanLeaf<T>::setHuffmanCode( HuffmanBitCode aCode )
{
	fCharacter.setHuffmanMapping( aCode );
}

template <class T>
void HuffmanLeaf<T>::collectHuffmanCodes( set< HuffmanCode<T> >& aSet ) const
{
	aSet.insert( fCharacter );	
}

template <class T>
ostream& operator<<( ostream& aOS, const HuffmanLeaf<T>& aLeave )
{
	HuffmanLeaf<T> lLeave = aLeave;
	HuffmanBitCode lCode = lLeave.getCode();
	
	aOS << "(" << hex<< (int)lLeave.getCharacter() << "," << 
	 		dec << lLeave.getFrequency() << 
	 		",[" << lCode << "," << lCode.size() << "])";	
	return aOS;
}

////////////////////////////////////////////////////////////////////////////////////
// HuffmanNode<T>

template <class T>
int HuffmanNode<T>::fCount = 0;

template <class T>
HuffmanNode<T>::HuffmanNode()
{
	fLeft = NULL;
	fRight = NULL;
	fSum = 0;	
}

inline int max( int aLeft, int aRight )
{
	return aLeft < aRight ? aRight : aLeft;	
}

template <class T>
HuffmanNode<T>::HuffmanNode( IHuffmanElement<T>* aLeft, IHuffmanElement<T>* aRight )
{
	fLeft = aLeft;
	fRight = aRight;
	fNumber = fCount++;	
	if ( fLeft != NULL && fRight != NULL )
	{
		fSum = fLeft->getFrequency() + fRight->getFrequency();
		fDegree = 1 + max( fLeft->getDegree(), fRight->getDegree() );
	}
	else
	{
		fSum = 0;
		fDegree = 0;	
	}
}

template <class T>
HuffmanNode<T>::~HuffmanNode()
{
	delete fLeft;
	delete fRight;
}

template <class T>
IHuffmanElement<T>* HuffmanNode<T>::getLeft() const
{
	return fLeft;	
}

template <class T>
IHuffmanElement<T>* HuffmanNode<T>::getRight() const
{
	return fRight;	
}

template <class T>
long HuffmanNode<T>::getFrequency() const
{
	return fSum;	
}

template <class T>
long HuffmanNode<T>::getDataSize() const
{
	long Result = 0;;
	
	if ( fLeft )
		Result += fLeft->getDataSize();	
	if ( fRight )
		Result += fRight->getDataSize();	
	return Result;
}

template <class T>
long HuffmanNode<T>::getDictionarySize() const
{
	long Result = 0;;
	
	if ( fLeft )
		Result += fLeft->getDictionarySize();	
	if ( fRight )
		Result += fRight->getDictionarySize();	
	return Result;
}

template <class T>
int HuffmanNode<T>::getCount() const
{
	return fNumber;
}

template <class T>
int HuffmanNode<T>::getDegree() const
{
	return fDegree;	
}

template <class T>
void HuffmanNode<T>::setHuffmanCode( HuffmanBitCode aHuffmanCode )
{
	HuffmanBitCode lCode;

	if ( fLeft ) // add 0
	{
		lCode = aHuffmanCode;
		lCode.add0();
		fLeft->setHuffmanCode( lCode );
	}
	if ( fRight ) // add 1
	{
		lCode = aHuffmanCode;
		lCode.add1();
		fRight->setHuffmanCode( lCode );
	}
}

template <class T>
void HuffmanNode<T>::collectHuffmanCodes( set< HuffmanCode<T> >& aSet ) const
{
	if ( fLeft )
		fLeft->collectHuffmanCodes( aSet );
	if ( fRight )
		fRight->collectHuffmanCodes( aSet );
}

template <class T>
void HuffmanNode<T>::buildSubtree( HuffmanCode<T> aCode, HuffmanBitCode::iterator aRemainingBits )
{
	// advance iterator to next bit
	HuffmanBitCode::iterator lNewRemainingBits = aRemainingBits.next();

	IHuffmanElement<T>** lNextHook;

	if ( *aRemainingBits == 1 )
		lNextHook = &fRight;
	else
		lNextHook = &fLeft;

	// Have we reached a leave?
	if ( lNewRemainingBits == lNewRemainingBits.end() )
	{
		if ( *lNextHook != 0 )
		{
			cout << *lNextHook << endl;
			cout << aCode << endl;
			throw HUFFMAN_EXCEPTION( "Node already set." );
		}
		*lNextHook = new HuffmanLeaf<T>( aCode );
	}
	else
	{
		if ( *lNextHook == 0 )
		{
			HuffmanNode<T>* lNewNode = new HuffmanNode<T>( NULL, NULL );
			*lNextHook = lNewNode;
			lNewNode->buildSubtree( aCode, lNewRemainingBits );
		}
		else
		{
			if ( typeid(**lNextHook) != typeid(HuffmanNode<T>) )
			{
				cout << *lNextHook << endl;
				cout << aCode << endl;
				throw HUFFMAN_EXCEPTION( "Illegal node type." );
			}
			((HuffmanNode<T>*)(*lNextHook))->buildSubtree( aCode, lNewRemainingBits );
		}
	}
}

template <class T>
ostream& operator<<( ostream& aOS, const HuffmanNode<T>* aNode )
{
	HuffmanNode<T>* lNode = (HuffmanNode<T>*)aNode;
	
	aOS << "{" << dec << lNode->getFrequency() << 
			"," << lNode->getLeft() << 
			"," << lNode->getRight() << "}";	
	return aOS;
}

////////////////////////////////////////////////////////////////////////////////////
// HuffmanTree<T>

template <class T>
HuffmanTree<T>::HuffmanTree()
{
	fElements = NULL;
	fNumberOfCharacters = 0;	
}

template <class T>
HuffmanTree<T>::~HuffmanTree()
{
	delete fElements;
}

template <class T>
set< IHuffmanElement<T>*, LessIHuffmanElementPtr<T> > HuffmanTree<T>::analyzeFrequencies( istream& aIS ) const
{
	// analyze frequencies
	map <T,long> lCharacterFrequencies;
	T lCharacter;

	// reset file pointer	
	aIS.clear();
	aIS.seekg( 0 );
	
	cout << "Analyzing character frequencies " << flush;
	
	// we use the fact that long() is the default initializer for int	
	while ( HuffmanCharacter<T>::read( aIS, lCharacter ) )
		lCharacterFrequencies[lCharacter]++;
	
	cout << "done" << endl;
	
	// we have computed the frequencies, build set now
	typename map<T,long>::iterator iter;
	set< IHuffmanElement<T>*, LessIHuffmanElementPtr<T> > Result;

	for ( iter = lCharacterFrequencies.begin(); iter != lCharacterFrequencies.end(); ++iter )
	{
		Result.insert( new HuffmanLeaf<T>( iter->first, iter->second ) );
	}
	
	return Result;	
}

template <class T>
void HuffmanTree<T>::buildTree( istream& aIS )
{
	set< IHuffmanElement<T>*, LessIHuffmanElementPtr<T> > lSet = analyzeFrequencies( aIS );
	
 	typedef typename set< IHuffmanElement<T>*, LessIHuffmanElementPtr<T> >::iterator SETI;

	while ( lSet.size() > 1 )
	{
		SETI iter = lSet.begin();
		
		IHuffmanElement<T>* lLeft = *iter;
		lSet.erase( iter ); // remove left
		++iter;
		IHuffmanElement<T>* lRight = *iter;
		lSet.erase( iter ); // remove right

		// build new parent		
		lSet.insert( new HuffmanNode<T>( lLeft, lRight ) );
	}

	// set tree root
	fElements = *(lSet.begin());
	if ( fElements == NULL )
		throw HUFFMAN_EXCEPTION( "No nodes!" );
	fNumberOfCharacters = fElements->getFrequency();
}

template <class T>
void HuffmanTree<T>::buildHuffmanCodes()
{
	if ( fElements )
	{
		HuffmanBitCode lCode;

		HuffmanCode<T>::setMaxLength( getDegree() );
		fElements->setHuffmanCode( lCode );
	}
}

template <class T>
void HuffmanTree<T>::buildDictionary()
{
	if ( fElements )
		fElements->collectHuffmanCodes( fDictionary );
}

template <class T>
void HuffmanTree<T>::writeHeaderToStream( ostream& aOS )
{
	buildHuffmanCodes();
	buildDictionary();
	
	writeBinaryCStr( aOS, "HUFF-229" ); 					// write magic id
	writeBinaryLong( aOS, fNumberOfCharacters );			// write number of characters
	writeBinaryInt( aOS, HuffmanCode<T>::getMaxLength() );	// write max code length
	writeBinaryInt( aOS, fDictionary.size() );				// write number of mappings

	// write Huffman mappings [T, L, C]
	typedef typename set< HuffmanCode<T> >::iterator SETI;
		
	for ( SETI iter = fDictionary.begin(); iter != fDictionary.end(); ++iter )
	{
		HuffmanCode<T> lElem = *iter;
		HuffmanBitCode lCode = lElem.getCode(); 
		
		HuffmanCharacter<T>::write( aOS, lElem.getMappedCharacter() );	// write mapped character
		writeBinaryHuffmanLength<T>( aOS, lCode.size() );				// write code length
		writeBinaryHuffmanCode( aOS, lCode );							// write Huffman code
	}	
}

template <class T>
void HuffmanTree<T>::compressStream( ostream& aOS, istream& aIS )
{
	// build Huffman tree
	buildTree( aIS );

	// create header
	writeHeaderToStream( aOS );

	cout << "Effective compression: " << getEffectiveRatio() << "%" << endl;

	// build mapping for compression
	map <T, HuffmanBitCode> lMap;
	for ( typename set< HuffmanCode<T> >::iterator iter = fDictionary.begin(); iter != fDictionary.end(); ++iter )
	{
		HuffmanCode<T> lCharacter = *iter;
		lMap[lCharacter.getMappedCharacter()] = lCharacter.getCode();
	}	
 	
	// compress
	T lCharacter;

	// reset file pointer	
	aIS.clear();
	aIS.seekg( 0 );
	
	cout << "Compressing character stream " << flush;
	
	BitStreamWriter lBitStream( aOS );
	
	while ( HuffmanCharacter<T>::read( aIS, lCharacter ) )
		lBitStream.writeBits( lMap[lCharacter] );

	lBitStream.finish();
	cout << "done" << endl;
}

template <class T>
void HuffmanTree<T>::uncompressStream( ostream& aOS, istream& aIS )
{
	buildTreeFromHeaderOfStream( aIS );
	
	BitStreamReader<T> lBitStream( aIS, this );
	T lCharacter = 0;
	
	cout << "uncompressing " << flush;
	
	while ( lBitStream.getCharacter( lCharacter ) )
		HuffmanCharacter<T>::write( aOS, lCharacter );	

	cout << "done" << endl;
}

template <class T>
struct LessHuffmanCode : public binary_function<HuffmanCode<T>, HuffmanCode<T>, bool>
{
	bool operator()(const HuffmanCode<T>& aLeft, const HuffmanCode<T>& aRight) const
    { 
    	return aLeft.getCode() < aRight.getCode();
    }
};

template <class T>
void HuffmanTree<T>::buildTreeFromHeaderOfStream( istream& aIS )
{
	string lBuffer("");
	int lMaxCodeLength;
	int lDictionaryLength;
	
	readBinaryCStr( aIS, lBuffer, 8 ); 				// read magic id
	if ( lBuffer != "HUFF-229" )
		throw HuffmanException( "Input file is not Huffman-compressed!" );
	readBinaryLong( aIS, fNumberOfCharacters );		// read number of characters
	readBinaryInt( aIS, lMaxCodeLength );			// read max code length
	HuffmanCode<T>::setMaxLength( lMaxCodeLength );
	readBinaryInt( aIS, lDictionaryLength );		// read number of mappings

	// read Huffman mappings [T, L, C]
	T lCharacter;
	int lCodeLength;
	HuffmanBitCode lCode;
	set< HuffmanCode<T>, LessHuffmanCode<T> > lSet;
	
	for ( int i = 0; i < lDictionaryLength; i++ )
	{
		HuffmanCharacter<T>::read( aIS, lCharacter );			// read mapped character
		readBinaryHuffmanLength<T>( aIS, lCodeLength );			// read code length
		readBinaryHuffmanCode( aIS, lCode, lCodeLength );		// read Huffman code
		lSet.insert( HuffmanCode<T>( lCharacter, lCode ) );
	}
		
	typename set< HuffmanCode<T>, LessHuffmanCode<T> >::iterator iter;

	if ( lSet.size() == 1 )
	{
		fElements = new HuffmanLeaf<T>( *(lSet.begin()) );	
	}
	else
	{
		// we simply assume 2 or more
		HuffmanNode<T>* lElements = new HuffmanNode<T>( NULL, NULL );
		
		for ( iter = lSet.begin(); iter != lSet.end(); ++iter )
		{
			HuffmanCode<T> lCode = *iter;
			lElements->buildSubtree( lCode, ((HuffmanBitCode)lCode.getCode()).begin() );
		}
		fElements = lElements;
	}
}

template <class T>
IHuffmanElement<T>* HuffmanTree<T>::getNodes() const
{
	return fElements;	
}

template <class T>
int HuffmanTree<T>::getDegree() const
{
	if ( fElements )
		return fElements->getDegree();
	else
		return 0;	
}

template <class T>
long HuffmanTree<T>::getNumberOfCharacters() const
{
	return fNumberOfCharacters;	
}

template <class T>
int HuffmanTree<T>::getEffectiveRatio() const
{
 	long lOldSize = fElements->getFrequency() * (8 * sizeof(T));
 	long lNewSize = fElements->getDataSize();
 	long lDictSize = (fElements->getDictionarySize() + 8 + sizeof(long) + (2 * sizeof(int))) * 8;

 	return ((lOldSize-(lNewSize+lDictSize))*100)/lOldSize;
}

template <class T>
ostream& operator<<( ostream& aOS, const HuffmanTree<T>* aTree )
{
	HuffmanTree<T>* lTree = (HuffmanTree<T>*)aTree;
	
	aOS << lTree->getNodes();
	return aOS;
}

////////////////////////////////////////////////////////////////////////////////////
// HuffmanCharacter

template <class T>
bool HuffmanCharacter<T>::read( istream& aIS, T& aValue )
{
	typename HuffmanCharacter<T>::character lValue;
	
	aIS.read( (char*)lValue.field2, sizeof( T ) );
	aValue = lValue.field1;
	
	return aIS.good();
}

template <class T>
bool HuffmanCharacter<T>::write( ostream& aOS, T aValue )
{
	typename HuffmanCharacter<T>::character lValue;
	
	lValue.field1 = aValue;
	aOS.write( (char*)lValue.field2, sizeof( T ) );
	
	return aOS.good();
}

////////////////////////////////////////////////////////////////////////////////////
// Huffman<T>

template <class T>
void Huffman<T>::compress( string aFileName )
{
  	ifstream lReader;
  	ofstream lOutput;

  	lReader.open( aFileName.c_str(), iostream::binary );
  	if ( lReader.fail() )
    	throw HuffmanException( "Cannot open file \'" + aFileName + "\'." );

	string lOutName( aFileName );
  	lOutName += ".huff";
  	lOutput.open( lOutName.c_str(), iostream::binary );
  	if ( lOutput.fail() )
    	throw HuffmanException( "Cannot open output file \'" + lOutName + "\'." );

  	cout << "Compressing \'" << aFileName << "\':" << endl;

 	HuffmanTree<T> lTree;
	lTree.compressStream( lOutput, lReader );

	lReader.close();
	lOutput.close();
}

template <class T>
void Huffman<T>::uncompress( string aFileName )
{
  	ifstream lReader;
  	ofstream lOutput;

  	lReader.open( aFileName.c_str(), iostream::binary );
  	if ( lReader.fail() )
    	throw HuffmanException( "Cannot open file \'" + aFileName + "\'." );

	if ( (aFileName.size() < 6) ||
		 (aFileName.substr( aFileName.size() - 5) != ".huff") )
	{
		stringstream lSS;
		
		lSS << "File \'" << aFileName << ".huff\' required.";  
		throw HuffmanException( lSS.str() );
	}
	string lOutName( aFileName.substr( 0, aFileName.size() - 5 ) );
  	lOutput.open( lOutName.c_str(), iostream::binary );
  	if ( lOutput.fail() )
    	throw HuffmanException( "Cannot open output file \'" + lOutName + "\'." );

  	cout << "Uncompressing \'" << aFileName << "\' to \'" << lOutName << "\':" << endl;
 
 	HuffmanTree<T> lTree;
	lTree.uncompressStream( lOutput, lReader );

	lReader.close();
	lOutput.close();
}

////////////////////////////////////////////////////////////////////////////////////
// BitStreamWriter

void BitStreamWriter::init()
{
	for ( int i = 0; i < 32; i++ )
		fBuffer[i] = 0;
	fByteIndex = 0;
	fBitIndex = 8;	
}

BitStreamWriter::BitStreamWriter( ostream& aOS ) : fOS(aOS)
{
	init();		
}
	
void BitStreamWriter::writeBits( HuffmanBitCode& aBits )
{
	int lLength = aBits.size();

	for ( int i = 0; i < lLength; i++ )
	{
		if ( aBits[i] )
			fBuffer[fByteIndex] += 1 << (fBitIndex - 1);
		fBitIndex--;
		
		
		if ( fBitIndex == 0 )
		{
			if ( fByteIndex == 31 )
			{
				finish();
				init();
			}
			else
			{
				fByteIndex++;
				fBitIndex = 8;	
			}
		}
	}
}

void BitStreamWriter::finish()
{
	fOS.write( (char*)fBuffer, fByteIndex + 1 );	
}

////////////////////////////////////////////////////////////////////////////////////
// BitStreamReader

template <class T>
void BitStreamReader<T>::init()
{
	for ( int i = 0; i < 32; i++ )
		fBuffer[i] = 0;
	fByteIndex = 0;
	fBitIndex = 8;
	
	fIS.read( (char*)fBuffer, 32 );
	fLastRead = fIS.gcount();
}
	
template <class T>
BitStreamReader<T>::BitStreamReader( istream& aIS, HuffmanTree<T>* aTree ) : fIS(aIS)
{
	fTree = aTree->getNodes();
	fNumberOfCharacters = aTree->getNumberOfCharacters();
	init();
}
	
template <class T>
bool BitStreamReader<T>::getCharacter( T& aCharacter )
{
	if ( fNumberOfCharacters != 0 )
	{
		HuffmanBitCode lCode;
		
		if ( fLastRead == 0 )
			throw HuffmanException( "Input stream too short!" );
	
		T lCharacter = 0;
		IHuffmanElement<T>* lPToNode = fTree;

		for ( ; ; )
		{
			int lMove = 0;
			lMove = fBuffer[fByteIndex] & (1 << (fBitIndex - 1));
			if ( lMove )
				lCode.add1();
			else
				lCode.add0();

			// move bit pointer
			fBitIndex--;
			if ( fBitIndex == 0 )
			{
				if ( fByteIndex == 31 )
					init();
				else
				{
					fByteIndex++;
					fBitIndex = 8;	
				}
			}
			
			// check for Leave (only one code!) [SECURITY]
			if ( typeid(*lPToNode) == typeid(HuffmanLeaf<T>) )
			{
				lCharacter = ((HuffmanLeaf<T>*)lPToNode)->getCharacter();
				aCharacter = lCharacter;
				break;	
			}
			
			// lPToNode points to a node
			if ( lMove )
				lPToNode = ((HuffmanNode<T>*)lPToNode)->getRight();	
			else
				lPToNode = ((HuffmanNode<T>*)lPToNode)->getLeft();	

			// Have we read a complete code?
			if ( typeid(*lPToNode) == typeid(HuffmanLeaf<T>) )
			{
				lCharacter = ((HuffmanLeaf<T>*)lPToNode)->getCharacter();
				aCharacter = lCharacter;
				break;	
			}
		}
		
		fNumberOfCharacters--;
		return true;
	}

	return false;
}