f_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
+
+
+  f_skiplist.h
+
+
+  Copyright (c) 1995, 1996, 1997  by  LEDA Software GmbH
+  Postfach 151101, 66041 Saarbruecken, Germany
+  All rights reserved.
+ 
*******************************************************************************/


#ifndef F_SKIPLIST_H
#define F_SKIPLIST_H

#include <LEDA/basic.h>

class __exportC header_node;
class __exportC f_skiplist_node;

typedef f_skiplist_node* f_skiplist_item;
typedef header_node*    large_item;

class __exportC f_skiplist_node
{ friend class f_skiplist;

  GenPtr key;
  GenPtr inf;
  int    height;
  f_skiplist_item pred;  
  f_skiplist_item backward;  
  //f_skiplist_item* forward;  // pointer to array of forward pointers 
  f_skiplist_item forward[1];

};

class __exportC header_node : public f_skiplist_node
{ friend class __exportC f_skiplist;
  f_skiplist_item for_alignment[32];
  int true_height;
  f_skiplist* myseq;
  
};




class __exportC f_skiplist
{  
large_item  header;         
f_skiplist_item STOP;  
     
float prob; 
int randomBits;           
int randomsLeft;          



                   

   int  randomLevel();

virtual int cmp(GenPtr, GenPtr) const  
{ error_handler(1,"cmp should never be called"); return 0; }

virtual void copy_key(GenPtr&)  const  {  }
virtual void copy_inf(GenPtr&)  const  {  }
virtual void clear_key(GenPtr&) const { 
   error_handler(1,"clear_key should never be called");  }
virtual void clear_inf(GenPtr&) const  { 
   error_handler(1,"clear_inf should never be called");  } 
virtual void print_key(GenPtr)  const   { 
   error_handler(1,"print_key should never be called");  }
virtual void print_inf(GenPtr)  const  { 
   error_handler(1,"print_inf should never be called");  }

/*
virtual int int_type()    const  {  
   error_handler(1,"int_type should never be called"); return 0;  }
   */


virtual int key_type_id()    const  {  
   error_handler(1,"key_type_id should never be called"); return 0;  }

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



f_skiplist_item finger_search(f_skiplist_item,GenPtr,int&) const;
f_skiplist_item gen_finger_search(f_skiplist_item,GenPtr,int&) const;
f_skiplist_item int_finger_search(f_skiplist_item,GenPtr,int&) const;
f_skiplist_item double_finger_search(f_skiplist_item,GenPtr,int&) const;
f_skiplist_item finger_search(GenPtr,int&) const;
f_skiplist_item gen_finger_search(GenPtr,int&) const;
f_skiplist_item int_finger_search(GenPtr,int&) const;
f_skiplist_item double_finger_search(GenPtr,int&) const;
void          remove_item(f_skiplist_item);
void          insert_item_at_item(f_skiplist_item,f_skiplist_item,int);
void          print(const f_skiplist &, ostream&, string s, char space) const;
void          check_data_structure(const f_skiplist&, string s);




public:

 typedef f_skiplist_item item;

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

 GenPtr key(f_skiplist_item p) const;
 GenPtr inf(f_skiplist_item p) const;
 GenPtr& info(f_skiplist_item p) const;
 int     get_height(f_skiplist_item p) const;

 f_skiplist_item insert(GenPtr key, GenPtr inf);

 f_skiplist_item locate(GenPtr key) const;
 f_skiplist_item locate_succ(GenPtr key) const;
 f_skiplist_item locate_pred(GenPtr key) const;
 f_skiplist_item lookup(GenPtr key) const;

 f_skiplist_item finger_locate(f_skiplist_item, GenPtr key) const;
 f_skiplist_item finger_locate_succ(f_skiplist_item,GenPtr key) const;
 f_skiplist_item finger_locate_pred(f_skiplist_item,GenPtr key) const;
 f_skiplist_item finger_lookup(f_skiplist_item,GenPtr key) const;
 
 f_skiplist_item finger_locate(GenPtr key) const;
 f_skiplist_item finger_locate_succ(GenPtr key) const;
 f_skiplist_item finger_locate_pred(GenPtr key) const;
 f_skiplist_item finger_lookup(GenPtr key) const;


 f_skiplist_item min_item() const;
 f_skiplist_item max_item() const;

// sn: for compatibility with skiplist
 f_skiplist_item min() const;
 f_skiplist_item max() const;


 void          reverse_items(f_skiplist_item,f_skiplist_item);
 void          del(GenPtr key);
 void          del1(GenPtr key);

 void          conc(f_skiplist&,int=0);
 void          split_at_item(f_skiplist_item,f_skiplist&,f_skiplist&,int=0);

 void          merge(f_skiplist&);

 void          delete_subsequence(f_skiplist_item,f_skiplist_item, f_skiplist&);


 void          print(ostream& out, string s, char space) const
                { print(*this,out,s,space); }

 void          check_data_structure(string s)
   { check_data_structure(*this,s); }

void          validate_data_structure();

 f_skiplist_item insert_at_item(f_skiplist_item p, GenPtr key, GenPtr inf);
 f_skiplist_item insert_at_item(f_skiplist_item p, GenPtr key, GenPtr inf, int dir);



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

 f_skiplist_item first_item() const;
 f_skiplist_item next_item(f_skiplist_item p) const;
 f_skiplist_item succ(f_skiplist_item p) const;
 f_skiplist_item pred(f_skiplist_item p) const;


 /* piority queue operations */

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


};



inline GenPtr  f_skiplist::key(f_skiplist_item p) const  {  return p->key;  }
inline GenPtr  f_skiplist::inf(f_skiplist_item p) const  { return p->inf; }
inline GenPtr& f_skiplist::info(f_skiplist_item p) const { return p->inf; }

inline int     f_skiplist::get_height(f_skiplist_item p) const  { return p->height; }

inline f_skiplist_item f_skiplist::first_item() const  
{ f_skiplist_item q = header->forward[0];
  return (q==STOP) ? 0 : q;
}

inline f_skiplist_item f_skiplist::min_item() const  
{ f_skiplist_item q = header->forward[0];
  return (q==STOP) ? 0 : q;
}

inline f_skiplist_item f_skiplist::max_item() const  
{ f_skiplist_item q = STOP->pred;
  return (q==header) ? 0 : q;
}

inline f_skiplist_item f_skiplist::min() const { return min_item(); }
inline f_skiplist_item f_skiplist::max() const { return max_item(); }



inline f_skiplist_item f_skiplist::next_item(f_skiplist_item p) const 
{ if (p)
  { f_skiplist_item q =  p->forward[0]; 
    return (q->height < 0) ? 0 : q;
   }
  else return 0;
 }

inline f_skiplist_item f_skiplist::succ(f_skiplist_item p) const 
{ f_skiplist_item q =  p->forward[0]; 
  return (q->height < 0) ? 0 : q;
}


inline void f_skiplist::change_inf(f_skiplist_item p, GenPtr inf)  { p->inf = inf; }
inline int  f_skiplist::empty() const  { return (header->forward[0] == STOP); }

inline f_skiplist_item f_skiplist::find_min() const  { return min_item(); }

inline void f_skiplist::del_min() 
{ f_skiplist_item p = min_item(); if (p) del_item(p); }

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


/* dummy I/O and cmp functions */

inline void Print(const f_skiplist&,ostream&)  {  }
inline void Read(f_skiplist&, istream&)  {  }
inline int  compare(const f_skiplist&,const f_skiplist&)  {  return 0;  }


#endif