SkipList.h

Go to the documentation of this file.

#ifndef _SkipList_H
#define _SkipList_H

/*
  SkipList.h

  See: Pugh, William,  "Skip Lists: A Probabilistic Alternative to Balanced Trees"

*/
#include <limits.h> // INT_MAX
#include <SkipListElement.h>

#define SKIPLIST_NOT_FOUND -1

class SkipListElement;

class LINKAGE SkipList{
public:
    SkipList(float probability = 0.5);
    ~SkipList();

    void insert(const Key searchKey, const Value value);
    Key findMAX(const Key searchKey) const; 
    Key findMIN(const Key searchKey) const; 
    /* ITERATOR SUPPRT */
    void reset() {iter = myHeader->getElement(0);}
    int step() {
        iter = iter->getElement(0); return (iter != NIL);
    }

    Key getkey() {
        if (iter != NIL)
            return iter->getKey();
        else
            return (Key) -1;
    }

    Value getvalue() {
        if (iter != NIL)
            return iter->getValue();
        else
            return (Value) -1;
    }

    void free(const Key searchKey); 
    void freeRange(const Key loKey, const Key hiKey);

    void stat(); 

private:
    float myProbability;
    SkipListElement* myHeader;
    SkipListElement* iter;
    long myLength;
};

#endif // _SkipList_H