• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3102
  • Last Modified:

How To Create A Skip List in C++?

I'm working on an assignment for one of my classes that I'm having a lot of trouble with.  Basically we have to implement a skip list that stores rectangle names and their coordinates.  We also have to implement a couple of other functions, like:

insert name x y w h  (where x y is the bottom coordinate of the rectangle, w is the width, h is the height, and name is the key that it will be sorted by in the skip list)

remove name

remove x y w h

rangesearch x y w h (report all rectangles in the skip list that intersect the query rectangle)

allintersections  (report all rectangles that intersect with others)

search name (return parameters of rectangle name)

Also, when we implement the skip list, in order to receive full credit we need to implement it using node splicing, where basically you store within a node an array called forward that keeps a number of pointers equal to the number of lists in participates in.

We also need to maintain a header array that points to the beginning of the lists at each level. Since the number of levels can grow during insertion of successive nodes I also need to implement a procedure that allows the forward array to be extendible.

I cannot use existing STL C++ templates either.  I pretty much understand the concept, but I'm having trouble translating it into code, so what I'm looking for in a good solution is a link to or example code that does what I have described.

2 Solutions
zweiSoftware DeveloperCommented:
This might help (describes implementing skip lists in c++):
Below is my own implementation of a SkipList.

The bastypes.h containes some typedefs which you easily can replace. The mutex.h contains a mutex class based on CRITICAL_SECTION resource.

As it is an assignment I can't you give the implementation (which is in skiplist.cpp that must be included by the source using the SkipList).

But you may ask for any implementation and I could give you some code snippets if somewhat is unclear.

#ifndef SKIPLIST_H
#define SKIPLIST_H
// standard includes
#include <stdlib.h>
#include <time.h>
#ifdef _WINDOWS
// suppress warning <<duplicate template instantiation>>
   #pragma warning( disable : 4660 )
// @enum Skiplist limits
   SKIPLIST_MAXLEVEL    = 15, // @emem for about 1 billion (10^9) nodes
   SKIPLIST_PROBABILITY = 4   // @emem probability for next higher skip list 1/4
// project includes
#ifndef BASTYPES_H
   #include <bastypes.h>
#ifndef MUTEX_H
   #include <mutex.h>
// forward declaration
template <class TData, class TKey>
class SkipList;
template <class TData, class TKey>
class SkipListIterator;
template <class TData, class TKey>
class SkipPosition;
#define SkipPositionPtr SkipPosition<TData, TKey>*
// @doc   SkipPosition
// @class One node (element) of a skip list. A SkipPosition has a copy of the
//   <nl> key and a pointer to the data part of the element.
template <class TData, class TKey>
class SkipPosition
// @dataprivate
   // Attributes
   TData*                        m_pData;          // @cmember pointer to data
   TKey                          m_key;            // @cmember copy of key
   SkipPosition<TData, TKey>**   m_pArrForward;    // @cmember array of forward pointers
#ifdef _DEBUG
   int                           m_nLevel;         // skip level for debug purposes
// @funcpublic
   // constructors, destructor
   // @cmember constructor for head node; gets all 16 levels
   SkipPosition(int nLevel);
   // @cmember constructor for data nodes; gets a computed level
   SkipPosition(int nLevel, TData* pData, const TKey& key);
   // @cmember destructor deletes the array (chain) but not the data
   // @cmember get new pointer array depending on level
   void init(int nLevel);
   // @cmember get forward pointer of level idx
   SkipPosition<TData, TKey>*  getForward(int idx)
      { return m_pArrForward[idx]; }
   // @cmember get data pointer
   TData*                       getData()
      { return m_pData; }
   // @cmember get reference of key
   const TKey&                  getKey()
      { return m_key; }
   // @cmember set new forward pointer for level idx (chaining)
   void                         setForward(int idx, SkipPosition<TData, TKey>* pForward)
      { m_pArrForward[idx] = pForward; }
