Cosc 215 - Program #6

Counting Animals

Due: 4/22/08
Points: 50

For your final assignment, you are to create a database for a zoo that will keep track of the number of animals on hand. For each animal name (aadvark, camel, horse, etc.) there is only one count. The database will have three functions:

void add(String a): Adds one animal with the name "a" to the database.
void delete(String a): Deletes one animal with the name "a" from the database.
int getCount(String a): Returns the number of animals with the name "a" currently stored in the database.

The names of the animals will taken from this list of animal names. Note that all animal names are in lower case and do not contain spaces.

You should write a main method that reads in commands from standard input and executes the corresponding operation. Commands are all of the form <letter><animal> where <letter> is one of A, D, or C (for Add, Delete, and Count, respectively), and <animal> is the name of the animal. There will be one command per line and there is no space between the letter and the name. After reading in a Count command, the program should print, to standard output, the count of the animals with that name currenly in the database. At the end of the program run, the program should also print out the number of collisions that occurred during the run of the program (see below).

Additional requirements

Your program must use a hash table to implement the database and the hash table should use either linear probing, quadratic probing, or double hashing as the method for resolving collisions. The program should print out the total number of key collisions that occurred during the add, delete, and getCount operations. You should be creative in writing your own hash function. Try to minimize the number of collisions generated by your hash function. The size of the hash table should be reasonable for the list of animal names.

Example

For example, given the input file zooinput.txt, the program should produce zoooutput.txt. The number of collisions in the output will depend on your hash function and table size.

If you have questions or comments, email me at simon@mathcs.duq.edu