Solved

Ned Help w/ simple Skip List

Posted on 2004-04-20
6
408 Views
Last Modified: 2008-02-01
I have a project due next week and I need help w/ some simle skip list stuff. I understand the concepts of skip lists perfectly. HOwever, I am in a algorithm analysis class, not an actual programming course and we are expected to know more than we do. I have no idea how to implement a skip list. I found some code on the net, but it was all advanced -too advanced. We have to make a simple skip list that allow the user to insert the next key value. We then insert the key into the skip list and display a aligned text version of what the skip list looks like. Any help or web references would be greatly appreciated. I'm looking for maybe a constructor for a simple skip list class in c++ or even java.
Thanks
0
Comment
Question by:chuckbeats
[X]
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
6 Comments
 
LVL 22

Accepted Solution

by:
grg99 earned 168 total points
ID: 10867748


Do a google search for "skip list algorithm: and you'll get a bunch of hits.

One in particular gives some coding examples.  Normally I wouldnt refer you to source code, as this is an assignment, but the examples are in C#, which probably isnt  your language of choice, so you're not likely to just copy the code:

http://www.codeproject.com/csharp/SkipList1.asp




0
 
LVL 1

Assisted Solution

by:gamesdev
gamesdev earned 166 total points
ID: 10867787
Hi,
Did you check codeproject's skiplist tutorial?
http://www.codeproject.com/csharp/SkipList1.asp
Also, I found this online, with a skiplist C++ class:
http://www.csee.umbc.edu/courses/undergraduate/341/fall01/Lectures/SkipLists/skip_lists/skip_lists.html

See ya
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 166 total points
ID: 10869748
Below is a 'simple' SkipList implementation of a template class that manages only keys (not keys and data as usual). It works f.for example with strings. To handle classes or structs of your own you have to provide an appropriate copy constructor, operator==()  and operator<().

Tell me if you need an implementation of key and data or a non-template implementation.

Regards, Alex

#ifndef SKIPLIST_H
#define SKIPLIST_H

// standard includes
#include <stdlib.h>
#include <time.h>


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

// forward declaration

template <class T>
class SkipList;

template <class T>
class SkipListIterator;

template <class T>
class SkipListNode;

#define SkipListNodePtr SkipListNode<T>*

/////////////////////////////////////////////////////////////////////////////
// @doc   SkipListNode
//
// @class One node (element) of a skip list. A SkipListNode has a copy of the
//   <nl> key
//

template <class T>
class SkipListNode
{
// @dataprivate
private:
   // Attributes
   T               info;          // @cmember copy of key
   SkipListNode<T>**   arrForward;    // @cmember array of forward pointers

// @funcpublic
public:
   // constructors, destructor

   // @cmember constructor for m_head node; gets all 16 levels
   SkipListNode(int lev);
   // @cmember constructor for data nodes; gets a computed level
   SkipListNode(int lev, const T& key);
   // @cmember destructor deletes the arrays
  ~SkipListNode();
   // @cmember get new pointer array depending on level
   void init(int lev);

public:
   // @cmember get forward pointer of level idx
   SkipListNode<T>*  getForward(int idx)
      { return arrForward[idx]; }
   // @cmember get reference of key
   const T&      getKey()
      { return info; }
   // @cmember set new forward pointer for level idx (chaining)
   void          setForward(int idx, SkipListNode<T>* pForward)
      { arrForward[idx] = pForward; }

   friend class SkipList<T>;
   friend class SkipListIterator<T>;
};


/////////////////////////////////////////////////////////////////////////////
// @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 T>
class SkipList
{
// @dataprivate
private:
   // Attributes
   SkipListNode<T>      m_head;     // @cmember m_head node
   int                  m_depth;    // @cmember current maximal level
   
// @funcprivate
   // compute random level from 0 to SKIPLIST_MAXLEVEL
   int                  randomSkipLevel();

// @funcpublic
public:
   // @cmember default constructor
   SkipList();
   // @cmember destructor; deletes all nodes
  ~SkipList();

   // operations

   // @cmember insert new node and return true if not multiple
   bool        insert( const T& key );
   // @cmember remove existing node and return true if found
   bool        remove( const T& key );
   // @cmember find node by key
   bool        find( const T& key   );
   // @cmember get first key (not using an iterator)
   const T*    getFirst();
   // @cmember pop first key (get first node and remove it)
   T*          popFirst();
   // @cmember check if empty
   bool        isEmpty()
      {  return (m_head.getForward(0) == NULL); }

// @funcpublic
public:
   void        makeEmpty();
   int         count();
   void        display();
   int         depth()
   {  return m_depth; }

