CTBbtree.cxx Source File

00001 
00006 /*----------------------------------------------------------------------------*/
00007 /* C Tool Box: Designed and implemented by:                                   */
00008 /*    Walter F.J. Mueller   Gesellschaft fuer Schwerionenforschung (GSI)      */
00009 /*                          Planckstrasse 1, D-64291 Darmstadt, Germany       */
00010 /*                  Email:  W.F.J.Mueller@gsi.de                              */
00011 /*                  WWW:    http://www-kp3.gsi.de/www/kp3/people/mueller.html */
00012 /*------------------------------------------+---------------------------------*/
00013 
00032 #include <assert.h>
00033 #include <ctype.h>
00034 
00035 #include "CTB.hxx"
00036 #include "CTB_Trace.hxx"
00037 #include "CTBnum.hxx"
00038 #include "CTBosFill.hxx"
00039 #include "CTBprintf.hxx"
00040 #include "CTBbtree.hxx"
00041 
00042 //------------------------------------------+-----------------------------------
00044 
00045 CTBbtree::~CTBbtree()
00046 {
00047   CTB_Trace("~CTBbtree()");
00048   Clear();                                  // delete all nodes
00049 }
00050 
00051 //------------------------------------------+-----------------------------------
00053 
00060 void CTBbtree::Clear()
00061 {
00062   CTB_Trace("CTBbtree::Clear()");
00063   CTBbtreeNode* p_next = mp_rnode;
00064 
00065   if (!p_next) return;                      // quit if empty tree
00066 
00067   //
00068   // for a fast deletion of all nodes we do a full tree traversal,
00069   // simply `unlink' the node at the postorder visit (when it has no
00070   // childs anymore), clear the head pointer in the node to make look
00071   // it like an idle node and finally delete the node.
00072   //
00073   // This avoids all the bookkeeping overhead of the normal remove procedure.
00074   //
00075 
00076   static const CTBuint32 status_childmask = CTBbtreeNode::status_childmask;
00077   static const CTBuint32 status_heavymask = CTBbtreeNode::status_heavymask;
00078 
00079   for (;;) {                                // do a full tree traversal
00080     CTBbtreeNode* p_cur = p_next;
00081 
00082     assert(p_cur->mp_head == this);         // !?! node linked to this tree
00083                                             // !?! not both child bits set
00084     assert((p_cur->mi_status & status_childmask) != status_childmask);
00085                                             // !?! not both balance bits set
00086     assert((p_cur->mi_status & status_heavymask) != status_heavymask);
00087                                             // !?! uplink --> one child bit set
00088     assert(!p_cur->mp_up || (p_cur->mi_status & status_childmask));
00089                                             // !?! check downlink if left child
00090     assert(!p_cur->IsLeftChild()  || p_cur->mp_up->mp_left==p_cur);
00091                                             // !?! check downlink if left child
00092     assert(!p_cur->IsRightChild() || p_cur->mp_up->mp_right==p_cur);
00093                                             // !?! check uplink of left child
00094     assert(!p_cur->mp_left  || p_cur->mp_left->mp_up==p_cur);
00095                                             // !?! check uplink of right child
00096     assert(!p_cur->mp_right || p_cur->mp_right->mp_up==p_cur);
00097 
00098     p_next = p_cur->mp_left;
00099     if (p_next) continue;                   // descent into left subtree first
00100 
00101     p_next = p_cur->mp_right;
00102     if (p_next) continue;                   // descent into right subtree next
00103 
00104     p_next = p_cur->mp_up;                  // finally move to parent
00105 
00106     if (p_cur->IsLeftChild())  p_next->mp_left  = 0;    // unlink from parent
00107     if (p_cur->IsRightChild()) p_next->mp_right = 0;
00108     p_cur->mp_head = 0;                     // signal idle node
00109     delete p_cur;                           // and finally delete node
00110 
00111     if (!p_next) break;                     // stop after deleting root node
00112   }
00113 
00114   mp_rnode = 0;                             // finally clear all pointers
00115   mp_first = 0;
00116   mp_last  = 0;
00117   mi_size  = 0;
00118 
00119   return;
00120 }
00121 
00122 //------------------------------------------+-----------------------------------
00124 
00132 void CTBbtree::TreeHeight(int& i_minh, int& i_maxh, float& f_avrp) const
00133 {
00134   double d_nnode;
00135   double d_ncomp;
00136   
00137   if (!mp_rnode) {
00138     i_minh = 0;
00139     i_maxh = 0;
00140     f_avrp = 0.;
00141     return;
00142   }
00143 
00144   mp_rnode->SubTreeHeight(i_minh,i_maxh,d_nnode,d_ncomp);
00145   f_avrp = d_ncomp/d_nnode;  
00146   return;
00147 }
00148   
00149 //------------------------------------------+-----------------------------------
00151 
00157 bool CTBbtree::TreeCheck(ostream* p_os) const
00158 {
00159   int i_maxh = 0;
00160 
00161   return (mp_rnode) ? mp_rnode->SubTreeCheck(p_os,i_maxh) : true;
00162 }
00163 
00164 //------------------------------------------+-----------------------------------
00165 void print_address(                         // print address in hex
00166     ostream& os,
00167     void* p)
00168 {
00169   if (p) os << CTBprintf((CTBuint32) p,"x",8);
00170   else   os << "       -";
00171   return;
00172 }
00173 
00174 //------------------------------------------+-----------------------------------
00176 
00200 void CTBbtree::Dump(int i_indent, ostream& os, const char* p_text) const
00201 {
00202   CTBosFill bl(i_indent);
00203   int   i_minh = 0;
00204   int   i_maxh = 0;
00205   float f_avrp = 0.;
00206 
00207   os << bl << "--CTBbtree ";
00208   if (p_text) os << p_text;
00209   os << " @ " << this << endl;
00210   os << bl << "    mp_rnode:      " << mp_rnode << "\n";
00211   os << bl << "    mp_first:      " << mp_first << "\n";
00212   os << bl << "    mp_last:       " << mp_last  << "\n";
00213   os << bl << "    mi_size:       " << mi_size  << "\n";
00214 
00215   if (!mp_rnode) return;
00216 
00217   TreeHeight(i_minh,i_maxh,f_avrp);
00218   os << bl << "    tree height    max: " << i_maxh
00219      << "  min: " << i_minh 
00220      << "  average path: " << CTBprintf(f_avrp,"f",6,2) << "\n";
00221 
00222   os << bl <<"  rank lvl  bc      this        up     left    right  location\n";
00223 
00224   for (CTBbtreeNode* p_cur = mp_first; p_cur; p_cur = p_cur->Next()) {
00225     CTBint i_rank = p_cur->LWeight();
00226     int    i_lvl  = 0;
00227     char   c_bmode;
00228     char   c_cmode;
00229 
00230     // determine rank by walking up to the root node and
00231     // adding the LWeight's of parents if node is a right child
00232 
00233     for (CTBbtreeNode* p = p_cur; p; p = p->mp_up) { // walk up to root node
00234       i_lvl += 1;
00235       if (p->IsRightChild()) i_rank += p->mp_up->LWeight();
00236     }
00237 
00238     os << bl << CTBprintf(i_rank-1,"d",6)
00239        << " " << CTBprintf(i_lvl,"d",3);
00240 
00241     c_bmode = '0';
00242     if (p_cur->IsLeftHeavy())  c_bmode = '-';
00243     if (p_cur->IsRightHeavy()) c_bmode = '+';
00244     c_cmode = '^';
00245     if (p_cur->IsLeftChild())  c_cmode = 'l';
00246     if (p_cur->IsRightChild()) c_cmode = 'r';
00247     os << "  " << c_bmode << c_cmode;;
00248 
00249     os << "  "; print_address(os,p_cur);
00250     os << "  "; print_address(os,p_cur->mp_up);
00251     os << " ";  print_address(os,p_cur->mp_left);
00252     os << " ";  print_address(os,p_cur->mp_right);
00253 
00254     i_lvl = 0;
00255     os << "  ";
00256     for (CTBbtreeNode* p = p_cur; p; p = p->mp_up) { // walk up to root node
00257       char c_cmode = '^';
00258 
00259       if (p->IsLeftChild())  c_cmode = 'l';
00260       if (p->IsRightChild()) c_cmode = 'r';
00261       if (!p->mp_left && !p->mp_right) c_cmode = toupper(c_cmode);
00262 
00263       os << c_cmode;
00264       i_lvl += 1;
00265       if (i_lvl >= 24-i_indent) {           // limit to about 80 columns
00266         os << ">";
00267         break;
00268       }
00269     }
00270     os << endl;
00271   }
00272 
00273   TreeCheck(&cerr);                         // do some sanity checks
00274 
00275   return;
00276 }
00277 
00283 //------------------------------------------+-----------------------------------
00285 
00290 CTBbtreeNode* CTBbtree::operator[](CTBint i_ind) const
00291 {
00292   CTB_Trace("CTBbtree::operator[](CTBint)");
00293   CTBint i_rel = i_ind + 1;
00294 
00295   for (CTBbtreeNode* p = mp_rnode; p; ) {
00296     CTBint i_lw = p->LWeight();
00297     
00298     if (i_rel == i_lw) return p;            // found
00299     if (i_rel < i_lw) {                     // move left
00300       p = p->mp_left;
00301     } else {                                // move right
00302       i_rel -= i_lw;
00303       p = p->mp_right;
00304     }
00305   }
00306   
00307   return 0;
00308 }
00309 
00310 //------------------------------------------+-----------------------------------
00312 
00321 CTBbtree& CTBbtree::operator=(const CTBbtree& rhs)
00322 {
00323   // After deleting the old stuff do a full *structural* copy of the source
00324   // map. This produces a faithful image of the source tree.
00325 
00326   CTB_Trace("CTBbtree::operator=(const CTBbtree&)");
00327   CTBbtreeNode* p_rpos   = rhs.mp_rnode;    // rhs current position
00328   CTBbtreeNode* p_rpar   = 0;               // rhs parent
00329   CTBbtreeNode* p_lpos   = 0;               // lhs current position
00330   CTBbtreeNode* p_lpar   = 0;               // lhs parent
00331   int   i_origin         = 0;               // indicates where we came from
00332                                             // 0:up  -1:left  +1:right
00333 
00334   if (&rhs == this) return *this;           // catch copy onto itself
00335 
00336   Clear();                                  // cleanup lhs
00337 
00338   if (!p_rpos) return *this;                // empty rhs
00339 
00340   for (;;) {
00341     if (i_origin == 0) {                    // came from parent
00342                                             // create a new node
00343       p_lpos = p_rpos->Clone();             // clone this node, then set linkage
00344 
00345       p_lpos->mp_head   = this;             // then set linkage pointers
00346       p_lpos->mi_status = p_rpos->mi_status;
00347       if(p_rpos->IsRNode()) {
00348         mp_rnode = p_lpos;
00349       }
00350       else if (p_rpos->IsLeftChild()) {
00351         p_lpar->mp_left = p_lpos;
00352         p_lpos->mp_up   = p_lpar;
00353       } else {
00354         p_lpar->mp_right = p_lpos;
00355         p_lpos->mp_up    = p_lpar;
00356       }
00357 
00358       if (p_rpos->mp_left) {                // left subtree ?
00359         i_origin = 0;
00360         p_rpar   = p_rpos;                  // go down
00361         p_rpos   = p_rpos->mp_left;
00362         p_lpar   = p_lpos;
00363         p_lpos   = 0;
00364         continue;
00365       } else {
00366         i_origin = -1;                      // otherwise pretend to come from l
00367       }
00368     }
00369 
00370     if (i_origin == -1 && p_rpos->mp_right) { // from left and right subtree ?
00371         i_origin = 0;
00372         p_rpar   = p_rpos;                  // go down
00373         p_rpos   = p_rpos->mp_right;
00374         p_lpar   = p_lpos;
00375         p_lpos   = 0;
00376         continue;
00377     }
00378 
00379     if (p_rpos->IsRNode()) break;
00380 
00381     i_origin = (p_rpos->IsLeftChild()) ? -1 : 1;
00382     p_rpos   = p_rpar;
00383     p_rpar   = p_rpos->mp_up;
00384     p_lpos   = p_lpar;
00385     p_lpar   = p_lpos->mp_up;
00386   }
00387 
00388   mp_first = mp_rnode;                      // finally set first and last by
00389   mp_last  = mp_rnode;                      // following down the tree
00390   while (mp_first->mp_left)  mp_first = mp_first->mp_left;
00391   while (mp_last->mp_right)  mp_last  = mp_last->mp_right;
00392 
00393   return *this;
00394 }
00395 
00396 //------------------------------------------+-----------------------------------
00398 
00399 CTBbtreeNode::~CTBbtreeNode()
00400 {
00401   CTB_Trace("~CTBbtreeNode()");
00402 
00403   if (mp_head) Remove();                    // if busy remove from tree
00404 }
00405 
00406 //------------------------------------------+-----------------------------------
00408 
00418 CTBbtreeNode* CTBbtreeNode::Clone() const
00419 {
00420   CTB_Trace("CTBbtreeNode::Clone()");
00421 
00422   return new CTBbtreeNode();                // links just initialized in clone !
00423 }
00424 
00425 //------------------------------------------+-----------------------------------
00427 
00428 CTBbtreeNode* CTBbtreeNode::Next() const
00429 {
00430   CTB_Trace("CTBbtreeNode::Next()");
00431   CTBbtreeNode* p_next;
00432 
00433   // Basic rules for tree traversal:
00434   //  1. if you come from parent, go left
00435   //  2. if you come from left, visit node, go right
00436   //  3. if you come from right, go up
00437   //
00438   // so, if there is a right subtree, descent to its leftmost leave
00439   //
00440 
00441   if (mp_right) {
00442     p_next = mp_right;                      // goto right child
00443     while (p_next->mp_left) p_next = p_next->mp_left; // descent left subtree
00444     return p_next;
00445   }
00446 
00447   //
00448   // otherwise, climb as long as we come from the right, visit node if we
00449   // come from the left. This condition leads nicely also to a stop returning
00450   // a null pointer if we get back to the root node !
00451   //
00452 
00453   p_next = (CTBbtreeNode*) this;
00454   while (p_next->IsRightChild()) p_next = p_next->mp_up;
00455   return p_next->mp_up;
00456 }
00457 
00458 //------------------------------------------+-----------------------------------
00460 
00461 CTBbtreeNode* CTBbtreeNode::Prev() const
00462 {
00463   CTB_Trace("CTBbtreeNode::Prev()");
00464   CTBbtreeNode* p_prev;
00465 
00466   // this is just the mirrot image of First()
00467   //
00468   // so, if there is a left subtree, descent to its rightmost leave
00469   //
00470 
00471   if (mp_left) {
00472     p_prev = mp_left;                       // goto left child
00473     while (p_prev->mp_right) p_prev = p_prev->mp_right; // descent right subtree
00474     return p_prev;
00475   }
00476 
00477   //
00478   // otherwise, climb as long as we come from the left, visit node if we
00479   // come from the right. This condition leads nicely also to a stop returning
00480   // a null pointer if we get back to the root node !
00481   //
00482 
00483   p_prev = (CTBbtreeNode*) this;
00484   while(p_prev->IsLeftChild()) p_prev = p_prev->mp_up;
00485   return p_prev->mp_up;
00486 }
00487 
00488 //------------------------------------------+-----------------------------------
00490 
00499 CTBbtreeNode* CTBbtreeNode::Skip(CTBint i_offset) const
00500 {
00501   CTB_Trace("CTBbtreeNode::Skip(CTBint)");
00502   CTBbtreeNode* p = (CTBbtreeNode*) this;
00503   CTBint        i_rel = LWeight() + i_offset; // target rank in subtree (1base)
00504   
00505   if (i_offset ==  0) return p;             // trivial case
00506   if (i_offset ==  1) return Next();        // use tree walk for +/- 1
00507   if (i_offset == -1) return Prev();
00508 
00509   // Determine the number of left childs (i_offset < 0) or number of right
00510   // childs (i_offset > 1). If this is too small for the skip climp the tree.
00511   // Note: There is an asymmetrie in this algorithm because only LWeight is
00512   //       stored but not RWeight. For a left child the RWeight can be easily
00513   //       calculated using the parent LWeight, but for right child the only
00514   //       way is to climb the tree until a left child node is found or the
00515   //       root node is reached (here RWeight is determined using Size). This
00516   //       makes skips with positive offsets less efficient than skips with
00517   //       negative offsets.
00518   //
00519 
00520   for (; p; p = p->mp_up) {
00521     if (i_offset < 0) {                     // skip left
00522       if (i_rel >= 1) break;
00523     } else {                                // skip right
00524       if (p->IsLeftChild() && i_rel <= p->mp_up->LWeight() - 1) break;
00525       if (p->IsRNode() && i_rel <= mp_head->Size()) break;
00526     }
00527     if (p->IsRightChild()) {                // accumulate rank
00528       i_rel  += p->mp_up->LWeight();
00529     }
00530   }
00531   
00532   // Now determine the target node like in operator[]
00533 
00534   while (p) {
00535     CTBint i_lw = p->LWeight();
00536     
00537     if (i_rel == i_lw) return p;            // found
00538     if (i_rel < i_lw) {                     // move left
00539       p = p->mp_left;
00540     } else {                                // move right
00541       i_rel -= i_lw;
00542       p = p->mp_right;
00543     }
00544   }
00545 
00546   return 0;                                 // skip out of range
00547 }
00548 
00549 //------------------------------------------+-----------------------------------
00551 
00552 CTBint CTBbtreeNode::Rank() const
00553 {
00554   CTB_Trace("CTBbtreeNode::Rank()");
00555   CTBint i_rank = LWeight();
00556 
00557   for (const CTBbtreeNode* p = this; p; p = p->mp_up) { // walk up to root node
00558     if (p->IsRightChild()) i_rank += p->mp_up->LWeight();
00559   }
00560 
00561   return i_rank-1;
00562 }
00563 
00564 //------------------------------------------+-----------------------------------
00566 
00573 void CTBbtreeNode::Insert(CTBbtree& head,CTBbtreeNode* p_parent,int i_ctype)
00574 {
00575   CTB_Trace("CTBbtreeNode::Insert(CTBbtree&,CTBbtreeNode*,int)");
00576 
00577   assert(!mp_head);                         // !?! node must be idle
00578 
00579   if (!p_parent) {                          // no parent --> will be root node
00580     assert(i_ctype==0);                     // !?! child mode must be 0
00581     assert(!head.mp_rnode);                 // !?! head must be empty
00582 
00583     head.mi_size += 1;
00584     head.mp_rnode = this;
00585     head.mp_first = this;
00586     head.mp_last  = this;
00587 
00588     mp_head       = &head;
00589     mp_up         = 0;
00590     mp_left       = 0;
00591     mp_right      = 0;
00592     mi_status     = status_deltaw;          // set LWeight to 1 (counts itself)
00593 
00594   } else {                                  // link to a parent
00595     assert(i_ctype!=0);                     // !?! child mode left or right
00596     assert(p_parent->mp_head==&head);       // !?! parent must be with same head
00597     assert(!((i_ctype<0) ?                  // !?! child link must be empty
00598              p_parent->mp_left : p_parent->mp_right));
00599 
00600     head.mi_size += 1;
00601     mp_head       = &head;
00602     mp_up         = p_parent;
00603     mp_left       = 0;
00604     mp_right      = 0;
00605     if (i_ctype < 0) {                      // insert as left child
00606       p_parent->mp_left  = this;
00607       mi_status          = status_lchild + status_deltaw; // left child; LW=1
00608       if (head.mp_first == p_parent) head.mp_first = this;
00609     } else {                                // insert as right child
00610       p_parent->mp_right = this;
00611       mi_status          = status_rchild + status_deltaw; // right child;  LW=1
00612       if (head.mp_last == p_parent) head.mp_last = this;
00613     }
00614   }
00615 
00616   InsertFixup();                            // maintain rank and balance
00617 
00618   return;
00619 }
00620 
00621 //------------------------------------------+-----------------------------------
00623 
00634 void CTBbtreeNode::Remove()
00635 {
00636   CTB_Trace("CTBbtreeNode::Remove()");
00637 
00638   assert(mp_head);                          // !?! node must be busy
00639 
00640                                             // !?! not both child bits set
00641   assert((mi_status & status_childmask) != status_childmask);
00642                                             // !?! not both balance bits set
00643   assert((mi_status & status_heavymask) != status_heavymask);
00644                                             // !?! uplink --> one child bit set
00645   assert(!mp_up || (mi_status & status_childmask));
00646                                             // !?! check downlink if left child
00647   assert(!IsLeftChild()  || mp_up->mp_left==this);
00648                                             // !?! check downlink if left child
00649   assert(!IsRightChild() || mp_up->mp_right==this);
00650                                             // !?! check uplink of left child
00651   assert(!mp_left  || mp_left->mp_up==this);
00652                                             // !?! check uplink of right child
00653   assert(!mp_right || mp_right->mp_up==this);
00654 
00655   if (mp_left && mp_right) {                // handle inner node
00656     CTBbtreeNode* p_next = Next();          // get next node
00657 
00658     p_next->Remove();                       // remove this node from tree
00659 
00660     p_next->mp_head   = mp_head;            // and put it in place of this
00661     p_next->mp_up     = mp_up;
00662     p_next->mp_left   = mp_left;
00663     p_next->mp_right  = mp_right;
00664     p_next->mi_status = mi_status;
00665     if (IsRNode())          mp_head->mp_rnode = p_next;
00666     else if (IsLeftChild()) mp_up->mp_left    = p_next;
00667     else                    mp_up->mp_right   = p_next;
00668     if (mp_left)  mp_left->mp_up    = p_next;
00669     if (mp_right) mp_right->mp_up   = p_next;
00670 
00671     if (mp_head->mp_first == this) mp_head->mp_first = p_next; // fix first/last
00672     if (mp_head->mp_last  == this) mp_head->mp_last  = p_next;
00673 
00674   } else {                                  // handle nodes with 0 or 1 child
00675     CTBbtreeNode* p_sub = (mp_left) ? mp_left : mp_right;
00676 
00677     RemoveFixup();                          // maintain rank and balance
00678 
00679     mp_head->mi_size -= 1;
00680     if (mp_head->mp_first == this) mp_head->mp_first = Next();
00681     if (mp_head->mp_last  == this) mp_head->mp_last  = Prev();
00682 
00683     if (p_sub) {
00684       p_sub->mp_up = mp_up;                 // uplink of child
00685       p_sub->mi_status &= ~status_childmask; // transfer child mode to child
00686       p_sub->mi_status |= mi_status & status_childmask;
00687     }
00688 
00689     if (IsRNode())          mp_head->mp_rnode = p_sub; // parent downlink
00690     else if (IsLeftChild()) mp_up->mp_left    = p_sub;
00691     else                    mp_up->mp_right   = p_sub;
00692   }
00693 
00694   mp_head   = 0;                            // finally, clear all links
00695   mp_up     = 0;
00696   mp_left   = 0;
00697   mp_right  = 0;
00698   mi_status = 0;
00699 
00700   return;
00701 }
00702 
00703 //------------------------------------------+-----------------------------------
00705 
00719 void CTBbtreeNode::RotateLeft()
00720 {
00721   CTB_Trace("CTBbtreeNode::RotateLeft()");
00722 
00723   assert(mp_head);                          // !?! node linked ?
00724   assert(mp_right);                         // !?! right subtree exists ?
00725 
00726   CTBbtreeNode*  p_b    = this;
00727   CTBbtreeNode*  p_c    = mp_right;
00728   CTBbtreeNode*  p_b_up = mp_up;
00729   CTBbtreeNode*  p_ga   = p_c->mp_left;
00730 
00731   p_c->mp_up = p_b_up;                      // uplink to parent
00732   p_c->mi_status &= ~status_childmask;      // transfer child mode
00733   p_c->mi_status |= p_b->mi_status & status_childmask;
00734 
00735   if (p_b->IsRNode())          mp_head->mp_rnode = p_c; // parent downlink
00736   else if (p_b->IsLeftChild()) p_b_up->mp_left   = p_c;
00737   else                         p_b_up->mp_right  = p_c;
00738 
00739   p_b->mp_up = p_c;                         // B uplink
00740   p_b->SetLeftChild();
00741 
00742   p_c->mp_left = p_b;                       // C left child
00743 
00744   if (p_ga) {                               // ga uplink
00745     p_ga->mp_up = p_b;
00746     p_ga->SetRightChild();
00747   }
00748 
00749   p_b->mp_right = p_ga;                     // B right child
00750 
00751   p_c->LWeight(p_c->LWeight() + p_b->LWeight()); // weight: C' = C + B
00752 
00753   return;
00754 }
00755 
00756 // Notes:
00757 //  1. The rotators maintain all links including child mode bits, the
00758 //     LWeight, but *not* the balance factors. This is context dependent
00759 //     and must be done by the caller !!!
00760 
00761 //------------------------------------------+-----------------------------------
00763 
00778 void CTBbtreeNode::RotateRight()
00779 {
00780   CTB_Trace("CTBbtreeNode::RotateRight()");
00781 
00782   assert(mp_head);                          // !?! node linked ?
00783   assert(mp_left);                          // !?! left subtree exists ?
00784 
00785   CTBbtreeNode*  p_b    = this;
00786   CTBbtreeNode*  p_a    = mp_left;
00787   CTBbtreeNode*  p_b_up = mp_up;
00788   CTBbtreeNode*  p_be   = p_a->mp_right;
00789 
00790   p_a->mp_up = p_b_up;                      // uplink to parent
00791   p_a->mi_status &= ~status_childmask;      // transfer child mode
00792   p_a->mi_status |= p_b->mi_status & status_childmask;
00793 
00794   if (p_b->IsRNode())          mp_head->mp_rnode = p_a; // parent downlink
00795   else if (p_b->IsLeftChild()) p_b_up->mp_left   = p_a;
00796   else                         p_b_up->mp_right  = p_a;
00797 
00798   p_b->mp_up = p_a;                         // B uplink
00799   p_b->SetRightChild();
00800 
00801   p_a->mp_right = p_b;                      // A right child
00802 
00803   if (p_be) {                               // be uplink
00804     p_be->mp_up = p_b;
00805     p_be->SetLeftChild();
00806   }
00807 
00808   p_b->mp_left = p_be;                      // B left child
00809 
00810   p_b->LWeight(p_b->LWeight() - p_a->LWeight()); // weight: B' = B - A
00811 
00812   return;
00813 }
00814 
00815 //------------------------------------------+-----------------------------------
00817 
00834 void CTBbtreeNode::RotateLeftRight()
00835 {
00836   CTB_Trace("CTBbtreeNode::RotateLeftRight()");
00837 
00838   assert(mp_left);                          // !?! left subtree exists
00839   assert(mp_left->mp_right);                // !?! right of left subtree exists
00840 
00841   mp_left->RotateLeft();
00842   RotateRight();
00843 
00844   return;
00845 }
00846 
00847 //------------------------------------------+-----------------------------------
00849 
00866 void CTBbtreeNode::RotateRightLeft()
00867 {
00868   CTB_Trace("CTBbtreeNode::RotateRightLeft()");
00869 
00870   assert(mp_right);                         // !?! right subtree exists
00871   assert(mp_right->mp_left);                // !?! left of right subtree exists
00872 
00873   mp_right->RotateRight();
00874   RotateLeft();
00875 
00876   return;
00877 }
00878 
00879 //------------------------------------------+-----------------------------------
00881 
00882 void CTBbtreeNode::InsertFixup()
00883 {
00884   
00885   // 1. Fixup the LWeight's of all ancestors
00886   //    --> increment LWeight of all parents of left childs
00887   // 2. Rebalance according to the Adel'son-Vel'skil-Landis algorithm
00888   //    described as `Algorithm A in Chapter 6.2.3 of Knuth Volume 3
00889   //    For details [pb1p116].
00890 
00891   CTB_Trace("CTBbtreeNode::InsertFixup()");
00892 
00893   for (CTBbtreeNode* p = this; p; p = p->mp_up) { // walk up to root node
00894     if (p->IsLeftChild()) p->mp_up->IncLWeight();
00895   }  
00896 
00897 #ifndef UNBALANCED
00898 
00899   for (CTBbtreeNode* p_b = this; ; ) {
00900     CTBbtreeNode* p_a = p_b->mp_up;
00901     
00902     if (!p_a) break;                        // in rnode
00903     
00904     if (p_b->IsRightChild()) {              // current node is right child
00905       if (p_a->IsLeftHeavy()) {             // parent is left heavy
00906         p_a->SetBalanced();                 // -> set him balanced and quit
00907         break;
00908       }
00909       if (p_a->IsBalanced()) {              // parent is balanced
00910         p_a->SetRightHeavy();               // -> set him right heavy and quit
00911 
00912       } else {                              // parent is right heavy
00913         assert(!(p_b->IsBalanced()));       // !?! must be left or right heavy
00914 
00915         if (p_b->IsRightHeavy()) {          // parent right; current right heavy
00916           p_a->RotateLeft();                // -> do left rotation; case 1
00917           p_b->SetBalanced();               //    set child and parent balanced
00918           p_a->SetBalanced();
00919           break;
00920 
00921         } else {                            // parent right; current left heavy
00922           CTBbtreeNode* p_x = p_b->mp_left; // get left child
00923           
00924           assert(p_x);                      // !?! left child must exist
00925           p_a->RotateRightLeft();           // -> do right left rotation; case 2
00926           p_b->SetBalanced();               //    
00927           p_a->SetBalanced();
00928           if (p_x->IsRightHeavy()) p_a->SetLeftHeavy();
00929           if (p_x->IsLeftHeavy())  p_b->SetRightHeavy();          
00930           p_x->SetBalanced();
00931           break;
00932         }
00933       }
00934 
00935     } else {                                // current node is left child
00936       if (p_a->IsRightHeavy()) {            // parent is right heavy
00937         p_a->SetBalanced();                 // -> set him balanced and quit
00938         break;
00939       }
00940       if (p_a->IsBalanced()) {              // parent is balanced
00941         p_a->SetLeftHeavy();                // -> set him left heavy and quit
00942 
00943       } else {                              // parent is right heavy
00944         assert(!(p_b->IsBalanced()));       // !?! must be left or right heavy
00945 
00946         if (p_b->IsLeftHeavy()) {           // parent left; current left heavy
00947           p_a->RotateRight();               // -> do right rotation; case 1
00948           p_b->SetBalanced();               //    set child and parent balanced
00949           p_a->SetBalanced();
00950           break;
00951 
00952         } else {                            // parent left; current right heavy
00953           CTBbtreeNode* p_x = p_b->mp_right; // get right child
00954           
00955           assert(p_x);                      // !?! right child must exist
00956           p_a->RotateLeftRight();           // -> do left right rotation; case 2
00957           p_b->SetBalanced();               //    
00958           p_a->SetBalanced();
00959           if (p_x->IsLeftHeavy())  p_a->SetRightHeavy();
00960           if (p_x->IsRightHeavy()) p_b->SetLeftHeavy();   
00961           p_x->SetBalanced();
00962           break;
00963         }
00964       }
00965     }
00966    
00967     p_b = p_a;
00968   }
00969 
00970 #endif
00971 
00972   return;
00973 }
00974 
00975 //------------------------------------------+-----------------------------------
00977 
00978 void CTBbtreeNode::RemoveFixup()
00979 {
00980   // 1. Fixup the LWeight's of all ancestors
00981   //    --> decrement LWeight of all parents of left childs
00982   // 2. Rebalance according to the Foster algorithm
00983   //    described in chapter 6.2.3 of Knuth Volume 3
00984   //    For details [pb1p117].
00985 
00986   CTB_Trace("CTBbtreeNode::RemoveFixup()");
00987 
00988   for (CTBbtreeNode* p = this; p; p = p->mp_up) { // walk up to root node
00989     if (p->IsLeftChild()) p->mp_up->DecLWeight();
00990   }
00991 
00992 #ifndef UNBALANCED
00993   
00994   for (CTBbtreeNode* p = this; ; ) {
00995     CTBbtreeNode* p_a    = p->mp_up;
00996     CTBbtreeNode* p_next = p_a;
00997 
00998     if (!p_a) break;                        // in rnode
00999     
01000     if (p->IsLeftChild()) {                 // current node is left child
01001       if (p_a->IsLeftHeavy()) {             // parent is left heavy
01002         p_a->SetBalanced();                 // tree height decreased
01003 
01004       } else if (p_a->IsBalanced()) {       // parent is balanced
01005         p_a->SetRightHeavy();               // tree height unchanged
01006         break;
01007         
01008       } else {                              // parent is right heavy (rebalance)
01009         CTBbtreeNode* p_b = p_a->mp_right;  // right child of parent
01010         
01011         assert(p_b);                        // !?! 
01012         if (p_b->IsBalanced()) {            // case 3 (Knuth)
01013           p_a->RotateLeft();
01014           p_b->SetLeftHeavy();
01015           break;                            // tree height unchanged
01016           
01017         } else if (p_b->IsRightHeavy()) {   // case 1 (Knuth)
01018           p_a->RotateLeft();
01019           p_a->SetBalanced();
01020           p_b->SetBalanced();
01021           p_next = p_b;                     // tree height decreased
01022           
01023         } else {                            // case 2 (Knuth)
01024           CTBbtreeNode* p_x = p_b->mp_left;
01025           
01026           assert(p_x);                      // !?!
01027           p_a->RotateRightLeft();
01028           p_a->SetBalanced();
01029           p_b->SetBalanced();
01030           if (p_x->IsRightHeavy()) p_a->SetLeftHeavy();
01031           if (p_x->IsLeftHeavy())  p_b->SetRightHeavy();
01032           p_x->SetBalanced();
01033           p_next = p_x;                     // tree height decreased
01034         }
01035       }
01036 
01037     } else {                                // current node is right child
01038       if (p_a->IsRightHeavy()) {            // parent is right heavy
01039         p_a->SetBalanced();                 // tree height decreased
01040 
01041       } else if (p_a->IsBalanced()) {       // parent is balanced
01042         p_a->SetLeftHeavy();                // tree height unchanged
01043         break;
01044         
01045       } else {                              // parent is right heavy (rebalance)
01046         CTBbtreeNode* p_b = p_a->mp_left;   // left child of parent
01047         
01048         assert(p_b);                        // !?! 
01049         if (p_b->IsBalanced()) {            // case 3 (Knuth)
01050           p_a->RotateRight();
01051           p_b->SetRightHeavy();
01052           break;                            // tree height unchanged
01053           
01054         } else if (p_b->IsLeftHeavy()) {    // case 1 (Knuth)
01055           p_a->RotateRight();
01056           p_a->SetBalanced();
01057           p_b->SetBalanced();
01058           p_next = p_b;                     // tree height decreased
01059           
01060         } else {                            // case 2 (Knuth)
01061           CTBbtreeNode* p_x = p_b->mp_right;
01062           
01063           assert(p_x);                      // !?!
01064           p_a->RotateLeftRight();
01065           p_a->SetBalanced();
01066           p_b->SetBalanced();
01067           if (p_x->IsLeftHeavy())  p_a->SetRightHeavy();
01068           if (p_x->IsRightHeavy()) p_b->SetLeftHeavy();
01069           p_x->SetBalanced();
01070           p_next = p_x;                     // tree height decreased
01071         }
01072       }
01073 
01074     }
01075 
01076     p = p_next;
01077   }
01078 
01079 #endif
01080 
01081   return;
01082 }
01083 
01084 //------------------------------------------+-----------------------------------
01086 
01094 void CTBbtreeNode::SubTreeHeight(int& i_minh, int& i_maxh,
01095                                  double& d_nnode, double& d_ncomp) const
01096 {
01097   int     i_minh_l;
01098   int     i_maxh_l = 0;
01099   double  d_nnode_l;
01100   double  d_ncomp_l;
01101   int     i_minh_r;
01102   int     i_maxh_r = 0;
01103   double  d_nnode_r;
01104   double  d_ncomp_r;
01105   
01106   if (!mp_left && !mp_right) {              // no childs --> leave node
01107     i_minh  = 1;
01108     i_maxh  = 1;
01109     d_nnode = 1.;
01110     d_ncomp = 1.;
01111     return;
01112   }
01113   
01114   if (mp_left)  mp_left ->SubTreeHeight(i_minh_l,i_maxh_l,d_nnode_l,d_ncomp_l);
01115   if (mp_right) mp_right->SubTreeHeight(i_minh_r,i_maxh_r,d_nnode_r,d_ncomp_r);
01116   
01117   if (mp_left && !mp_right) {               // only left childs
01118     i_minh  = 1  + i_minh_l;
01119     i_maxh  = 1  + i_maxh_l;
01120     d_nnode = 1. + d_nnode_l;
01121     d_ncomp = d_nnode + d_ncomp_l;
01122   } else if (!mp_left && mp_right) {        // only right childs
01123     i_minh  = 1  + i_minh_r;
01124     i_maxh  = 1  + i_maxh_r;
01125     d_nnode = 1. + d_nnode_r;
01126     d_ncomp = d_nnode + d_ncomp_r;
01127   } else {                                  // left and right childs
01128     i_minh  = 1  + CTBmin(i_minh_l,i_minh_r);
01129     i_maxh  = 1  + CTBmax(i_maxh_l,i_maxh_r);
01130     d_nnode = 1. + d_nnode_l + d_nnode_r;
01131     d_ncomp = d_nnode + d_ncomp_l + d_ncomp_r;
01132   }
01133 
01134   return;
01135 }
01136 
01137 //------------------------------------------+-----------------------------------
01139 
01140 bool CTBbtreeNode::SubTreeCheck(
01141     ostream* p_os,
01142     int& i_maxh) const
01143 {
01144   bool    b_ok_l   = true;
01145   bool    b_ok_r   = true;
01146   bool    b_ok;
01147   int     i_maxh_l = 0;
01148   int     i_maxh_r = 0;
01149   int     i_dheight;
01150   
01151   if (!mp_left && !mp_right) {              // no childs --> leave node
01152     i_maxh  = 1;
01153     return true;
01154   }
01155   
01156   if (mp_left)  b_ok_l = mp_left ->SubTreeCheck(p_os,i_maxh_l);
01157   if (mp_right) b_ok_r = mp_right->SubTreeCheck(p_os,i_maxh_r);
01158 
01159   b_ok = b_ok_l && b_ok_r;
01160   i_maxh = 1  + CTBmax(i_maxh_l,i_maxh_r);
01161 
01162   i_dheight = i_maxh_r - i_maxh_l;          // finally, do some sanity checks
01163 
01164   if (IsBalanced() && i_dheight != 0) {
01165     b_ok = false;
01166     if (p_os) (*p_os) << "%CTBbtreeNode-I Node @" << (void*) this 
01167                       << " status = balanced   but h_r-h_r = " 
01168                       << i_dheight << endl;
01169   }
01170   if (IsLeftHeavy() && i_dheight != -1) {
01171     b_ok = false;
01172     if (p_os) (*p_os) << "%CTBbtreeNode-I Node @" << (void*) this 
01173                       << " status = leftheavy  but h_r-h_r = " 
01174                       << i_dheight << endl;
01175   }
01176   if (IsRightHeavy() && i_dheight !=  1) {
01177     b_ok = false;
01178     if (p_os) (*p_os) << "%CTBbtreeNode-I Node @" << (void*) this 
01179                       << " status = rightheavy but h_r-h_r = " 
01180                       << i_dheight << endl;
01181   }  
01182   
01183   return b_ok;
01184 }