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

Get proactive database performance tuning online

At Percona’s web store you can order full Percona Database Performance Audit in minutes. Find out the health of your database, and how to improve it. Pay online with a credit card. Improve your database performance now!

Question has a verified solution.

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

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

765 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