CS 112 A1 - Fall 2004: Homework 4

Due Tuesday, November 9, 11:59 P.M.

Reading: Chapters 8, pages 317- 333 and 344-360, and chapter 10, pages 429 - 470

Please keep in mind the policy on collaboration.

Introduction

The Database

The database will contain records which hold the following:

• First name (secondary key);
• Last name (primary key);
• Phone number; and
• Email address.

Each of these will be a character string. The records will be ordered by primary and secondary keys as in the phone book, i.e., to compare two records A and B to determine their relative order, you would first compare A.lastname and B.lastname using, say, strcmp() from the string library. If these names are not identical, then the ordering on the names determines the ordering on the records. If the names are identical, then you must look at the first names to try to order the records. This is just like the ordering in the phone book, except we will only use the first and second names. You will have to write a function recordCompare which takes pointers to two records and returns -1 if A < B, returns 1 if A > B, and returns 0 if the keys of the two records are equal.

When the program runs, it loads the data from a file into an S-Tree (described below). The root pointer to the tree should be private data in a class called STree, with the appropriate interface functions, as defined in the next section.

Commands

When you execute your program, it can either take its input from the terminal as you type it or you can input the commands from the datafile. In either case you should first use "add" commands to build your database and then use other commands to manipulate and print the database. Here is a sample datafile you can use. If you use this file to test out your program you should add commands at the end of the file to test the various data operations as described below. The last command should be "quit". The program accepts user commands to perform the following operations:

• add a new person to the table with his/her phone number and email address. The command add will be followed (not necessarily on the same line) by the first name, last name, phone number, and email address. You should not prompt for these strings, but simply assume that the user will enter them in this order. (See the example session below.) If the person is already there (i.e., there is already an record in the database with the same first and second names) print an appropriate message and ignore the request to add a new record.
• remove the record from the database with a given first name and last name. If that record does not exist, do nothing, but print out a warning message
• print the first name, second name, phone number, and email address for a particular person; this command will be followed by the first name and then the last name, as keys. If the person is not in the table, then print an appropriate warning message.
• list the contents of the entire database; this command will print the names, phone numbers, and email addresses for everyone in the database, in order (as specified above). In other words, this would be a lexicographic listing such as you see in a phone book.
• quit use the list command to print out the whole database and then quit the system.

csa% a.out <  hw4.datafile.txt  

Welcome to the Automated Phone Book System.
Loading database from hw4.datafile.txt.....

Enter one of the following commands:

     add <first name> <last name> <phone number> <email> 
                   - Add a new individual to the phone book
     remove <first name> <last name>
                   - Remove the data for an individual       
     print <first name> <last name> 
                   - Print out the phone number and address of an individual
     list          - List the entire phone book in order
     quit          - Quit the system

Commands can be abbreviated by their first letter (e.g., ``a'' for ``add''). 

phonebook> p bill farmer                          // Note: the first three entries were already in the DB
Name: bill farmer 
Phone: 8921
Email: farmer@cs

phonebook> p stan sclaroff
Name: stan sclaroff
Phone: 8988
Email: sclaroff@cs

phonebook> p glenn gould
Name: glenn gould 
Phone: 8111
Email: ggould@cs

phonebook> add wayne snyder 8925 snyder@cs
Added wayne snyder.

phonebook> a robin williams 
534-8923 mork@universe.com
Added robin williams.

phonebook> a wayne snyder 3283 snyder@cs
wayne snyder is already in the phone book. 

phonebook> a alan turing 1212 
    turing@heaven.com
Added alan turing. 

phonebook> a donald knuth 9872 don@berkeley.edu
Added donald knuth.

phonebook> a jane snyder 9873 jsnyder@acs.bu.edu
Added jane snyder.

phonebook> s snyder wayne
Unknown command ``s'', try again. 

phonebook> p snyder wayne
snyder wayne is not in the phone book.

phonebook> p wayne snyder
Name: wayne snyder 
Phone: 8925
Email: snyder@cs

phonebook> r stan sclaroff
Removed stan sclaroff.

phonebook> p stan sclaroff
stan sclaroff is not in the phone book.


phonebook> list

====================================================
|                Phone Directory                   |
----------------------------------------------------
|    Name         |   Phone  |      Email          |
====================================================
| farmer, bill    |   8921   | farmer@cs           |
----------------------------------------------------
| gould, glenn    |   8111   | ggould@cs.bu.edu    |
----------------------------------------------------
| knuth, donald   |   9872   | don@berkeley.edu    |
----------------------------------------------------
| smith, jane    |   9873   | jsmith@acs.bu.edu  |
----------------------------------------------------
| turing, alan    |   1212   | turing@heaven.com   |
----------------------------------------------------
| williams, robin |   8923   | mork@universe.com   |
====================================================
phonebook> q
Thank you. 
(The whole list is printed here.)
Goodbye. I enjoyed serving your every whim.

The user input will come from the keyboard (standard input), and output should go to the terminal screen (standard output).

Data Structures

