Lab 1: phone book

First, download the files medium-book and big-book. These contain (randomly-generated) phone books for your program. medium-book contains 10000 names and phone numbers and big-book contains a million.

If you run shuf -n 10 medium-book or shuf -n 10 big-book, it will print out 10 random names and numbers from the phone book. You can use this when testing the program.

Then compile Lab1.java in the normal way, and run it, passing either medium-book or big-book as a parameter:

If you are using Eclipse, you should instead put medium-book and big-book in your project directory (the directory containing src), and then specify either medium-book or big-book as the parameter under Run → Run Configurations… → Arguments.

You will be able to type in someone’s name and see their phone number. Unfortunately, the phone book doesn’t work yet. Type quit to quit:

Looking in Lab1.java, you will find a class called PhoneBook. It provides the following methods, but at the moment none of them are implemented. Your job is to implement them.

The main phone book program reads the phone book file, and for each entry it calls add(). When the user types in a name, it will call find(). The phone book file is in alphabetical order, as required by the comment for add() above.

The add() and find() methods both refer to a class called Person. This class represents a person in the phone book. It has two fields, name and phone:

Your task is to implement PhoneBook.

You will use a dynamic array to store the phone book. So add() will add a person to the dynamic array and size() will return its size.

In add(), you must check that the entries you get are in alphabetical order. In other words, compare the name of the person you are adding with the name of the last person you added. If they are in the wrong order, throw an IllegalArgumentException.

For find(), use a binary search. This works because the phone book is in alphabetical order.

Do not use the Java collections API! For example, do not use an ArrayList to implement the dynamic array: instead, you need to use a plain Java array and write the code for the dynamic array yourself. The same applies to the binary search: write it yourself!

To sum up:

First try the program out on medium-book and big-book. (The section "Running the program" tells you how to find out which names are in the phone book.)

You must also test yourself that the PhoneBook class is correct. Do this by writing some tiny (0-5 people) phone books and testing your program on them. (Most bugs can be found by testing on small inputs.) Think carefully about what you need to test to make sure that PhoneBook does everything it should. Open the file medium-book in a text editor to see how to write your own phone books.

Finally, there is an automatic testing program you can run. Download Lab1Test.class and put it in the same directory where your .class files are. Then open a terminal, change to that directory and run java Lab1Test. This will run some tests and report whether they passed or failed.

You should submit Lab1.java and the phone books that you wrote for testing. You should also say why you think your tests make sure that the PhoneBook is correct. Submit your code using the Fire system.

Your code should be well-commented. Submissions that are poorly commented or hard to read may be summarily rejected!