English
bb1_tree.h
资源名称：leda.tar.gz [点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：6k
源码类别：
数值算法/人工智能
开发平台：
MultiPlatform
- /*******************************************************************************
- +
- + 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
