home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / treeimp.cxx < prev    next >
C/C++ Source or Header  |  1995-04-04  |  8KB  |  327 lines
  1.  
  2.  
  3.  
  4.  
  5. /*
  6.  *
  7.  *          Copyright (C) 1994, M. A. Sridhar
  8.  *  
  9.  *
  10.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  11.  *     to copy, modify or distribute this software  as you see fit,
  12.  *     and to use  it  for  any  purpose, provided   this copyright
  13.  *     notice and the following   disclaimer are included  with all
  14.  *     copies.
  15.  *
  16.  *                        DISCLAIMER
  17.  *
  18.  *     The author makes no warranties, either expressed or implied,
  19.  *     with respect  to  this  software, its  quality, performance,
  20.  *     merchantability, or fitness for any particular purpose. This
  21.  *     software is distributed  AS IS.  The  user of this  software
  22.  *     assumes all risks  as to its quality  and performance. In no
  23.  *     event shall the author be liable for any direct, indirect or
  24.  *     consequential damages, even if the  author has been  advised
  25.  *     as to the possibility of such damages.
  26.  *
  27.  */
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34. #ifndef _treeimp_cxx_
  35. #define _treeimp_cxx_
  36.  
  37. #ifdef __GNUC__
  38. #pragma implementation
  39. #endif
  40.  
  41.  
  42. #define _no_cl_tree_typedefs_
  43. #include "base/tree.h"
  44. #include "base/binding.h"
  45. #include "base/basicops.h"
  46.  
  47.  
  48. //
  49. //---------------------------Node--------------------
  50. //
  51.  
  52.  
  53.  
  54. template <class ItemType>
  55. CL_TreeNode<ItemType>::CL_TreeNode (CL_TreeNodeLabel l)
  56. : _label (l), _parent (NULL)
  57. {
  58.     _indexInParent = 0;
  59.     _content = CL_Basics<ItemType>::MakeCopy
  60.         (CL_Basics<ItemType>::NullValue());
  61. }
  62.  
  63.  
  64. template <class ItemType>
  65. CL_TreeNode<ItemType>* CL_TreeNode<ItemType>::AddChild
  66.     (CL_TreeNodeLabel l, long leftSiblingIndex)
  67. {
  68.     CL_TreeNode<ItemType>* node = new CL_TreeNode<ItemType> (l);
  69.     return (node && AddChild (node, leftSiblingIndex)) ? node : NULL;
  70. }
  71.  
  72.  
  73.  
  74.  
  75. template <class ItemType>
  76. CL_TreeNode<ItemType>* CL_TreeNode<ItemType>::Child (long index) const
  77. {
  78.     if (index < 0 || index >= _childPtrs.Size())
  79.         return NULL;
  80.     return (CL_TreeNode<ItemType>*) _childPtrs[index];
  81. }
  82.     
  83.  
  84. template <class ItemType>
  85. CL_TreeNode<ItemType>::~CL_TreeNode ()
  86. {
  87.     CL_Basics<ItemType>::Destroy (_content);
  88. }
  89.     
  90. template <class ItemType>
  91. ItemType& CL_TreeNode<ItemType>::Content ()
  92. {
  93.     return CL_Basics<ItemType>::Deref (_content);
  94. }
  95.     
  96.  
  97.  
  98.  
  99. template <class ItemType>
  100. CL_TreeNode<ItemType>* CL_TreeNode<ItemType>::AddChild
  101.     (CL_TreeNode<ItemType>* node, long leftSiblingIndex)
  102. {
  103.     if (leftSiblingIndex >= ChildCount())
  104.         leftSiblingIndex = ChildCount() - 1;
  105.     if (! _childPtrs.Insert (node, leftSiblingIndex))
  106.         return NULL;
  107.     node->_indexInParent = leftSiblingIndex + 1;
  108.     node->_parent = this;
  109.     return node;
  110. }
  111.  
  112.  
  113.  
  114.  
  115. //
  116. //-----------------CL_Tree ---------------------------------------
  117. //
  118.  
  119. template <class ItemType>
  120. CL_Tree<ItemType>::CL_Tree()
  121. {
  122.     _root = NULL;
  123. }
  124.  
  125.     
  126. template <class ItemType>
  127. CL_Tree<ItemType>::CL_Tree(CL_TreeNodeLabel rt)
  128. {
  129.     _root = new CL_TreeNode<ItemType> (rt);
  130.     _map.Add (rt, _root);
  131. }
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140. template <class ItemType>
  141. CL_TreeNode<ItemType>* CL_Tree<ItemType>::AddChild
  142.     (CL_TreeNodeLabel obj, CL_TreeNodeLabel parent, long i)
  143. {
  144.     CL_TreeNode<ItemType>* node, *child;
  145.  
  146.     if (!PrepareToChange())
  147.         return NULL;
  148.     node = Node (parent);
  149.     if (node == NULL)
  150.         return NULL;
  151.     if (_map.IncludesKey (obj))
  152.         return NULL;
  153.     child = node->AddChild (obj, i);
  154.     if (child && _map.Add (obj, child)) {
  155.         Notify();
  156.         return child;
  157.     }
  158.     else
  159.         return NULL;
  160. }     
  161.  
  162.  
  163.     
  164.  
  165. template <class ItemType>
  166. CL_TreeNode<ItemType>* CL_Tree<ItemType>::NewRoot
  167.     (CL_TreeNodeLabel l)
  168. {
  169.     if (!PrepareToChange())
  170.         return NULL;
  171.     CL_TreeNode<ItemType>* root = new CL_TreeNode<ItemType> (l);
  172.     if (!root)
  173.         return NULL;
  174.     if ( (_root == NULL || root->AddChild (_root)) &&  _map.Add (l, root)) {
  175.         _root = root;
  176.         _root->_indexInParent = 0;
  177.         Notify();
  178.         return _root;
  179.     }
  180.     return NULL;
  181. }
  182.  
  183.     
  184.  
  185.  
  186. template <class ItemType>
  187. CL_Tree<ItemType>* CL_Tree<ItemType>::ExtractSubtree(CL_TreeNodeLabel obj)
  188. {
  189.     if (!PrepareToChange())
  190.         return NULL;
  191.     CL_TreeNode<ItemType>* node = Node (obj);
  192.     if (node == NULL)
  193.         return NULL;
  194.     CL_TreeNode<ItemType>* parent = node->_parent;
  195.     if (parent) {
  196.         (parent->_childPtrs).Remove (node->_indexInParent);
  197.         long n = parent->ChildCount();
  198.         for (long i = node->_indexInParent; i < n; i++) {
  199.             CL_TreeNode<ItemType>* sibling = parent->Child(i);
  200.             sibling->_indexInParent--;
  201.         }
  202.     }
  203.     CL_Tree<ItemType>* new_tree = new CL_Tree<ItemType>;
  204.     new_tree->_root = node;
  205.     node->_parent = NULL;
  206.     node->_indexInParent = 0;
  207.     new_tree->_BuildSubmap (new_tree->_root);
  208.     Notify();
  209.     return new_tree;
  210. }
  211.     
  212. template <class ItemType>
  213. CL_TreeNode<ItemType>* CL_Tree<ItemType>::Node (CL_TreeNodeLabel l) const
  214. {
  215.     return (CL_TreeNode<ItemType> *) (((CL_Tree<ItemType>*) this)->_map)[l];
  216.     // --------------------------------^^^^^^^^^^^^^^^^^^^^ cast away const
  217. }
  218.  
  219.  
  220.  
  221. template <class ItemType>
  222. void CL_Tree<ItemType>::DestroySubtree(CL_TreeNodeLabel l)
  223. {
  224.     if (!PrepareToChange())
  225.         return;
  226.     CL_TreeNode<ItemType>* node = Node (l);
  227.     if (node == NULL)
  228.         return;
  229.     CL_TreeNode<ItemType>* parent = node->_parent;
  230.     if (parent) {
  231.         (parent->_childPtrs).Remove (node->_indexInParent);
  232.         long n = parent->ChildCount();
  233.         for (long i = node->_indexInParent; i < n; i++) {
  234.             CL_TreeNode<ItemType>* sibling = parent->Child(i);
  235.             sibling->_indexInParent--;
  236.         }
  237.     }
  238.     _DeleteSubtree (node);
  239.     Notify ();
  240. }
  241.  
  242.  
  243.  
  244.  
  245. template <class ItemType>
  246. long CL_Tree<ItemType>::PostOrderWalk (CL_TreeNodeLabel l,
  247.                                         const CL_AbstractBinding& bind) const
  248. {
  249.     long count = 0;
  250.     CL_TreeNode<ItemType>* node = Node (l);
  251.     if (node == NULL)
  252.         return 0;
  253.     CL_Binding<CL_Object> nullBinding (0, 0);
  254.     _Walk (node, nullBinding, bind, count, 0);
  255.     return count;
  256. }
  257.  
  258.  
  259.  
  260. template <class ItemType>
  261. long CL_Tree<ItemType>::Traverse (CL_TreeNodeLabel l,
  262.                                   const CL_AbstractBinding& b1,
  263.                                   const CL_AbstractBinding& b2) const
  264. {
  265.     long count = 0;
  266.     CL_TreeNode<ItemType>* node = Node (l);
  267.     if (node == NULL)
  268.         return 0;
  269.     _Walk (node, b1, b2, count, 0);
  270.     return count;
  271. }
  272.  
  273.  
  274. // Protected CL_Tree methods:
  275.  
  276. template <class ItemType>
  277. void CL_Tree<ItemType>::_DeleteSubtree (CL_TreeNode<ItemType>* node)
  278. {
  279.     if (!node)
  280.         return;
  281.     long n = node->ChildCount ();
  282.     for (long i = 0; i < n; i++) {
  283.         _DeleteSubtree ((CL_TreeNode<ItemType>*) (node->_childPtrs)[i]);
  284.     }
  285.     _map.Remove (node->_label);
  286.     delete node;
  287. }
  288.  
  289.  
  290.  
  291. template <class ItemType>
  292. void CL_Tree<ItemType>::_BuildSubmap (CL_TreeNode<ItemType>* node)
  293. {
  294.     if (!node)
  295.         return;
  296.     long n = node->ChildCount ();
  297.     for (long i = 0; i < n; i++) {
  298.         _BuildSubmap ((CL_TreeNode<ItemType>*) (node->_childPtrs)[i]);
  299.     }
  300.     _map.Add (node->_label, node);
  301. }
  302.  
  303. template <class ItemType>
  304. bool CL_Tree<ItemType>::_Walk (CL_TreeNode<ItemType>* node,
  305.                                const CL_AbstractBinding& b1,
  306.                                const CL_AbstractBinding& b2,
  307.                                long& count, long depth) const
  308. {
  309.     if (!node)
  310.         return TRUE;
  311.     if (b1.Valid() && !b1.Execute (*node, depth))
  312.         return FALSE;
  313.     long n = node->ChildCount ();
  314.     count++;
  315.     for (long i = 0; i < n; i++) {
  316.         if (!_Walk (node->Child(i), b1, b2, count, depth+1)) return FALSE;
  317.     }
  318.     return b2.Valid() ? b2.Execute (*node, depth) : TRUE;
  319. }
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326. #endif  /* _treeimp_cxx_ */
  327.