Solved

How To Create A Skip List in C++?

Posted on 2009-05-10
2
2,870 Views
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.

Thanks.
0
Comment
Question by:btlovesyou
2 Comments
 
LVL 7

Assisted Solution

by:zwei
zwei earned 200 total points
ID: 24350102
This might help (describes implementing skip lists in c++):
http://en.literateprograms.org/Skip_list_(C_Plus_Plus)
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 300 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 )

#endif

*/
 

// @enum Skiplist limits

enum

{

   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>

#endif
 

#ifndef MUTEX_H

   #include <mutex.h>

#endif
 

// 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

private:

   // 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

#endif
 

// @funcpublic

public:

   // 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

  ~SkipPosition();

   // @cmember get new pointer array depending on level

   void init(int nLevel);
 

public:

   // @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; }

#endif
 

   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

private:

   // 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

public:

   // @cmember default constructor

   SkipList();

   // @cmember constructor to set multiple Flag

   SkipList(bool multipleAllowed);

   // @cmember destructor; deletes all nodes but no data

  ~SkipList();
 

   // 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

private:

   // 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

public:

   // 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
 

};
 
 

#endif // SKIPLIST_H

Open in new window

0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

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…
Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

747 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now