Skip Lists in C++

Overview

In this homework, you are going to implement a c++ version skiplist. The skiplist follows the general instrustion from HW2, the C-version template.

Besides, there are some additional requirements:

• C++ template
• Iterator
• Const Correctness
• Operator Overloading

Consider learning those topics as well as the following topics before you start:

• std::less
• std::pair

Instructions

General Instructions

Implement a Skip List in C++. See the header file skiplist.h and skiplist.hpp for further details. You need to add definitions in the skiplist.h, according to the instructions in the comments and implement all functions in skiplist.hpp. Updated.

Compilation of the source code requires no errors or warnings and conformity to the C++ 11 standard. Here is the Makefile we will use for grading.

The whole assignment consists of three classes: skiplist, _listnode and iterator. The later two classes are nested classes of skiplist.

SkipList Implementation Details (This part is identical to that of HW2)

You are required to implement skiplists with following rules:

• The height of each node is determined via geometric distribution on node creation. Randomly determine the level of a node by:

  #define RAND_HALF (RAND_MAX)/2
  node_level = 0;
  while (node_level < s->height_limit - 1 && rand() < RAND_HALF) ++node_level;

• The header of skip list is always pointing to a dummy node, whose key = NULL and value = NULL . The height of the dummy header always equals the height_limit for the list.
• The initial height of an empty list is 1
• The allocInt and deleteInt functions are used for allocating memory for int and copying its value.

C++ Template

Template Programming is used throughout the whole assignment, for generic programming. The Key, Value and Compare functions are all in generic type.

Iterator

The find function of skiplist will return an iterator to the found element. For the iterator, you are required to implement 6 different operators:

• Prefix Increment
• suffix increment
• == operator
• != operator
• 2 standard C++ member access operators (-> and *)

Besides, you are required to implement the const_iterator as the const version of iterator. begin(), end() and find() on const skiplist that should return const_iterator, which observes the const-correctness for an iterator of a const list.

Const Correctness

Comments

We require that you will have one line with comments for every four non-blank lines. Comments have to be meaningful and in English.

Memory safety

No memory leaks are allowed. Memory leaks will be automatically detected and manually screened and will result in a decrease in your score after the deadline.

Copy Constructor

Submission

You should submit a compressed file named as hw7.tar to autolab.

The directory tree of your submission should look like the following :

├── skiplist.h
└── skiplist.hpp

Note: your submission should NOT contain main() function

Autolab

Note: We will test your program using the functions declared in the header file provided as well as some other functions defined by us. The output of the individual test cases will NOT be given in auto-grader and any attempt at retrieving the test cases or the program outputs will be seen as plagiarism.

Test Environment

The test environment on autolab is Ubuntu 16.04 with gcc 5.x