   friend class SkipListIterator<T>;
};

/////////////////////////////////////////////////////////////////////////////
// @doc   SkipListIterator
//
// @class Iterator for a SkipList dictionary.
//   <nl> Step forward (ascending sort order) to SkipList
//
template <class T>
class SkipListIterator
{
// @dataprivate
private:
   // Attributes
   SkipList<T>* list;       // @cmember pointer to SkipList
   SkipListNode<T>* current;    // @cmember current node
   int          curLev;     // @cmember current level

// @funcpublic
public:
   // constructor / destructor


   // @cmember constructor; gets the SkipList to iterate on
   SkipListIterator(SkipList<T>* pList)
      : list(pList), current(NULL) {}
   // @cmember default destructor
  ~SkipListIterator() {}

   // @cmember get next element
   const T*    getNext( bool& bFirst );
   // @cmember find next element and set current to find position
   const T*    findNext( bool& bFirst, const T& key );
};


#endif // SKIPLIST_H


// @mfunc constructor for m_head node (maximal m_depth)
template <class T>
inline
SkipListNode<T>::SkipListNode(int lev)
{
   init(lev);
}

// @mfunc constructor with random m_depth, data and key
template <class T>
inline
SkipListNode<T>::SkipListNode(int lev, const T& key)
: info(key)
{
   init(lev);
}

// @mfunc create skip array with requested m_depth
template <class T>
inline
void SkipListNode<T>::init(int lev)
{
   arrForward = new SkipListNodePtr[lev];
   for (int i = 0; i < lev; i++)
      arrForward[i] = NULL;
}

// @mfunc destructor
// Note: data pointers will NOT be deleted; This MUST be done elsewhere
template <class T>
inline
SkipListNode<T>::~SkipListNode()
{
   delete [] arrForward;
}


// @mfunc default constructor; creates m_head node and initializes start m_depth to 1
template <class T>
inline
SkipList<T>::SkipList()
: m_head(SKIPLIST_MAXLEVEL), m_depth(1)
{
   // we initialize the random number generation by current system time
   // therefore we get new random numbers for each skiplist

   srand( (unsigned)time( NULL ) );
}

// @mfunc destructor
template <class T>
inline
SkipList<T>::~SkipList()
{
   SkipListNodePtr pCur = m_head.getForward(0);
   SkipListNodePtr pLst = NULL;

   while (pCur != NULL)
   {
      pLst = pCur;
      pCur = pCur->getForward(0);
      delete pLst;
   }
}

// operations

// search
template <class T>
inline
bool SkipList<T>::find( const T& key   )
{
   SkipListNodePtr pCur  = &m_head;

   for (int i = m_depth-1; i >= 0; i--)
   {
      while (pCur->getForward(i) != NULL &&
             pCur->getForward(i)->getKey() < key)
         pCur = pCur->getForward(i);
   }

   pCur  = pCur->getForward(0);
   if (pCur != NULL && pCur->getKey() == key)
   {
      return true;
   }

   return false;
}

// get random from 1 ... SKIPLIST_MAXLEVEL
template <class T>
inline
int SkipList<T>::randomSkipLevel()
{
   int lev = 1;
   while (rand() % SKIPLIST_PROBABILITY == 0 && lev < SKIPLIST_MAXLEVEL)
      lev++;
   return lev;
}

template <class T>
inline
bool  SkipList<T>::insert( const T& key )
{
   SkipListNodePtr pUpdate[SKIPLIST_MAXLEVEL] = { NULL };
   SkipListNodePtr pCur = &m_head;

   int i;
   for (i = m_depth-1; i >= 0; i--)
   {
      while (pCur->getForward(i) != NULL &&
             pCur->getForward(i)->getKey() < key)
         pCur = pCur->getForward(i);

      pUpdate[i] =  pCur;
   }

   if (pCur->getForward(0) != NULL && pCur->getForward(0)->getKey() == key)
   {
       return false;
   }
   int           nPosLevel   = randomSkipLevel();
   SkipListNodePtr   pNew        = new SkipListNode<T>(nPosLevel, key);
   for ( ; m_depth < nPosLevel; m_depth++)
      pUpdate[m_depth] = &m_head;

   for (i = 0; i < nPosLevel; i++)
   {
      pNew->setForward(i, pUpdate[i]->getForward(i));
      pUpdate[i]->setForward(i, pNew);
   }
   return true;
}

