Project will use C++ linked lists to implement a hash table. The hash table will be encapsulated inside a class called Table. The class will be tested in two different programs: one is a command-based test driver that you need to write (a program to maintain student names and scores), and the other is for a concordance program that is already written.
Makefile is already provided. Examples on how to use it:
make grades // Makes the grades executable.
make concord // Makes the concord executable.
make pa5list // Makes the pa5list executable.
Table interface
The Table class is similar in functionality to the Java Map class. To simplify your implementation, this one does not use C++ templates (= Java generics), but is fixed to use a key type of string and a value type of int. Also to keep things simple, there is no iterator interface: the only way to visit all the elements is via the printAll function.
The exact interface for the Table class is given in Table.h. You are not allowed to change the interface (i.e., public section) for this class.
The concord program: Example of using the Table class
We wrote a complete program that uses the Table class, concord.cpp. This version filters words, but it does not sort the output. We wrote this whole program for you -- you will just need to complete your Table class (including testing it, of course) to be able to compile and run concord successfully.
Please read the code in concord.cpp to see examples of how to call the Table methods, and what they do. In particular, you can see that, since lookup returns a pointer to the value that goes with the given key, we can use lookup not only to access that value, but also to update the value.
Info about hashStats parameter
The hashStats() method is parameterized so you can use it to print out to different output streams at different times. One of these streams is cout and another is cerr. You write the print statements in this function just as if you were writing to cout, but you use the parameter instead. Here's an example of defining and calling a function with an ostream parameter:
// Param "out" is the output stream to write to.
// (passed by reference, because "<<" updates the stream object)
void testOut(ostream &out) {
out << "Hello there!" << endl;
}
. . .
// example calls:
testOut(cout);
testOut(cerr);
You can see an example call to hashStats in the main function in in concord.cpp.
Table implementation
You are required to implement your Table class using a hash table that you implement. This hash table will do collision resolution by chaining with linked lists. For this assignment you may not use STL container classes or any other classes or functions not implemented by you (a few exceptions: C++ string, the I/O library, and a hash function from the library that is called in the starter code).
Since the key type is fixed for this hash table, we can fix what the hash function is too. We wrote the hash function for you. It's defined in the private section of the Table class.
Note: to compare two C++ strings for equality, you use ==. By the way, the other relational operators are also defined for strings as well.
Unlike in a Java HashMap, the hash table in a Table object will be a fixed size once it gets created. There are two constructors for the Table class; one that uses a constant in Table to determine the size, and another that gets the size to use in a parameter. The latter makes the class more flexible; but we also included it to make it easy for you to test your code on very small hash table sizes so you can force collisions to occur.
Dynamic arrays.
An implication of the client-specified hash size discussed in the previous paragraph is that our representation has to involve a dynamic array, rather than a fixed size array. Remember that with a fixed-size array in C++, the size is fixed at compile-time, so it's impossible to use a value specified from the client/user. Once we create the dynamic array for our table, however, its size won't change.
Creating a dynamic array looks a lot like creating a Java array, except we use a pointer type. The pointer points to the first element in the array. However, once the array is created we can use normal [] syntax to reference elements.
Here is some example code for a dynamic array:
int * arr; // var decl for a dynamic array of integers
arr = new int[10]; // create an array of 10 ints
// (unlike in java, array elements are not automatically initialized with this statement)
arr = new int[10](); // this version *will* init the values to all zeroes
arr[3] = 7; // put a 7 in a[3]
cout << arr[10]; // error: invalid array index (exact behavior undefined)
delete [] arr; // reclaim memory for the array
// (use [] form of delete with anything allocated with [] form of new)
The syntax for declaring our array will be a little hairy, because the element type itself will be a pointer (i.e., because it's a linked list to be used for chaining). Each element is going to be a Node* for a linked list:
Node* * data; // decl for array of pointers to Node (yes, need two *'s)
data = new Node*[100](); // allocate an array of 100 pointers to Node
// and initializes them all to 0 ( = NULL)
data[0]; // this expression is type Node*
This example should be helpful for you to get started with working with this type in the Table class. To make it a little easier we have also defined the ListType typedef for you. What we are creating here is a dynamic array of ListType's. Here's the code we just saw, but using ListType instead:
typedef Node * ListType;
ListType * data;
data = new ListType[100]();
data[0]; // this expression is type ListType (= Node*)
Linked list functions.
One requirement for managing the complexity of the Table class representation, and keeping different levels of abstraction straight is to write linked list routines that take ListType as a parameter to do each of the necessary linked list operations for dealing with a hash chain. For example, one such function might be:
bool listRemove(ListType & list, string target);
When your Table code calls listRemove, it would pass to it one element of the hash table array (i.e., one chain, or one hash bucket).
You are required to define these functions as regular functions in listFuncs.cpp, rather than trying to make them part of the Table class. Because we are writing them as a separately compilable module, we will also need to put their prototypes in listFuncs.h.
Copy semantics and reclaiming memory.
The Table class contains dynamic data, so we need to be concerned about how table objects get copied. When we pass an object by value, the formal parameter is initialized using something called the copy constructor. When we assign one object to another we use the assignment (=) operator. C++ supplies built-in versions of these two methods; however, the built-in versions only do a shallow copy, so do not work correctly for objects that contain dynamic data. It's a little bit tricky to define these correctly to do deep copy, so we are going opt for something simpler here: we are going to disallow copying our Table objects. We do this by making the headers for those methods private. We already put the code to disallow copies in the private section of your Table.h file; you do not need to do anything else for this to work the way we want. Table objects can still be used as parameters passed by reference or const-reference, since that doesn't involve copying the object.
[One note for future reference: even if you create a class that disallows copies, you normally would define another method, called a destructor, that reclaims the dynamic memory when a client is done with your object. We won't have time to discuss that topic in detail, and not having it won't really matter for the way we are using Tables in our client programs here, so our Table class is not going to define a destructor.]
Note: you should still reclaim the Node memory no longer needed when you remove an entry from the Table.
This is going to be a simple program to keep track of students and their scores in a class. It's not meant to be ultra-realistic (for example, only one score per name, and no way to save scores), but it's really a test driver for your Table implementation.
The program takes one optional command-line argument, the size for the hash table -- if the argument is left off, the program uses the default hash size. We have already written the code to deal with the command line argument. When the program starts up it creates a hash table, immediately prints out the hashStats() for that empty table, and then should print the initial command prompt ("cmd> "). In the following example of program startup % is the Linux shell prompt and user input is shown in italics
grades 7
number of buckets: 7
number of entries: 0
number of non-empty buckets: 0
longest chain: 0
cmd>
Once this start-up happens the program repeatedly reads and executes commands from the user, printing out the command prompt (cmd>) after it finishes the previous command, until the user enters the quit command.
Here are the commands for the program (in the following a name will always be a single word):
insert name score // Insert this name and score in the grade table. If this name was already present, print a message
to that effect, and don't do the insert.
change name newscore // Change the score for name. Print an appropriate message if this name isn't present.
lookup name // Lookup the name, and print out his or her score, or a message indicating that student is not in the
table.
remove name // Remove this student. If this student wasn't in the grade table, print a message to that effect.
print // Prints out all names and scores in the table.
size // Prints out the number of entries in the table.
stats // Prints out statistics about the hash table at this point. (Calls hashStats() method)
help // Prints out a brief command summary.
quit // Exits the program.
The only error-checking required for this program is for you to print out "ERROR: invalid command", and the command summary (see 'help' command) if a user give an invalid command name. Once you print the message your program should then display another command prompt.
So, for example, you do not have to check whether the user has entered the correct number of arguments or the correct type of arguments for a command (i.e., the graders will not test your program on those conditions).
Note: this program enables you to test all of the Table methods.
Using the concord program to test Table
Once you are convinced your Table class works with the grades program you should use concord.cpp program along with the .txt files that came with the assignment to test your Table class with a larger amount of data. This program does not use all of the Table methods, so is not suitable as a complete test of your Table class. See comments in concord.cpp for how to run it.
Program development and milestone
Here's a suggested development plan:
1. Think through what exact operations you will need on a single chain to implement the various Table methods. Define the exact interface of functions to do these operations on a single linked list. These kinds of operations were discussed here.
2. Write and test all of the linked list routines. Because they don't depend on the private data of the hash table class (just the Node class) you can write a separate program to test these thoroughly, before you tackle any of code dealing with a dynamic array, etc. Please note that you are not required to submit the tester file, it is just used for testing purposes to make sure your program works correctly.
3. Once you are convinced that your list code works, you can start working on the Table class that uses these functions. Implement the constructors, insert and printAll methods of Table, and test them with a partially written grades.cpp.
4. Add other Table methods and the corresponding grades.cpp code that tests those methods to your program, one at a time, testing them as you go, until you have a completely working grades program.
5. Test your Table class with concord.cpp running on the two story files given.