Notes, hints, and assumptions

• It is easiest to deal with strings of bits using the following type:

       std::basic_string<bool>
  

  This type works just like the std::string class you have used before (including working with standard library iterators and algorithms).
• Engineers at FCI have already implemented a class for reading and writing individual bits, as well as a main program to test your classes. The code can be found in

       /dept/cs/cs230/public/projects/project2
  

  The bit_unpacker class provides a function that returns individual bits from a stream:

   bool read(std::istream & in);
  

  The bit_packer class provides two functions, one that writes a string of bits to a stream, and a second that should be used after you have processed the last bit to ensure all bits are actually written (this is necessary since the system can only write bytes, or groups of 8 bits, at a time):

   void write(std::ostream &, const std::basic_string<bool> &);
   void flush(std::ostream &);
  

  Do not mix normal I/O and bit I/O on the same stream!

• You will need to ``rewind'' the input stream after you have counted the frequency of the byte values so that you can compress it. To do this, use the following to member functions:

            std::istream & in;
            in.clear();
            in.seekg(0);
  

• You will need some way to keep track of the ``forest'' of binary trees you are combining to form the final encoding tree. Obviously, you should use a standard library container. Of the two containers we have studied (vectors and lists), which one is more appropriate for this project? Think about the types of operations you will be performing and how long they will take with each container.

  If you are comfortable with STL and would like to try something more advanced, investigate using the priority_queue class in the standard library for this task. You will need to use a function object to tell it how to compare the weight of two binary trees. Use of this class is strictly optional; if you have trouble getting it to work, just use a list or vector.

• Remember that standard library containers copy the values that they hold. It will be very expensive to copy an entire binary tree each time it is added to or removed from a container, so store a pointer to the tree instead.
• The standard library component pair will be useful for holding two items (the weight and the byte value) in a binary tree node.
• In step 2 of the encoding algorithm, you will need to be able to quickly locate the leaf node for a given character. This is best done with an array of iterators.
• Be careful using the << and >> operators; they may not accurately read and write byte values. Use the put and get methods instead (see the implementation of the bit_packer and bit_unpacker classes). Use the << and >> operators only when you need to do some type of conversion, for example when writing out the integer count of the number of characters.
• What happens if the file being compressed is empty? What if it contains only a single byte (perhaps repeated over and over)? What should the compressed file look like for these cases? Does your final program handle them correctly?
• If you are using Microsoft Visual C++, you may get some warnings like the following:

  c:\program files\devstudio\vc\include\iosfwd(83) : warning
  C4804: '<' : unsafe use of type 'bool' in operation
  c:\program files\devstudio\vc\include\iosfwd(127) : warning
  C4305: 'return' : truncation from 'const int' to 'bool'
  

  These are in the standard library and can be safely ignored.