lltreeiterators_test.cpp
上传用户:king477883
上传日期:2021-03-01
资源大小:9553k
文件大小:43k
源码类别:

游戏引擎

开发平台:

C++ Builder

  1. /**
  2.  * @file   lltreeiterators.cpp
  3.  * @author Nat Goodspeed
  4.  * @date   2008-08-20
  5.  * @brief  Test of lltreeiterators.h
  6.  * 
  7.  * $LicenseInfo:firstyear=2008&license=viewergpl$
  8.  * 
  9.  * Copyright (c) 2008-2010, Linden Research, Inc.
  10.  * 
  11.  * Second Life Viewer Source Code
  12.  * The source code in this file ("Source Code") is provided by Linden Lab
  13.  * to you under the terms of the GNU General Public License, version 2.0
  14.  * ("GPL"), unless you have obtained a separate licensing agreement
  15.  * ("Other License"), formally executed by you and Linden Lab.  Terms of
  16.  * the GPL can be found in doc/GPL-license.txt in this distribution, or
  17.  * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2
  18.  * 
  19.  * There are special exceptions to the terms and conditions of the GPL as
  20.  * it is applied to this Source Code. View the full text of the exception
  21.  * in the file doc/FLOSS-exception.txt in this software distribution, or
  22.  * online at
  23.  * http://secondlifegrid.net/programs/open_source/licensing/flossexception
  24.  * 
  25.  * By copying, modifying or distributing this software, you acknowledge
  26.  * that you have read and understood your obligations described above,
  27.  * and agree to abide by those obligations.
  28.  * 
  29.  * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO
  30.  * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY,
  31.  * COMPLETENESS OR PERFORMANCE.
  32.  * $/LicenseInfo$
  33.  */
  34. // Precompiled header
  35. #include "linden_common.h"
  36. // STL headers
  37. // std headers
  38. #include <iostream>
  39. #include <sstream>
  40. #include <string>
  41. // external library headers
  42. #include <boost/bind.hpp>
  43. #include <boost/range/iterator_range.hpp>
  44. #include <boost/foreach.hpp>
  45. // associated header
  46. #include "../lltreeiterators.h"
  47. #include "../llpointer.h"
  48. #include "../test/lltut.h"
  49. /*****************************************************************************
  50. *   tut test group
  51. *****************************************************************************/
  52. namespace tut
  53. {
  54.     struct iter_data
  55.     {
  56.     };
  57.     typedef test_group<iter_data> iter_group;
  58.     typedef iter_group::object iter_object;
  59.     tut::iter_group ig("lltreeiterators");
  60. } // namespace tut
  61. /*****************************************************************************
  62. *   boost::get_pointer() specialization for LLPointer<>
  63. *****************************************************************************/
  64. // This specialization of boost::get_pointer() undoubtedly belongs in
  65. // llmemory.h. It's used by boost::bind() so that you can pass an
  66. // LLPointer<Foo> as well as a Foo* to a functor such as
  67. // boost::bind(&Foo::method, _1).
  68. //namespace boost
  69. //{
  70.     template <class NODE>
  71.     NODE* get_pointer(const LLPointer<NODE>& ptr) { return ptr.get(); }
  72. //};
  73. /*****************************************************************************
  74. *   ScopeLabel
  75. *****************************************************************************/
  76. class ScopeLabel
  77. {
  78. public:
  79.     ScopeLabel(const std::string& label): mLabel(label)
  80.     {
  81.         std::cout << "Entering " << mLabel << 'n';
  82.     }
  83.     ~ScopeLabel()
  84.     {
  85.         std::cout << "Leaving  " << mLabel << 'n';
  86.     }
  87. private:
  88.     std::string mLabel;
  89. };
  90. /*****************************************************************************
  91. *   Cleanup
  92. *****************************************************************************/
  93. // Yes, we realize this is redundant with auto_ptr and LLPointer and all
  94. // kinds of better mechanisms. But in this particular source file, we need to
  95. // test nodes managed with plain old dumb pointers as well as nodes managed
  96. // with LLPointer, so we introduce this mechanism.
  97. //
  98. // In the general case, when we declare a Cleanup for some pointer, delete the
  99. // pointer when the Cleanup goes out of scope.
  100. template <typename PTRTYPE>
  101. struct Cleanup
  102. {
  103.     Cleanup(const PTRTYPE& ptr): mPtr(ptr) {}
  104.     ~Cleanup()
  105.     {
  106.         delete mPtr;
  107.     }
  108.     PTRTYPE mPtr;
  109. };
  110. // But when the pointer is an LLPointer<something>, Cleanup is a no-op:
  111. // LLPointer will handle the cleanup automagically.
  112. template <typename NODE>
  113. struct Cleanup< LLPointer<NODE> >
  114. {
  115.     Cleanup(const LLPointer<NODE>& ptr) {}
  116.     ~Cleanup() {}
  117. };
  118. /*****************************************************************************
  119. *   Expected
  120. *****************************************************************************/
  121. // Expected is a base class used to capture the expected results -- a sequence
  122. // of string node names -- from one of our traversals of this example data.
  123. // Its subclasses initialize it with a pair of string iterators. It's not
  124. // strictly necessary to customize Expected to model Boost.Range, it's just
  125. // convenient.
  126. struct Expected
  127. {
  128.     template <typename ITER>
  129.     Expected(ITER begin, ITER end):
  130.         strings(begin, end)
  131.     {}
  132.     /*------ The following are to make Expected work with Boost.Range ------*/
  133.     typedef std::vector<std::string> container_type;
  134.     typedef container_type::iterator iterator;
  135.     typedef container_type::const_iterator const_iterator;
  136.     typedef container_type::size_type size_type;
  137.     container_type strings;
  138.     iterator begin() { return strings.begin(); }
  139.     iterator end()   { return strings.end(); }
  140.     size_type size() { return strings.size(); }
  141.     const_iterator begin() const { return strings.begin(); }
  142.     const_iterator end() const   { return strings.end(); }
  143. };
  144. // We have a couple of generic Expected template subclasses. This list of
  145. // strings is used for the "else" case when all specializations fail.
  146. const char* bad_strings[] = { "FAIL" };
  147. /*****************************************************************************
  148. *   verify()
  149. *****************************************************************************/
  150. // test function: given (an object modeling) a Boost.Range of tree nodes,
  151. // compare the sequence of visited node names with a range of expected name
  152. // strings. Report success both with std::cout output and a bool return. The
  153. // string desc parameter is to identify the different tests.
  154. template <typename NODERANGE, typename STRINGRANGE>
  155. bool verify(const std::string& desc, NODERANGE noderange, STRINGRANGE expected)
  156. {
  157.     typename boost::range_iterator<NODERANGE>::type
  158.         nri = boost::begin(noderange),
  159.         nrend = boost::end(noderange);
  160.     typename boost::range_iterator<STRINGRANGE>::type
  161.         sri = boost::begin(expected),
  162.         srend = boost::end(expected);
  163.     // We choose to loop over both sequences explicitly rather than using
  164.     // std::equal() or std::lexicographical_compare(). The latter tells you
  165.     // whether one sequence is *less* than the other -- it doesn't tell you
  166.     // equality. std::equal() needs you to verify the sequence lengths ahead
  167.     // of time. Anyway, comparing explicitly allows us to report much more
  168.     // information about any sequence mismatch.
  169.     for ( ; nri != nrend && sri != srend; ++nri, ++sri)
  170.     {
  171.         if ((*nri)->name() != *sri)
  172.         {
  173.             std::cout << desc << " mismatch: "
  174.                       << "expected " << *sri << ", got " << (*nri)->name() << "n";
  175.             return false;
  176.         }
  177.     }
  178.     if (nri != nrend)
  179.     {
  180.         std::cout << desc << " produced too many items:n";
  181.         for ( ; nri != nrend; ++nri)
  182.         {
  183.             std::cout << "  " << (*nri)->name() << 'n';
  184.         }
  185.         return false;
  186.     }
  187.     if (sri != srend)
  188.     {
  189.         std::cout << desc << " produced too few items, omitting:n";
  190.         for ( ; sri != srend; ++sri)
  191.         {
  192.             std::cout << "  " << *sri << 'n';
  193.         }
  194.         return false;
  195.     }
  196. //  std::cout << desc << " test passedn";
  197.     return true;
  198. }
  199. /*****************************************************************************
  200. *   PlainNode: LLLinkIter, non-refcounted
  201. *****************************************************************************/
  202. class PlainNode
  203. {
  204. public:
  205.     PlainNode(const std::string& name, PlainNode* next=NULL):
  206.         mName(name),
  207.         mNext(next)
  208.     {}
  209.     ~PlainNode()
  210.     {
  211.         delete mNext;
  212.     }
  213.     std::string name() const { return mName; }
  214.     PlainNode* next() const { return mNext; }
  215. public:                             // if this were 'private', couldn't bind mNext
  216.     PlainNode* mNext;
  217. private:
  218.     std::string mName;
  219. };
  220. namespace tut
  221. {
  222.     template<> template<>
  223.     void iter_object::test<1>()
  224.     {
  225. //      set_test_name("LLLinkedIter -- non-refcounted class");
  226.         PlainNode* last(new PlainNode("c"));
  227.         PlainNode* second(new PlainNode("b", last));
  228.         PlainNode* first(new PlainNode("a", second));
  229.         Cleanup<PlainNode*> cleanup(first);
  230.         static const char* cseq[] = { "a", "b", "c" };
  231.         Expected seq(boost::begin(cseq), boost::end(cseq));
  232.         std::string desc1("Iterate by public link member");
  233. //      std::cout << desc1 << ":n";
  234.         // Try instantiating an iterator with NULL. This test is less about
  235.         // "did we iterate once?" than "did we avoid blowing up?"
  236.         for (LLLinkedIter<PlainNode> pni(NULL, boost::bind(&PlainNode::mNext, _1)), end;
  237.              pni != end; ++pni)
  238.         {
  239. //          std::cout << (*pni)->name() << 'n';
  240.             ensure("LLLinkedIter<PlainNode>(NULL)", false);
  241.         }
  242.         ensure(desc1,
  243.                verify(desc1,
  244.                       boost::make_iterator_range(LLLinkedIter<PlainNode>(first,
  245.                                                                          boost::bind(&PlainNode::mNext, _1)),
  246.                                                  LLLinkedIter<PlainNode>()),
  247.                       seq));
  248.         std::string desc2("Iterate by next() method");
  249. //      std::cout << desc2 << ":n";
  250. //      for (LLLinkedIter<PlainNode> pni(first, boost::bind(&PlainNode::next, _1)); ! (pni == end); ++pni)
  251. //          std::cout << (**pni).name() << 'n';
  252.         ensure(desc2,
  253.                verify(desc2,
  254.                       boost::make_iterator_range(LLLinkedIter<PlainNode>(first,
  255.                                                                          boost::bind(&PlainNode::next, _1)),
  256.                                                  LLLinkedIter<PlainNode>()),
  257.                       seq));
  258.         {
  259. //          LLLinkedIter<PlainNode> pni(first, boost::bind(&PlainNode::next, _1));
  260. //          std::cout << "First  is " << (*pni++)->name() << 'n';
  261. //          std::cout << "Second is " << (*pni  )->name() << 'n';
  262.         }
  263.         {
  264.             LLLinkedIter<PlainNode> pni(first, boost::bind(&PlainNode::next, _1));
  265.             ensure_equals("first",  (*pni++)->name(), "a");
  266.             ensure_equals("second", (*pni  )->name(), "b");
  267.         }
  268.     }
  269. } // tut
  270. /*****************************************************************************
  271. *   RCNode: LLLinkIter, refcounted
  272. *****************************************************************************/
  273. class RCNode;
  274. typedef LLPointer<RCNode> RCNodePtr;
  275. class RCNode: public LLRefCount
  276. {
  277. public:
  278.     RCNode(const std::string& name, const RCNodePtr& next=RCNodePtr()):
  279.         mName(name),
  280.         mNext(next)
  281.     {
  282. //      std::cout << "New  RCNode(" << mName << ")n";
  283.     }
  284.     RCNode(const RCNode& that):
  285.         mName(that.mName),
  286.         mNext(that.mNext)
  287.     {
  288. //      std::cout << "Copy RCNode(" << mName << ")n";
  289.     }
  290.     virtual ~RCNode();
  291.     std::string name() const { return mName; }
  292.     RCNodePtr next() const { return mNext; }
  293. public:                             // if this were 'private', couldn't bind mNext
  294.     RCNodePtr mNext;
  295. private:
  296.     std::string mName;
  297. };
  298. std::ostream& operator<<(std::ostream& out, const RCNode& node)
  299. {
  300.     out << "RCNode(" << node.name() << ')';
  301.     return out;
  302. }
  303. // This string contains the node name of the last RCNode destroyed. We use it
  304. // to validate that LLLinkedIter<RCNode> in fact contains LLPointer<RCNode>,
  305. // and that therefore an outstanding LLLinkedIter to an instance of a
  306. // refcounted class suffices to keep that instance alive.
  307. std::string last_RCNode_destroyed;
  308. RCNode::~RCNode()
  309. {
  310. //  std::cout << "Kill " << *this << "n";
  311.     last_RCNode_destroyed = mName;
  312. }
  313. namespace tut
  314. {
  315.     template<> template<>
  316.     void iter_object::test<2>()
  317.     {
  318. //      set_test_name("LLLinkedIter -- refcounted class");
  319.         LLLinkedIter<RCNode> rcni, end2;
  320.         {
  321. //          ScopeLabel label("inner scope");
  322.             RCNodePtr head(new RCNode("x", new RCNode("y", new RCNode("z"))));
  323. //          for (rcni = LLLinkedIter<RCNode>(head, boost::bind(&RCNode::mNext, _1)); rcni != end2; ++rcni)
  324. //              std::cout << **rcni << 'n';
  325.             rcni = LLLinkedIter<RCNode>(head, boost::bind(&RCNode::next, _1));
  326.         }
  327. //      std::cout << "Now the LLLinkedIter<RCNode> is the only remaining reference to RCNode chainn";
  328.         ensure_equals(last_RCNode_destroyed, "");
  329.         ensure(rcni != end2);
  330.         ensure_equals((*rcni)->name(), "x");
  331.         ++rcni;
  332.         ensure_equals(last_RCNode_destroyed, "x");
  333.         ensure(rcni != end2);
  334.         ensure_equals((*rcni)->name(), "y");
  335.         ++rcni;
  336.         ensure_equals(last_RCNode_destroyed, "y");
  337.         ensure(rcni != end2);
  338.         ensure_equals((*rcni)->name(), "z");
  339.         ++rcni;
  340.         ensure_equals(last_RCNode_destroyed, "z");
  341.         ensure(rcni == end2);
  342.     }
  343. }
  344. /*****************************************************************************
  345. *   TreeNode
  346. *****************************************************************************/
  347. class TreeNode;
  348. typedef LLPointer<TreeNode> TreeNodePtr;
  349. /**
  350.  * TreeNode represents a refcounted tree-node class that hasn't (yet) been
  351.  * modified to incorporate LLTreeIter methods. This illustrates how you can
  352.  * use tree iterators either standalone, or with free functions.
  353.  */
  354. class TreeNode: public LLRefCount
  355. {
  356. public:
  357.     typedef std::vector<TreeNodePtr> list_type;
  358.     typedef list_type::const_iterator child_iterator;
  359.     // To avoid cycles, use a "weak" raw pointer for the parent link
  360.     TreeNode(const std::string& name, TreeNode* parent=0):
  361.         mParent(parent),
  362.         mName(name)
  363.     {}
  364.     TreeNodePtr newChild(const std::string& name)
  365.     {
  366.         TreeNodePtr child(new TreeNode(name, this));
  367.         mChildren.push_back(child);
  368.         return child;
  369.     }
  370.     std::string name() const { return mName; }
  371.     TreeNodePtr getParent() const { return mParent; }
  372.     child_iterator child_begin() const { return mChildren.begin(); }
  373.     child_iterator child_end() const   { return mChildren.end(); }
  374. private:
  375.     std::string mName;
  376.     // To avoid cycles, use a "weak" raw pointer for the parent link
  377.     TreeNode* mParent;
  378.     list_type mChildren;
  379. };
  380. /**
  381.  * This is an example of a helper function to facilitate iterating from a
  382.  * TreeNode up to the root or down from the root (see LLTreeIter::RootIter).
  383.  *
  384.  * Example:
  385.  * @code
  386.  * BOOST_FOREACH(TreeNodePtr node, getRootRange<LLTreeIter::UP>(somenode))
  387.  * {
  388.  *     std::cout << node->name() << 'n';
  389.  * }
  390.  * @endcode
  391.  */
  392. template <LLTreeIter::RootIter DISCRIM>
  393. boost::iterator_range< LLTreeRootIter<DISCRIM, TreeNode> >
  394. getRootRange(const TreeNodePtr& node)
  395. {
  396.     typedef LLTreeRootIter<DISCRIM, TreeNode> iter_type;
  397.     typedef boost::iterator_range<iter_type> range_type;
  398.     return range_type(iter_type(node, boost::bind(&TreeNode::getParent, _1)),
  399.                       iter_type());
  400. }
  401. /**
  402.  * This is an example of a helper function to facilitate walking a given
  403.  * TreeNode's subtree in any supported order (see LLTreeIter::WalkIter).
  404.  *
  405.  * Example:
  406.  * @code
  407.  * BOOST_FOREACH(TreeNodePtr node, getWalkRange<LLTreeIter::DFS_PRE>(root))
  408.  * {
  409.  *     std::cout << node->name() << 'n';
  410.  * }
  411.  * @endcode
  412.  */
  413. template <LLTreeIter::WalkIter DISCRIM>
  414. boost::iterator_range< LLTreeWalkIter<DISCRIM, TreeNode, TreeNode::child_iterator> >
  415. getWalkRange(const TreeNodePtr& node)
  416. {
  417.     typedef LLTreeWalkIter<DISCRIM, TreeNode, TreeNode::child_iterator> iter_type;
  418.     typedef boost::iterator_range<iter_type> range_type;
  419.     return range_type(iter_type(node,
  420.                                 boost::bind(&TreeNode::child_begin, _1),
  421.                                 boost::bind(&TreeNode::child_end, _1)),
  422.                       iter_type());
  423. }
  424. /*****************************************************************************
  425. *   EnhancedTreeNode
  426. *****************************************************************************/
  427. class EnhancedTreeNode;
  428. typedef LLPointer<EnhancedTreeNode> EnhancedTreeNodePtr;
  429. /**
  430.  * More typically, you enhance the tree-node class itself with template
  431.  * methods like the above. This EnhancedTreeNode class illustrates the
  432.  * technique. Normally, of course, you'd simply add these methods to TreeNode;
  433.  * we put them in a separate class to preserve the undecorated TreeNode class
  434.  * to illustrate (and test) the use of plain tree iterators and standalone
  435.  * helper functions.
  436.  *
  437.  * We originally implemented EnhancedTreeNode as a subclass of TreeNode -- but
  438.  * because TreeNode stores and manipulates TreeNodePtrs and TreeNode*s,
  439.  * reusing its methods required so much ugly downcast logic that we gave up
  440.  * and restated the whole class. Bear in mind that logically these aren't two
  441.  * separate classes; logically they're two snapshots of the @em same class at
  442.  * different moments in time.
  443.  */
  444. class EnhancedTreeNode: public LLRefCount
  445. {
  446. public:
  447.     /*-------------- The following is restated from TreeNode ---------------*/
  448.     typedef std::vector<EnhancedTreeNodePtr> list_type;
  449.     typedef list_type::const_iterator child_iterator;
  450.     // To avoid cycles, use a "weak" raw pointer for the parent link
  451.     EnhancedTreeNode(const std::string& name, EnhancedTreeNode* parent=0):
  452.         mParent(parent),
  453.         mName(name)
  454.     {}
  455.     EnhancedTreeNodePtr newChild(const std::string& name)
  456.     {
  457.         EnhancedTreeNodePtr child(new EnhancedTreeNode(name, this));
  458.         mChildren.push_back(child);
  459.         return child;
  460.     }
  461.     std::string name() const { return mName; }
  462.     EnhancedTreeNodePtr getParent() const { return mParent; }
  463.     child_iterator child_begin() const { return mChildren.begin(); }
  464.     child_iterator child_end() const   { return mChildren.end(); }
  465. private:
  466.     std::string mName;
  467.     // To avoid cycles, use a "weak" raw pointer for the parent link
  468.     EnhancedTreeNode* mParent;
  469.     list_type mChildren;
  470. public:
  471.     /*----- End of TreeNode; what follows is new with EnhancedTreeNode -----*/
  472.     /**
  473.      * Because the type of the iterator range returned by getRootRange()
  474.      * depends on the discriminator enum value, instead of a simple typedef we
  475.      * use a templated struct. Example usage:
  476.      *
  477.      * @code
  478.      * for (EnhancedTreeNode::root_range<LLTreeIter::UP>::type range =
  479.      *      somenode->getRootRange<LLTreeIter::UP>();
  480.      *      range.first != range.second; ++range.first)
  481.      * {
  482.      *     std::cout << (*range.first)->name() << 'n';
  483.      * }
  484.      * @endcode
  485.      */
  486.     template <LLTreeIter::RootIter DISCRIM>
  487.     struct root_range
  488.     {
  489.         typedef boost::iterator_range< LLTreeRootIter<DISCRIM, EnhancedTreeNode> > type;
  490.     };
  491.     /**
  492.      * Helper method for walking up to (or down from) the tree root. See
  493.      * LLTreeIter::RootIter.
  494.      *
  495.      * Example usage:
  496.      * @code
  497.      * BOOST_FOREACH(EnhancedTreeNodePtr node, somenode->getRootRange<LLTreeIter::UP>())
  498.      * {
  499.      *     std::cout << node->name() << 'n';
  500.      * }
  501.      * @endcode
  502.      */
  503.     template <LLTreeIter::RootIter DISCRIM>
  504.     typename root_range<DISCRIM>::type getRootRange() const
  505.     {
  506.         typedef typename root_range<DISCRIM>::type range_type;
  507.         typedef typename range_type::iterator iter_type;
  508.         return range_type(iter_type(const_cast<EnhancedTreeNode*>(this),
  509.                                     boost::bind(&EnhancedTreeNode::getParent, _1)),
  510.                           iter_type());
  511.     }
  512.     /**
  513.      * Because the type of the iterator range returned by getWalkRange()
  514.      * depends on the discriminator enum value, instead of a simple typedef we
  515.      * use a templated stuct. Example usage:
  516.      *
  517.      * @code
  518.      * for (EnhancedTreeNode::walk_range<LLTreeIter::DFS_PRE>::type range =
  519.      *      somenode->getWalkRange<LLTreeIter::DFS_PRE>();
  520.      *      range.first != range.second; ++range.first)
  521.      * {
  522.      *     std::cout << (*range.first)->name() << 'n';
  523.      * }
  524.      * @endcode
  525.      */
  526.     template <LLTreeIter::WalkIter DISCRIM>
  527.     struct walk_range
  528.     {
  529.         typedef boost::iterator_range< LLTreeWalkIter<DISCRIM,
  530.                                                       EnhancedTreeNode,
  531.                                                       EnhancedTreeNode::child_iterator> > type;
  532.     };
  533.     /**
  534.      * Helper method for walking a given node's subtree in any supported
  535.      * order (see LLTreeIter::WalkIter).
  536.      *
  537.      * Example usage:
  538.      * @code
  539.      * BOOST_FOREACH(EnhancedTreeNodePtr node, somenode->getWalkRange<LLTreeIter::DFS_PRE>())
  540.      * {
  541.      *     std::cout << node->name() << 'n';
  542.      * }
  543.      * @endcode
  544.      */
  545.     template <LLTreeIter::WalkIter DISCRIM>
  546.     typename walk_range<DISCRIM>::type getWalkRange() const
  547.     {
  548.         typedef typename walk_range<DISCRIM>::type range_type;
  549.         typedef typename range_type::iterator iter_type;
  550.         return range_type(iter_type(const_cast<EnhancedTreeNode*>(this),
  551.                                     boost::bind(&EnhancedTreeNode::child_begin, _1),
  552.                                     boost::bind(&EnhancedTreeNode::child_end, _1)),
  553.                           iter_type());
  554.     }
  555. };
  556. /*****************************************************************************
  557. *   PlainTree
  558. *****************************************************************************/
  559. struct PlainTree
  560. {
  561.     PlainTree(const std::string& name, PlainTree* parent=0):
  562.         mName(name),
  563.         mParent(parent),
  564.         mNextSibling(0),
  565.         mFirstChild(0)
  566.     {
  567.         mLastChildLink = &mFirstChild;
  568.     }
  569.     ~PlainTree()
  570.     {
  571.         delete mNextSibling;
  572.         delete mFirstChild;
  573.     }
  574.     PlainTree* newChild(const std::string& name)
  575.     {
  576.         PlainTree* child(new PlainTree(name, this));
  577.         *mLastChildLink = child;
  578.         mLastChildLink = &child->mNextSibling;
  579.         return child;
  580.     }
  581.     std::string name() const { return mName; }
  582.     std::string mName;
  583.     PlainTree* mParent;
  584.     PlainTree* mNextSibling;
  585.     PlainTree* mFirstChild;
  586.     PlainTree** mLastChildLink;
  587. };
  588. // This "classic" tree tracks each node's children with a linked list anchored
  589. // at the parent's mFirstChild and linked through each child's mNextSibling.
  590. // LLTreeDFSIter<> and LLTreeBFSIter<> need functors to return begin()/end()
  591. // iterators over a given node's children. But because this tree's children
  592. // aren't stored in an STL container, we can't just export that container's
  593. // begin()/end(). Instead we'll use LLLinkedIter<> to view the hand-maintained
  594. // linked list as an iterator range. The straightforward way to do that would
  595. // be to add child_begin() and child_end() methods. But let's say (for the
  596. // sake of argument) that this struct is so venerable we don't dare modify it
  597. // even to add new methods. Well, we can use free functions (or functors) too.
  598. LLLinkedIter<PlainTree> PlainTree_child_begin(PlainTree* node)
  599. {
  600.     return LLLinkedIter<PlainTree>(node->mFirstChild, boost::bind(&PlainTree::mNextSibling, _1));
  601. }
  602. LLLinkedIter<PlainTree> PlainTree_child_end(PlainTree* node)
  603. {
  604.     return LLLinkedIter<PlainTree>();
  605. }
  606. /**
  607.  * This is an example of a helper function to facilitate iterating from a
  608.  * PlainTree up to the root or down from the root (see LLTreeIter::RootIter).
  609.  * Note that we're simply overloading the same getRootRange() helper function
  610.  * name we used for TreeNode.
  611.  *
  612.  * Example:
  613.  * @code
  614.  * BOOST_FOREACH(PlainTree* node, getRootRange<LLTreeIter::UP>(somenode))
  615.  * {
  616.  *     std::cout << node->name() << 'n';
  617.  * }
  618.  * @endcode
  619.  */
  620. template <LLTreeIter::RootIter DISCRIM>
  621. boost::iterator_range< LLTreeRootIter<DISCRIM, PlainTree> >
  622. getRootRange(PlainTree* node)
  623. {
  624.     typedef LLTreeRootIter<DISCRIM, PlainTree> iter_type;
  625.     typedef boost::iterator_range<iter_type> range_type;
  626.     return range_type(iter_type(node, boost::bind(&PlainTree::mParent, _1)),
  627.                       iter_type());
  628. }
  629. /**
  630.  * This is an example of a helper function to facilitate walking a given
  631.  * PlainTree's subtree in any supported order (see LLTreeIter::WalkIter). Note
  632.  * that we're simply overloading the same getWalkRange() helper function name
  633.  * we used for TreeNode.
  634.  *
  635.  * Example:
  636.  * @code
  637.  * BOOST_FOREACH(PlainTree* node, getWalkRange<LLTreeIter::DFS_PRE>(root))
  638.  * {
  639.  *     std::cout << node->name() << 'n';
  640.  * }
  641.  * @endcode
  642.  */
  643. template <LLTreeIter::WalkIter DISCRIM>
  644. boost::iterator_range< LLTreeWalkIter<DISCRIM, PlainTree, LLLinkedIter<PlainTree> > >
  645. getWalkRange(PlainTree* node)
  646. {
  647.     typedef LLTreeWalkIter<DISCRIM, PlainTree, LLLinkedIter<PlainTree> > iter_type;
  648.     typedef boost::iterator_range<iter_type> range_type;
  649.     return range_type(iter_type(node,
  650.                                 PlainTree_child_begin,
  651.                                 PlainTree_child_end),
  652.                       iter_type());
  653. }
  654. // We could go through the exercise of writing EnhancedPlainTree containing
  655. // root_range, getRootRange(), walk_range and getWalkRange() members -- but we
  656. // won't. See EnhancedTreeNode for examples.
  657. /*****************************************************************************
  658. *   Generic tree test data
  659. *****************************************************************************/
  660. template <class NODE>
  661. typename LLPtrTo<NODE>::type example_tree()
  662. {
  663.     typedef typename LLPtrTo<NODE>::type NodePtr;
  664.     NodePtr root(new NODE("root"));
  665.     NodePtr A(root->newChild("A"));
  666.     NodePtr A1(A->newChild("A1"));
  667. /*  NodePtr A1a*/(A1->newChild("A1a"));
  668. /*  NodePtr A1b*/(A1->newChild("A1b"));
  669. /*  NodePtr A1c*/(A1->newChild("A1c"));
  670.     NodePtr A2(A->newChild("A2"));
  671. /*  NodePtr A2a*/(A2->newChild("A2a"));
  672. /*  NodePtr A2b*/(A2->newChild("A2b"));
  673. /*  NodePtr A2c*/(A2->newChild("A2c"));
  674.     NodePtr A3(A->newChild("A3"));
  675. /*  NodePtr A3a*/(A3->newChild("A3a"));
  676. /*  NodePtr A3b*/(A3->newChild("A3b"));
  677. /*  NodePtr A3c*/(A3->newChild("A3c"));
  678.     NodePtr B(root->newChild("B"));
  679.     NodePtr B1(B->newChild("B1"));
  680. /*  NodePtr B1a*/(B1->newChild("B1a"));
  681. /*  NodePtr B1b*/(B1->newChild("B1b"));
  682. /*  NodePtr B1c*/(B1->newChild("B1c"));
  683.     NodePtr B2(B->newChild("B2"));
  684. /*  NodePtr B2a*/(B2->newChild("B2a"));
  685. /*  NodePtr B2b*/(B2->newChild("B2b"));
  686. /*  NodePtr B2c*/(B2->newChild("B2c"));
  687.     NodePtr B3(B->newChild("B3"));
  688. /*  NodePtr B3a*/(B3->newChild("B3a"));
  689. /*  NodePtr B3b*/(B3->newChild("B3b"));
  690. /*  NodePtr B3c*/(B3->newChild("B3c"));
  691.     NodePtr C(root->newChild("C"));
  692.     NodePtr C1(C->newChild("C1"));
  693. /*  NodePtr C1a*/(C1->newChild("C1a"));
  694. /*  NodePtr C1b*/(C1->newChild("C1b"));
  695. /*  NodePtr C1c*/(C1->newChild("C1c"));
  696.     NodePtr C2(C->newChild("C2"));
  697. /*  NodePtr C2a*/(C2->newChild("C2a"));
  698. /*  NodePtr C2b*/(C2->newChild("C2b"));
  699. /*  NodePtr C2c*/(C2->newChild("C2c"));
  700.     NodePtr C3(C->newChild("C3"));
  701. /*  NodePtr C3a*/(C3->newChild("C3a"));
  702. /*  NodePtr C3b*/(C3->newChild("C3b"));
  703. /*  NodePtr C3c*/(C3->newChild("C3c"));
  704.     return root;
  705. }
  706. // WalkExpected<WalkIter> is the list of string node names we expect from a
  707. // WalkIter traversal of our example_tree() data.
  708. template <LLTreeIter::WalkIter DISCRIM>
  709. struct WalkExpected: public Expected
  710. {
  711.     // Initialize with bad_strings: we don't expect to use this generic case,
  712.     // only the specializations. Note that for a classic C-style array we must
  713.     // pass a pair of iterators rather than extracting boost::begin() and
  714.     // boost::end() within the target constructor: a template ctor accepts
  715.     // these classic C-style arrays as char** rather than char*[length]. Oh well.
  716.     WalkExpected(): Expected(boost::begin(bad_strings), boost::end(bad_strings)) {}
  717. };
  718. // list of string node names we expect from traversing example_tree() in
  719. // DFS_PRE order
  720. const char* dfs_pre_strings[] =
  721. {
  722.     "root",
  723.     "A",
  724.     "A1",
  725.     "A1a",
  726.     "A1b",
  727.     "A1c",
  728.     "A2",
  729.     "A2a",
  730.     "A2b",
  731.     "A2c",
  732.     "A3",
  733.     "A3a",
  734.     "A3b",
  735.     "A3c",
  736.     "B",
  737.     "B1",
  738.     "B1a",
  739.     "B1b",
  740.     "B1c",
  741.     "B2",
  742.     "B2a",
  743.     "B2b",
  744.     "B2c",
  745.     "B3",
  746.     "B3a",
  747.     "B3b",
  748.     "B3c",
  749.     "C",
  750.     "C1",
  751.     "C1a",
  752.     "C1b",
  753.     "C1c",
  754.     "C2",
  755.     "C2a",
  756.     "C2b",
  757.     "C2c",
  758.     "C3",
  759.     "C3a",
  760.     "C3b",
  761.     "C3c"
  762. };
  763. // specialize WalkExpected<DFS_PRE> with the expected strings
  764. template <>
  765. struct WalkExpected<LLTreeIter::DFS_PRE>: public Expected
  766. {
  767.     WalkExpected(): Expected(boost::begin(dfs_pre_strings), boost::end(dfs_pre_strings)) {}
  768. };
  769. // list of string node names we expect from traversing example_tree() in
  770. // DFS_POST order
  771. const char* dfs_post_strings[] =
  772. {
  773.     "A1a",
  774.     "A1b",
  775.     "A1c",
  776.     "A1",
  777.     "A2a",
  778.     "A2b",
  779.     "A2c",
  780.     "A2",
  781.     "A3a",
  782.     "A3b",
  783.     "A3c",
  784.     "A3",
  785.     "A",
  786.     "B1a",
  787.     "B1b",
  788.     "B1c",
  789.     "B1",
  790.     "B2a",
  791.     "B2b",
  792.     "B2c",
  793.     "B2",
  794.     "B3a",
  795.     "B3b",
  796.     "B3c",
  797.     "B3",
  798.     "B",
  799.     "C1a",
  800.     "C1b",
  801.     "C1c",
  802.     "C1",
  803.     "C2a",
  804.     "C2b",
  805.     "C2c",
  806.     "C2",
  807.     "C3a",
  808.     "C3b",
  809.     "C3c",
  810.     "C3",
  811.     "C",
  812.     "root"
  813. };
  814. // specialize WalkExpected<DFS_POST> with the expected strings
  815. template <>
  816. struct WalkExpected<LLTreeIter::DFS_POST>: public Expected
  817. {
  818.     WalkExpected(): Expected(boost::begin(dfs_post_strings), boost::end(dfs_post_strings)) {}
  819. };
  820. // list of string node names we expect from traversing example_tree() in BFS order
  821. const char* bfs_strings[] =
  822. {
  823.     "root",
  824.     "A",
  825.     "B",
  826.     "C",
  827.     "A1",
  828.     "A2",
  829.     "A3",
  830.     "B1",
  831.     "B2",
  832.     "B3",
  833.     "C1",
  834.     "C2",
  835.     "C3",
  836.     "A1a",
  837.     "A1b",
  838.     "A1c",
  839.     "A2a",
  840.     "A2b",
  841.     "A2c",
  842.     "A3a",
  843.     "A3b",
  844.     "A3c",
  845.     "B1a",
  846.     "B1b",
  847.     "B1c",
  848.     "B2a",
  849.     "B2b",
  850.     "B2c",
  851.     "B3a",
  852.     "B3b",
  853.     "B3c",
  854.     "C1a",
  855.     "C1b",
  856.     "C1c",
  857.     "C2a",
  858.     "C2b",
  859.     "C2c",
  860.     "C3a",
  861.     "C3b",
  862.     "C3c"
  863. };
  864. // specialize WalkExpected<BFS> with the expected strings
  865. template <>
  866. struct WalkExpected<LLTreeIter::BFS>: public Expected
  867. {
  868.     WalkExpected(): Expected(boost::begin(bfs_strings), boost::end(bfs_strings)) {}
  869. };
  870. // extract a particular "arbitrary" node from the example_tree() data: the
  871. // second (middle) node at each child level
  872. template <class NODE, typename CHILDITER>
  873. typename LLPtrTo<NODE>::type
  874. get_B2b(const typename LLPtrTo<NODE>::type& root,
  875.         const boost::function<CHILDITER(const typename LLPtrTo<NODE>::type&)>& child_begin)
  876. {
  877.     typedef typename LLPtrTo<NODE>::type NodePtr;
  878.     CHILDITER Bi(child_begin(root));
  879.     ++Bi;
  880.     NodePtr B(*Bi);
  881.     CHILDITER B2i(child_begin(B));
  882.     ++B2i;
  883.     NodePtr B2(*B2i);
  884.     CHILDITER B2bi(child_begin(B2));
  885.     ++B2bi;
  886.     NodePtr B2b(*B2bi);
  887.     return B2b;
  888. }
  889. // RootExpected<RootIter> is the list of string node names we expect from a
  890. // RootIter traversal of our example_tree() data.
  891. template <LLTreeIter::RootIter DISCRIM>
  892. struct RootExpected: public Expected
  893. {
  894.     // Initialize with bad_strings: we don't expect to use this generic case,
  895.     // only the specializations.
  896.     RootExpected(): Expected(boost::begin(bad_strings), boost::end(bad_strings)) {}
  897. };
  898. // list of string node names we expect from traversing UP from
  899. // example_tree()'s B2b node
  900. const char* up_from_B2b[] =
  901. {
  902.     "B2b",
  903.     "B2",
  904.     "B",
  905.     "root"
  906. };
  907. // specialize RootExpected<UP> with the expected strings
  908. template <>
  909. struct RootExpected<LLTreeIter::UP>: public Expected
  910. {
  911.     RootExpected(): Expected(boost::begin(up_from_B2b), boost::end(up_from_B2b)) {}
  912. };
  913. // list of string node names we expect from traversing DOWN to
  914. // example_tree()'s B2b node
  915. const char* down_to_B2b[] =
  916. {
  917.     "root",
  918.     "B",
  919.     "B2",
  920.     "B2b"
  921. };
  922. // specialize RootExpected<DOWN> with the expected strings
  923. template <>
  924. struct RootExpected<LLTreeIter::DOWN>: public Expected
  925. {
  926.     RootExpected(): Expected(boost::begin(down_to_B2b), boost::end(down_to_B2b)) {}
  927. };
  928. /*****************************************************************************
  929. *   Generic tree test functions
  930. *****************************************************************************/
  931. template<LLTreeIter::RootIter DISCRIM, class NODE, typename PARENTFUNC>
  932. bool LLTreeRootIter_test(const std::string& itername, const std::string& nodename,
  933.                          const typename LLPtrTo<NODE>::type& node,
  934.                          PARENTFUNC parentfunc)
  935. {
  936.     std::ostringstream desc;
  937.     desc << itername << '<' << nodename << "> from " << node->name();
  938.     if (!  verify(desc.str(),
  939.                   boost::make_iterator_range(LLTreeRootIter<DISCRIM, NODE>(node, parentfunc),
  940.                                              LLTreeRootIter<DISCRIM, NODE>()),
  941.                   RootExpected<DISCRIM>()))
  942.         return false;
  943. //  std::cout << desc.str() << 'n';
  944.     // Try instantiating an iterator with NULL (that is, a default-constructed
  945.     // node pointer). This test is less about "did we iterate once?" than "did
  946.     // we avoid blowing up?"
  947.     for (LLTreeRootIter<DISCRIM, NODE> hri = LLTreeRootIter<DISCRIM, NODE>(typename LLPtrTo<NODE>::type(), parentfunc), hrend;
  948.          hri != hrend; /* ++hri */) // incrementing is moot, and MSVC complains
  949.     {
  950. //      std::cout << nodename << '(' << (*hri)->name() << ")n";
  951.         std::cout << itername << '<' << nodename << ">(NULL)n";
  952.         return false;
  953.     }
  954.     return true;
  955. }
  956. template<class NODE, typename CHILDITER, typename PARENTFUNC, typename CHILDFUNC>
  957. bool LLTreeUpIter_test(const std::string& nodename, PARENTFUNC parentfunc, CHILDFUNC childfunc)
  958. {
  959.     bool success = true;
  960.     typedef typename LLPtrTo<NODE>::type ptr_type;
  961.     ptr_type root(example_tree<NODE>());
  962.     Cleanup<ptr_type> cleanup(root);
  963.     ptr_type B2b(get_B2b<NODE, CHILDITER>(root, childfunc));
  964.     if (! LLTreeRootIter_test<LLTreeIter::UP,   NODE>("LLTreeUpIter",   nodename, B2b, parentfunc))
  965.         success = false;
  966.     if (! LLTreeRootIter_test<LLTreeIter::DOWN, NODE>("LLTreeDownIter", nodename, B2b, parentfunc))
  967.         success = false;
  968.     return success;
  969. }
  970. template <LLTreeIter::WalkIter DISCRIM, class NODE, typename CHILDITER,
  971.           typename CHILDBEGINFUNC, typename CHILDENDFUNC>
  972. bool LLTreeWalkIter_test(const std::string& itername, const std::string& nodename,
  973.                       CHILDBEGINFUNC childbegin, CHILDENDFUNC childend)
  974. {
  975.     typename LLPtrTo<NODE>::type root(example_tree<NODE>());
  976.     Cleanup<typename LLPtrTo<NODE>::type> cleanup(root);
  977.     std::ostringstream desc;
  978.     desc << itername << '<' << nodename << "> from " << root->name();
  979.     if (!  verify(desc.str(),
  980.                   boost::make_iterator_range(LLTreeWalkIter<DISCRIM, NODE, CHILDITER>(root,
  981.                                                                                       childbegin,
  982.                                                                                       childend),
  983.                                              LLTreeWalkIter<DISCRIM, NODE, CHILDITER>()),
  984.                   WalkExpected<DISCRIM>()))
  985.         return false;
  986.     // Try instantiating an iterator with NULL (that is, a default-constructed
  987.     // node pointer). This test is less about "did we iterate once?" than "did
  988.     // we avoid blowing up?"
  989.     for (LLTreeWalkIter<DISCRIM, NODE, CHILDITER> twi = LLTreeWalkIter<DISCRIM, NODE, CHILDITER>(typename LLPtrTo<NODE>::type(),
  990.                                                       childbegin,
  991.                                                       childend),
  992.                                                   twend;
  993.          twi != twend; /* ++twi */) // incrementing is moot, and MSVC complains
  994.     {
  995.         std::cout << itername << '<' << nodename << ">(NULL)n";
  996.         return false;
  997.     }             
  998.     return true;
  999. }
  1000. template <class NODE, typename CHILDITER,
  1001.           typename PARENTFUNC, typename CHILDBEGINFUNC, typename CHILDENDFUNC>
  1002. bool LLTreeIter_tests(const std::string& nodename,
  1003.                       PARENTFUNC parentfunc, CHILDBEGINFUNC childbegin, CHILDENDFUNC childend)
  1004. {
  1005.     bool success = true;
  1006.     if (! LLTreeUpIter_test<NODE, CHILDITER>(nodename, parentfunc, childbegin))
  1007.         success = false;
  1008. /*==========================================================================*|
  1009.     LLTreeIter_test<NODE, LLTreeDFSIter<NODE, CHILDITER> >("LLTreeDFSIter", nodename,
  1010.                                                            childbegin, childend);
  1011.     LLTreeIter_test<NODE, LLTreeDFSPostIter<NODE, CHILDITER> >("LLTreeDFSPostIter", nodename,
  1012.                                                                childbegin, childend);
  1013.     LLTreeIter_test<NODE, LLTreeBFSIter<NODE, CHILDITER> >("LLTreeBFSIter", nodename,
  1014.                                                            childbegin, childend);
  1015. |*==========================================================================*/
  1016.     if (! LLTreeWalkIter_test<LLTreeIter::DFS_PRE,  NODE, CHILDITER>("LLTreeDFSIter", nodename,
  1017.                                                                      childbegin, childend))
  1018.         success = false;
  1019.     if (! LLTreeWalkIter_test<LLTreeIter::DFS_POST, NODE, CHILDITER>("LLTreeDFSPostIter", nodename,
  1020.                                                                      childbegin, childend))
  1021.         success = false;
  1022.     if (! LLTreeWalkIter_test<LLTreeIter::BFS,      NODE, CHILDITER>("LLTreeBFSIter", nodename,
  1023.                                                                      childbegin, childend))
  1024.         success = false;
  1025.     return success;
  1026. }
  1027. namespace tut
  1028. {
  1029.     template<> template<>
  1030.     void iter_object::test<3>()
  1031.     {
  1032. //      set_test_name("LLTreeIter tests");
  1033.         ensure(LLTreeIter_tests<TreeNode, TreeNode::child_iterator>
  1034.                                ("TreeNode",
  1035.                                 boost::bind(&TreeNode::getParent, _1),
  1036.                                 boost::bind(&TreeNode::child_begin, _1),
  1037.                                 boost::bind(&TreeNode::child_end, _1)));
  1038.         ensure(LLTreeIter_tests<PlainTree, LLLinkedIter<PlainTree> >
  1039.                                ("PlainTree",
  1040.                                 boost::bind(&PlainTree::mParent, _1),
  1041.                                 PlainTree_child_begin,
  1042.                                 PlainTree_child_end));
  1043.     }
  1044.     template<> template<>
  1045.     void iter_object::test<4>()
  1046.     {
  1047. //      set_test_name("getRootRange() tests");
  1048.         // This test function illustrates the looping techniques described in the
  1049.         // comments for the getRootRange() free function, the
  1050.         // EnhancedTreeNode::root_range template and the
  1051.         // EnhancedTreeNode::getRootRange() method. Obviously the BOOST_FOREACH()
  1052.         // forms are more succinct.
  1053.         TreeNodePtr tnroot(example_tree<TreeNode>());
  1054.         TreeNodePtr tnB2b(get_B2b<TreeNode, TreeNode::child_iterator>
  1055.                           (tnroot, boost::bind(&TreeNode::child_begin, _1)));
  1056.     
  1057.         std::string desc1("BOOST_FOREACH(TreeNodePr, getRootRange<LLTreeIter::UP>(tnB2b))");
  1058. //      std::cout << desc1 << "n";
  1059.         // Although we've commented out the output statement, ensure that the
  1060.         // loop construct is still valid, as promised by the getRootRange()
  1061.         // documentation.
  1062.         BOOST_FOREACH(TreeNodePtr node, getRootRange<LLTreeIter::UP>(tnB2b))
  1063.         {
  1064. //          std::cout << node->name() << 'n';
  1065.         }
  1066.         ensure(desc1,
  1067.                verify(desc1, getRootRange<LLTreeIter::UP>(tnB2b), RootExpected<LLTreeIter::UP>()));
  1068.         EnhancedTreeNodePtr etnroot(example_tree<EnhancedTreeNode>());
  1069.         EnhancedTreeNodePtr etnB2b(get_B2b<EnhancedTreeNode, EnhancedTreeNode::child_iterator>
  1070.                                    (etnroot, boost::bind(&EnhancedTreeNode::child_begin, _1)));
  1071. //      std::cout << "EnhancedTreeNode::root_range<LLTreeIter::DOWN>::type range =n"
  1072. //                << "    etnB2b->getRootRange<LLTreeIter::DOWN>();n"
  1073. //                << "for (EnhancedTreeNode::root_range<LLTreeIter::DOWN>::type::iterator ri = range.begin();n"
  1074. //                << "     ri != range.end(); ++ri)n";
  1075.         EnhancedTreeNode::root_range<LLTreeIter::DOWN>::type range =
  1076.             etnB2b->getRootRange<LLTreeIter::DOWN>();
  1077.         for (EnhancedTreeNode::root_range<LLTreeIter::DOWN>::type::iterator ri = range.begin();
  1078.              ri != range.end(); ++ri)
  1079.         {
  1080. //          std::cout << (*ri)->name() << 'n';
  1081.         }
  1082.         std::string desc2("BOOST_FOREACH(EnhancedTreeNodePtr node, etnB2b->getRootRange<LLTreeIter::UP>())");
  1083. //      std::cout << desc2 << 'n';
  1084.         BOOST_FOREACH(EnhancedTreeNodePtr node, etnB2b->getRootRange<LLTreeIter::UP>())
  1085.         {
  1086. //          std::cout << node->name() << 'n';
  1087.         }
  1088.         ensure(desc2,
  1089.                verify(desc2, etnB2b->getRootRange<LLTreeIter::UP>(), RootExpected<LLTreeIter::UP>()));
  1090.     }
  1091.     template<> template<>
  1092.     void iter_object::test<5>()
  1093.     {
  1094. //      set_test_name("getWalkRange() tests");
  1095.         // This test function doesn't illustrate the looping permutations for
  1096.         // getWalkRange(); see getRootRange_tests() for such examples. This
  1097.         // function simply verifies that they all work.
  1098.         // TreeNode, using helper function
  1099.         TreeNodePtr tnroot(example_tree<TreeNode>());
  1100.         std::string desc_tnpre("getWalkRange<LLTreeIter::DFS_PRE>(tnroot)");
  1101.         ensure(desc_tnpre,
  1102.                verify(desc_tnpre,
  1103.                       getWalkRange<LLTreeIter::DFS_PRE>(tnroot),
  1104.                       WalkExpected<LLTreeIter::DFS_PRE>()));
  1105.         std::string desc_tnpost("getWalkRange<LLTreeIter::DFS_POST>(tnroot)");
  1106.         ensure(desc_tnpost,
  1107.                verify(desc_tnpost,
  1108.                       getWalkRange<LLTreeIter::DFS_POST>(tnroot),
  1109.                       WalkExpected<LLTreeIter::DFS_POST>()));
  1110.         std::string desc_tnb("getWalkRange<LLTreeIter::BFS>(tnroot)");
  1111.         ensure(desc_tnb,
  1112.                verify(desc_tnb,
  1113.                       getWalkRange<LLTreeIter::BFS>(tnroot),
  1114.                       WalkExpected<LLTreeIter::BFS>()));
  1115.         // EnhancedTreeNode, using method
  1116.         EnhancedTreeNodePtr etnroot(example_tree<EnhancedTreeNode>());
  1117.         std::string desc_etnpre("etnroot->getWalkRange<LLTreeIter::DFS_PRE>()");
  1118.         ensure(desc_etnpre,
  1119.                verify(desc_etnpre,
  1120.                       etnroot->getWalkRange<LLTreeIter::DFS_PRE>(),
  1121.                       WalkExpected<LLTreeIter::DFS_PRE>()));
  1122.         std::string desc_etnpost("etnroot->getWalkRange<LLTreeIter::DFS_POST>()");
  1123.         ensure(desc_etnpost,
  1124.                verify(desc_etnpost,
  1125.                       etnroot->getWalkRange<LLTreeIter::DFS_POST>(),
  1126.                       WalkExpected<LLTreeIter::DFS_POST>()));
  1127.         std::string desc_etnb("etnroot->getWalkRange<LLTreeIter::BFS>()");
  1128.         ensure(desc_etnb,
  1129.                verify(desc_etnb,
  1130.                       etnroot->getWalkRange<LLTreeIter::BFS>(),
  1131.                       WalkExpected<LLTreeIter::BFS>()));
  1132.         // PlainTree, using helper function
  1133.         PlainTree* ptroot(example_tree<PlainTree>());
  1134.         Cleanup<PlainTree*> cleanup(ptroot);
  1135.         std::string desc_ptpre("getWalkRange<LLTreeIter::DFS_PRE>(ptroot)");
  1136.         ensure(desc_ptpre,
  1137.                verify(desc_ptpre,
  1138.                       getWalkRange<LLTreeIter::DFS_PRE>(ptroot),
  1139.                       WalkExpected<LLTreeIter::DFS_PRE>()));
  1140.         std::string desc_ptpost("getWalkRange<LLTreeIter::DFS_POST>(ptroot)");
  1141.         ensure(desc_ptpost,
  1142.                verify(desc_ptpost,
  1143.                       getWalkRange<LLTreeIter::DFS_POST>(ptroot),
  1144.                       WalkExpected<LLTreeIter::DFS_POST>()));
  1145.         std::string desc_ptb("getWalkRange<LLTreeIter::BFS>(ptroot)");
  1146.         ensure(desc_ptb,
  1147.                verify(desc_ptb,
  1148.                       getWalkRange<LLTreeIter::BFS>(ptroot),
  1149.                       WalkExpected<LLTreeIter::BFS>()));
  1150.     }
  1151. } // tut