Skip to content

Instantly share code, notes, and snippets.

@unsuthee
Created November 20, 2012 08:00
Show Gist options
  • Save unsuthee/4116663 to your computer and use it in GitHub Desktop.
Save unsuthee/4116663 to your computer and use it in GitHub Desktop.
C++ Implementation of Skiplist
///////////////////////////////////////////////////////////////////////////////
#ifndef _SKIPLIST_H_
#define _SKIPLIST_H_
#include <iostream>
#include <sstream>
///////////////////////////////////////////////////////////////////////////////
template<class K,class V,int MAXLEVEL>
class skiplist_node
{
public:
skiplist_node()
{
for ( int i=1; i<=MAXLEVEL; i++ ) {
forwards[i] = NULL;
}
}
skiplist_node(K searchKey):key(searchKey)
{
for ( int i=1; i<=MAXLEVEL; i++ ) {
forwards[i] = NULL;
}
}
skiplist_node(K searchKey,V val):key(searchKey),value(val)
{
for ( int i=1; i<=MAXLEVEL; i++ ) {
forwards[i] = NULL;
}
}
virtual ~skiplist_node()
{
}
K key;
V value;
skiplist_node<K,V,MAXLEVEL>* forwards[MAXLEVEL+1];
};
///////////////////////////////////////////////////////////////////////////////
template<class K, class V, int MAXLEVEL = 16>
class skiplist
{
public:
typedef K KeyType;
typedef V ValueType;
typedef skiplist_node<K,V,MAXLEVEL> NodeType;
skiplist(K minKey,K maxKey):m_pHeader(NULL),m_pTail(NULL),
max_curr_level(1),max_level(MAXLEVEL),
m_minKey(minKey),m_maxKey(maxKey)
{
m_pHeader = new NodeType(m_minKey);
m_pTail = new NodeType(m_maxKey);
for ( int i=1; i<=MAXLEVEL; i++ ) {
m_pHeader->forwards[i] = m_pTail;
}
}
virtual ~skiplist()
{
NodeType* currNode = m_pHeader->forwards[1];
while ( currNode != m_pTail ) {
NodeType* tempNode = currNode;
currNode = currNode->forwards[1];
delete tempNode;
}
delete m_pHeader;
delete m_pTail;
}
void insert(K searchKey,V newValue)
{
skiplist_node<K,V,MAXLEVEL>* update[MAXLEVEL];
NodeType* currNode = m_pHeader;
for(int level=max_curr_level; level >=1; level--) {
while ( currNode->forwards[level]->key < searchKey ) {
currNode = currNode->forwards[level];
}
update[level] = currNode;
}
currNode = currNode->forwards[1];
if ( currNode->key == searchKey ) {
currNode->value = newValue;
}
else {
int newlevel = randomLevel();
if ( newlevel > max_curr_level ) {
for ( int level = max_curr_level+1; level <= newlevel; level++ ) {
update[level] = m_pHeader;
}
max_curr_level = newlevel;
}
currNode = new NodeType(searchKey,newValue);
for ( int lv=1; lv<=max_curr_level; lv++ ) {
currNode->forwards[lv] = update[lv]->forwards[lv];
update[lv]->forwards[lv] = currNode;
}
}
}
void erase(K searchKey)
{
skiplist_node<K,V,MAXLEVEL>* update[MAXLEVEL];
NodeType* currNode = m_pHeader;
for(int level=max_curr_level; level >=1; level--) {
while ( currNode->forwards[level]->key < searchKey ) {
currNode = currNode->forwards[level];
}
update[level] = currNode;
}
currNode = currNode->forwards[1];
if ( currNode->key == searchKey ) {
for ( int lv = 1; lv <= max_curr_level; lv++ ) {
if ( update[lv]->forwards[lv] != currNode ) {
break;
}
update[lv]->forwards[lv] = currNode->forwards[lv];
}
delete currNode;
// update the max level
while ( max_curr_level > 1 && m_pHeader->forwards[max_curr_level] == NULL ) {
max_curr_level--;
}
}
}
const NodeType* find(K searchKey)
{
NodeType* currNode = m_pHeader;
for(int level=max_curr_level; level >=1; level--) {
while ( currNode->forwards[level]->key < searchKey ) {
currNode = currNode->forwards[level];
}
}
currNode = currNode->forwards[1];
if ( currNode->key == searchKey ) {
return currNode;
}
else {
return NULL;
}
}
bool empty() const
{
return ( m_pHeader->forwards[1] == m_pTail );
}
std::string printList()
{
std::stringstream sstr;
NodeType* currNode = m_pHeader->forwards[1];
while ( currNode != m_pTail ) {
sstr << "(" << currNode->key << "," << currNode->value << ")" << endl;
currNode = currNode->forwards[1];
}
return sstr.str();
}
const int max_level;
protected:
double uniformRandom()
{
return rand() / double(RAND_MAX);
}
int randomLevel() {
int level = 1;
double p = 0.5;
while ( uniformRandom() < p && level < MAXLEVEL ) {
level++;
}
return level;
}
K m_minKey;
K m_maxKey;
int max_curr_level;
skiplist_node<K,V,MAXLEVEL>* m_pHeader;
skiplist_node<K,V,MAXLEVEL>* m_pTail;
};
///////////////////////////////////////////////////////////////////////////////
#endif // _SKIPLIST_H_
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment