#include "HuffmanTree.h"
//--------------------------------------------------------------------
HuffmanTree::HuffmanTree(vector<HuffmanTreeNodePtr>
& InVectorOfNodes)
{
root=NULL;
BuildHuffmanTree(InVectorOfNodes);
}
//--------------------------------------------------------------------
HuffmanTree::HuffmanTree(const HuffmanTree &
InHuffmanTreeToCopy)
{
root =
CopyTree(InHuffmanTreeToCopy.root);
}
//--------------------------------------------------------------------
HuffmanTree::~HuffmanTree()
{
if(root!=NULL)
ClearTree(root);
}
//--------------------------------------------------------------------
void
HuffmanTree::ClearTree(HuffmanTreeNodePtr InRoot)
{
//recursively
delete the HuffmanTreeNodes in the HuffmanTree
}
//--------------------------------------------------------------------
HuffmanTreeNodePtr
HuffmanTree::CopyTree(HuffmanTreeNodePtr InRoot)
{
//recursively
fill the new HuffmanTree with an existing HuffmanTree
}
//--------------------------------------------------------------------
void
HuffmanTree::PrintCode(ostream & InOS)
{
/*
/*
It is recomended that you use a variable to keep track of the code
/*
you generate from the tree as you traverse. You can use whatever you
/*
are comfortable with. If you choose not to use it at all, you may
/*
modify the method not to use the variable code.
/*
/*
If you do want to use the variable code you will define /*type*/
/*
Some options are:
/*
string code; //to store a string of "1" and "0"
/*
vector<bool> code; //a vector of booleans
*/
/*type*/ code;
PrintCode(root,code,InOS);
}
//--------------------------------------------------------------------
void
HuffmanTree::PrintCode(HuffmanTreeNodePtr InRoot, /*type*/
code, ostream & InOS)
{
//recursively travesere the tree and
//print
the binary code of each HuffmanTreeNode that contains a character
}
//--------------------------------------------------------------------
void
HuffmanTree::DecodeAndPrint(istream & InInputStream,
ostream & InOutputStream)
{
while (!InInputStream.eof())
DecodeAndPrint(root,
InInputStream, InOutputStream);
}
//--------------------------------------------------------------------
void
HuffmanTree::DecodeAndPrint(HuffmanTreeNodePtr InRoot,
istream & InInputStreamToDecode, ostream & InOutputStream)
{
//recursively decode one character in the binary input stream
}
//--------------------------------------------------------------------
void
HuffmanTree::BuildHuffmanTree(vector<HuffmanTreeNodePtr>
& InVectorOfNodes)
{
//if the vector's size is 0
//the
vector has no HuffmanNodePtr from which to build the tree, return
if(InVectorOfNodes.size()==
0)
return;
//while we have more than one HuffmanTreeNodePtr in the
tree
while(InVectorOfNodes.size()
> 1)
{
//sort the vector of HuffmanTreeNodePtrs
Sort(InVectorOfNodes);
//Merge the two smallest Nodes into a subtree with a new
parent
MergeTwoSmallestIntoSubtree(InVectorOfNodes);
}
//vector now remains with one HuffmanTreeNodePtr holding
the value of our tree
root =
CopyTree(InVectorOfNodes[0]);
//we no longer need the vector, so we can now delete any
allocated HuffmanTreeNodes in it
for(int
i=0; i< InVectorOfNodes.size(); i++)
ClearTree(InVectorOfNodes[i]);
}
//--------------------------------------------------------------------
void
HuffmanTree::MergeTwoSmallestIntoSubtree(vector<HuffmanTreeNodePtr>
& InVectorOfNodes)
{
//get the two nodes with the smallest frequencies
//create
a new parent node with the sum of the frequencies
//make
the smallest frequencies children of the new parent
//remove
children from the vector
//insert
the new parent into the vector
//note:
parent will now contain a subtree with two smallest children
}
//--------------------------------------------------------------------
void
HuffmanTree::Sort(vector<HuffmanTreeNodePtr> &
InVectorOfNodes)
{
bool
sorted=false;
int
lastIndex = InVectorOfNodes.size()-1;
for(int
pass=1; pass <= lastIndex && !sorted; pass++)
{
sorted=true;
for(int
index=0; index<=lastIndex-pass; ++index)
{
int
nextIndex = index+1;
//if frequency if a HuffmanTreeNode is greater than than
the frequency of the next one
if(InVectorOfNodes[index]->GetFrequency()
> InVectorOfNodes[nextIndex]->GetFrequency())
{
swap(InVectorOfNodes[index],
InVectorOfNodes[nextIndex]);
sorted=false;
}
//if the frequencies are the same, put the one lowest
alphabetically first
if(InVectorOfNodes[index]->GetFrequency()
== InVectorOfNodes[nextIndex]->GetFrequency())
if(InVectorOfNodes[index]->GetCharacter()
> InVectorOfNodes[nextIndex]->GetCharacter())
swap(InVectorOfNodes[index],
InVectorOfNodes[nextIndex]);
}
}
}
//--------------------------------------------------------------------
//FRIEND METHODS
//--------------------------------------------------------------------
void
RemoveFromFrontInVector(vector<HuffmanTreeNodePtr> & InVectorOfNodes)
{
if(InVectorOfNodes.size()
== 0)
return;
else
{
InVectorOfNodes.erase(InVectorOfNodes.begin());
}
}
//--------------------------------------------------------------------
void RemoveFromEndInVector(vector<HuffmanTreeNodePtr>
& InVectorOfNodes)
{
InVectorOfNodes.pop_back();
}
//--------------------------------------------------------------------
void InsertAtEndInVector( vector<HuffmanTreeNodePtr>
& InVectorOfNodes,HuffmanTreeNodePtr InNewNode)
{
InVectorOfNodes.push_back(InNewNode);
}
//--------------------------------------------------------------------
void InsertAtFrontInVector( vector<HuffmanTreeNodePtr>
& InVectorOfNodes, HuffmanTreeNodePtr InNewNode)
{
InVectorOfNodes.insert(InVectorOfNodes.begin(),InNewNode);
}
//--------------------------------------------------------------------
int
GetPositionOfCharInVector(vector<HuffmanTreeNodePtr> &
InVectorOfNodes, char InCharToLookFor)
{
for(int
i=0; i < InVectorOfNodes.size(); i++)
{
if(InVectorOfNodes[i]->GetCharacter()
== InCharToLookFor)
return
i;
}
return -1; //to signal character was not found
}
//--------------------------------------------------------------------