lab_huffman
Hazardous Huffman Codes
HuffmanTree Class Reference

HuffmanTree: class that represents a Huffman tree for encoding and decoding files with Huffman coding. More...

#include <huffman_tree.h>

Collaboration diagram for HuffmanTree:
[legend]

Classes

class  TreeNode
 TreeNode class: internal representation of the Huffman tree. More...
 

Public Member Functions

 HuffmanTree (std::vector< Frequency > frequencies)
 Creates a HuffmanTree from a given set of Frequency objects. More...
 
 HuffmanTree (BinaryFileReader &bfile)
 Creates a HuffmanTree from a binary file that has been written to compress the tree information. More...
 
 HuffmanTree (const HuffmanTree &other)
 Copy constructor for Huffman Trees. More...
 
 ~HuffmanTree ()
 Destructor for Huffman Trees. More...
 
const HuffmanTreeoperator= (const HuffmanTree &rhs)
 Assignment operator for HuffmanTree. More...
 
std::string decodeFile (BinaryFileReader &bfile)
 Decodes a given file into its string contents. More...
 
void writeToFile (const std::string &data, BinaryFileWriter &bfile)
 Writes a string of data to the binary file using Huffman coding. More...
 
void writeToFile (char c, BinaryFileWriter &bfile)
 Writes a signle character to the binary file using Huffman coding. More...
 
void writeTree (BinaryFileWriter &bfile)
 Writes a compressed version of the tree to the file. More...
 
void printInOrder () const
 Prints each element in the tree in an in-order traversal. More...
 
void print (std::ostream &out) const
 Prints the tree to a stream. More...
 

Static Public Member Functions

static Frequency testRemoveSmallest (std::vector< Frequency > single, std::vector< Frequency > merge)
 Test function for removeSmallest, function is meant to called for testing purposes to make sure that removeSmallest is working correctly. More...
 

Private Member Functions

void copy (const HuffmanTree &other)
 Private helper function that copies another HuffmanTree. More...
 
TreeNodecopy (const TreeNode *current)
 Recursive, private helper function that copies a given subtree of another HuffmanTree. More...
 
void clear (TreeNode *current)
 Recursive, private helper function that frees all memory associated with a subtree of the HuffmanTree. More...
 
void buildTree (const std::vector< Frequency > &frequencies)
 Helper function used by the constructor to build a HuffmanTree for a collection of Frequency data. More...
 
TreeNodereadTree (BinaryFileReader &bfile)
 Helper function used by the constructor to build a HuffmanTree from a compressed version of the tree written in a binary file. More...
 
void buildMap (TreeNode *current, std::vector< bool > &path)
 Recursive helper function used by the constructor to build a map of characters to their encoded values based on the tree structure built. More...
 
void printInOrder (const TreeNode *current) const
 Private helper for printing a tree in order. More...
 
std::vector< bool > getBitsForChar (char c)
 Determines the encoded value for a given character. More...
 
void decode (std::stringstream &ss, BinaryFileReader &bfile)
 Helper function that decodes a file by traversing the tree based on the bits read. More...
 
void writeTree (TreeNode *current, BinaryFileWriter &bfile)
 Helper function to write the tree out to a binary file in a compressed way. More...
 
int height (const TreeNode *subRoot) const
 Private helper to get the height of the HuffmanTree. More...
 

Static Private Member Functions

static TreeNoderemoveSmallest (std::queue< TreeNode * > &singleQueue, std::queue< TreeNode * > &mergeQueue)
 Helper function: finds the smallest element on the two queues and removes it. More...
 

Private Attributes

TreeNoderoot_
 Root of the HuffmanTree. More...
 
std::map< char, std::vector< bool > > bitsMap_
 Standard map that maps characters to their encoded values. More...
 

Static Private Attributes

static const int _max_print_height = 9
 Maximum height of trees to enable printing for (chosen by fair dice roll) More...
 

Detailed Description

HuffmanTree: class that represents a Huffman tree for encoding and decoding files with Huffman coding.

Constructor & Destructor Documentation

◆ HuffmanTree() [1/3]

HuffmanTree::HuffmanTree ( std::vector< Frequency frequencies)

Creates a HuffmanTree from a given set of Frequency objects.

