skiplist.h

This software was done in part for a textbook on AI I ve written called _The Basis of AI_ (tentative

/*******************************************************************************
+
+  LEDA 3.5
+
+
+  skiplist.h
+
+
+  Copyright (c) 1995, 1996, 1997  by  LEDA Software GmbH
+  Postfach 151101, 66041 Saarbruecken, Germany
+  All rights reserved.
+ 
*******************************************************************************/


#ifndef LEDA_SKIPLIST_H
#define LEDA_SKIPLIST_H

#include <LEDA/basic.h>

//------------------------------------------------------------------------------
// Pugh's skip lists
//------------------------------------------------------------------------------

class __exportC skiplist_node
{ 
  friend class __exportC skiplist;

  static leda_mutex mutex_id_count;
  static unsigned long id_count;

  GenPtr key;
  GenPtr inf;
  int    level;
  unsigned long id;           // id number
  skiplist_node* pred;  
  skiplist_node* backward;  
  skiplist_node* forward[1];  // variable sized array of forward pointers 

  friend unsigned long ID_Number(skiplist_node* p) { return p->id; }

 };

typedef skiplist_node* skiplist_item;


class __exportC skiplist
{  
   int level;                  // maximum level
   skiplist_node*  header;     // pointer to header
   skiplist_item  stopper;     // pointer to end 
   unsigned long randomBits;   // random bit source
   int randomsLeft;            // number of unused bit pairs in randomBits
   int count;                  // number of entries

   float prob;                 

   random_source ran;

   int  randomLevel();

virtual int cmp(GenPtr, GenPtr) const { return 0; }
virtual void copy_key(GenPtr&)  const {}
virtual void copy_inf(GenPtr&)  const {}
virtual void clear_key(GenPtr&) const {}
virtual void clear_inf(GenPtr&) const {}
virtual void print_key(GenPtr)  const {}
virtual void print_inf(GenPtr)  const {}

virtual int key_type_id()       const { return UNKNOWN_TYPE_ID; }

skiplist_item search(GenPtr,int&) const;
skiplist_item gen_search(GenPtr,int&) const;
skiplist_item int_search(GenPtr,int&) const;
skiplist_item double_search(GenPtr,int&) const;

void          remove_item(skiplist_item);
void          insert_item_at_item(skiplist_item,skiplist_item);

public:

 typedef skiplist_item item;

 skiplist(float prob = 0.25);
 skiplist(const skiplist&);
 skiplist& operator=(const skiplist&);
 virtual ~skiplist();

 GenPtr key(skiplist_item p) const;
 GenPtr& inf(skiplist_item p) const;
 int     get_level(skiplist_item p) const;

 skiplist_item insert(GenPtr key, GenPtr inf);
 skiplist_item locate(GenPtr key) const;
 skiplist_item locate_succ(GenPtr key) const;
 skiplist_item locate_pred(GenPtr key) const;
 skiplist_item lookup(GenPtr key) const;
 skiplist_item min() const;
 skiplist_item max() const;
 void          reverse_items(skiplist_item,skiplist_item);
 void          del(GenPtr key);
 void          del1(GenPtr key);

 void          conc(skiplist&);
 void          split_at_item(skiplist_item,skiplist&,skiplist&);

 void          print();

 skiplist_item insert_at_item(skiplist_item p, GenPtr key, GenPtr inf);

 skiplist_item insert1(GenPtr key, GenPtr inf);


 void          change_inf(skiplist_item p, GenPtr inf);
 void          del_item(skiplist_item p);
 void          clear();
 int           size() const;
 int           empty() const;

 skiplist_item first_item() const;
 skiplist_item end_item() const;
 skiplist_item next_item(skiplist_item p) const;
 skiplist_item succ(skiplist_item p) const;
 skiplist_item pred(skiplist_item p) const;


 // piority queue operations

 skiplist_item find_min() const;
 void del_min();
 void decrease_key(skiplist_item p, GenPtr k);


};




inline GenPtr  skiplist::key(skiplist_item p) const { return p->key; }
inline GenPtr& skiplist::inf(skiplist_item p) const { return p->inf; }

inline int     skiplist::get_level(skiplist_item p) const { return p->level; }


inline skiplist_item skiplist::end_item() const { return 0; }  

inline skiplist_item skiplist::first_item() const  
{ skiplist_item q = header->forward[0];
  return (q==stopper) ? 0 : q;
 }

inline skiplist_item skiplist::min() const  
{ skiplist_item q = header->forward[0];
  return (q==stopper) ? 0 : q;
 }

inline skiplist_item skiplist::max() const  
{ skiplist_item q = stopper->pred;
  return (q==header) ? 0 : q;
 }

inline skiplist_item skiplist::next_item(skiplist_item p) const 
{ if (p)
  { skiplist_item q =  p->forward[0]; 
    return (q==stopper) ? 0 : q;
   }
  else return 0;
 }

inline skiplist_item skiplist::succ(skiplist_item p) const 
{ skiplist_item q =  p->forward[0]; 
  return (q==stopper) ? 0 : q;
 }

inline skiplist_item skiplist::pred(skiplist_item p) const 
{ skiplist_item q =  p->pred; 
  return (q==header) ? 0 : q;
 }

inline void skiplist::change_inf(skiplist_item p, GenPtr inf) 
{ clear_inf(p->inf); 
  copy_inf(inf);  
  p->inf = inf; 
 }

inline int  skiplist::size() const { return count; }
inline int  skiplist::empty() const { return count==0; }

//priority queue
inline skiplist_item skiplist::find_min() const { return min(); }

inline void skiplist::del_min() 
{ skiplist_item p = min(); if (p) del_item(p); }

inline void skiplist::decrease_key(skiplist_item p, GenPtr k) 
{ insert(k,p->inf); del_item(p);}


#endif