home *** CD-ROM | disk | FTP | other *** search
/ Liren Large Software Subsidy 7 / 07.iso / c / c221 / 6.ddi / MWHC.006 / G0 < prev    next >
Encoding:
Text File  |  1992-06-07  |  4.4 KB  |  132 lines
  1. #ifndef __RWBINTREE_H__
  2. #define __RWBINTREE_H__
  3. pragma push_align_members(64);
  4.  
  5. /*
  6.  * Binary tree of pointers to RWCollectable objects
  7.  *
  8.  * $Header:   E:/vcs/rw/bintree.h_v   1.6   01 Apr 1992 16:38:30   KEFFER  $
  9.  *
  10.  ****************************************************************************
  11.  *
  12.  * Rogue Wave 
  13.  * P.O. Box 2328
  14.  * Corvallis, OR 97339
  15.  * Voice: (503) 754-3010    FAX: (503) 757-6650
  16.  *
  17.  * Copyright (C) 1989, 1990, 1991. This software is subject to copyright 
  18.  * protection under the laws of the United States and other countries.
  19.  *
  20.  ***************************************************************************
  21.  *
  22.  * $Log:   E:/vcs/rw/bintree.h_v  $
  23.  * 
  24.  *    Rev 1.6   01 Apr 1992 16:38:30   KEFFER
  25.  * Removed private (and undefined) declaration for constructFrom().
  26.  * 
  27.  *    Rev 1.5   04 Mar 1992 09:02:38   KEFFER
  28.  * nil changed to rwnil
  29.  * 
  30.  *    Rev 1.4   18 Feb 1992 09:54:02   KEFFER
  31.  * 
  32.  *    Rev 1.3   29 Oct 1991 13:56:14   keffer
  33.  * 
  34.  *    Rev 1.2   28 Oct 1991 09:08:06   keffer
  35.  * Changed inclusions to <rw/xxx.h>
  36.  * 
  37.  */
  38.  
  39. #include "rw/colclass.h"
  40. #include "rw/iterator.h"
  41. #include "rw/mempool.h"
  42. STARTWRAP
  43. #include <stddef.h>
  44. ENDWRAP
  45.  
  46. // Node in binary tree:
  47. class RWExport RWTreeNode : public RWMemoryPool {
  48. private:
  49. friend class RWExport RWBinaryTree;
  50. friend class RWExport RWBinaryTreeIterator;
  51.   RWTreeNode*        right;    // Pointer to right node.
  52.   RWTreeNode*        left;   // Pointer to left node.
  53.   RWCollectable*    e;      // Pointer to RWCollectable object.
  54. private:
  55.   // Private constructor:
  56.   RWTreeNode(RWCollectable* a, RWTreeNode* p=rwnil, RWTreeNode* n=rwnil) 
  57.     { e = a; left = p; right = n; }
  58. };
  59.  
  60. #include "rw/gqueue.h"
  61. declare(GQueue, RWCollectable)
  62.  
  63. class RWExport RWBinaryTree : public RWCollection {
  64. friend class RWExport RWBinaryTreeIterator;
  65.   RWTreeNode*            root;      // root = top-level item in tree
  66. protected:
  67.   void                applyChildren(const RWTreeNode*, RWapplyCollectable, void*);
  68.   void                balanceUnique();
  69.   RWTreeNode*                balanceChildren(unsigned, GQueue(RWCollectable)&);
  70.   void                countChildren(const RWTreeNode*, unsigned&) const;
  71.   void                deleteChildren(RWTreeNode*);
  72.   RWCollectable*        deleteNode(RWTreeNode* victim, RWTreeNode* parent);
  73.   void                insertChildrenOf(const RWTreeNode*);
  74. public:
  75.   RWBinaryTree();
  76.   RWBinaryTree(const RWBinaryTree&);
  77.   ~RWBinaryTree();
  78.  
  79.   void                operator=(const RWBinaryTree&);
  80.   RWBoolean            operator<=(const RWBinaryTree& bt) const; // Subset of bt
  81.   RWBoolean            operator==(const RWBinaryTree& bt) const;
  82.  
  83.   // Special member function to balance a binary tree:
  84.   void                balance();
  85.  
  86. /********  Standard Member Functions for Collection Classes ********/  
  87.   virtual void            apply(RWapplyCollectable, void*);
  88.   virtual void            clear();
  89. //virtual void            clearAndDestroy();
  90. //virtual RWBoolean        contains(const RWCollectable*) const;
  91.   virtual unsigned        entries() const;            // Total entries
  92.   virtual RWCollectable*    find(const RWCollectable*) const;        // First occurrence
  93.   virtual RWCollectable*    insert(RWCollectable*);
  94.   virtual ClassID        isA() const {return __RWBINARYTREE;}
  95.   virtual RWBoolean        isEmpty() const {return root==rwnil;}
  96.   virtual RWBoolean        isEqual(const RWCollectable*) const;
  97.   virtual RWCollectable*    newSpecies() const;
  98.   virtual unsigned        occurrencesOf(const RWCollectable*) const;
  99.   virtual RWCollectable*    remove(const RWCollectable*);        // Remove first occurrence
  100. //virtual void             removeAndDestroy(const RWCollectable*); 
  101.   virtual void            restoreGuts(RWvistream&);
  102.   virtual void            restoreGuts(RWFile&);
  103.  
  104. #ifdef RDEBUG
  105.   void    printChildren(const RWTreeNode*, ostream&, unsigned&, char) const;
  106.   friend ostream& operator<<(ostream&, const RWBinaryTree& bt);
  107. #endif
  108. };    
  109.  
  110. #include "rw/gstack.h"
  111. declare(GStack, RWTreeNode)
  112.  
  113. class RWExport RWBinaryTreeIterator : public RWIterator {
  114. protected:
  115.   const RWBinaryTree*        tree;        // Binary tree for this iterator.
  116.   const RWTreeNode*        here;        // Current node.
  117.   GStack(RWTreeNode)        stack;
  118. private:
  119.   void                descendLeft();
  120. public:
  121.   RWBinaryTreeIterator(const RWBinaryTree&);
  122.  
  123. /*********** Virtual functions inherited from class RWIterator ***********/
  124.   virtual RWCollectable*    findNext(const RWCollectable*);        // Find next matching item
  125.   virtual RWCollectable*    key() const;                // Return current value
  126.   virtual RWCollectable*    operator()();                // Advance iterator
  127.   virtual void               reset();
  128. };
  129.  
  130. pragma pop_align_members();
  131. #endif /* __RWBINTREE_H__ */
  132.