Implement a Table ADT to store university course information. You must use separate chaining to handle collisions by inserting new records at the front of the list. Your HashTable class must implement the TableADT interface:
interface TableADT { // calculate the hash code of the data and add it to the table public void add(Course data); // calculate the hash code of the data and look it up to see if it is in the table public bool isInTable(Course data); } public class HashTable implements TableADT{...}
Your program must read and parse a file containing course information. The file will be formatted as follows. Note that some courses/instructors names may be fictitous. But the formatting will be consistent. Some course names and/or instructor names and/or room numbers may be repeated for multiple courses. If two entries are exactly the same then do not add the second copy; they must have at least one property that is different.
BEGIN COURSE
Course Number
Instructor Name
Number of students
Lecture times
Room Number
END COURSE
BEGIN COURSE
Course Number
Instructor Name
Number of students
Lecture times
Room Number
END COURSE
For example: See image.
You should store all course information in a Course object, with the following members: See image.
You may add additional members if you choose. Note however that you must implement your own hash function that ensures sufficient randomness. A good idea would be to concatenate some/all of the members into one large String and use the polynomial hash function and Horner’s Method as seen in class. The Node class used for the linked lists should have the following members: See image.
You may add additional members if you choose. Note however that the user must NOT be able to edit the key or data fields. As you read records from the file you must add each one to the hash table and print out whether or not there was a collision.
Read in a second file of course information (formatted the same way as the first). Search the hash table for these courses and print out whether they were successfully found or not. Regardless of whether the course was found or not print out how many nodes needed to be scanned to find the result (minimum 0 for not-found, minimum 1 for found).
Your output should look something like this:
John Smith 1234567 (umsmith@cc.umanitoba.ca)
Reading course data from file courses.txt
Added course COMP2140 taught by Chris Iverach-Brereton (no collision)
Added course COMP2140 taught by Joel van Dyk (no collision)
Added course TIME1000 taught by Sir John Smith of Tardis (no collision)
Added course STAT1000 taught by John Fu (collision with TIME1000)
Skipping duplicate TIME1000
Done reading courses
Reading lookup data from file lookup.txt
Course COMP2140 taught by Joel van Dyk is in the table (scanned 1 node)
Course COMP1010 taught by Christina Penner is not in the table (scanned 0 nodes)
Course TIME1000 taught by Sir John Smith of Tardis is in the table (scaned 2 nodes)
Course STAT1000 taught by John Fu is in the table (scaned 1 node)
Done reading lookup data
End of processing
Sample input files will be made available on the course website. Until those are made you must create your own test data using the format specified above.