rendered paste body// 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 ~0template<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_Hclass 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:$ makeg++ -Wall -O2 -c -o Heap.o Heap.cppg++ -Wall -O2 -c -o Node.o Node.cppg++ -Wall -O2 -c -o Info.o Info.cppg++ -Wall -O2 -c -o Tree.o Tree.cppg++ -Wall -O2 -c -o FileReader.o FileReader.cppg++ -Wall -O2 -c -o FileWriter.o FileWriter.cppg++ -Wall -O2 -c -o Encoder.o Encoder.cppg++ -Wall -O2 -c -o Decoder.o Decoder.cppg++ -Wall -O2 -c -o Main.o Main.cppg++ Root.o Leaf.o Heap.o Node.o Info.o Tree.o FileReader.o FileWriter.o Encoder.o Decoder.o Main.o -o coompressTree.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 statusmake: *** [coompress] Error 1*/