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:
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 &);
};
The algorithm to write out the tree is recursive:
huffman encode input-file compressed-file huffman decode compressed-file outputThe 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).
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 &);
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).
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.
This project will require a number of files, so submission will require some extra steps. Make sure that every file that you submit has your name, section meeting time, and instructor name in a comment at the top.
Your submission must include a text file called readme.txt This file must include your name, section meeting time, and instructor name. In addition, it must include a list of all the inplementation files and any special instructions that the TA will need to know in order to run your program.
Example:
Snoop Doggie Dog Section 8: Thursday, 6 PM Eric Breimer binary_tree.h huffman_codec.h huffman_codec.cpp main.cpp To run the program type huffman encode infile compressed-file or huffman decode compressed-file outfile
Create a tar file. Tar is an acronym for Tape Archive. To create
a tar file, use the tar command with two flags c (for create)
and f (for file), followed by the file name of the tar file (it
should have a .tar suffix) followed by the names of all of the
files that you want to send. For example the following command:
tar cf temp.tar myfile.h myfile.cpp readme.txt
creates a tar file called temp.tar which contains three files,
myfile.h, myfile.cpp and readme.txt.
You will need to check to make sure that the tar file is correct. The
best way to do this is to copy the tar file to another directory and run
the following command:
tar xf temp.tar
After running this command, the files myfile,cpp, myfile.h
and myfile.rc will be in the new directory. Here are the unix
commands to do this:
mkdir newdir cp temp.tar newdir/temp.tar cd newdir tar xf temp.tarThe first line creates a new directory called newdir, the second copies the tar file to the new directory, the third line makes newdir the current directory, and the fourth line extracts the files.
Use the unix copy command cp to copy your submission. For example:
cp temp.tar /dept/cs/cs230/project2/section8/snoopd.tar
Please, make sure you copy your tar file into the subdirectory for your section and verify that the name of your tar file is your RCS login. You will not recieve credit for your submission unless you follow the submission guidelines.
Your binary tree must implement the functions described in the binary_tree.h
file that was given. Although your code may not be completely correct and
may not compile, you can still earn the full 25% (given a valid effort).
Your code must attempt to implement the huffman coding algorithm.
You must properly use the binary tree to generate encodings. Although your
code may not be completely correct and may not compile, you can still earn
the full 20% (given a valid effort).
Your code must attempt to implement the huffman decoding algorithm.
You must properly use the binary tree to decode the compressed text. Although
your code may not be completely correct and may not compile, you can still
earn the full 10% (given a valid effort).
Failure to follow the coding guidelines will result in up to a 15%
penalty. You can not get credit for the coding guidelines unless you've
made a valid attempt to implement all the components (binary tree, encoding
algorithm, and decoding algorithm).
Even if you program does not encode or decode properly, you can
still earn up to 10% for successful compilation. You can not get credit
for compilation unless you've made a valid attempt to implement all the
components (binary tree, encoding algorithm, and decoding algorithm).
Using the encode option, your program should generate a compressed
file that is smaller than the original input file (assume that you are
given a reasonably sized input file; some small files will not compress
well). Then, using the decode option, your program must generate the original
input file. Proper encoding can not be verified without proper decoding.
If your program encodes and decodes properly, you earn an automatic 20%