Help with SkipList Implementation in Java SkipLists Implementation Write code th

Question

Help with SkipList Implementation in Java

SkipLists Implementation

Write code that implements and exercises skiplists.

Interfaces

Interface SkipList_Interface

Class SkipList_Node

Class SkipList

Notes

In the beginning, there are only two initial nodes called head and tail and all the forward pointers of the head node point to the tail. Their string data is null and they should not be changed in any case.

When a new node is inserted, it needs to be placed between the head and tail nodes and relevant pointers should be rearranged accordingly. A right place for a newly-created node should be searched with forward pointers starting from the head node. When creating a node for insertion, it should get a level along with string data. The level should be determined by using randomLevel method provided in SkipList class, which randomly generates each level with probability 0.5. The maximum level of a node in skiplist is pre-defined as 100 in class SkipList. We expect the probability 0.5^100 is small enough to cover almost all levels generated by randomLevel method for our implementation.

For removing, the target node to be deleted should be first searched with forward pointers starting from the head node as same as insertion. Forward pointers of relevant nodes need to be adjusted correctly and the size of skiplist is decreased by one if remove succeed.

Explanation / Answer

Code

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

class Skip_list {
public:
Skip_list();
~Skip_list();

void print() const;

std::string* find(int searchKey) const;

void insert(int searchKey, const std::string& newValue);

void erase(int searchKey);

private:

struct Node {
int key;
std::string value;

std::vector<Node*> forward;

Node(int k, const std::string& v, int level):
key(k), value(v),forward(level,nullptr)
{}   
};  

int randomLevel() const;   

static int nodeLevel(const Node* v);

static Node* makeNode(int key, std::string val, int level);

Node* lower_bound(int searchKey) const ;

std::vector<Node*> predecessors(int searchKey) const ;

const float probability;
const int maxLevel;
Node* head; // pointer to first node
Node* NIL; // last node
};

Skip_list::Skip_list() :
probability(0.5),
maxLevel(16)
{
int headKey = std::numeric_limits<int>::min();
head = new Node(headKey, "head", maxLevel);

int nilKey = std::numeric_limits<int>::max();
NIL = new Node(nilKey, "NIL", maxLevel);

std::fill(head->forward.begin(), head->forward.end(), NIL);
}

Skip_list::~Skip_list() {
auto node = head;
while (node->forward[0]) {
auto tmp = node;
node = node->forward[0];
delete tmp;
}
delete node;
}

std::string* Skip_list::find(int searchKey) const {
std::string* res{};
if (auto x = lower_bound(searchKey)) {
if (x->key == searchKey && x!=NIL) {
res = &(x->value);
}
}
return res;
}

void Skip_list::print() const {
Node* list = head->forward[0];
int lineLenght = 0;

std::cout << "{";

while (list != NIL) {
std::cout << "value: " << list->value
<< ", key: " << list->key
<< ", level: " << nodeLevel(list);

list = list->forward[0];

if (list != NIL) std::cout << " : ";

if (++lineLenght % 2 == 0) std::cout << " ";
}
std::cout << "} ";
}

void Skip_list::insert(int searchKey, const std::string& newValue) {
auto preds = predecessors(searchKey);

{
auto next = preds[0]->forward[0];
if (next->key == searchKey && next != NIL) {
next->value = newValue;
return;
}
}

const int newNodeLevel = randomLevel();
auto newNodePtr = makeNode(searchKey, newValue, newNodeLevel);

for (int i = 0; i < newNodeLevel; ++i) {
newNodePtr->forward[i] = preds[i]->forward[i];
preds[i]->forward[i] = newNodePtr;
}
}

void Skip_list::erase(int searchKey) {
auto preds = predecessors(searchKey);

auto node = preds[0]->forward[0];
if (node->key != searchKey || node == NIL) {
return;
}

for (size_t i = 0; i < nodeLevel(node); ++i) {
preds[i]->forward[i] = node->forward[i];
}
delete node;   
}

int Skip_list::nodeLevel(const Node* v) {
return v->forward.size();
}

Skip_list::Node* Skip_list::makeNode(int key, std::string val, int level) {
return new Node(key, val, level);
}

int Skip_list::randomLevel() const {
int v = 1;
while (((double)std::rand() / RAND_MAX) < probability &&
v < maxLevel) {
v++;
}
return v;
}

Skip_list::Node* Skip_list::lower_bound(int searchKey) const{
Node* x = head;

for (unsigned int i = nodeLevel(head); i-- > 0;) {
while ( x->forward[i]->key < searchKey) {
x = x->forward[i];
}
}
return x->forward[0];
}

std::vector<Skip_list::Node*> Skip_list::predecessors(int searchKey) const {
std::vector<Node*> result(nodeLevel(head),nullptr);
Node* x = head;

for (unsigned int i = nodeLevel(head); i-- > 0;) {
while (x->forward[i]->key < searchKey) {
x = x->forward[i];
}
result[i] = x;
}
return result;
}

int main() {

Skip_list s;

for (int i = 0; i < 50; ++i) {
std::stringstream ss;
ss << i;

s.insert(i, ss.str());
}

s.print();
std::cout << std::endl;

auto f = s.find(10);
if (f) std::cout << "Node found! value: " << f << ' ';
else std::cout << "Node NOT found! ";

s.insert(40, "TEST");

s.print();
std::cout << std::endl;

s.erase(40);

s.print();
std::cout << std::endl;

std::cout << " Done! ";
getchar();
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.