Assignment 6: MiniBrowser 2

Displaying Text

In this part of the assignment, you'll implement a class called LineManager that stores all the lines for the current webpage, and provides information about which lines should be displayed onscreen. Unlike your previous implementation from assignment 5, it is implemented using a binary search tree of Lines. You'll have to create a binary search tree given a sorted Vector of Line pointers, and utilize that binary search tree as needed. The only member variable (a.k.a. instance variable; private variable; field) you are allowed to have in your implementation is a pointer to the root of your binary search tree. Do not use any other collections or data structures in any part of your code, or have any other private instance variables.

You will need to use Line objects, which represent a single line of text (spanning the entire width of the page). Below is an image of MiniBrowser, with each line outlined in red. The widths of all the lines are the same, and you can sort lines by y-coordinate, with the top line (one with the smallest y-coordinate) as the smallest. In the example below, the line "The Princess Bride is a 1973 fantasy romance novel by American" is the first Line in the webpage.

You will not need to manipulate or interact with the text; you can just treat the lines as rectangles (potentially with space between them) that together make up the webpage. No two Line objects will overlap.

The browser already handles splitting the entire webpage into lines. However, since the webpage (generally) is not visible all at once, not all of the lines need to be drawn; in fact, drawing all of the lines would make your browser run very slowly. The solution is an optimization to only draw those lines that will be visible, so your job is to write a function to determine which lines should be drawn. As the user scrolls up or down the page, the "visible range" of lines will change. Binary Search Trees are very effective at handling these "range queries," or returning all the elements within a range.

Browsers also need to handle user clicks, recognizing, for example, if the user is attempting to follow a hyperlink. You will implement a method that, given a y-coordinate, returns a pointer to the line at that location. Our starter code will then search that line for a link, allowing the user to travel to different pages. BSTs are also effective at searching for an element.

At this link, you will find a sample interactive webpage with 12 lines of text and a scrollbar on the right (inside the black box). The black box indicates what is actually visible on the computer, but as you drag the scrollbar (give it a try), the lines will scroll out of view. The browser could render (draw) all the lines of the webpage, but since only 4-5 are visible at a time, it can optimize and only draw those that are fully or partially on the screen. Below the screen, linesInRange's value will update with which lines are in the viewable range of the screen.
The red "x" on the screen represents a location where the user may click; the line at the location of the "x" is reflected next to lineAt at the bottom of the demo. Note that there may be space between the lines, so the element is sometimes nullptr.

A Line has the following fields and methods:

Since each line spans the width of a page, we only need to store information about its height and vertical placement, not its width or horizontal placement.

As each Line corresponds to a line of text, we can order Lines by their y-coordinate, meaning that the first Line is the line at the top of the screen.

To avoid having to store the text associated with a Line multiple times and to more easily be able to link a Line a user clicked on with the text, you will only be dealing with pointers to Lines. Thus, whenever you store or manipulate the Lines, you should do so using pointers. You should not create Lines in your implementation.

The sorts of operations the LineManager needs to perform are well-suited for a binary-search tree. Because we need to store a Line in each node, we have defined the LineManagerNode struct (defined in LineManagerNode.h) for you to build the BST with:

struct LineManagerNode {
    Line* line;
    LineManagerNode* left;
    LineManagerNode* right;
};

Your job is to implement the following functions:

The members listed above represent your class's required behavior. But you may add other member functions to help you implement all of the appropriate behavior. Any other member functions you provide must be private. Remember that each member function of your class should have a clear, coherent purpose. You should provide private helper members for common repeated operations. Make a member function and/or parameter const if it does not perform modification of the object's state.

Autocomplete

No browser would be complete without autocomplete, the list below the search bar that dynamically suggests article titles as the user types.

Before tackling this part of the assignment, you should review the notes about tries from Friday's (11/9) lecture.

Our autocomplete will use the several thousand most common Wikipedia article titles (included in TopArticles.txt, which the starter code reads in and adds to the Autocomplete object using the public methods below). When the user begins typing a word, the autocomplete should suggest articles from that list that begin with the characters the user has already typed.

