Computer Science 3300
Fall 2015
Section 001
Programming Assignment 8

1. Create files trace.cpp and trace.h. Create the trace-level variable and a function to set the trace-level, as discussed above under tracing.

2. Create file huffman.cpp, the source code for the encoding program huffman. Add a main function to it that just sets the trace-level. Try it. Does it set the trace-level correctly?

3. Write a function in huffman.cpp to get the character frequencies. Assume the characters in the file are 8-bits (one byte), so there are 256 possible characters. See writing files using the stdio library and reading files using the stdio library.

Create an array of 256 integers in main to store the frequency counts, one for each possible character that can be stored in one byte.

Write a function that computes the character counts. It should start by setting all of the character frequencies to 0. Then it should open the appropriate file, read the characters, and increment the count for a character each time it is seen. When it is done, it should close the file.

Make the frequency counter return true if it was successful in opening the file and false if not.

Make main call the frequency counter. If it returns false, then there should be a meaningful message to the user, and the program should stop.

Important. You will be using characters as array indices. Do not use type char for an array index. Characters are assumed to be from −128 to 127. Read each character as an integer, where it will be a number from 0 to 255. If you need a character variable, use type unsigned char.

4. Add a function to trace.cpp that takes appropriate parameters and, if the trace level is at least 1, shows the frequencies of all characters that occur at least once.

You will want another function, also in trace.cpp, that shows a character's name. The name of 'a' is just a. But the name of '\n' (the newline character) should be \n, or some other desriptive name, such as newline. Use descriptive names for the tab and space characters as well. For an unprintable character whose code is n, use \n, where you show the character code. (Include <cctype>. Then isprint(c) is true if character c is printable. You are best off passing isprint an integer code, not a character.)

5. Create a file, tree.h, holding the following type definition.

  enum NodeKind {leaf, nonleaf};

  struct Node {
    NodeKind kind;
    char     ch;
    Node*    left;
    Node*    right;

    Node(char c)
    {
      kind = leaf;
      ch   = c;
    }
    Node(Node* L, Node *R)
    {
      kind  = nonleaf;
      left  = L;
      right = R;
    }      
  };

The idea is that a leaf has kind leaf and a nonleaf has kind nonleaf. The ch field should only be used in a leaf and the left and right fields should only be used for a nonleaf. You will lose points if you use the ch field of a nonleaf or the left or right fields of a leaf.

6. Add a function to trace.cpp that prints a tree to the standard output, using the notation described above. Modify main so that it builds some trees and prints them. Does the tree printer appear to work? After it works, remove the tests of the tree printer from main.

7. Write a function in huffman.cpp that takes the array of character frequencies and returns a huffman tree based on the character frequencies. The huffman tree should have type Node*.

For Assignment 5 you implemented the priority queue abstract data type. Copy that implementation into the directory for assignment 8 and modify it by defining

  struct Node;
  typedef Node* PQItemType;
  typedef int   PQPriorityType;

To build the huffman tree, create a priority queue. Insert a leaf into the priority queue for each character whose frequency is not 0, with its frequency as its priority. Notice that

   Node* t = new Node('a');

Now repeatedly remove two trees from the priority queue. Combine them into a single tree.

   Node* t = new Node(r,s);

After taking the first tree out of the priority queue, check whether the priority queue is empty. If so, then the tree that you just got is the answer. So return it. Ask yourself whether you need to destroy the priority queue.

Ensure that your function only uses features of the priority queue module that are part of its interface. Do not use features that should remain hidden inside the priority queue module! For example, do not make use of the information that a priority queue is represented by a linked list. Do not make direct use of type PQCell or any value of type PQCell*. You will lose a lot of points if you use non-exported features of the priority queue module.

8. Modify main so that it builds the huffman tree and, if the trace level is at least 1, shows the resulting tree.

Modify your function so that, if the trace level is at least 2, it shows the entire contents of the priority queue after inserting all of the leaves and after each step of combining two trees. Use printPriorityQueue. What parameters should you pass it?

Test your program. Does it seem to create a sensible Huffman tree?

9. Now, in huffman.cpp, write a function that takes the Huffman tree and returns an array of 256 strings that holds the character codes of all characters that occur at least once. (Only those characters are in the tree.) Use the C++ string type to make your job easy.

Your function will actually need to have two parameters: A tree t (a subtree of the full huffman tree) and a string s that is the path from the root of the full huffman tree to the root of subtree t. Now ask yourself how to handle the case where t is a leaf and how to handle the case where t is a nonleaf. At a nonleaf, what string parameter should you pass to recursive calls?

10. Add a function to trace.cpp that shows the code from the code array. When showing a character, use your function that shows the character's name.

Make main build the code and, if the trace level is at least 1, show the code.

Test what you have so far.

