IST238: Algorithms. Project #5.

1. Implement priority queue template class PQueue with the following public methods:
   • default constructor PQueue() and constructor that allows to specify the amount of memory allocated for the queue PQueue(int N). For this particular project you may assume that your queue will never contain more than 256 elements.
   • destructor ~PQueue()
   • method void (Item node) that adds an item to the queue
   • method Item get_top() that returns the highest priority item and removes it from the queue
   • Boolean method bool empty() that returns true if the queue is empty and false otherwise
   • method int Size() that returns the current size of the queue
   Note 1: you should use the heap structure to implement this class.
   Note 2: unlike what we done in the class your priority queue class should be a template class; that is, it should be able to work with any kind of elements.
2. Implement the BitMap class that has the following interface:

   class BitMap {
     private:
        ...
     public:
       BitMap();                        // default constructor
       BitMap(int N);                   // constructor that allocates enough memory to store N bits
       BitMap(ifstream &finp);          // constructor that reads the whole bitmap from the given binary file
       ~BitMap();                       // destructor
       bool get_bit(int i);             // returns the specified bit (true=1, false=0)
       void set_bit(int i, bool value); // sets the specified bit
       bool Get();                      // returns the current bit
       void Put(char bit);              // sets the current bit according to the char value: '0'->0 '1'->1
       void Put(string bits);           // sets a sequence of bits from the current position
       void print();                    // for debugging purposes provide a tool that prints the whole bitmap as a sequence of 1s and 0s
       void DumpToFile(ofstream &fout); // saves the all information from the bitmap into a binary file
   };
   
         

   Note 1: you should maintain that special pointer that points to the current position. In fact, you need even two such pointers for writing and reading.
   Note 2: Please see the example that shows how to deal with binary files.
3. Implement the Huffman code to construct the optimal prefix tree. To complete this, you need:
   • read all characters from the specified file (please refer to I/O example to see how to deal with text files)
   • count their frequencies
   • create the as many nodes of the type Node as you have read distinct characters
   • run the Huffman's algorithm to construct the optimal prefix tree
   • based on the prefix tree build the coding table that specifies variable length code for each character from the file
4. Develop a pair of functions that deal with the Huffman binary tree:
   void DumpTreeToFile(Node*, ofstream&) - that dumps the complete tree into the binary file passed as the second argument, and
   void RestoreTreeFromFile(Node*, ifstream&) - that restores the complete tree from the binary file.
5. Re-read the file and print the sequence of zeros and ones corresponding to the file contents. The coded version of the text should be written into a binary file with the same name as the input file is and extension huf.
6. Your program should analyze the command line arguments. If it's executed with the first argument -c it should compress the text file which name is to be given as the second argument. The program should read the text file and save the compressed version of the file into a binary file with the same name and additional extension huf. It also should print the compression rate. For example:

   C:\IST238\> huffman -c test.txt
   File 'test.txt' has been compressed down to 14% of its original size.
   The compressed file 'test.txt.huf'.
         

   If the program executed with the first command line argument -u, then the second argument is to be treated as a name of a binary file to decompress. This binary file should have the saved huffman coding tree and the bitmap.