This trie is a little different from those we discussed in class as Wikipedia article titles are not comprised of only the letters a-z. As a result, you will need to design your own struct for each node of the Trie, keeping in mind that your trie will need to be able to support many different characters (including whitespace or even non-English characters). You'll need to devise a space-efficient solution that will work for any character value without any wasted space. For that reason, you should not use an array. One suggestion, however, is to use a string that is one character long instead of a char to store the single character - this is because some more rare characters may have strange values that make debugging more confusing. Keep in mind that this trie is case-sensitive, meaning "Princess Bride" is different from "princess bride".

You will implement the following methods.

Compression

In this part of the assignment, you will implement the Huffman coding algorithm to compress and uncompress data. We provide a mini program called "Shrink-It" that lets you test just the different parts of your encoding code, including compressing and uncompressing different types of data (we have provided sample files to use in the res/ folder). Once you complete your algorithm, you can also run the main browser program and check the "Compress?" box to have the built-in cache store compressed versions of webpages, instead of the uncompressed ones as you did in assignment 5. At the bottom, you'll be able to see an indicator of the space savings of the compressed cache. You should be able to see some pretty substantial (~30-40%) savings!

Problem Description:

Huffman encoding (Wikipedia) (Wolfram Mathworld) is an algorithm devised by David A. Huffman of MIT in 1952 for compressing text data to make a file occupy a smaller number of bytes. This relatively simple compression algorithm is powerful enough that variations of it are still used today in computer networks, fax machines, modems, HDTV, and other areas.

Normally text data is stored in a standard format of 8 bits per character using an encoding called ASCII that stores every character using a binary integer value from 0-255. (ASCII encoding table) The idea of Huffman encoding is to abandon the rigid 8-bits-per-character requirement and use different-length binary encodings for different characters. The advantage of doing this is that if a character occurs frequently in the file, such as the common letter 'e', it could be given a shorter encoding (fewer bits), making the file smaller. The tradeoff is that some characters may need to use encodings that are longer than 8 bits, but this is reserved for characters that occur infrequently, so the extra cost is worth it.

The table below compares ASCII values of various characters to possible Huffman encodings for some English text. Frequent characters such as space and 'e' have short encodings, while rarer ones like 'z' have longer ones. (* The Huffman encodings shown in the table below are hypothetical and would not always be the result of your program.)

In this program you will write code to encode and decode files using Huffman's algorithm, which relies on binary trees. We provide you with starter code for the user interaction and menus. The following is one sample partial log of execution of the provided main program. More logs are available above or through the Compare Output feature in your console window.

Welcome to CS 106B/X Shrink-It!
...
B)uild enc.tree   C)ompress     VB) View binary
E)ncode data      U)ncompress   VT) View text
D)ecode data      F)ree tree    VS) View side-by-side
Q)uit

Your choice? c
Input file name: large.txt
Output file name (Enter for large.huf): large.huf
Reading 9768 uncompressed bytes.
Compressing ...
Wrote 5921 compressed bytes.

Here is a supplementary handout on Huffman encoding and file compression if you are interested in more information after reading this spec.

Encoding a File:

To perform a Huffman encoding of a given text source file into a destination compressed file, you must first build a Huffman tree. This operation is represented by the required function buildEncodingTree that you will implement. A Huffman tree is a binary tree with a particular structure, where each node represents a character and its count of occurrences in the file. The path of left (0) and right (1) links along the tree from its root to each leaf indicates the binary encoding of that character in your eventual compressed output. There is a well-defined algorithm for converting a given input data set into a Huffman tree.

Suppose we have a file named example.txt whose contents are:

ab ab cab

In the original file, this text occupies 10 bytes (80 bits) of data. The 10th is a special "end-of-file" (EOF) byte, which we will represent using the special fake value of 256.

A possible Huffman tree for this input data is shown below. There is an algorithm to create a Huffman tree from a given input data, which we'll show later in this document. For now let's just look at the given tree and understand how it would be useful for compressing data.

                   +---+
                   |   |
                   +---+
           0 _____/     \_____ 1
            /                 \
       +---+                   +---+
       |   |                   |   |
       +---+                   +---+
    0 /     \ 1             0 /     \ 1
     /       \               /       \
