diff options
Diffstat (limited to 'indra/llcommon')
| -rw-r--r-- | indra/llcommon/CMakeLists.txt | 3 | ||||
| -rw-r--r-- | indra/llcommon/tests/lltreeiterators_test.cpp | 1222 |
2 files changed, 1224 insertions, 1 deletions
diff --git a/indra/llcommon/CMakeLists.txt b/indra/llcommon/CMakeLists.txt index 10c145e17b..c8e030623b 100644 --- a/indra/llcommon/CMakeLists.txt +++ b/indra/llcommon/CMakeLists.txt @@ -243,11 +243,12 @@ LL_ADD_PROJECT_UNIT_TESTS(llcommon "${llcommon_TEST_SOURCE_FILES}") set(test_libs llcommon ${LLCOMMON_LIBRARIES} ${WINDOWS_LIBRARIES}) LL_ADD_INTEGRATION_TEST(commonmisc "" "${test_libs}") LL_ADD_INTEGRATION_TEST(lldate "" "${test_libs}") +LL_ADD_INTEGRATION_TEST(llframetimer "" "${test_libs}") LL_ADD_INTEGRATION_TEST(lllazy "" "${test_libs}") LL_ADD_INTEGRATION_TEST(llrand "" "${test_libs}") LL_ADD_INTEGRATION_TEST(llsdserialize "" "${test_libs}") LL_ADD_INTEGRATION_TEST(llstring "" "${test_libs}") -LL_ADD_INTEGRATION_TEST(llframetimer "" "${test_libs}") +LL_ADD_INTEGRATION_TEST(lltreeiterators "" "${test_libs}") # *TODO - reenable these once tcmalloc libs no longer break the build. #ADD_BUILD_TEST(llallocator llcommon) diff --git a/indra/llcommon/tests/lltreeiterators_test.cpp b/indra/llcommon/tests/lltreeiterators_test.cpp new file mode 100644 index 0000000000..d6d9f68110 --- /dev/null +++ b/indra/llcommon/tests/lltreeiterators_test.cpp @@ -0,0 +1,1222 @@ +/** + * @file lltreeiterators.cpp + * @author Nat Goodspeed + * @date 2008-08-20 + * @brief Test of lltreeiterators.h + * + * $LicenseInfo:firstyear=2008&license=viewergpl$ + * + * Copyright (c) 2008-2009, Linden Research, Inc. + * + * Second Life Viewer Source Code + * The source code in this file ("Source Code") is provided by Linden Lab + * to you under the terms of the GNU General Public License, version 2.0 + * ("GPL"), unless you have obtained a separate licensing agreement + * ("Other License"), formally executed by you and Linden Lab. Terms of + * the GPL can be found in doc/GPL-license.txt in this distribution, or + * online at http://secondlifegrid.net/programs/open_source/licensing/gplv2 + * + * There are special exceptions to the terms and conditions of the GPL as + * it is applied to this Source Code. View the full text of the exception + * in the file doc/FLOSS-exception.txt in this software distribution, or + * online at + * http://secondlifegrid.net/programs/open_source/licensing/flossexception + * + * By copying, modifying or distributing this software, you acknowledge + * that you have read and understood your obligations described above, + * and agree to abide by those obligations. + * + * ALL LINDEN LAB SOURCE CODE IS PROVIDED "AS IS." LINDEN LAB MAKES NO + * WARRANTIES, EXPRESS, IMPLIED OR OTHERWISE, REGARDING ITS ACCURACY, + * COMPLETENESS OR PERFORMANCE. + * $/LicenseInfo$ + */ + +// Precompiled header +#include "linden_common.h" + +#if LL_WINDOWS +#pragma warning (disable : 4180) // qualifier applied to function type has no meaning; ignored +#endif + +// STL headers +// std headers +#include <iostream> +#include <sstream> +#include <string> +// external library headers +#include <boost/bind.hpp> +#include <boost/range/iterator_range.hpp> +#include <boost/foreach.hpp> + +// associated header +#include "../lltreeiterators.h" +#include "../llpointer.h" + +#include "../test/lltut.h" + +/***************************************************************************** +* tut test group +*****************************************************************************/ +namespace tut +{ + struct iter_data + { + }; + typedef test_group<iter_data> iter_group; + typedef iter_group::object iter_object; + tut::iter_group ig("lltreeiterators"); +} // namespace tut + +/***************************************************************************** +* boost::get_pointer() specialization for LLPointer<> +*****************************************************************************/ +// This specialization of boost::get_pointer() undoubtedly belongs in +// llmemory.h. It's used by boost::bind() so that you can pass an +// LLPointer<Foo> as well as a Foo* to a functor such as +// boost::bind(&Foo::method, _1). +//namespace boost +//{ + template <class NODE> + NODE* get_pointer(const LLPointer<NODE>& ptr) { return ptr.get(); } +//}; + +/***************************************************************************** +* ScopeLabel +*****************************************************************************/ +class ScopeLabel +{ +public: + ScopeLabel(const std::string& label): mLabel(label) + { + std::cout << "Entering " << mLabel << '\n'; + } + ~ScopeLabel() + { + std::cout << "Leaving " << mLabel << '\n'; + } +private: + std::string mLabel; +}; + +/***************************************************************************** +* Cleanup +*****************************************************************************/ +// Yes, we realize this is redundant with auto_ptr and LLPointer and all +// kinds of better mechanisms. But in this particular source file, we need to +// test nodes managed with plain old dumb pointers as well as nodes managed +// with LLPointer, so we introduce this mechanism. +// +// In the general case, when we declare a Cleanup for some pointer, delete the +// pointer when the Cleanup goes out of scope. +template <typename PTRTYPE> +struct Cleanup +{ + Cleanup(const PTRTYPE& ptr): mPtr(ptr) {} + ~Cleanup() + { + delete mPtr; + } + PTRTYPE mPtr; +}; + +// But when the pointer is an LLPointer<something>, Cleanup is a no-op: +// LLPointer will handle the cleanup automagically. +template <typename NODE> +struct Cleanup< LLPointer<NODE> > +{ + Cleanup(const LLPointer<NODE>& ptr) {} + ~Cleanup() {} +}; + +/***************************************************************************** +* Expected +*****************************************************************************/ +// Expected is a base class used to capture the expected results -- a sequence +// of string node names -- from one of our traversals of this example data. +// Its subclasses initialize it with a pair of string iterators. It's not +// strictly necessary to customize Expected to model Boost.Range, it's just +// convenient. +struct Expected +{ + template <typename ITER> + Expected(ITER begin, ITER end): + strings(begin, end) + {} + /*------ The following are to make Expected work with Boost.Range ------*/ + typedef std::vector<std::string> container_type; + typedef container_type::iterator iterator; + typedef container_type::const_iterator const_iterator; + typedef container_type::size_type size_type; + container_type strings; + iterator begin() { return strings.begin(); } + iterator end() { return strings.end(); } + size_type size() { return strings.size(); } + const_iterator begin() const { return strings.begin(); } + const_iterator end() const { return strings.end(); } +}; + +// We have a couple of generic Expected template subclasses. This list of +// strings is used for the "else" case when all specializations fail. +const char* bad_strings[] = { "FAIL" }; + +/***************************************************************************** +* verify() +*****************************************************************************/ +// test function: given (an object modeling) a Boost.Range of tree nodes, +// compare the sequence of visited node names with a range of expected name +// strings. Report success both with std::cout output and a bool return. The +// string desc parameter is to identify the different tests. +template <typename NODERANGE, typename STRINGRANGE> +bool verify(const std::string& desc, NODERANGE noderange, STRINGRANGE expected) +{ + typename boost::range_iterator<NODERANGE>::type + nri = boost::begin(noderange), + nrend = boost::end(noderange); + typename boost::range_iterator<STRINGRANGE>::type + sri = boost::begin(expected), + srend = boost::end(expected); + // We choose to loop over both sequences explicitly rather than using + // std::equal() or std::lexicographical_compare(). The latter tells you + // whether one sequence is *less* than the other -- it doesn't tell you + // equality. std::equal() needs you to verify the sequence lengths ahead + // of time. Anyway, comparing explicitly allows us to report much more + // information about any sequence mismatch. + for ( ; nri != nrend && sri != srend; ++nri, ++sri) + { + if ((*nri)->name() != *sri) + { + std::cout << desc << " mismatch: " + << "expected " << *sri << ", got " << (*nri)->name() << "\n"; + return false; + } + } + if (nri != nrend) + { + std::cout << desc << " produced too many items:\n"; + for ( ; nri != nrend; ++nri) + { + std::cout << " " << (*nri)->name() << '\n'; + } + return false; + } + if (sri != srend) + { + std::cout << desc << " produced too few items, omitting:\n"; + for ( ; sri != srend; ++sri) + { + std::cout << " " << *sri << '\n'; + } + return false; + } +// std::cout << desc << " test passed\n"; + return true; +} + +/***************************************************************************** +* PlainNode: LLLinkIter, non-refcounted +*****************************************************************************/ +class PlainNode +{ +public: + PlainNode(const std::string& name, PlainNode* next=NULL): + mName(name), + mNext(next) + {} + ~PlainNode() + { + delete mNext; + } + std::string name() const { return mName; } + PlainNode* next() const { return mNext; } +public: // if this were 'private', couldn't bind mNext + PlainNode* mNext; +private: + std::string mName; +}; + +namespace tut +{ + template<> template<> + void iter_object::test<1>() + { +// set_test_name("LLLinkedIter -- non-refcounted class"); + PlainNode* last(new PlainNode("c")); + PlainNode* second(new PlainNode("b", last)); + PlainNode* first(new PlainNode("a", second)); + Cleanup<PlainNode*> cleanup(first); + static const char* cseq[] = { "a", "b", "c" }; + Expected seq(boost::begin(cseq), boost::end(cseq)); + std::string desc1("Iterate by public link member"); +// std::cout << desc1 << ":\n"; + // Try instantiating an iterator with NULL. This test is less about + // "did we iterate once?" than "did we avoid blowing up?" + for (LLLinkedIter<PlainNode> pni(NULL, boost::bind(&PlainNode::mNext, _1)), end; + pni != end; ++pni) + { +// std::cout << (*pni)->name() << '\n'; + ensure("LLLinkedIter<PlainNode>(NULL)", false); + } + ensure(desc1, + verify(desc1, + boost::make_iterator_range(LLLinkedIter<PlainNode>(first, + boost::bind(&PlainNode::mNext, _1)), + LLLinkedIter<PlainNode>()), + seq)); + std::string desc2("Iterate by next() method"); +// std::cout << desc2 << ":\n"; +// for (LLLinkedIter<PlainNode> pni(first, boost::bind(&PlainNode::next, _1)); ! (pni == end); ++pni) +// std::cout << (**pni).name() << '\n'; + ensure(desc2, + verify(desc2, + boost::make_iterator_range(LLLinkedIter<PlainNode>(first, + boost::bind(&PlainNode::next, _1)), + LLLinkedIter<PlainNode>()), + seq)); + { +// LLLinkedIter<PlainNode> pni(first, boost::bind(&PlainNode::next, _1)); +// std::cout << "First is " << (*pni++)->name() << '\n'; +// std::cout << "Second is " << (*pni )->name() << '\n'; + } + { + LLLinkedIter<PlainNode> pni(first, boost::bind(&PlainNode::next, _1)); + ensure_equals("first", (*pni++)->name(), "a"); + ensure_equals("second", (*pni )->name(), "b"); + } + } +} // tut + +/***************************************************************************** +* RCNode: LLLinkIter, refcounted +*****************************************************************************/ +class RCNode; +typedef LLPointer<RCNode> RCNodePtr; + +class RCNode: public LLRefCount +{ +public: + RCNode(const std::string& name, const RCNodePtr& next=RCNodePtr()): + mName(name), + mNext(next) + { +// std::cout << "New RCNode(" << mName << ")\n"; + } + RCNode(const RCNode& that): + mName(that.mName), + mNext(that.mNext) + { +// std::cout << "Copy RCNode(" << mName << ")\n"; + } + virtual ~RCNode(); + std::string name() const { return mName; } + RCNodePtr next() const { return mNext; } +public: // if this were 'private', couldn't bind mNext + RCNodePtr mNext; +private: + std::string mName; +}; + +std::ostream& operator<<(std::ostream& out, const RCNode& node) +{ + out << "RCNode(" << node.name() << ')'; + return out; +} + +// This string contains the node name of the last RCNode destroyed. We use it +// to validate that LLLinkedIter<RCNode> in fact contains LLPointer<RCNode>, +// and that therefore an outstanding LLLinkedIter to an instance of a +// refcounted class suffices to keep that instance alive. +std::string last_RCNode_destroyed; + +RCNode::~RCNode() +{ +// std::cout << "Kill " << *this << "\n"; + last_RCNode_destroyed = mName; +} + +namespace tut +{ + template<> template<> + void iter_object::test<2>() + { +// set_test_name("LLLinkedIter -- refcounted class"); + LLLinkedIter<RCNode> rcni, end2; + { +// ScopeLabel label("inner scope"); + RCNodePtr head(new RCNode("x", new RCNode("y", new RCNode("z")))); +// for (rcni = LLLinkedIter<RCNode>(head, boost::bind(&RCNode::mNext, _1)); rcni != end2; ++rcni) +// std::cout << **rcni << '\n'; + rcni = LLLinkedIter<RCNode>(head, boost::bind(&RCNode::next, _1)); + } +// std::cout << "Now the LLLinkedIter<RCNode> is the only remaining reference to RCNode chain\n"; + ensure_equals(last_RCNode_destroyed, ""); + ensure(rcni != end2); + ensure_equals((*rcni)->name(), "x"); + ++rcni; + ensure_equals(last_RCNode_destroyed, "x"); + ensure(rcni != end2); + ensure_equals((*rcni)->name(), "y"); + ++rcni; + ensure_equals(last_RCNode_destroyed, "y"); + ensure(rcni != end2); + ensure_equals((*rcni)->name(), "z"); + ++rcni; + ensure_equals(last_RCNode_destroyed, "z"); + ensure(rcni == end2); + } +} + +/***************************************************************************** +* TreeNode +*****************************************************************************/ +class TreeNode; +typedef LLPointer<TreeNode> TreeNodePtr; + +/** + * TreeNode represents a refcounted tree-node class that hasn't (yet) been + * modified to incorporate LLTreeIter methods. This illustrates how you can + * use tree iterators either standalone, or with free functions. + */ +class TreeNode: public LLRefCount +{ +public: + typedef std::vector<TreeNodePtr> list_type; + typedef list_type::const_iterator child_iterator; + + // To avoid cycles, use a "weak" raw pointer for the parent link + TreeNode(const std::string& name, TreeNode* parent=0): + mParent(parent), + mName(name) + {} + TreeNodePtr newChild(const std::string& name) + { + TreeNodePtr child(new TreeNode(name, this)); + mChildren.push_back(child); + return child; + } + std::string name() const { return mName; } + TreeNodePtr getParent() const { return mParent; } + child_iterator child_begin() const { return mChildren.begin(); } + child_iterator child_end() const { return mChildren.end(); } +private: + std::string mName; + // To avoid cycles, use a "weak" raw pointer for the parent link + TreeNode* mParent; + list_type mChildren; +}; + +/** + * This is an example of a helper function to facilitate iterating from a + * TreeNode up to the root or down from the root (see LLTreeIter::RootIter). + * + * Example: + * @code + * BOOST_FOREACH(TreeNodePtr node, getRootRange<LLTreeIter::UP>(somenode)) + * { + * std::cout << node->name() << '\n'; + * } + * @endcode + */ +template <LLTreeIter::RootIter DISCRIM> +boost::iterator_range< LLTreeRootIter<DISCRIM, TreeNode> > +getRootRange(const TreeNodePtr& node) +{ + typedef LLTreeRootIter<DISCRIM, TreeNode> iter_type; + typedef boost::iterator_range<iter_type> range_type; + return range_type(iter_type(node, boost::bind(&TreeNode::getParent, _1)), + iter_type()); +} + +/** + * This is an example of a helper function to facilitate walking a given + * TreeNode's subtree in any supported order (see LLTreeIter::WalkIter). + * + * Example: + * @code + * BOOST_FOREACH(TreeNodePtr node, getWalkRange<LLTreeIter::DFS_PRE>(root)) + * { + * std::cout << node->name() << '\n'; + * } + * @endcode + */ +template <LLTreeIter::WalkIter DISCRIM> +boost::iterator_range< LLTreeWalkIter<DISCRIM, TreeNode, TreeNode::child_iterator> > +getWalkRange(const TreeNodePtr& node) +{ + typedef LLTreeWalkIter<DISCRIM, TreeNode, TreeNode::child_iterator> iter_type; + typedef boost::iterator_range<iter_type> range_type; + return range_type(iter_type(node, + boost::bind(&TreeNode::child_begin, _1), + boost::bind(&TreeNode::child_end, _1)), + iter_type()); +} + +/***************************************************************************** +* EnhancedTreeNode +*****************************************************************************/ +class EnhancedTreeNode; +typedef LLPointer<EnhancedTreeNode> EnhancedTreeNodePtr; + +/** + * More typically, you enhance the tree-node class itself with template + * methods like the above. This EnhancedTreeNode class illustrates the + * technique. Normally, of course, you'd simply add these methods to TreeNode; + * we put them in a separate class to preserve the undecorated TreeNode class + * to illustrate (and test) the use of plain tree iterators and standalone + * helper functions. + * + * We originally implemented EnhancedTreeNode as a subclass of TreeNode -- but + * because TreeNode stores and manipulates TreeNodePtrs and TreeNode*s, + * reusing its methods required so much ugly downcast logic that we gave up + * and restated the whole class. Bear in mind that logically these aren't two + * separate classes; logically they're two snapshots of the @em same class at + * different moments in time. + */ +class EnhancedTreeNode: public LLRefCount +{ +public: + /*-------------- The following is restated from TreeNode ---------------*/ + typedef std::vector<EnhancedTreeNodePtr> list_type; + typedef list_type::const_iterator child_iterator; + + // To avoid cycles, use a "weak" raw pointer for the parent link + EnhancedTreeNode(const std::string& name, EnhancedTreeNode* parent=0): + mParent(parent), + mName(name) + {} + EnhancedTreeNodePtr newChild(const std::string& name) + { + EnhancedTreeNodePtr child(new EnhancedTreeNode(name, this)); + mChildren.push_back(child); + return child; + } + std::string name() const { return mName; } + EnhancedTreeNodePtr getParent() const { return mParent; } + child_iterator child_begin() const { return mChildren.begin(); } + child_iterator child_end() const { return mChildren.end(); } + +private: + std::string mName; + // To avoid cycles, use a "weak" raw pointer for the parent link + EnhancedTreeNode* mParent; + list_type mChildren; +public: + /*----- End of TreeNode; what follows is new with EnhancedTreeNode -----*/ + + /** + * Because the type of the iterator range returned by getRootRange() + * depends on the discriminator enum value, instead of a simple typedef we + * use a templated struct. Example usage: + * + * @code + * for (EnhancedTreeNode::root_range<LLTreeIter::UP>::type range = + * somenode->getRootRange<LLTreeIter::UP>(); + * range.first != range.second; ++range.first) + * { + * std::cout << (*range.first)->name() << '\n'; + * } + * @endcode + */ + template <LLTreeIter::RootIter DISCRIM> + struct root_range + { + typedef boost::iterator_range< LLTreeRootIter<DISCRIM, EnhancedTreeNode> > type; + }; + + /** + * Helper method for walking up to (or down from) the tree root. See + * LLTreeIter::RootIter. + * + * Example usage: + * @code + * BOOST_FOREACH(EnhancedTreeNodePtr node, somenode->getRootRange<LLTreeIter::UP>()) + * { + * std::cout << node->name() << '\n'; + * } + * @endcode + */ + template <LLTreeIter::RootIter DISCRIM> + typename root_range<DISCRIM>::type getRootRange() const + { + typedef typename root_range<DISCRIM>::type range_type; + typedef typename range_type::iterator iter_type; + return range_type(iter_type(const_cast<EnhancedTreeNode*>(this), + boost::bind(&EnhancedTreeNode::getParent, _1)), + iter_type()); + } + + /** + * Because the type of the iterator range returned by getWalkRange() + * depends on the discriminator enum value, instead of a simple typedef we + * use a templated stuct. Example usage: + * + * @code + * for (EnhancedTreeNode::walk_range<LLTreeIter::DFS_PRE>::type range = + * somenode->getWalkRange<LLTreeIter::DFS_PRE>(); + * range.first != range.second; ++range.first) + * { + * std::cout << (*range.first)->name() << '\n'; + * } + * @endcode + */ + template <LLTreeIter::WalkIter DISCRIM> + struct walk_range + { + typedef boost::iterator_range< LLTreeWalkIter<DISCRIM, + EnhancedTreeNode, + EnhancedTreeNode::child_iterator> > type; + }; + + /** + * Helper method for walking a given node's subtree in any supported + * order (see LLTreeIter::WalkIter). + * + * Example usage: + * @code + * BOOST_FOREACH(EnhancedTreeNodePtr node, somenode->getWalkRange<LLTreeIter::DFS_PRE>()) + * { + * std::cout << node->name() << '\n'; + * } + * @endcode + */ + template <LLTreeIter::WalkIter DISCRIM> + typename walk_range<DISCRIM>::type getWalkRange() const + { + typedef typename walk_range<DISCRIM>::type range_type; + typedef typename range_type::iterator iter_type; + return range_type(iter_type(const_cast<EnhancedTreeNode*>(this), + boost::bind(&EnhancedTreeNode::child_begin, _1), + boost::bind(&EnhancedTreeNode::child_end, _1)), + iter_type()); + } +}; + +/***************************************************************************** +* PlainTree +*****************************************************************************/ +struct PlainTree +{ + PlainTree(const std::string& name, PlainTree* parent=0): + mName(name), + mParent(parent), + mNextSibling(0), + mFirstChild(0) + { + mLastChildLink = &mFirstChild; + } + ~PlainTree() + { + delete mNextSibling; + delete mFirstChild; + } + PlainTree* newChild(const std::string& name) + { + PlainTree* child(new PlainTree(name, this)); + *mLastChildLink = child; + mLastChildLink = &child->mNextSibling; + return child; + } + std::string name() const { return mName; } + + std::string mName; + PlainTree* mParent; + PlainTree* mNextSibling; + PlainTree* mFirstChild; + PlainTree** mLastChildLink; +}; + +// This "classic" tree tracks each node's children with a linked list anchored +// at the parent's mFirstChild and linked through each child's mNextSibling. +// LLTreeDFSIter<> and LLTreeBFSIter<> need functors to return begin()/end() +// iterators over a given node's children. But because this tree's children +// aren't stored in an STL container, we can't just export that container's +// begin()/end(). Instead we'll use LLLinkedIter<> to view the hand-maintained +// linked list as an iterator range. The straightforward way to do that would +// be to add child_begin() and child_end() methods. But let's say (for the +// sake of argument) that this struct is so venerable we don't dare modify it +// even to add new methods. Well, we can use free functions (or functors) too. +LLLinkedIter<PlainTree> PlainTree_child_begin(PlainTree* node) +{ + return LLLinkedIter<PlainTree>(node->mFirstChild, boost::bind(&PlainTree::mNextSibling, _1)); +} + +LLLinkedIter<PlainTree> PlainTree_child_end(PlainTree* node) +{ + return LLLinkedIter<PlainTree>(); +} + +/** + * This is an example of a helper function to facilitate iterating from a + * PlainTree up to the root or down from the root (see LLTreeIter::RootIter). + * Note that we're simply overloading the same getRootRange() helper function + * name we used for TreeNode. + * + * Example: + * @code + * BOOST_FOREACH(PlainTree* node, getRootRange<LLTreeIter::UP>(somenode)) + * { + * std::cout << node->name() << '\n'; + * } + * @endcode + */ +template <LLTreeIter::RootIter DISCRIM> +boost::iterator_range< LLTreeRootIter<DISCRIM, PlainTree> > +getRootRange(PlainTree* node) +{ + typedef LLTreeRootIter<DISCRIM, PlainTree> iter_type; + typedef boost::iterator_range<iter_type> range_type; + return range_type(iter_type(node, boost::bind(&PlainTree::mParent, _1)), + iter_type()); +} + +/** + * This is an example of a helper function to facilitate walking a given + * PlainTree's subtree in any supported order (see LLTreeIter::WalkIter). Note + * that we're simply overloading the same getWalkRange() helper function name + * we used for TreeNode. + * + * Example: + * @code + * BOOST_FOREACH(PlainTree* node, getWalkRange<LLTreeIter::DFS_PRE>(root)) + * { + * std::cout << node->name() << '\n'; + * } + * @endcode + */ +template <LLTreeIter::WalkIter DISCRIM> +boost::iterator_range< LLTreeWalkIter<DISCRIM, PlainTree, LLLinkedIter<PlainTree> > > +getWalkRange(PlainTree* node) +{ + typedef LLTreeWalkIter<DISCRIM, PlainTree, LLLinkedIter<PlainTree> > iter_type; + typedef boost::iterator_range<iter_type> range_type; + return range_type(iter_type(node, + PlainTree_child_begin, + PlainTree_child_end), + iter_type()); +} + +// We could go through the exercise of writing EnhancedPlainTree containing +// root_range, getRootRange(), walk_range and getWalkRange() members -- but we +// won't. See EnhancedTreeNode for examples. + +/***************************************************************************** +* Generic tree test data +*****************************************************************************/ +template <class NODE> +typename LLPtrTo<NODE>::type example_tree() +{ + typedef typename LLPtrTo<NODE>::type NodePtr; + NodePtr root(new NODE("root")); + NodePtr A(root->newChild("A")); + NodePtr A1(A->newChild("A1")); +/* NodePtr A1a*/(A1->newChild("A1a")); +/* NodePtr A1b*/(A1->newChild("A1b")); +/* NodePtr A1c*/(A1->newChild("A1c")); + NodePtr A2(A->newChild("A2")); +/* NodePtr A2a*/(A2->newChild("A2a")); +/* NodePtr A2b*/(A2->newChild("A2b")); +/* NodePtr A2c*/(A2->newChild("A2c")); + NodePtr A3(A->newChild("A3")); +/* NodePtr A3a*/(A3->newChild("A3a")); +/* NodePtr A3b*/(A3->newChild("A3b")); +/* NodePtr A3c*/(A3->newChild("A3c")); + NodePtr B(root->newChild("B")); + NodePtr B1(B->newChild("B1")); +/* NodePtr B1a*/(B1->newChild("B1a")); +/* NodePtr B1b*/(B1->newChild("B1b")); +/* NodePtr B1c*/(B1->newChild("B1c")); + NodePtr B2(B->newChild("B2")); +/* NodePtr B2a*/(B2->newChild("B2a")); +/* NodePtr B2b*/(B2->newChild("B2b")); +/* NodePtr B2c*/(B2->newChild("B2c")); + NodePtr B3(B->newChild("B3")); +/* NodePtr B3a*/(B3->newChild("B3a")); +/* NodePtr B3b*/(B3->newChild("B3b")); +/* NodePtr B3c*/(B3->newChild("B3c")); + NodePtr C(root->newChild("C")); + NodePtr C1(C->newChild("C1")); +/* NodePtr C1a*/(C1->newChild("C1a")); +/* NodePtr C1b*/(C1->newChild("C1b")); +/* NodePtr C1c*/(C1->newChild("C1c")); + NodePtr C2(C->newChild("C2")); +/* NodePtr C2a*/(C2->newChild("C2a")); +/* NodePtr C2b*/(C2->newChild("C2b")); +/* NodePtr C2c*/(C2->newChild("C2c")); + NodePtr C3(C->newChild("C3")); +/* NodePtr C3a*/(C3->newChild("C3a")); +/* NodePtr C3b*/(C3->newChild("C3b")); +/* NodePtr C3c*/(C3->newChild("C3c")); + return root; +} + +// WalkExpected<WalkIter> is the list of string node names we expect from a +// WalkIter traversal of our example_tree() data. +template <LLTreeIter::WalkIter DISCRIM> +struct WalkExpected: public Expected +{ + // Initialize with bad_strings: we don't expect to use this generic case, + // only the specializations. Note that for a classic C-style array we must + // pass a pair of iterators rather than extracting boost::begin() and + // boost::end() within the target constructor: a template ctor accepts + // these classic C-style arrays as char** rather than char*[length]. Oh well. + WalkExpected(): Expected(boost::begin(bad_strings), boost::end(bad_strings)) {} +}; + +// list of string node names we expect from traversing example_tree() in +// DFS_PRE order +const char* dfs_pre_strings[] = +{ + "root", + "A", + "A1", + "A1a", + "A1b", + "A1c", + "A2", + "A2a", + "A2b", + "A2c", + "A3", + "A3a", + "A3b", + "A3c", + "B", + "B1", + "B1a", + "B1b", + "B1c", + "B2", + "B2a", + "B2b", + "B2c", + "B3", + "B3a", + "B3b", + "B3c", + "C", + "C1", + "C1a", + "C1b", + "C1c", + "C2", + "C2a", + "C2b", + "C2c", + "C3", + "C3a", + "C3b", + "C3c" +}; + +// specialize WalkExpected<DFS_PRE> with the expected strings +template <> +struct WalkExpected<LLTreeIter::DFS_PRE>: public Expected +{ + WalkExpected(): Expected(boost::begin(dfs_pre_strings), boost::end(dfs_pre_strings)) {} +}; + +// list of string node names we expect from traversing example_tree() in +// DFS_POST order +const char* dfs_post_strings[] = +{ + "A1a", + "A1b", + "A1c", + "A1", + "A2a", + "A2b", + "A2c", + "A2", + "A3a", + "A3b", + "A3c", + "A3", + "A", + "B1a", + "B1b", + "B1c", + "B1", + "B2a", + "B2b", + "B2c", + "B2", + "B3a", + "B3b", + "B3c", + "B3", + "B", + "C1a", + "C1b", + "C1c", + "C1", + "C2a", + "C2b", + "C2c", + "C2", + "C3a", + "C3b", + "C3c", + "C3", + "C", + "root" +}; + +// specialize WalkExpected<DFS_POST> with the expected strings +template <> +struct WalkExpected<LLTreeIter::DFS_POST>: public Expected +{ + WalkExpected(): Expected(boost::begin(dfs_post_strings), boost::end(dfs_post_strings)) {} +}; + +// list of string node names we expect from traversing example_tree() in BFS order +const char* bfs_strings[] = +{ + "root", + "A", + "B", + "C", + "A1", + "A2", + "A3", + "B1", + "B2", + "B3", + "C1", + "C2", + "C3", + "A1a", + "A1b", + "A1c", + "A2a", + "A2b", + "A2c", + "A3a", + "A3b", + "A3c", + "B1a", + "B1b", + "B1c", + "B2a", + "B2b", + "B2c", + "B3a", + "B3b", + "B3c", + "C1a", + "C1b", + "C1c", + "C2a", + "C2b", + "C2c", + "C3a", + "C3b", + "C3c" +}; + +// specialize WalkExpected<BFS> with the expected strings +template <> +struct WalkExpected<LLTreeIter::BFS>: public Expected +{ + WalkExpected(): Expected(boost::begin(bfs_strings), boost::end(bfs_strings)) {} +}; + +// extract a particular "arbitrary" node from the example_tree() data: the +// second (middle) node at each child level +template <class NODE, typename CHILDITER> +typename LLPtrTo<NODE>::type +get_B2b(const typename LLPtrTo<NODE>::type& root, + const boost::function<CHILDITER(const typename LLPtrTo<NODE>::type&)>& child_begin) +{ + typedef typename LLPtrTo<NODE>::type NodePtr; + CHILDITER Bi(child_begin(root)); + ++Bi; + NodePtr B(*Bi); + CHILDITER B2i(child_begin(B)); + ++B2i; + NodePtr B2(*B2i); + CHILDITER B2bi(child_begin(B2)); + ++B2bi; + NodePtr B2b(*B2bi); + return B2b; +} + +// RootExpected<RootIter> is the list of string node names we expect from a +// RootIter traversal of our example_tree() data. +template <LLTreeIter::RootIter DISCRIM> +struct RootExpected: public Expected +{ + // Initialize with bad_strings: we don't expect to use this generic case, + // only the specializations. + RootExpected(): Expected(boost::begin(bad_strings), boost::end(bad_strings)) {} +}; + +// list of string node names we expect from traversing UP from +// example_tree()'s B2b node +const char* up_from_B2b[] = +{ + "B2b", + "B2", + "B", + "root" +}; + +// specialize RootExpected<UP> with the expected strings +template <> +struct RootExpected<LLTreeIter::UP>: public Expected +{ + RootExpected(): Expected(boost::begin(up_from_B2b), boost::end(up_from_B2b)) {} +}; + +// list of string node names we expect from traversing DOWN to +// example_tree()'s B2b node +const char* down_to_B2b[] = +{ + "root", + "B", + "B2", + "B2b" +}; + +// specialize RootExpected<DOWN> with the expected strings +template <> +struct RootExpected<LLTreeIter::DOWN>: public Expected +{ + RootExpected(): Expected(boost::begin(down_to_B2b), boost::end(down_to_B2b)) {} +}; + +/***************************************************************************** +* Generic tree test functions +*****************************************************************************/ +template<LLTreeIter::RootIter DISCRIM, class NODE, typename PARENTFUNC> +bool LLTreeRootIter_test(const std::string& itername, const std::string& nodename, + const typename LLPtrTo<NODE>::type& node, + PARENTFUNC parentfunc) +{ + std::ostringstream desc; + desc << itername << '<' << nodename << "> from " << node->name(); + if (! verify(desc.str(), + boost::make_iterator_range(LLTreeRootIter<DISCRIM, NODE>(node, parentfunc), + LLTreeRootIter<DISCRIM, NODE>()), + RootExpected<DISCRIM>())) + return false; +// std::cout << desc.str() << '\n'; + // Try instantiating an iterator with NULL (that is, a default-constructed + // node pointer). This test is less about "did we iterate once?" than "did + // we avoid blowing up?" + for (LLTreeRootIter<DISCRIM, NODE> hri = LLTreeRootIter<DISCRIM, NODE>(typename LLPtrTo<NODE>::type(), parentfunc), hrend; + hri != hrend; /* ++hri */) // incrementing is moot, and MSVC complains + { +// std::cout << nodename << '(' << (*hri)->name() << ")\n"; + std::cout << itername << '<' << nodename << ">(NULL)\n"; + return false; + } + return true; +} + +template<class NODE, typename CHILDITER, typename PARENTFUNC, typename CHILDFUNC> +bool LLTreeUpIter_test(const std::string& nodename, PARENTFUNC parentfunc, CHILDFUNC childfunc) +{ + bool success = true; + typedef typename LLPtrTo<NODE>::type ptr_type; + ptr_type root(example_tree<NODE>()); + Cleanup<ptr_type> cleanup(root); + ptr_type B2b(get_B2b<NODE, CHILDITER>(root, childfunc)); + if (! LLTreeRootIter_test<LLTreeIter::UP, NODE>("LLTreeUpIter", nodename, B2b, parentfunc)) + success = false; + if (! LLTreeRootIter_test<LLTreeIter::DOWN, NODE>("LLTreeDownIter", nodename, B2b, parentfunc)) + success = false; + return success; +} + +template <LLTreeIter::WalkIter DISCRIM, class NODE, typename CHILDITER, + typename CHILDBEGINFUNC, typename CHILDENDFUNC> +bool LLTreeWalkIter_test(const std::string& itername, const std::string& nodename, + CHILDBEGINFUNC childbegin, CHILDENDFUNC childend) +{ + typename LLPtrTo<NODE>::type root(example_tree<NODE>()); + Cleanup<typename LLPtrTo<NODE>::type> cleanup(root); + std::ostringstream desc; + desc << itername << '<' << nodename << "> from " << root->name(); + if (! verify(desc.str(), + boost::make_iterator_range(LLTreeWalkIter<DISCRIM, NODE, CHILDITER>(root, + childbegin, + childend), + LLTreeWalkIter<DISCRIM, NODE, CHILDITER>()), + WalkExpected<DISCRIM>())) + return false; + // Try instantiating an iterator with NULL (that is, a default-constructed + // node pointer). This test is less about "did we iterate once?" than "did + // we avoid blowing up?" + for (LLTreeWalkIter<DISCRIM, NODE, CHILDITER> twi = LLTreeWalkIter<DISCRIM, NODE, CHILDITER>(typename LLPtrTo<NODE>::type(), + childbegin, + childend), + twend; + twi != twend; /* ++twi */) // incrementing is moot, and MSVC complains + { + std::cout << itername << '<' << nodename << ">(NULL)\n"; + return false; + } + return true; +} + +template <class NODE, typename CHILDITER, + typename PARENTFUNC, typename CHILDBEGINFUNC, typename CHILDENDFUNC> +bool LLTreeIter_tests(const std::string& nodename, + PARENTFUNC parentfunc, CHILDBEGINFUNC childbegin, CHILDENDFUNC childend) +{ + bool success = true; + if (! LLTreeUpIter_test<NODE, CHILDITER>(nodename, parentfunc, childbegin)) + success = false; +/*==========================================================================*| + LLTreeIter_test<NODE, LLTreeDFSIter<NODE, CHILDITER> >("LLTreeDFSIter", nodename, + childbegin, childend); + LLTreeIter_test<NODE, LLTreeDFSPostIter<NODE, CHILDITER> >("LLTreeDFSPostIter", nodename, + childbegin, childend); + LLTreeIter_test<NODE, LLTreeBFSIter<NODE, CHILDITER> >("LLTreeBFSIter", nodename, + childbegin, childend); +|*==========================================================================*/ + if (! LLTreeWalkIter_test<LLTreeIter::DFS_PRE, NODE, CHILDITER>("LLTreeDFSIter", nodename, + childbegin, childend)) + success = false; + if (! LLTreeWalkIter_test<LLTreeIter::DFS_POST, NODE, CHILDITER>("LLTreeDFSPostIter", nodename, + childbegin, childend)) + success = false; + if (! LLTreeWalkIter_test<LLTreeIter::BFS, NODE, CHILDITER>("LLTreeBFSIter", nodename, + childbegin, childend)) + success = false; + return success; +} + +namespace tut +{ + template<> template<> + void iter_object::test<3>() + { +// set_test_name("LLTreeIter tests"); + ensure(LLTreeIter_tests<TreeNode, TreeNode::child_iterator> + ("TreeNode", + boost::bind(&TreeNode::getParent, _1), + boost::bind(&TreeNode::child_begin, _1), + boost::bind(&TreeNode::child_end, _1))); + ensure(LLTreeIter_tests<PlainTree, LLLinkedIter<PlainTree> > + ("PlainTree", + boost::bind(&PlainTree::mParent, _1), + PlainTree_child_begin, + PlainTree_child_end)); + } + + template<> template<> + void iter_object::test<4>() + { +// set_test_name("getRootRange() tests"); + // This test function illustrates the looping techniques described in the + // comments for the getRootRange() free function, the + // EnhancedTreeNode::root_range template and the + // EnhancedTreeNode::getRootRange() method. Obviously the BOOST_FOREACH() + // forms are more succinct. + TreeNodePtr tnroot(example_tree<TreeNode>()); + TreeNodePtr tnB2b(get_B2b<TreeNode, TreeNode::child_iterator> + (tnroot, boost::bind(&TreeNode::child_begin, _1))); + + std::string desc1("BOOST_FOREACH(TreeNodePr, getRootRange<LLTreeIter::UP>(tnB2b))"); +// std::cout << desc1 << "\n"; + // Although we've commented out the output statement, ensure that the + // loop construct is still valid, as promised by the getRootRange() + // documentation. + BOOST_FOREACH(TreeNodePtr node, getRootRange<LLTreeIter::UP>(tnB2b)) + { +// std::cout << node->name() << '\n'; + } + ensure(desc1, + verify(desc1, getRootRange<LLTreeIter::UP>(tnB2b), RootExpected<LLTreeIter::UP>())); + + EnhancedTreeNodePtr etnroot(example_tree<EnhancedTreeNode>()); + EnhancedTreeNodePtr etnB2b(get_B2b<EnhancedTreeNode, EnhancedTreeNode::child_iterator> + (etnroot, boost::bind(&EnhancedTreeNode::child_begin, _1))); + +// std::cout << "EnhancedTreeNode::root_range<LLTreeIter::DOWN>::type range =\n" +// << " etnB2b->getRootRange<LLTreeIter::DOWN>();\n" +// << "for (EnhancedTreeNode::root_range<LLTreeIter::DOWN>::type::iterator ri = range.begin();\n" +// << " ri != range.end(); ++ri)\n"; + EnhancedTreeNode::root_range<LLTreeIter::DOWN>::type range = + etnB2b->getRootRange<LLTreeIter::DOWN>(); + for (EnhancedTreeNode::root_range<LLTreeIter::DOWN>::type::iterator ri = range.begin(); + ri != range.end(); ++ri) + { +// std::cout << (*ri)->name() << '\n'; + } + + std::string desc2("BOOST_FOREACH(EnhancedTreeNodePtr node, etnB2b->getRootRange<LLTreeIter::UP>())"); +// std::cout << desc2 << '\n'; + BOOST_FOREACH(EnhancedTreeNodePtr node, etnB2b->getRootRange<LLTreeIter::UP>()) + { +// std::cout << node->name() << '\n'; + } + ensure(desc2, + verify(desc2, etnB2b->getRootRange<LLTreeIter::UP>(), RootExpected<LLTreeIter::UP>())); + } + + template<> template<> + void iter_object::test<5>() + { +// set_test_name("getWalkRange() tests"); + // This test function doesn't illustrate the looping permutations for + // getWalkRange(); see getRootRange_tests() for such examples. This + // function simply verifies that they all work. + + // TreeNode, using helper function + TreeNodePtr tnroot(example_tree<TreeNode>()); + std::string desc_tnpre("getWalkRange<LLTreeIter::DFS_PRE>(tnroot)"); + ensure(desc_tnpre, + verify(desc_tnpre, + getWalkRange<LLTreeIter::DFS_PRE>(tnroot), + WalkExpected<LLTreeIter::DFS_PRE>())); + std::string desc_tnpost("getWalkRange<LLTreeIter::DFS_POST>(tnroot)"); + ensure(desc_tnpost, + verify(desc_tnpost, + getWalkRange<LLTreeIter::DFS_POST>(tnroot), + WalkExpected<LLTreeIter::DFS_POST>())); + std::string desc_tnb("getWalkRange<LLTreeIter::BFS>(tnroot)"); + ensure(desc_tnb, + verify(desc_tnb, + getWalkRange<LLTreeIter::BFS>(tnroot), + WalkExpected<LLTreeIter::BFS>())); + + // EnhancedTreeNode, using method + EnhancedTreeNodePtr etnroot(example_tree<EnhancedTreeNode>()); + std::string desc_etnpre("etnroot->getWalkRange<LLTreeIter::DFS_PRE>()"); + ensure(desc_etnpre, + verify(desc_etnpre, + etnroot->getWalkRange<LLTreeIter::DFS_PRE>(), + WalkExpected<LLTreeIter::DFS_PRE>())); + std::string desc_etnpost("etnroot->getWalkRange<LLTreeIter::DFS_POST>()"); + ensure(desc_etnpost, + verify(desc_etnpost, + etnroot->getWalkRange<LLTreeIter::DFS_POST>(), + WalkExpected<LLTreeIter::DFS_POST>())); + std::string desc_etnb("etnroot->getWalkRange<LLTreeIter::BFS>()"); + ensure(desc_etnb, + verify(desc_etnb, + etnroot->getWalkRange<LLTreeIter::BFS>(), + WalkExpected<LLTreeIter::BFS>())); + + // PlainTree, using helper function + PlainTree* ptroot(example_tree<PlainTree>()); + Cleanup<PlainTree*> cleanup(ptroot); + std::string desc_ptpre("getWalkRange<LLTreeIter::DFS_PRE>(ptroot)"); + ensure(desc_ptpre, + verify(desc_ptpre, + getWalkRange<LLTreeIter::DFS_PRE>(ptroot), + WalkExpected<LLTreeIter::DFS_PRE>())); + std::string desc_ptpost("getWalkRange<LLTreeIter::DFS_POST>(ptroot)"); + ensure(desc_ptpost, + verify(desc_ptpost, + getWalkRange<LLTreeIter::DFS_POST>(ptroot), + WalkExpected<LLTreeIter::DFS_POST>())); + std::string desc_ptb("getWalkRange<LLTreeIter::BFS>(ptroot)"); + ensure(desc_ptb, + verify(desc_ptb, + getWalkRange<LLTreeIter::BFS>(ptroot), + WalkExpected<LLTreeIter::BFS>())); + } +} // tut |