I need help with this assignment to implement the code for skip list in C++, ASAP.

Goals: Working with dynamic arrays, pointers, doubly linked lists

(The Interface(.h) and Implementation(.cpp) code are listed below)

For this assignment, you will write a Skip List data structure to store integers. When searching a Skip List, items can be found in O(log n) time. No duplicates are allowed.

The above picture shows a SkipList with a depth of 5, Level-0 to Level-4

Some of those items (based on a coin toss, 50% chance using (rand() % 2) == 1) are inserted at level = 1, i.e. at L1. Some of those items are inserted at L2, and so on.

SkipList has front and rear guards, in our case INT_MIN and INT_MAX as the first and the last items at each of the levels. This makes it easier to add and find items.

Skip List is made up of private SNode elements. Each SNode has SNode* of next, prev, upLevel and downLevel, as well as data which holds the actual integer value stored at the node.

front and rear guards are special SNode* objects to make the implementation easier. The pointers to these guards are kept in arrays, named frontGuards and rearGuards, see below for details.

The public functions of SkipList are:

// default SkipList has depth of 1, just one doubly-linked list

explicit SkipList(int depth = 1);

// destructor

virtual ~SkipList();

// return true if successfully added, no duplicates

bool Add(int data);

// return true if successfully removed

bool Remove(int data);

// return true if found in SkipList

bool Contains(int data);

The private variables and functions of SkipList are:

class SNode {

public:

// SNode stores int as data

explicit SNode(int data);

// data for SNode

int data;

// link to next SNode

SNode *next;

// link to prev SNode

SNode *prev;

// link to up one level

SNode *upLevel;

// link to down one level

SNode *downLevel;

};

// depth of SkipList, levels are 0 to depth-1

int depth;

// array of depth SNode* objects as frontGuards linking levels

// if depth = 2, we'd have frontGuards[0] and frontGuards[1]

SNode **frontGuards;

// array of depth SNode* objects as rearGuards linking levels

SNode **rearGuards;

// given a SNode, place it before the given NextNode

void addBefore(SNode *newNode, SNode *nextNode);

// return true 50% of time,

// each node has a 50% chance of being at higher level

bool alsoHigher() const;

};

///////////////////////////////the code sources///////////////////////////////////////////

skiplist.h

#ifndef ASS4_SKIPLIST_H #define ASS4_SKIPLIST_H

#include #include

using namespace std;

// only SkipList class can create SNode objects

class SkipList;

class SNode { friend class SkipList; friend ostream &operator

private: // constructor explicit SNode(int value);

// data contained in the object int value{0};

// link to Next SNode vector forward;

// link to Prev SNode vector backward;

// how many forward/backward pointers it has int height() const;

// increase the number of forward/backward pointers it has void increaseHeight(); };

class SkipList { // display with level friend ostream &operator

private: // maximum number of levels int maxLevel = 1;

// probability of inserting at a higher level // as an integer between 0% and 100% (exclusive) int probability = 0;

// head of linked levels SNode *head;

// tail of linked levels SNode *tail;

// given a SNode, place it before the given nextNode void addBefore(SNode *newNode, SNode *nextNode);

// return true p% of time, // for p = 50, each node has a 50% chance of being at higher level bool shouldInsertAtHigher() const;

// connect 2 nodes in a line static void connect2AtLevel(SNode *a, SNode *b, int level);

// connect 3 nodes in a line static void connect3AtLevel(SNode *a, SNode *b, SNode *c, int level);

SNode *containsSNode(int data) const;

vector getBeforeNodes(int data) const;

public: // default SkipList has only 1 level, just one doubly-linked list explicit SkipList(int maxLevel = 1, int probability = 0);

// destructor virtual ~SkipList();

// copy not allowed SkipList(const SkipList &other) = delete;

// move not allowed SkipList(SkipList &&other) = delete;

// assignment not allowed SkipList &operator=(const SkipList &other) = delete;

// move assignment not allowed SkipList &operator=(SkipList &&other) = delete;

// return true if successfully added, no duplicates allowed bool add(int value);

// return true if successfully added, no duplicates bool add(const vector &values);

// return true if successfully removed bool remove(int data);

// return true if found in SkipList bool contains(int data) const; };

#endif // ASS4_SKIPLIST_H

skiplist.cpp

#include #include #include #include

#include "skiplist.h"

using namespace std;

ostream &operator= 0; d--) { out forward[d]; if (curr != skip.tail) { out value; curr = curr->forward[d]; } while (curr != nullptr && curr != skip.tail) { out " value; curr = curr->forward[d]; } out

SNode::SNode(int value) : value{value} {}

// how many forward/backward pointers it has int SNode::height() const { return 0; }

// increase the number of forward/backward pointers it has void SNode::increaseHeight() {}

SkipList::SkipList(int maxLevel, int probability) : maxLevel{maxLevel}, probability{probability} { assert(maxLevel > 0 && probability >= 0 && probability

bool SkipList::shouldInsertAtHigher() const { return rand() % 100

bool SkipList::add(const vector &values) { return true; }

bool SkipList::add(int value) { return true; }

SkipList::~SkipList() { // need to delete individual nodes }

bool SkipList::remove(int data) { return true; }

// get the node that would be before this data // at level-0 vector SkipList::getBeforeNodes(int data) const { vector v(maxLevel); return v; }

SNode *SkipList::containsSNode(int data) const { return nullptr; }

bool SkipList::contains(int data) const { return true; }

void SkipList::connect2AtLevel(SNode *a, SNode *b, int level) {}

void SkipList::connect3AtLevel(SNode *a, SNode *b, SNode *c, int level) {}

main.cpp

#include #include

#include "skiplist.h"

using namespace std;

void test1() { // setting seed for easy testing srand(10000); SkipList skp(5, 80); cout

int main() {

test1();

cout L4 -INF- ---> +INE 1 1 v -> +INF L3 -INF 15 15 120 +INE L1 -INF 10 15 10 15 35 70 120 +INE