On Tue, 20 Feb 2001, Student K wrote:

> Hi Lucia,
> 
> I hope your break is going well.
> 
> I have a few questions regarding Assignment #2 which I hope don't give
> too much away, but I know how the algorithms for the programming
> questions work. Is simply implementing them (obviously). Just a few
> things I need to know:
> 
> - For the Huffman question: Unlike in Encode, in Decode we read in bits
> (1's and 0's). Now, if we did this on paper, like in the written
> question, we'd traverse through a tree. Do we do this in the program?
> Because I can't find the tree in the program to traverse through. If
> there is one in there, can you direct me to where (i.e. which program
> and line?)

IBitStream takes care of reading bytes and sending bits to you.
Methods  get and eof are enough. If the first byte in the file is a byte
representing number 7 and the second number 1, IBitStream will make sure
you will get the bits correctly, in order, like:
0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0 ,0, 0, 0, 0, 1.
OBitStream did the oppositte when packing the bits as bytes to be
sent to the file at time of encoding.
All this should be transparent to you, and all you have to do to
read bits is to call "get" from IBitStream class.
 
Where is the tree?
HuffmanDecoder is a derived class from HuffmanObject.
HuffmanObject contains a member HuffmanTree* tree;
This is the pointer to the root of the tree. Upon creation of
the object dec of class HuffmanDecoder in the main program,
the constructor for both HuffmanDecoder and HuffmanObject were
invoked and the tree was built.

So, inside HuffmanDecoder::decode method, the member "tree"
is available for use by you.
Now - how to traverse the tree?
Take a look at HuffmanTree (indeed this class should have been
called HuffmanTreeNode, since it stores one node of the tree).
In huffmantree.h you can find, HuffmanTree has the following
quite useful memebers (:-)) ):
getLeft, getRight, getHuffmanCharacter, and isLeaf

The tree node (HuffmanTree) stores a pointer to left
and right nodes, and if it is  a leaf, it stores the corresponding
character.
Now, you are ready to travel trhough the tree:
start at the root, and depepdning on the bit you got, go right
or left. Whenever a leaf is reached you have decoded one letter 
(how to get the letter? use getHuffmanCharacter method for the 
leaf node).
As you keep decoding, you will be writing the decoded letters
to the output file.

> 
> - This is sort of a continuation to the first question, but could you
> give me a quick clarification to what's going on in the get function in
> IBitStream? What confuses me is the bits processed. I see it's checking
> if the number of bits is 8, so does this mean the encoded.bin file may
> not look the same as something on paper. In other words, if you tried
> decoding 101, in encoded.bin would you get 00000101 or something like
> that? You can see the problem I'm having is with IBitStream and the
> input, because, unlike simply traversing through a tree, I don't know
> when to stop, i.e. when there's a leaf. Yes, there's a IsLeaf function,
> but I can't find that tree still...
> 

I hope this is now clear based on my previous explanation.

> - Oh, one other thing for Huffman: If we do traverse through a tree, how
> do we return to the top (after reaching a leaf)?
> 

Let's say that you want to go left,right and left from the root and
then go back to the root.
HuffmanTree *p;

p = tree; // now p points to the root of the tree
p = p->getLeft();   // p points to left child of the root
p = p->getRight();  // p points to right child of left chilf of the root
p = p->getLeft(); // p points to left child of right child of left child
                  // of root
p = tree; // p is now pointing to teh root of the tree again

> Okay, for the Password Question:
> 
> - I think I understand seekg and seekp, but I'm not sure how to access
> lines (instead of bytes or chars). I guess it's the same as accessing
> simple records, but the only way I could see us doing this is to have
> fixed length of records, but I don't think it's the correct method.
> Could you give me some advice on how to do this? For this reason, I
> don't know how to access the middle record (when using the binary search
> method).

The records are of fixed length. Please, discover the correct length of
the records, taking into account the fact that you have extra characters
to indicate end-of-line. This is a constant trhough your program.

You have two main tasks, which BTW are illustrated in the book page
224.
If you look at class FixedRecordFile, you see that all you
need to do in order to use the binary search procedure at the top
of the page is to implement:
int NumRecs();
int ReadByRRN(RecType & record,int RRN); 

To discover the number of records:
- position yourself at the end of the file (with seekg)
- discover the current byte offset (with tell)
- divide the byteoffset by the size of a record

To read a record by relative record number (ReadByRNN):
- position yourself at the correct byte offset (using seekg)
  how to get the correct byte offset? you should be able to
  calculate using the record size and the RRN.
- read a record as usual (you are at the right position).

Before trying to do the binary search itself,
experiment with the program, testing if your ReadByRRN works
correctly or not; adjust your record size correctly, etc.
A good programming practice is to test individual methods before
using them. Once you program ReadByRRN, test it from the main
program trying to read the first, the 10th, the last record,
and see if it's working as it should. Once this is working,
the binary search will be very simple - you can even follow the
book algorithm (with corrrections).
 
Beware of the folloing two mistakes in the binary search at the top of
page 224:
 guess = (high+low)/2;  // "+" rather than "-"
 if (obj.Key() > key) ....   // ">" rather than "<"

> 
> - Also, can we use a fixed number of records in the program? As you can
> see, I'm using a method similar to the one in the text (in the binary
> search section).
> 

Yes. That is what I have already explained above.

> If you could help me out a bit I would really appreciate it, as I can't
> make it to your office hours on Friday. If they are not clear please let
> me know. I appreciate your feedback as you've done it in the past.
> 
> My one midterm question I have is if there will be a midterm review
> class (next week).

Yes. The last lecture in the week is going to be a review.
In the first lecture, I will ask you to bring questions or problems
to be solved in class in the following lecture. 
The last lecture of the week (Thursday or Friday, depending on the
group) will do: quick review of the course material up to now,
answering questions & solving problems proposed by you.

Lucia Moura