// Heap.h
#ifndef HEAP_H
#define HEAP_H


//////////////////////////////////////////////////////////////////////////
//                                                                      //
// CLASS NAME:  Heap                                                    //
//                                                                      //
// DESCRIPTION: -Stores up to N items of type T.                        //
//              -Allows adding an item or extracting the best item.     //
//              -Supported operations are accomplished at O(log(n)),    //
//               where n is the current number of items in the heap.    //
//                                                                      //
// REMARKS:     1) T is determined at declaration.                      //
//              2) N is determined at initialization.                   //
//              3) The meaning of "best", either minimal or maximal,    //
//                 is determined at declaration.                        //
//                 In order to support Heap<MIN,T> and Heap<MAX,T>,     //
//                 one of the following options must be viable:         //
//                 1. bool operator<(T,T) and bool operator>(T,T).      //
//                 2. bool T::operator<(T) and bool T::operator>(T).    //
//                 3. T::operator P(), where P is a type, for which     //
//                    one of the above options is viable.               //
//                                                                      //
// AUTHOR:      Barak Manos (barrak_manos@yahoo.com)                    //
//                                                                      //
//////////////////////////////////////////////////////////////////////////


#define MIN_TYPE  0
#define MAX_TYPE ~0


template<int TYPE,class ITEM>
class Heap
{
public:
	Heap(int iMaxNumOfItems);
	~Heap();

	bool AddItem(ITEM*  pItem);
	bool GetBest(ITEM** pItem);
protected:
	int  BestOfTwo(int i,int j);
	void SwapItems(int i,int j);

	ITEM** m_aItems;
	int    m_iMaxNumOfItems;
	int    m_iCurrNumOfItems;
};

#endif

// Heap.cpp
#include "Root.h"
#include "Heap.h"


//Template class - Implementation is in the header file...

template<int TYPE,class ITEM>
Heap<TYPE,ITEM>::Heap(int iMaxNumOfItems)
{
	m_iCurrNumOfItems=0;
	m_iMaxNumOfItems=iMaxNumOfItems;
	m_aItems=new ITEM*[m_iMaxNumOfItems];
}


template<int TYPE,class ITEM>
Heap<TYPE,ITEM>::~Heap()
{
	delete[] m_aItems;
}


template<int TYPE,class ITEM>
bool Heap<TYPE,ITEM>::AddItem(ITEM* pItem)
{
	if (m_iCurrNumOfItems==m_iMaxNumOfItems)
		return false;

	m_aItems[m_iCurrNumOfItems]=pItem;

	for (int i=m_iCurrNumOfItems,j=(i+1)/2-1; j>=0; i=j,j=(i+1)/2-1)
	{
		if (BestOfTwo(i,j)==i)
			SwapItems(i,j);
		else
			break;
	}

	m_iCurrNumOfItems++;

	return true;
}


template<int TYPE,class ITEM>
bool Heap<TYPE,ITEM>::GetBest(ITEM** pItem)
{
	if (m_iCurrNumOfItems==0)
		return false;

	m_iCurrNumOfItems--;

	*pItem=m_aItems[0];
	m_aItems[0]=m_aItems[m_iCurrNumOfItems];

	for (int i=0,j=(i+1)*2-1; j<m_iCurrNumOfItems; i=j,j=(i+1)*2-1)
	{
		if (j+1<m_iCurrNumOfItems)
			j=BestOfTwo(j,j+1);
		if (BestOfTwo(i,j)==j)
			SwapItems(i,j);
		else
			break;
	}

	return true;
}


template<int TYPE,class ITEM>
int Heap<TYPE,ITEM>::BestOfTwo(int i,int j)
{
	switch (TYPE)
	{
	case MIN_TYPE:
		return *m_aItems[i]<*m_aItems[j]? i:j;
	case MAX_TYPE:
		return *m_aItems[i]>*m_aItems[j]? i:j;
	}
	return -1;
}


template<int TYPE,class ITEM>
void Heap<TYPE,ITEM>::SwapItems(int i,int j)
{
	ITEM* pTemp=m_aItems[i];
	m_aItems[i]=m_aItems[j];
	m_aItems[j]=pTemp;
}

// Tree.h
#ifndef TREE_H
#define TREE_H

class Tree
{
public:
	Tree(Info* pInfo);
	~Tree();

	Node** GetLeaves();
	Node*  GetRoot();
private:
	void CreateLeaves();
	void CreateRoot();

	void DestroyLeaves();
	void DestroyRoot();

