home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / gbtree.cxx < prev    next >
C/C++ Source or Header  |  1995-03-08  |  26KB  |  950 lines
  1.  
  2.  
  3.  
  4.  
  5. /*
  6.  *
  7.  *          Copyright (C) 1994, M. A. Sridhar
  8.  *  
  9.  *
  10.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  11.  *     to copy, modify or distribute this software  as you see fit,
  12.  *     and to use  it  for  any  purpose, provided   this copyright
  13.  *     notice and the following   disclaimer are included  with all
  14.  *     copies.
  15.  *
  16.  *                        DISCLAIMER
  17.  *
  18.  *     The author makes no warranties, either expressed or implied,
  19.  *     with respect  to  this  software, its  quality, performance,
  20.  *     merchantability, or fitness for any particular purpose. This
  21.  *     software is distributed  AS IS.  The  user of this  software
  22.  *     assumes all risks  as to its quality  and performance. In no
  23.  *     event shall the author be liable for any direct, indirect or
  24.  *     consequential damages, even if the  author has been  advised
  25.  *     as to the possibility of such damages.
  26.  *
  27.  */
  28.  
  29.  
  30.  
  31.  
  32.  
  33. #ifdef __GNUC__
  34. #pragma implementation
  35. #endif
  36.  
  37. #include "base/gbtree.h"
  38. #ifdef DEBUG
  39. #include "base/memory.h"
  40. #endif
  41.  
  42. #define MAX_BTREE_HEIGHT 30 // Can't have trees higher than this
  43.  
  44.  
  45.  
  46. ////////////////////////////////////////////////////////////////////////////
  47. //         CL_GenericBTreeNode function definitions                       //
  48. ////////////////////////////////////////////////////////////////////////////
  49.  
  50.  
  51.  
  52. CL_GenericBTreeNode::CL_GenericBTreeNode
  53.     (short order, CL_BTreeNodeSpace* space, CL_AbstractComparator& cmp)
  54. :  _order (order), _cmp (cmp), _nodeSpace (space)
  55. {
  56.     _keyCount = 0;
  57.     register short n = 2*order;
  58.     _subtree = new CL_BTreeNodeHandle [n];
  59.     for (short i = 0; i < n; i++)
  60.         _subtree[i] = 0;
  61.     _item = new CL_VoidPtr [n-1];
  62.     _isLeaf = TRUE;
  63.     _subtreeSize = 0;
  64.     
  65. }
  66.  
  67.  
  68. CL_GenericBTreeNode::~CL_GenericBTreeNode()
  69. {
  70.     delete [] _item;
  71.     delete [] _subtree ;
  72. }
  73.  
  74.  
  75. bool CL_GenericBTreeNode::Search (CL_VoidPtr itm, short& index) const
  76. {
  77.     if (!_item)
  78.         return FALSE;
  79.     short i;
  80.     short result;
  81.     if (_keyCount <= 7) { // Small number of keys, do a linear search
  82.         if (_keyCount == 0) {
  83.             index = -1;
  84.             return FALSE;
  85.         }
  86.         for (i = 0; i < _keyCount; i++) {
  87.             result = _cmp (_item[i], itm);
  88.             if (result >= 0)
  89.                 break;
  90.         }
  91.         if (result == 0) {
  92.             index = i;
  93.             return TRUE;
  94.         }
  95.         else  {
  96.             index = i-1;
  97.             return FALSE;
  98.         }
  99.     }
  100.  
  101.     // Do a binary search
  102.     short lo = 0, hi = _keyCount-1, mid;
  103.     while (lo <= hi) {
  104.         mid = (lo + hi)/2;
  105.         result = _cmp (_item[mid], itm);
  106.         if (result == 0) {
  107.             index = mid;
  108.             return TRUE;
  109.         }
  110.         if (result < 0)
  111.             lo = mid+1;
  112.         else
  113.             hi = mid-1;
  114.     }
  115.     index = (result <= 0) ? (mid) :  mid-1;
  116.     return FALSE;
  117. }
  118.  
  119. void CL_GenericBTreeNode::ShiftRightAt (short pos, short amount)
  120. {
  121.     for (short i = _keyCount-1; i >= pos; i--) {
  122.         _item[i+amount] = _item[i];
  123.         _subtree[i+amount+1] = _subtree[i+1];
  124.     }
  125.     _subtree [pos+amount] = _subtree[pos];
  126.     for (i = pos; i < pos+amount; i++) {
  127.         _item[i] = 0;
  128.     }
  129. }
  130.  
  131.  
  132. void CL_GenericBTreeNode::ShiftLeftAt (short pos, short amount)
  133. {
  134.     for (short i = pos; i < _keyCount; i++) {
  135.         _item[i-amount] = _item[i];
  136.         _subtree[i-amount] = _subtree[i];
  137.     }
  138.     // Now move the rightmost subtree
  139.     _subtree [_keyCount-amount] = _subtree[_keyCount];
  140.     for (i = _keyCount-amount+1; i <= _keyCount; i++)
  141.         _subtree[i] = 0;
  142.     for (i = _keyCount-amount; i < _keyCount; i++)
  143.         _item[i] = 0;
  144.     _keyCount -= amount;
  145. }
  146.  
  147.  
  148.  
  149. void CL_GenericBTreeNode::MoveSubNode
  150.     (const CL_GenericBTreeNode& x, short pos, short our_pos,
  151.      short nkeys)
  152. {
  153.     short i, j;
  154.     for (i = our_pos, j = pos; i < our_pos + nkeys; i++, j++) {
  155.         _item[i] = x._item[j];
  156.         _subtree[i] = x._subtree[j];
  157.         x._item[j] = 0;
  158.         x._subtree[j] = 0;
  159.     }
  160.     _subtree[our_pos+nkeys] = x._subtree[pos + nkeys];
  161. }
  162.  
  163.  
  164.  
  165. ////////////////////////////////////////////////////////////////////////////
  166. //                  CL_BTreeNodeSpace methods                             //
  167. ////////////////////////////////////////////////////////////////////////////
  168.  
  169.  
  170.  
  171.  
  172.  
  173. void CL_BTreeNodeSpace::_Destroy (CL_GenericBTreeNode* node) const
  174. {
  175.     if (node) {
  176.         register short n = node->Size();
  177.         for (short i = 0; i < n; i++)
  178.             DestroyItem (node->Item(i));
  179.         delete node;
  180.     }
  181. }
  182.     
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189. ////////////////////////////////////////////////////////////////////////////
  190. //              CL_HeapBTreeNodeSpace methods                             //
  191. ////////////////////////////////////////////////////////////////////////////
  192.  
  193.  
  194.  
  195. CL_HeapBTreeNodeSpace::CL_HeapBTreeNodeSpace (short order, const
  196.                                               CL_GenericBTree& tree,
  197.                                               CL_AbstractComparator& cmp)
  198. : CL_BTreeNodeSpace (order, tree, cmp)
  199. {
  200.     _root = CreateNode();
  201. }
  202.  
  203.  
  204.  
  205. CL_HeapBTreeNodeSpace::~CL_HeapBTreeNodeSpace ()
  206. {
  207.     // Traverse the tree and get rid of all the nodes
  208.     _DestroySubtree (_root);
  209.     _root = NULL;
  210. }
  211.  
  212.  
  213.  
  214. void CL_HeapBTreeNodeSpace::_DestroySubtree (CL_BTreeNodeHandle h)
  215. {
  216.     // Do a post-order walk, destroying nodes as we go along
  217.     if (!h)
  218.         return;
  219.     CL_GenericBTreeNode* node = (CL_GenericBTreeNode*) h;
  220.     register short n = node->Size();
  221.     for (register short i = 0; i <= n; i++)
  222.         _DestroySubtree (node->Subtree(i));
  223.     _Destroy (node);
  224. }
  225.  
  226.  
  227. CL_BTreeNodeHandle CL_HeapBTreeNodeSpace::CreateNode ()
  228. {
  229.     CL_GenericBTreeNode* p = _BuildNode ();
  230.     if (p)
  231.         _SetHandle (*p, (CL_BTreeNodeHandle) p);
  232.     return (CL_BTreeNodeHandle) p;
  233. }
  234.  
  235.  
  236. // static long time = 0; // DEBUG
  237. // static FILE* theFile = fopen ("g:/logfile", "w"); // DEBUG
  238.  
  239. CL_GenericBTreeNode*  CL_HeapBTreeNodeSpace::BorrowNode
  240. (CL_BTreeNodeHandle h) const
  241. {
  242.     // if (h) fprintf (theFile, "%8lx %08ld borrowed\n", h, time++); // DEBUG
  243.     return (CL_GenericBTreeNode*) h;
  244. }
  245.  
  246.  
  247. void CL_HeapBTreeNodeSpace::ReturnNode (CL_GenericBTreeNode* /* h */) const
  248. {
  249.     // fprintf (theFile, "%8lx %08ld returned\n",  h, time++); // DEBUG
  250. }
  251.  
  252.  
  253. void CL_HeapBTreeNodeSpace::DestroyNode (CL_GenericBTreeNode* node)
  254. {
  255.     // fprintf (theFile, "%8lx %08ld destroyed\n", node, time++); // DEBUG
  256.     _Destroy (node);
  257. }
  258.  
  259.  
  260.  
  261.  
  262.  
  263. ////////////////////////////////////////////////////////////////////////////
  264. //                     CL_GenericBTree       definitions                  //
  265. ////////////////////////////////////////////////////////////////////////////
  266.  
  267.  
  268.  
  269. CL_GenericBTree::CL_GenericBTree (CL_AbstractComparator& cmp,
  270.                                   short order, CL_BTreeNodeSpace* space)
  271. : _comparator (cmp)
  272. {
  273.     _order = maxl (order, 2);
  274.     if (space) {
  275.         _nodeSpace = space;
  276.         _ownNodeSpace = FALSE;
  277.     }
  278.     else {
  279.         _nodeSpace = new CL_HeapBTreeNodeSpace (_order, *this, cmp);
  280.         _ownNodeSpace = TRUE;
  281.     }
  282. }
  283.  
  284.  
  285. CL_GenericBTree::~CL_GenericBTree ()
  286. {
  287.     if (_ownNodeSpace)
  288.         delete _nodeSpace;
  289. }
  290.  
  291.  
  292. CL_VoidPtr CL_GenericBTree::Find (CL_VoidPtr item) const
  293. {
  294.     short pos;
  295.     bool found;
  296.     CL_VoidPtr ret_val = NULL;
  297.  
  298.     CL_BTreeNodeHandle curHandle = _nodeSpace->RootHandle ();
  299.     CL_GenericBTreeNode* current;
  300.     do {
  301.         current = _nodeSpace->BorrowNode (curHandle);
  302.         found = current->Search (item, pos);
  303.     if (found || current->_isLeaf) break;
  304.         curHandle = current->_subtree [pos+1];
  305.         _nodeSpace->ReturnNode (current);
  306.     } while (1);
  307.     if (found)
  308.         ret_val = current->_item [pos];
  309.     _nodeSpace->ReturnNode (current);
  310.     return ret_val;
  311. }
  312.  
  313.  
  314.  
  315.  
  316. CL_VoidPtr CL_GenericBTree::ItemWithRank (long rank) const
  317. {
  318.     CL_GenericBTreeNode* tmp_ptr, *p1;
  319.     tmp_ptr = _nodeSpace->BorrowRoot ();
  320.     if (!tmp_ptr || tmp_ptr->_keyCount <= 0)
  321.         return NULL;
  322.     rank = minl (maxl (rank, 0), tmp_ptr->_subtreeSize-1);
  323.     do {
  324.         if (tmp_ptr->_isLeaf) {
  325.             assert ((0 <= rank && rank <= tmp_ptr->_keyCount-1),
  326.                     ("Internal error: CL_GenericBTree::ItemWithRank:"
  327.                      "bad key count %d rank %ld", tmp_ptr->_keyCount, rank));
  328.             CL_VoidPtr ret = tmp_ptr->_item[rank];
  329.             _nodeSpace->ReturnNode (tmp_ptr);
  330.             return ret;
  331.         }
  332.         // We're in a non-leaf, so find the subtree to descend into
  333.         // (if any)
  334.         for (short i = 0; i < tmp_ptr->_keyCount; i++) {
  335.             p1 = _nodeSpace->BorrowNode (tmp_ptr->_subtree[i]);
  336.             if (p1->_subtreeSize > rank)
  337.                 break;
  338.             rank -= p1->_subtreeSize; // Account for i-th subtree
  339.             _nodeSpace->ReturnNode (p1);
  340.             if (rank == 0) {
  341.                 // We've got the item we wanted
  342.                 CL_VoidPtr ret = tmp_ptr->_item[i];
  343.                 _nodeSpace->ReturnNode (tmp_ptr);
  344.                 return ret;
  345.             }
  346.             rank--;               // Account for i-th key in node
  347.         }
  348.         if (i >= tmp_ptr->_keyCount) {
  349.             // Descend into rightmost subtree
  350.             p1 = _nodeSpace->BorrowNode (tmp_ptr->_subtree[i]);
  351.         }
  352.         _nodeSpace->ReturnNode (tmp_ptr);
  353.         tmp_ptr = p1;
  354.     } while (1);
  355. }
  356.  
  357.  
  358. long CL_GenericBTree::RankOf (CL_VoidPtr item) const
  359. {
  360.     short pos;
  361.     bool found;
  362.     long count = 0;
  363.  
  364.     CL_GenericBTreeNode* tmp_ptr, *p1;
  365.     tmp_ptr = _nodeSpace->BorrowRoot ();
  366.     if (!tmp_ptr || tmp_ptr->_keyCount <= 0)
  367.         return 0;
  368.     do {
  369.         found = tmp_ptr->Search (item, pos);
  370.         if (tmp_ptr->_isLeaf) {
  371.             _nodeSpace->ReturnNode (tmp_ptr);
  372.             count += found ? pos : pos+1;
  373.             return count;
  374.         }
  375.         // We're in a non-leaf, so find the subtree to descend into
  376.         for (short i = 0; i <= pos; i++) {
  377.             p1 = _nodeSpace->BorrowNode (tmp_ptr->_subtree[i]);
  378.             count += p1->_subtreeSize; // Account for i-th subtree
  379.             _nodeSpace->ReturnNode (p1);
  380.         }
  381.         if (found)  {
  382.             _nodeSpace->ReturnNode (tmp_ptr);
  383.             return count + pos;
  384.         }
  385.         count += pos+1; // Account for the keys we compared
  386.         p1 = _nodeSpace->BorrowNode (tmp_ptr->_subtree[i]);
  387.         _nodeSpace->ReturnNode (tmp_ptr);
  388.         tmp_ptr = p1;
  389.     } while (1);
  390. }
  391.  
  392.  
  393.  
  394. long CL_GenericBTree::Size() const
  395. {
  396.     CL_GenericBTreeNode* node = _nodeSpace->BorrowRoot ();
  397.     long size = node->_subtreeSize;
  398.     _nodeSpace->ReturnNode (node);
  399.     return size;
  400. }
  401.  
  402.  
  403.    
  404.  
  405.  
  406. bool CL_GenericBTree::Add (CL_VoidPtr item)
  407. {
  408.     bool        ans;
  409.     CL_GenericBTreeNode* aNode,  *root;
  410.  
  411.     root = _nodeSpace->BorrowRoot ();
  412.     if (root->_keyCount < (2*_order - 1)) {
  413.         ans = _InsertNonFull (root, item);
  414.         return ans;
  415.     }
  416.  
  417.     // Root is full; create a new empty root
  418.     aNode = _nodeSpace->MakeNode(); // aNode  will be the new root 
  419.     CL_BTreeNodeHandle h = aNode->Handle();
  420.     aNode->_subtree [0] = root->Handle();
  421.     aNode->_isLeaf = FALSE;
  422.     aNode->_subtreeSize = root->_subtreeSize;
  423.     _SplitChild (aNode, 0, root);
  424.     _nodeSpace->ReturnNode (root);
  425.  
  426.     _nodeSpace->NewRoot (h);
  427.  
  428.     // Now add the key 
  429.     ans = _InsertNonFull (aNode, item);
  430.     return ans;
  431. }
  432.  
  433.  
  434.  
  435.  
  436.  
  437.  
  438.  
  439.  
  440.  
  441.  
  442. //
  443. // Private methods
  444. //
  445.  
  446. bool CL_GenericBTree::_InsertNonFull (CL_GenericBTreeNode* x, CL_VoidPtr item)
  447. {
  448.     short pos;
  449.     CL_GenericBTreeNode* y, *z = x;
  450.     CL_GenericBTreeNode* stack[MAX_BTREE_HEIGHT];
  451.     // We need a stack for updating the subtree sizes
  452.     short sp = 0;
  453.     bool found = FALSE;
  454.     
  455.     while (z && !(found = z->Search (item, pos))) {
  456.         stack[sp++] = z;
  457.     if (z->_isLeaf) break;
  458.         pos++;
  459.         y =  _nodeSpace->BorrowNode (z->_subtree[pos]);
  460.         if (y->_keyCount == 2*_order-1) {
  461.             _SplitChild (z, pos, y);
  462.             if (_comparator (item, z->_item[pos]) >= 0) {
  463.                 pos++;
  464.         _nodeSpace->ReturnNode (y);
  465.                 y = _nodeSpace->BorrowNode (z->_subtree[pos]);
  466.             }
  467.         }
  468.         z = y;
  469.     }
  470.  
  471.     if (!found) {
  472.         short n = z->_keyCount;
  473.         if (n > 0) {
  474.             z->ShiftRightAt (pos+1);
  475.             z->_item[pos+1] = item;
  476.         }
  477.         else 
  478.             z->_item[0] = item;
  479.         z->_keyCount++;
  480.         for (short i = 0; i < sp; i++) {
  481.             stack[i]->_subtreeSize++;
  482.         }
  483.     }
  484.     for (short i = 0; i < sp; i++) {
  485.         _nodeSpace->WriteBack (stack[i]);
  486.     }
  487.     return !found;
  488. }  
  489.  
  490.  
  491. void CL_GenericBTree::_SplitChild (CL_GenericBTreeNode* x,
  492.                                    short i, CL_GenericBTreeNode* y) 
  493. {
  494.     CL_GenericBTreeNode* z = _nodeSpace->MakeNode();
  495.     z->MoveSubNode (*y, _order, 0, _order-1);
  496.     z->_isLeaf = y->_isLeaf;
  497.     z->_keyCount = y->_keyCount = _order-1;
  498.     x->ShiftRightAt (i); 
  499.         // We shouldn't shift subtree[i], but it shouldn't matter
  500.     x->_subtree[i+1] = z->Handle();
  501.     x->_item [i] = y->_item [_order-1];
  502.     x->_keyCount++;
  503.  
  504.     // Recompute _subtreeSize for y and z
  505.     long size = 0;
  506.     if (!z->_isLeaf) {
  507.         for (short j = 0; j <= z->_keyCount; j++) {
  508.             CL_GenericBTreeNode* p = _nodeSpace->BorrowNode
  509.                 (z->_subtree[j]);
  510.             size += p->_subtreeSize;
  511.             _nodeSpace->ReturnNode (p);
  512.         }
  513.     }
  514.     size += z->_keyCount;
  515.     z->_subtreeSize = size;
  516.     y->_subtreeSize -= size+1;
  517.     _nodeSpace->WriteBack (z);
  518.     _nodeSpace->NodeModified (y);
  519.     _nodeSpace->NodeModified (x);
  520. }
  521.  
  522.  
  523.  
  524.  
  525.  
  526.  
  527.  
  528.  
  529.  
  530.  
  531.  
  532.  
  533.  
  534.  
  535.  
  536. CL_VoidPtr CL_GenericBTree::Remove (CL_VoidPtr key)
  537. {
  538.     CL_GenericBTreeNode* root = _nodeSpace->BorrowRoot();
  539.     CL_GenericBTreeNode* node = root;
  540.     CL_VoidPtr retVal;
  541.     
  542.     if (!node || node->_keyCount == 0) // Empty root
  543.         return (CL_VoidPtr) NULL;
  544.     if (node->_keyCount == 1 && node->_isLeaf) {
  545.         // Tree has only one key
  546.         if (_comparator (key, node->_item[0]) == 0) {
  547.             node->_keyCount = node->_subtreeSize = 0;
  548.             _nodeSpace->WriteBack (node);
  549.             return node->_item[0];
  550.         }
  551.         return NULL;
  552.     }
  553.     CL_GenericBTreeNode* stack[MAX_BTREE_HEIGHT];
  554.     // We need a stack for updating the subtree sizes
  555.     short sp = 0;
  556.     short index = 0;
  557.     bool found = FALSE;
  558.  
  559.     CL_GenericBTreeNode* q;
  560.     // stack[sp++] = node;
  561.     enum {SEARCHING, DESCENDING} state = SEARCHING;
  562.     DeleteActionEnum action;
  563.     while (1) {
  564.         if (state == SEARCHING) {
  565.             found = node->Search (key, index);
  566.             if (found)
  567.                 retVal = node->_item[index];
  568.         }
  569.         q = _DescendInto (node, index+1, action);
  570.         if (node == root &&  node->_keyCount == 0) {
  571.             _nodeSpace->DestroyNode (node);
  572.         }
  573.         else {
  574.             // We should add the root to the stack only if it wasn't
  575.             // already destroyed
  576.             stack [sp++] = node;
  577.         }            
  578.     if (!q) break;
  579.         // _DescendInto may have caused our key to be copied into q.
  580.         // If so, it would be copied into either q->_item[0] or
  581.         // q->_item[_order-1]  (because of a right or left rotation,
  582.         // respectively) or into q->_item[_order-1] (because of a merge).
  583.         if (found) {
  584.             state = DESCENDING;
  585.             if (action == RotateRight) {
  586.                 index = 0;
  587.             }
  588.             else if (action == RotateLeft || action == Merge) {
  589.                 index = _order-1;
  590.             }
  591.             else // No rotation or merge was done
  592.                 break;
  593.         }
  594.         node = q;
  595.     }
  596.     if (!found) {
  597.         // The key is not in the tree
  598.         for (short i = 0; i < sp; i++)
  599.             _nodeSpace->WriteBack(stack[i]);
  600.         return (CL_VoidPtr) NULL;
  601.     }
  602.     if (node->_isLeaf) {
  603.         // Key found in leaf
  604.         node->ShiftLeftAt (index+1);
  605.     }
  606.     else {
  607.         // The key is in an internal node, so we'll replace it by its
  608.         // inorder successor:
  609.         CL_GenericBTreeNode* p = q;
  610.         while (1) {
  611.             stack[sp++] = p;
  612.         if (p->_isLeaf) break;
  613.             p = _DescendInto (p, 0, action);
  614.         }
  615.         node->_item[index] = p->_item[0];
  616.         p->ShiftLeftAt(1);
  617.     }
  618.  
  619.     // Now update subtree sizes along search path
  620.     short i = 0;
  621.     if (stack[0]->_keyCount == 0) {
  622.         i = 1;
  623.     }
  624.     for (; i < sp; i++) {
  625.         stack[i]->_subtreeSize--;
  626.         _nodeSpace->WriteBack (stack[i]);
  627.     }
  628.     return retVal;
  629. }
  630.  
  631.  
  632. CL_GenericBTreeNode* CL_GenericBTree::_DescendInto
  633.     (CL_GenericBTreeNode* node, short subtreeIndex, DeleteActionEnum& action)
  634. {
  635.     CL_GenericBTreeNode* child, *sibling, *p;
  636.     child = _nodeSpace->BorrowNode (node->_subtree[subtreeIndex]);
  637.     if (!child || child->_keyCount >= _order) {
  638.         action = NoAction;
  639.         return child;
  640.     }
  641.     if (subtreeIndex == 0) {
  642.         sibling = _nodeSpace->BorrowNode (node->_subtree[1]);
  643.         p = _Adjust (node, 0, child, sibling, action);
  644.     }
  645.     else {
  646.         sibling = _nodeSpace->BorrowNode
  647.             (node->_subtree[subtreeIndex-1]);
  648.         p = _Adjust (node, subtreeIndex-1, sibling, child, action);
  649.     }
  650.     if (action != Merge)
  651.         _nodeSpace->ReturnNode (sibling);
  652.     return p;
  653. }
  654.  
  655.  
  656.  
  657. CL_GenericBTreeNode* CL_GenericBTree::_Adjust
  658.   (CL_GenericBTreeNode* node, short index,
  659.    CL_GenericBTreeNode* c0, CL_GenericBTreeNode* c1, DeleteActionEnum& action)
  660. {
  661.     assert ((c0 != NULL && c1 != NULL),
  662.             ("BTree::Adjust: assertion failed: line %d\n", __LINE__));
  663.     assert ((c0->_keyCount == _order-1 || c1->_keyCount == _order-1),
  664.             ("BTree::Adjust: assertion failed: line %d\n", __LINE__));
  665.             
  666.     if (c0->_keyCount == _order-1 && c1->_keyCount == _order-1) {
  667.         // Merge the two nodes
  668.         c0->_item[_order-1] = node->_item[index];
  669.         c0->MoveSubNode (*c1, 0, _order, _order-1);
  670.         c0->_keyCount = 2*_order-1;
  671.         c0->_subtreeSize += c1->_subtreeSize+1;
  672.         
  673.         _nodeSpace->DestroyNode (c1);
  674.         if (node->_keyCount > 1) {
  675.             node->ShiftLeftAt (index+1);
  676.             node->_subtree[index] = c0->Handle();
  677.         }
  678.         else {
  679.             _nodeSpace->NewRoot (c0->Handle());
  680.         }
  681.         action = Merge;
  682.         return c0;
  683.     }
  684.     if (c0->_keyCount >= _order) {
  685.         // Rotate right
  686.         c1->ShiftRightAt (0);
  687.         c1->_item[0] = node->_item[index];
  688.         c1->_subtree[0] = c0->_subtree[c0->_keyCount];
  689.         node->_item[index] = c0->_item[c0->_keyCount-1];
  690.         c0->_keyCount--;
  691.         c1->_keyCount++;
  692.         CL_GenericBTreeNode* p = _nodeSpace->BorrowNode
  693.             (c1->_subtree[0]);
  694.         long xfr = (p) ? p->_subtreeSize+1 : 1;
  695.         c1->_subtreeSize += xfr;
  696.         c0->_subtreeSize -= xfr;
  697.         if (p)
  698.             _nodeSpace->ReturnNode (p);
  699.         _nodeSpace->NodeModified (c0);
  700.         action = RotateRight;
  701.         return c1;
  702.     }
  703.     else {
  704.         // c1->keyCount >= order, so rotate left
  705.         c0->_item[_order-1] = node->_item[index];
  706.         c0->_subtree[_order] = c1->_subtree[0];
  707.         c0->_keyCount++;
  708.         node->_item[index] = c1->_item[0];
  709.         CL_GenericBTreeNode* p = _nodeSpace->BorrowNode
  710.             (c0->_subtree[_order]);
  711.         long xfr = (p) ? p->_subtreeSize+1 : 1;
  712.         c1->_subtreeSize -= xfr;
  713.         c0->_subtreeSize += xfr;
  714.         c1->ShiftLeftAt(1);
  715.         if (p)
  716.             _nodeSpace->ReturnNode (p);
  717.         _nodeSpace->NodeModified (c1);
  718.         action = RotateLeft; 
  719.         return c0;
  720.     }
  721. }
  722.  
  723.             
  724.         
  725.     
  726.  
  727.  
  728. CL_VoidPtr CL_GenericBTree::ExtractMin ()
  729. {
  730.     CL_GenericBTreeNode* stack[MAX_BTREE_HEIGHT];
  731.     // We need a stack for updating the subtree sizes
  732.     short sp = 0;
  733.     CL_GenericBTreeNode* node = _nodeSpace->BorrowRoot();
  734.     if (node->_keyCount == 0)
  735.         return NULL;
  736.     stack[sp++] = node;
  737.     DeleteActionEnum action;
  738.     while (!node->_isLeaf) {
  739.         node = _DescendInto (node, 0, action);
  740.         stack[sp++] = node;
  741.     }
  742.     CL_VoidPtr item = node->_item[0];
  743.     node->ShiftLeftAt(1);
  744.     for (short i = 0; i < sp; i++) {
  745.         stack[i]->_subtreeSize--;
  746.         _nodeSpace->WriteBack (stack[i]);
  747.     }
  748.     return item;
  749. }
  750.  
  751.  
  752.  
  753.  
  754. ///////////////////////////////////////////////////////////////////
  755. //                  BTreeIterator methods                        //
  756. ///////////////////////////////////////////////////////////////////
  757.  
  758.  
  759.  
  760.  
  761.  
  762. // The  BTreeIterator  remembers and   manipulates  the  search path  to  a
  763. // particular key in the tree.
  764. // 
  765. // A search path is a sequence of pairs of the form <node#, subtree#>, with
  766. // the  first pair <root,  subtree#> and the   last pair being  of the form
  767. // <node#,  key#>. It completely   specifies the path   from the root  to a
  768. // particular key in the tree.
  769. //
  770. // The Iterator maintains the invariant that the path specified by the
  771. // current values in the array represents the path to the key that was
  772. // returned by the most recent call to Next().
  773.  
  774.  
  775. struct PathStruct {
  776. public:
  777.     CL_BTreeNodeHandle _handle;
  778.     short              _indexInNode;
  779. };
  780.  
  781.  
  782. CL_GenericBTreeIterator::CL_GenericBTreeIterator
  783. (const CL_GenericBTree& tree) :_tree (tree)
  784. {
  785.     _path = new PathStruct [MAX_BTREE_HEIGHT];
  786.     _length = 0;
  787.     Reset();
  788. }
  789.  
  790. CL_GenericBTreeIterator::CL_GenericBTreeIterator
  791.     (const CL_GenericBTreeIterator& itr)
  792. : _tree (itr._tree)
  793. {
  794.     _path = new PathStruct [MAX_BTREE_HEIGHT];
  795.     if (_path) {
  796.         _length = itr._length;
  797.         for (register short i = 0; i < _length; i++)
  798.             ((PathStruct*) _path)[i] = ((PathStruct*) itr._path)[i];
  799.     }
  800.     else
  801.         _length = 0;
  802.     _index = itr._index;
  803. }
  804.  
  805.  
  806. CL_GenericBTreeIterator::~CL_GenericBTreeIterator()
  807. {
  808.     if (_path)
  809.         delete [] (PathStruct*) _path;
  810. }
  811.  
  812.  
  813.  
  814. void CL_GenericBTreeIterator::BeginFrom (CL_VoidPtr item)
  815. {
  816.     short pos;
  817.     bool found;
  818.  
  819.     if (!_path) // Memory allocation failed?
  820.         return;
  821.     _length = 0;
  822.     _index  = -1;
  823.     if (_tree.Size() <= 0)
  824.         return;
  825.     PathStruct* path = (PathStruct*) _path;
  826.  
  827.     register CL_BTreeNodeSpace* space =  _tree.NodeSpace();
  828.     CL_BTreeNodeHandle tmp_handle = space->RootHandle ();
  829.     CL_GenericBTreeNode* tmp_ptr, *p;
  830.     do {
  831.         tmp_ptr = space->BorrowNode (tmp_handle);
  832.         found = tmp_ptr->Search (item, pos);
  833.         path[_length]._handle = tmp_handle;
  834.         _index += path[_length]._indexInNode = found ? pos : pos+1;
  835.         _length++;
  836.     if (tmp_ptr->_isLeaf) break;
  837.         for (register long i = 0; i <= pos; i++) {
  838.             CL_GenericBTreeNode* p = space->BorrowNode
  839.                 (tmp_ptr->_subtree[i]);
  840.             _index += p->_subtreeSize;
  841.             space->ReturnNode (p);
  842.         }
  843.     if (found) break;
  844.         tmp_handle = tmp_ptr->_subtree [pos+1];
  845.         space->ReturnNode (tmp_ptr);
  846.     } while (1);
  847.     if (!tmp_ptr->_isLeaf) {
  848.         // We're in an internal node; so move down to the leaf
  849.         tmp_handle = tmp_ptr->_subtree[pos];
  850.         do {
  851.             p = space->BorrowNode (tmp_handle);
  852.             path[_length]._handle = tmp_handle;
  853.             path[_length]._indexInNode = p->_keyCount;
  854.             _length++;
  855.             tmp_handle = p->_subtree[p->_keyCount]; // Rightmost subtree
  856.             space->ReturnNode (p);
  857.         } while (tmp_handle);
  858.     }
  859.     path[_length-1]._indexInNode--;  // So that the first call to Next gives
  860.                                      // the nearest key >= the given key
  861.     space->ReturnNode (tmp_ptr);
  862. }
  863.  
  864.  
  865.  
  866.  
  867.  
  868. void CL_GenericBTreeIterator::Reset ()
  869. {
  870.     if (!_path) // Memory allocation failed?
  871.         return;
  872.     _length = 1;
  873.     PathStruct* path = (PathStruct*) _path;
  874.     path[0]._handle = _tree.NodeSpace()->RootHandle();
  875.     path[0]._indexInNode = -1;
  876.     _index = -1;
  877. }
  878.  
  879.  
  880.  
  881.  
  882.  
  883. CL_VoidPtr CL_GenericBTreeIterator::Next ()
  884. {
  885.     if (_index >= _tree.Size())
  886.         return NULL;
  887.     CL_VoidPtr retVal;
  888.     
  889.     if (!_path || _length == 0)
  890.         return NULL;
  891.     PathStruct* path = (PathStruct*) _path;
  892.     CL_GenericBTreeNode* node;
  893.     short  ndx = path[_length-1]._indexInNode;
  894.     register CL_BTreeNodeSpace* space =  _tree.NodeSpace();
  895.     node = space->BorrowNode (path[_length-1]._handle);
  896.  
  897.     _index++;
  898.     if (! node->_isLeaf) {
  899.         // Move to the next right subtree
  900.         path[_length-1]._indexInNode++;
  901.         CL_BTreeNodeHandle handle = node->_subtree [ndx+1];
  902.         while (!node->_isLeaf) {
  903.             path[_length]._handle = handle;
  904.             path[_length]._indexInNode = 0;
  905.             _length++;
  906.             space->ReturnNode (node);
  907.             node = space->BorrowNode (handle);
  908.             handle = node->_subtree[0];
  909.         };
  910.         retVal = node->_item[0];
  911.         space->ReturnNode (node);
  912.         return retVal;
  913.     }
  914.     
  915.     // We're in a leaf
  916.     if (ndx >= node->_keyCount-1) {
  917.             // We're at far right of the leaf, so move up
  918.         do {
  919.             _length--;
  920.             space->ReturnNode (node);
  921.         if (_length <= 0) break;
  922.             node = space->BorrowNode (path[_length-1]._handle);
  923.             ndx = path[_length-1]._indexInNode;
  924.         } while (ndx >= node->_keyCount);
  925.         if (_length) {
  926.             retVal = node->_item[ndx];
  927.             space->ReturnNode (node);
  928.         }
  929.         else
  930.             retVal = NULL;
  931.         return retVal;
  932.     }
  933.     // We're in the middle or at left end of a leaf
  934.     path[_length-1]._indexInNode++;
  935.     retVal = node->_item[path[_length-1]._indexInNode];
  936.     space->ReturnNode (node);
  937.     return retVal;
  938. }
  939.  
  940.  
  941.  
  942.  
  943. bool CL_GenericBTreeIterator::More ()
  944. {
  945.     return _index < _tree.Size()-1;
  946. }
  947.  
  948.  
  949.  
  950.