home *** CD-ROM | disk | FTP | other *** search
/ The Devil's Doorknob BBS Capture (1996-2003) / devilsdoorknobbbscapture1996-2003.iso / Dloads / OTHERUTI / TCPP30-1.ZIP / CLASSSRC.ZIP / BTREEINN.CPP < prev    next >
C/C++ Source or Header  |  1992-02-18  |  23KB  |  711 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  BTREEINN.CPP                                                          */
  4. /*                                                                        */
  5. /*  Copyright Borland International 1991                                  */
  6. /*  All Rights Reserved                                                   */
  7. /*                                                                        */
  8. /*------------------------------------------------------------------------*/
  9.  
  10. #if !defined( CHECKS_H )
  11. #include <Checks.h>
  12. #endif  // CHECKS_H
  13.  
  14. #if !defined( __BTREE_H )
  15. #include <BTree.h>
  16. #endif  // __BTREE_H
  17.  
  18. #ifndef __STDLIB_H
  19. #include <stdlib.h>
  20. #endif
  21.  
  22. #ifndef __IOSTREAM_H
  23. #include <iostream.h>
  24. #endif
  25.  
  26. //====== InnerNode functions ======
  27.  
  28. InnerNode::InnerNode(InnerNode* P, Btree* T) : Node(0,P,T)
  29. {
  30.     item = new Item[maxIndex()+1];
  31.     if( item == 0 )
  32.         ClassLib_error( __ENOMEMIA );
  33. }
  34.  
  35. InnerNode::InnerNode(InnerNode* Parent, Btree* Tree, Node* oldroot)
  36.                 : Node(0, Parent, Tree)
  37. {
  38.     // called only by Btree to initialize the InnerNode that is
  39.     // about to become the root.
  40.     item = new Item[maxIndex()+1];
  41.     if( item == 0 )
  42.         ClassLib_error( __ENOMEMIA );
  43.     append( 0, oldroot );
  44. }
  45.  
  46. InnerNode::~InnerNode()
  47. {
  48.     if( last > 0 )
  49.         delete item[0].tree;
  50.     for( int i = 1; i <= last; i++ )
  51.         {
  52.         delete item[i].tree;
  53.         if( tree->ownsElements() )
  54.             delete item[i].key;
  55.         }
  56.     delete [] item;
  57. }
  58.  
  59. // for quick (human reader) lookup, functions are in alphabetical order
  60.  
  61. void InnerNode::add( Sortable *obj, int index )
  62. {
  63.     // this is called only from Btree::add()
  64.     PRECONDITION( index >= 1 );
  65.     LeafNode* ln = getTree(index-1)->lastLeafNode();
  66.     ln->add( obj, ln->last+1 );
  67. }
  68.  
  69. void InnerNode::addElt( Item& itm, int at )
  70. {
  71.     PRECONDITION( 0 <= at && at <= last+1 );
  72.     PRECONDITION( last < maxIndex() );
  73.     for( int i = last+1; i > at ; i-- )
  74.         getItem(i) = getItem(i-1);
  75.     setItem( at, itm );
  76.     last++;
  77. }
  78.  
  79. void InnerNode::addElt( int at, Sortable* k, Node* t)
  80. {
  81.     Item newitem( k, t );
  82.     addElt( newitem, at );
  83. }
  84.  
  85. void InnerNode::add( Item& itm, int at )
  86. {
  87.     addElt( itm, at );
  88.     if( isFull() )
  89.         informParent();
  90. }
  91.  
  92. void InnerNode::add( int at, Sortable* k, Node* t)
  93. {
  94.     Item newitem( k, t );
  95.     add( newitem, at );
  96. }
  97.  
  98. void InnerNode::appendFrom( InnerNode* src, int start, int stop )
  99. {
  100.     // this should never create a full node
  101.     // that is, it is not used anywhere where THIS could possibly be
  102.     // near full.
  103.     if( start > stop )
  104.         return;
  105.     PRECONDITION( 0 <= start && start <= src->last );
  106.     PRECONDITION( 0 <= stop  && stop  <= src->last );
  107.     PRECONDITION( last + stop - start + 1 < maxIndex() ); // full-node check
  108.     for( int i = start; i <= stop; i++ )
  109.         setItem( ++last, src->getItem(i) );
  110. }
  111.  
  112. void InnerNode::append( Sortable* D, Node* N )
  113. {
  114.     // never called from anywhere where it might fill up THIS
  115.     PRECONDITION( last < maxIndex() );
  116.     setItem( ++last, D, N );
  117. }
  118.  
  119. void InnerNode::append( Item& itm )
  120. {
  121.     PRECONDITION( last < maxIndex() );
  122.     setItem( ++last, itm );
  123. }
  124.  
  125. void InnerNode::balanceWithLeft( InnerNode* leftsib, int pidx )
  126. {
  127.     // THIS has more than LEFTSIB;  move some item from THIS to LEFTSIB.
  128.     // PIDX is the index of the parent item that will change when keys
  129.     // are moved.
  130.     PRECONDITION( Vsize() >= leftsib->Psize() );
  131.     PRECONDITION( parent->getTree(pidx) == this );
  132.     int newThisSize = (Vsize() + leftsib->Psize())/2;
  133.     int noFromThis = Psize() - newThisSize;
  134.     pushLeft( noFromThis, leftsib, pidx );
  135. }
  136.  
  137. void InnerNode::balanceWithRight( InnerNode* rightsib, int pidx )
  138. {
  139.     // THIS has more than RIGHTSIB;  move some items from THIS to RIGHTSIB.
  140.     // PIDX is the index of the parent item that will change when keys
  141.     // are moved.
  142.     PRECONDITION( Psize() >= rightsib->Vsize() );
  143.     PRECONDITION( parent->getTree(pidx) == rightsib );
  144.     int newThisSize = (Psize() + rightsib->Vsize())/2;
  145.     int noFromThis = Psize() - newThisSize;
  146.     pushRight( noFromThis, rightsib, pidx );
  147.  
  148. }
  149.  
  150. void InnerNode::balanceWith( InnerNode* rightsib, int pindx )
  151. {
  152.     // PINDX is the index of the parent item whose key will change when
  153.     // keys are shifted from one InnerNode to the other.
  154.     if( Psize() < rightsib->Vsize() )
  155.         rightsib->balanceWithLeft( this, pindx );
  156.     else
  157.         balanceWithRight( rightsib, pindx );
  158. }
  159.  
  160. void InnerNode::decrNofKeys( Node *that )
  161. {
  162.     // THAT is a child of THIS that has just shrunk by 1
  163.     int i = indexOf( that );
  164.     item[i].nofKeysInTree--;
  165.     if( parent != 0 )
  166.         parent->decrNofKeys( this );
  167.     else
  168.         tree->decrNofKeys();
  169. }
  170.  
  171. long InnerNode::findRank( Sortable* what ) const
  172. {
  173.     // recursively look for WHAT starting in the current node
  174.  
  175.     if ( *what < *getKey(1) )
  176.         return getTree(0)->findRank(what);
  177.     long sum = getNofKeys(0);
  178.     for( int i = 1; i < last; i++ )
  179.         {
  180.         if( *what == *getKey(i) )
  181.             return sum;
  182.         sum++;
  183.         if( *what < *getKey(i+1) )
  184.             return sum + getTree(i)->findRank(what);
  185.         sum += getNofKeys(i);
  186.         }
  187.     if( *what == *getKey(last) )
  188.         return sum;
  189.     sum++;
  190.     // *what > getKey(last), so recurse on last item.tree
  191.     return sum + getTree(last)->findRank(what);
  192. }
  193.  
  194. long InnerNode::findRank_bu( const Node *that ) const
  195. {
  196.     // findRank_bu is findRank in reverse.
  197.     // whereas findRank looks for the object and computes the rank
  198.     // along the way while walking DOWN the tree, findRank_bu already
  199.     // knows where the object is and has to walk UP the tree from the
  200.     // object to compute the rank.
  201.     int L = indexOf( that );
  202.     long sum = 0;
  203.     for( int i = 0; i < L; i++ )
  204.         sum += getNofKeys(i);
  205.     return sum + L + (parent == 0 ? 0 : parent->findRank_bu( this ));
  206. }
  207.  
  208. LeafNode*InnerNode::firstLeafNode()
  209. {
  210.     return getTree(0)->firstLeafNode();
  211. }
  212.  
  213. Object& InnerNode::found(Sortable* what, Node** which, int* where )
  214. {
  215.     // recursively look for WHAT starting in the current node
  216.     for( int i = 1 ; i <= last; i++ )
  217.         {
  218.         if( *getKey(i) == *what )
  219.             {
  220.             // then could go in either item[i].tree or item[i-1].tree
  221.             // should go in one with the most room, but that's kinda
  222.             // hard to calculate, so we'll stick it in item[i].tree
  223.             *which = this;
  224.             *where = i;
  225.             return *getKey(i);
  226.             }
  227.         if( *getKey(i) > *what )
  228.             return getTree(i-1)->found(what, which, where);
  229.         }
  230.     // *what > *(*this)[last].key, so recurse on last item.tree
  231.     return getTree(last)->found( what, which, where );
  232. }
  233.  
  234. void InnerNode::incrNofKeys( Node *that )
  235. {
  236.     // THAT is a child of THIS that has just grown by 1
  237.     int i = indexOf( that );
  238.     item[i].nofKeysInTree++;
  239.     if( parent != 0 )
  240.         parent->incrNofKeys( this );
  241.     else
  242.         tree->incrNofKeys();
  243. }
  244.  
  245. #pragma warn -rvl
  246.  
  247. int InnerNode::indexOf( const Node *that ) const
  248. {
  249.     // returns a number in the range 0 to this->last
  250.     // 0 is returned if THAT == tree[0]
  251.     for( int i = 0; i <= last; i++ )
  252.         if( getTree(i) == that )
  253.             return i;
  254.     CHECK( 0 );
  255. }
  256.  
  257. #pragma warn .rvl
  258.  
  259. void InnerNode::informParent()
  260. {
  261.     if( parent == 0 )
  262.         {
  263.         // then this is the root of the tree and nees to be split
  264.         // inform the btree.
  265.         PRECONDITION( tree->root == this );
  266.         tree->rootIsFull();
  267.         }
  268.     else
  269.         parent->isFull( this );
  270. }
  271.  
  272. void InnerNode::isFull(Node *that)
  273. {
  274.     // the child node THAT is full.   We will either redistribute elements
  275.     // or create a new node and then redistribute.
  276.     // In an attempt to minimize the number of splits, we adopt the following
  277.     // strategy:
  278.     //  * redistribute if possible
  279.     //  * if not possible, then split with a sibling
  280.     if( that->isLeaf )
  281.         {
  282.         LeafNode *leaf = (LeafNode *)that;
  283.         LeafNode *left, *right;
  284.         // split LEAF only if both sibling nodes are full.
  285.         int leafidx = indexOf(leaf);
  286.         int hasRightSib = (leafidx < last)
  287.                                 && ((right=(LeafNode*)getTree(leafidx+1))
  288.                                           != 0);
  289.         int hasLeftSib  = (leafidx > 0)
  290.                                 && ((left=(LeafNode*)getTree(leafidx-1))
  291.                                          != 0);
  292.         int rightSibFull = (hasRightSib && right->isAlmostFull());
  293.         int leftSibFull  = (hasLeftSib  && left->isAlmostFull());
  294.         if( rightSibFull )
  295.             {
  296.             if( leftSibFull )
  297.                 {
  298.                 // both full, so pick one to split with
  299.                 left->splitWith( leaf, leafidx );
  300.                 }
  301.             else if( hasLeftSib )
  302.                 {
  303.                 // left sib not full, so balance with it
  304.                 leaf->balanceWithLeft( left, leafidx );
  305.                 }
  306.             else
  307.                 {
  308.                 // there is no left sibling, so split with right
  309.                 leaf->splitWith( right, leafidx+1 );
  310.                 }
  311.             }
  312.         else if( hasRightSib )
  313.             {
  314.             // right sib not full, so balance with it
  315.             leaf->balanceWithRight( right, leafidx+1 );
  316.             }
  317.         else if( leftSibFull )
  318.             {
  319.             // no right sib, and left sib is full, so split with it
  320.             left->splitWith( leaf, leafidx );
  321.             }
  322.         else if( hasLeftSib )
  323.             {
  324.             // left sib not full so balance with it
  325.             leaf->balanceWithLeft( left, leafidx );
  326.             }
  327.         else
  328.             {
  329.             // neither a left or right sib; should never happen
  330.             CHECK(0);
  331.             }
  332.         }
  333.     else {
  334.         InnerNode *inner = (InnerNode *)that;
  335.         // split INNER only if both sibling nodes are full.
  336.         int inneridx = indexOf(inner);
  337.         InnerNode *left, *right;
  338.         int hasRightSib = (inneridx < last)
  339.                                 && ((right=(InnerNode*)getTree(inneridx+1))
  340.                                           != 0);
  341.         int hasLeftSib  = (inneridx > 0)
  342.                                 && ((left=(InnerNode*)getTree(inneridx-1))
  343.                                          != 0);
  344.         int rightSibFull = (hasRightSib && right->isAlmostFull());
  345.         int leftSibFull  = (hasLeftSib  && left->isAlmostFull());
  346.         if( rightSibFull )
  347.             {
  348.             if( leftSibFull )
  349.                 {
  350.                 left->splitWith( inner, inneridx );
  351.                 }
  352.             else if( hasLeftSib )
  353.                 {
  354.                 inner->balanceWithLeft( left, inneridx );
  355.                 }
  356.             else
  357.                 {
  358.                 // there is no left sibling
  359.                 inner->splitWith(right, inneridx+1);
  360.                 }
  361.             }
  362.         else if( hasRightSib )
  363.             {
  364.             inner->balanceWithRight( right, inneridx+1 );
  365.             }
  366.         else if( leftSibFull )
  367.             {
  368.             left->splitWith( inner, inneridx );
  369.             }
  370.         else if( hasLeftSib )
  371.             {
  372.             inner->balanceWithLeft( left, inneridx );
  373.             }
  374.         else {
  375.             CHECK(0);
  376.             }
  377.         }
  378. }
  379.  
  380. void InnerNode::isLow( Node *that )
  381. {
  382.     // the child node THAT is <= half full.  We will either redistribute
  383.     // elements between children, or THAT will be merged with another child.
  384.     // In an attempt to minimize the number of mergers, we adopt the following
  385.     // strategy:
  386.     //  * redistribute if possible
  387.     //  * if not possible, then merge with a sibling
  388.     if( that->isLeaf )
  389.         {
  390.         LeafNode *leaf = (LeafNode *)that;
  391.         LeafNode *left, *right;
  392.         // split LEAF only if both sibling nodes are full.
  393.         int leafidx = indexOf(leaf);
  394.         int hasRightSib = (leafidx < last)
  395.                                 && ((right=(LeafNode*)getTree(leafidx+1))
  396.                                           != 0);
  397.         int hasLeftSib  = (leafidx > 0)
  398.                                 && ((left=(LeafNode*)getTree(leafidx-1))
  399.                                          != 0);
  400.         if( hasRightSib
  401.             && (leaf->Psize() + right->Vsize()) >= leaf->maxPsize())
  402.             {
  403.             // then cannot merge,
  404.             // and balancing this and rightsib will leave them both
  405.             // more than half full
  406.             leaf->balanceWith( right, leafidx+1 );
  407.             }
  408.         else if( hasLeftSib
  409.             && (leaf->Vsize() + left->Psize()) >= leaf->maxPsize())
  410.             {
  411.             // ditto
  412.             left->balanceWith( leaf, leafidx );
  413.             }
  414.         else if( hasLeftSib )
  415.             {
  416.             // then they should be merged
  417.             left->mergeWithRight( leaf, leafidx );
  418.             }
  419.         else if( hasRightSib )
  420.             {
  421.             leaf->mergeWithRight( right, leafidx+1 );
  422.             }
  423.         else
  424.             {
  425.             CHECK(0); // should never happen
  426.             }
  427.         }
  428.     else
  429.         {
  430.         InnerNode *inner = (InnerNode *)that;
  431.         //
  432.         int inneridx = indexOf(inner);
  433.         InnerNode *left, *right;
  434.         int hasRightSib = (inneridx < last)
  435.                                 && ((right=(InnerNode*)getTree(inneridx+1))
  436.                                           != 0);
  437.         int hasLeftSib  = (inneridx > 0)
  438.                                 && ((left=(InnerNode*)getTree(inneridx-1))
  439.                                          != 0);
  440.         if( hasRightSib
  441.             && (inner->Psize() + right->Vsize()) >= inner->maxPsize())
  442.             {
  443.             // cannot merge
  444.             inner->balanceWith( right, inneridx+1 );
  445.             }
  446.         else if( hasLeftSib
  447.             && (inner->Vsize() + left->Psize()) >= inner->maxPsize())
  448.             {
  449.             // cannot merge
  450.             left->balanceWith( inner, inneridx );
  451.             }
  452.         else if( hasLeftSib )
  453.             {
  454.             left->mergeWithRight( inner, inneridx );
  455.             }
  456.         else if( hasRightSib )
  457.             {
  458.             inner->mergeWithRight( right, inneridx+1 );
  459.             }
  460.         else
  461.             {
  462.             CHECK(0);
  463.             }
  464.         }
  465. }
  466.  
  467. LeafNode*InnerNode::lastLeafNode()
  468. {
  469.     return getTree(last)->lastLeafNode();
  470. }
  471.  
  472. void InnerNode::mergeWithRight( InnerNode* rightsib, int pidx )
  473. {
  474.     PRECONDITION( Psize() + rightsib->Vsize() < maxIndex() );
  475.     if( rightsib->Psize() > 0 )
  476.         rightsib->pushLeft( rightsib->Psize(), this, pidx );
  477.     rightsib->setKey( 0, parent->getKey( pidx ) );
  478.     appendFrom( rightsib, 0, 0 );
  479.     parent->incNofKeys( pidx-1, rightsib->getNofKeys(0)+1 );
  480.     parent->removeItem( pidx );
  481.     delete rightsib;
  482. }
  483.  
  484. long InnerNode::nofKeys() const
  485. {
  486.     long sum = 0;
  487.     for( int i = 0; i <= last; i++)
  488.         sum += getNofKeys(i);
  489.     return sum + Psize();
  490. }
  491.  
  492. Object& InnerNode::operator[]( long idx ) const
  493. {
  494.     for( int j=0; j <= last; j++ )
  495.         {
  496.         long R;
  497.         if( idx < (R = getNofKeys(j)) )
  498.             return (*getTree(j))[idx];
  499.         if( idx == R )
  500.             {
  501.             if( j == last )
  502.                 return NOOBJECT;
  503.             else
  504.                 return *getKey(j+1);
  505.             }
  506.         idx -= R+1; // +1 because of the key in the node
  507.         }
  508.     return NOOBJECT;
  509. }
  510.  
  511. void InnerNode::printOn(ostream& out) const
  512. {
  513.     out << " [ " << "/" << getNofKeys(0) << *getTree(0);
  514.     for( int i = 1; i <= last; i++ )
  515.         {
  516.         //*!*!*!*!* not for distribution!
  517.         CHECK( getTree(i)->debugKey == 1017 );
  518.         if( i > 1 )
  519.             CHECK( *getKey(i-1) <= *getKey(i) );
  520.         out << *getKey(i) << "/" << getNofKeys(i) << *getTree(i);
  521.         }
  522.     out << " ] ";
  523. }
  524.  
  525. void InnerNode::pushLeft( int noFromThis, InnerNode* leftsib, int pidx )
  526. {
  527.     // noFromThis==1 => moves the parent item into the leftsib,
  528.     // and the first item in this's array into the parent item
  529.     PRECONDITION( parent->getTree(pidx) == this );
  530.     PRECONDITION( noFromThis > 0 && noFromThis <= Psize() );
  531.     PRECONDITION( noFromThis + leftsib->Psize() < maxPsize() );
  532.     setKey( 0, parent->getKey(pidx) ); // makes appendFrom's job easier
  533.     leftsib->appendFrom( this, 0, noFromThis-1 );
  534.     shiftLeft( noFromThis );
  535.     parent->setKey( pidx, getKey(0) );
  536.     parent->setNofKeys( pidx-1, leftsib->nofKeys() );
  537.     parent->setNofKeys( pidx, nofKeys() );
  538. }
  539.  
  540. void InnerNode::pushRight(int noFromThis, InnerNode* rightsib, int pidx)
  541. {
  542.     PRECONDITION( noFromThis > 0 && noFromThis <= Psize() );
  543.     PRECONDITION( noFromThis + rightsib->Psize() < rightsib->maxPsize() );
  544.     PRECONDITION( parent->getTree(pidx) == rightsib );
  545.     //
  546.     // The operation is three steps:
  547.     //  Step I.  Make room for the incoming keys in RIGHTSIB.
  548.     //  Step II. Move the items from THIS into RIGHTSIB.
  549.     //  Step III.Update the length of THIS.
  550.     //
  551.     // Step I.: make space for noFromThis items
  552.     //
  553.     int start = last - noFromThis + 1;
  554.     int tgt, src;
  555.     tgt = rightsib->last + noFromThis;
  556.     src = rightsib->last;
  557.     rightsib->last = tgt;
  558.     rightsib->setKey( 0, parent->getKey( pidx ) ); incNofKeys(0);
  559.     while( src >= 0 )
  560.         {
  561.         // do this kind of assignment on InnerNode Items only when
  562.         // the parent fields
  563.         // of the moved items do not change, as they don't here.
  564.         // Otherwise, use setItem so the parents are updated appropriately.
  565.         rightsib->getItem(tgt--) = rightsib->getItem(src--);
  566.         }
  567.  
  568.     // Step II.Move the items from THIS into RIGHTSIB
  569.     for( int i = last; i >= start; i-- )
  570.         {
  571.         // this is the kind of assignment to use when parents change
  572.         rightsib->setItem(tgt--, getItem(i));
  573.         }
  574.     parent->setKey( pidx, rightsib->getKey(0) );
  575.     decNofKeys(0);
  576.     CHECK( tgt == -1 );
  577.  
  578.     // Step III.
  579.     last -= noFromThis;
  580.  
  581.     // Step VI.  update nofKeys
  582.     parent->setNofKeys( pidx-1, nofKeys() );
  583.     parent->setNofKeys( pidx, rightsib->nofKeys() );
  584. }
  585.  
  586. void InnerNode::remove( int index )
  587. {
  588.     PRECONDITION( index >= 1 && index <= last );
  589.     LeafNode* lf = getTree(index)->firstLeafNode();
  590.     setKey( index, lf->item[0] );
  591.     lf->removeItem(0);
  592. }
  593.  
  594. void InnerNode::removeItem( int index )
  595. {
  596.     PRECONDITION( index >= 1 && index <= last );
  597.     for( int to = index; to < last; to++ )
  598.         item[to] = item[to+1];
  599.     last--;
  600.     if( isLow() )
  601.         {
  602.         if( parent == 0 )
  603.             {
  604.             // then this is the root; when only one child, make the child
  605.             // the root
  606.             if( Psize() == 0 )
  607.                 tree->rootIsEmpty();
  608.             }
  609.         else
  610.             parent->isLow( this );
  611.         }
  612. }
  613.  
  614. void InnerNode::shiftLeft( int cnt )
  615. {
  616.     if( cnt <= 0 )
  617.         return;
  618.     for( int i = cnt; i <= last; i++ )
  619.         getItem(i-cnt) = getItem(i);
  620.     last -= cnt;
  621. }
  622.  
  623. void InnerNode::split()
  624. {
  625.     // this function is called only when THIS is the only descendent
  626.     // of the root node, and THIS needs to be split.
  627.     // assumes that idx of THIS in Parent is 0.
  628.     InnerNode* newnode = new InnerNode( parent );
  629.     CHECK( newnode != 0 );
  630.     parent->append( getKey(last), newnode );
  631.     newnode->appendFrom( this, last, last );
  632.     last--;
  633.     parent->incNofKeys( 1, newnode->getNofKeys(0) );
  634.     parent->decNofKeys( 0, newnode->getNofKeys(0) );
  635.     balanceWithRight( newnode, 1 );
  636. }
  637.  
  638. void
  639. InnerNode::splitWith( InnerNode *rightsib, int keyidx )
  640. {
  641.     // THIS and SIB are too full; create a NEWnODE, and balance
  642.     // the number of keys between the three of them.
  643.     //
  644.     // picture: (also see Knuth Vol 3 pg 478)
  645.     //              keyidx keyidx+1
  646.     //           +--+--+--+--+--+--...
  647.     //           |  |  |  |  |  |
  648.     // parent--->|  |     |     |
  649.     //           |  |     |     |
  650.     //           +*-+*-+*-+--+--+--...
  651.     //            |  |  |
  652.     //       +----+  |  +-----+
  653.     //       |       +-----+  |
  654.     //       V             |  V
  655.     //       +----------+  |  +----------+
  656.     //       |          |  |  |          |
  657.     // this->|          |  |  |          |<--sib
  658.     //       +----------+  |  +----------+
  659.     //                     V
  660.     //                    data
  661.     //
  662.     // keyidx is the index of where the sibling is, and where the
  663.     // newly created node will be recorded (sibling will be moved to
  664.     // keyidx+1)
  665.     //
  666.     PRECONDITION( keyidx > 0 && keyidx <= parent->last );
  667.     // I would like to be able to prove that the following assertion
  668.     // is ALWAYS true, but it is beyond my time limits.  If this assertion
  669.     // ever comes up False, then the code to make it so must be inserted
  670.     // here.
  671.     // assert(parent->getKey(keyidx) == rightsib->getKey(0));
  672.     // During debugging, this came up False, so
  673.     rightsib->setKey(0,parent->getKey(keyidx));
  674.     int nofKeys        = Psize() + rightsib->Vsize();
  675.     int newSizeThis    = nofKeys / 3;
  676.     int newSizeNew     = (nofKeys - newSizeThis) / 2;
  677.     int newSizeSib     = (nofKeys - newSizeThis - newSizeNew);
  678.     int noFromThis     = Psize() - newSizeThis;
  679.     int noFromSib      = rightsib->Vsize() - newSizeSib;
  680.     // because of their smaller size, this InnerNode may not have to
  681.     // give up any elements to the new node.  I.e., noFromThis == 0.
  682.     // This will not happen for LeafNodes.
  683.     // We handle this by pulling an item from the rightsib.
  684.     CHECK( noFromThis >= 0 );
  685.     CHECK( noFromSib >= 1 );
  686.     InnerNode* newNode = new InnerNode(parent);
  687.     CHECK( newNode != 0 );
  688.     if( noFromThis > 0 )
  689.         {
  690.         newNode->append( getItem(last) );
  691.         parent->addElt( keyidx, getKey(last--), newNode );
  692.         if( noFromThis > 2 )
  693.             this->pushRight( noFromThis-1, newNode, keyidx );
  694.         rightsib->pushLeft( noFromSib, newNode, keyidx+1 );
  695.         }
  696.     else
  697.         {
  698.         // pull an element from the rightsib
  699.         newNode->append( rightsib->getItem(0) );
  700.         parent->addElt( keyidx+1, rightsib->getKey(1), rightsib);
  701.         rightsib->shiftLeft(1);
  702.         parent->setTree( keyidx, newNode );
  703.         rightsib->pushLeft( noFromSib-1, newNode, keyidx+1 );
  704.         }
  705.     parent->setNofKeys( keyidx-1, this->nofKeys() );
  706.     parent->setNofKeys( keyidx, newNode->nofKeys() );
  707.     parent->setNofKeys( keyidx+1, rightsib->nofKeys() );
  708.     if( parent->isFull() )
  709.         parent->informParent();
  710. }
  711.