Computer Science 2530
Fall 2016
Programming Assignment 8

1. Create files trace.cpp and trace.h. You can use a global variable to indicate the trace level, which can be 0 or 1. Create the variable in trace.cpp. If your variable is called tracelevel, then trace.cpp will say

  int tracelevel = 0;

  extern int tracelevel;

Add a function that takes argc and argv and sets the trace level to 1 if the command line contains -t.

2. A Makefile is provided. Look at it to see what the targets are and what they do.

3. Create file huffman.cpp, the source code for the compression program huffman. Add a main function to it that just sets the trace-level. Use the following heading for main (in huffman.cpp).

  int main(int argc, char** argv)

Try it. Does it set tracelevel correctly?

4. 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 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 the character is seen. When it is done, your function should close the file.

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

What are appropriate parameters to pass to the frequency counter? Remember that it is a specialist. It counts character frequencies in a given file. Don't make it more aware of the context in which it sits than it needs to be.

Now 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. The program must not keep going when the file to read does not exist.

Important. You will be using characters as array indices. Do not use type char for an array index. Values of type char are assumed to be from −128 to 127. That won't work for array indices.

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.

If you receive a warning that an array index has type char, heed the warning!

5. Add a function to trace.cpp that takes appropriate parameters and, if tracing is turned on, shows the frequencies of all characters that occur at least once in a clear and readable format.

You will want another function, also in trace.cpp, that prints 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 (and is not a white-space character). Pass isprint an integer code, not a character.)

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

#ifndef TREE_H
#define TREE_H

  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;
    }      
  };

  typedef Node* Tree;

#endif

The idea is that a leaf has kind leaf and a nonleaf has kind nonleaf. The ch field must only be used in a leaf and the left and right fields mus 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.

You should include tree.h in any file that needs to use the tree type.

7. Add a function to trace.cpp that prints a tree to the standard output, using the notation described above. To show a leaf in the tree, show the character's name, not the raw character.

Modify main so that it builds some test trees and prints them. Does the tree printer appear to work? After it works, remove the tests of the tree printer from main.

8. 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 Tree.

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

  #include "tree.h"
  typedef Tree 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

   Tree t = new Node('a');

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

   Tree 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. Should you destroy the priority queue?

Important. 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! Do not add any new features to pqueue.cpp.

This is very important. When I compile your program, I will link in my own priority queue module that implements the interface described in assignment 5. If you use anything that is not part of that interface, your program will not compile.

Important. The function that builds the Huffman tree is an expert in building Huffman trees.

1. Do not make other functions (except those that are helpers for the tree builder) know anything about how a Huffman tree is built from an array of frequencies. In particular, no other function should know that a priority queue is involved.

2. The tree builder should not know more about the rest of the program than it needs to know in order to do its job. Choose its interface in a sensible way.

9. Modify main in huffman.cpp so that it builds the huffman tree and, if tracing is turned on, shows the resulting tree.

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

10. Now, in huffman.cpp, write a function buildCode that takes the Huffman tree t and an array Code that can hold 256 strings. This function should fill in the Code array so that, if character c occurs at a leaf in t then Code[c] holds the code of c, as a null-terminated string. If character c does not occur in tree t, then Code[c] should be NULL.

Your function will need to have the following parameters.

• A tree t (a subtree of the full huffman tree)

• The array Code to fill with the code.

• A null-terminated string pref of 0's and 1's that is the sequence of edge labels from the root of the huffman tree to the root of t.

If your function is called buildCode, then, for each character c in t with code r (according to t), buildCode(t, Code, pref) adds code pref+t for character c to array Code. If t is (e, g) then buildCode(t, Code, "01") stores code "010" for e and code "011" for g. Now you see why that parameter is called pref.

If t is a leaf holding character c, then add pref into Code> as the code for character c.

If t is not a leaf, then buildCode should call itself on the left and right subtrees of t. The pref parameter for the call on the left subtree should be pref with '0' added to the end. The pref parameter for the call on the right subtree should be pref with '1' added to the end. (Create local arrays in buildCode and and copy pref into them using strcpy. Then concatenate "0" to the end of one and "1" to the end of the other using strcat.)

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

Make main build the code and, if tracing is turned on, show the code.

Test what you have so far.

12. 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, packing 8 bits into each byte.

13. Add a function to huffman.cpp that writes a description of a given tree into a given open binary file (type BFILE*). Note that this is not the same as your trace function that writes a tree for debugging.

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.

14. Create file unhuffman.cpp, which will be the program that uncompresses a file. You will want a file written by huffman, holding a description of a tree.

Write a function in unhuffman.cpp that reads a tree whose description is in a given open BFILE* file, and returns the tree. (Open the file in main.) 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.

When you encounter a nonleaf, it is important that you read the left subtree then the right subtree, in that order. According to the definition of C++, when a function call f(A, B) is evaluated, expressions A and B can be evaluated in any order. To avoid that, do the recursive calls in separate statements.

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.

Write a main function in unhuffman.cpp. It should start by turning tracing on or off. Then it opens the binary file whose name is given in the command line, reads a tree from it, and, if tracing is turned on, writes the tree to the standard output for debugging. Make the trace readable.

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.

15. Test what you have so far. Your huffman program should write a description of the tree into the binary file and your unhuffman program should read it back correctly.

16. Write a function in huffman.cpp that takes the array of character codes, a binary file that is opened for writing, and the name of the file to read. It should reread the input file and write the code for each character that it reads into the open binary file.

Modify main so that, after writing the tree to the binary file, it calls that new function to write then encoded characters.

Note. Do not close the binary file between writing the tree and writing the character codes. Only close it after doing both steps.

17. Return to unhuffman.cpp. Write a function that reads the code for a single character and returns the character, as an integer. If it encounters and end-of-file, it should return EOF. This function will need take the Huffman tree and an open binary file for reading.

As you read each bit, move down the tree in the appropriate direction. When you hit a leaf, that is the answer.

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.

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

19. 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.

20. Once everything is working, submit your work.