Assignment 5 Skip Lists

CMPT 225 
Assignment 5
Skip Lists

You are to write a skip list class, any associated exception classes, and do some tests of it. As part of the
code, you will need to be able to print a skip list.
The entry class should be called Entry, and it should hold a key (integer) and data (a string). It should
have a method called random(), which gives it a random key between 0 and 99, inclusive, and a random
data string of three lowercase letters. It should have getters for the key and the data. It should have a
toString method which converts it to a string like so: (14, drn). You may use your code from Assignment
4 for this class.
The principal class will be called SkipList, and it should hold Entry objects. It should have operations:
type name
Entry& find(k) // if the map M has an entry with key k, return it;
 // else, return a reference to a special Entry end.
Entry& greaterEntry(k) // finds the entry with the lowest key that is greater than k.
Entry& lessEntry(k) // finds the entry with the greatest key that is less than k.
void put(k, v) // if there is no entry with key k, insert entry (k, v),
 // and otherwise set the entry’s value to v.
void erase(k) // if the map M has an entry with key k, remove it from M.
 // Otherwise give an error.
int size() // number of elements in the skip list
bool empty() // is size == 0
It should also have a constructor and a destructor. You will need a QuadNode class that holds the four
pointers and a reference/pointer to an Entry.
Note that the functions are given approximately. Add or remove references (&) where necessary or
sensible, and add const to arguments and functions if they are const. I also haven’t defined all the data
members that the classes should have.
Your code should also include a “print” function for SkipList. It can be an overloaded operator<< if you
like, or a simple function. It should print each list of the skip list, with the smallest list first, in the
fashion that skip lists were shown in lecture. Each element should print only the key and should be
allocated 2 spaces; each connection between elements should be two dashes (minus signs). A simple
example is the following, for a skip list of 4 lists containing 14, 18, 27, 29, and 34:
-inf----------------------inf
-inf------18----------34--inf
-inf------18--27------34--inf
-inf--14--18--27--29--34--inf
In your main file, insert 8 entries into a skip list, then print the skip list. Delete an entry from the skip
list, and print it again. Do one find of an element in the list, printing the result, and one find of an
element not in the list (the one you deleted is best), printing the result. Next do a greaterEntry() and a
lessEntry(), again printing the results.
Finally, generate 40 random entries and insert them all into an empty skip list. Print the skip list.
You will be judged on correctness of your code and on code style, so don’t forget to keep your code
clean as you develop it! (Or at the very least, clean it up before submission. We don’t want to see
untidy code.)