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:

## 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...

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...

## 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...

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...

TreeNoderemoveSmallest (std::queue< TreeNode *> &singleQueue, std::queue< TreeNode *> &mergeQueue)
Helper function: finds the smallest element on the two queues and removes it. 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...

## 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.

Date
Summer 2012

## ◆ HuffmanTree() [1/3]

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

Creates a HuffmanTree from a given set of Frequency objects.

Parameters
 frequencies The 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
 bfile The binary file to read our compressed tree information from

## ◆ HuffmanTree() [3/3]

 HuffmanTree::HuffmanTree ( const HuffmanTree & other )

Copy constructor for Huffman Trees.

Parameters
 other The HuffmanTree to copy.

## ◆ ~HuffmanTree()

 HuffmanTree::~HuffmanTree ( )

Destructor for Huffman Trees.

## ◆ operator=()

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

Assignment operator for HuffmanTree.

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

## ◆ decodeFile()

 string HuffmanTree::decodeFile ( BinaryFileReader & bfile )

Decodes a given file into its string contents.

Parameters
Returns
The decoded contents of the file.

## ◆ 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
 data The string to be written. bfile The 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
 c The character to be written. bfile The 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
 bfile The binary file to be written to.

## ◆ printInOrder() [1/2]

 void HuffmanTree::printInOrder ( ) const

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

## ◆ print()

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

Prints the tree to a stream.

Parameters
 out The stream to print to

## ◆ copy() [1/2]

 void HuffmanTree::copy ( const HuffmanTree & other )
private

Private helper function that copies another HuffmanTree.

Parameters
 other The 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
 current The root of the subtree in the other HuffmanTree to be copied.
Returns
A pointer to the root of the new, copied subtree.

## ◆ clear()

 void HuffmanTree::clear ( TreeNode * current )
private

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

Parameters
 current The root of the subtree to free data from.

## ◆ 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
 frequencies The set of Frequency objects to build the tree with.
Todo:

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!

 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
 bfile The binary file we are reading.
Returns
A pointer to the root of the subtree built.
Todo:

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.

## ◆ 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
 current The current node we are visiting. path The current path we have taken to get to this node. Used to store the encoded value for the characters of the tree.

## ◆ printInOrder() [2/2]

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

Private helper for printing a tree in order.

Parameters
 current The current subRoot

## ◆ removeSmallest()

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

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
 singleQueue The first queue to inspect. mergeQueue The second queue to inspect.
Returns
A pointer to the smallest TreeNode that used to be at the front of one of the queues.
Todo:

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.

## ◆ getBitsForChar()

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

Determines the encoded value for a given character.

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

## ◆ 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
 ss The stringstream being used to build the decoded output string. bfile The binary file we are decoding.
Todo:

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.

## ◆ 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
 current The root of the subtree we are currently writing. bfile The fiel we are writing to.
Todo:

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.

## ◆ height()

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

Private helper to get the height of the HuffmanTree.

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

## ◆ _max_print_height

 const int HuffmanTree::_max_print_height = 9
staticprivate

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

## ◆ root

 TreeNode* HuffmanTree::root
private

Root of the HuffmanTree.

## ◆ bitsMap

 std::map > HuffmanTree::bitsMap
private

Standard map that maps characters to their encoded values.

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