Skip List

skiplist.hpp

#include <ctime>
#include <cstdlib>
#include <stack>
#include <memory>

template <class K, class V>
class SkipList
{
	// key-value data
	struct Pair
	{
		K _key;
		V _value;
		Pair(const K &k, const V &v): _key(k), _value(v) {}
	};

	// link list node
	struct Node
	{
		Node *_next, *_prev, *_children;
		Pair *_pair;
		Node(Pair *pair = nullptr, Node *prev = nullptr,
			 Node *next = nullptr, Node *children = nullptr): 
			_pair(pair), _prev(prev), _next(next), _children(children) {}
		~Node()
		{
			// if node is bottom node, then delete pair
			if (_children == nullptr && _pair)
				delete _pair;
		}
	};

	Node *head = new Node();

	// find the node that node->_key <= key
	Node *searchList(Node *li, const K &key)
	{
		Node *ptr = li;
		while (ptr->_next && ptr->_next->_pair->_key <= key)
			ptr = ptr->_next;
		return ptr;
	}
public:
	SkipList()
	{
		srand(time(nullptr));
	}

	SkipList(const SkipList &li)
	{
		head = new Node();
		srand(time(nullptr));
		// reach bottom list
		Node *bottomList = li.head;
		while (bottomList->_children)
			bottomList = bottomList->_children;
		// add items to new skiplist
		for (Node *ptr = bottomList; ptr; ptr = ptr->_next)
			if (ptr->_pair)
				put(ptr->_pair->_key, ptr->_pair->_value);
	}

	~SkipList()
	{
		// delete all nodes
		Node *li = head;
		while (li) {
			Node *tmphead = li;
			li = li->_children;
			Node *ptr = tmphead;
			while (ptr) {
				Node *tempnode = ptr;
				ptr = ptr->_next;
				delete tempnode;
			}
		}
	}

	SkipList& operator=(SkipList li)
	{
		std::swap(head, li.head);
		return (*this);
	}

	void put(const K &key, const V &value)
	{
		// track the precursor node in each level
		std::stack<Node*> prevs;
		Node *li = head;
		while (li) {
			Node *prev = searchList(li, key);
			prevs.push(prev);
			li = prev->_children;
		}
		// insert node in bottom level
		Pair *pair = new Pair(key, value);
		Node *prev = prevs.top();
		prevs.pop();
		// already exist
		if (prev->_pair && prev->_pair->_key == key) {
			prev->_pair->_value = value;
			return;
		}
		Node *newNode = new Node(pair, prev, prev->_next);
		if (prev->_next)
			prev->_next->_prev = newNode;
		prev->_next = newNode;
		// insert node in higher level
		while (true) {
			bool insertUp = rand() % 2;
			if (!insertUp)
				return;
			if (!prevs.empty()) {
				prev = prevs.top();
				prevs.pop();
			} else {
				head = new Node(nullptr, nullptr, nullptr, head);
				prev = head;
			}
			newNode = new Node(pair, prev, prev->_next, newNode);
			if (prev->_next)
				prev->_next->_prev = newNode;
			prev->_next = newNode;
		}
	}

	V *get(const K &key)
	{
		Node *ptr;
		Node *li = head;
		while (li) {
			ptr = searchList(li, key);
			if (ptr->_pair && ptr->_pair->_key == key)
				return &ptr->_pair->_value;
			li = ptr->_children;
		}
		if (ptr->_pair == nullptr || ptr->_pair->_key != key)
			return nullptr;
		return &ptr->_pair->_value;
	}

	void remove(const K &key)
	{
		// find node
		Node *ptr = head;
		while (ptr) {
			Node *node = searchList(ptr, key);
			if (node->_pair && node->_pair->_key == key) {
				ptr = node;
				break;
			}
			ptr = node->_children;
		}
		// not found
		if (ptr == nullptr)
			return;
		// delete node in each level
		while (ptr) {
			ptr->_prev->_next = ptr->_next;
			if (ptr->_next)
				ptr->_next->_prev = ptr->_prev;
			ptr = ptr->_children;
		}
	}
};