Parameters
frequenciesThe Frequency objects for this tree.

◆ HuffmanTree() [2/3]

HuffmanTree::HuffmanTree ( BinaryFileReader bfile)

Creates a HuffmanTree from a binary file that has been written to compress the tree information.

Parameters
bfileThe binary file to read our compressed tree information from

◆ HuffmanTree() [3/3]

HuffmanTree::HuffmanTree ( const HuffmanTree other)

Copy constructor for Huffman Trees.

Parameters
otherThe HuffmanTree to copy.

◆ ~HuffmanTree()

HuffmanTree::~HuffmanTree ( )

Destructor for Huffman Trees.

Member Function Documentation

◆ buildMap()

void HuffmanTree::buildMap ( TreeNode current,
std::vector< bool > &  path 
)
private

Recursive helper function used by the constructor to build a map of characters to their encoded values based on the tree structure built.

Parameters
currentThe current node we are visiting.
pathThe current path we have taken to get to this node. Used to store the encoded value for the characters of the tree.

◆ buildTree()

void HuffmanTree::buildTree ( const std::vector< Frequency > &  frequencies)
private

Helper function used by the constructor to build a HuffmanTree for a collection of Frequency data.

Each Frequency object represents a character and how often it appears in the data to be encoded.

Parameters
frequenciesThe set of Frequency objects to build the tree with.
Todo:
Your code here!

First, place all of the leaf nodes into the singleQueue in increasing order of frequency. Note: frequencies is already sorted for you.

Next, until there is only one node on the two queues (that is, one of the queues is empty and one has a single node), remove the two smallest entries from the two queues. Then, create a new internal node with these nodes as children, whose frequency is the sum of these two children's frequencies. Place the new internal node onto the back of the mergeQueue.

Finally, when there is a single node left, it is the root. Assign it to the root and you're done!

◆ clear()

void HuffmanTree::clear ( TreeNode current)
private

Recursive, private helper function that frees all memory associated with a subtree of the HuffmanTree.

Parameters
currentThe root of the subtree to free data from.

◆ copy() [1/2]

void HuffmanTree::copy ( const HuffmanTree other)
private

Private helper function that copies another HuffmanTree.

Parameters
otherThe HuffmanTree to be copied.

◆ copy() [2/2]

HuffmanTree::TreeNode * HuffmanTree::copy ( const TreeNode current)
private

Recursive, private helper function that copies a given subtree of another HuffmanTree.

Parameters
currentThe root of the subtree in the other HuffmanTree to be copied.
Returns
A pointer to the root of the new, copied subtree.

◆ decode()

void HuffmanTree::decode ( std::stringstream ss,
BinaryFileReader bfile 
)
private

Helper function that decodes a file by traversing the tree based on the bits read.

Parameters
ssThe stringstream being used to build the decoded output string.
bfileThe binary file we are decoding.
Todo:
Your code here!

This code is reading in all of the bits in the binary file given. After reading a bit, we go left if the bit was a 0 (or false), and we go right if the bit was a 1 (or true).

Special case: if we are at a leaf node, we should "print" its character to the stringstream (with operator<<, just like cout) and start traversing from the root node again.

◆ decodeFile()

string HuffmanTree::decodeFile ( BinaryFileReader bfile)

Decodes a given file into its string contents.

Parameters
bfileBinaryFileReader to read bits from.
Returns
The decoded contents of the file.

◆ getBitsForChar()

vector< bool > HuffmanTree::getBitsForChar ( char  c)
private

Determines the encoded value for a given character.

Parameters
cThe character to find the encoded value for.
Returns
The encoded value for that character.

◆ height()

int HuffmanTree::height ( const TreeNode subRoot) const
private

Private helper to get the height of the HuffmanTree.

Parameters
subRootWhere we're currently at.
Returns
the height of the tree

◆ operator=()

const HuffmanTree & HuffmanTree::operator= ( const HuffmanTree rhs)

Assignment operator for HuffmanTree.

Parameters
rhsThe right hand side of the assignment statement.
Returns
A reference for performing chained assignments.

◆ print()

void HuffmanTree::print ( std::ostream out) const

Prints the tree to a stream.

Parameters
outThe stream to print to

◆ printInOrder() [1/2]

