?
Solved

Ned Help w/ simple Skip List

Posted on 2004-04-20
6
Medium Priority
?
411 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 504 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 498 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 498 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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

771 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