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