In this program, you will implement Huffman coding using the template PriorityQueue class from the course notes (I provide much of the code for PriorityQueue below).

Most likely you don't have much experience with implementing template classes, but we will be using them frequently in the notes.

Code of perfection

You will use (and add to) the PriorityQueue class above in order to implement Huffman codes using a supplied driver (once again, I will test with a different driver). You will write two classes HuffmanTree and HuffmanAlgorithm. The algorithm class will implement Huffman codes by storing instances of the tree class in a PriorityQueue. You will determine codes for each lower-case letter and then construct codes for words (that consist of only letters).

Recall the Huffman coding algorithm from the Module 2 lecture notes:

For each letter, create a small tree with a single node and weight (the frequency). Repeat until all nodes form a single tree: Select the two trees with the smallest weights. Merge these trees into a new tree by adding a node that is the parent of both. The weight of the new tree is the sum of the weights of the two previous trees. Assign a 0 to the left branch (lower weight) and a 1 to the other branch. 

Your HuffmanTree class should allow the following operations. (These are not directly tested by the driver, but are required for full credit.) You may have additional methods. Feel free to reuse code from Program 1. Non-leaves should store the sum of the weights of the descendant leaves.

• Constructor(s)
• Copy constructor
• Destructor
• operator= (assignment, not equality)
• operator< : This is necessary to store a HuffmanTree in the PriorityQueue. The ordering of the trees will be determined by the sum of the weights contained in the tree. If there is a tie, the then tree storing the earliest character is smaller ('a' is smaller than 'z').
• A method to traverse the tree and generate the code for each letter. The codebook can be the return value or it can be passed in/out as a parameter (I chose the latter in my implementation).
• Note: For implementing Huffman coding, it is recommended that you have a HuffmanTree constructor that combines two input HuffmanTrees into a new tree (by adding a new root node). To implement this efficiently, the new tree should "capture" the memory used in the input trees and leave the input trees empty (so that memory is not shared between different objects).

Your HuffmanAlgorithm class must store HuffmanTree objects in a PriorityQueue of the supplied class in order to implement the algorithm. Neither of your classes should use templates (only the priority queue class does this).

Another fine mess

Here are further details. First, to compile with my driver

you will need the following methods in your algorithm class:

• HuffmanAlgorithm(int (&counts)[NUM_LETTERS]) : This constructor takes the frequency for each letter from 'a' to 'z'. It should construct the Huffman tree and compute the code for each character. Much of the work is being done here! Set NUM_LETTERS to 26 in one of your header files. Note that counts[0] is the frequency for the letter 'a' and counts[25] is the frequency for the letter 'z'. Your constructor MUST use the supplied PriorityQueue class to find the next trees to merge at every step. This method should first construct the Huffman tree. It should then construct the code for each letter by traversing the tree (using a call to the HuffmanTree traversal method) and storing a string for each letter (always assign 0 to the lower weight branch and 1 to the higher weight branch). The codebook should be stored as an array in the private data.
• string getWord(string in) : This methods takes in a word to encode. All letters in the word are converted to the appropriate bit strings. Non-letters may be ignored.
• operator<< : Output the letter-to-code translation table with one letter per line (in alphabetical order) followed by a space and the binary encoding from the Huffman algorithm.
• destructor: deallocate all memory appropriately (if necessary)

You must also implement the following methods in the PriorityQueue class (even if they are not necessary to get the correct output):

• default constructor (no parameters)
• copy constructor
• operator=
• destructor
• PriorityQueue(Comparable* array[], int count): constructor that takes an array of Comparable pointers and constructs a PriorityQueue using the (supplied) heapify method.

These methods should assume that the Comparables being stored have their own appropriate constructors/operators/destructor defined. Remember that the first element in the vector storing the heap is a dummy/duplicate to simplify the implementation of various methods. This has implications for the above operations.

Relevant module goals

• Use the priority queue ADT in programming projects
• Implement a priority queue using a binary heap

You will turn in a zip file with (only) your PriorityQueue.h, HuffmanTree.h, HuffmanTree.cpp, HuffmanAlgorithm.h, and HuffmanAlgorithm.cpp files.

//------------------------------------------------------------------------ // HW2.CPP // Driver code for testing Huffman class for creating Huffman codes // Author: Clark Olson //------------------------------------------------------------------------ // This code tests all of the basic functionality of the Huffman class // for CSS 502 HW 2. It is not meant to exhaustively test the class. // // Assumptions: // - none //------------------------------------------------------------------------ #include #include "HuffmanAlgorithm.h" // Must have "const int NUM_LETTERS = 26;" in HuffmanAlgorithm.h or HuffmanTree.h using namespace std; //------------------------------------------------------------------------ // main // Preconditions: none // Postconditions: tests methods of the Huffman class using randomly // generated character counts int main() { // Create random counts int counts[NUM_LETTERS]; for (int i = 0; i < NUM_LETTERS; i++) { counts[i] = rand() % 1000; } // Construct Huffman codes and display table HuffmanAlgorithm code(counts); cout << code << endl; // Simple test of encoding words cout << "test: " << code.getWord("test") << endl; cout << "least: " << code.getWord("least") << endl; cout << endl; return 0; }