Listing 1: Classes SLPosition and SkipList
#include <stdlib.h> #include <assert.h> const int SLMAX_LEVEL = 15; template <class DATA, class KEY> class Skiplist; // forward declaration for friend statement template <class DATA, class KEY> class SLPosition { DATA *data; KEY key; SLPosition<DATA,KEY> **forward; public: SLPosition( int level ); SLPosition( int level, DATA *cdata, const KEY &ckey ); ~SLPosition() { // note that we don't delete data as we can't tell who else // might have a pointer to it delete [] forward; } friend class Skiplist<DATA,KEY>; }; template <class DATA, class KEY> class Skiplist { SLPosition<DATA,KEY> head; int level; // the number of lists in the skiplist int rand_level(); public: Skiplist(); void insert( DATA *data, const KEY &key ); DATA * remove( const KEY &key ); DATA * find( const KEY &key ); }; /* End of File */