+---+         +---+     +---+         +---+
|' '|         |   |     |'a'|         |'b'|
+---+         +---+     +---+         +---+
           0 /     \ 1
            /       \
       +---+         +---+
       |'c'|         |EOF|
       +---+         +---+

If we traverse the tree and think of each left branch as a 0 and each right branch as a 1, we can traverse the tree to come up with binary encodings for every character in the file. In this case, those encodings would be:

' ' = 00
'c' = 010
EOF = 011
'a' = 10
'b' = 11

We could then write out the binary encoded versions of these characters to compress the original input of ab ab cab (which is 10 bytes including EOF) into the following compressed version, which occupies only 22 bits (3 bytes):

1011001011000101011011

This particular example encoding takes advantage of the fact that not every ASCII character appears in the input file, but Huffman encoding can still effectively compress a file even if it uses a wider variety of characters.

Now that we've explored the Huffman tree structure and how it can be useful, let's talk about how to build a Huffman tree for a given input file's contents.

Building a Huffman Tree:

The task of building the Huffman tree for a given input file is represented by the following function that you must write in encoding.cpp. The nodes of your Huffman tree must be allocated on the heap so that they will remain in existence after your function returns. Your function must return a pointer to the node representing the root of the tree you have created. Your function must have the following signature:

HuffmanNode* buildEncodingTree(istream& input)

In this function you read input from a given input stream, which could be a file on disk, a string stream, or any other source of input. You may assume that the input file exists and can be read, though the file might be empty.

Suppose as in the previous example we have a file named example.txt whose contents are:

ab ab cab

To begin encoding this file into a Huffman tree, you should count the number of occurrences of each unique character. You should also include a count of a single occurrence of the fake character PSEUDO_EOF, which is a global constant defined in the provided starter code; note that PSEUDO_EOF doesn't appear in the input file, and you have to manually fake as though it appears at the end of the file. In the previous input, there are two spaces, three occurrences of 'a', three 'b', one 'c', and one pseudo EOF. (An empty file should be considered to contain only 1 occurrence of PSEUDO_EOF and no other characters.)

You should store these counts into node structures, and put the node structures into a priority queue, with smaller counts having more urgent priority, so that characters with lower counts will come out of the queue sooner. For example, the following might be the contents of the priority queue for the preceding input file. The priority queue is somewhat arbitrary in how it breaks ties, such as 'c' being before EOF and 'a' being before 'b'.

   front                                      back
+---------------------------------------------------+
|                                                   |
|  +-----+   +-----+   +-----+   +-----+   +-----+  |
|  | 'c' |   | EOF |   | ' ' |   | 'a' |   | 'b' |  |
|  |  1  |   |  1  |   |  2  |   |  3  |   |  3  |  |
|  +-----+   +-----+   +-----+   +-----+   +-----+  |
|                                                   |
+---------------------------------------------------+

The elements you put into the priority queue should be pointers to binary tree nodes, with each node storing a character and a count of its occurrences. We provide you with a structure called HuffmanNode that represents a node in a Huffman encoding tree:

struct HuffmanNode {
    int character;       // character being represented by this node
    int count;           // number of occurrences of that character
    HuffmanNode* zero;   // 0 (left) subtree (null if empty)
    HuffmanNode* one;    // 1 (right) subtree (null if empty)
    ...
};

The character field is declared as type int, but you should think of it as if it were a char. (Types char and int are largely interchangeable in C++, but using int here allows us to sometimes use character to store values outside the normal range of char for use as special flags.) The character field of a node can take one of three types of values:

• an actual char ASCII value from 0-255;
• the constant PSEUDO_EOF (defined in bitstream.h in the Stanford library), which represents the pseudo-EOF value (the symbol, denoted by | in the supplemental Huffman handout, that marks the end of the encoding) that you will need to place at the end of an encoded stream (this happens to be the value 256); or
• the constant NOT_A_CHAR (defined in bitstream.h in the Stanford library), which represents something that isn't actually a character. (This can be stored in branch nodes of the Huffman encoding tree that have children, because such nodes do not represent any one individual character.) (This happens to be the value 257.)