#ifdef _DEBUG
   int                          getLevel()
      { return m_nLevel; }
   friend class SkipList<TData, TKey>;
   friend class SkipListIterator<TData, TKey>;
// @class   Balanced template dictionary. The balancing is done
//          by using a random number of single chained sorted lists.
//          The list of level 0 contains all nodes, level 1 about 1/4,
//          level 2 about 1/16 and so on. For each new node the level
//          of skiplists will be randomly computed. The search strategy
//          is now to start at the highest skip level till the new
//          key is less than one of the nodes keys, go one level
//          down searching again, and so on. On level 0 the key is
//          or a new insertion point is found.
template <class TData, class TKey>
class SkipList
// @dataprivate
   // Attributes
   SkipPosition<TData, TKey>     m_head;     // @cmember head node
   int                           m_nLevel;   // @cmember current maximal level
   CriticalSection               m_cs;       // @cmember to make the map thread-safe
   bool                          m_multiple; // @cmember multiple entries having the same key allowed
// @funcprivate
   // compute random level from 0 to SKIPLIST_MAXLEVEL
   int      randomSkipLevel();
// @funcpublic
   // @cmember default constructor
   // @cmember constructor to set multiple Flag
   SkipList(bool multipleAllowed);
   // @cmember destructor; deletes all nodes but no data
   // operations
   // @cmember   new node
   void         insert( TData* pData, const TKey& key );
   // @cmember remove existing node and return data pointer
   TData*       remove( const TKey& key, TData* pData = NULL );
   // @cmember remove existing node where a not unique key is indexed
   TData*       removeMultiple( const TKey& key, int idx, TData* pData = NULL  );
   // @cmember find node by key
   TData*       find( const TKey& key   );
   // @cmember find node by key and index (if key is not unique)
   TData*       findMultiple( const TKey& key, int idx );
   // @cmember get first node (not using an iterator)
   TData*       getFirst();
   // @cmember get first key (not using an iterator)
   TKey*        getFirstKey();
   // @cmember pop first node (get first node and remove it)
   TData*       popFirst();
   // @cmember check if empty
   bool         isEmpty()
      {  return (m_head.getForward(0) == NULL); }
   // @cmember removes and deletes all data items
   int          deleteAllData();
   // @cmember  gives reference to existing value or insert nodes
   TData&       operator[] (const TKey& key);
   // @cmember get number of entries  
   int          getCount();
   friend class SkipListIterator<TData, TKey>;
// @doc   SkipListIterator
// @class Iterator for a SkipList dictionary.
//   <nl> Step forward (ascending sort order) to SkipList
template <class TData, class TKey>
class SkipListIterator
// @dataprivate
   // Attributes
   SkipList<TData, TKey>*     m_pList;       // @cmember pointer to SkipList
   SkipPosition<TData, TKey>* m_pCur;        // @cmember current node
   int                        m_nCurLevel;   // @cmember current level
   TKey                       m_curKey;      // @cmember current key
// @funcpublic
   // constructor / destructor
   // @cmember constructor; gets the SkipList to iterate on
   SkipListIterator(SkipList<TData, TKey>* pList)
      : m_pList(pList), m_pCur(NULL) {}
   // @cmember default destructor
  ~SkipListIterator() {}
   // @cmember get next element
   TData*      getNext( bool& bFirst );
   // @cmember find next element and set current to find position
   TData*      findNext( bool& bFirst, const TKey& key );
   // @cmember return last key found
   const TKey* getCurrentKey() const;
#ifdef _DEBUG
   int      getCurLevel();
#endif // SKIPLIST_H

Open in new window

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Cloud Class® Course: Microsoft Azure 2017

Azure has a changed a lot since it was originally introduce by adding new services and features. Do you know everything you need to about Azure? This course will teach you about the Azure App Service, monitoring and application insights, DevOps, and Team Services.

Tackle projects and never again get stuck behind a technical roadblock.
Join Now