CPS 100, Fall 2000, Huff FAQ

1. December 5 Reading a tree in the header

   If you're writing/reading a tree to store header information (using a pre-order traversal) you must be careful. You CANNOT write code like this:

      Tree * read(ibstream& input)
      {
          int val;
          input.readbits(1,val);
          if (val == 0) {         // internal node
            return new Tree(999, read(input), read(input));
          }
          // more code here
       }
   

   This is the right idea, but C++ and C don't guarantee the order in which arguments to a function are evaulated. THis means the two recursive calls might Not be evaluated in left/right order.

   Instead you must write code like this:

      Tree * read(ibstream& input)
      {
          int val;
          input.readbits(1,val);
          if (val == 0) {         // internal node
            Tree * left = read(input);
            Tree * right = read(input);
            return new Tree(999, left,right);
          }
   

2. November 20 Deleting a file from a C++ program

   The C/C++ system call unlink will remove a file specified by a string as an argument:

   string filename = "foo.cpp"; unlink(filename.c_str()); The file whose name is foo.cpp will be removed as a result of executing the function call to unlink

   To use unlink you need

   #include <unistd.h>

3. November 20 Writing characters when unhuffing

   To write characters/8-bit chunks when unhuffing, use an obstream and writebits:

   ob.writebits(BITS_PER_CHAR, value); where value is an int/8-bit chunk stored in a leaf of a Huffman tree.

4. November 20 Are files the same?

   The Unix command diff tells if two files are the same:

   diff foo.cpp foo.cpp.hf If nothing is printed when running diff the files are the same. If something is printed, it will tell you waht the differences are for text files. For binary files the output will just be "the files are different".

   If you compress then uncompress an executable, it will be the same file if you do things correctly, but you won't be able to execute it since it won't have its execute permission set. To do this run the chmod command:

   chmod +x filename Will add "execute permission" to the file named filename

5. November 20 pseudo-eof

   You must create a node, with count/weight 1, that contains PSEUDO_EOF (see globals.h) as the info field of the node, and add this node to the collection of nodes used to make the Huffman tree. You create this node explicitly, it's not created automatically from your counts.

   Once created, it will become part of the tree and thus have a zero/one encoding derived from the root-to-leaf path.

   You must write this encoding after compressing all the "real" characters (when you re-read the file being compressed). You must write the encoding explicitly.

   Your unhuff program will know what the encoding of PSEUDO_EOF is -- see the assignment write-up for how to use the pseudo-eof value when uncompressing.

6. November 20 Viewing raw data

   You can "see" the raw data in a file using the od command (octal dump). One version of use is:

   od -t uC rawdata | more This will show the file named rawdata one byte at a time, with 16 bytes per line. The first number on each line is the offset (in base-16) in the file, i.e., 16 numbers, followed by another 16 numbers, etc. The 16 numbers on each line are printed in unsigned decimal (that's the u that's an argument in the od command). The C argument following the u means use a character or 8 bits. Changing the C to an S will show 16 bits at a time (a short is 16 bits, the S is for short). Type man od for more details.

7. November 20 Bit operators

   If you use the bitwise and operator & to determine if a bit is on, be sure to parenthesize:

   int val; input.readbits(BITS_PER_WORD, val); if ( (val & 1) == 0) { // read a 0 bit, act accordingly }

   Note that writing the following will NOT work:

   if (val & 1 == 0) Here the == has higher precedence than the & so this is compiled as follows since 1 == 0 is false or zero if (val & 0) This is ALWAYS 0 or false.

8. November 20 Using tpqueue with pointers

   If you use a tpqueue (in tpq.h) you may need to declare a comparer object. For an example see tpqtest.cpp. Note the use of the typedef in that code for Thing *, the alias Thingptr is used. If you DON'T use this, you'll probably make a mistake in your compare function. It should have this prototype:

   int compare(Thing * const & lhs, Thing * const & rhs) const

   In particular, look where the const is, NOT before Thing, hence the typedef alias to make things easier.

9. November 20 Declaring a priority queue

   It's a little tricky to declare a priority queue in the private section of a class if you're going to construct it from a a comparer object (like the code in tpqtest.cpp and pqdemo.cpp.)

   Most likely, you'll use the priority queue in some member function that creates a tree. So you can declare the pq in that function, with the comparer class in the .cpp file for the class. Supose you have a class HuffTree

   void HuffTree::makeTree(..) { ComparerObjectThingy comp; tpqueue<Tree *> pq(comp); // code here to create huffman tree using pq // using standard huffman algorithm for tree creation myRoot = pq.getmin(); // get root, only item left }

   If you really need to declare the priority queue as a private data member you might want to look at the implementation of tpqueue in tpq.h and tpq.cpp to see how the static comparer object is created and used.

   Alternatively, you can define a Comparer object in your .cpp file, NOT inside a class, but global to the file:

   ComparerThing ct; HuffClass::HuffClass() : myQ(ct) { }