Skiplist.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/memory.h>
 
#include <cstdlib>
#include <ctime>
 
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() : m_lSize(0) {
        srand((unsigned int)time(nullptr));
        m_realheight = 5;
        m_height = 1;
        m_start = (Element**)malloc(m_realheight * sizeof(Element*));
        m_start[0] = nullptr;
    }
 
    ~Skiplist() {
        clear();
        free(m_start);
    }
 
    bool isElement(X item) const {
        int h = m_height - 1;
        Element** cur = m_start; // wheeha!
        while (true) {
            if (cur[h] && *(cur[h]->entry) < *item) { //nxt != nullptr
                cur = cur[h]->next;
            } else if (--h < 0) {
                return cur[0] && *(cur[0]->entry) == *item;
            }
        }
    }
 
    void add(X item) {
        m_lSize++;
 
        int nh = random_height();
        Element* n = new Element(item, nh);
        if (nh > m_height) {
            grow(nh);
        }
 
        int h = m_height - 1;
        Element** cur = m_start; // wheeha!
        while (true) {
            if (cur[h] && *(cur[h]->entry) < *item) { //nxt != nullptr
                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 m_lSize; }
 
    bool empty() const { return m_lSize == 0; }
 
 
    void clear(bool killData = false) {
        Element* item = m_start[0];
        while (item) {
            Element* old = item;
            item = item->next[0];
            if (killData) {
                delete old->entry;
            }
            delete old;
        }
        m_lSize = 0;
        m_height = 1;
        m_start[0] = nullptr;
    }
 
    const SkiplistIterator<X> begin() const { return m_start[0]; }
 
    const SkiplistIterator<X> end() const { return nullptr; }
 
private:
    int m_lSize;
    Element** m_start;
    int m_height;
    int m_realheight;
 
    int random_height() {
        int h = 1;
        while (rand() > RAND_MAX / 2) {
            h++;
        }
        return h;
    }
 
    void grow(int newheight) {
        if (newheight > m_realheight) {
            m_realheight = newheight;
            Element** newStart =
                    static_cast<Element**>(realloc(m_start, m_realheight * sizeof(Element*)));
            if (newStart == nullptr) {
                free(m_start);
            } else {
                m_start = newStart;
            }
        }
        for (int i = newheight; i-- > m_height;) {
            m_start[i] = nullptr;
        }
        m_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 != nullptr; }
 
    SkiplistIterator<X>& operator++() {
        el = el->next[0];
        return *this;
    }
 
    SkiplistIterator<X> operator++(int) {
        SkiplistIterator<X> it = *this;
        el = el->next[0];
        return it;
    }
 
    bool operator==(const SkiplistIterator<X> other) const { return el == other.el; }
 
    bool operator!=(const SkiplistIterator<X> other) const { return !operator==(other); }
};
 
}