home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / gbtree.h < prev    next >
C/C++ Source or Header  |  1995-04-08  |  19KB  |  524 lines
  1.  
  2.  
  3. #ifndef _btree_h_ /* Sun Jan 17 20:31:53 1993 */
  4. #define _btree_h_
  5.  
  6.  
  7.  
  8.  
  9.  
  10. /*
  11.  *
  12.  *          Copyright (C) 1994, M. A. Sridhar
  13.  *  
  14.  *
  15.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  16.  *     to copy, modify or distribute this software  as you see fit,
  17.  *     and to use  it  for  any  purpose, provided   this copyright
  18.  *     notice and the following   disclaimer are included  with all
  19.  *     copies.
  20.  *
  21.  *                        DISCLAIMER
  22.  *
  23.  *     The author makes no warranties, either expressed or implied,
  24.  *     with respect  to  this  software, its  quality, performance,
  25.  *     merchantability, or fitness for any particular purpose. This
  26.  *     software is distributed  AS IS.  The  user of this  software
  27.  *     assumes all risks  as to its quality  and performance. In no
  28.  *     event shall the author be liable for any direct, indirect or
  29.  *     consequential damages, even if the  author has been  advised
  30.  *     as to the possibility of such damages.
  31.  *
  32.  */
  33.  
  34.  
  35.  
  36.  
  37. // There are four classes related to the generic B-tree:
  38. // \par\begin{tabular}{lp{3.5in}}
  39. //   CL_GenericBTree&       a class that encapsulates B-tree algorithms\\
  40. //   CL_GenericBTreeNode&   which defines the structure  of a node in a
  41. //                          B-tree\\
  42. //   CL_GenericBTreeIterator& an object that  allows  inspection  of  the
  43. //                          items in a B-tree in ascending order\\
  44. //   CL_BTreeNodeSpace&     which  defines  an  object  for  managing a
  45. //                          repository of B-tree nodes\\
  46. // \end{tabular}\par
  47. // The  algorithms implemented  here  assume that items   are stored in the
  48. // internal nodes  as  well as in  the leaves;  this  is therefore not  the
  49. // B+-tree (the one in which items are stored only at the leaves).
  50. // 
  51. // To enhance reusability, the B-tree is viewed as operating on a NodeSpace
  52. // object. The latter is an object that manages the  space of nodes for the
  53. // tree via {\it node  handles.}  The   B-tree's  methods  do  not make any
  54. // assumptions about the NodeSpace other than the  public protocol; thus it
  55. // is possible to create in-memory or disk-based (and even shared-memory or
  56. // remote-server-based)   B-trees  simply   by using   different  NodeSpace
  57. // objects. The B-tree methods access the nodes via a BTreeNodeHandle.
  58. //
  59. // The generic B-tree does {\it not\/} own the objects that the pointers
  60. // point to, and therefore does not delete them when it is destroyed. The
  61. // BTreeIterator can be used to iterate over the tree's contents and
  62. // destroy pointed-to objects.
  63.  
  64.  
  65. //  Revision history:
  66. //
  67. //      M. A. Sridhar          April 28th, 1993
  68. //
  69. //      Completely redone:     October 25, 1993 -- MAS
  70. //
  71.  
  72.  
  73. #ifdef __GNUC__
  74. #pragma interface
  75. #endif
  76.  
  77.  
  78. #include "base/cmparatr.h"
  79.  
  80.  
  81. typedef long CL_BTreeNodeHandle;
  82.  
  83. class CL_EXPORT CL_BTreeNodeSpace;
  84. class CL_EXPORT CL_GenericBTreeIterator;
  85. class CL_EXPORT CL_GenericBTreeNode;
  86.  
  87.  
  88. class CL_GenericBTree {
  89.  
  90. public:
  91.  
  92.  
  93.     // --------------------- Construction and destruction ------------------
  94.  
  95.     
  96.     CL_GenericBTree (CL_AbstractComparator& cmp,
  97.                      short order = 2, CL_BTreeNodeSpace* space = NULL);
  98.     // Create a new B-tree of given order. Duplicate items are not
  99.     // allowed. The NodeSpace may by created by the derived class and
  100.     // passed to this constructor; if it is NULL, a default in-memory node
  101.     // space is created. If the derived class passes a non-null NodeSpace,
  102.     // it is the responsibility of the derived class to destroy the
  103.     // NodeSpace object.
  104.     //
  105.     // The third parameter specifies the comparator to be used when
  106.     // comparing two cells.
  107.     //
  108.     // The order must be at least 2; anything
  109.     // less than 2 is taken to be 2.
  110.     
  111.  
  112.     virtual ~CL_GenericBTree ();
  113.     // Destructor.
  114.  
  115.  
  116.     // ----------------------- Search and related methods ------------------
  117.  
  118.     CL_BTreeNodeSpace* NodeSpace () const
  119.         {return _nodeSpace;};
  120.     // Return the NodeSpace used by this tree.
  121.  
  122.     CL_AbstractComparator& Comparator () const {return _comparator;};
  123.     // Return a reference to the comparator used by this tree.
  124.     
  125.     virtual CL_VoidPtr Find (CL_VoidPtr item) const;
  126.     // Search the tree for the given item. Return a pointer to the
  127.     // found item if the search was successful, as the function value. If
  128.     // the search fails, the return value is NULL.
  129.  
  130.     CL_VoidPtr Smallest () const {return ItemWithRank (0);};
  131.     // Find and return the minimum item. If the tree is empty,
  132.     // the null pointer is returned. The implementation simply returns the
  133.     // value {\tt ItemWithRank (0)}.
  134.  
  135.     CL_VoidPtr Largest () const {return ItemWithRank (Size()-1);};
  136.     // Find and return the maximum item. If the tree is empty,
  137.     // the null pointer is returned. The implementation simply returns the
  138.     // value {\tt ItemWithRank (Size()-1)}.
  139.  
  140.  
  141.     virtual CL_VoidPtr ItemWithRank (long i) const;
  142.     // Given an index $i$ between 0 and Size()-1, return the element of rank
  143.     // $i$, i.e., the element that has $i$ elements less than it in the tree.
  144.     // If $i \le 0$, this returns the smallest element, and if $i \ge {\tt
  145.     // Size()}$, this returns the largest element. If the tree is empty,
  146.     // the null value of the base type is returned. The implementation
  147.     // examines only the nodes on the path from the root to the one
  148.     // containing the key sought, and therefore takes no more than $\log
  149.     // n$ time steps with $n$ keys in the tree.
  150.     //
  151.     //   Note that it is possible to iterate through the elements of the tree
  152.     // via calls to this method, varying the index from 0 to Size()-1;
  153.     // however, this is much less efficient than using the BTreeIterator.
  154.  
  155.     virtual long RankOf (CL_VoidPtr p) const;
  156.     // Return the number of elements in the tree that are less than the
  157.     // parameter.
  158.     
  159.     virtual long Size () const;
  160.     // Return the size of the tree (number of items currently present).
  161.     // The implementation needs constant time regardless of tree size.
  162.  
  163.  
  164.     // ------------------------ Modification ------------------------------
  165.  
  166.     virtual bool Add  (CL_VoidPtr item);
  167.     // Add the item to the tree. Return TRUE if successfully added,
  168.     // FALSE if the item was already in the tree.
  169.  
  170.     virtual CL_VoidPtr Remove (CL_VoidPtr item);
  171.     // Remove the specified item from the tree. Return NULL if the
  172.     // item was not found in the tree, and the found item otherwise. The
  173.     // implementation needs (in the worst case) two passes over the path
  174.     // to the key, and so takes $2\log n$ time steps with $n$ keys in the
  175.     // tree. It also coalesces any non-full nodes along the path from the
  176.     // root to the deleted key.
  177.  
  178.     virtual CL_VoidPtr ExtractMin ();
  179.     // Remove and return the smallest item in the tree. Return the null
  180.     // pointer if the tree is empty.
  181.  
  182.  
  183.     
  184.     // --------------------- End public protocol -----------------------
  185.  
  186.  
  187.         
  188. protected:
  189.  
  190.     //------------------- Protected helper methods ---------------------
  191.  
  192.  
  193.     enum DeleteActionEnum {NoAction, RotateLeft, RotateRight, Merge};
  194.     
  195.     bool                 _InsertNonFull (CL_GenericBTreeNode* n1,
  196.                                          CL_VoidPtr p);
  197.     
  198.     void                 _SplitChild (CL_GenericBTreeNode* n,
  199.                                       short i, CL_GenericBTreeNode*);
  200.  
  201.     CL_GenericBTreeNode* _DescendInto (CL_GenericBTreeNode*, short,
  202.                                        DeleteActionEnum&);
  203.  
  204.     CL_GenericBTreeNode* _Adjust (CL_GenericBTreeNode* node, short index,
  205.                                   CL_GenericBTreeNode* c0,
  206.                                   CL_GenericBTreeNode* c1, DeleteActionEnum&);
  207.  
  208.     // --------------------- Friend declarations --------------------
  209.  
  210.     //    friend CL_GenericBTreeNode;
  211.  
  212.     
  213.     //------------ Instance data -----------------------------
  214.     short                   _order;
  215.     CL_BTreeNodeSpace*      _nodeSpace;
  216.     CL_AbstractComparator&  _comparator;
  217.  
  218. private:
  219.     bool  _ownNodeSpace;
  220. };
  221.  
  222.  
  223.  
  224.  
  225. // This class encapsulates a single node of the B-tree.
  226.  
  227.  
  228. class CL_GenericBTreeNode {
  229.  
  230. public:
  231.  
  232.     // ------------------ Access and Manipulation -----------------
  233.  
  234.     long Size() const {return _keyCount;};
  235.     // Return the number of items in this node.
  236.  
  237.     CL_VoidPtr Item (short i) const {return _item[i];};
  238.     // Return the i-th item.  The value i must be such that
  239.     // $0 \le i < {\tt Size()}$.
  240.  
  241.     CL_BTreeNodeHandle Subtree (short i) const {return _subtree[i];};
  242.     // Return the handle of the i-th subtree. The value i must be such that
  243.     // $0 \le i \le {\tt Size()}$.
  244.  
  245.     long SubtreeSize() const {return _subtreeSize;};
  246.     // Return the number of keys in the subtree rooted at this node. This
  247.     // method consults an instance variable, and therefore takes constant
  248.     // time; it does not need to  traverse the subtree.
  249.     
  250.     CL_BTreeNodeHandle Handle() {return _handle;};
  251.     // Return a reference to the handle for this node.
  252.  
  253.     CL_BTreeNodeSpace* NodeSpace () const {return _nodeSpace;};
  254.     // Return the NodeSpace in which this node lives.
  255.     
  256.     virtual bool Search (CL_VoidPtr key, short& position) const;
  257.     // Search the node for the given key; return greatest $i$ such that
  258.     // {\tt key[i] <= key}. Return TRUE if {\tt key[i] == key}, FALSE
  259.     // otherwise.
  260.  
  261.     virtual void ShiftRightAt (short pos, short amount = 1);
  262.     // Shift all the keys and subtrees, beginning at position pos,
  263.     // right by the given amount. Note that the subtree to the left of
  264.     // key[pos] is {\it also\/} moved.
  265.  
  266.     virtual void ShiftLeftAt (short pos, short amount = 1);
  267.     // Shift all the keys and subtrees, beginning at position pos,
  268.     // left by the given amount. Note that the subtree to the left of
  269.     // key[pos] is {\it also\/} moved.
  270.  
  271.     virtual void MoveSubNode (const CL_GenericBTreeNode& x, short pos,
  272.                       short our_pos, short nkeys);
  273.     // MoveSubNode: Move {\it nkeys\/} keys, and their left and right
  274.     // subtrees, beginning from position pos in node $x$ into ourselves
  275.     // beginning at position {\it our_pos}.
  276.  
  277.  
  278.     // --------------------- End public protocol -----------------------
  279.  
  280.  
  281. protected:
  282.  
  283.     CL_AbstractComparator& _cmp;      // Comparator must be initialized
  284.                                       // BEFORE NodeSpace is initialized
  285.     CL_BTreeNodeSpace*   _nodeSpace;  
  286.     CL_BTreeNodeHandle* _subtree;     // Pointer to array of subtree handles
  287.     CL_VoidPtr*         _item;        // Pointer to array of items
  288.     short               _keyCount;    // # keys in node
  289.     bool                _isLeaf;      // Is this node a leaf?
  290.     long                _subtreeSize; // # keys in subtree rooted at this node
  291.  
  292.     CL_BTreeNodeHandle  _handle;      // Our handle
  293.     short               _order;
  294.  
  295.     friend CL_GenericBTree;
  296.     friend CL_GenericBTreeIterator;
  297.     friend CL_BTreeNodeSpace;
  298.  
  299.     // ---------------- Construction and destruction ---------------
  300.     
  301.     CL_GenericBTreeNode (short order, CL_BTreeNodeSpace* space,
  302.                          CL_AbstractComparator& cmp);
  303.     // Constructor: create a node of the B-tree with given order.
  304.  
  305.     virtual ~CL_GenericBTreeNode();
  306.     // Destructor.
  307.  
  308. };
  309.  
  310.  
  311.  
  312.  
  313. // The NodeSpace is the space in which tree nodes are stored. Nodes in
  314. // this space are accessed via handles encapsulated by the
  315. // SubTreeHandle class. The NodeSpace functions as a kind of "node
  316. // library" from which nodes can be "borrowed" and "returned."
  317. // Borrowed nodes can be modified, in which case the NodeSpace must be
  318. // informed of the modification via the NodeModified method.
  319. //
  320. // The BTree class assumes that the NodeSpace class provides the
  321. // following primitives:
  322. // \par\begin{tabular}{lp{3.5truein}}
  323. //    RootHandle, & which returns the handle of the root of the
  324. //                  tree \\
  325. //    Root, &       which returns a raw C++ pointer to the root \\
  326. //    NewRoot, &    which modifies the root handle\\
  327. //    CreateNode, & which creates a new node in the NodeSpace and
  328. //                  returns a handle to it. \\
  329. //    BorrowNode, & which returns a raw C++ pointer to the node
  330. //                  specified by the given handle. This pointer
  331. //                  points to space owned by NodeSpace. \\
  332. //    ReturnNode, & which informs the NodeSpace that the caller
  333. //                  done with the node \\
  334. //    NodeModified,&which tells the NodeSpace that the caller
  335. //                  has modified the specified node (but is not
  336. //                  necessarily done with that node yet) \\
  337. //    DestroyNode,& which destroys the given node, and invalidates
  338. //                  its handle. \\
  339. // \end{tabular}\par
  340. // The default implementation is for the node space on the heap, so that
  341. // translation between node handles and pointers is trivial.
  342.  
  343.  
  344. class CL_BTreeNodeSpace  {
  345.  
  346. public:
  347.     CL_BTreeNodeSpace (short order, const CL_GenericBTree& tree,
  348.                        CL_AbstractComparator& cmp);
  349.     // Construct a new NodeSpace.
  350.  
  351.     virtual ~CL_BTreeNodeSpace () {};
  352.     
  353.     // --------------- Essential (core) functions ----------------
  354.     
  355.     virtual CL_BTreeNodeHandle   RootHandle () const = 0;
  356.  
  357.     virtual void                 NewRoot (CL_BTreeNodeHandle h) = 0;
  358.     
  359.     virtual CL_BTreeNodeHandle   CreateNode () = 0;
  360.  
  361.     virtual void                 DestroyNode (CL_GenericBTreeNode*) = 0;
  362.  
  363.     virtual CL_GenericBTreeNode* BorrowNode (CL_BTreeNodeHandle h) const = 0;
  364.     //  Return a null pointer if the handle h is zero.
  365.     
  366.     virtual void                 ReturnNode (CL_GenericBTreeNode* ) const = 0;
  367.     
  368.     virtual void                 NodeModified (CL_GenericBTreeNode*) = 0;
  369.     
  370.  
  371.     // -------------------- Convenience functions --------------------
  372.     
  373.     CL_GenericBTreeNode* BorrowRoot () const
  374.         {return BorrowNode (RootHandle());};
  375.     // Convenience function to borrow the root of the tree.
  376.  
  377.     void WriteBack (CL_GenericBTreeNode* node)
  378.         { NodeModified (node); ReturnNode (node);};
  379.     // Convenience function that calls {\small\tt NodeModified} and then
  380.     // {\small\tt ReturnNode}.
  381.  
  382.     CL_GenericBTreeNode*  MakeNode () 
  383.         { return BorrowNode (CreateNode());};
  384.     // Convenience function that creates a new node and then borrows it.
  385.  
  386.     virtual void DestroyItem (CL_VoidPtr) const {};
  387.     // Destroy the item pointed to by the parameter. This method is called
  388.     // for each item of a node when the node is being destroyed. The default
  389.     // implementation does nothing; derived classes may override this method.
  390.  
  391.     // --------------------- End public protocol -----------------------
  392.  
  393. protected:
  394.     short _order;
  395.     CL_AbstractComparator& _cmp;    // Declare _cmp before _tree, to
  396.                                     // initialize in correct order
  397.     const CL_GenericBTree& _tree;
  398.  
  399.     virtual CL_GenericBTreeNode* _BuildNode () const
  400.         {return new CL_GenericBTreeNode (_order, (CL_BTreeNodeSpace*)
  401.                                          this, _cmp);};
  402.     // Create an empty node and return it. This method is
  403.     // meant for use by derived classes, since the BTreeNode constructor is
  404.     // protected.
  405.     
  406.     virtual void _Destroy (CL_GenericBTreeNode* node) const;
  407.     // Call {\tt delete} on the parameter. The default implementation
  408.     // invokes DestroyItem on each contained item, and then destroys the
  409.     // node. This method is
  410.     // meant for use by derived classes, since the BTreeNode destructor is
  411.     // protected.
  412.  
  413.     virtual void _SetHandle (CL_GenericBTreeNode& node,
  414.                              CL_BTreeNodeHandle h) const
  415.         {node._handle = h;};
  416.     // Set the handle of {\tt node} to {\tt h}. This method is
  417.     // meant for use by derived classes.
  418.     
  419.  
  420. };
  421.  
  422.  
  423.  
  424. inline CL_BTreeNodeSpace::CL_BTreeNodeSpace
  425.     (short order, const CL_GenericBTree& tree, CL_AbstractComparator& cmp)
  426. : _order (order), _cmp (cmp), _tree (tree)
  427. {
  428. };
  429.  
  430.  
  431.  
  432.  
  433. class CL_GenericBTreeIterator {
  434.  
  435. public:
  436.     CL_GenericBTreeIterator (const CL_GenericBTree& t);
  437.     // Constructor: create a BTreeIterator for the given tree t.
  438.  
  439.     CL_GenericBTreeIterator (const CL_GenericBTreeIterator& itr);
  440.     // Copy constructor. The copy inspects the same B-tree as {\tt itr}, and
  441.     // (unless reset) begins  its iteration at the item at which {\tt itr}
  442.     // is currently positioned.
  443.     
  444.     virtual ~CL_GenericBTreeIterator();
  445.     // Destructor.
  446.     
  447.     void Reset();
  448.     // Reset the iterator to the leftmost (smallest) item.
  449.     
  450.     void BeginFrom (CL_VoidPtr p);
  451.     // Begin the iteration from the given item (or the one immediately
  452.     // larger, if the given item isn't in the tree).
  453.     
  454.     bool More();
  455.     // Tell whether there are more items in the iteration.
  456.     
  457.     CL_VoidPtr Next();
  458.     // Return the next item in the iteration sequence. Return the NULL
  459.     // pointer if no more items.
  460.  
  461.     long CurrentRank () const {return _index;};
  462.     // Return the rank of the element that was returned by the most recent
  463.     // call to Next().
  464.     
  465.     // --------------------- End public protocol -----------------------
  466.  
  467.  
  468. protected:
  469.     CL_VoidPtr                  _path;      // Stack containing path to
  470.                                             // current element
  471.     short                       _length;    // Length of stack
  472.     long                        _index;     // Rank of  element most recently
  473.                                             // returned by Next
  474.     const      CL_GenericBTree& _tree;      // The tree being inspected
  475.     
  476. };
  477.  
  478.  
  479.  
  480.  
  481.  
  482.  
  483.  
  484.  
  485.  
  486.  
  487. class CL_EXPORT CL_HeapBTreeNodeSpace: public CL_BTreeNodeSpace {
  488.  
  489. public:
  490.     CL_HeapBTreeNodeSpace (short order, const CL_GenericBTree& tree,
  491.                            CL_AbstractComparator& cmp);
  492.  
  493.     ~CL_HeapBTreeNodeSpace ();
  494.     
  495.     virtual CL_BTreeNodeHandle RootHandle () const { return _root; };
  496.  
  497.     virtual void NewRoot (CL_BTreeNodeHandle h) { _root = h; };
  498.     
  499.     virtual CL_BTreeNodeHandle CreateNode ();
  500.  
  501.     virtual CL_GenericBTreeNode* BorrowNode (CL_BTreeNodeHandle h) const;
  502.     
  503.     virtual void ReturnNode (CL_GenericBTreeNode* ) const;
  504.     
  505.     virtual void NodeModified (CL_GenericBTreeNode*) {};
  506.     
  507.     virtual void DestroyNode (CL_GenericBTreeNode* node);
  508.  
  509.     // --------------------- End public protocol -----------------------
  510.  
  511. protected:
  512.     CL_BTreeNodeHandle _root;
  513.  
  514.     void               _DestroySubtree (CL_BTreeNodeHandle h);
  515.     
  516. };
  517.  
  518.  
  519.  
  520.  
  521. #endif
  522.  
  523.  
  524.