Program 4- Linked Lists ­ Skip List Purpose

 Linked Lists ­ Skip List Purpose This programming assignment implements a skip list and compares its performance with that of the doubly linked and the MTF lists you have implemented/used in the Lab 4. Skip List The skip list is a sorted list whose find( ) is bounded by O( log n ) on average. As shown below, a level­6 skip list consists of six parallel lists where the lowest list includes all items in a sorted order; middle lists inherit items from their one­level lower list with a 50% possibility; and the top list includes no items. All of those lists' left and right most items are a dummy whose actual value is a negative and positive infinitive respectively. S5: -inf <---------------------------------------------------------- +inf ^ ^ | | v v S4: -inf <---------- 17 <------------------------------------------ +inf ^ ^ ^ | | | v v v S3: -inf <---------- 17 <---------- 25 <-------------------------- +inf ^ ^ ^ ^ | | | | v v v v S2: -inf <---------- 17 <---------- 25 <---------- 38 <---------- +inf ^ ^ ^ ^ ^ | | | | | v v v v v S1: -inf <-- 12 <-- 17 <---------- 25 <-- 31 <-- 38 <---------- +inf ^ ^ ^ ^ ^ ^ ^ | | | | | | | v v v v v v v S0: -inf <-- 12 <-- 17 <-- 20 <-- 25 <-- 31 <-- 38 <-- 45 <-- +inf Inialize and delete In this implementation, Skip lists have 6 levels (S0 to S5). Each level's left and right most items are a dummy whose actual value is a negative and positive infinitive respectively. Initialize slist is implemented in init() function, and it is called in constructor method. Since slist creates a number of pointers, it should clear up all items and delete pointer in destructor method, using clear() function. init() function is given. You have to complete the clear() function. clear() function will iterate through to delete all pointers of SListNode, and at the end of each level, the leftmost dummy header point to the rightmost dummy header as next pointer. Find Algorithm Given a value to find, the find( ) function starts with the left most dummy item of the top level list, (­inf of S5 in the above example), and repeats the following two steps until it reaches the item at the lowest list that includes the given value: 1. move right toward +inf while the current item < the given value, 2. shift down to the same item at the next lower list if it exists For instance, in order to find item 31, we traverse from S5's ­inf through S4's ­inf, S4's 17, S3's 17, S3's 25, S2's 25, S1's 25, S1's 31, and S0's 31. In our implementation, we have two methods such as find( ) and searchPointer( ):  Insert Algorithm Given a new object to insert, the insert( object ) function starts with calling searchPointer( object ). If searchPointer( value ) returns a pointer to the exact item, we don't have to insert this value. Otherwise, start inserting this item just in front of (i.e., on the left side of) what searchPointer( object ) has returned. After inserting the item at the lowest level, (i.e., at S0), you have to repeat the following steps: 1. Calls rand( ) % 2 to decide whether the same item should be inserted in a one­level higher list. Insert one when rand( ) % 2 returns 1, otherwise stop the insertion. 2. To insert the same new item in a one­level higher list, move left toward ­inf at the current level until encountering an item that has a link to the one­higher level list. 3. Shift up to the same item in the next higher list. 4. Move right just one time, (i.e., to the next item). 5. Insert the new item in front of the current item. For instance, to insert item 23, you have to go to item 25, insert 23 in front of 25, and thereafter call rand( ) % 2 to decide if you need to insert the same item in the next higher list. If it returns 1, you have to traverse S0's 20, S0's 17, S1's 17, and S1's 25. Insert 23 before item 25. Repeat the same sequence of operations to insert 23 on S2, S3, and S4. However, don't insert any items at the top level, (i.e., S5). S5: -inf <------------------------------------------------------------------ +inf ^ ^ | | v v S4: -inf <---------- 17 <---------- <---------------------------------- +inf ^ ^ ^ | | | v v v S3: -inf <---------- 17 <---------- <-- 25 <-------------------------- +inf ^ ^ ^ ^ | | | | v v v v S2: -inf <---------- 17 <---------- <-- 25 <---------- 38 <---------- +inf ^ ^ ^ ^ ^ | | | | | v v v v v S1: -inf <-- 12 <-- 17 <---------- <-- 25 <-- 31 <-- 38 <---------- +inf ^ ^ ^ ^ ^ ^ ^ ^ | | | | | | | | v v v v v v v v S0: -inf <-- 12 <-- 17 <-- 20 <-- 23 <-- 25 <-- 31 <-- 38 <-- 45 <-- +inf Delete Algorithm Given an object to delete, the remove( object ) function starts with calling searchPointer( object ). If searchPointer( value ) returns a pointer to the exact item, we delete this item from the lowest up to the highest level as repeatedly traversing a pointer from the current item to its above item. For instance, to delete item 17, start its deletion from S0's 17, simply go up to S1's 17, delete it, and repeat the same operations till you delete S4's 17. Statement of Work Download the following files to your project. (Files­­Programs/Program4/) You'll see the following files: dlist.h: a doubly­linked list's header file dlist.cpp.h: a doubly­linked list's template implementation mtflist.h: an MTF list's header file mtflist.cpp.h: an MTF list's template implementation (Should get from Lab 4 solution) transposelist.h: an transpose list's header file transposelist.cpp.h: an transpose list's template implementation (Should get from Lab4 solution) slist.h: a skip list's header file slist_incomplete.cpp.h: a skip list's template cpp file that you have to complete driver.cpp: a main program for the skip list statistics.cpp: a main program to compare different algorithms Complete slist_incomplete.cpp.h by implementing the clear, insert and remove functions: template void SList