home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / tree.h < prev    next >
C/C++ Source or Header  |  1995-04-08  |  10KB  |  290 lines
  1.  
  2.  
  3.  
  4.  
  5. #ifndef _tree_h_ /* Mon Aug 23 17:09:26 1993 */
  6. #define _tree_h_
  7.  
  8.  
  9.  
  10.  
  11.  
  12. /*
  13.  *
  14.  *          Copyright (C) 1994, M. A. Sridhar
  15.  *  
  16.  *
  17.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  18.  *     to copy, modify or distribute this software  as you see fit,
  19.  *     and to use  it  for  any  purpose, provided   this copyright
  20.  *     notice and the following   disclaimer are included  with all
  21.  *     copies.
  22.  *
  23.  *                        DISCLAIMER
  24.  *
  25.  *     The author makes no warranties, either expressed or implied,
  26.  *     with respect  to  this  software, its  quality, performance,
  27.  *     merchantability, or fitness for any particular purpose. This
  28.  *     software is distributed  AS IS.  The  user of this  software
  29.  *     assumes all risks  as to its quality  and performance. In no
  30.  *     event shall the author be liable for any direct, indirect or
  31.  *     consequential damages, even if the  author has been  advised
  32.  *     as to the possibility of such damages.
  33.  *
  34.  */
  35.  
  36.  
  37.  
  38.  
  39.  
  40. // This is  a  tree class that maintains parent-child relationships among
  41. // objects drawn from  a LabelType class.   The tree class is  a template
  42. // class based  on the  LabelType parameter. Each  node  of the  tree  is
  43. // labeled with an  element of type  LabelType, and all  the nodes of the
  44. // tree are required to have distinct labels.  In addition,  each node of
  45. // the tree may contain a pointer to a user-defined object.
  46. // 
  47. // The destructor of the tree destroys all the nodes in it, but  does not
  48. // invoke the destructors of the user-defined objects stored in the nodes
  49. // (i.e., the objects referenced by the Content() method of the Node). If
  50. // the tree is instantiated with a pointer-based template base type (as is
  51. // GenericTree), the pointed-to objects are {\it not\/} destroyed by the
  52. // tree's destructor; a tree walker (see {\tt treewalk.h}) can be used to
  53. // do so before destroying the tree.
  54. // 
  55. // Caveat: In the interests of future expandability, do NOT use templated
  56. // names  for types; use only the  typedef names at  the end of this file
  57. // (e.g., use VoidPtrTree but  not {\small\tt  CL_Tree <VoidPtr>}).  This
  58. // will allow the implementation to be made more efficient (later) without
  59. // affecting the  interface.
  60.  
  61.  
  62.  
  63. #ifdef __GNUC__
  64. #pragma interface
  65. #endif
  66.  
  67. #include "base/object.h"
  68. #include "base/sequence.h"
  69. #include "base/map.h"
  70. #include "base/binding.h"
  71.  
  72. template <class ItemType> class CL_TreeNode;
  73.     
  74.  
  75. typedef long CL_TreeNodeLabel;
  76.  
  77. template <class ItemType>
  78. class CL_EXPORT  CL_Tree: public CL_Object {
  79.  
  80. public:
  81.  
  82.     // --------------- Construction and destruction ----------------
  83.  
  84.     CL_Tree ();
  85.     // Default constructor: build an empty tree.
  86.  
  87.     CL_Tree (CL_TreeNodeLabel root);
  88.     // Constructor: build a tree with root having the given label.
  89.  
  90.     ~CL_Tree()
  91.     { _DeleteSubtree (_root);}
  92.     // Destructor.
  93.     
  94.     // -------------------- Querying operations ------------------------
  95.  
  96.     CL_TreeNode<ItemType>* Root () const
  97.         { return _root;};
  98.     // Return the root of the tree.
  99.  
  100.     CL_TreeNode<ItemType>* Node (CL_TreeNodeLabel l) const;
  101.     // Return the node with the given label, if it exists; return NULL
  102.     // if no such node. The return value points to memory owned by the
  103.     // tree, and must not be destroyed by the caller.
  104.     
  105.     
  106.  
  107.     // ---------- Addition and removal of nodes and subtrees -----------
  108.     
  109.     CL_TreeNode<ItemType>* AddChild (CL_TreeNodeLabel obj,
  110.                                       CL_TreeNodeLabel parent,
  111.                                       long index = 200000L);
  112.     // Add obj as the i-th child of the given parent; return the newly
  113.     // created node. Return NULL on error (e.g. parent is not in tree,
  114.     // invalid index specified, a node with the given label is already
  115.     // in the tree, or a memory allocation error occurs). An index of
  116.     // -1 specifies leftmost child. 
  117.     // Specifying a very larger index (specifically, anything larger
  118.     // than the number of siblings) causes addition as the rightmost
  119.     // child. The default value of the index is large enough, in most
  120.     // situations, to mean addition as rightmost child.
  121.  
  122.     CL_TreeNode<ItemType>* NewRoot (CL_TreeNodeLabel l);
  123.     // Create a new root with given label, and make the current root
  124.     // the (only) child of the new root. Return the new root if
  125.     // successful, and NULL on failure.
  126.     
  127.     CL_Tree<ItemType>* ExtractSubtree (CL_TreeNodeLabel obj);
  128.     // Remove and return the subtree rooted at the given node. The
  129.     // returned tree must be destroyed by the caller of this method.
  130.     
  131.     void DestroySubtree (CL_TreeNodeLabel x);
  132.     // Destroy the subtree rooted at x, and remove x from its
  133.     // parent's set of children.
  134.  
  135.     // --------------------- Traversal -----------------------------
  136.  
  137.     long PostOrderWalk (CL_TreeNodeLabel l, const
  138.                         CL_AbstractBinding& bind) const;
  139.     // Perform a post-order traversal of the subtree rooted at the
  140.     // node with the given label, and at each node in the traversal,
  141.     // invoke the given method with  the first parameter being the
  142.     // node and  the second parameter being the depth of the current
  143.     // node in the subtree being traversed (note that this NOT the
  144.     // depth in the entire tree unless the traversal starts at the
  145.     // root of the tree!). The traversal continues while the called
  146.     // method returns TRUE, and  stops when either the method returns
  147.     // FALSE or the subtree has been completely visited. The called
  148.     // method should NOT modify the tree. 
  149.     //    The return value is the number of nodes traversed.
  150.  
  151.     long Traverse (CL_TreeNodeLabel l, const CL_AbstractBinding& action1,
  152.                    const CL_AbstractBinding& action2) const;
  153.     // This is a generalized traversal of the tree,
  154.     // incorporating both preorder and postorder as special cases.
  155.     // It traverses the subtree rooted at the node with the given label,
  156.     // using the following algorithm:
  157.     // 
  158.     //        Invoke {\tt action1} at current node $v$ \\
  159.     //        For each child $w$ of current node $v$, in left-to-right order,
  160.     //            recursively traverse the subtree rooted at $w$ \\
  161.     //        Invoke {\tt action2} at current node $v$ \\
  162.     //
  163.     // The parameter values to the methods of {\tt action1} and {\tt
  164.     // action2}, and 
  165.     // the return value of the method, are as in the method PostOrderWalk.
  166.     // The traversal terminates when either the subtree has been
  167.     // completed, or when either of the action calls returns FALSE.
  168.     // Note that there are {\it two\/} calls at each node: once when entering
  169.     // the node and once when backing up into the node. This is true
  170.     // even for leaf nodes.
  171.     //
  172.     // If either the object or the method of a given binding is NULL,
  173.     // the action is not invoked.
  174.     //
  175.     // Neither of the action methods should modify the tree.
  176.     
  177.     // --------------------- Basic methods ---------------------------
  178.  
  179.     const char* ClassName() const { return "CL_Tree";};
  180.     
  181.     CL_ClassId ClassId() const   { return _CL_Tree_CLASSID;};
  182.  
  183.  
  184.     // --------------------- End public protocol ----------------------
  185.     
  186.     
  187.     
  188. protected:
  189.  
  190.     void _DeleteSubtree (CL_TreeNode<ItemType>* node);
  191.  
  192.     void _BuildSubmap   (CL_TreeNode<ItemType>* node);
  193.  
  194.     bool _Walk          (CL_TreeNode<ItemType>* node,
  195.                          const CL_AbstractBinding& b1,
  196.                          const CL_AbstractBinding& b2,
  197.                          long& count, long depth) const;
  198.     
  199.     CL_TreeNode<ItemType>* _root;
  200.     CL_IntPtrMap           _map; // The map of label values to node pointers
  201. };
  202.  
  203.  
  204.  
  205.  
  206.  
  207. // The class TreeNode is intended to be used only in conjunction with the
  208. // class Tree; nodes of the tree may be accessed via the Node() method of
  209. // the tree. Do not use node methods for modifying the node directly.
  210.  
  211. template <class ItemType>
  212. class CL_EXPORT  CL_TreeNode: public CL_Object {
  213.     
  214. public:
  215.     CL_TreeNode (CL_TreeNodeLabel lbl);
  216.  
  217.     ~CL_TreeNode();
  218.  
  219.     // ------------------ Querying functions -------------------------
  220.  
  221.     CL_TreeNodeLabel Label () const
  222.     { return _label; }
  223.  
  224.     CL_TreeNode<ItemType>* Parent () const
  225.     { return _parent; };
  226.     
  227.     const CL_ObjectSequence& Children () const {return  _childPtrs;};
  228.  
  229.     CL_TreeNode<ItemType>* Child (long childIndex) const;
  230.  
  231.     long IndexInParent () const
  232.     { return _indexInParent; };
  233.     
  234.     long ChildCount () const
  235.     { return _childPtrs.Size();};
  236.  
  237.     bool IsLeaf () const
  238.     {return ChildCount() == 0;};
  239.  
  240.     ItemType& Content ();
  241.     // Return the user-specified content of this node. Note that a
  242.     // reference is returned, which can be modified by the user of
  243.     // this class.
  244.  
  245. protected:
  246.     friend class CL_Tree<ItemType>;
  247.  
  248.     // ------------------- Modification functions -------------------
  249.  
  250.     CL_TreeNode<ItemType>* AddChild (CL_TreeNodeLabel lbl, long
  251.                                      leftSiblingIndex = 200000L);
  252.     // Add a child to this node, immediately to the right of the child
  253.     // with given index. Index of -1 specifies leftmost child.
  254.     // Specifying a very larger index (specifically, anything larger
  255.     // than the number of siblings) causes addition as the rightmost
  256.     // child. The default value of the index is large enough, in most
  257.     // situations, to mean addition as rightmost child.
  258.     // If successful, return a pointer to the new child node; otherwise,
  259.     // return NULL.
  260.  
  261.     
  262.     CL_TreeNode<ItemType>* AddChild (CL_TreeNode<ItemType>* node,
  263.                                       long leftSiblingIndex = 200000L);
  264.  
  265.  
  266.  
  267.     CL_TreeNodeLabel        _label;
  268.     CL_TreeNode<ItemType>*  _parent;
  269.     CL_ObjectSequence       _childPtrs;      // Ptrs to nodes
  270.     long                    _indexInParent;  // Child number of this
  271.                                              // node
  272.     CL_VoidPtr              _content;
  273.  
  274.     
  275. };
  276.  
  277.  
  278.  
  279.  
  280.  
  281. #ifndef _no_cl_tree_typedefs_
  282. #include "base/treedef.h"
  283. #endif
  284.  
  285.  
  286.  
  287. #endif
  288.  
  289.  
  290.