void HuffmanTree::printInOrder ( ) const

Prints each element in the tree in an in-order traversal.

◆ printInOrder() [2/2]

void HuffmanTree::printInOrder ( const TreeNode current) const
private

Private helper for printing a tree in order.

Parameters
currentThe current subRoot

◆ readTree()

HuffmanTree::TreeNode * HuffmanTree::readTree ( BinaryFileReader bfile)
private

Helper function used by the constructor to build a HuffmanTree from a compressed version of the tree written in a binary file.

Parameters
bfileThe binary file we are reading.
Returns
A pointer to the root of the subtree built.
Todo:
Your code here!

This code is reading a HuffanTree in from a file in the format that we wrote it above. The strategy, then, is as follows:

  1. If the file has no more bits, we're done.
  2. If we read a 1 bit, we are a leaf node: create a new TreeNode with the character that is the next byte in the file (its frequency should be 0, since we are ignoring frequency data now).
  3. If we read a 0 bit, create a new internal node (with frequency 0, since we are ignoring them now, and set its left child and right children to be the subtrees built recursively.
  4. Your function should return the TreeNode it creates, or NULL if it did not create one.

◆ removeSmallest()

HuffmanTree::TreeNode * HuffmanTree::removeSmallest ( std::queue< TreeNode * > &  singleQueue,
std::queue< TreeNode * > &  mergeQueue 
)
staticprivate

Helper function: finds the smallest element on the two queues and removes it.

In the event that there is a tie, it should remove the front of the singleQueue.

Parameters
singleQueueThe first queue to inspect.
mergeQueueThe second queue to inspect.
Returns
A pointer to the smallest TreeNode that used to be at the front of one of the queues.
Todo:
Your code here!

Remove the smallest TreeNode * from the two queues given as parameters. The entries on the queues are in sorted order, so the smaller of the two queues heads is the smallest item in either of the queues. Return this item after removing it from its queue.

◆ testRemoveSmallest()

Frequency HuffmanTree::testRemoveSmallest ( std::vector< Frequency single,
std::vector< Frequency merge 
)
static

Test function for removeSmallest, function is meant to called for testing purposes to make sure that removeSmallest is working correctly.

Parameters
singleThe first vector to inspect.
mergeThe second vector to inspect.
Returns
The smallest frequency from both vectors.

◆ writeToFile() [1/2]

void HuffmanTree::writeToFile ( const std::string data,
BinaryFileWriter bfile 
)

Writes a string of data to the binary file using Huffman coding.

Parameters
dataThe string to be written.
bfileThe binary file to write the string to.

◆ writeToFile() [2/2]

void HuffmanTree::writeToFile ( char  c,
BinaryFileWriter bfile 
)

Writes a signle character to the binary file using Huffman coding.

Parameters
cThe character to be written.
bfileThe binary file to write the character to.

◆ writeTree() [1/2]

void HuffmanTree::writeTree ( BinaryFileWriter bfile)

Writes a compressed version of the tree to the file.

Parameters
bfileThe binary file to be written to.

◆ writeTree() [2/2]

void HuffmanTree::writeTree ( TreeNode current,
BinaryFileWriter bfile 
)
private

Helper function to write the tree out to a binary file in a compressed way.

Parameters
currentThe root of the subtree we are currently writing.
bfileThe fiel we are writing to.
Todo:
Your code here!

This code is writing the current HuffmanTree in a compressed format to the given BinaryFileWriter. The strategy for doing so is as follows:

  1. If we are a leaf node, write the bit "1" followed by the byte that is the character of this node.
  2. If we are an internal node, writ the bit "0", and then encode the left and right subtree, recursively.

Note that we don't encode the frequencies in this compressed version: this is fine, as the structure of the tree still reflects what the relative frequencies were.

Member Data Documentation

◆ _max_print_height

const int HuffmanTree::_max_print_height = 9
staticprivate

Maximum height of trees to enable printing for (chosen by fair dice roll)

◆ bitsMap_

std::map<char, std::vector<bool> > HuffmanTree::bitsMap_
private

Standard map that maps characters to their encoded values.

◆ root_

TreeNode* HuffmanTree::root_
private

Root of the HuffmanTree.


The documentation for this class was generated from the following files: