HuffmanTree: class that represents a Huffman tree for encoding and decoding files with Huffman coding.
More...
#include "huffman_tree.h"
|
| static const int | _max_print_height = 9 |
| | Maximum height of trees to enable printing for (chosen by fair dice roll) More...
|
| |
HuffmanTree: class that represents a Huffman tree for encoding and decoding files with Huffman coding.
- Author
- Chase Geigle
- Date
- Summer 2012
◆ HuffmanTree() [1/3]
◆ HuffmanTree() [2/3]
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]
Copy constructor for Huffman Trees.
- Parameters
-
◆ ~HuffmanTree()
| HuffmanTree::~HuffmanTree |
( |
| ) |
|
Destructor for Huffman Trees.
◆ operator=()
Assignment operator for HuffmanTree.
- Parameters
-
| rhs | The right hand side of the assignment statement. |
- Returns
- A reference for performing chained assignments.
◆ decodeFile()
Decodes a given file into its string contents.
- Parameters
-
- Returns
- The decoded contents of the file.
◆ writeToFile() [1/2]
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]
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]
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()
Prints the tree to a stream.
- Parameters
-
| out | The stream to print to |
◆ copy() [1/2]
Private helper function that copies another HuffmanTree.
- Parameters
-
◆ copy() [2/2]
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()
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:
- 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!
◆ readTree()
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:
- 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:
- If the file has no more bits, we're done.
- 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).
- 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.
- Your function should return the TreeNode it creates, or NULL if it did not create one.
◆ buildMap()
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()
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:
- 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.
◆ 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()
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:
- 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.
◆ writeTree() [2/2]
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:
- 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:
- If we are a leaf node, write the bit "1" followed by the byte that is the character of this node.
- 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
◆ bitsMap
Standard map that maps characters to their encoded values.
The documentation for this class was generated from the following files:
Collaboration diagram for HuffmanTree: