bb1_tree.h

高效数据类型和算法库

/*******************************************************************************
+
+  LEDA-R  3.2.3
+
+  bb1_tree.h
+
+  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/



#ifndef LEDA_BB_TREE_H
#define LEDA_BB_TREE_H

//--------------------------------------------------------------------
//  
//  BB[alpha] Trees
//
//  Michael Wenzel   (1989)
//
// Implementation follows
// Kurt Mehlhorn: Data Structures and Algorithms 1, section III.5.1
//
// Aenderungen:
//   - virtuelle compare-Funktion   (M. Wenzel, Nov. 1989)
//--------------------------------------------------------------------


#include <LEDA/b_stack.h>


// -----------------------------------------------------
// declarations and definitions
// -------------------------------------------------------

const int BSTACKSIZE = 32 ; // according to tree.size and alpha

const float SQRT1_2 = 0.70710678;

class bb1_node;
class bb1_tree;

typedef bb1_node* bb1_item;

typedef bb1_node* bb1_tree_item;

typedef b_stack<bb1_item> bb1_tree_stack;


typedef void (*DRAW_BB_NODE_FCT)(double,double,void*);
typedef void (*DRAW_BB_EDGE_FCT)(double,double,double,double);

class bb1_node {

  GenPtr ke;
  GenPtr inf;
  int gr;
  bb1_item sohn[2];

  friend class bb1_tree;
  friend class range_tree;
  friend class Segment_Tree;
  friend class seg_node_tree;

public:

  GenPtr key()           { return ke; }
  GenPtr info()          { return inf; }

  int blatt()         { return (gr==1); }
  int groesse()       { return gr; }

  float bal()
	{ if (blatt()) return 0.5 ;
	  else return float(float(sohn[0]->groesse())/float(gr));
        }

  bb1_node(GenPtr k=0,GenPtr i=0,int leaf=0,bb1_item ls=0,bb1_item rs=0)
    { ke = k;
      inf = i;
      sohn[0] = ls;
      sohn[1] = rs;
      if (leaf==0)
	gr=1;
      else gr = ls->groesse()+rs->groesse();
    }

  bb1_node(bb1_item p)
    { 
      ke = p->key();
      inf = p->info();
      gr = p->groesse();
      sohn[0] = p->sohn[0];
      sohn[1] = p->sohn[1];
    }
      
  LEDA_MEMORY(bb1_node)

}; 



class bb1_tree {

  bb1_item root;
  bb1_item first;
  bb1_item iterator;
  int   anzahl; 
  float alpha;
  float d;
  bb1_tree_stack st;

  friend class bb1_node;
  friend class range_tree;
  friend class seg_node_tree;
  friend class Segment_Tree;

  int   blatt(bb1_item it)
	{ return (it) ? it->blatt() : 0; }

  void  lrot(bb1_item , bb1_item ); 
  void  rrot(bb1_item , bb1_item ); 
  void  ldrot(bb1_item , bb1_item ); 
  void  rdrot(bb1_item , bb1_item ); 

  void  deltree(bb1_item);
  bb1_item copytree(bb1_item , bb1_item , bb1_item& );
  bb1_item search(GenPtr);
  bb1_item sinsert(GenPtr, GenPtr=0);
  bb1_item sdel(GenPtr );

protected:
 bb1_tree_item item(void* p) const { return bb1_tree_item(p); }


public:

  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 {}

  GenPtr     key(bb1_item it)  const   { return it->ke;  }
  GenPtr&    info(bb1_item it)         { return it->inf; }
  GenPtr     inf(bb1_item it)  const   { return it->inf; }
  GenPtr     translate(GenPtr y);

  bb1_item insert(GenPtr ,GenPtr );
  bb1_item change_obj(GenPtr ,GenPtr );
  bb1_item change_inf(bb1_item it,GenPtr y) { if (it)  
  	                                 { it->inf = y;
                                           return it; }
                                         else return 0;
                                        }

  bb1_item del(GenPtr);

  void del_item(bb1_item it) { if (it) del(it->key()); }
  void del_min() { if (first) del(first->key()); } 
  void decrease_key(bb1_item p, GenPtr k) { GenPtr i = p->info(); 
                                            del(p->key());
                                            insert(k,i);
                                           }

  bb1_item locate(GenPtr)  const;
  bb1_item located(GenPtr) const;
  bb1_item lookup(GenPtr)  const;

  bb1_item cyclic_succ(bb1_item it)  const
  	  { return it ? it->sohn[1] : 0 ; }
  bb1_item cyclic_pred(bb1_item it)  const
	  { return it ? it->sohn[0] : 0 ; }
  bb1_item succ(bb1_item it) const
          { return ( it && it->sohn[1] != first ) ? it->sohn[1] : 0 ; }
  bb1_item pred(bb1_item it) const
          { return ( it && it != first ) ? it->sohn[0] : 0 ; }

  bb1_item ord(int k);
  bb1_item min()       const    { return (first) ? first : 0; }
  bb1_item find_min()  const    { return (first) ? first : 0; }
  bb1_item max()       const    { return (first) ? first->sohn[0] : 0 ; }

  bb1_item first_item() const         { return (first) ? first : 0; }
  bb1_item next_item(bb1_item x) const { return succ(x); }

  bb1_item move_iterator() ;

  int current_item(bb1_item& x) 
     { if (!iterator) return 0;
       else { x = iterator; return 1; }
     }


  void init_iterator()          { iterator = 0; }
  void  lbreak()                { iterator = 0; }


  void  clear();
  int   size()    const        { return anzahl; }
  int   empty()   const        { return (anzahl==0) ? true : false; }

  int   member(GenPtr );
  bb1_tree& operator=(const bb1_tree& w);

  void  set_alpha(float a) 
        { if (anzahl>=3)
             error_handler(4,"aenderung von alpha nicht erlaubt");
          if ((a<0.25) || (a>1-SQRT1_2))
             error_handler(3,"alpha not in range");
          alpha=a;
          d = 1/(2-alpha) ;
        }

  float get_alpha() { return alpha; }

  bb1_tree() : st(BSTACKSIZE)
  { 
    root = first = iterator = 0;
    anzahl = 0;
    alpha=0.28;
    d=1/(2-alpha);
  }

  bb1_tree(float);
  bb1_tree(const bb1_tree&);


// virtual  // if the destructor is declared virtual range/segment trees crash

  ~bb1_tree()  { clear(); }



  void draw(DRAW_BB_NODE_FCT, DRAW_BB_EDGE_FCT, bb1_node*,
            double, double, double, double, double);

  void draw(DRAW_BB_NODE_FCT, DRAW_BB_EDGE_FCT, 
            double, double, double, double);

};


#endif