CSci 230 -- Data Structures and Algorithms
Project 2 -- File Compression, Inc.
Preliminary Due Date: Thursday, Oct. 15 at 11:59:59 pm
Program Due: Wednesday, Oct. 21 at 11:59:59 pm

Your successful completion of the ``Meows and Mutts'' project has resulted in a mild case of kennel cough and a referral to File Compression, Inc., a company specializing in software for compressing the size of files. Mr. Zvi Lepmel, Chief Technical Officer of FCI, has brought you in as a consultant to help with the implementation of a new product that performs a type of compression known as Huffman coding. (You can find some background information on this technique in your textbook in Section 10.1.2.)

Huffman coding requires the ability to manipulate binary trees, so one of the deliverables for this project will be the implementation of a binary tree class, similar to the generic container classes found in the C++ Standard Library. You have already met with the FCI team and sketched out the following interface for the class:

template <class T>
class binary_tree
{
public:
  binary_tree();
  ~binary_tree();
  binary_tree(const T &);
  binary_tree(const binary_tree &);
  binary_tree & operator=(const binary_tree &);

  friend class iterator;
  class iterator
  {
  public:
    friend class binary_tree;
    iterator();
    ~iterator();
    T & operator*() const;
    bool operator!=(const iterator &) const;
    bool operator==(const iterator &) const;

    iterator left() const;            // go to left child node
    iterator right() const;           // go to right child node
    iterator parent() const;          // go to parent node
    bool is_root() const;             // true if at root
    bool is_leaf() const;             // true if at a leaf
  };

  iterator begin() const;
  iterator end() const;
  T & root();

  void combine(binary_tree & t1, binary_tree & t2);
};

In addition to the usual constructors and destructors, the binary tree class also contains an iterator class for traversing over the nodes in the tree. Binary tree iterators support some of the normal iterator operations, plus some special functions for traversing binary trees. Additional member functions of the binary tree class provide iterators to the ``begin'' (root) node and a special ``end'' node not in the tree, and fetch the value stored in the root node of the tree.

Here is an example of how the binary tree class and its iterator class is intended to be used:

// Print out contents of tree using an ``in-order'' traversal.
void inorder_traversal(const binary_tree<int>::iterator & i)
{
  if (i.is_leaf())
  {
    std::cout << *i << " ";
  }
  else
  {
    inorder_traversal(i.left());
    std::cout << *i << " ";
    inorder_traversal(i.right());
  }
}

void main()
{
   binary_tree<int> tree;

    ...   // put some stuff into the tree

   inorder_traversal(tree.begin());
}

One member function deserves special mention. Since a binary tree container will be made up of dynamically allocated nodes, it is possible to ``combine'' two binary trees as the children of the root node of a third binary tree in constant time (this is similar to how STL lists can be spliced together). A special function is provided in the header and should be implemented by you to do exactly this. The nodes in t1 become the left subtree, and the nodes in t2 become the right subtree of the third tree, (represented by *this). The ``root'' tree must consist of only a single node, and both t1 and t2 are empty afterwards. This sounds complicated, but remember it will be done in constant time!

With the help of this binary tree class (and some useful standard library components), a class for performing Huffman encoding and decoding can be implemented. The interface for this class is quite simple it provides two member functions, one to encode and one to decode. Both use standard library streams for their input and output.

class huffman_codec
{
public:
  void encode(std::istream &, std::ostream &);
  void decode(std::istream &, std::ostream &);
};