Skip List

skiplist.cpp

#include <iostream>
#include <string>
#include <sstream>
#include <ostream>
#include <cassert>

using namespace std;

static const int MultiplyDeBruijnBitPosition[] = 
{
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

// http://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightParallel
int ffs(unsigned v)
{
    return MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];
}

unsigned PRNG()
{
    static unsigned nSeed = 5323;

    nSeed = (8253729 * nSeed + 2396403);

    return nSeed % 0x7fffffff;
}

template <class Key, class Value, const int MaxLevel>
class SkipNode
{
public:
    SkipNode(int level, Key * k = NULL, Value * v = NULL)
        : _key(k)
        , _value(v)
        , _level(level)
    {
        for (int x = 1; x <= MaxLevel; ++x)
        {
            forward[x] = NULL;
            distance[x] = 0;
        }
    }

    ~SkipNode()
    {
        delete _key;
        delete _value;
    }

    Key * key()
    {
        return _key;
    }

    Value * value()
    {
        return _value;
    }

    int level() const
    {
        return _level;
    }

public:
    SkipNode * forward[MaxLevel + 1];
    int distance[MaxLevel + 1];

private:
    Key * _key;
    Value * _value;
    int _level;
};

template <class Key, class Value, const int MaxLevel>
class SkipList
{
    typedef SkipNode<Key, Value, MaxLevel> Node;

public:
    SkipList()
        : _head(new Node(MaxLevel))
        , _level(1)
    {
    }

    ~SkipList()
    {
        Node * node = _head;

        while (node)
        {
            Node * next = node->forward[1];

            delete node;

            node = next;
        }
    }

    bool insert(Key * searchKey, Value * newValue)
    {
        Node * x = _head, * update[MaxLevel+1];
        int steps[MaxLevel+1] = { 0 };
    
        for (int h = _level; h >= 1; --h)
        {
            while (x->forward[h] != NULL && *x->forward[h]->key() < *searchKey)
            {
                steps[h] += x->distance[h];
                x = x->forward[h];
            }

            update[h] = x;
        }

        x = x->forward[1];

        if (x == NULL || *x->key() != *searchKey)
        {
            int newLevel = generateLevel();

            if (newLevel > _level)
            {
                for (int i = _level + 1; i <= newLevel; ++i)
                    update[i] = _head;

                _level = newLevel;
            }

            x = new Node(newLevel, searchKey, newValue);

            int distance = 0;

            for (int i = 1; i <= newLevel; ++i)
            {
                x->forward[i] = update[i]->forward[i];
                update[i]->forward[i] = x;
                x->distance[i] = update[i]->distance[i] - distance;
                update[i]->distance[i] = distance + 1;
                distance += steps[i];
            }

            for (int h = newLevel + 1; h <= _level; ++h)
            {
                update[h]->distance[h]++;
            }

            return true;
        }

        return false;
    }

    bool remove(Key * searchKey)
    {
        Node * x = _head, * update[MaxLevel+1];
    
        for (int h = _level; h >= 1; --h)
        {
            while (x->forward[h] != NULL && *x->forward[h]->key() < *searchKey)
            {
                x = x->forward[h];
            }

            update[h] = x;
        }

        x = x->forward[1];

        if (x != NULL && *x->key() == *searchKey)
        {
            int nodeLevel = update[1]->forward[1]->level();

            for (int i = 1; i <= _level; ++i)
            {
                if (update[i]->forward[i] != x) break;

                update[i]->distance[i] += update[i]->forward[i]->distance[i] - 1;
                update[i]->forward[i] = x->forward[i];
            }

            for (int h = nodeLevel + 1; h <= _level; ++h)
            {
                update[h]->distance[h]--;
            }

            delete x;

            while ((_level > 1) && ((_head->forward[_level] == NULL)))
            {
                _level--;
            }

            return true;
        }

        return false;
    }

    Value * search(Key * searchKey) const
    {
        Node * x = _head;

        for (int h = _level; h >= 1; --h)
        {
            while (x->forward[h] != NULL && *x->forward[h]->key() < *searchKey)
            {
                x = x->forward[h];
            }
        }

        x = x->forward[1];

        return (x != NULL && *x->key() == *searchKey) ? x->value() : NULL;
    }

    Value * at(unsigned i) const
    {
        Node * x = _head;

        for (int h = _level; h >= 1; --h)
        {
            while (x->forward[h] != NULL && x->distance[h] <= i)
            {
                i -= x->distance[h];
                x = x->forward[h];
            }
        }

        return i == 0 ? x->value() : NULL;
    }
  
    void displayList(ostream& os) 
    { 
        os<<"\n*****Skip List*****"<<"\n"; 

        for(int i=1; i<=_level; i++) 
        { 
            Node *node = _head->forward[i];

            os << "Level " << i << ": "; 

            while(node != NULL) 
            { 
                os << *node->key() << " "; 
                
                node = node->forward[i]; 
            }

            os << "\n"; 
        } 
    };

private:
    static int generateLevel_slower()
    {
        int newLevel = 1;

        while (((PRNG() % 100) / 100.0) < .5)
        {
            newLevel++;
        }
        
        return newLevel < MaxLevel ? newLevel : MaxLevel;
    }

    // http://ticki.github.io/blog/skip-lists-done-right/
    static int generateLevel()
    {
        return ffs(PRNG() & ((1 << MaxLevel) - 1)) + 1;
    }

private:
    Node * _head;
    int _level;
};

struct Product
{
    float cost;
    int quantity;
    int location;
};

ostream & operator<<(ostream & os, const Product & obj)
{
    os << "{ cost: " << obj.cost << ", quantity: " << obj.quantity << ", localtion: " << obj.location << " }";

    return os;
}

template <class SkipList>
void printAt(const SkipList & sl, unsigned i)
{
    cout << "found by index (" << i << "): " << *sl.at(i) << endl;
}

typedef Product productData;
typedef SkipList<string, productData, 4> MySkipList;

int main(int argc, char * argv[])
{
    MySkipList aSkipList;

    productData * first = new productData, * special = new productData, * last = new productData;

    first->cost = 10, first->quantity = 20, first->location = 30;
    special->cost = 1, special->quantity = 2, special->location = 3;
    last->cost = -1, last->quantity = -2, last->location = -3;

    aSkipList.insert(new string("Y8792"), last);
    aSkipList.insert(new string("A1234"), first);
    aSkipList.insert(new string("B2345"), special);
    aSkipList.insert(new string("C3456"), new productData);
    aSkipList.insert(new string("D4567"), new productData);
    aSkipList.insert(new string("E5678"), new productData);
    aSkipList.insert(new string("F6789"), new productData);
    aSkipList.insert(new string("G7890"), new productData);

    aSkipList.displayList(cout);

    printAt(aSkipList, 1);
    printAt(aSkipList, 8);

    ostringstream oss;

    for (int i = 0; i < 30; ++i)
    {
        oss << "A" << i;

        aSkipList.insert(new string(oss.str()), new productData);

        oss.str("");
    }

    aSkipList.displayList(cout);

    string* aKey = new string("B2345");

    cout << "found by key (" << *aKey << "): " << *aSkipList.search(aKey) << endl;

    printAt(aSkipList, 38);

    aSkipList.remove(new string("D4567"));

    aSkipList.displayList(cout);

    printAt(aSkipList, 37);

    for (int i = 0; i < 30; ++i)
    {
        oss << "A" << i;

        aSkipList.remove(new string(oss.str()));

        oss.str("");
    }

    aSkipList.displayList(cout);

    printAt(aSkipList, 1);

    return 0;
}