skiplist source

#include "SkipList.h"

template <class Key, class Obj>
SkipList<Key, Obj>::SkipList(float p, int m, Key* k)
{
    curHeight = 1;
    maxHeight = m;
    probability = p;

    //create head with maximum height
    head = new SkipNode<Key, Obj>(maxHeight);
    //create tail with maximum height
    tail = new SkipNode<Key, Obj>(k, (Obj*)NULL, maxHeight);
    //attach all of head's pointers to the tail
    for (int x = 1; x <= maxHeight; x++)
    {
        head->forwardNodes[x] = tail;
    }
}

template <class Key, class Obj>
SkipList<Key, Obj>::~SkipList()
{
    SkipNode<Key, Obj>* tmp;
    SkipNode<Key, Obj>* nxt;
    tmp = head;
    //go through all base-level nodes and remove them
    while (tmp)
    {
        nxt = tmp->forwardNodes[1];
        delete tmp;
        tmp = nxt;
    }
}

template <class Key, class Obj>
bool SkipList<Key, Obj>::insert(Key* k, Obj* o)
{
    int lvl = 0, h = 0;
    SkipNode<Key, Obj>** updateVec =
        new SkipNode<Key, Obj>*[maxHeight + 1];
    SkipNode<Key, Obj>* tmp = head;
    Key* cmpKey;

    //find the right spot for new node on each level
    //starting from the highest level, go over each level
    for (h = curHeight; h >= 1; h--)
    {
        //get key of next node on height h
        cmpKey = tmp->forwardNodes[h]->getKey();
        //compare and go further until you find a node with key greater than new item's
        //we're comparing key of next node, while keeping preceding node in tmp
        while (*cmpKey < *k)
        {
            tmp = tmp->forwardNodes[h];
            cmpKey = tmp->forwardNodes[h]->getKey();
        }
        //vector of all preceding nodes
        updateVec[h] = tmp;
    }

    //we've got preceding node on base level in tmp, go 1 forward
    tmp = tmp->forwardNodes[1];
    cmpKey = tmp->getKey();

    //if duplicate, don't insert the new node
    if (*cmpKey == *k)
    {
        return false;
    }
    else //insert the node
    {
        //generate height of new node
        lvl = generateHeight();
        if (lvl > curHeight) //if it's greater than current maximum height, update the head
        {
            for (int i = curHeight + 1; i <= lvl; i++)
                updateVec[i] = head;
            curHeight = lvl;
        }
        //insert the new element on all levels up to his height
        tmp = new SkipNode<Key, Obj>(k, o, lvl);
        for (int i = 1; i <= lvl; i++)
        {
            tmp->forwardNodes[i] = updateVec[i]->forwardNodes[i];
            updateVec[i]->forwardNodes[i] = tmp;
        }
    }
    return true;
}

template <class Key, class Obj>
bool SkipList<Key, Obj>::remove(Key* k)
{
    SkipNode<Key, Obj>** updateVec =
        new SkipNode<Key, Obj>*[maxHeight + 1];
    SkipNode<Key, Obj>* tmp = head;
    Key* cmpKey;

    //find the nodes preceding this node on all levels
    for (int h = curHeight; h > 0; h--)
    {
        cmpKey = tmp->forwardNodes[h]->getKey();
        while (*cmpKey < *k)
        {
            tmp = tmp->forwardNodes[h];
            cmpKey = tmp->forwardNodes[h]->getKey();
        }
        //vector of all preceding nodes
        updateVec[h] = tmp;
    }
    //we've got preceding node on base level in tmp, go 1 forward
    tmp = tmp->forwardNodes[1];
    cmpKey = tmp->getKey();

    //delete the node
    if (*cmpKey == *k)
    {
        //on all levels of list
        for (int i = 1; i <= curHeight; i++)
        {
            //if level exceeds height of this node, break
            if (updateVec[i]->forwardNodes[i] != tmp)
                break;
            //attach preceding node to the next one
            updateVec[i]->forwardNodes[i] = tmp->forwardNodes[i];
        }
        //delete this node
        delete tmp;

        //calculate new height of list (if this node was the highest)
        while ((curHeight > 1) &&
            ((head->forwardNodes[curHeight]->getKey() == tail->getKey())))
            curHeight--;
        return true;
    }
    else
    {
        return false;
    }
}

template <class Key, class Obj>
Obj* SkipList<Key, Obj>::retrieve(Key* k)
{
    int h = 0;
    //SkipNode<Key, Obj>** updateVec = new SkipNode<Key, Obj>*[maxHeight + 1];
    SkipNode<Key, Obj>* tmp = head;
    Key* cmpKey;

    //starting from the top level, find the node
    for (h = curHeight; h >= 1; h--)
    {
        cmpKey = tmp->forwardNodes[h]->getKey();
        while (*cmpKey < *k)
        {
            tmp = tmp->forwardNodes[h];
            cmpKey = tmp->forwardNodes[h]->getKey();
        }
    }

    //we've got preceding node on base level in tmp, go 1 forward
    tmp = tmp->forwardNodes[1];
    cmpKey = tmp->getKey();
    if (*cmpKey == *k)
        return tmp->getObj();
    else
        return (SkipNode<Key, Obj>*) NULL;
}

template <class Key, class Obj>
int SkipList<Key, Obj>::generateHeight()
{
    //random seed
    srand(time(NULL));
    //start with minimum height
    int height = 1;
    do
    {
        //get a random float from 0 to 1
        float random = static_cast<float>(rand() / static_cast<float>(RAND_MAX));
        //if probability fits in the number, increase the height and calculate again
        if (probability < random)
        {
            ++height;
        }
        //if it doesn't, we return the current height
        else
        {
            break;
        }
    } while (height <= maxHeight); //don't exceed the maximum height
    return height;
}

/*
template <class Key, class Obj>
SkipList<Key, Obj>::iterator SkipList<Key, Obj>::begin()
{
    return iterator(head);
}

template <class Key, class Obj>
SkipList<Key, Obj>::iterator SkipList<Key, Obj>::end()
{
    return iterator(tail);
}

template <class Key, class Obj>
SkipList<Key, Obj>::iterator::iterator(SkipNode<Key, Obj>* ptr)
{
    cur = ptr;
}

template <class Key, class Obj>
iterator SkipList<Key, Obj>::iterator::operator++()
{
    cur = cur->forwardNodes[1];
}
*/