home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / tbtree.h < prev    next >
C/C++ Source or Header  |  1995-04-08  |  8KB  |  207 lines
  1.  
  2.  
  3. #ifndef _tbtree_h_ /* Sun May 15 10:56:04 1994 */
  4. #define _tbtree_h_
  5.  
  6. /*
  7.  *
  8.  *          Copyright (C) 1994, M. A. Sridhar
  9.  *  
  10.  *
  11.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  12.  *     to copy, modify or distribute this software  as you see fit,
  13.  *     and to use  it  for  any  purpose, provided   this copyright
  14.  *     notice and the following   disclaimer are included  with all
  15.  *     copies.
  16.  *
  17.  *                        DISCLAIMER
  18.  *
  19.  *     The author makes no warranties, either expressed or implied,
  20.  *     with respect  to  this  software, its  quality, performance,
  21.  *     merchantability, or fitness for any particular purpose. This
  22.  *     software is distributed  AS IS.  The  user of this  software
  23.  *     assumes all risks  as to its quality  and performance. In no
  24.  *     event shall the author be liable for any direct, indirect or
  25.  *     consequential damages, even if the  author has been  advised
  26.  *     as to the possibility of such damages.
  27.  *
  28.  */
  29.  
  30.  
  31.  
  32. // This is a template-based, type-safe version of the Generic B-tree.
  33. // Methods for this class are provided in the header file, so that
  34. // type-safe instantiations of the {\small\tt CL_BTree} can be constructed
  35. // with arbitrary base types. The lengths of these methods, however, are
  36. // very small, so that no significant overhead is incurred.
  37. //
  38. // The ItemType class,  which  is the type  parameter for the BTree and
  39. // the BTreeIterator, must support the  assignment operator and the comparison
  40. // operators.  An ItemType may be  a composite object,  such as a key-value
  41. // pair; it  is then the responsibility of  the ItemType  class to use only
  42. // the key part for comparison, but both key and value for copying.
  43.  
  44.  
  45.  
  46. #ifdef __GNUC__
  47. #pragma interface
  48. #endif
  49.  
  50.  
  51.  
  52. #include "base/gbtree.h"
  53. #include "base/iterator.h"
  54.  
  55. template <class ItemType> class CL_BTreeIterator;
  56.  
  57. template <class ItemType>
  58. class CL_EXPORT CL_BTree: public CL_Object {
  59.  
  60. public:
  61.     CL_BTree (short order = 2, CL_BTreeNodeSpace* space = NULL);
  62.     // Create a B-tree with given order. This must be at least 2; anything
  63.     // less than 2 is taken to be 2. A NodeSpace may be specified in the
  64.     // second parameter; if it is specified, the tree does not take
  65.     // responsibility for it, and the caller must guarantee that it exists
  66.     // for the lifetime of the tree and is destroyed afterwards. If no
  67.     // NodeSpace is specified, a default in-memory NodeSpace is used.
  68.  
  69.     CL_BTree (CL_AbstractComparator& cmp, short order = 2,
  70.               CL_BTreeNodeSpace* space = NULL);
  71.     // Alternate constructor: use the given comparator. The comparator and
  72.     // NodeSpace are assumed to be "borrowed" from the user of this object.
  73.     
  74.     ~CL_BTree ();
  75.     // Destructor.
  76.     
  77.     //
  78.     // ----------------------- Search and related methods ------------------
  79.  
  80.     virtual const ItemType& Find (const ItemType& item) const;
  81.     // Search the tree for the given item. Return the
  82.     // found item if the search was successful, as the function value. If
  83.     // the search fails, the return value is the null value of the ItemType.
  84.  
  85.  
  86.     const ItemType& Smallest () const {return ItemWithRank (0);};
  87.     // Find and return the minimum item. If the tree is empty,
  88.     // the null value is returned.
  89.  
  90.     const ItemType& Largest () const {return ItemWithRank (Size()-1);};
  91.     // Find and return the maximum item. If the tree is empty,
  92.     // the null value is returned.
  93.  
  94.     virtual const ItemType& ItemWithRank (long i) const;
  95.     // Given an index $i$ between 0 and Size()-1, return the element of rank
  96.     // $i$, i.e., the element that has $i$ elements less than it in the tree.
  97.     // If $i \le 0$, this returns the smallest element, and if $i \ge {\tt
  98.     // Size()}$, this returns the largest element. If the tree is empty,
  99.     // the null value of the base type is returned. The implementation
  100.     // examines only the nodes on the path from the root to the one
  101.     // containing the key sought, and therefore takes no more than $\log
  102.     // n$ time steps with $n$ keys in the tree.
  103.     //
  104.     // Note that it is possible to iterate through the elements of the tree
  105.     // via calls to this method, varying the index from 0 to Size()-1;
  106.     // however, this is much less efficient than using the BTreeIterator.
  107.     
  108.     virtual long RankOf (const ItemType& p) const;
  109.     // Return the number of elements in the tree that are less than the
  110.     // parameter.
  111.     
  112.     virtual long Size () const;
  113.     // Return the size of the tree (number of items currently present).
  114.     // The implementation needs constant time regardless of tree size.
  115.  
  116.  
  117.     // ------------------------ Modification ------------------------------
  118.  
  119.     virtual bool Add  (const ItemType& item);
  120.     // Add the item to the tree. Return TRUE if successfully added,
  121.     // FALSE if the item was already in the tree.
  122.  
  123.     virtual ItemType Remove (const ItemType& item);
  124.     // Remove the specified item from the tree. Return the removed item if
  125.     // it was found in the tree, and the null value otherwise. The
  126.     // implementation needs (in the worst case) two passes over the path
  127.     // to the key, and so takes $2\log n$ time steps with $n$ keys in the
  128.     // tree. It also coalesces any non-full nodes along the path from the
  129.     // root to the deleted key.
  130.  
  131.     virtual ItemType ExtractMin ();
  132.     // Remove and return the smallest item in the tree. Return the null
  133.     // pointer if the tree is empty.
  134.  
  135.  
  136.     // ---------------------- Basic methods ----------------------------
  137.  
  138.     void IntoStream (ostream& strm) const;
  139.     // Override the method inherited from {\tt CL_Object}.
  140.     // Dump the whole tree in indented form on {\tt strm}. This is for
  141.     // debugging purposes only, and uses the {\tt AsString} method on the
  142.     // {\tt ItemType}.
  143.  
  144.     virtual const char* ClassName () const { return "CL_BTree";};
  145.  
  146.     // --------------------- End public protocol -----------------------
  147.  
  148.  
  149. protected:
  150.     CL_Comparator<ItemType> _comparator;
  151.     CL_GenericBTree         _tree;
  152.     CL_HeapBTreeNodeSpace*  _space;
  153.     
  154.     void  PrintTree (CL_BTreeNodeHandle h, short level, ostream&) const;
  155.  
  156.     friend       CL_BTreeIterator<ItemType>;
  157. };
  158.  
  159.  
  160. // This is a template-based version of the iterator over a B-tree whose
  161. // template base is {\small\tt ItemType}.
  162.  
  163. template <class ItemType>
  164. class CL_EXPORT CL_BTreeIterator: public CL_Iterator<ItemType> {
  165.  
  166. public:
  167.     CL_BTreeIterator (const CL_BTree<ItemType>& t);
  168.     // Constructor: create a BTreeIterator for the given tree t.
  169.  
  170.     CL_BTreeIterator (const CL_BTreeIterator<ItemType>& itr);
  171.     // Copy constructor. The copy inspects the same B-tree as {\tt itr}, and
  172.     // (unless reset) begins  its iteration at the item at which {\tt itr}
  173.     // is currently positioned.
  174.     
  175.     void Reset();
  176.     // Reset the iterator to the leftmost (smallest) item.
  177.     
  178.     void BeginFrom (const ItemType&);
  179.     // Begin the iteration from the given item (or the one immediately
  180.     // larger, if the given item isn't in the tree).
  181.     
  182.     bool More();
  183.     // Tell whether there are more items in the iteration.
  184.     
  185.     const ItemType& Next();
  186.     // Return the next item in the iteration sequence.
  187.     
  188.  
  189.     // ---------------------- Basic methods ----------------------------
  190.  
  191.     const char* ClassName () const { return "CL_BTreeIterator";};
  192.  
  193.     // --------------------- End public protocol -----------------------
  194.  
  195.  
  196. protected:
  197.     CL_GenericBTreeIterator    _iter;
  198.     ItemType                   _data;
  199. };
  200.  
  201.  
  202.  
  203.  
  204.  
  205.  
  206. #endif /* _tbtree_h_ */
  207.