Tech or Treat! Write an article about your scariest tech disaster to win gadgets!Learn more


How To Create A Skip List in C++?

Posted on 2009-05-10
Medium Priority
Last Modified: 2012-06-21
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.

Question by:btlovesyou
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions

Assisted Solution

zwei earned 800 total points
ID: 24350102
This might help (describes implementing skip lists in c++):
LVL 39

Accepted Solution

itsmeandnobodyelse earned 1200 total points
ID: 24361828
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


Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses

647 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question