/*******************************************************************************++  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