#ifndef _HUFFMAN_TREE_H_
#define _HUFFMAN_TREE_H_
#include "HuffmanTreeNode.h"
#include <ostream>
#include <vector>
using namespace std;
class HuffmanTree
{
public:
/*
Purpose: constructs
a HuffmanTree from a vector of HuffmanTreeNodePtrs that point to
HuffmanTreeNodes
Preconditon: a
vector of HuffmanTreeNodes, InVectorOfNodes, must be passed
Postcondition: a
HuffmanTree will now exist, created from the nodes in the vector, the vector
will be cleared when the method completes
*/
HuffmanTree(vector<HuffmanTreeNodePtr>
& InVectorOfNodes);
/*
Purpose:
constructs a HuffmanTree from an existing HuffmanTree
Preconditon:
a HuffmanTree, InHufmanTreeToCopy, must be passed
Postcondition:
a HuffmanTree will now exist, created from an existing HuffmanTree
*/
HuffmanTree(const
HuffmanTree & InHuffmanTreeToCopy);
/*
Purpose:
destroys a HuffmanTree
Preconditon:
none
Postcondition:
none
*/
~HuffmanTree();
/*
Purpose: prints the
the binary code for each character stored in a leaf HuffmanTreeNode in the
HuffmanTree
Preconditon:
a output stream, InOS, for which to print to, must be passed
Postcondition:
none
*/
void
PrintCode(ostream & InOS);
/*
Purpose: decodes a
stream of "binary data" - a stream of characters 1 and 0, into a
stream of characters decoded from the HuffmanTree
Preconditon: an
input stream, InInputStream must be passed which contains the binary data, the
ouptut stream which will be used to output the decoded text
Postcondition:
none
*/
void DecodeAndPrint(istream
& InInputStream, ostream & InOutputStream);
//---------------------------------------------
//
global freind methods for use with vector of HuffmanTreeNodePtr,
vector<HuffmanTreeNodePtr>
//---------------------------------------------
/*
Purpose: removes a
HuffmanTreeNode from the front of the vector of HuffmanTreeNodePtr,
vector<HuffmanTreeNodePtr>
Preconditon:
a vector of HuffmantreeNodePtr, InVectorOfNodes, must be passed
Postcondition:
none
*/
friend void
RemoveFromFrontInVector(vector<HuffmanTreeNodePtr> &
InVectorOfNodes);
/*
Purpose: removes a
HuffmanTreeNode from the end of the vector of HuffmanTreeNodePtr,
vector<HuffmanTreeNodePtr>
Preconditon:
a vector of HuffmantreeNodePtr, InVectorOfNodes, must be passed
Postcondition:
none
*/
friend void
RemoveFromEndInVector(vector<HuffmanTreeNodePtr> & InVectorOfNodes);
/*
Purpose: inserts a
HuffmanTreeNode at the end of the vector of HuffmanTreeNodePtr,
vector<HuffmanTreeNodePtr>
Preconditon: a
vector of HuffmantreeNodePtr, InVectorOfNodes, must be passed, and the
HuffmanTreeNode to insert, InNewNode, must be passed
Postcondition:
none
*/
friend void
InsertAtEndInVector(vector<HuffmanTreeNodePtr> & InVectorOfNodes,
HuffmanTreeNodePtr InNewNode);
/*
Purpose: inserts a
HuffmanTreeNode at the front of the vector of HuffmanTreeNodePtr,
vector<HuffmanTreeNodePtr>
Preconditon: a
vector of HuffmantreeNodePtr, InVectorOfNodes, must be passed, and the
HuffmanTreeNode to insert, InNewNode, must be passed
Postcondition:
none
*/
friend void
InsertAtFrontInVector(vector<HuffmanTreeNodePtr> & InVectorOfNodes,
HuffmanTreeNodePtr InNewNode);
/*
Purpose:
returns the position of a character in a HufmanTreeNodePtr vector
Preconditon: a vector of HuffmantreeNodePtr, InVectorOfNodes,
must be passed, and the char, InCharToLookFor must be passed
Postcondition:
returns an int with the position of the character in the vector, if character
is not found returns -1
*/
friend int
GetPositionOfCharInVector(vector<HuffmanTreeNodePtr> &
InVectorOfNodes, char InCharToLookFor);
private:
HuffmanTreeNodePtr
root;
/*
Purpose: prints the
the binary code for each character stored in a leaf HuffmanTreeNode in the
HuffmanTree
Preconditon: the
root of a HuffmanTree, InRoot, from which the traversing starts, must be
passed, a output stream, InOS, for which to print to, must be passed, a
variable, code, to temporarily hold the code generated from the tree must be
passed
Postcondition:
none
*/
void
PrintCode(HuffmanTreeNodePtr InRoot, /*type*/ code, ostream & InOS);
/*
Purpose: to recursively decode one character in a binary
input stream (consisting solely of 1's and 0's)
Preconditon: the
root of a HuffmanTree, InRoot, from which the traversing starts, must be
passed, an input stream, InInputStream must be passed which contains the binary
data, the ouptut stream which will be used to output the decoded text
Postcondition:
InInputStream will contain fewer bits; one character will be added to InOutputStream
*/
void
DecodeAndPrint(HuffmanTreeNodePtr InRoot, istream & InInputStream, ostream
& InOutputStream);
/*
Purpose:
to dealocate and delete all HuffmanTreeNodes in HuffmanTree
Precondition:
the root of the tree to be deleted must be passed
Postcondition:
none
*/
void
ClearTree( HuffmanTreeNodePtr InRoot);
/*
Purpose:
copies an existing HuffmanTree and returns a pointer to the copied HuffmanTree
Preconditon:
The root of the HuffmanTree to be copied, InRoot, must be passed
Postcondition:
a HuffmanTreeNodePtr to the new HuffmanTrees root must be passed
*/
HuffmanTreeNodePtr
CopyTree( HuffmanTreeNodePtr InRoot);
/*
Purpose: Builds the
HuffmanTree from a vector of HuffmanTreeNodePtr where every parent
HuffmanTreeNode contains the sum of frequenices of its children and all leaves
of the tree are the HuffmanTreeNodes from the vector of HuffmanTreeNodePtr
Preconditon:
a vector of HuffmantreeNodePtr, InVectorOfNodes, must be passed
Postcondition:
none
*/
void
BuildHuffmanTree(vector<HuffmanTreeNodePtr> & InVectorOfNodes);
/*
Purpose:
Merges the two smallest HuffmanTreeNodes in the vector, by creating a new
parent for them that will contain the sum of their frequencies
Preconditon:
a vector of HuffmantreeNodePtr, InVectorOfNodes, must be passed; it will be sorted in ascending order by
frequency
Postcondition:
the two nodes with the smallest frequencies will be removed and in their place there will be one node with the removed nodes as children and
whose frequency will be the sum of the frequencies of the two removed nodes
*/
void
MergeTwoSmallestIntoSubtree(vector<HuffmanTreeNodePtr> &
InVectorOfNodes);
/*
Purpose:
sorts the HuffmanTreeNodes pointed to by vector of HuffmanTreeNodePtr, by
frequency
Precondition:
a vector of HuffmantreeNodePtr, InVectorOfNodes, must be passed
Postcondition:
none
*/
void Sort(
vector<HuffmanTreeNodePtr> & InVectorOfNodes);
};
#endif