开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
_ab_tree.c
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：33k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

_ab_tree.c：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _ab_tree.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. #include <LEDA/impl/ab_tree.h>
  16. //---------------------------------------------------------------
  17. //  
  18. //  Michael Wenzel:
  19. //  function insert_at_item added
  20. //
  21. //  double links between leaf and inner node with same key
  22. //
  23. //  delete overwrites copies of keys in inner nodes
  24. //
  25. //  leafs are nodes of degree 1, linked by son[1], son[2]
  26. //
  27. //---------------------------------------------------------------
  29. //------------------------------------------------------------------
  30. // constructors
  31. //------------------------------------------------------------------
  34. ab_tree_node::ab_tree_node(int p_,int height_,int index_,ab_tree_node* father_,int b)
  35. {
  36.     son  = (ab_tree_node**) allocate_words(b+2);   /* array[1..b+1] */
  37.     k    = (GenPtr*) allocate_words(b+1);             /* array[1..b]   */
  38.     same = (ab_tree_node**) allocate_words(b+1);   /* array[1..b]   */
  41.     // position 0 contains the size of the array:
  43.     son[0]  = (ab_tree_node*)(Convert(b+2));
  44.     k[0]    = (GenPtr)(Convert(b+1));
  45.     same[0] = (ab_tree_node*)(Convert(b+1));
  47.     p=p_;
  48.     height=height_;
  49.     index=index_;
  50.     father=father_;
  51.     int i;
  52.     for(i=1;i<=(b+1);son[i++]=0);
  53.     for(i=1;i<=b;k[i++]=0);
  54.     for(i=1;i<=b;same[i++]=0);                
  55.    }
  58.  ab_tree_node::~ab_tree_node() 
  59.  { deallocate_words(son,*(int*)son);    // first element gives size 
  60.    deallocate_words(same,*(int*)same);
  61.    deallocate_words(k,*(int*)k);
  62.   }
  67.  ab_tree::ab_tree(int a_,int b_)
  68.  {
  69.    root=maximum=minimum=0;
  70.    count=0;
  71.    height=-1;
  72.    if((a_>=2)&&(b_>=2*a_-1))
  73.     { a=a_;
  74.       b=b_;
  75.      }
  76.    else error_handler(1,"ab_tree: illegal arguments (a,b) in tree constructor");
  77.  }
  79.  ab_tree::ab_tree(const ab_tree& T)
  80.   {
  81.      if (T.root==0) {root=maximum=minimum=0;height=-1;count=0;}
  82.      else { abnode help=0;
  83.     root = T.copy_ab_tree(T.root,help,T.b);
  84.             maximum=help;
  85.             help=root;
  86.             while (help->p) help=help->son[1];
  87.     minimum=help;
  88.             height=T.height;
  89.             count=T.count;
  90.           };
  91.      a=T.a;
  92.      b=T.b;
  93.   }
  95. //-----------------------------------------------------------------
  96. // operators
  97. //-----------------------------------------------------------------
  99.  ab_tree& ab_tree::operator=(const ab_tree& T)
  100.   {  if (this == &T) return *this;
  102.      clear();
  104.      if (T.root!=0) 
  105.      { abnode help=0;
  106.        root=copy_ab_tree(T.root,help,T.b);
  107.        maximum=help;
  108.        help=root;
  109.        while (help->p) help=help->son[1];
  110.        minimum=help;
  111.        height=T.height;
  112.        count=T.count;
  113.       };
  115.      a=T.a;
  116.      b=T.b;
  118.      return *this;
  119.   }
  122. //-----------------------------------------------------------------
  123. // member functions
  124. //-----------------------------------------------------------------
  126. void ab_tree::exchange_leaves(ab_tree_node* v, ab_tree_node* w)
  127. { // exchange leaves v and w
  129.   GenPtr k1 = v->k[1]; 
  130.   int p1 = v->index;
  131.   ab_tree_node* u1 = v->same[1];
  132.   ab_tree_node* f1 = v->father;
  134.   GenPtr k2 = w->k[1]; 
  135.   int p2 = w->index;
  136.   ab_tree_node* u2 = w->same[1];
  137.   ab_tree_node* f2 = w->father;
  140.   f1->son[p1] = w;
  141.   w->index    = p1;
  142.   w->same[1]  = u1;
  143.   w->father   = f1;
  145.   f2->son[p2] = v;
  146.   v->index    = p2;
  147.   v->same[1]  = u2;
  148.   v->father   = f2;
  150.   ab_tree_node* pred1 = v->son[1];
  151.   ab_tree_node* succ1 = v->son[2];
  153.   ab_tree_node* pred2 = w->son[1];
  154.   ab_tree_node* succ2 = w->son[2];
  156.   w->son[1] = pred1;
  157.   if (pred1) pred1->son[2] = w;
  158.   if (succ1!=w) 
  159.   { w->son[2] = succ1;
  160.     succ1->son[1] = w;
  161.    }
  163.   if (pred2==v) pred2 = w;
  166.   v->son[1] = pred2;
  167.   v->son[2] = succ2;
  168.   pred2->son[2] = v;
  169.   if (succ2) succ2->son[1] = v;
  171.   // minimum & maximum:
  172.   if (v==minimum) minimum = w;
  173.   if (w==maximum) maximum = v;
  175.   // overwrite inner copies:
  176.   
  177.   int pos1=1;
  178.   while(u1->same[pos1]!=v) pos1++;
  180.   int pos2=1;
  181.   if (u2) while(u2->same[pos2]!=w) pos2++;
  183.   u1->k[pos1] = k2;
  184.   u1->same[pos1] = w;
  186.   if (u2) 
  187.   { u2->k[pos2] = k1;
  188.     u2->same[pos2] = v;
  189.    }
  191. }
  193. void ab_tree::reverse_items(ab_tree_node* v, ab_tree_node* w)
  194. { // reverse sequence of leaves: v, ..., w
  196.   if (v==w) return;
  198. /*
  199.   if (cmp(v->k[1],w->k[1])<0) 
  200.   { newline;
  201.     cout << "a = "; print_key(v->k[1]); newline;
  202.     cout << "b = "; print_key(w->k[1]); newline;
  203.     error_handler(1,"ab_tree: illegal reverse_items(a,b)n");
  204.    }
  205. */
  207.   ab_tree_node* u;
  209.   for(;;)
  210.   { exchange_leaves(v,w);
  211.     u = pred(v);
  212.     if (u == w) break;
  213.     v = succ(w);
  214.     if (v==u) break;
  215.     w = u;
  216.    }
  218. }
  221.  void ab_tree::clear()
  222.  { if (root!=0) del_tree(root);
  223.    maximum=minimum=root=0;
  224.    count = 0;
  225.    height=-1;
  226.   }
  229.  void ab_tree::del(GenPtr key)
  230.  { if (!root) return;                      // s.n.
  232.    ab_tree_node* w=locate(key);
  234.    if(w && cmp(w->k[1],key) == 0)  del_item(w);
  236.    else /* error_handler(1,"ab_tree: del(key):key is not in tree") */;
  237.  }
  240. ab_tree_node* ab_tree::expand(ab_tree_node* v,int i)
  242. // expand v by returning an additional son to the right of w
  243. // --> w is the i-th son of v
  244. // s.n.: if i==0 then  new leftmost son
  245. // expand does not test a<=number of sons(v)<=b
  246. // m.w. expand does not set same links for new leaves
  248.  {
  249.    // move the nodes right to w to give an additional son to 
  250.    // the right of w
  252.    int l=(v->p);
  254.    if (i < l)
  255.    {
  256.      v->son[l+1]=v->son[l];
  257.      v->son[l+1]->index=l+1;
  258.      l--;
  259.     }
  261.    while(i < l) 
  262.    { 
  263.      v->k[l+1] = v->k[l];
  264.      v->same[l+1] = v->same[l];
  266.      v->son[l+1]=v->son[l];
  267.      v->son[l+1]->index=l+1;
  269.      l--;
  270.     };
  272.    if (v->height>1)
  273.       v->son[i+1] = new ab_tree_node(0,v->height-1,i+1,v,b);
  274.    else  
  275.       v->son[i+1] = new ab_tree_node(0,v->height-1,i+1,v,1);
  277.    (v->p)++;
  279.    return v->son[i+1];
  280. }                     
  281.                      
  283. void ab_tree::split_node(ab_tree_node* v)
  284. {
  285.  /* adding a child increases the degree of v by 1. If v->p<=b after
  286.     adding the new leave, then we are done . Otherwise we have to 
  287.     split v. Splitting can propagate ==> Loop 
  289.     m.w. changes same links between nodes                          */
  291.   ab_tree_node* y;
  293.   while (v->p==b+1) 
  294.   {
  295.     if (v!=root)  y = v->father;
  296.     else 
  297.     { y=new ab_tree_node(1,v->height+1,0,0,b);
  298.       root=y;height++;
  299.       y->son[1]=v;
  300.       v->index=1;
  301.       v->father=y;
  302.      };
  305.     register ab_tree_node* u;
  307.     u = expand(y,v->index);   // u <-- new right brother of v
  309.     int down =(int)((b+1)/2) ;
  310.     int up = (b+1)- down;
  313.     if (u->index <= b)
  314.     { y->k[u->index] = y->k[v->index];
  315.       y->same[u->index] = y->same[v->index];
  316.      }
  318.     y->k[v->index] = v->k[down];
  319.     y->same[v->index]  = v->same[down];
  320.     y->same[v->index]->same[1] = y;    
  321.  
  323.     // split v, i.e. take the rightmost (b+1)/2 children and keys
  324.     // away from v and incorporate them into u and store key v->k[(b+1)/2]
  325.     // in y ( = father(v))  between the pointers to v and u i.e. at position
  326.     // v->index
  328.     // m.w. change same links of v to y and u
  330.     register int j;
  332.     for (j=1;j<up;j++)    
  333.     {
  334.       u->son[j] = v->son[down+j];
  335.       u->son[j]->index=j;
  336.       u->son[j]->father=u;
  337.       u->k[j] = v->k[down+j];
  338.       u->same[j] = v->same[down+j]; 
  339.       u->same[j]->same[1] = u;      
  341.       v->son[down+j] = 0;      // muss das sein ?
  342.       v->same[down+j] = 0;          
  343.       v->k[down+j] = 0;
  345.      };
  347.     u->son[up]=v->son[b+1];
  348.     u->son[up]->index=up;
  349.     u->son[up]->father=u;
  351.     v->son[b+1] = 0;          // und das?
  352.     v->same[down] = 0;                 
  353.     v->k[down] = 0;
  355.     v->p = down;             // change number of children
  356.     u->p = up;
  358.     v = y;
  359.   }
  361. }
  363. ab_tree_node* ab_tree::insert(GenPtr key, GenPtr inf)
  364. {
  366.  if (root==0) { root=new ab_tree_node(0,0,0,0,1);
  367.                 copy_key(key);
  368.                 copy_inf(inf);
  369.                 root->inf = inf;
  370.                 root->k[1]= key;
  371.                 height=0;
  372.                 maximum=minimum=root;
  373.                 count++;
  374.                 return root;
  375.                }
  377.  // insert_at_item calls copy_key & copy_inf
  379.  ab_tree_node* p = locate(key);
  380.  if (p==nil) p = maximum;
  381.  return insert_at_item(p,key,inf);
  383. }
  385. ab_tree_node* ab_tree::insert_at_item(ab_tree_node* w, GenPtr key, GenPtr inf)
  386. { 
  387.   // insert a new item (key,inf) left or right of leaf w  (according to key(w))
  389.    copy_inf(inf);
  391.    ab_tree_node* v;
  393.     if (cmp(w->k[1],key)!=0)
  394.     {
  395.       copy_key(key);
  397.      if ( w!=minimum && cmp(w->son[1]->k[1],key) > 0)
  398.       { cout << "INSERT_AT: WRONG POSITIONn";
  399.         cout << "insert:   key = "; print_key(key); cout << "n";
  400.         if (w!=maximum) 
  401.            cout << "succ-pos: key = "; print_key(w->son[2]->k[1]); cout << "n";
  402.         cout << "position: key = "; print_key(w->k[1]); cout << "n";
  403.         cout << "pred-pos: key = "; print_key(w->son[1]->k[1]); cout << "n";
  404.         error_handler(1,"ab_tree::insert_at : wrong position "); 
  405.        }
  407.      if ( w!=maximum && cmp(w->son[2]->k[1],key) < 0)
  408.       { cout << "INSERT_AT: WRONG POSITIONn";
  409.         cout << "insert:   key = "; print_key(key); cout << "n";
  410.         cout << "succ-pos: key = "; print_key(w->son[2]->k[1]); cout << "n";
  411.         cout << "position: key = "; print_key(w->k[1]); cout << "n";
  412.         if (w!=minimum)
  413.            cout << "pred-pos: key = "; print_key(w->son[1]->k[1]); cout << "n";
  414.         error_handler(1,"ab_tree::insert_at : wrong position "); 
  415.        }
  418.         count++;
  419.         if (root==w) {   v=new ab_tree_node(2,1,0,0,b);
  420.                          root=v;height=1;
  421.                          ab_tree_node* u;
  422.                          if (cmp(key,w->k[1])<0)
  423.                              {   
  424.                                  u=new ab_tree_node(0,0,1,v,1);
  425.                                  v->son[1]=u;u->k[1]=key; u->inf=inf;
  426.                                  v->son[2]=w ;
  427.                                  v->p=2;v->k[1]=u->k[1];
  428.  u->same[1] = v;
  429.                                  v->same[1] = u;
  430.  w->index=2;
  431.                                  minimum=u;
  432.                                  u->son[2] = w;
  433.                                  w->son[1] = u;
  434.                              }
  435.                          else {
  436.                                  u=new ab_tree_node(0,0,2,v,1);
  437.                                  v->son[1]=w;
  438.  w->same[1] = v;
  439.                                  v->same[1] = w;
  440.                                  v->son[2]=u;u->k[1]=key; u->inf=inf;
  441.                                  v->p=2;v->k[1]=w->k[1];
  442.                                  w->index=1; 
  443.                                  maximum=u;
  444.                                  w->son[2] = u;
  445.                                  u->son[1] = w;
  446.                               }
  447.                          w->father=v;
  449.                          return u;
  450.                       }; 
  452. if ((w!=maximum) && (cmp(key,w->k[1])>0)) w=w->son[2];
  454.         ab_tree_node* u;
  456.         int index1 = w->index;
  458.         v = w->father;
  460.         if (cmp(key,w->k[1])<0)
  461.         { u = expand(v,index1-1);   // new son u left of w
  462. /*
  463.                  v
  465.               /  |  
  467.                 (u)  w  
  468. */
  469.           u->k[1] = key;
  470.           u->inf = inf;
  472.           u->son[2] = w;
  473.           u->son[1] = w->son[1];
  474.           w->son[1] = u;
  476.   u->same[1] = v;        
  477.           v->k[index1] = key;
  478.           v->same[index1] = u ;  
  480.           if (minimum == w)  
  481.              minimum=u;
  482.           else 
  483.              u->son[1]->son[2] = u;
  485.          }
  486.         else 
  487.         { u = expand(v,index1);   // new son u right of w
  488. /*
  489.                  v
  491.               /  |  
  493.              w  (u)     
  494. */
  495.           u->k[1] = key;
  496.           u->inf = inf;
  498.           u->son[1] = w;
  499.           u->son[2] = w->son[2];
  500.           w->son[2] = u;
  502.           if (maximum == w)  
  503.           {
  504.             maximum=u;
  505.             v->k[index1] = w->k[1];
  506.     w->same[1] = v;        
  507.     v->same[index1] = w ;  
  509.            }
  510.           else
  511.           {
  512.             v->k[index1+1] = key;
  513.     u->same[1] = v;        
  514.     v->same[index1+1] = u ;  
  516.             u->son[2]->son[1] = u;
  517.            }
  519.          }
  521.         if (v->p > b) split_node(v);
  523.         return u;
  524.       }
  525.    else { clear_inf(w->inf);
  526.           w->inf = inf; 
  527.           return w;
  528.          }
  529.    }
  531. ab_tree_node* ab_tree::locate(GenPtr key) const
  532.    {
  533.   /* searching for an element key in a (a,b)-tree ;
  534.    we search down the tree starting at the root r until we reache 
  535.    a leave. In each node v we use the sequence k[1](v),..k[v->p-1](v) 
  536.    in order to guide the search to the proper subtree.In the the
  537.    function we assume that k[0](v)<key<k[v->p](v) for every
  538.    element key in U
  539.    locate returns a pointer to a leave*/ 
  541.   if (root == nil) return nil;
  543.   ab_tree_node* v = root;
  544.   GenPtr*       K = v->k;
  545.   int   child_num = v->p;
  547.   if (int_type())
  548.       while (child_num)  // while v is not a leave
  549.       { int i;
  550.         for(i=1; i < child_num && long(key) > long(K[i]); i++); 
  551.         v=v->son[i];
  552.         K=v->k;
  553.         child_num = v->p;
  554.        }
  555.    else
  556.       while (child_num)
  557.       { int i = 1;
  558.         while(i < child_num && cmp(key,K[i]) > 0) i++; 
  559.         v=v->son[i];
  560.         K=v->k;
  561.         child_num = v->p;
  562.        }
  564.   return (cmp(key,v->k[1]) <= 0) ? v : nil;
  565. }
  567. ab_tree_node* ab_tree::locate_succ(GenPtr key) const
  568. { ab_tree_node* v = locate(key);
  569.   if (v==0) return maximum;
  570.   if (cmp(key,v->k[1])==0) return v;
  571.   return v->son[1];
  572.  }
  574. ab_tree_node* ab_tree::locate_pred(GenPtr key) const
  575. { ab_tree_node* v = locate(key);
  576.   if (v==0) return maximum;
  577.   if (cmp(key,v->k[1])==0) return v;
  578.   return v->son[1];
  579.  }
  582. ab_tree_node* ab_tree::lookup(GenPtr k) const 
  583. { ab_tree_node* p = locate(k);
  584.   if (p && cmp(k,key(p))!=0 ) p = 0;
  585.   return p;
  586.  }
  589. void ab_tree::fuse(ab_tree_node* v,ab_tree_node* y)
  590.    {
  591.    /* fuse v and y, i.e. make all sons of y to sons of v and move all
  592.       keys from y to v and delete node y; also move one key (the key
  593.       between the pointers to y and v) from z to v; (note that this will
  594.       shrink z, i.e. decrease the arity of z by one)  
  595.    */
  597.    ab_tree_node* z=v->father;
  599.    GenPtr hilf=z->k[v->index] ;     /* before k[v->p] was not used {=0}*/
  600.               /* 
  601.                  we only must copy the pointer of son and the node-keys
  602.                  from y to v
  603.               */
  604.       /* change same-pointer of y and z                     */
  605.    v->k[v->p]=hilf; 
  606.    v->same[v->p]=z->same[v->index];  
  607.    v->same[v->p]->same[1] = v;       
  609.    int i;
  610.    for(i=1;i<y->p;i++) {  v->k[v->p+i]=y->k[i];
  611.       v->same[v->p+i]=y->same[i];    
  612.       v->same[v->p+i]->same[1]=v;    
  613.                               v->son[v->p+i]=y->son[i];
  614.                               v->son[v->p+i]->index=v->p+i;
  615.                               v->son[v->p+i]->father=v;
  616.                            };
  617.    v->son[v->p+y->p]=y->son[y->p];   /* copy of the last son from y*/
  618.    v->son[v->p+y->p]->index=v->p+y->p;
  619.    v->son[v->p+y->p]->father=v;
  621.    v->p=v->p+y->p;
  623.    for(i=v->index;i<z->p;i++) { z->k[i]=z->k[i+1];
  624. z->same[i] = z->same[i+1]; 
  625.                                 z->son[i+1]=z->son[i+2];
  626.                                 if (z->son[i+1]!=0){z->son[i+1]->index=i+1; 
  627.                                 z->son[i+1]->father=z;};
  628.                                };
  629.    z->p--;
  630.    z->k[z->p]=0;      
  631.    z->same[z->p]=0;   
  633.    delete y;
  634.    
  635.   }
  638.  void ab_tree::share(ab_tree_node* v,ab_tree_node* y,int direct)
  639.  {
  640.   /* we assume that y is the right brother of v;
  641.      take the leftmost son away from y and make it an additional(right-
  642.      most) son of v; also move one key( the key between the pointers
  643.      to v and y) from z down to v and replace it by the leftmost
  644.      key of y;    
  645.      the other case is equivalent
  646.      let z be the father of v
  647.    */
  649.      ab_tree_node* z=v->father;
  651.      if (direct==1)  { 
  652.                        v->son[v->p+1]=y->son[1];
  653.                        v->son[v->p+1]->index=v->p+1;
  654.                        v->son[v->p+1]->father=v;
  655.                        v->k[v->p]=z->k[v->index];
  656.        v->same[v->p]=z->same[v->index];   
  657.                        v->same[v->p]->same[1] = v;    
  658.                        z->k[v->index]=y->k[1];
  659.                        z->same[v->index]=y->same[1];      
  660.        z->same[v->index]->same[1]=z;      
  662.                        v->p++;    
  664.                        for(int i=1;i<(y->p)-1;i++) 
  665.                        { y->son[i]=y->son[i+1];
  666.                          y->son[i]->index=i;
  667.                          y->k[i]=y->k[i+1];
  668.                          y->same[i]=y->same[i+1];
  669.                        };
  671.                        y->p--;     // decrease number of children
  673.                        y->son[y->p]=y->son[y->p+1];
  674.                        y->son[y->p]->index=y->p;
  675.                        y->son[y->p+1]=0;  
  676.                        y->k[y->p]=0;
  677.        y->same[y->p] = 0;                 
  678.                      }
  679.      else            {    // y is at the left side of v
  680.                        for(int i=v->p;i>=1;i--) 
  681.                        { v->son[i+1]=v->son[i];
  682.                          v->son[i+1]->index=i+1;
  683.                          v->k[i+1]=v->k[i];
  684.                          v->same[i+1]=v->same[i]; 
  685.                         };
  687.                        v->son[1]=y->son[y->p];
  688.                        v->son[1]->index=1;
  689.                        v->son[1]->father=v;
  690.                        y->son[y->p]=0;
  692.                        v->p++;
  693.                        y->p--;
  695.                        v->k[1]=z->k[y->index];
  696.        v->same[1]=z->same[y->index];     
  697.        v->same[1]->same[1] = v;            
  698.                        z->k[y->index]=y->k[y->p];
  699.                        z->same[y->index]=y->same[y->p];  
  700.                        z->same[y->index]->same[1] = z;   
  701.                        y->k[y->p]=0;
  702.        y->same[y->p]=0;                    
  703.                      };
  704.      }
  707.  void ab_tree::del_item(ab_tree_node* w)
  708.     {
  709.          /* 
  710.           we must delete leave w with father v
  711.           we shrink v by deleting leave w and one of the keys in the 
  712.           adjacent to the pointer to w 
  713.           (if w is the i-th son of v then we delete k[i](v) if i<v->p
  714.           k[i-1](v) if i=v->p  ).
  715.   m.w. if i=v->p we overwrite the inner node 
  716.        in which key w->k[1] is stored with k[i-1](v)
  717.        and then delete k[i-1](v)
  718.          */
  721.        if (w==nil) error_handler(1,"ab_tree: nil item in del_item");
  723.        count--;
  725.        if (maximum==minimum)  
  726.         { maximum=minimum=root=0; 
  727.           height=-1; 
  728.           clear_key(w->k[1]);
  729.           clear_inf(w->inf);
  730.           delete w; 
  731.           return;
  732.          }
  733. /* here w==root==> last leave will be deleted*/
  734.        
  735.        ab_tree_node* succ = w->son[2];
  736.        ab_tree_node* pred = w->son[1];
  738.        if (pred) pred->son[2]   = succ;
  739.        else minimum = succ;
  740.        if (succ) succ->son[1] = pred;
  741.        else  maximum = pred;
  744.        ab_tree_node* v    = w->father;
  746.        v->son[w->index]=0;
  747.        if (w->index==v->p) {
  748.      if (succ)
  749.      { //overwrite copies in inner node u
  750.        ab_tree_node* u = w->same[1];
  751.        int pos=1;
  752.                                while(u->same[pos]!=w) pos++;
  753.        u->k[pos]=pred->k[1];  
  754.        u->same[pos]=pred;
  755.        pred->same[1] = u;
  756.      }
  757.      else
  758.        v->same[v->p-1]->same[1]=0; 
  759.                              v->k[v->p-1]=0;
  760.      v->same[v->p-1]=0;           
  761.    }
  762.        else                { v->k[w->index]=0 ;
  763.      v->same[w->index]=0;         
  764.                              for(int i=w->index;i<(v->p)-1;i++)
  765.                              { v->k[i]=v->k[i+1];
  766.                                v->same[i]=v->same[i+1]; 
  767.                                v->son[i]=v->son[i+1];
  768.                                v->son[i]->father=v;
  769.                                v->son[i]->index=i;
  770.                               };
  771.                              v->son[v->p-1]=v->son[v->p];
  772.                              v->son[v->p]=0;
  773.                              v->k[v->p-1]=0;
  774.                              v->same[v->p-1]=0;          
  775.                              v->son[v->p-1]->father=v;
  776.                              v->son[v->p-1]->index=v->p-1;
  777.                            };
  779.        clear_key(w->k[1]);
  780.        clear_inf(w->inf);
  781.        delete w;
  783.        (v->p)--;
  784.        
  785.        if ((v==root) && (v->p==1)) {  
  786.                                   if (v->son[1]==0) 
  787.                                       {v->son[1]=v->son[2];
  788.                                        v->son[2]=0;  };
  789.                                   root=v->son[1];
  790.                                   delete v;
  791.                                   root->index=0;
  792.                                   root->father=0;
  793.                                   root->p=0;
  794.                                   root->height=0;
  795.                                   height=0;
  796.                                   minimum=maximum=root;
  797.                                   return; 
  798.                                 };
  800.        if (v->p >= a) return;
  802.     /* otherwise v needs to be rebalanced by either fusing or sharing
  803.      let y be any brother of v*/
  804.      ab_tree_node* z;
  805.      ab_tree_node* y;
  806.      int dir;
  807.        if (v->index==1)  {
  808.                             z=v->father;
  809.                             y=z->son[v->index+1] ;
  810.                            dir=1;    //  y is the right son of v
  811.                          }
  812.        else              { 
  813.                             z=v->father;
  814.                             y=z->son[v->index-1] ;
  815.                            dir =0;   //  y is the left son of v
  816.                          };
  817.        while ((v->p==a-1) && (y->p==a))
  818.             {
  819.              if (dir==1) fuse(v,y); 
  820.              else  fuse(y,v); 
  822.              if (z==root) {
  823.                            if (z->p==1) {
  824.                                          if (dir==1){
  825.                                                       root=v;
  826.                                                       v->father=0;
  827.                                                       v->index=0;   }
  828.                                          else {
  829.                                                 root=y;
  830.                                                 y->father=0;
  831.                                                 y->index=0;    };
  832.                                          height--;
  833.                                          delete z;  
  834.                                        };
  835.                            return;
  836.                           };
  837.              v=z;       // continue recursion
  838.              if (v->index==1)  {z=v->father;
  839.                                 y=z->son[v->index+1] ;
  840.                                 dir=1;  // y is the right son of v
  841.                                }
  842.              else              { z=v->father;
  843.                                  y=z->son[v->index-1];
  844.                                  dir=0;
  845.                                };
  846.             };
  847.     /* we have either v->p>=a and rebalancing is completed or
  848.      v->p = a-1 and y->p > a and rebalancing is completed by sharing;*/
  850.       if (v->p==a-1)
  851.         {       /*
  852.                  it is important to which side y is in order to v
  853.                  ==> dir is an information about in the function share
  854.                 */
  855.            share(v,y,dir);
  856.         };
  857.       return;
  858.  }
  861. ab_tree& ab_tree::conc(ab_tree& s2)
  863. { 
  864.   if ((a!=s2.a)||(b!=s2.b)) 
  865.      error_handler(1,"ab_tree: incompatible trees in concatenate operation");
  867.   if (s2.root==0) return *this;
  869.   if (root==0) 
  870.   { root=s2.root;
  871.     maximum=s2.maximum;
  872.     minimum=s2.minimum;
  873.     height=s2.height;
  874.     count =s2.count;
  875.    }
  876.   else
  877.   { if (cmp(maximum->k[1],s2.minimum->k[1])>=0) 
  878.                     error_handler(1,"ab_tree: join(S,T) : max(S)>=min(T)"); 
  880.     concat(*this,s2,maximum,maximum->k[1]);
  882.     // link leaves 
  883.     maximum->son[2]=s2.minimum;       
  884.     s2.minimum->son[1]=maximum;
  886.     maximum=s2.maximum;              
  887.    }
  889.   s2.root=0;
  890.   s2.maximum=0;
  891.   s2.minimum=0;
  892.   s2.height=-1;
  894.   return *this;
  895. }
  898. /*---------------------------------------------------------------------
  899.   global functions
  900. ----------------------------------------------------------------------*/
  902. void concat(ab_tree& s1,ab_tree& s2,ab_tree_node* current,GenPtr cur_key)
  903. { 
  904.   // Result in s1
  906.   ab_tree_node* v=s1.root;
  907.   ab_tree_node* w=s2.root;
  908.   int h1=v->height;     
  909.   int h2=w->height;
  910.   int i;
  912.   if(h1==h2)
  913.      { ab_tree_node* z=new ab_tree_node(2,h1+1,0,0,s1.b);
  914.        z->son[1]=v;z->son[2]=w; z->k[1]=cur_key;
  915.        z->son[1]->father=z; z->son[2]->father=z;
  916.        z->son[1]->index=1;z->son[2]->index=2;
  917.        z->same[1]=current;              
  918.        current->same[1]=z;              
  919.        s1.height++;
  920.        s1.root=z;
  921.     }
  922.   else { if (h1>h2)
  923.          {
  924.             for(i=1;i<h1-h2;i++,v=v->son[v->p]);  
  925.             v->son[v->p+1]=w;
  926.             v->son[v->p+1]->father=v;
  927.             v->son[v->p+1]->index=v->p+1;
  928.             v->k[v->p]=cur_key;
  929.     v->same[v->p]=current;     
  930.     current->same[1]=v;        
  931.       v->p++;
  932.     if (v->p==s1.b+1)  {s1.split_node(v);  };
  933.         }
  934.         else /* h1<h2 */
  935.         {
  936.    for(i=1;i<=h2-h1-1;i++,w=w->son[1]);
  937.            for(i=w->p;i>1;i--)
  938.             { w->son[i+1]=w->son[i];
  939.               w->son[i+1]->father=w;
  940.          w->son[i+1]->index=i+1;
  941.               w->k[i]=w->k[i-1];
  942.       w->same[i]=w->same[i-1];   
  943.             };
  944.            w->p++;
  945.            w->son[2]=w->son[1];
  946.            w->son[2]->father=w;
  947.            w->son[2]->index=2;
  948.            w->son[1]=v;
  949.            w->son[1]->father=w;
  950.            w->son[1]->index=1;
  951.            w->k[1]=cur_key;
  952.    w->same[1]=current;             
  953.    current->same[1]=w;             
  954.            if (w->p==s2.b+1) {s2.split_node(w);};
  955.    s1.root =  s2.root;
  956.    s1.height =  s2.height;
  957.         }
  958.       }
  960.   /* maximum/minimum are now undefined  */
  962. }
  966. /*
  967. void ab_tree::split_at_key(GenPtr y,ab_tree& L,ab_tree& R)
  968. { ab_tree_node* w = locate(y);
  969.   if (!w) error_handler(1,"ab_tree: split: no item ");
  970.   split_at_item(w,L,R);
  971.  }
  972. */
  974. void ab_tree::split_at_item(ab_tree_node* w,ab_tree& L,ab_tree& R)
  975.   {
  976.     if(((a!=L.a)||(a!=R.a))||((b!=L.b)||(b!=R.b)))
  977.        error_handler(1,"ab_tree: incompatible trees in split operation");
  978.     
  979.     /* initialisation   */
  980.     L.root=L.minimum=L.maximum=0;L.height=-1;
  981.     R.root=R.minimum=R.maximum=0;R.height=-1;
  983.     if(root==0) return;
  985.     if (w==0) 
  986.     { R.root = root;
  987.       R.height = height;
  988.       R.maximum = maximum;
  989.       R.minimum = minimum;
  990.       R.count = count;
  991.       root = 0;
  992.       height = -1;
  993.       maximum = 0;
  994.       minimum = 0;
  995.       count = 0;
  996.       return;
  997.      }
  999.     if (w==maximum) 
  1000.     { L.root = root;
  1001.       L.height = height;
  1002.       L.maximum = maximum;
  1003.       L.minimum = minimum;
  1004.       L.count = count;
  1005.       root = 0;
  1006.       height = -1;
  1007.       maximum = 0;
  1008.       minimum = 0;
  1009.       count = 0;
  1010.       return;
  1011.      }
  1013.     ab_tree_node* l;
  1014.     ab_tree_node* r;    // pointers to the roots of the left and right subtree
  1017.     /* parameters for concat  */
  1019.     ab_tree_node* current_l=0 ;
  1020.     GenPtr           current_l_key=0;
  1022.     ab_tree_node* current_r=0;  
  1023.     GenPtr           current_r_key=0;
  1025.     int i;
  1028.     /* w is a pointer to the leave y  */
  1029.     ab_tree_node* v;
  1031.     /* store leaf to split at         */
  1032.     ab_tree_node* leaf=w;
  1035.      l = w;
  1036.      r = 0;
  1038.       do{
  1039.          v=w->father;
  1040.          int index_of_w = w->index; 
  1042.        /* now we have construct the  left and right subtrees and the pointers
  1043.           to the roots  --> we must construct two trees with these roots*/
  1045.         if ((L.root==0)&&(l!=0))  { L.root=l;
  1046.             L.height=l->height; 
  1047.             L.root->father=0;
  1048.             L.root->index=0;
  1049.           }
  1050.         else { if ((L.root!=0)&&(l!=0))
  1051.                  {  ab_tree L1(L.a,L.b);
  1052.             L1.root=l;
  1053.                     L1.height=l->height;
  1054.                     L1.root->father=0;
  1055.                     L1.root->index=0;
  1056.             concat(L1,L,current_l,current_l_key);
  1057.             L.root  = L1.root;
  1058.                     L.height= L1.height;
  1059.                     L.count = L1.count;
  1061.                     L1.root=0;
  1062.          }
  1063.              }
  1064.        if ((R.root==0)&&(r!=0))  {R.root=r;
  1065.            R.height=r->height;
  1066.           R.root->father=0;
  1067.           R.root->index=0;
  1068.                                   R.root->p=r->p;
  1069.          }
  1070.        else { if ((R.root!=0)&&(r!=0))
  1071.                 { ab_tree R1(R.a,R.b);
  1072.      R1.root=r;
  1073.   R1.height=r->height;
  1074.                   R1.root->father=0;
  1075.                   R1.root->index=0;
  1076.                   R1.root->p=r->p;
  1077.   concat(R,R1,current_r,current_r_key);
  1078.                   R1.root=0;
  1079.         }
  1080.             }
  1081.         if (v!=0)
  1082.         {
  1083.          if (index_of_w==1)     /* w is leftmost son of v */
  1084.          { l=0;
  1085.            r=v;
  1086.            current_r=v->same[1];
  1087.            current_r_key=v->k[1];
  1088.    r->same[1]->same[1]=0;        
  1089.    for(i=2;i<r->p;i++) 
  1090.             {  r->son[i-1]=r->son[i];
  1091.            r->son[i-1]->index=i-1;
  1092.          r->k[i-1]=r->k[i];
  1093.        r->same[i-1]=r->same[i];  
  1094.          }
  1095.            r->son[r->p-1]=r->son[r->p];    /* last son */
  1096.            r->son[r->p-1]->index=r->p-1;
  1097.            r->son[r->p]=0;
  1098.            r->p--; 
  1099.            r->k[r->p]=0;
  1100.    r->same[r->p]=0;      
  1101.            if (r->p==1) r=r->son[1];
  1102.          } 
  1103.          else {if ( index_of_w==v->p )
  1104.                  {  r=0;
  1105.                     l=v;
  1106.     l->son[l->p]=0;  /* last son */
  1107.     l->p--;
  1108.     current_l=l->same[index_of_w-1];
  1109.     current_l_key=current_l->k[1];
  1110.                     l->k[l->p]=0;
  1111.     l->same[l->p]->same[1]=0;   
  1112.     l->same[l->p]=0;            
  1113.                     if (l->p==1) l=l->son[1];
  1114. } 
  1115.                else  /* if w is not the leftmost or rightmost son of v*/
  1116.                {  
  1117.                  r=v;
  1118.                  l=new ab_tree_node(index_of_w-1,v->height,0,0,R.b);
  1119.    current_l=v->same[index_of_w-1];
  1120.    current_l_key=current_l->k[1];
  1121.  current_r=v->same[index_of_w];   
  1122.  current_r_key=current_r->k[1];
  1123.  // current_r=(v->k[index_of_w])-1;   ERROR: liefert neuen Schluessel ;
  1124.                  for(i=1;i<index_of_w-1;i++)
  1125.       {
  1126.    l->son[i]=v->son[i];
  1127.    l->son[i]->index=i;
  1128.                    l->son[i]->father=l;
  1129.    l->k[i]=v->k[i];
  1130.    l->same[i]=v->same[i];  
  1131.    l->same[i]->same[1]=l;  
  1132.   };
  1133.  l->son[index_of_w-1]=v->son[index_of_w-1];
  1134.  l->son[index_of_w-1]->index=index_of_w-1;
  1135.                  l->son[index_of_w-1]->father=l;
  1137.                  r->son[index_of_w] = 0;   // changed
  1139.       for (i=1;i<r->p-index_of_w;i++)
  1140.   {
  1141.    r->son[i]=r->son[i+index_of_w];
  1142.                    r->son[i+index_of_w]=0;
  1143.                  r->son[i]->index=i;
  1144.                    r->son[i]->father=r;
  1145.    r->k[i]=r->k[i+index_of_w];
  1146.    r->same[i]=r->same[i+index_of_w]; 
  1147.                    r->k[i+index_of_w]=0;
  1148.    r->same[i+index_of_w]=0;
  1149.   };
  1150.          r->son[r->p-index_of_w]=r->son[r->p];  /* last son */
  1151.                  r->son[r->p]=0;
  1152.  r->son[r->p-index_of_w]->index=i;
  1153.                  r->son[r->p-index_of_w]->father=r;
  1154.  r->p=r->p-index_of_w;
  1155.                  if (l->p==1) l=l->son[1];
  1156.                  if (r->p==1) r=r->son[1];
  1157.                 };
  1158.                };
  1159.               };
  1161.  /* initialisation for the next iteration  */
  1162.   w=v;
  1163.  }
  1164.  while (w!=0);
  1167.  /* unlink leaves    m.w.         */
  1168.  leaf->same[1]=0;
  1169.  leaf->son[2]->son[1]=0;
  1170.  leaf->son[2]=0;
  1172.  /* redefine maximum and minimum  */
  1173.  L.minimum=minimum;
  1174.  ab_tree_node* help=L.root;
  1175.  while (help->p) help=help->son[help->p];
  1176.  L.maximum=help;
  1177.  help=R.root;
  1178.  while (help->son[1]!=0) help=help->son[1];
  1179.  R.minimum=help;
  1180.  R.maximum=maximum;
  1182.  maximum=minimum=root=l=r=0;
  1183.  height=-1; 
  1184.  count = 0;
  1186.  delete l;
  1187.  delete r;
  1189. }
  1191. void ab_tree::pr_ab_tree(ab_tree_node* localroot,int blancs) const
  1193. { 
  1194.   if (localroot==0)
  1195.    { for(int j=1;j<=blancs;j++) cout<<" ";
  1196.      cout << "NILn";
  1197.      return;
  1198.     }
  1199.   
  1200.   if (localroot->p == 0) 
  1201.    { for(int j=1;j<=blancs;j++) cout<<" ";
  1202.      print_key(localroot->k[1]); 
  1203. /*
  1204.      ab_tree_node* s= localroot->same[1];
  1205.      cout << " same = "; 
  1206.      if (s) print_key(s->k[1]); 
  1207.      else cout << "NIL";
  1208. */
  1209.      cout << "n";
  1210.     }
  1212.    else
  1213.     { for(int i=1;i<localroot->p;i++)
  1214.       { pr_ab_tree(localroot->son[i],blancs+10);
  1215.         for(int j=1;j<=blancs;j++) cout<<" ";
  1216.         print_key(localroot->k[i]); 
  1217. /*
  1218.         cout << " same = "; 
  1219.         print_key(localroot->same[i]->k[1]); 
  1220. */
  1221.         cout << "n";
  1222.        };
  1223.       pr_ab_tree(localroot->son[localroot->p],blancs+10);
  1224.     }
  1225. } 
  1226.  
  1227. ab_tree_node* ab_tree::copy_ab_tree(ab_tree_node* localroot,
  1228.                                     abnode& last_leaf,int b0) const
  1229. { 
  1230.   ab_tree_node* r;
  1232.   if (localroot->p == 0)   //leaf
  1233.    { r=new ab_tree_node(localroot->p,localroot->height,localroot->index,0,1); 
  1235.      r->k[1]= localroot->k[1];
  1236.      r->inf = localroot->inf;
  1238.      copy_key(r->k[1]);
  1239.      copy_inf(localroot->inf);
  1241.      r->son[1]=last_leaf;
  1242.      if (last_leaf) last_leaf->son[2] = r;
  1243.      last_leaf = r;               
  1245.     }
  1246.   else
  1247.    { r=new ab_tree_node(localroot->p,localroot->height,localroot->index,0,b0); 
  1249.      for(int i=1;i<localroot->p;i++)
  1250.      { r->son[i]=copy_ab_tree(localroot->son[i],last_leaf,b0);
  1251.        r->son[i]->father=r;
  1252.        r->k[i]=localroot->k[i];
  1253.        last_leaf->same[1]=r;        
  1254.        r->same[i]=last_leaf;        
  1255.       }
  1257.      r->son[localroot->p]=copy_ab_tree(localroot->son[localroot->p],last_leaf,b0);
  1258.      r->son[localroot->p]->father=r;
  1259.    }
  1261.   return r;
  1262. }
  1263.         
  1264. void ab_tree::del_tree(ab_tree_node* localroot)
  1265. { // deletes subtree  rooted at localroot
  1267.   int k = localroot->p;
  1269.   for(int i=1;i<=k;i++) del_tree(localroot->son[i]);
  1271.   if (k==0) //leaf
  1272.   { clear_key(localroot->k[1]);
  1273.     clear_inf(localroot->inf);
  1274.    }
  1276.   delete localroot;
  1277. }
  1279. void ab_tree::change_inf(ab_tree_node* p, GenPtr x) 
  1280. { clear_inf(p->inf);
  1281.   copy_inf(x);
  1282.   p->inf = x;
  1283.  }