std::string FileName$="-1"$: unsigned int mFrequency Table $[256]=[1]$; std::vector LeafList; HuffNode Root reinterpret$\_$cast$(-1)$; std::vector mEncoding Table$[256]$;

Huffman$($const std::string& fileName$)(//1000$: Implement this method

$-$Huffman

$//1000$: Implement this method

void GenerateFrequency Table

$//$ TODO: Implement this method

void GenerateLeafList$()$

$//$ TODO: Implement this method

void GenerateTree$($

$//$ TODO: Implement this method

void GenerateEncoding Table

$//$ TODO: Implement this method

void ClearTree

$/$ TODO: Implement this method

void ClearTree $($HuffNode $\_$curr$)\{$

$//$ TODO: Implement this method

void Compress $($const char$*\_$outputFile$)(//$ TODO: Implement this method

void Decompress $($const char$*\_$outputFile$)(//$ TODO: Implement this method

Huffman Constructor

$$ Assign the appropriate data member the value from the parameter

Zero out the entire frequency table

Set the root to a value that indicates the tree is currently empty

GenerateFrequency Table

Open the file in binary mode, using a std::ifstream

Read the file one byte at a time, and increment the corresponding index The indices of the frequency table line up with the ASCII values

Close the file when complete

GenerateLeafList

Iterate through the frequency table and dynamically create a leaf node for each non$-0$ frequency

Add each node to the mLeafList vector

Generate Tree

Create the priority queue

This will be storing HuffNode in a vector, and uses HuffCompare for the comparator

Populate the priority queue with the data in the leaf list

Generate the tree with the following algorithm

While the queue has more than $1$ node

Store the top two nodes into some temporary pointers and pop them

Create a new parent node with first node as the left child, and second node as the right child

Set the parent's value to $1,$ and the frequency to the sum of its two children's frequencies

Set the first and sexond nodes parent to the newly created mode

Stunt the new node into the queue

Set the root data membes

ClearTree

$$ Perform a post$-$order traversal to delete all of the nodes

Same as Clear from the BST

Destructor

$$ Clean up all of the dynamically allocated memory $($There$\text{'}$s a method to help with this$)$

GenerateEncoding Table

Go through all of the leaf nodes and generate the bit codes

$$ This is done by traversing up the tree from each leaf node with a temporary pointer, and storing the direction in the corresponding vector

Each index of the encoding table aligns to an ASCII value

As you move up$,$ push a $0$ to the vector if you passed through a left child connection, and a $1$ if you passed through a right connection

Once you hit the root node, reverse the values in the vector

Compress

In this method, mFileName is the file to compress, and the parameter is the name of the file to

write to

Create the frequency table, leaf list, tree, and encoding table by calling the existing methods in this order$)$

Create a BitOfstream and supply it the Huffman header

Open the input file in binary mode with a std: ifstream

Compress the ble For each byte in the original file, write out the corresponding bit code from the encoding table