\documentclass{article}
\usepackage{hyperlatex}
\newcommand{\hlink}[3]{\xlink{#1}{#2}{#3}\texonly{\footnote{#2}}}
\newcommand{\tild}{\~{}}
\input{techexp}
\texonly{\textheight 9in}
\texonly{\topmargin -0.5in}
\texonly{\oddsidemargin 0.0in}
\texonly{\textwidth 6.5in}
\newcommand{\HlxIcons}{}

\htmltitle{CSCI 230 --- Data Structures and Algorithms --- Project 2}
\htmladdress{~}
\htmlattributes{BODY}{BGCOLOR="#ffffe6"}
\setcounter{htmlautomenu}{2}
\htmlonly{\setcounter{secnumdepth}{0}}
\setcounter{htmldepth}{0}

\title{CSCI 230 --- Data Structures and Algorithms\\
       Project 2 --- File Compression, Inc. }

\author{~}

\begin{document} \maketitle

\subsection*{Submission Deadline: Wednesday, Nov.\ 10 at 
\mbox{11:59:59~pm}}

Your successful completion of the ``Object Oriented Airlines''
project has resulted in union strike
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
{\em 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 the main deliverable 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:
\begin{verbatim}
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);
};
\end{verbatim}

%% I think brief examples of how the iterator is declared and used
%% from outside will help enormously.  This will allow students to tie
%% this notion of an iterator to what they have seen before.

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:
\begin{verbatim}
// 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());
}
\end{verbatim}

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).
%%  Minor change below
A special function is provided in the header and should be implemented
by you to do exactly this.
The nodes in {\tt t1} become the left subtree,
and the nodes in {\tt t2} become the right subtree
of the third tree (represented by {\tt *this}).
The ``root'' tree must consist of only a single node,
and both {\tt t1} and {\tt 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.
\begin{verbatim}
class huffman_codec
{
public:
  void encode(std::istream &, std::ostream &);
  void decode(std::istream &, std::ostream &);
};
\end{verbatim}


\subsection*{Encoding Algorithm}

The Huffman encoding algorithm is as follows:
\begin{enumerate}
\item Construct the encoding tree:
\begin{enumerate}
\item Count the frequency of each byte value in the input
(note that there are~$2^8 = 256$ possible byte values).
\item Construct an initial binary tree for each byte value,
weighted by its frequency.
\item Repeat until there is only a single tree remaining:
combine the two trees with the smallest weights into a
new tree, with weight equal to the sum of that of the two combined
trees.
\end{enumerate}
\item \label{get_code_from_tree} Construct the encoding table: 
for each byte value in the input, determine its code
by tracing from the leaf node representing that value to the 
root of the tree. 
(Note that this will give you the code {\em backwards},
and you will need to reverse it.)
\item Write out the compressed data:
\begin{enumerate}
\item Write out the encoding tree (it is necessary to decode the
file later).  See below for a technique to do this.
\item Write out the count of characters in the input.
\item Write out the compressed data.
\end{enumerate}
\end{enumerate}

\subsection*{Decoding Algorithm}

To decode a file:
\begin{enumerate}
\item Read in and reconstruct the encoding tree (see below).
\item Read in the character count.
\item While there are characters left to decode:
\begin{enumerate}
\item Start at the root of the encoding tree.
\item While not at a leaf node, read a bit from the input and
go to the left or right child as appropriate.
\item Output the character in the leaf node.
\end{enumerate}
\end{enumerate}

\subsection*{Encoding Tree Output}

Writing out the encoding tree is fairly straightforward.
First, we can ignore the weight information,
since it is only used in the initial construction of the 
tree from the frequency data.
Also, we can take advantage of the fact that every node
in the tree is either a leaf or has exactly two children.

The algorithm to write out the tree is recursive:
\begin{enumerate}
\item If the root node of the tree is itself a leaf:
\begin{enumerate}
\item Write out the byte value stored in the leaf, preceded by the
character ``.'' (period).
\item Return.
\end{enumerate}
\item Otherwise:
\begin{enumerate}
\item Recursively write out the left subtree, surrounded by parentheses.
\item Recursively write out the right subtree, surrounded by parentheses.
\end{enumerate}
\end{enumerate}

\subsection*{Encoding Tree Input}

Reading in and reconstructing the tree is also recursive:
\begin{enumerate}
\item Read a character byte.
\item If the character is ``.'' (period),
then we have a leaf:
\begin{enumerate}
\item Read the next byte, and create a new tree
with that value in its node.
\item Return the new tree.
\end{enumerate}
\item Otherwise, the character must be a left parentheses,
indicating we have two subtrees:
\begin{enumerate}
\item Recursively read in the left subtree.
\item Read in and skip the closing right parentheses and the 
next left parentheses.
\item Recursively read in the right subtree.
\item Read in and skip the closing right parentheses.
\item Create a new tree combining the left and right subtrees,
and return it.
\end{enumerate}
\end{enumerate}



\subsection*{Program synopsis and input format}

The program will be run twice with the command-lines
\begin{verbatim}
    huffman encode input-file compressed-file
    huffman decode compressed-file output
\end{verbatim}
The decoded output will be compared to
(and should be identical with) the input file.
You can use any file for sample input (even binary files).


\subsection*{Notes, hints, and assumptions}

\begin{itemize}

\item Engineers at FCI have already implemented a class for
reading and writing individual bits,
as well as a main program to test your classes.
In addition they have completed most of the Huffman encoding 
and decoding routines.
The code can be found in:
\begin{center}
\hlink{Project 2 Auxiliary Files Directory}{http://www.rpi.edu/dept/cs/cs230/public/projects/project2/}{}
\end{center}
This directory is also accessible directly on the RCS file system
\begin{verbatim}
     /dept/cs/cs230/public/projects/project2
\end{verbatim}
Be sure to carefully look over the code and make sure you understand it.

You will need to complete certain parts of the Huffman encoding/decoding
algorithms in the file {\tt huffman\_codec.cpp}. Search for the
string ``COMPLETE'' in the source code and follow the comments.

\item The {\tt bit\_unpacker} class provides a function that returns
individual bits from a stream:
\begin{verbatim}
 bool read(std::istream & in);
\end{verbatim}
The {\tt 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):
\begin{verbatim}
 void write(std::ostream &, const std::basic_string<bool> &);
 void flush(std::ostream &);
\end{verbatim}

\item It is easiest to deal with strings of bits using the following type:
\begin{verbatim}
     std::basic_string<bool>
\end{verbatim}
This type works just like the {\tt std::string} class you have used
before (including working with standard library iterators and algorithms).

\item You will need some way to keep track of the ``forest'' of
binary trees you are combining to form the final encoding tree.
To do this, use the {\tt priority\_queue} class in the standard library.
Most of this has been done for you already by the FCI engineers.

\item 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.

\item The standard library component {\tt pair} will be useful
for holding two items (the weight and the byte value)
in a binary tree node.

\item 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?

\item If you are using Microsoft Visual~C++, you may get some
warnings like the following:
\begin{verbatim}
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'
\end{verbatim}
These are in the standard library and can be safely ignored.

\end{itemize}


\subsection*{Implementation environment}

Your program must compile and run using the Visual C++ developement environment. 


\subsection*{Submission dates and guidelines}

The submission deadline is Nov. 10 at
11:59:59~pm.  Projects submitted later than this will NOT be
accepted for credit.
Detailed project submission guidelines will be posted on the course web site.


\subsection*{Grading criteria}

The program will be graded 25\% for a clean compilation, 40\% for
correctness of the program, and 35\% for program structure.
Criteria
for program correctness may be discerned from the foregoing
description and will solely be based on the output from your program.
Program structure includes class organization, member function design,
code readability (indentation, variable names, etc.), and commentary.
There should be comments describing the purpose of each class and the
member functions and member variables.  The comments about each class
\textbf{must} also include a discussion of the flexibility of the
class design and how well it will support future changes.  Keep other
comments, especially within the body of each function, short and
concise.  Avoid comments that just state in English what is obvious from the
code.  One bad example is
\begin{verbatim}
   i ++;   //  increment i
\end{verbatim}


\subsection*{Academic integrity}

Students may discuss the class and algorithm design.
All code must be implemented by the student alone.
Sharing of code among students is expressly
forbidden and will be detected by code comparison tools.  Projects
from all six sections will be graded together by the TAs.

\end{document}