template <class T>
inline
bool SkipList<T>::remove(const T& key)
{
   SkipListNodePtr pUpdate[SKIPLIST_MAXLEVEL] = { NULL };
   SkipListNodePtr pCur = &m_head;

   int i;
   for (i = m_depth-1; i >= 0; i--)
   {
      while (pCur->getForward(i) != NULL &&
             pCur->getForward(i)->getKey() < key)
      {
         pCur = pCur->getForward(i);
      }
      pUpdate[i] =  pCur;
   }
   pCur = pCur->getForward(0);

   if (pCur != NULL && pCur->getKey() == key)
   {
      for (i = 0; i < m_depth; i++)
      {
         if (pUpdate[i]->getForward(i) != pCur)
            break;
         else
            pUpdate[i]->setForward(i, pCur->getForward(i));
      }

      delete pCur;
      while (m_depth > 0 && m_head.getForward(m_depth-1) == NULL)
         m_depth--;

      return true;
   }

   return false;
}

// @mfunc get first key (not using an iterator)
template <class T>
inline
const T* SkipList<T>::getFirst()
{
   SkipListNodePtr pCur = m_head.getForward(0);
   T*          pKey = (pCur != NULL)? &pCur->getKey() : NULL;

   return pKey;
}

// @mfunc pop first key (get first node and remove it)
template <class T>
inline
T* SkipList<T>::popFirst()
{
   SkipListNodePtr pCur  = m_head.getForward(0);
   if (pCur != NULL)
   {
      T*  pKey  = new T;
      *pKey     = pCur->getKey();
      remove(*pKey);
      return pKey;
   }
   return NULL;
}

// @mfunc delete all entries and reset
template <class T>
inline
void SkipList<T>::makeEmpty()
{
    SkipListNodePtr pCur = m_head.getForward(0);
    SkipListNodePtr pLst = NULL;
   
    while (pCur != NULL)
    {
        pLst = pCur;
        pCur = pCur->getForward(0);
        delete pLst;
    }
    m_head.init(SKIPLIST_MAXLEVEL);
    m_depth = 1;
}

// @mfunc count entries
template <class T>
inline
int SkipList<T>::count()
{  
    SkipListNodePtr pCur  = &m_head;
    int             n = 0;
    while ((pCur = pCur->getForward(0)) != NULL)
        n++;
    return n;
}

// @mfunc show entries
template <class T>
inline
void SkipList<T>::display()
{
    SkipListNodePtr pUpdate[SKIPLIST_MAXLEVEL] = { NULL };
    SkipListNodePtr pCur  = &m_head;
    for (int i = 1; i < m_depth; i++)
    {
        pUpdate[i] = m_head.getForward(i);
    }
   
    while ((pCur = pCur->getForward(0)) != NULL)
    {
        cout << pCur->getKey();
        for (int i = 1; i < m_depth; i++)
        {
            if (pUpdate[i] == pCur)
            {
                pUpdate[i] = pCur->getForward(i);
                cout << " | " << pCur->getKey();
            }
            else
                break;
        }
        cout << endl;
    }
}


///////////////////////////////////////////////////////////////////////////
// implementation of class SkipListIterator<T>
//
template <class T>
inline
const T* SkipListIterator<T>::getNext(bool& bFirst)
{
   if (list == NULL)
      return NULL;

   if (bFirst || current == NULL)
      current = &list->m_head;

   curLev = 1;

   bFirst  = true;
   if (current != NULL && current->getForward(0) != NULL)
   {
      bFirst   = false;
      current  = current->getForward(0);
      return &current->getKey();
   }
   return NULL;
}

template <class T>
inline
const T* SkipListIterator<T>::findNext(bool& bFirst, const T& key)
{
   if (list == NULL)
      return NULL;

   if (bFirst || current == NULL)
   {
      current  = &list->m_head;
      curLev   = list->m_depth;
   }

   T*   pKey = NULL;
   int  i    = 0;

   bFirst = true;
   if (current != NULL && current->getForward(0) != NULL)
   {
      for (i = curLev - 1; i >= 0; i--)
      {
         while (current->getForward(i) != NULL &&
                current->getForward(i)->getKey() < key)
            current = current->getForward(i);

         if (current->getForward(0) != NULL &&
             current->getForward(0)->getKey() == key)
         {
            pKey    = &current->getForward(0)->getKey();
            while (i > 0 && current->getForward(0) != current->getForward(i))
                i--;
            break;
         }
      }

      bFirst   = false;
      if (pKey != NULL)
         current = current->getForward(0);

   }
   curLev = (i > 0)? i + 1 : 1;

   return pKey;
}


0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Ready to improve network connectivity? Watch this webinar to learn how SD-WANs and a one-click instant connect tool can boost provisions, deployment, and management of your cloud connection.

Question has a verified solution.

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

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

728 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