home *** CD-ROM | disk | FTP | other *** search
/ PC Media 7 / PC MEDIA CD07.iso / share / prog / cm / cmbintr.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-09-06  |  4.2 KB  |  92 lines
  1. // CmBinTr.h
  2. // -----------------------------------------------------------------
  3. // Compendium - C++ Container Class Library
  4. // Copyright (C) 1992-1994, Glenn M. Poorman, All rights reserved
  5. // -----------------------------------------------------------------
  6. // Binary tree definition.
  7. // -----------------------------------------------------------------
  8.  
  9. #ifndef _CMBINTR_H
  10. #define _CMBINTR_H
  11.  
  12. #include <cm/include/cmcont.h>
  13. #include <cm/include/cmtstack.h>
  14. #include <cm/include/cmtqueue.h>
  15.  
  16. class CmBinaryTreeNode;                            // Tree node class stub.
  17. class CmBinaryTreeIterator;                        // Iterator class stub.
  18.  
  19. class CmBinaryTree : public CmContainer {          // Tree class definition.
  20. public:
  21.   CmBinaryTree() : _root(NULL) {}                  // Default tree constructor.
  22.   CmBinaryTree(const CmBinaryTree&);               // Tree copy constructor.
  23.  ~CmBinaryTree();                                  // Tree destructor.
  24.  
  25.   CmBinaryTree& operator=(const CmBinaryTree&);    // Assignment operator.
  26.  
  27.   Bool        add        (CmObject*);              // Add object to tree.
  28.   Bool        remove     (CmObject*);              // Remove equal object.
  29.   CmObject*   lookup     (CmObject*) const;        // Locate equal object.
  30.   Bool        contains   (CmObject*) const;        // Tree has object?
  31.   unsigned    occurrences(CmObject*) const;        // Count occurrences of.
  32.   void        removeAll  ();                       // Clear tree contents.
  33.   CmObject*   root       () const;                 // Return root object.
  34.   void        balance    ();                       // Balance the tree.
  35.   CmIterator* newIterator() const;                 // Get tree iterator.
  36.   Bool        write      (CmReserveFile&) const;   // Write to reserve file.
  37.   Bool        read       (CmReserveFile&);         // Read from reserve file.
  38.  
  39.   CMOBJECT_DEFINE(CmBinaryTree, CmContainer)       // Define object funcs.
  40.  
  41. protected:
  42.   void balanceHalf(CmTQueue<CmBinaryTreeNode*>*, int, int);  // Balance tree.
  43.  
  44.   static void killNode(CmBinaryTreeNode*, Bool);   // Destroy sub-nodes.
  45.  
  46.   CmBinaryTreeNode *_root;                         // Tree root node.
  47.   friend            CmBinaryTreeIterator;          // Iterator can access.
  48. };
  49.  
  50. class CmBinaryTreeIterator : public CmIterator {   // Iterator definition.
  51. public:
  52.   CmBinaryTreeIterator(const CmBinaryTree &Tr);    // Constructor.
  53.  ~CmBinaryTreeIterator();                          // Destructor.
  54.  
  55.   Bool      done    () const { return (!_node); }  // Check if at end.
  56.   CmObject* next    ();                            // Return and advance.
  57.   CmObject* previous();                            // Return and backup.
  58.   CmObject* current () const;                      // Get current object.
  59.   void      first   ();                            // Move to first object.
  60.   void      last    ();                            // Move to last object.
  61.  
  62.   CMOBJECT_DEFINE(CmBinaryTreeIterator, CmIterator)  // Define object funcs.
  63.  
  64. protected:
  65.   const CmBinaryTree          &_tree;              // Tree being iterated.
  66.   CmBinaryTreeNode            *_node;              // Current tree node.
  67.   CmTStack<CmBinaryTreeNode*> *_stack;             // Node stack.
  68.   friend                       CmBinaryTree;       // Tree class can access.
  69. };
  70.  
  71. class CmBinaryTreeNode {                           // Tree node class.
  72. protected:
  73.   CmBinaryTreeNode *_left;                         // Left subtree pointer.
  74.   CmObject         *_data;                         // Object pointer.
  75.   CmBinaryTreeNode *_right;                        // Right subtree pointer.
  76.   friend            CmBinaryTree;                  // Tree can access.
  77.   friend            CmBinaryTreeIterator;          // Iterator can access.
  78.  
  79.   CmBinaryTreeNode(CmObject *O)                    // Node constructor.
  80.                   : _left(NULL), _data(O), _right(NULL) {}
  81. };
  82.  
  83. // "root" returns the root object of the tree.
  84. inline CmObject* CmBinaryTree::root() const
  85. { return (_root) ? _root->_data : NULL; }
  86.  
  87. // "current" returns the current tree object.
  88. inline CmObject* CmBinaryTreeIterator::current() const
  89. { return (_node) ? _node->_data : NULL; }
  90.  
  91. #endif
  92.