Skiplist.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifndef OGDF_SKIPLIST_H
#define OGDF_SKIPLIST_H

#include <ogdf/basic/basic.h>

namespace ogdf {

template<class X> class SkiplistIterator;


template<class X> class Skiplist {
    friend class SkiplistIterator<X>;
    friend class Element;
    
    class Element {
        friend class Skiplist<X>;
        friend class SkiplistIterator<X>;
    
        X entry; // content
        Element** next; // successor elements
    
        // construction
        Element(const X &item, int height) :
                entry(item) {
            next = (Element**)malloc(height*sizeof(Element*));
        }
        
        ~Element() {
            free(next);
        }
    
        OGDF_NEW_DELETE
    };
    
public:

    Skiplist() : lSize(0) {
        srand(time(NULL));
        realheight = 5;
        height = 1;
        start = (Element**)malloc(realheight*sizeof(Element*));
        start[0] = NULL;
    }
    
    ~Skiplist() {
        clear();
        free(start);
    }

    bool isElement(X item) const {
        int h = height - 1;
        Element** cur = start; // wheeha!
        while(true) {   
            if( cur[h] && *(cur[h]->entry) < *item ) //nxt != NULL
                cur = cur[h]->next;
            else if(--h < 0)
                return cur[0] && *(cur[0]->entry) == *item;
        }
    }
    
    void add(X item) {
        lSize++;
        
        int nh = random_height();
        Element* n = OGDF_NEW Element(item, nh);
        if(nh > height)
            grow(nh);           

        int h = height - 1;
        Element** cur = start; // wheeha!
        while(true)  {  
            if( cur[h] && *(cur[h]->entry) < *item ) //nxt != NULL
                cur = cur[h]->next;
            else {
                if(h < nh) { // add only if new element is high enough
                    n->next[h] = cur[h];
                    cur[h] = n;
                }
                if(--h < 0)
                    return;
            }
        }
    }   

    int size() const { return lSize; }
    
    int empty() const { return (lSize==0); }


    void clear(bool killData = false) {
        Element* item = start[0];
        Element* old;
        while(item) {
            old = item;
            item = item->next[0];
            if(killData)
                delete old->entry;
            delete old;
        }
        lSize = 0;
        height = 1;
        start[0] = 0;
    }
    
    const SkiplistIterator<X> begin() const { return start[0]; }

private:
    int lSize;
    Element** start;
    int height;
    int realheight;

    int random_height() {
        int h = 1;
        while(rand() > RAND_MAX/2) h++;
        return h;
    }
    
    void grow(int newheight) {
        if(newheight > realheight) {
            realheight = newheight;
            start = (Element**)realloc(start, realheight*sizeof(Element*));
        }
        for(int i = newheight; i-->height;) {
            start[i] = NULL;
        }
        height = newheight;
    }
    
};

template<class X> class SkiplistIterator {
    friend class Skiplist<X>;
    
    const typename Skiplist<X>::Element *el;
    
    SkiplistIterator(const typename Skiplist<X>::Element *e) { el = e; }
    
public:

    const X &operator*() const { return el->entry; }
    
    bool valid() const { return el; }
    
    SkiplistIterator<X> &operator++() {
        el = el->next[0];
        return *this;
    }
    SkiplistIterator<X> operator++(int) {
        SkiplistIterator<X> it = *this;
        el = el->next[0];
        return it;
    }   

    SkiplistIterator<X> &operator=(const SkiplistIterator<X> &it) {
        el = it.el;
        return *this;
    }
};

}

#endif /*OGDF_SKIPLIST_H*/