Copyright ©  T. H. Merrett

308-420A           Secondary Storage Algorithms and Data Structures       Week 6

				  Assignment 6

The telephone book is represented as two files, a full trie indexing the phone
numbers (/course/cs420/data/triePhone), and a data file containing the other
fields (/course/cs420/data/dataNameAddr).

Write a Java program to search the trie and retrieve the corresponding data
for the phone numbers 2883502, 2883508, 3364566, 8445663 and 8453932. (You
may treat each of these as a separate request.)

Each file is a  RandomAccessFile. The data file consists of blocks of records
containing the fields  Name  (40 bytes) and  Address  (33 bytes). The record
and blocksize information (73 bytes and 100 records/block) are stored in the
index trie. Your program should use this stored information, and read a full
block at a time into a buffer, extracting individual records from the buffer.

The trie indexing the phone numbers has two main components, with numeric
parameters before and after each. The first component is the set of pages
containing the bitpairs that represent the nodes of the trie. The second
component is the indexing information for these pages: the top counters,
the bottom counters, the numbers of nodes, and the addresses on disk. Here
is the layout.

	byte*	type	meaning
	   0	int	number of pages in the trie (nTrie=42)
	   4	int	blocksize of trie pages in bytes (BTrie=64)
	   8	short	height of trie in page levels (h=4)
	  10	short	number of node levels per page level (t=8)
	  12	bp[]	nTrie blocks of BTrie bytes each: the trie
			("array of bitpairs, bp[]")
	2700	int	number of entries in page index (indexSize=46)
	2704	int[]	Tcount[indexSize]
	2888	int[]	Bcount[indexSize]
	3072	int[]	nodeCt[indexSize]
	3256	int[]	Addr[indexSize]
	3440	short	blocksize of data pages in records (bData=100)
	3442	short	size of data records in bytes (RData=73)

*Do not hard-code these addresses into your program, but calculate them from
 the stored parameters, and the number 12, which is the space needed by the
 first four numbers. (To confirm your understanding of the above layout, check
 that the stored parameters give the byte addresses listed, and answer the
 bonus questions at the end. Note that there is an extra Tcount and Bcount for
 the end of each level of trie pages; the corresponding values of nodeCt and
 Addr are -1, which can be used to detect the end of each level.)

Read the four arrays, Tcount, Bcount, nodeCt, and Addr, into main memory at the
outset and keep them there (736 bytes). Read the pages of trie nodes into main
memory only as needed (64 bytes each), but you may keep one page for each of the
four levels in main memory (256 bytes).

You will need to support the search logic you have been given for tries with a
mechanism to handle arrays of bitpairs, to compare bitpairs with bits in the
query, and to convert numeric query keys to bitstrings. Bits are stored eight
to the byte, and bitpairs four to the byte: use Java's byte masking operations;
but also take the time to build classes for bits, bitpairs, sequences of both,
and a cursor mechanism to keep track of where you are. Make the input and the
trie page data as close to arrays of bits or bitpairs, respectively, as you
can. It will require some time to do this, so start this assignment early.

The trie stores four bitpairs in each byte with the first pair in the least
significant two bits and the fourth pair in the most significant. Thus the mask
is updated as follows to scan the bitpairs in the correct order:
	mask= mask==192 ? 3 : mask*4.

For a bonus mark, answer the questions: what is the compression achieved by
storing the 885 phone numbers in triePhone instead of as 7-byte character
strings? 4-byte integers? 3-byte integers? What is the compression of the
whole file (including waste due to blocking the data)? Note that there are
9294 trie nodes, and hence bitpairs: if there were no wastage in either
trie pages or data pages, what would the compression be over the original
ascii file? What is the load factor of the 42 trie pages?

Optional: change your program to use internet sockets via HostClient, as you
did with Assignment 1. Compare the running times. Try this from home.

You may find the following four classes handy: bit, bitSeq, bitPair, bitPairSeq.
They are in ~cs612/java, along with the other java classes for the course.

Shared marks for shared work: assignments should be your own work; marks
for joint assignments will be divided by the number of collaborators.
But please feel free to work in groups to learn or for extra work that
is not for marks.