diff options
Diffstat (limited to 'indra/llcommon/lltreeiterators.h')
| -rw-r--r-- | indra/llcommon/lltreeiterators.h | 711 |
1 files changed, 711 insertions, 0 deletions
diff --git a/indra/llcommon/lltreeiterators.h b/indra/llcommon/lltreeiterators.h new file mode 100644 index 0000000000..c946566e84 --- /dev/null +++ b/indra/llcommon/lltreeiterators.h @@ -0,0 +1,711 @@ +/** + * @file lltreeiterators.h + * @author Nat Goodspeed + * @date 2008-08-19 + * @brief This file defines iterators useful for traversing arbitrary node + * classes, potentially polymorphic, linked into strict tree + * structures. + * + * Dereferencing any one of these iterators actually yields a @em + * pointer to the node in question. For example, given an + * LLLinkedIter<MyNode> <tt>li</tt>, <tt>*li</tt> gets you a pointer + * to MyNode, and <tt>**li</tt> gets you the MyNode instance itself. + * More commonly, instead of writing <tt>li->member</tt>, you write + * <tt>(*li)->member</tt> -- as you would if you were traversing an + * STL container of MyNode pointers. + * + * It would certainly be possible to build these iterators so that + * <tt>*iterator</tt> would return a reference to the node itself + * rather than a pointer to the node, and for many purposes it would + * even be more convenient. However, that would be insufficiently + * flexible. If you want to use an iterator range to (e.g.) initialize + * a std::vector collecting results -- you rarely want to actually @em + * copy the nodes in question. You're much more likely to want to copy + * <i>pointers to</i> the traversed nodes. Hence these iterators + * produce pointers. + * + * Though you specify the actual NODE class as the template parameter, + * these iterators internally use LLPtrTo<> to discover whether to + * store and return an LLPointer<NODE> or a simple NODE*. + * + * By strict tree structures, we mean that each child must have + * exactly one parent. This forbids a child claiming any ancestor as a + * child of its own. Child nodes with multiple parents will be visited + * once for each parent. Cycles in the graph will result in either an + * infinite loop or an out-of-memory crash. You Have Been Warned. + * + * $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$ + */ + +#if ! defined(LL_LLTREEITERATORS_H) +#define LL_LLTREEITERATORS_H + +#include "llptrto.h" +#include <vector> +#include <deque> +#include <boost/iterator/iterator_facade.hpp> +#include <boost/function.hpp> +#include <boost/static_assert.hpp> + +namespace LLTreeIter +{ + /// Discriminator between LLTreeUpIter and LLTreeDownIter + enum RootIter { UP, DOWN }; + /// Discriminator between LLTreeDFSIter, LLTreeDFSPostIter and LLTreeBFSIter + enum WalkIter { DFS_PRE, DFS_POST, BFS }; +} + +/** + * LLBaseIter defines some machinery common to all these iterators. We use + * boost::iterator_facade to define the iterator boilerplate: the conventional + * operators and methods necessary to implement a standards-conforming + * iterator. That allows us to specify the actual iterator semantics in terms + * of equal(), dereference() and increment() methods. + */ +template <class SELFTYPE, class NODE> +class LLBaseIter: public boost::iterator_facade<SELFTYPE, + // use pointer type as the + // reference type + typename LLPtrTo<NODE>::type, + boost::forward_traversal_tag> +{ +protected: + /// LLPtrTo<NODE>::type is either NODE* or LLPointer<NODE>, as appropriate + typedef typename LLPtrTo<NODE>::type ptr_type; + /// function that advances from this node to next accepts a node pointer + /// and returns another + typedef boost::function<ptr_type(const ptr_type&)> func_type; + typedef SELFTYPE self_type; +}; + +/// Functor returning NULL, suitable for an end-iterator's 'next' functor +template <class NODE> +typename LLPtrTo<NODE>::type LLNullNextFunctor(const typename LLPtrTo<NODE>::type&) +{ + return typename LLPtrTo<NODE>::type(); +} + +/** + * LLLinkedIter is an iterator over an intrusive singly-linked list. The + * beginning of the list is represented by LLLinkedIter(list head); the end is + * represented by LLLinkedIter(). + * + * The begin LLLinkedIter must be instantiated with a functor to extract the + * 'next' pointer from the current node. Supposing that the link pointer is @c + * public, something like: + * + * @code + * NODE* mNext; + * @endcode + * + * you can use (e.g.) <tt>boost::bind(&NODE::mNext, _1)</tt> for the purpose. + * Alternatively, you can bind whatever accessor method is normally used to + * advance to the next node, e.g. for: + * + * @code + * NODE* next() const; + * @endcode + * + * you can use <tt>boost::bind(&NODE::next, _1)</tt>. + */ +template <class NODE> +class LLLinkedIter: public LLBaseIter<LLLinkedIter<NODE>, NODE> +{ + typedef LLBaseIter<LLLinkedIter<NODE>, NODE> super; +protected: + /// some methods need to return a reference to self + typedef typename super::self_type self_type; + typedef typename super::ptr_type ptr_type; + typedef typename super::func_type func_type; +public: + /// Instantiate an LLLinkedIter to start a range, or to end a range before + /// a particular list entry. Pass a functor to extract the 'next' pointer + /// from the current node. + LLLinkedIter(const ptr_type& entry, const func_type& nextfunc): + mCurrent(entry), + mNextFunc(nextfunc) + {} + /// Instantiate an LLLinkedIter to end a range at the end of the list + LLLinkedIter(): + mCurrent(), + mNextFunc(LLNullNextFunctor<NODE>) + {} + +private: + /// leverage boost::iterator_facade + friend class boost::iterator_core_access; + + /// advance + void increment() + { + mCurrent = mNextFunc(mCurrent); + } + /// equality + bool equal(const self_type& that) const { return this->mCurrent == that.mCurrent; } + /// dereference + ptr_type& dereference() const { return const_cast<ptr_type&>(mCurrent); } + + ptr_type mCurrent; + func_type mNextFunc; +}; + +/** + * LLTreeUpIter walks from the node in hand to the root of the tree. The term + * "up" is applied to a tree visualized with the root at the top. + * + * LLTreeUpIter is an alias for LLLinkedIter, since any linked tree that you + * can navigate that way at all contains parent pointers. + */ +template <class NODE> +class LLTreeUpIter: public LLLinkedIter<NODE> +{ + typedef LLLinkedIter<NODE> super; +public: + /// Instantiate an LLTreeUpIter to start from a particular tree node, or + /// to end a parent traversal before reaching a particular ancestor. Pass + /// a functor to extract the 'parent' pointer from the current node. + LLTreeUpIter(const typename super::ptr_type& node, + const typename super::func_type& parentfunc): + super(node, parentfunc) + {} + /// Instantiate an LLTreeUpIter to end a range at the root of the tree + LLTreeUpIter(): + super() + {} +}; + +/** + * LLTreeDownIter walks from the root of the tree to the node in hand. The + * term "down" is applied to a tree visualized with the root at the top. + * + * Though you instantiate the begin() LLTreeDownIter with a pointer to some + * node at an arbitrary location in the tree, the root will be the first node + * you dereference and the passed node will be the last node you dereference. + * + * On construction, LLTreeDownIter walks from the current node to the root, + * capturing the path. Then in use, it replays that walk in reverse. As with + * all traversals of interesting data structures, it is actively dangerous to + * modify the tree during an LLTreeDownIter walk. + */ +template <class NODE> +class LLTreeDownIter: public LLBaseIter<LLTreeDownIter<NODE>, NODE> +{ + typedef LLBaseIter<LLTreeDownIter<NODE>, NODE> super; + typedef typename super::self_type self_type; +protected: + typedef typename super::ptr_type ptr_type; + typedef typename super::func_type func_type; +private: + typedef std::vector<ptr_type> list_type; +public: + /// Instantiate an LLTreeDownIter to end at a particular tree node. Pass a + /// functor to extract the 'parent' pointer from the current node. + LLTreeDownIter(const ptr_type& node, + const func_type& parentfunc) + { + for (ptr_type n = node; n; n = parentfunc(n)) + mParents.push_back(n); + } + /// Instantiate an LLTreeDownIter representing "here", the end of the loop + LLTreeDownIter() {} + +private: + /// leverage boost::iterator_facade + friend class boost::iterator_core_access; + + /// advance + void increment() + { + mParents.pop_back(); + } + /// equality + bool equal(const self_type& that) const { return this->mParents == that.mParents; } + /// implement dereference/indirection operators + ptr_type& dereference() const { return const_cast<ptr_type&>(mParents.back()); } + + list_type mParents; +}; + +/** + * When you want to select between LLTreeUpIter and LLTreeDownIter with a + * compile-time discriminator, use LLTreeRootIter with an LLTreeIter::RootIter + * template arg. + */ +template <LLTreeIter::RootIter DISCRIM, class NODE> +class LLTreeRootIter +{ + enum { use_a_valid_LLTreeIter_RootIter_value = false }; +public: + /// Bogus constructors for default (unrecognized discriminator) case + template <typename TYPE1, typename TYPE2> + LLTreeRootIter(TYPE1, TYPE2) + { + BOOST_STATIC_ASSERT(use_a_valid_LLTreeIter_RootIter_value); + } + LLTreeRootIter() + { + BOOST_STATIC_ASSERT(use_a_valid_LLTreeIter_RootIter_value); + } +}; + +/// Specialize for LLTreeIter::UP +template <class NODE> +class LLTreeRootIter<LLTreeIter::UP, NODE>: public LLTreeUpIter<NODE> +{ + typedef LLTreeUpIter<NODE> super; +public: + /// forward begin ctor + LLTreeRootIter(const typename super::ptr_type& node, + const typename super::func_type& parentfunc): + super(node, parentfunc) + {} + /// forward end ctor + LLTreeRootIter(): + super() + {} +}; + +/// Specialize for LLTreeIter::DOWN +template <class NODE> +class LLTreeRootIter<LLTreeIter::DOWN, NODE>: public LLTreeDownIter<NODE> +{ + typedef LLTreeDownIter<NODE> super; +public: + /// forward begin ctor + LLTreeRootIter(const typename super::ptr_type& node, + const typename super::func_type& parentfunc): + super(node, parentfunc) + {} + /// forward end ctor + LLTreeRootIter(): + super() + {} +}; + +/** + * Instantiated with a tree node, typically the root, LLTreeDFSIter "flattens" + * a depth-first tree walk through that node and all its descendants. + * + * The begin() LLTreeDFSIter must be instantiated with functors to obtain from + * a given node begin() and end() iterators for that node's children. For this + * reason, you must specify the type of the node's child iterator as an + * additional template parameter. + * + * Specifically, the begin functor must return an iterator whose dereferenced + * value is a @em pointer to a child tree node. For instance, if each node + * tracks its children in an STL container of node* pointers, you can simply + * return that container's begin() iterator. + * + * Alternatively, if a node tracks its children with a classic linked list, + * write a functor returning LLLinkedIter<NODE>. + * + * The end() LLTreeDFSIter must, of course, match the begin() iterator's + * template parameters, but is constructed without runtime parameters. + */ +template <class NODE, typename CHILDITER> +class LLTreeDFSIter: public LLBaseIter<LLTreeDFSIter<NODE, CHILDITER>, NODE> +{ + typedef LLBaseIter<LLTreeDFSIter<NODE, CHILDITER>, NODE> super; + typedef typename super::self_type self_type; +protected: + typedef typename super::ptr_type ptr_type; + // The func_type is different for this: from a NODE pointer, we must + // obtain a CHILDITER. + typedef boost::function<CHILDITER(const ptr_type&)> func_type; +private: + typedef std::vector<ptr_type> list_type; +public: + /// Instantiate an LLTreeDFSIter to start a depth-first walk. Pass + /// functors to extract the 'child begin' and 'child end' iterators from + /// each node. + LLTreeDFSIter(const ptr_type& node, const func_type& beginfunc, const func_type& endfunc): + mBeginFunc(beginfunc), + mEndFunc(endfunc), + mSkipChildren(false) + { + // Only push back this node if it's non-NULL! + if (node) + mPending.push_back(node); + } + /// Instantiate an LLTreeDFSIter to mark the end of the walk + LLTreeDFSIter() {} + + /// flags iterator logic to skip traversing children of current node on next increment + void skipDescendants(bool skip = true) { mSkipChildren = skip; } + +private: + /// leverage boost::iterator_facade + friend class boost::iterator_core_access; + + /// advance + /// This implementation is due to http://en.wikipedia.org/wiki/Depth-first_search + void increment() + { + // Capture the node we were just looking at + ptr_type current = mPending.back(); + // Remove it from mPending so we don't process it again later + mPending.pop_back(); + if (!mSkipChildren) + { + // Add all its children to mPending + addChildren(current); + } + // reset flag after each step + mSkipChildren = false; + } + /// equality + bool equal(const self_type& that) const { return this->mPending == that.mPending; } + /// implement dereference/indirection operators + ptr_type& dereference() const { return const_cast<ptr_type&>(mPending.back()); } + + /// Add the direct children of the specified node to mPending + void addChildren(const ptr_type& node) + { + // If we just use push_back() for each child in turn, we'll end up + // processing children in reverse order. We don't want to assume + // CHILDITER is reversible: some of the linked trees we'll be + // processing manage their children using singly-linked lists. So + // figure out how many children there are, grow mPending by that size + // and reverse-copy the children into the new space. + CHILDITER chi = mBeginFunc(node), chend = mEndFunc(node); + // grow mPending by the number of children + mPending.resize(mPending.size() + std::distance(chi, chend)); + // reverse-copy the children into the newly-expanded space + std::copy(chi, chend, mPending.rbegin()); + } + + /// list of the nodes yet to be processed + list_type mPending; + /// functor to extract begin() child iterator + func_type mBeginFunc; + /// functor to extract end() child iterator + func_type mEndFunc; + /// flag which controls traversal of children (skip children of current node if true) + bool mSkipChildren; +}; + +/** + * Instantiated with a tree node, typically the root, LLTreeDFSPostIter + * "flattens" a depth-first tree walk through that node and all its + * descendants. Whereas LLTreeDFSIter visits each node before visiting any of + * its children, LLTreeDFSPostIter visits all of a node's children before + * visiting the node itself. + * + * The begin() LLTreeDFSPostIter must be instantiated with functors to obtain + * from a given node begin() and end() iterators for that node's children. For + * this reason, you must specify the type of the node's child iterator as an + * additional template parameter. + * + * Specifically, the begin functor must return an iterator whose dereferenced + * value is a @em pointer to a child tree node. For instance, if each node + * tracks its children in an STL container of node* pointers, you can simply + * return that container's begin() iterator. + * + * Alternatively, if a node tracks its children with a classic linked list, + * write a functor returning LLLinkedIter<NODE>. + * + * The end() LLTreeDFSPostIter must, of course, match the begin() iterator's + * template parameters, but is constructed without runtime parameters. + */ +template <class NODE, typename CHILDITER> +class LLTreeDFSPostIter: public LLBaseIter<LLTreeDFSPostIter<NODE, CHILDITER>, NODE> +{ + typedef LLBaseIter<LLTreeDFSPostIter<NODE, CHILDITER>, NODE> super; + typedef typename super::self_type self_type; +protected: + typedef typename super::ptr_type ptr_type; + // The func_type is different for this: from a NODE pointer, we must + // obtain a CHILDITER. + typedef boost::function<CHILDITER(const ptr_type&)> func_type; +private: + // Upon reaching a given node in our pending list, we need to know whether + // we've already pushed that node's children, so we must associate a bool + // with each node pointer. + typedef std::vector< std::pair<ptr_type, bool> > list_type; +public: + /// Instantiate an LLTreeDFSPostIter to start a depth-first walk. Pass + /// functors to extract the 'child begin' and 'child end' iterators from + /// each node. + LLTreeDFSPostIter(const ptr_type& node, const func_type& beginfunc, const func_type& endfunc): + mBeginFunc(beginfunc), + mEndFunc(endfunc), + mSkipAncestors(false) + { + if (! node) + return; + mPending.push_back(typename list_type::value_type(node, false)); + makeCurrent(); + } + /// Instantiate an LLTreeDFSPostIter to mark the end of the walk + LLTreeDFSPostIter() {} + + /// flags iterator logic to skip traversing ancestors of current node on next increment + void skipAncestors(bool skip = true) { mSkipAncestors = skip; } + +private: + /// leverage boost::iterator_facade + friend class boost::iterator_core_access; + + /// advance + /// This implementation is due to http://en.wikipedia.org/wiki/Depth-first_search + void increment() + { + // Pop the previous current node + mPending.pop_back(); + makeCurrent(); + } + /// equality + bool equal(const self_type& that) const { return this->mPending == that.mPending; } + /// implement dereference/indirection operators + ptr_type& dereference() const { return const_cast<ptr_type&>(mPending.back().first); } + + struct isOpen + { + bool operator()(const typename list_type::value_type& item) + { + return item.second; + } + }; + + /// Call this each time we change mPending.back() -- that is, every time + /// we're about to change the value returned by dereference(). If we + /// haven't yet pushed the new node's children, do so now. + void makeCurrent() + { + if (mSkipAncestors) + { + mPending.erase(std::remove_if(mPending.begin(), mPending.end(), isOpen()), mPending.end()); + mSkipAncestors = false; + } + + // Once we've popped the last node, this becomes a no-op. + if (mPending.empty()) + return; + // Here mPending.back() holds the node pointer we're proposing to + // dereference next. Have we pushed that node's children yet? + if (mPending.back().second) + return; // if so, it's okay to visit this node now + // We haven't yet pushed this node's children. Do so now. Remember + // that we did -- while the node in question is still back(). + mPending.back().second = true; + addChildren(mPending.back().first); + // Now, because we've just changed mPending.back(), make that new node + // current. + makeCurrent(); + } + + /// Add the direct children of the specified node to mPending + void addChildren(const ptr_type& node) + { + // If we just use push_back() for each child in turn, we'll end up + // processing children in reverse order. We don't want to assume + // CHILDITER is reversible: some of the linked trees we'll be + // processing manage their children using singly-linked lists. So + // figure out how many children there are, grow mPending by that size + // and reverse-copy the children into the new space. + CHILDITER chi = mBeginFunc(node), chend = mEndFunc(node); + // grow mPending by the number of children + mPending.resize(mPending.size() + std::distance(chi, chend)); + // Reverse-copy the children into the newly-expanded space. We can't + // just use std::copy() because the source is a ptr_type, whereas the + // dest is a pair of (ptr_type, bool). + for (typename list_type::reverse_iterator pi = mPending.rbegin(); chi != chend; ++chi, ++pi) + { + pi->first = *chi; // copy the child pointer + pi->second = false; // we haven't yet pushed this child's chldren + } + } + + /// list of the nodes yet to be processed + list_type mPending; + /// functor to extract begin() child iterator + func_type mBeginFunc; + /// functor to extract end() child iterator + func_type mEndFunc; + /// flags logic to skip traversal of ancestors of current node + bool mSkipAncestors; +}; + +/** + * Instantiated with a tree node, typically the root, LLTreeBFSIter "flattens" + * a breadth-first tree walk through that node and all its descendants. + * + * The begin() LLTreeBFSIter must be instantiated with functors to obtain from + * a given node the begin() and end() iterators of that node's children. For + * this reason, you must specify the type of the node's child iterator as an + * additional template parameter. + * + * Specifically, the begin functor must return an iterator whose dereferenced + * value is a @em pointer to a child tree node. For instance, if each node + * tracks its children in an STL container of node* pointers, you can simply + * return that container's begin() iterator. + * + * Alternatively, if a node tracks its children with a classic linked list, + * write a functor returning LLLinkedIter<NODE>. + * + * The end() LLTreeBFSIter must, of course, match the begin() iterator's + * template parameters, but is constructed without runtime parameters. + */ +template <class NODE, typename CHILDITER> +class LLTreeBFSIter: public LLBaseIter<LLTreeBFSIter<NODE, CHILDITER>, NODE> +{ + typedef LLBaseIter<LLTreeBFSIter<NODE, CHILDITER>, NODE> super; + typedef typename super::self_type self_type; +protected: + typedef typename super::ptr_type ptr_type; + // The func_type is different for this: from a NODE pointer, we must + // obtain a CHILDITER. + typedef boost::function<CHILDITER(const ptr_type&)> func_type; +private: + // We need a FIFO queue rather than a LIFO stack. Use a deque rather than + // a vector, since vector can't implement pop_front() efficiently. + typedef std::deque<ptr_type> list_type; +public: + /// Instantiate an LLTreeBFSIter to start a depth-first walk. Pass + /// functors to extract the 'child begin' and 'child end' iterators from + /// each node. + LLTreeBFSIter(const ptr_type& node, const func_type& beginfunc, const func_type& endfunc): + mBeginFunc(beginfunc), + mEndFunc(endfunc) + { + if (node) + mPending.push_back(node); + } + /// Instantiate an LLTreeBFSIter to mark the end of the walk + LLTreeBFSIter() {} + +private: + /// leverage boost::iterator_facade + friend class boost::iterator_core_access; + + /// advance + /// This implementation is due to http://en.wikipedia.org/wiki/Breadth-first_search + void increment() + { + // Capture the node we were just looking at + ptr_type current = mPending.front(); + // Remove it from mPending so we don't process it again later + mPending.pop_front(); + // Add all its children to mPending + CHILDITER chend = mEndFunc(current); + for (CHILDITER chi = mBeginFunc(current); chi != chend; ++chi) + mPending.push_back(*chi); + } + /// equality + bool equal(const self_type& that) const { return this->mPending == that.mPending; } + /// implement dereference/indirection operators + ptr_type& dereference() const { return const_cast<ptr_type&>(mPending.front()); } + + /// list of the nodes yet to be processed + list_type mPending; + /// functor to extract begin() child iterator + func_type mBeginFunc; + /// functor to extract end() child iterator + func_type mEndFunc; +}; + +/** + * When you want to select between LLTreeDFSIter, LLTreeDFSPostIter and + * LLTreeBFSIter with a compile-time discriminator, use LLTreeWalkIter with an + * LLTreeIter::WalkIter template arg. + */ +template <LLTreeIter::WalkIter DISCRIM, class NODE, typename CHILDITER> +class LLTreeWalkIter +{ + enum { use_a_valid_LLTreeIter_WalkIter_value = false }; +public: + /// Bogus constructors for default (unrecognized discriminator) case + template <typename TYPE1, typename TYPE2> + LLTreeWalkIter(TYPE1, TYPE2) + { + BOOST_STATIC_ASSERT(use_a_valid_LLTreeIter_WalkIter_value); + } + LLTreeWalkIter() + { + BOOST_STATIC_ASSERT(use_a_valid_LLTreeIter_WalkIter_value); + } +}; + +/// Specialize for LLTreeIter::DFS_PRE +template <class NODE, typename CHILDITER> +class LLTreeWalkIter<LLTreeIter::DFS_PRE, NODE, CHILDITER>: + public LLTreeDFSIter<NODE, CHILDITER> +{ + typedef LLTreeDFSIter<NODE, CHILDITER> super; +public: + /// forward begin ctor + LLTreeWalkIter(const typename super::ptr_type& node, + const typename super::func_type& beginfunc, + const typename super::func_type& endfunc): + super(node, beginfunc, endfunc) + {} + /// forward end ctor + LLTreeWalkIter(): + super() + {} +}; + +/// Specialize for LLTreeIter::DFS_POST +template <class NODE, typename CHILDITER> +class LLTreeWalkIter<LLTreeIter::DFS_POST, NODE, CHILDITER>: + public LLTreeDFSPostIter<NODE, CHILDITER> +{ + typedef LLTreeDFSPostIter<NODE, CHILDITER> super; +public: + /// forward begin ctor + LLTreeWalkIter(const typename super::ptr_type& node, + const typename super::func_type& beginfunc, + const typename super::func_type& endfunc): + super(node, beginfunc, endfunc) + {} + /// forward end ctor + LLTreeWalkIter(): + super() + {} +}; + +/// Specialize for LLTreeIter::BFS +template <class NODE, typename CHILDITER> +class LLTreeWalkIter<LLTreeIter::BFS, NODE, CHILDITER>: + public LLTreeBFSIter<NODE, CHILDITER> +{ + typedef LLTreeBFSIter<NODE, CHILDITER> super; +public: + /// forward begin ctor + LLTreeWalkIter(const typename super::ptr_type& node, + const typename super::func_type& beginfunc, + const typename super::func_type& endfunc): + super(node, beginfunc, endfunc) + {} + /// forward end ctor + LLTreeWalkIter(): + super() + {} +}; + +#endif /* ! defined(LL_LLTREEITERATORS_H) */ |