Your algorithm converts the priority queue of nodes into a Huffman tree as follows: You repeatedly remove the two node pointers A and B from the front of the queue (the two with the fewest occurrences) and create a new parent node C, whose children are A and B, and whose count of occurrences is the sum of A's and B's. The first node removed (A) becomes the left child, and the second (B) becomes the right. The new node is re-inserted into the queue in sorted order of occurrences. This process is repeated until the queue contains only one binary tree node with all the others as its children. This will be the root of our finished Huffman tree. (Note: Don't actually name your variables A, B, and C in your code. One-letter variable names are usually bad.)

The following diagram shows the algorithm in progress. Notice that the nodes with low frequencies end up far down in the tree, and nodes with high frequencies end up near the root of the tree. This structure can be used to create an efficient encoding in the next step.

   front                                      back
+---------------------------------------------------+
|                                                   |
|  +-----+   +-----+   +-----+   +-----+   +-----+  |
|  | 'c' |   | EOF |   | ' ' |   | 'a' |   | 'b' |  |
|  |  1  |   |  1  |   |  2  |   |  3  |   |  3  |  |
|  +-----+   +-----+   +-----+   +-----+   +-----+  |
|                                                   |
+---------------------------------------------------+

   front                            back
+-----------------------------------------+
|                                         |
|  +-----+   +-----+   +-----+   +-----+  |
|  | ' ' |   |     |   | 'a' |   | 'b' |  |
|  |  2  |   |  2  |   |  3  |   |  3  |  |
|  +-----+   +-----+   +-----+   +-----+  |
|              / \                        |
+-------------/---\-----------------------+
             /     \
        +-----+   +-----+
        | 'c' |   | EOF |
        |  1  |   |  1  |
        +-----+   +-----+

   front                  back
+-------------------------------+
|                               |
|  +-----+   +-----+   +-----+  |
|  | 'a' |   | 'b' |   |     |  |
|  |  3  |   |  3  |   |  4  |  |
|  +-----+   +-----+   +-----+  |
|                        / \    |
+-----------------------/---\---+
                       /     \
                  +-----+   +-----+
                  | ' ' |   |     |
                  |  2  |   |  2  |
                  +-----+   +-----+
                              / \
                             /   \
                       +-----+   +-----+
                       | 'c' |   | EOF |
                       |  1  |   |  1  |
                       +-----+   +-----+

     front                   back
  +--------------------------------+
  |                                |
  |  +-----+              +-----+  |
  |  |     |              |     |  |
  |  |  4  |              |  6  |  |
  |  +-----+              +-----+  |
  |    / \                  / \    |
  +---/---\----------------/---\---+
     /     \              /     \
+-----+   +-----+    +-----+   +-----+
| ' ' |   |     |    | 'a' |   | 'b' |
|  2  |   |  2  |    |  3  |   |  3  |
+-----+   +-----+    +-----+   +-----+
            / \
           /   \
     +-----+   +-----+
     | 'c' |   | EOF |
     |  1  |   |  1  |
     +-----+   +-----+

          +---------------+
          |               |
          |    +-----+    |
          |    |     |    |
          |    | 10  |    |
          |    +-----+    |
          |     /   \     |
          +---/-------\---+
            /           \
     +-----+             +-----+
     |     |             |     |
     |  4  |             |  6  |
     +-----+             +-----+
       / \                 / \
      /   \               /   \
+-----+   +-----+   +-----+   +-----+
| ' ' |   |     |   | 'a' |   | 'b' |
|  2  |   |  2  |   |  3  |   |  3  |
+-----+   +-----+   +-----+   +-----+
            / \
           /   \
     +-----+   +-----+
     | 'c' |   | EOF |
     |  1  |   |  1  |
     +-----+   +-----+

When building the encoding tree, use the PriorityQueue collection provided by the Stanford libraries, defined in library header priorityqueue.h. This priority queue allows each element to be enqueued along with an associated numeric priority. The priority queue then sorts elements by their priority, with the dequeue function always returning the element with the minimum priority number. Consult the PriorityQueue documentation on the course website and lecture slides for more information about priority queues.

Compressing a File Using a Huffman Tree:

Once you have a Huffman tree, you can use it to compress a file. The step of encoding a file's data using a Huffman tree is represented by the following function that you must write:

void encodeData(istream& input, HuffmanNode* encodingTree, obitstream& output)

(The obitstream type is an output stream for writing bits and is described later in this document.)

The Huffman code for each character is derived from your binary tree by thinking of each left branch as a bit value of 0 and each right branch as a bit value of 1, as shown in the diagram below.

               +-----+
               |     |
               | 10  |
               +-----+
              /       \
        0   /           \   1
     +-----+             +-----+
     |     |             |     |
     |  4  |             |  6  |
     +-----+             +-----+
       / \                 / \
  0   /   \   1       0   /   \   1
+-----+   +-----+   +-----+   +-----+
| ' ' |   |     |   | 'a' |   | 'b' |
|  2  |   |  2  |   |  3  |   |  3  |
+-----+   +-----+   +-----+   +-----+
            / \
       0   /   \   1
     +-----+   +-----+
     | 'c' |   | EOF |
     |  1  |   |  1  |
     +-----+   +-----+

The code for each character can be determined by traversing the tree. To reach ' ' we go left twice from the root, so the code for ' ' is 00. The code for 'c' is 010, the code for EOF is 011, the code for 'a' is 10 and the code for 'b' is 11.

Using these encodings, we can encode the file's text into a shorter binary representation. The text ab ab cab would be encoded as:

1011001011000101011011

The following table details the char-to-binary translation in more detail. The overall encoded contents of the file require 22 bits, or almost 3 bytes, compared to the original file of 10 bytes.

Since the character encodings have different lengths, often the length of a Huffman-encoded file does not come out to an exact multiple of 8 bits. Files are stored as sequences of whole bytes, so in cases like this the remaining digits of the last bit are filled with 0s. You have no control over this; it is a rule of the operating system that every file must occupy whole bytes.

It might worry you that the characters are stored without any delimiters between them, since their encodings can be different lengths and characters can cross byte boundaries, as with 'a' at the end of the second byte. But this will not cause problems in decoding the file, because Huffman encodings by definition have a useful prefix property where no character's encoding can ever occur as the start of another's encoding.

In your function you will read one character at a time from a given input file, and use the provided Huffman tree to come up with a translation from each character to binary, then write the character's encoded binary bits to the given bit output bit stream. After writing the file's contents, you should write a single occurrence of the binary encoding for PSEUDO_EOF into the output so that you'll be able to identify the end of the data when decompressing the file later.

You may assume that the parameters are valid: that the given Huffman tree is valid and contains information for every character that appears in the input file, that the input file stream is readable, and that the output stream is writable. The streams are already opened and ready to be read/written; you do not need to prompt the user or open/close the files yourself.

Decoding a File:

You can use a Huffman tree to decode text that was previously encoded with its binary patterns. The step of decoding the file's data from the compressed binary bits is represented by the following function that you must write:

void decodeData(ibitstream& input, HuffmanNode* encodingTree, ostream& output)

(The ibitstream type is an input stream for reading bits and is described later in this document.)

The decoding algorithm is to read each bit from the file, one at a time, and use these bits to recursively traverse the Huffman tree. Starting from the root, if the bit is a 0, you move left in the tree. If the bit is 1, you move right. You do this until you hit a leaf node. Leaf nodes represent characters, so once you reach a leaf, you output that character, and then your algorithm should return to the top of the tree. For example, suppose we are given the same encoding tree above, and we are asked to decode a file containing the following bits:

111001000100101001100000

Using the Huffman tree, we walk from the root until we find characters, then output them and go back to the root.

• We read a 1 (right), then a 1 (right). We reach the leaf 'b' and output it. Return to the root.
  111001000100101001100000
• We read a 1 (right), then a 0 (left). We reach leaf 'a' and output it. Return to root.
  111001000100101001100000
• We read a 0 (left), then a 1 (right), then a 0 (left). We reach 'c' and output it.
  111001000100101001100000
• We read a 0 (left), then a 0 (left). We reach ' ' and output a space.
  111001000100101001100000
• We read a 1 (right), then a 0 (left). We reach 'a' and output it.
  111001000100101001100000
• We read a 0 (left), then a 1 (right), then a 0 (left). We reach 'c' and output it.
  111001000100101001100000
• We read a 1 (right), then a 0 (left). We reach 'a' and output it.
  111001000100101001100000
• We read a 0, 1, 1. This is our EOF encoding pattern, so we stop.
  111001000100101001100000
• The overall decoded text is "bac aca". (Notice that we do not read or decode the final 00000 bits in the last byte because they come after the EOF marker.)

In this function you should do the opposite of encodeData; you read the input one bit at a time, and write the uncompressed contents one byte at a time. You may assume that the streams are already opened and you do not need to prompt the user for file names, nor open/close the files yourself.

To manually verify that your implementations of encodeData and decodeData are working correctly, use our provided test code to compress strings of your choice into a sequence of 0s and 1s. The rest of this document describes a header that you will add to compressed files, but in encodeData and decodeData, you should not write or read this header from the file. Instead, just use the encoding tree you're given. Worry about headers only in the compress / uncompress functions described later.

Proper Use of I/O Streams:

In parts of this program you will need to read and write individual bytes to files. In the past we have wanted to read input an entire line or word at a time. But in this program it is much better to read one single character (byte) at a time. So you should use the following in/output stream functions:

You might also find that you want to read an input stream, then "rewind" it back to the start and read it again. To do this on an input stream variable named input, you can use the rewindStream function from "filelib.h" (documentation):

rewindStream(input);   // tells the stream to seek back to the beginning

Bit Input/Output Streams:

To read or write a compressed file, reading one byte at a time is still too much; you will want to read and write binary data one single bit (eighth of a byte) at a time, which is not directly supported by the default in/output streams. Therefore the Stanford C++ library provides obitstream and ibitstream classes with writeBit and readBit members to make it easier. These classes come from "bitstream.h" (documentation):

When reading from an bit input stream (ibitstream), you can detect the end of the file by either looking for a readBit result of -1, or by calling the fail() member function on the input stream after trying to read from it, which will return true if the last readBit call was unsuccessful due to reaching the end of the file.

Note that the bit in/output streams also provide the same members as the original ostream and istream classes from the C++ standard library, such as getline, <<, >>, etc. But you usually don't want to use those, because they operate on an entire byte (8 bits) at a time, or more; whereas you want to process these streams one bit at a time.

Compress/Uncompress and Header:

The last step of this program is to glue all of your previous code together into two functions that do all of the work of compressing and uncompressing a file in a single call. An important concept used by these two functions is the notion of a file header that they will use to store data about the compression process.

void compress(istream& input, obitstream& output)
void uncompress(ibitstream& input, ostream& output)

Let's discuss the compress function in more detail. In this function you should compress the given input file into the given output file, combining all of the steps described previously. You will take as parameters an input file that should be encoded and an output bit stream to which the compressed bits of that input file should be written. You should read the input file one character at a time, building an encoding of its contents, and write a compressed version of that input file, including a header, to the specified output file. This function should be built on top of the other encoding functions described earlier in this document and should call them as needed.

You may assume that the streams are both valid and read/writeable, but the input file might be empty. If the file is empty, your code will fail to read the header, so you should stop there and return without uncompressing the file. The streams are already opened and ready to be read/written; you do not need to prompt the user for filenames or open/close the files yourself. If your function allocates any dynamic memory on the heap, you must free it and not leak memory.

But there is an additional piece of work that your compress function needs to do, which is to write a header into the compressed file. The reason you need a header is because in order to decode the compressed file later, we need a way to recreate its Huffman tree. Without the encoding tree, you don't know the mappings from bit patterns to characters. What if all we have is the compressed file? How will we know how to decode it?

To address this issue, you must come up with a way of storing information about the Huffman encodings inside the compressed file itself. The encodings must be stored as a prefix of data at the start of the compressed file, which we will call the header of the file. The idea is that when opening our compressed file later, the first several bytes will store your encoding information, and then those bytes are immediately followed by the compressed binary bits that we compressed earlier. In spirit we want to write out the Huffman tree into the compressed file; but it isn't possible to write out the tree directly, so we must come up with a way to "flatten" the tree, or store information equivalent to the tree's contents, or store information that can be used to rebuild or recreate the tree's contents.

What should we store in our header? How do we represent the Huffman tree and its binary character encodings? This is up to you. You don't need to store the header as compressed binary data, and you don't have to write the encoding header bit-by-bit. It's fine to just write out normal ASCII characters if you like. Or if you want to come up with a more efficient compressed way of representing your header, that is fine, too.

If you're stumped about how to write out a reasonable header, you can just use the following suboptimal algorithm to write out a mapping of character counts as follows. If you create a mapping of character counts from the original uncompressed file, you could regenerate the encoding tree from that, which would give you the information you need to uncompress the file. For example, for our ab ab cab example, a mapping of characters to frequencies would be the following (the keys are shown by their ASCII integer values, such as 32 for ' ', and 97 for 'a', and 256 for EOF, because that is the way the map would look if you printed it out):

{32:2, 97:3, 98:3, 99:1, 256:1}

In C++, collections like maps can easily be read and written to/from streams using << and >> operators. So all you need to do for your header is write your map using << into the bit output stream first before you start writing bits into the compressed file, and read that same map back in using >> later when you uncompress it.

For very small input files like our example, the header can end up being larger than the compressed file's data; it can even make it so that the compressed file is larger than the original uncompressed file was! Oops! But this is okay as long as the cost of the header is not so bad relative to the overall file size for a larger file.

Now let's discuss the uncompress function in more detail. In this function you should do the opposite of compress; you should read the bits from the given input file one at a time, including your header packed inside the start of the file, to write the original contents of that file to the file specified by the output parameter. You may assume that the streams are valid and read/writeable, but the input file might be empty. The streams are already open and ready to be used; you do not need to prompt the user for filenames or open/close files. If your function allocates any dynamic memory on the heap, you must free it and not leak memory.

Freeing Memory:

You must make sure that your algorithm does not leak memory. To help ensure this, you must write one more function that accepts a pointer to the root of a Huffman tree as a parameter and frees all of the heap-allocated memory associated with that tree:

void freeTree(HuffmanNode* node)

Your code must free the root node and all nodes in its subtrees. There should be no effect if the tree passed is null.

The idea is that your other functions should call freeTree as appropriate to clean up after themselves. If any of your functions creates a Huffman tree but does not return it to the caller, then your function should also free the tree.

Development Strategy and Hints:

Do not use type char anywhere in your program. Declare all character variables as type int. This is needed for your program to function properly. If you use char, non-text files (e.g. images) won't work.

When writing the bit patterns to the compressed file, note that you do not write the ASCII characters '0' and '1' (that wouldn't do much for compression!), instead the bits in the compressed form are written one-by-one using the readBit and writeBit member functions on the bitstream objects. Similarly, when you are trying to read bits from a compressed file, don't use >> or byte-based methods like get or getline; use readBit instead. The bits that are returned from readBit will be either 0 or 1, but not '0' or '1'.

Work step-by-step. Get each part of the encoding program working before starting on the next one. You can test each function individually using our provided client program, even if others are blank or incomplete. Consider breaking each required step into sub-steps as appropriate and testing each sub-step in isolation.

Start out with small test files (two characters, ten characters, one sentence) to practice on before you start trying to compress large books of text. What sort of files do you expect Huffman to be particularly effective at compressing? On what sort of files will it less effective? Are there files that grow instead of shrink when Huffman encoded? Consider creating sample files to test out your theories.

Your implementation should be robust enough to compress any kind of file: text, binary, image, or even one it has previously compressed. Your program probably won't be able to further squish an already compressed file (and in fact, it can get larger because of header overhead) but it should be possible to compress multiple iterations, uncompress the same number of iterations, and return to the original file.

Your program only has to uncompress files compressed by your program. You do not need to protect against user error such as trying to uncompress a file that isn't in the proper compressed format.

The operations that read and write bits are somewhat inefficient and working on a large file (100K and more) will take some time. Don't be concerned if the reading/writing phase is slow for very large files.

Note that Qt Creator puts the compressed binary files created by your code in your build_Xxxxxxx folder. They won't show up in the normal res/ resource folder of your project.

Frequently Asked Questions (FAQ):