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 / BTREELFN.CPP < prev    next >
C/C++ Source or Header  |  1992-02-18  |  11KB  |  360 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  BTREELFN.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. //====== LeafNode functions =======
  27.  
  28. LeafNode::LeafNode(InnerNode* P, Sortable* O, Btree* T): Node(1, P, T)
  29. {
  30.     item = new Sortable *[maxIndex()+1];
  31.     if( item == 0 )
  32.         ClassLib_error( __ENOMEMLN );
  33.     if( O != 0 )
  34.         item[++last] = O;
  35. }
  36.  
  37. LeafNode::~LeafNode()
  38. {
  39.     if( tree->ownsElements() )
  40.         {
  41.         for( int i = 0; i <= last; i++ )
  42.             delete item[i];
  43.         }
  44.     delete [] item;
  45. }
  46.  
  47. void LeafNode::add(Sortable *obj, int index)
  48. {
  49.     // add the object OBJ to the leaf node, inserting it at location INDEX
  50.     // in the item array
  51.     PRECONDITION( 0 <= index && index <= last+1 );
  52.     PRECONDITION( last <= maxIndex() );
  53.     for( int i = last+1; i > index ; i-- )
  54.         item[i] = item[ i - 1 ];
  55.     item[ index ] = obj;
  56.     last++;
  57.  
  58.     // check for overflow
  59.     if( parent == 0 )
  60.         tree->incrNofKeys( );
  61.     else
  62.         parent->incrNofKeys( this );
  63.  
  64.     if( isFull() )
  65.         {
  66.         // it's full; tell parent node
  67.         if( parent == 0 )
  68.             {
  69.             // this occurs when this leaf is the only node in the
  70.             // btree, and this->tree->root == this
  71.             CHECK( tree->root == this );
  72.             // in which case we inform the btree, which can be
  73.             // considered the parent of this node
  74.             tree->rootIsFull();
  75.             }
  76.         else
  77.             {
  78.             // the parent is responsible for splitting/balancing subnodes
  79.             parent->isFull( this );
  80.             }
  81.         }
  82. }
  83.  
  84. void LeafNode::appendFrom( LeafNode* src, int start, int stop )
  85. {
  86.     // A convenience function, does not worry about the element in
  87.     // the parent, simply moves elements from SRC[start] to SRC[stop]
  88.     // into the current array.
  89.     // This should never create a full node.
  90.     // That is, it is not used anywhere where THIS could possibly be
  91.     // near full.
  92.     // Does NOT handle nofKeys.
  93.     if( start > stop )
  94.         return;
  95.     PRECONDITION( 0 <= start && start <= src->last );
  96.     PRECONDITION( 0 <= stop  && stop  <= src->last );
  97.     PRECONDITION( last + stop - start + 1 < maxIndex() ); // full-node check
  98.     for( int i = start; i <= stop; i++ )
  99.         item[++last] = src->item[i];
  100.     CHECK( last < maxIndex() );
  101. }
  102.  
  103. void LeafNode::append( Sortable* D )
  104. {
  105.     // never called from anywhere where it might fill up THIS
  106.     // does NOT handle nofKeys.
  107.     item[++last] = D;
  108.     CHECK( last < maxIndex() );
  109. }
  110.  
  111.  
  112. void LeafNode::balanceWithLeft( LeafNode* leftsib, int pidx )
  113. {
  114.     // THIS has more than LEFTSIB;  move some items from THIS to LEFTSIB.
  115.     PRECONDITION( Vsize() >= leftsib->Psize() );
  116.     int newThisSize = (Vsize() + leftsib->Psize())/2;
  117.     int noFromThis  = Psize() - newThisSize;
  118.     pushLeft( noFromThis, leftsib, pidx );
  119. }
  120.  
  121. void LeafNode::balanceWithRight( LeafNode* rightsib, int pidx )
  122. {
  123.     // THIS has more than RIGHTSIB;  move some items from THIS to RIGHTSIB.
  124.     PRECONDITION( Psize() >= rightsib->Vsize() );
  125.     int newThisSize = (Psize() + rightsib->Vsize())/2;
  126.     int noFromThis  = Psize() - newThisSize;
  127.     pushRight( noFromThis, rightsib, pidx );
  128. }
  129.  
  130. void LeafNode::balanceWith( LeafNode* rightsib, int pidx )
  131. {
  132.     // PITEM is the parent item whose key will change when keys are shifted
  133.     // from one LeafNode to the other.
  134.     if( Psize() < rightsib->Vsize() )
  135.         rightsib->balanceWithLeft( this, pidx );
  136.     else
  137.         balanceWithRight( rightsib, pidx );
  138. }
  139.  
  140. long LeafNode::findRank( Sortable* what ) const
  141. {
  142.     // WHAT was not in any inner node; it is either here, or it's
  143.     // not in the tree
  144.     for( int i = 0; i <= last; i++ )
  145.         {
  146.         if( *item[i] == *what )
  147.             return i;
  148.         if( *item[i] >= *what )
  149.             return -1;
  150.         }
  151.     return -1;
  152. }
  153.  
  154. LeafNode *LeafNode::firstLeafNode()
  155. {
  156.     return this;
  157. }
  158.  
  159. Object& LeafNode::found(Sortable* what, Node** which, int* where )
  160. {
  161.     // WHAT was not in any inner node; it is either here, or it's
  162.     // not in the tree
  163.     for( int i = 0; i <= last; i++ )
  164.         {
  165.         if( *item[i] == *what )
  166.             {
  167.             *which = this;
  168.             *where = i;
  169.             return *item[i];
  170.             }
  171.         if( *item[i] >= *what )
  172.             {
  173.             *which = this;
  174.             *where = i;
  175.             return NOOBJECT;
  176.             }
  177.         }
  178.     *which = this;
  179.     *where = last+1;
  180.     return NOOBJECT;
  181. }
  182.  
  183. #pragma warn -rvl
  184.  
  185. int LeafNode::indexOf( const Sortable *that ) const
  186. {
  187.     // returns a number in the range 0 to maxIndex()
  188.     for( int i = 0; i <= last; i++ )
  189.         {
  190.         if( item[i] == that )
  191.             return i;
  192.         }
  193.     CHECK(0);
  194. }
  195.  
  196. #pragma warn .rvl
  197.  
  198. LeafNode *LeafNode::lastLeafNode()
  199. {
  200.     return this;
  201. }
  202.  
  203. void LeafNode::mergeWithRight( LeafNode* rightsib, int pidx )
  204. {
  205.     PRECONDITION( Psize() + rightsib->Vsize() < maxPsize() );
  206.     rightsib->pushLeft( rightsib->Psize(), this, pidx );
  207.     append( parent->getKey( pidx ) );
  208.     parent->setNofKeys( pidx-1, nofKeys() );
  209.     // cout << "in mergeWithRight:\n" << *parent << "\n";
  210.     parent->removeItem( pidx );
  211.     delete rightsib;
  212.     // cout << "in mergeWithRight:\n" << *parent << "\n";
  213. }
  214.  
  215. long LeafNode::nofKeys( int ) const
  216. {
  217.     return 1;
  218. }
  219.  
  220. long LeafNode::nofKeys() const
  221. {
  222.     return Psize();
  223. }
  224.  
  225. void LeafNode::printOn(ostream& out) const
  226. {
  227.     out << " < ";
  228.     for( int i = 0; i <= last; i++ )
  229.         out << *item[i] << " " ;
  230.     out << "> ";
  231. }
  232.  
  233. void LeafNode::pushLeft( int noFromThis, LeafNode* leftsib, int pidx )
  234. {
  235.     // noFromThis==1 => moves the parent item into the leftsib,
  236.     // and the first item in this's array into the parent item
  237.     PRECONDITION( noFromThis > 0 && noFromThis <= Psize() );
  238.     PRECONDITION( noFromThis + leftsib->Psize() < maxPsize() );
  239.     PRECONDITION( parent->getTree(pidx) == this );
  240.     leftsib->append( parent->getKey(pidx) );
  241.     if( noFromThis > 1 )
  242.         leftsib->appendFrom( this, 0, noFromThis-2 );
  243.     parent->setKey( pidx, item[noFromThis-1] );
  244.     shiftLeft( noFromThis );
  245.     parent->setNofKeys( pidx-1, leftsib->nofKeys() );
  246.     parent->setNofKeys( pidx, nofKeys() );
  247. }
  248.  
  249. void LeafNode::pushRight( int noFromThis, LeafNode* rightsib, int pidx )
  250. {
  251.     // noFromThis==1 => moves the parent item into the
  252.     // rightsib, and the last item in this's array into the parent
  253.     // item
  254.     PRECONDITION(noFromThis > 0 && noFromThis <= Psize());
  255.     PRECONDITION(noFromThis + rightsib->Psize() < maxPsize());
  256.     PRECONDITION(parent->getTree(pidx) == rightsib);
  257.     // The operation is five steps:
  258.     //  Step I.  Make room for the incoming keys in RIGHTSIB.
  259.     //  Step II. Move the key in the parent into RIGHTSIB.
  260.     //  Step III.Move the items from THIS into RIGHTSIB.
  261.     //  Step IV. Move the item from THIS into the parent.
  262.     //  Step V.  Update the length of THIS.
  263.     //
  264.     // Step I.: make space for noFromThis items
  265.     //
  266.     int start = last - noFromThis + 1;
  267.     int tgt, src;
  268.     tgt = rightsib->last + noFromThis;
  269.     src = rightsib->last;
  270.     rightsib->last = tgt;
  271.     while (src >= 0)
  272.         rightsib->item[tgt--] = rightsib->item[src--];
  273.  
  274.     // Step II. Move the key from the parent into place
  275.     rightsib->item[ tgt-- ] = parent->getKey( pidx );
  276.  
  277.     // Step III.Move the items from THIS into RIGHTSIB
  278.     for( int i = last; i > start; i-- )
  279.         rightsib->item[tgt--] = item[i];
  280.     CHECK( tgt == -1 );
  281.  
  282.     // Step IV.
  283.     parent->setKey( pidx, item[ start ] );
  284.  
  285.     // Step V.
  286.     last -= noFromThis;
  287.  
  288.     // Step VI.  update nofKeys
  289.     parent->setNofKeys( pidx-1, nofKeys() );
  290.     parent->setNofKeys( pidx, rightsib->nofKeys() );
  291. }
  292.  
  293. void LeafNode::remove( int index )
  294. {
  295.     PRECONDITION( index >= 0 && index <= last );
  296.     for( int to = index; to < last; to++ )
  297.         item[to] = item[to+1];
  298.     last--;
  299.     if( parent == 0 )
  300.         tree->decrNofKeys();
  301.     else
  302.         parent->decrNofKeys( this );
  303.     if( isLow() )
  304.         {
  305.         if( parent == 0 )
  306.             {
  307.             // then this is the root; when no keys left, inform the tree
  308.             if( Psize() == 0 )
  309.                 tree->rootIsEmpty();
  310.             }
  311.         else
  312.             parent->isLow( this );
  313.         }
  314. }
  315.  
  316. void LeafNode::shiftLeft( int cnt )
  317. {
  318.     if( cnt <= 0 )
  319.         return;
  320.     for( int i = cnt; i <= last; i++ )
  321.         item[i-cnt] = item[i];
  322.     last -= cnt;
  323. }
  324.  
  325. void LeafNode::split()
  326. {
  327.     // this function is called only when THIS is the only descendent
  328.     // of the root node, and THIS needs to be split.
  329.     // assumes that idx of THIS in Parent is 0.
  330.     LeafNode* newnode = new LeafNode( parent );
  331.     CHECK( newnode != 0 );
  332.     parent->append( item[last--], newnode );
  333.     parent->setNofKeys( 0, parent->getTree(0)->nofKeys() );
  334.     parent->setNofKeys( 1, parent->getTree(1)->nofKeys() );
  335.     balanceWithRight( newnode, 1 );
  336. }
  337.  
  338. void LeafNode::splitWith( LeafNode *rightsib, int keyidx )
  339. {
  340.     PRECONDITION(parent == rightsib->parent);
  341.     PRECONDITION(keyidx > 0 && keyidx <= parent->last);
  342.     int nofKeys        = Psize() + rightsib->Vsize();
  343.     int newSizeThis    = nofKeys / 3;
  344.     int newSizeNew     = (nofKeys - newSizeThis) / 2;
  345.     int newSizeSib     = (nofKeys - newSizeThis - newSizeNew);
  346.     int noFromThis     = Psize() - newSizeThis;
  347.     int noFromSib      = rightsib->Vsize() - newSizeSib;
  348.     CHECK(noFromThis >= 0);
  349.     CHECK(noFromSib >= 1);
  350.     LeafNode* newNode  = new LeafNode(parent);
  351.     CHECK( newNode != 0 );
  352.     parent->addElt( keyidx, item[last--], newNode );
  353.     parent->setNofKeys( keyidx, 0 );
  354.     parent->decNofKeys( keyidx-1 );
  355.     this->pushRight( noFromThis-1, newNode, keyidx );
  356.     rightsib->pushLeft( noFromSib, newNode, keyidx+1 );
  357.     if( parent->isFull() )
  358.         parent->informParent();
  359. }
  360.