home *** CD-ROM | disk | FTP | other *** search
/ PC Media 7 / PC MEDIA CD07.iso / share / prog / cm / cmbtree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-06  |  5.1 KB  |  112 lines
  1. // CmBTree.h
  2. // -----------------------------------------------------------------
  3. // Compendium - C++ Container Class Library
  4. // Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
  5. // -----------------------------------------------------------------
  6. // BTree tree definition.
  7. // -----------------------------------------------------------------
  8.  
  9. #ifndef _CMBTREE_H
  10. #define _CMBTREE_H
  11.  
  12. #include <cm/include/cmcont.h>
  13.  
  14. class CmBTreeNode;                             // Tree node class stub.
  15. class CmBTreeIterator;                         // Tree iterator class stub.
  16.  
  17. class CmBTree : public CmContainer {           // BTree class definition.
  18. public:
  19.   CmBTree(unsigned = 3);                       // Default tree constructor.
  20.   CmBTree(const CmBTree&);                     // Tree copy constructor.
  21.  ~CmBTree();                                   // Tree destructor.
  22.  
  23.   CmBTree& operator=(const CmBTree&);          // Assignment operator.
  24.  
  25.   unsigned order () const;                     // Return tree order.
  26.   unsigned height() const;                     // Return tree height.
  27.  
  28.   Bool        add        (CmObject*);          // Add object to tree.
  29.   Bool        remove     (CmObject*);          // Remove equal object.
  30.   CmObject*   lookup     (CmObject*) const;    // Find equal object in tree.
  31.   Bool        contains   (CmObject*) const;    // See if tree contains equal.
  32.   unsigned    occurrences(CmObject*) const;    // Count occurrences of equal.
  33.   void        removeAll  ();                   // Remove all objects.
  34.   CmIterator* newIterator() const;             // Create tree iterator.
  35.  
  36.   CMOBJECT_DEFINE(CmBTree, CmContainer)        // Define object funcs.
  37.  
  38. protected:
  39.   CmBTreeNode* nodeSearch(CmObject*) const;    // Search for insertion node.
  40.   CmBTreeNode* lookupNode(CmObject*) const;    // Get node where object is.
  41.   CmBTreeNode* lookupAbs (CmObject*) const;    // Get node of exact object.
  42.  
  43.   static void removeNodes(CmBTreeNode*, Bool); // Remove node children.
  44.   static unsigned minKeys(unsigned);           // Get minimum keys allowed.
  45.  
  46.   unsigned     _order;                         // Tree order.
  47.   CmBTreeNode *_root;                          // Root tree node.
  48.   friend       CmBTreeIterator;                // Iterator class can access.
  49. };
  50.  
  51. class CmBTreeNode {                            // Tree node definition.
  52. protected:
  53.   CmBTreeNode(CmBTreeNode*, unsigned);         // Node constructor.
  54.  ~CmBTreeNode();                               // Node destructor.
  55.  
  56.   int  shouldGo(CmObject*) const;              // Where should object insert.
  57.   int  index   (CmObject*) const;              // Index of equal object.
  58.   int  indexAbs(CmObject*) const;              // Index of absolute object.
  59.   int  index   (CmBTreeNode*) const;           // Index where child is located.
  60.   Bool addAt   (int, CmObject*, CmBTreeNode*, int); // Add object at index.
  61.   Bool removeAt(int);                          // Remove object at index.
  62.   void clear   (int);                          // Clear arrays.
  63.  
  64.   CmBTreeNode* split(unsigned);                // Split the node.
  65.  
  66.   CmBTreeNode  *_parent;                       // Parent node.
  67.   CmObject    **_data;                         // (order  ) object pointers.
  68.   CmBTreeNode **_children;                     // (order+1) child nodes.
  69.   int           _total;                        // Number of objects in node.
  70.   friend        CmBTree;                       // Tree class can access.
  71.   friend        CmBTreeIterator;               // Iterator class can access.
  72. };
  73.  
  74. class CmBTreeIterator : public CmIterator {    // Iterator class definition.
  75. public:
  76.   CmBTreeIterator(const CmBTree &Tr);          // Iterator constructor.
  77.  
  78.   Bool      done    () const;                  // Check if at end.
  79.   CmObject* next    ();                        // Return and advance.
  80.   CmObject* previous();                        // Return and backup.
  81.   CmObject* current () const;                  // Get current object.
  82.   void      first   ();                        // Move to first object.
  83.   void      last    ();                        // Move to last object.
  84.  
  85.   CMOBJECT_DEFINE(CmBTreeIterator, CmIterator) // Define object funcs.
  86.  
  87. protected:
  88.   const CmBTree          &_tree;               // Tree being iterated.
  89.   CmBTreeNode            *_node;               // Current tree node.
  90.   int                     _index;              // Current node object.
  91.   friend                  CmBTree;             // Tree class can access.
  92. };
  93.  
  94. // "order" returns the current tree order.
  95. inline unsigned CmBTree::order () const
  96. { return _order; }
  97.  
  98. // "minKeys" returns the minimum number of keys allowed in a non-
  99. // root node of the tree.
  100. inline unsigned CmBTree::minKeys(unsigned ordr)
  101. { return (((ordr / 2) * 2) == ordr) ? (ordr / 2) - 1 : (ordr / 2); }
  102.  
  103. // "done" returns whether or not we are done iterating.
  104. inline Bool CmBTreeIterator::done() const
  105. { return (!_node); }
  106.  
  107. // "current" returns the current object pointed to by this iterator.
  108. inline CmObject* CmBTreeIterator::current() const
  109. { return (_node && _node->_data[_index]) ? _node->_data[_index] : NULL; }
  110.  
  111. #endif
  112.