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 / BTREE.CPP < prev    next >
C/C++ Source or Header  |  1992-02-18  |  16KB  |  498 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  BTREE.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. /*
  27.  
  28. Implementation notes:
  29.  
  30. This implements B-trees with several refinements.  Most of them can be found
  31. in Knuth Vol 3, but some were developed to adapt to restrictions imposed
  32. by C++.  First, a restatement of Knuth's properties that a B-tree must
  33. satisfy, assuming we make the enhancement he suggests in the paragraph
  34. at the bottom of page 476.  Instead of storing null pointers to non-existent
  35. nodes (which Knuth calls the leaves) we utilize the space to store keys.
  36. Therefore, what Knuth calls level (l-1) is the bottom of our tree, and
  37. we call the nodes at this level LeafNodes.  Other nodes are called InnerNodes.
  38. The other enhancement we have adopted is in the paragraph at the bottom of
  39. page 477: overflow control.
  40.  
  41. The following are modifications of Knuth's properties on page 478:
  42.  
  43. i)  Every InnerNode has at most Order keys, and at most Order+1 sub-trees.
  44. ii) Every LeafNode has at most 2*(Order+1) keys.
  45. iii)An InnerNode with k keys has k+1 sub-trees.
  46. iv) Every InnerNode that is not the root has at least InnerLowWaterMark keys.
  47. v)  Every LeafNode that is not the root has at least LeafLowWaterMark keys.
  48. vi) If the root is a LeafNode, it has at least one key.
  49. vii)If the root is an InnerNode, it has at least one key and two sub-trees.
  50. viii)All LeafNodes are the same distance from the root as all the other
  51.     LeafNodes.
  52. ix) For InnerNode n with key n[i].key, then sub-tree n[i-1].tree contains
  53.     all keys <= n[i].key, and sub-tree n[i].tree contains all keys >= n[i].key.
  54. x)  Order is at least 3.
  55.  
  56. The values of InnerLowWaterMark and LeafLowWaterMark may actually be set
  57. by the user when the tree is initialized, but currently they are set
  58. automatically to:
  59.         InnerLowWaterMark = ceiling(Order/2)
  60.         LeafLowWaterMark  = Order - 1
  61.  
  62. If the tree is only filled, then all the nodes will be at least 2/3 full.
  63. They will almost all be exactly 2/3 full if the elements are added to the
  64. tree in order (either increasing or decreasing).  [Knuth says McCreight's
  65. experiments showed almost 100% memory utilization.  I don't see how that
  66. can be given the algorithms that Knuth gives.  McCreight must have used
  67. a different scheme for balancing.  [ No, he used a different scheme for
  68. splitting: he did a two-way split instead of the three way split as we do
  69. here.  Which means that McCreight does better on insertion of ordered data,
  70. but we should do better on insertion of random data.]]
  71.  
  72. It must also be noted that B-trees were designed for DISK access algorithms,
  73. not necessarily in-memory sorting, as we intend it to be used here.  However,
  74. if the order is kept small (< 6?) any inefficiency is negligible for
  75. in-memory sorting.  Knuth points out that balanced trees are actually
  76. preferable for memory sorting.  I'm not sure that I believe this, but
  77. it's interesting.  Also, deleting elements from balanced binary trees, being
  78. beyond the scope of Knuth's book (p. 465), is beyond my scope.  B-trees
  79. are good enough.
  80.  
  81.  
  82. A B-tree is declared to be of a certain ORDER (4 by default).  This number
  83. determines the number of keys contained in any interior node of the tree.
  84. Each interior node will contain ORDER keys, and therefore ORDER+1 pointers
  85. to sub-trees.  The keys are numbered and indexed 1 to ORDER while the
  86. pointers are numbered and indexed 0 to ORDER.  The 0th ptr points to the
  87. sub-tree of all elements that are less than key[1].  Ptr[1] points to the
  88. sub-tree that contains all the elements greater than key[1] and less than
  89. key[2].  etc.  The array of pointers and keys is allocated as ORDER+1
  90. pairs of keys and nodes, meaning that one key field (key[0]) is not used
  91. and therefore wasted.  Given that the number of interior nodes is
  92. small, that this waste allows fewer cases of special code, and that it
  93. is useful in certain of the methods, it was felt to be a worthwhile waste.
  94.  
  95. The size of the exterior nodes (leaf nodes) does not need to be related to
  96. the size of the interior nodes at all.  Since leaf nodes contain only
  97. keys, they may be as large or small as we like independent of the size
  98. of the interior nodes.  For no particular reason other than it seems like
  99. a good idea, we will allocate 2*(ORDER+1) keys in each leaf node, and they
  100. will be numbered and indexed from 0 to 2*ORDER+1.  It does have the advantage
  101. of keeping the size of the leaf and interior arrays the same, so that if we
  102. find allocation and de-allocation of these arrays expensive, we can modify
  103. their allocation to use a garbage ring, or something.
  104.  
  105. Both of these numbers will be run-time constants associated with each tree
  106. (each tree at run-time can be of a different order).  The variable `order'
  107. is the order of the tree, and the inclusive upper limit on the indices of
  108. the keys in the interior nodes.  The variable `order2' is the inclusive
  109. upper limit on the indices of the leaf nodes, and is designed
  110.     (1) to keep the sizes of the two kinds of nodes the same;
  111.     (2) to keep the expressions involving the arrays of keys looking
  112.         somewhat the same:   lower limit        upper limit
  113.           for inner nodes:        1                order
  114.           for leaf  nodes:        0                order2
  115.         Remember that index 0 of the inner nodes is special.
  116.  
  117. Currently, order2 = 2*(order+1).
  118.  
  119.  picture: (also see Knuth Vol 3 pg 478)
  120.  
  121.            +--+--+--+--+--+--...
  122.            |  |  |  |  |  |
  123.  parent--->|  |     |     |
  124.            |  |     |     |
  125.            +*-+*-+*-+--+--+--...
  126.             |  |  |
  127.        +----+  |  +-----+
  128.        |       +-----+  |
  129.        V             |  V
  130.        +----------+  |  +----------+
  131.        |          |  |  |          |
  132.  this->|          |  |  |          |<--sib
  133.        +----------+  |  +----------+
  134.                      V
  135.                     data
  136.  
  137. It is conceptually VERY convenient to think of the data as being the
  138. very first element of the sib node.  Any primitive that tells sib to
  139. perform some action on n nodes should include this `hidden' element.
  140. For InnerNodes, the hidden element has (physical) index 0 in the array,
  141. and in LeafNodes, the hidden element has (virtual) index -1 in the array.
  142. Therefore, there are two `size' primitives for nodes:
  143. Psize       - the physical size: how many elements are contained in the
  144.               array in the node.
  145. Vsize       - the `virtual' size; if the node is pointed to by
  146.               element 0 of the parent node, then Vsize == Psize;
  147.               otherwise the element in the parent item that points to this
  148.               node `belongs' to this node, and Vsize == Psize+1;
  149.  
  150. Parent nodes are always InnerNodes.
  151.  
  152. These are the primitive operations on Nodes:
  153.  
  154. append(elt)     - adds an element to the end of the array of elements in a
  155.                   node.  It must never be called where appending the element
  156.                   would fill the node.
  157. split()         - divide a node in two, and create two new nodes.
  158. splitWith(sib)  - create a third node between this node and the sib node,
  159.                   divvying up the elements of their arrays.
  160. pushLeft(n)     - move n elements into the left sibling
  161. pushRight(n)    - move n elements into the right sibling
  162. balanceWithRight() - even up the number of elements in the two nodes.
  163. balanceWithLeft()  - ditto
  164.  
  165.  
  166. To allow this implementation of btrees to also be an implementation of
  167. sorted arrays/lists, the overhead is included to allow O(log n) access
  168. of elements by their rank (`give me the 5th largest element').
  169. Therefore, each Item keeps track of the number of keys in and below it
  170. in the tree (remember, each item's tree is all keys to the RIGHT of the
  171. item's own key).
  172.  
  173. [ [ < 0 1 2 3 > 4 < 5 6 7 > 8 < 9 10 11 12 > ] 13 [ < 14 15 16 > 17 < 18 19 20 > ] ]
  174.    4  1 1 1 1   4   1 1 1   5   1  1  1  1      7  3   1  1  1    4    1  1  1
  175. */
  176.  
  177. //====== Btree functions ========
  178.  
  179. void Btree::finishInit( int O )
  180. {
  181.     if( O < 3 )
  182.         ClassLib_error( __EORDER3 );
  183.     ownsElements( 0 );
  184.     root = 0;
  185.     Order = O;
  186.     Order2 = 2 * (O+1);
  187.     Leaf_MaxIndex = Order2 - 1;     // item[0..Order2-1]
  188.     Inner_MaxIndex = Order;         // item[1..Order]
  189.     //
  190.     // the low water marks trigger an exploration for balancing
  191.     // or merging nodes.
  192.     // When the size of a node falls below X, then it must be possible to
  193.     // either balance this node with another node, or it must be possible
  194.     // to merge this node with another node.
  195.     // This can be guaranteed only if (this->size() < (maxSize()-1)/2).
  196.     //
  197.     //
  198.     Leaf_LowWaterMark = ((Leaf_MaxIndex+1            // == maxSize()
  199.                                          )-1) / 2    // satisfies the above
  200.                                                   - 1; // because we compare
  201.                                                      // lowwatermark with last
  202.  
  203.     Inner_LowWaterMark = (Order-1) / 2;
  204. }
  205.  
  206. Btree::Btree(int O) : itemsInContainer(0)
  207. {
  208.     finishInit(O);
  209. }
  210.  
  211. Btree::~Btree(void)
  212. {
  213.     if( root != 0 )
  214.         delete root;
  215. }
  216.  
  217. void Btree::flush( DeleteType dt )
  218. {
  219.     int oldValue = ownsElements();
  220.     ownsElements( delObj(dt) );
  221.     if( root != 0 )
  222.         delete root;
  223.     itemsInContainer = 0;
  224.     root = 0;
  225.     ownsElements( oldValue );
  226. }
  227.  
  228. int Btree::hasMember( Object& o ) const
  229. {
  230.     if( !o.isSortable() )
  231.         ClassLib_error( __ENOTSORT );
  232.     if( root == 0 )
  233.         return 0;
  234.     else
  235.         {
  236.         Node* loc;
  237.         int idx;
  238.         return root->found(&(Sortable&)o, &loc, &idx) != NOOBJECT;
  239.         }
  240. }
  241.  
  242. long Btree::rank( const Object& o ) const
  243. {
  244.     if( !o.isSortable() )
  245.         ClassLib_error( __ENOTSORT );
  246.     if( root == 0 )
  247.         return -1;
  248.     else
  249.         return root->findRank(&(Sortable&)o);
  250. }
  251.  
  252. Object& Btree::findMember( Object& o ) const
  253. {
  254.     if( !o.isSortable() )
  255.         ClassLib_error(__ENOTSORT);
  256.     if( root == 0 )
  257.         return NOOBJECT;
  258.     else
  259.         {
  260.         Node* loc;
  261.         int idx;
  262.         return root->found(&(Sortable&)o, &loc, &idx);
  263.         }
  264. }
  265.  
  266. void Btree::printOn( ostream& out ) const
  267. {
  268.     if( root == 0 )
  269.         out << "<empty>" ;
  270.     else
  271.         root->printOn(out);
  272. }
  273.  
  274. extern "C" void __ErrorMessage( const char * );
  275.  
  276. int Btree::isEqual( const Object& obj ) const
  277. {
  278.     if( obj.isA() == btreeClass )
  279.         {
  280.         __ErrorMessage( "Btree isEqual not implemented\n" );
  281.         exit(1);
  282.         }
  283.     return 0;
  284.  
  285.     // two btrees are equal only if they have the same number of
  286.     // elements, and they are all equal.  The structure of the tree
  287.     // itself doesn't enter into it.
  288. }
  289.  
  290.  
  291. long Btree::i_add( const Object& o )
  292. {
  293.     long r;
  294.     if( !o.isSortable() )
  295.         ClassLib_error( __ENOTSORT );
  296.     if( root == 0 )
  297.         {
  298.         root = new LeafNode( 0, &(Sortable&)o, this );
  299.         CHECK( root != 0 );
  300.         incrNofKeys();
  301.         r = 0;
  302.         }
  303.     else
  304.         {
  305.         Node* loc;
  306.         int idx;
  307.         if( root->found(&(Sortable&)o, &loc, &idx) != NOOBJECT )
  308.             {
  309.             // loc and idx are set to either where the object
  310.             // was found, or where it should go in the Btree.
  311.             // Nothing is here now, but later we might give the user
  312.             // the ability to declare a B-tree as `unique elements only',
  313.             // in which case we would handle an exception here.
  314.             // cerr << "Multiple entry warning\n";
  315.             }
  316.         else
  317.             {
  318.             CHECK( loc->isLeaf );
  319.             }
  320.         if( loc->isLeaf )
  321.             {
  322.             if( loc->parent == 0 )
  323.                 r = idx;
  324.             else
  325.                 r = idx + loc->parent->findRank_bu( loc );
  326.             }
  327.         else
  328.             {
  329.             InnerNode *iloc = (InnerNode*)loc;
  330.             r = iloc->findRank_bu( iloc->getTree( idx ) );
  331.             }
  332.         loc->add( &(Sortable&)o, idx );
  333.         }
  334.     CHECK( r == rank( (Sortable&)o ) || (Sortable&)o == (*this)[r] );
  335.     return r;
  336. }
  337.  
  338. void Btree::add( Object& o )
  339. {
  340.     if( !o.isSortable() )
  341.         ClassLib_error( __ENOTSORT );
  342.     if (root == 0)
  343.         {
  344.         root = new LeafNode( 0, &(Sortable&)o, this );
  345.         CHECK( root != 0 );
  346.         incrNofKeys();
  347.         }
  348.     else
  349.         {
  350.         Node* loc;
  351.         int idx;
  352.         if( root->found(&(Sortable&)o, &loc, &idx) != NOOBJECT )
  353.             {
  354.             // loc and idx are set to either where the object
  355.             // was found, or where it should go in the Btree.
  356.             // Nothing is here now, but later we might give the user
  357.             // the ability to declare a B-tree as `unique elements only',
  358.             // in which case we would handle an exception here.
  359.             }
  360.         loc->add( &(Sortable&)o, idx );
  361.         }
  362. }
  363.  
  364. void Btree::detach( Object& o, DeleteType dt )
  365. {
  366.     if( !o.isSortable() )
  367.         ClassLib_error(__ENOTSORT);
  368.     if( root == 0 )
  369.         return;
  370.  
  371.     Node* loc;
  372.     int idx;
  373.     Object* obj = &(root->found( &(Sortable&)o, &loc, &idx ));
  374.     if( *obj == NOOBJECT )
  375.         return;
  376.     loc->remove( idx );
  377.     if( delObj(dt) )
  378.         delete obj;
  379. }
  380.  
  381. void Btree::rootIsFull()
  382. {
  383.     // the root of the tree is full; create an InnerNode that
  384.     // points to it, and then inform the InnerNode that it is full.
  385.     Node* oldroot = root;
  386.     root = new InnerNode( 0, this, oldroot );
  387.     CHECK( root != 0 );
  388.     oldroot->split();
  389. }
  390.  
  391. void Btree::rootIsEmpty()
  392. {
  393.     if( root->isLeaf )
  394.         {
  395.         LeafNode* lroot = (LeafNode*)root;
  396.         CHECK( lroot->Psize() == 0 );
  397.         delete lroot;
  398.         root = 0;
  399.         }
  400.     else {
  401.         InnerNode* iroot = (InnerNode*)root;
  402.         CHECK(iroot->Psize() == 0);
  403.         root = iroot->getTree(0);
  404.         root->parent = 0;
  405.         delete iroot;
  406.         }
  407. }
  408.  
  409. Item::Item()
  410. {
  411.     nofKeysInTree = 0;
  412.     tree = 0;
  413.     key = 0;
  414. }
  415.  
  416. Item::Item(Node* n, Sortable* o)
  417. {
  418.     nofKeysInTree = n->nofKeys()+1;
  419.     tree = n;
  420.     key = o;
  421. }
  422.  
  423. Item::Item(Sortable* o, Node* n)
  424. {
  425.     nofKeysInTree = n->nofKeys()+1;
  426.     tree = n;
  427.     key = o;
  428. }
  429.  
  430. Item::~Item()
  431. {
  432. }
  433.  
  434. //
  435. //====== Node functions ======
  436. //
  437.  
  438. Node::Node(int isleaf, InnerNode* P, Btree* T)
  439. {
  440.     // nofElts = 0;
  441.     last = -1;
  442.     /*dbg*/debugKey = 1017; // !*!*!* not for distribution
  443.     isLeaf = isleaf;
  444.     parent = P;
  445.     if( P == 0 )
  446.         {
  447.         CHECK( T != 0 );
  448.         tree = T;
  449.         }
  450.     else
  451.         tree = P->tree;
  452. }
  453.  
  454. Node::~Node()
  455. {
  456. }
  457.  
  458. //
  459. //===== BtreeIterator methods =====
  460. //
  461.  
  462. void BtreeIterator::restart()
  463. {
  464.     index = 0;
  465. }
  466.  
  467. Object& BtreeIterator::operator++()
  468. {
  469.     return beingIterated[++index];
  470. }
  471.  
  472. Object& BtreeIterator::operator++( int )
  473. {
  474.     return beingIterated[index++];
  475. }
  476.  
  477. Object& BtreeIterator::current()
  478. {
  479.     return beingIterated[index];
  480. }
  481.  
  482.  
  483. ContainerIterator&
  484. Btree::initIterator() const
  485. {
  486.     return *( (ContainerIterator *)new BtreeIterator( *this ) );
  487. }
  488.  
  489. BtreeIterator::~BtreeIterator()
  490. {
  491. }
  492.  
  493.  
  494. BtreeIterator::operator int()
  495. {
  496.     return index < beingIterated.getItemsInContainer();
  497. }
  498.