SkipListGen.hpp

#ifndef GM_SKIP_LISTS_HPP_
#define GM_SKIP_LISTS_HPP_
 
#include <geotypes.hpp>
 
namespace Geometrics
{
   class RandomHeight
   { public:
      RandomHeight(int maxLvl, float prob);
      ~RandomHeight() {}
      int newLevel(void);
   private:
      int maxLevel;
      float probability;
   };
   /* End of File */
 
 
   class SkipNodeGeneric
   {
   public:
     /****************************************************/
     /* if iValueSize is non-zero, the construction will */
     /*   allocation memory and copy the value, else     */
     /*   will just use the pointer.                     */
     /****************************************************/
      SkipNodeGeneric ( int  iKeySize,
                        u8*  pu8Key,
            int  iValueSize,
                        u8*  pu8Value,
                        int  iHeight);
     SkipNodeGeneric();
      SkipNodeGeneric      (int  iHeight);
      ~SkipNodeGeneric();
      u8*   getKey(void);
      u8*   getValue(void);
      int   getHeight(void);
      SkipNodeGeneric** m_forwardNodes;
   private:
      int nodeHeight;
      u8*    m_pu8Key;
      u8*    m_pu8Value;
 
   };
 
   typedef int (*SkipListKeyCompareFunction)(u8* pu8Key1, u8* pu8Key2);
 
   class SkipListGeneric
   {
   public:
      SkipListGeneric (float                      fProbability,
                       int                        iMaxHeight,
                       u8                         *iMaxKey,
                       int                        iKeySize,
                       int                        iValueSize,
                       SkipListKeyCompareFunction compareFxn );
      ~SkipListGeneric();
 
      bool     insert   (u8* newKey, u8* newValue);
      bool     insertWithoutCopy  (u8* newKey, u8* newValue);
      bool     remove   (u8* puKey);
      bool     forget   (u8* puKey);
     
      u8*      retrieve (u8* puKey);
      u8*      previousTo (u8* puKey, u8** foundKey);
      u8*      following  (u8* puKey, u8** foundKey);
      u8*      first      (u8** foundKey);
      int      size       ();
   private:
     bool     insertInternal (u8* puKey, u8* puValue, bool makeCopy);
     SkipNodeGeneric  *m_head;
     SkipNodeGeneric  *m_psngTail;
     float probability;
     int maxHeight,
         curHeight,
         m_iKeySize,
         m_iValueSize;
     SkipListKeyCompareFunction  m_compareFxn;
     RandomHeight* randGen;
   };
};
 
#endif