11. The goal is to pack 8 bits into each byte. But before doing that, take a simpler approach where you write each bit as a character so that you can read it. After everything seems to work you can change it so that it writes a binary file instead.

Get files binary.h, binary1.cpp and binary2.cpp. They provide the following tools for writing files.

Type BFILE

BFILE* openBinaryFileWrite(const char* filename)

This function opens binary file filename for writing and returns a pointer to a structure that describes the open file. It returns NULL if the file cannot be opened.

void writeBit(BFILE* f, int b)

This function writes bit b (either 0 or 1) into open file f. Make sure that b is either 0 or 1. It should not be '0' or '1'.

void writeByte(BFILE* f, int b)

This function writes byte or character b. into open file f.

void closeBinaryFileWrite(BFILE* f)

This function closes file f. You must close the file when you are done writing.

Both files binary1.cpp and binary2.cpp have the same interface, described by binary.h. File binary1.cpp writes a text file, writing character '0' to represent bit 0 and character '1' to represent bit 1, allowing you to read the output with a text editor, but not actually compressing. File binary2.cpp writes a binary file.

12. Add a function to huffman.cpp that writes the huffman tree into a given open binary file (type BFILE*).

1. To write a leaf, write a 1 bit followed by the character stored at the leaf (8 bits). So, if t is a leaf, you write t as follows.

     writeBit(f, 1);
     writeByte(f, t->ch);
   

2. To write a nonleaf, write a 0 bit followed by the left subtree followed by the right subtree. So, if t is not a leaf, write t as follows, assuming your function is called writeTreeBinary.

     writeBit(f, 0);
     writeTreeBinary(f, t->left);
     writeTreeBinary(f, t->right);
   

Modify main so that it opens the second file name in the command line as a binary file for writing. Then it writes the Huffman tree to the binary file and closes the file.

13. Create file unhuffman.cpp, which will be the program that uncompresses a file.

Write a function in unhuffman.cpp that reads the description of a tree from a given open BFILE* file, and returns the tree. Keep it simple. To read a tree, start by reading a bit. If the bit is a 1, you are looking at a leaf. Read the character (a byte) and build a leaf holding that character. But if the bit is a 0, then you are looking at a nonleaf. Read the left subtree then the right subtree.

Be careful about parameters. When you encounter a nonleaf, it is important that you read the left subtree then the right subtree. When a function call f(A, B) is evaluated, expressions A and B can be evaluated in any order. If order of evaluation is important (which it is for reading a tree), do the evaluations in separate statements before doing the function call.

Write a main function that opens the binary file whose name is given in the command line, reads a tree from it, and, if the trace level is at least 1, writes the tree to the standard output for debugging.

Use the following for reading the binary file, also described by binary.h.

BFILE* openBinaryFileRead(const char* filename)

This function opens binary file filename for reading and returns a pointer to a structure that describes the open file. It returns NULL if the file cannot be opened.

int readBit(BFILE* f)

This function reads one bit from file f and returns the bit (either 0 or 1). At the end of the file, readBit returns EOF.

int readByte(BFILE* f)

This function reads one byte (8 bits) from file f and returns the byte. Use it to get a byte that you wrote using writeByte. At the end of the file, readByte returns EOF.

void closeBinaryFileRead(BFILE* f)

This function closes file f. Once it is closed, you cannot read from it again.

When you link unhuffman.cpp, it is critical that you use the same implementation of binary.h as for huffman.cpp. Either link both with binary1.cpp or both with binary2.cpp.

14. Test what you have so far. Your huffman program should write a description of the tree into the binary file. Read it back with unhuffman. Is the tree correct?

15. Write a function in huffman.cpp that takes the array of character codes, an open binary file and the name of the file to read. It should reread the input file and write the codes for the characters that it reads into the binary file.

Modify main so that, after writing the tree to the binary file, it also writes all of the character codes.

16. Return to unhuffman.cpp. Write a function that reads the code for a single character and writes that character. It should take the Huffman tree, an open binary file for reading and an open file for writing.

As you read each bit, move down the tree in the appropriate direction. When you hit a leaf, write out the character at that leaf then start again at the root of the tree to get the next character. Keep going until you hit the end of the file.

It is possible that this function encounters the end of the file. You will find it convenient for this function to return an indication of whether it was successful in reading a character code or encountered the end-of-file.

Important note. The code for a character only has a bit in it for each nonleaf. There is no bit for a leaf. So when reading the code, only read a bit when you are at a nonleaf in the tree, to decide whether to move to the left or right. Do not read a bit when you are at a leaf.

17. Now write a function to do the uncompression. It should keep reading character codes and writing the corresponding character until the end-of-file is reached.

18. Test both programs. If you compress a file and then uncompress it, do you get back exactly what was in the original file? Try a file that contains tabs, spaces and has more than one line. Try some non-letter characters too.

19. Once everything is working, submit your work.