Solved

Ned Help w/ simple Skip List

Posted on 2004-04-20
6
400 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
6 Comments
 
LVL 22

Accepted Solution

by:
grg99 earned 168 total points
Comment Utility


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
Comment Utility
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
Comment Utility
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
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.

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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now