home *** CD-ROM | disk | FTP | other *** search
/ PC Media 7 / PC MEDIA CD07.iso / share / prog / cm / cmtbtree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-06  |  4.3 KB  |  94 lines
  1. // CmTBTree.h
  2. // -----------------------------------------------------------------
  3. // Compendium - C++ Container Class Library
  4. // Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
  5. // -----------------------------------------------------------------
  6. // BTree template definition.
  7. // -----------------------------------------------------------------
  8.  
  9. #ifndef _CMTBTREE_H
  10. #define _CMTBTREE_H
  11.  
  12. #include <cm/include/cmtcont.h>
  13.  
  14. template <class T> class CmTBTreeNode;          // Tree node class stub.
  15. template <class T> class CmTBTreeIterator;      // Tree iterator class stub.
  16.  
  17. template <class T> class CmTBTree : public CmTContainer<T> {
  18. public:
  19.   CmTBTree(unsigned = 3);                       // Default tree constructor.
  20.   CmTBTree(const CmTBTree<T>&);                 // Tree copy constructor.
  21.  ~CmTBTree();                                   // Tree destructor.
  22.  
  23.   CmTBTree<T>& operator=(const CmTBTree<T>&);   // Assignment operator.
  24.  
  25.   unsigned order () const;                      // Return tree order.
  26.   unsigned height() const;                      // Return tree height.
  27.  
  28.   Bool     add        (const T&);               // Add item to tree.
  29.   Bool     remove     (const T&);               // Remove item from tree.
  30.   const T& lookup     (const T&) const;         // Find equal item in tree.
  31.   Bool     contains   (const T&) const;         // See if tree contains equal.
  32.   unsigned occurrences(const T&) const;         // Count occurrences of equal.
  33.   void     removeAll  ();                       // Remove all items.
  34.  
  35.   CmTIterator<T>* newIterator() const;          // Create tree iterator.
  36.  
  37. protected:
  38.   CmTBTreeNode<T>* nodeSearch(const T&) const; // Search for insertion node.
  39.   CmTBTreeNode<T>* lookupNode(const T&) const; // Get node where item is.
  40.  
  41.   static void removeNodes(CmTBTreeNode<T>*);   // Remove node children.
  42.   static unsigned minKeys(unsigned);           // Get minimum keys allowed.
  43.  
  44.   unsigned         _order;                     // Tree order.
  45.   CmTBTreeNode<T> *_root;                      // Root tree node.
  46.   friend           CmTBTreeIterator<T>;        // Iterator class can access.
  47. };
  48.  
  49. template <class T> class CmTBTreeNode {        // Tree node definition.
  50. protected:
  51.   CmTBTreeNode(CmTBTreeNode<T>*, unsigned);    // Node constructor.
  52.  ~CmTBTreeNode();                              // Node destructor.
  53.  
  54.   int  shouldGo(const T&);                     // Where should item insert.
  55.   int  index   (const T&);                     // Index where item is located.
  56.   int  index   (CmTBTreeNode<T>*);             // Index where child is located.
  57.   Bool addAt   (int, const T&, CmTBTreeNode<T>*, int); // Add item at index.
  58.   Bool removeAt(int);                          // Remove item at index.
  59.   void clear   (int);                          // Clear arrays.
  60.  
  61.   CmTBTreeNode<T>* split(unsigned);            // Split the node.
  62.  
  63.   CmTBTreeNode<T>  *_parent;                   // Parent node.
  64.   T                *_data;                     // (order  ) data items.
  65.   CmTBTreeNode<T> **_children;                 // (order+1) child nodes.
  66.   int               _total;                    // Number of items in node.
  67.   friend            CmTBTree<T>;               // Tree class can access.
  68.   friend            CmTBTreeIterator<T>;       // Iterator class can access.
  69. };
  70.  
  71. template <class T> class CmTBTreeIterator : public CmTIterator<T> {
  72. public:
  73.   CmTBTreeIterator(const CmTBTree<T>&);        // Iterator constructor.
  74.  
  75.   Bool     done    () const;                   // Check if at end.
  76.   const T& next    ();                         // Return and advance.
  77.   const T& previous();                         // Return and backup.
  78.   const T& current () const;                   // Get current item.
  79.   void     first   ();                         // Move to first item.
  80.   void     last    ();                         // Move to last item.
  81.  
  82. protected:
  83.   const CmTBTree<T>      &_tree;               // Tree being iterated.
  84.   CmTBTreeNode<T>        *_node;               // Current tree node.
  85.   int                     _index;              // Current node object.
  86.   friend                  CmTBTree<T>;         // Tree class can access.
  87. };
  88.  
  89. #if defined(__TURBOC__) || defined(__xlC__)
  90. #include <cm/include/cmtbtree.cc>
  91. #endif
  92.  
  93. #endif
  94.