The database items will be stored in a structure which has the data fields firstname, lastname, phonenumber and email.

The nodes of the S-tree will have three fields They are a leftptr, a rightptr, and an entry field which holds a whole record. Each S-tree has a pointer ROOT which points to the root of the tree.

The basic idea of S-trees is as follows. An S-tree is a binary tree that is ordered but possibly not balanced. It has the ordering property that, for any node N and any ancestor M of N, if M has a key less than N it is in N's left subtree, and if M has a key greater than N it is in N's right subtree. (Note: In our case the keys are strings and less than mean less than in alphabetic order. )

We implement our S-trees by writing an STree class. You will need to write the class headers and the class implementation in files called hw4.tree.cpp and hw4.tree.h which will be submitted.

Algorithms

1. For the find algorithm, you should implement the tree search algorithm based on the ordering of the tree. That is, when you are at a node in the tree, you test if the data stored at the node is the record you are looking for (by looking at the lastname and then the firstname). If not then go the the left subtree (by using leftptr) if the key you are finding is less than the key in the node. If it is greater then you go to the right subtree. You can use the recordCompare function you write to do this.
2. The algorithms for add and remove should return a bool value indicating whether or not they were successful.
3. For add, you search the tree for the key (lastname and firstname) until you find a null pointer. You insert the new node below the null pointer. If you find the key while searching, then return "add failed, firstname lastname is already in the database."
4. Remove is a bit tricky. You again search for the node. If it is not found, then return "remove failed...". If you do find the node, say N, you need to take out N and rearrange the S-Tree. There are 3 cases to consider:

   (i) If N is a leaf, then just remove the node, and update the pointer of N's parent to null.

   (ii) N has one child. Then that child replaces N. To do this you need to change the pointer in N's parent that pointed to N to point to N's child. (And to do this you need to be able to find N's parent when you find N !)

   (iii) N has two children. Find the node M with the largest key in the left subtree of N. Replace N with M. Update all the pointers that need updating.

5. For list you need to print out all records in lexicographic order of the keys. We have seen in class that for a search tree ordered as ours are, you need to do the inorder traversal of the tree, printing out the information of the nodes as you go. You can use a recursive algorithm to do this or use a stack.

   I/O

   If you use an input file, the name of the input file should be read in on the command line. So "csa% a.out < hw4-datafile" should do it. A datafile you can use is mentioned above. The file will have each record listed, one per line, with white space between each of the strings, and a newline at the end, e.g., the file used in the above example looks as follows:

   add glenn gould 8111 ggould@cs.bu.edu 
   add  bill farmer 8921 don@berkeley.edu 
   add stan sclaroff 8988 sclaroff@cs    
   

   If you find it helpful, feel free to add a flag like "end" in a last line at the end of the data file just top make it easier to identify when you have finished with the file. The flag would tell the program to then go to the part of the program which prints out the welcome message.

   At the end, when the user types quit, the program would write out to the terminal all records currently in the S-tree, in the format just specified. You can just use the "list" command to do this.

   Note that the datafile just listed is not in alphabetical order. The reason for this is that it would be very inefficient to insert the names in alphabetic order as it would result in a very unbalanced tree.

   Use a makefile

   Write a make file for this program that will generate the executable ``h4'' for the program above. This will be a smaller portion of your grade for this homework, but still must be done correctly to get full credit.

   You should name your make file ``h4makefile'' and submit it as part of this homework. Since the utility make normally expects the makefile to be named ``Makefile'' or ``makefile'', you will have to run the make utility with:

   make -f h4makefile

   Use the make file from the discussion section page as a guide for this one.

   What to hand in

   Write your code in a main program in hw4.main.cpp and your library containing the new code for the S-tree in hw4.stree.cpp and hw4.stree.h. Submit this in a directory called hw4 using gsubmit, as usual. You should design your interface according to good object-oriented principles and provide the usual documentation for a human reader to easily understand your code. You will need to submit a file hw4.doc.txt for this.

   Also provide a script file hw4.script.txt showing that your program compiles and was able to handle the actions shown in the sample session above. You should list the data file before and after the run as part of the script, to show that you accurately create the proper data file.

   And finally you need to submit a makefile named hw4makefile.

    

   To submit hw4:

   1. You must be logged onto csa, and all files must be on the csa computer.
   2. Test that your program works by compiling it with g++.
   3. Check that your documentation and .txt files are readable by printing them out to the screen using the more command.
   4. Create a subdirectory called hw4, using the mkdir command.
   5. Copy all files to be submitted and no others into this subdirectory. The following files (and ONLY these files) should be in subdirectory hw4:
      • hw4.main.cpp
      • hw4.stree.h
      • hw4.stree.cpp
      • hw4.script.txt
      • hw4.doc.txt
      • hw4makefile

      To submit the assignment, cd to the directory containing the hw4 subdirectory and type:
      gsubmit cs112 -cp hw4
      This should submit the entire hw4 subdirectory.
      For further details on gsubmit, see the submit documentation.

      Good luck!