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