/*******************************************************************************++  LEDA 3.5+++  ab_tree.h+++  Copyright (c) 1995, 1996, 1997  by  LEDA Software GmbH+  Postfach 151101, 66041 Saarbruecken, Germany+  All rights reserved.+ *******************************************************************************/#ifndef LEDA_AB_TREE_H#define LEDA_AB_TREE_H//------------------------------------------------------------------------------// (a,b)-trees //------------------------------------------------------------------------------#include    <LEDA/basic.h>class __exportC ab_tree;class __exportC ab_tree_node;struct __exportC ab_tree_elem {GenPtr key;ab_tree_node* child;};class __exportC ab_tree_node {friend class __exportC ab_tree;  static leda_mutex mutex_id_count;  static unsigned long id_count;  int height;  int size;  unsigned long id;  ab_tree_node* father;  ab_tree_elem* last;  ab_tree_elem  arr[1];  ab_tree_node*& succ() { return arr[0].child; }  ab_tree_node*& pred() { return arr[1].child; }  GenPtr& key() { return arr[0].key; }  GenPtr& inf() { return arr[1].key; }friend unsigned long ID_Number(ab_tree_node* p) { return p->id; }friend inline ab_tree_node* new_ab_tree_node(int,int,ab_tree_node*,int);};   class __exportC ab_tree   {    int a;    int b;    int height;             /* height of tree   */    int count;              /* number of leaves */    ab_tree_node* root;    ab_tree_node* minimum;      ab_tree_node* maximum;    ab_tree_elem* expand(ab_tree_node*, ab_tree_node*, ab_tree_node*, int);    ab_tree_elem* index(ab_tree_node* v, ab_tree_node* u);    ab_tree_elem* same(ab_tree_node* v);    GenPtr shrink(ab_tree_node* v, ab_tree_elem* pos);    void split_node(ab_tree_node* v);    void share(ab_tree_node* v,ab_tree_node* y,int direct);    void fuse (ab_tree_node* v,ab_tree_node* w);    void del_tree(ab_tree_node* localroot);    void exchange_leaves(ab_tree_node*, ab_tree_node*);    void pr_ab_tree(ab_tree_node*,int) const;    ab_tree_node* locate(GenPtr,bool&) const;    ab_tree_node* copy_ab_tree(ab_tree_node*,ab_tree_node*&,int) const;    virtual int key_type_id() const { return UNKNOWN_TYPE_ID; }    virtual int cmp(GenPtr, GenPtr) const { return 0; }    virtual void clear_key(GenPtr&) const {}    virtual void clear_inf(GenPtr&) const {}    virtual void copy_key(GenPtr&)  const {}    virtual void copy_inf(GenPtr&)  const {}    virtual void print_key(GenPtr)  const {}    virtual void print_inf(GenPtr)  const {}public:    typedef ab_tree_node* item;    void clear();    GenPtr  inf(ab_tree_node* p)  const { return p->inf(); }    GenPtr  key(ab_tree_node* p)  const { return p->key(); }    ab_tree_node* insert(GenPtr, GenPtr);    ab_tree_node* insert_at_item(ab_tree_node*, GenPtr, GenPtr, int);    ab_tree_node* insert_at_item(ab_tree_node*, GenPtr, GenPtr);    ab_tree_node* locate_succ(GenPtr) const;    ab_tree_node* locate_pred(GenPtr) const;    ab_tree_node* locate(GenPtr x) const { return locate_succ(x); }    ab_tree_node* lookup(GenPtr) const;    void del(GenPtr);    void del_item(ab_tree_node*);    void change_inf(ab_tree_node*, GenPtr);    void reverse_items(ab_tree_node*, ab_tree_node*);    void conc(ab_tree&);    void split_at_item(ab_tree_node*, ab_tree&, ab_tree&);    void del_min() { if (minimum) del_item(minimum); }    void decrease_key(ab_tree_node* p, GenPtr k);    bool member(GenPtr k)  const { return (lookup(k))? true: false ; }    ab_tree_node* min()                      const { return minimum; }    ab_tree_node* find_min()                 const { return minimum; }    ab_tree_node* max()                      const { return maximum; }    ab_tree_node* first_item()               const { return minimum; }    ab_tree_node* next_item(ab_tree_node* p) const { return p ? p->succ() : 0; }    ab_tree_node* succ(ab_tree_node* p)      const { return p->succ(); }    ab_tree_node* pred(ab_tree_node* p)      const { return p->pred(); }    int  size()  const { return count;       }    bool empty() const { return (count==0) ? true : false;   }    void print() const { pr_ab_tree(root,1); }    ab_tree(int=2,int=16);     ab_tree(const ab_tree& T);    ab_tree& operator=(const ab_tree&);     virtual ~ab_tree(){ clear(); } };#endif