home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / treewalk.cxx < prev    next >
C/C++ Source or Header  |  1995-04-06  |  7KB  |  276 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.  
  35.  
  36. #ifndef _treewalk_cxx_ /* Tue Mar 15 12:53:06 1994 */
  37. #define _treewalk_cxx_
  38.  
  39. #ifdef __GNUC__
  40. #pragma implementation
  41. #endif
  42.  
  43.  
  44. #include "base/string.h"
  45.  
  46. #define _no_cl_treewalk_typedefs_
  47. #include "base/treewalk.h"
  48. #include "base/binding.h"
  49.  
  50.  
  51.  
  52.  
  53. // --------------------- CL_PostOrderWalker -----------------------------
  54.  
  55.  
  56.  
  57.  
  58. template <class ItemType>
  59. class StackEntry: public CL_Object {
  60.  
  61. public:
  62.     CL_TreeNode<ItemType>* node;
  63.     long                   index;
  64.  
  65.     StackEntry (CL_TreeNode<ItemType>* n) : node (n), index (0) {};
  66.     ~StackEntry () {};
  67. };
  68.  
  69.  
  70. // The stack defines the path to the node that will be returned on the
  71. // next call to Next.
  72.  
  73.  
  74. #ifdef __GNUC__
  75. #pragma implementation
  76. #endif
  77.  
  78.  
  79. template <class ItemType>
  80. CL_PostOrderWalker<ItemType>::CL_PostOrderWalker
  81.     (CL_TreeNode<ItemType>*  node)
  82. : _subtreeRoot (node)
  83. {
  84.     Reset ();
  85. }
  86.  
  87. template <class ItemType>
  88. CL_PostOrderWalker<ItemType>::~CL_PostOrderWalker ()
  89. {
  90.     _stack.DestroyContents();
  91. }
  92.  
  93.  
  94. template <class ItemType>
  95. void CL_PostOrderWalker<ItemType>::Reset ()
  96. {
  97.     _stack.DestroyContents ();
  98.     CL_TreeNode<ItemType>* node = _subtreeRoot;
  99.     while (node) {
  100.         StackEntry<ItemType>* p = new StackEntry<ItemType> (node);
  101.         if (!p)
  102.             return; // No memory
  103.         _stack.Add (p);
  104.         node = node->Child(0);
  105.     }
  106. }
  107.  
  108.  
  109.  
  110.  
  111. template <class ItemType>
  112. bool CL_PostOrderWalker<ItemType>::More ()
  113. {
  114.     return (_stack.Size() > 0);
  115. }
  116.  
  117.  
  118.  
  119. template <class ItemType>
  120. CL_TreeNode<ItemType>* CL_PostOrderWalker<ItemType>::Next ()
  121. {
  122.     long n = _stack.Size();
  123.     if (n <= 0)
  124.         return NULL;
  125.     StackEntry<ItemType>* current = (StackEntry<ItemType>*) _stack[n-1];
  126.     if (n == 1) {
  127.         CL_TreeNode<ItemType>* retVal = current->node;
  128.         _stack.DestroyContents ();
  129.         return retVal;
  130.     }
  131.  
  132.     // So the stack has at least two entries:
  133.     // Does current node have a right sibling?
  134.     StackEntry<ItemType>* parent = (StackEntry<ItemType>*) _stack[n-2];
  135.     CL_TreeNode<ItemType>* ret_val = current->node;
  136.     short count = parent->node->ChildCount();
  137.     if (count > parent->index + 1) {
  138.         // Yes, there's a right sibling; move to it
  139.         parent->index++;
  140.         current->node = parent->node->Child (parent->index);
  141.         current->index = 0;
  142.         // Now move left and down
  143.         CL_TreeNode<ItemType>* node = current->node;
  144.         do {
  145.             node = node->Child(0);
  146.             if (!node) break;
  147.             StackEntry<ItemType>* p = new StackEntry<ItemType> (node);
  148.             if (!p)
  149.                 return NULL; // No memory
  150.             _stack.Add (p);
  151.         } while (1);
  152.     }
  153.     else {
  154.         // No right sibling; just move to the parent
  155.         StackEntry<ItemType>* p = (StackEntry<ItemType>*)
  156.             _stack.ExtractRightmost();
  157.         delete p;
  158.     }
  159.     return ret_val;
  160. }
  161.  
  162.  
  163.  
  164. // --------------------- CL_PreOrderWalker -----------------------------
  165.  
  166.  
  167.  
  168.  
  169.  
  170. template <class ItemType>
  171. CL_PreOrderWalker<ItemType>::CL_PreOrderWalker
  172.   (CL_TreeNode<ItemType>*  node)
  173. : _subtreeRoot (node)
  174. {
  175.     Reset ();
  176. }
  177.  
  178.  
  179. template <class ItemType>
  180. CL_PreOrderWalker<ItemType>::~CL_PreOrderWalker ()
  181. {
  182.     _stack.DestroyContents();
  183. }
  184.  
  185.  
  186.  
  187. template <class ItemType>
  188. void CL_PreOrderWalker<ItemType>::Reset ()
  189. {
  190.     _stack.DestroyContents ();
  191.     CL_TreeNode<ItemType>* node = _subtreeRoot;
  192.     if (!node)
  193.         return;
  194.     StackEntry<ItemType>* p = new StackEntry<ItemType> (node);
  195.     if (!p)
  196.         return; // No memory
  197.     _stack.Add (p);
  198. }
  199.  
  200.  
  201.  
  202.  
  203. template <class ItemType>
  204. bool CL_PreOrderWalker<ItemType>::More ()
  205. {
  206.     return (_stack.Size() > 0);
  207. }
  208.  
  209.  
  210.  
  211. template <class ItemType>
  212. CL_TreeNode<ItemType>* CL_PreOrderWalker<ItemType>::Next ()
  213. {
  214.     long n = _stack.Size();
  215.     if (n <= 0)
  216.         return NULL;
  217.     StackEntry<ItemType>* current = (StackEntry<ItemType>*) _stack[n-1];
  218.     CL_TreeNode<ItemType>* ret_val = current->node;
  219.  
  220.     if (!current->node->IsLeaf()) {
  221.         // It's an internal node; move to its leftmost child
  222.         CL_TreeNode<ItemType>* node = current->node->Child(0);
  223.         StackEntry<ItemType>* p = new StackEntry<ItemType> (node);
  224.         if (!p)
  225.             return NULL; // No memory
  226.         _stack.Add (p);
  227.     }
  228.     else {
  229.         // It's a leaf; move up the tree until we find an ancestor that has
  230.         // a right sibling (the ancestor might be the current node itself)
  231.         StackEntry<ItemType>* p = (StackEntry<ItemType>*)
  232.             _stack.ExtractRightmost ();
  233.         delete p;
  234.         if (_stack.Size() <= 0) // We just finished
  235.             return NULL;
  236.         do {
  237.             long n = _stack.Size();
  238.         if (n <= 0) break;
  239.             p = (StackEntry<ItemType>*) _stack[n-1];
  240.             if (p->index < p->node->ChildCount() - 1)
  241.                 break;
  242.             delete (StackEntry<ItemType>*) _stack.ExtractRightmost();
  243.         } while (1);
  244.         if (_stack.Size() > 0) {
  245.             // We still have a few more nodes
  246.             p->index++;
  247.             StackEntry<ItemType>* q = new StackEntry<ItemType>
  248.                 (p->node->Child (p->index));
  249.             if (!q) // No memory
  250.                 return NULL;
  251.             _stack.Add (q);
  252.         }
  253.     }
  254.     return ret_val;
  255. }
  256.  
  257.  
  258.  
  259.  
  260.  
  261. #include "base/treewdef.h"
  262.  
  263. #if defined(__GNUC__) && __GNUC_MINOR__ >= 6
  264. template class  CL_PostOrderWalker<CL_ObjectPtr>;
  265. template class  CL_PreOrderWalker<CL_ObjectPtr> ;
  266. template class  StackEntry<CL_ObjectPtr>;
  267.  
  268. template class  CL_PreOrderWalker<long> ;
  269. template class  CL_PostOrderWalker<long>;
  270. template class  StackEntry<long>;
  271. #endif
  272.  
  273.  
  274. #endif /* _treewalk_cxx_ */
  275.  
  276.