Write a program according to the specifications found below, that:

• compresses a text file into a Huffman-encoded file, generating the symbol frequency file for that particular text file

• decodes a Huffman-encoded file into a text file, using the symbol frequency file for that particular file.

write the following class.

Class HuffmanCoder.java:

This class uses a Huffman tree for encoding a character and decoding a code string. Your implementation of the HuffmanCoder class must follow the specifications below, with the method headers as specified.

Attributes:

• private HuffmanTree huffTree: the Huffman tree

• private ArrayUnorderedList<EncodingData> encodingList: an unordered list of encoding data that will be used for encoding a text file into a Huffman-coded compressed file

Constructor to write:

• public HuffmanCoder(ArrayOrderedList<HuffmanPair> pairsList): this constructor will create the huffTree, using the 4th Huffman tree constructor. It will also call the private helper method buildEncodingList(BinaryTreeNode<HuffmanPair> node, String encoding) which will build the list of symbols and their encodings from the Huffman tree huffTree. See below for further instructions.

Methods to write:

• public char decode(String code): This method will take the specified string of binary digits that is a Huffman encoding, and will return the original coded character. It will use the following decoding technique: as you get each character from the parameter string, traverse the tree beginning at the root, taking the left-hand path if the character is 0 and the right-hand path if the character is 1. When you encounter a leaf, you have found the symbol that was encoded. If the string of binary digits code does not lead to a leaf node, then the method must return (char) 0.

• public String encode(char c)throws ElementNotFoundException: This method will take the specified character and return the string representation of the binary Huffman encoding of that character.

• public String toString(): This method will return a string representation of the encoding list.

• private void buildEncodingList (BinaryTreeNode<HuffmanPair> node, String encoding): This method will build the unordered list encodingList (an attribute of the HuffmanCoder class) from the Huffman tree huffTree. The list encodingList will be a list of EncodingData objects. This method will add new EncodingData objects to encodingList recursively, following this algorithm:
if the parameter node is a leaf node add a new EncodingData object whose symbol is the character in the Huffman pair of that node and whose encoding is the second parameter encoding else call buildEncodingList with the left child of node and encoding with character ‘0’ appended call buildEncodingList with the right child of node and encoding with character ‘1’ appended .