lab05 : Hash Table part 1

num ready? description submit.cs link
lab05 true Hash Table part 1

https://ucsb-cs32-s17.github.io/lab/lab05/

THIS IS AN INDIVIDUAL LAB. Pair programming is not permitted.

Each individual must submit their own individual submission.

Step 1: Get the lab05 starter code into your repository directory

In this step, we are going to copy the lab05 starter files from the instructors directory into your ~/cs32/lab05 directory.

The files are in the instructors directory at

~aduncan/public_html/cs32/s17/labs/lab05/*

and also accessible via the URL

https://www.cs.ucsb.edu/~aduncan/cs32/s17/labs/lab05

You want to copy these files into your ~/cs32/lab05 directory.

Step 2: Write the table.h header file

Write table.h to define class Table as it is used in the demonstration program named tabledemo.cpp. Your Table must hold Entry objects as defined in entry.h (and implemented in entry.cpp). For the demonstration program to compile successfully, your table.h must define at least the following public functions:

Your class may define other functions too, either public or private ones. In particular, you will probably want to add a hashing function to transform the key values - in our version, function hashkey is a private function. And of course, your class must define the private data a Table object stores.

HINT: You will probably want to use chained hashing for this lab. That means that each row in your Table will be of type std::vector<Entry>. It is often convenient to typedef that type to some shorter name, so your method signatures don’t get clunky.

Step 3: Write the Table class to implement the header from Step 2

Write table.cpp to implement your class Table. You may use tools from any of the standard libraries except <map>, <set>, <unordered_map> and <unordered_set>.

Hint: write stub code for each method, and get your class to compile. Then filling in the methods is a SMOP (Simple Matter of Programming).

In planning your implementations, keep in mind the following requirements:

Clarification about Big-O restrictions:
It is important that you store and manipulate Entry objects (i.e., instances of class Entry), and not separately handle the integer keys and string data. That is because we assess the efficiency of your functions by using the Entry::access_count() function before and after various operations. The time tests used by submit.cs will fail if they detect impossibly small counts of Entry accesses. Do notice that sorting Entry objects is no more complicated than sorting numbers, thanks to the operator conversion function that allows an Entry object to be treated like an int when appropriate. So, for example, if e1 and e2 are both entry objects, then (e1 < e2) will evaluate to true if e1.key() is less than e2.key(). All of the other relational operators work too! The power of overloading.

Step 4: Testing

Compile and test your program at CSIL (by connecting remotely is okay). Create your own testing program(s) to do so. After you think that all parts are working properly, you should verify that your implementation compiles and executes correctly with the demonstration program too. Use the following command to compile it:

g++ -std=c++11 -o tabledemo tabledemo.cpp table.cpp entry.cpp

The demonstration also requires a copy of the file fips.txt (Federal Information Processing Standard codes for all U.S. counties) to reside in your current working directory. (This file is provided along with the other ones.)

Step 5: Submit your work

You will turn in both table.h and table.cpp.

From our class page at https://submit.cs.ucsb.edu/, click the “Make Submission” button next to PA1, or use the following command from a CS terminal:

~submit/submit -p 748 table.cpp table.h

Be sure to wait for the results of all tests. If you score 100/100, and you’ve followed all of the other rules, then you’ll earn full credit.