	Node** m_aLeaves;
	Node*  m_pRoot;

	Info*                m_pInfo;
	Heap<MIN_TYPE,Node>* m_pHeap;
};


#endif

// Tree.cpp
#include "Root.h"
#include "Leaf.h"
#include "Info.h"
#include "Node.h"
#include "Heap.h"
#include "Tree.h"


Tree::Tree(Info* pInfo)
{
	m_pInfo=pInfo;
	m_pHeap=new Heap<MIN_TYPE,Node>(m_pInfo->NumOfSymbols());

	CreateLeaves();
	CreateRoot();

	delete m_pHeap;
}


Tree::~Tree()
{
	DestroyLeaves();
	DestroyRoot();
}


Node** Tree::GetLeaves()
{
	return m_aLeaves;
}


Node* Tree::GetRoot()
{
	return m_pRoot;
}


void Tree::CreateLeaves()
{
	int* aSymbolVector=m_pInfo->SymbolVector();
	int* aSymCntVector=m_pInfo->SymCntVector();

	m_aLeaves=new Node*[m_pInfo->SymbolsRange()];
	for (int i=0; i<m_pInfo->NumOfSymbols(); i++)
	{
		m_aLeaves[aSymbolVector[i]]=new Node(aSymbolVector[i],NO_NODE);
		(int&)(*m_aLeaves[aSymbolVector[i]])=aSymCntVector[i];
		m_pHeap->AddItem(m_aLeaves[aSymbolVector[i]]);
	}
}


void Tree::CreateRoot()
{
	Node* pChild0;
	Node* pChild1;

	for (int i=0; i<m_pInfo->NumOfSymbols()-1; i++)
	{
		m_pHeap->GetBest(&pChild0);
		m_pHeap->GetBest(&pChild1);
		m_pHeap->AddItem(new Node(pChild0,pChild1));
	}
	m_pHeap->GetBest(&m_pRoot);
}


void Tree::DestroyLeaves()
{
	delete[] m_aLeaves;
}


void Tree::DestroyRoot()
{
	Node* pParent;
	if (m_pRoot!=NO_NODE)
	{
		pParent=m_pRoot;
		m_pRoot=pParent->Child0();
		DestroyRoot();
		m_pRoot=pParent->Child1();
		DestroyRoot();
		delete pParent;
	}
}

/*
The result:
$ make
g++ -Wall -O2   -c -o Heap.o Heap.cpp
g++ -Wall -O2   -c -o Node.o Node.cpp
g++ -Wall -O2   -c -o Info.o Info.cpp
g++ -Wall -O2   -c -o Tree.o Tree.cpp
g++ -Wall -O2   -c -o FileReader.o FileReader.cpp
g++ -Wall -O2   -c -o FileWriter.o FileWriter.cpp
g++ -Wall -O2   -c -o Encoder.o Encoder.cpp
g++ -Wall -O2   -c -o Decoder.o Decoder.cpp
g++ -Wall -O2   -c -o Main.o Main.cpp
g++ Root.o Leaf.o Heap.o Node.o Info.o Tree.o FileReader.o FileWriter.o Encoder.o Decoder.o Main.o -o coompress
Tree.o: In function `Tree::CreateRoot()':
Tree.cpp:(.text+0x10a): undefined reference to `Heap<0, Node>::GetBest(Node**)'
Tree.cpp:(.text+0x116): undefined reference to `Heap<0, Node>::GetBest(Node**)'
Tree.cpp:(.text+0x144): undefined reference to `Heap<0, Node>::AddItem(Node*)'
Tree.cpp:(.text+0x162): undefined reference to `Heap<0, Node>::GetBest(Node**)'
Tree.o: In function `Tree::CreateLeaves()':
Tree.cpp:(.text+0x23e): undefined reference to `Heap<0, Node>::AddItem(Node*)'
Tree.o: In function `Tree::Tree(Info*)':
Tree.cpp:(.text+0x2b8): undefined reference to `Heap<0, Node>::Heap(int)'
Tree.cpp:(.text+0x2df): undefined reference to `Heap<0, Node>::~Heap()'
Tree.o: In function `Tree::Tree(Info*)':
Tree.cpp:(.text+0x368): undefined reference to `Heap<0, Node>::Heap(int)'
Tree.cpp:(.text+0x38f): undefined reference to `Heap<0, Node>::~Heap()'
collect2: ld returned 1 exit status
make: *** [coompress] Error 1
*/