Subject: [Boost-commit] svn:boost r50256 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/cursor boost/tree/detail/node libs/tree/test
From: ockham_at_[hidden]
Date: 2008-12-12 19:46:26
Author: bernhard.reiter
Date: 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
New Revision: 50256
URL: http://svn.boost.org/trac/boost/changeset/50256
Log:
Some (bi)nary node related cleanup.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 3
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp | 1
sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp | 110 ++++++++++++++--------------
sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp | 8 +-
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 10 +-
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 3
sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp | 11 ++
sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp | 156 +++++++++++++--------------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 75 +++++++++++++++++--
10 files changed, 202 insertions(+), 177 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -14,6 +14,9 @@
[section TODO]
General:
+* Rename node/nary.hpp back to node/binary.hpp, and cleanup.
+* Extend and parametrize subtree tests (subtree root, subtree size).
+* Clean up node/cursor/binary_tree implementation.
* Fix forest copy
* Fix cursor archetypes: *order copy checks don't compile
* Test insert_cursor independently of algorithms.
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -44,7 +44,7 @@
typedef typename Alloc::template rebind<value_type>::other allocator_type;
private:
- typedef node<value_type, detail::binary_array> node_type;
+ typedef node<value_type/*, detail::binary_array*/> node_type;
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/nary.hpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -62,7 +62,6 @@
typedef node_type* node_pointer;
public:
-
typedef typename mpl::eval_if<
is_const<Node>
, add_const<typename Node::value_type>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/node/nary.hpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -26,7 +26,7 @@
using boost::array;
-template <class T> struct binary_array : public array<T, 2> { };
+//template <class T> struct binary_array : public array<T, 2> { };
//struct node_base;
/*
@@ -61,60 +61,60 @@
}
};
-template <template <typename> class Container>
-class node_base;
+//template <template <typename> class Container>
+//class node_base;
+//
+//template <template <typename> class Container>
+//class node_base : public node_with_parent_base, public Container<node_base<Container>*> {
+// typedef node_base<Container> self_type;
+//
+//public:
+//
+// typedef Container<node_base<Container>*> base_type;
+// typedef typename base_type::size_type size_type;
+// typedef self_type* base_pointer;
+// typedef self_type const* const_base_pointer;
+//
+// node_base() : node_with_parent_base()
+// { }
+//
+// static base_pointer nil()
+// {
+// static self_type m_nil_obj;
+// static base_pointer m_nil = &m_nil_obj;
+// return m_nil;
+// }
+//
+// void init()
+// {
+// for (typename base_type::size_type i=0; i<base_type::size(); ++i)
+// operator[](i) = nil();
+// }
+//
+// // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
+// bool const empty() const
+// {
+// return ((this == nil()) || this->base_type::empty());
+// }
+//
+// // O(n); n is number of parent's children
+// typename base_type::size_type const get_index() const
+// {
+// typename base_type::size_type i = 0;
+// while (static_cast<base_pointer>(this->m_parent)->base_type::operator[](i++) != this);
+// return --i;
+// //return (static_cast<base_pointer>(this->m_parent)->base_type::operator[](0) == this ? 0 : 1);
+// }
+//};
-template <template <typename> class Container>
-class node_base : public node_with_parent_base, public Container<node_base<Container>*> {
- typedef node_base<Container> self_type;
-
-public:
-
- typedef Container<node_base<Container>*> base_type;
- typedef typename base_type::size_type size_type;
- typedef self_type* base_pointer;
- typedef self_type const* const_base_pointer;
-
- node_base() : node_with_parent_base()
- { }
-
- static base_pointer nil()
- {
- static self_type m_nil_obj;
- static base_pointer m_nil = &m_nil_obj;
- return m_nil;
- }
-
- void init()
- {
- for (typename base_type::size_type i=0; i<base_type::size(); ++i)
- operator[](i) = nil();
- }
-
- // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
- bool const empty() const
- {
- return ((this == nil()) || this->base_type::empty());
- }
-
- // O(n); n is number of parent's children
- typename base_type::size_type const get_index() const
- {
- typename base_type::size_type i = 0;
- while (static_cast<base_pointer>(this->m_parent)->base_type::operator[](i++) != this);
- return --i;
- //return (static_cast<base_pointer>(this->m_parent)->base_type::operator[](0) == this ? 0 : 1);
- }
-};
-
-template <>
-class node_base<binary_array>
+//template <>
+class node_base//<binary_array>
: public node_with_parent_base/*, public binary_array<node_base<binary_array>*>*/ {
- typedef node_base<binary_array> self_type;
+ typedef node_base/*<binary_array>*/ self_type;
public:
- typedef binary_array<node_base*> base_type;
+ typedef array<node_base*, 2> base_type;
typedef self_type* base_pointer;
typedef self_type const* const_base_pointer;
@@ -205,18 +205,18 @@
};
-template <typename T, template <typename> class Container>
-class node : public node_base<Container> {
+template <typename T/*, template <typename> class Container*/>
+class node : public node_base/*<Container>*/ {
public:
typedef T value_type;
- typedef Container<node_base<Container>*> container_type;
+// typedef Container<node_base/*<Container>*/*> container_type;
- typedef node<value_type, Container> node_type;
+ typedef node<value_type/*, Container*/> node_type;
typedef node_type* node_pointer;
typedef node_type& node_reference;
//typedef node_pointer position_type;
- typedef node_base<Container> base_type;
+ typedef node_base/*<Container>*/ base_type;
typedef base_type* base_pointer;
typedef base_type const* const_base_pointer;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -157,13 +157,13 @@
template <class InCursor, class OutCursor, class Op>
OutCursor transform (preorder, forest_cursor<InCursor> s, forest_cursor<OutCursor> t, Op op)
{
- return transform(preorder(), InCursor(s), InCursor(t), op);
+ return transform(preorder(), InCursor(s), OutCursor(t), op);
}
template <class InCursor, class OutCursor>
OutCursor copy (preorder, forest_cursor<InCursor> s, forest_cursor<OutCursor> t)
{
- return copy(preorder(), InCursor(s), InCursor(t));
+ return copy(preorder(), InCursor(s), OutCursor(t));
}
/// Postoder - inorder
@@ -177,13 +177,13 @@
template <class InCursor, class OutCursor, class Op>
OutCursor transform (postorder, forest_cursor<InCursor> s, forest_cursor<OutCursor> t, Op op)
{
- return transform(inorder(), InCursor(s), InCursor(t), op);
+ return transform(inorder(), InCursor(s), OutCursor(t), op);
}
template <class InCursor, class OutCursor>
OutCursor copy (postorder, forest_cursor<InCursor> s, forest_cursor<OutCursor> t)
{
- return copy(inorder(), InCursor(s), InCursor(t));
+ return copy(inorder(), InCursor(s), OutCursor(t));
}
} // namespace tree
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -62,7 +62,7 @@
{}
};
- typedef node<value_type, mycontainer> node_type;
+ typedef node<value_type/*, mycontainer*/> node_type;
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
typedef typename node_traits<node_type>::node_base_type node_base_type;
@@ -86,11 +86,11 @@
explicit nary_tree (allocator_type const& alloc = allocator_type())
: m_header(), m_value_alloc(alloc)
{
- m_header.push_back(node_base_type::nil());
- m_header.push_back(&m_header);
+// m_header.push_back(node_base_type::nil());
+// m_header.push_back(&m_header);
-// m_header[0] = node_base_type::nil();
-// m_header[1] = &m_header;
+ m_header.m_children[0] = node_base_type::nil();
+ m_header.m_children[1] = &m_header;
}
explicit nary_tree (size_type n, value_type const& value = value_type(),
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -21,6 +21,7 @@
{
binary_tree<int> bt0;
BOOST_CHECK(bt0.root().empty());
+ //BOOST_CHECK(bt0.root().begin() == bt0.root().end()); //FIXME
// test with allocator?
}
@@ -30,7 +31,7 @@
binary_tree<int> bt0;
BOOST_CHECK(bt0.root().empty());
- binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8);
+ binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8); //FIXME
c.to_begin();
BOOST_CHECK(c == bt0.root().begin());
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -37,6 +37,17 @@
test_traversal(Order(), l.begin(), l.end());
}
+BOOST_AUTO_TEST_CASE( test_foreach_subtree3 )
+{
+ boost::tree::for_each(
+ preorder(),
+ bt.root().begin(),
+ boost::lambda::bind(&std::list<int>::push_back, &l, boost::lambda::_1)
+ );
+ test_subtree_traversal(preorder(), l.begin(), l.end(), 1);
+ BOOST_CHECK_EQUAL(l.size(), 5);
+}
+
BOOST_AUTO_TEST_CASE_TEMPLATE( test_copy, Order, orders)
{
boost::tree::copy(Order(), bt.root(), o);
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/iterator_algorithm_test.cpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -25,108 +25,6 @@
BOOST_FIXTURE_TEST_SUITE( iterator_algorithms_test, test_binary_tree_with_list_fixture<int> )
-//template <class Cursor, class Op>
-//void underefed_for_each_recursive(Cursor s, Op& f)
-//{
-// Cursor t = s.end();
-// f(s); // Caution: f(s) comes before s.to_begin(), as opposed to
-// s.to_begin(); // "normal" preorder for_each
-// do
-// if (!s.empty())
-// underefed_for_each_recursive(s, f);
-// while (s++ != t);
-//}
-//
-//template <class Cursor, class Op>
-//Op underefed_for_each(Cursor s, Op f)
-//{
-// Cursor t = s.end();
-// f(s); // Caution: f(s) comes before s.to_begin(), as opposed to
-// s.to_begin(); // "normal" preorder for_each
-// do
-// if (!s.empty())
-// underefed_for_each_recursive(s, f);
-// while (s++ != t);
-//
-// return f;
-//}
-//
-//template <class Order>
-//void comparisons_using_ac(binary_tree<int>::cursor c) {
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(c));
-//}
-//
-//template <class Order>
-//void comparisons_using_rtc(binary_tree<int>::cursor c) {
-// compare_cursor_to_iterator_traversal(Order(), c);
-//}
-
-/**
- * Check all iterator traversals by comparing them to a recursive cursor
- * algorithm output. Do that at different stages of the tree while adding
- * elements to it, so different tree shapes are checked to be catered for
- * by the iterator algorithms.
- *
- * Afterwards, do all that using iterators wrapped around
- * "explicit stack"-based cursors also.
- *
- * FIXME: This depends too much on the correct behavior of cursor algorithms.
- * Do check algorithms, but with ready-made, differently shaped trees.
- */
-//void compare_cursor_to_iterator_traversal() {
-//BOOST_AUTO_TEST_CASE_TEMPLATE( compare_cursor_to_iterator_traversal_test, Order, orders )
-//{
-// binary_tree<int> test_tree2;
-// //test::compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-//
-// binary_tree<int>::cursor c = test_tree2.insert(test_tree2.root(), 8);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// c = test_tree2.insert(c.to_begin(), 3);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// test_tree2.insert(c.to_begin(), 1);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// c = test_tree2.insert(++c, 6);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// test_tree2.insert(c.to_begin(), 4);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// test_tree2.insert(++c, 7);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// c = test_tree2.insert(test_tree2.root().end(), 10);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// c = test_tree2.insert(test_tree2.root().end().end(), 14);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// c = test_tree2.insert(c.to_begin(), 13);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// c = test_tree2.insert(c.to_begin(), 11);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// c = test_tree2.insert(++c, 12);
-// compare_cursor_to_iterator_traversal(Order(), test_tree2.root());
-// compare_cursor_to_iterator_traversal(Order(), make_ascending_cursor(test_tree2.root()));
-//
-// underefed_for_each(test_tree2.root(), comparisons_using_ac<Order>);
-// underefed_for_each(test_tree2.root(), comparisons_using_rtc<Order>);
-//}
-
BOOST_AUTO_TEST_CASE_TEMPLATE( test_iterator_algorithms, Order, orders )
{
test_traversal(Order(), begin(Order(), bt.root())
@@ -151,6 +49,60 @@
, end(Order(), make_ascending_cursor(bt.root()))), 11);
}
+BOOST_AUTO_TEST_CASE( test_subtree3_iterator_algorithms )
+{
+ test_subtree_traversal(preorder(), begin(preorder(), bt.root().begin())
+ , end(preorder(), bt.root().begin()), 1);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), bt.root().begin())
+ , end(preorder(), bt.root().begin())), 5);
+
+ test_subtree_traversal(inorder(), begin(inorder(), bt.root().begin())
+ , end(inorder(), bt.root().begin()), 0);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), bt.root().begin())
+ , end(inorder(), bt.root().begin())), 5);
+
+ test_subtree_traversal(postorder(), begin(postorder(), bt.root().begin())
+ , end(postorder(), bt.root().begin()), 0);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), bt.root().begin())
+ , end(postorder(), bt.root().begin())), 5);
+}
+
+BOOST_AUTO_TEST_CASE( test_subtree6_iterator_algorithms )
+{
+ test_subtree_traversal(preorder(), begin(preorder(), bt.root().begin().end())
+ , end(preorder(), bt.root().begin().end()), 3);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), bt.root().begin().end())
+ , end(preorder(), bt.root().begin().end())), 3);
+
+ test_subtree_traversal(inorder(), begin(inorder(), bt.root().begin().end())
+ , end(inorder(), bt.root().begin().end()), 2);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), bt.root().begin().end())
+ , end(inorder(), bt.root().begin().end())), 3);
+
+ test_subtree_traversal(postorder(), begin(postorder(), bt.root().begin().end())
+ , end(postorder(), bt.root().begin().end()), 1);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), bt.root().begin().end())
+ , end(postorder(), bt.root().begin().end())), 3);
+}
+
+BOOST_AUTO_TEST_CASE( test_subtree10_iterator_algorithms )
+{
+ test_subtree_traversal(preorder(), begin(preorder(), bt.root().end())
+ , end(preorder(), bt.root().end()), 6);
+ BOOST_CHECK_EQUAL(std::distance(begin(preorder(), bt.root().end())
+ , end(preorder(), bt.root().end())), 5);
+
+ test_subtree_traversal(inorder(), begin(inorder(), bt.root().end())
+ , end(inorder(), bt.root().end()), 6);
+ BOOST_CHECK_EQUAL(std::distance(begin(inorder(), bt.root().end())
+ , end(inorder(), bt.root().end())), 5);
+
+ test_subtree_traversal(postorder(), begin(postorder(), bt.root().end())
+ , end(postorder(), bt.root().end()), 5);
+ BOOST_CHECK_EQUAL(std::distance(begin(postorder(), bt.root().end())
+ , end(postorder(), bt.root().end())), 5);
+}
+
BOOST_AUTO_TEST_CASE( test_ascending_iterator_algorithms )
{
binary_tree<int>::cursor c = bt.root();
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp 2008-12-12 19:46:25 EST (Fri, 12 Dec 2008)
@@ -162,15 +162,35 @@
}
template <class Iterator>
-void test_subtree_traversal(boost::tree::preorder, Iterator a, Iterator b)
+void test_subtree_traversal(boost::tree::preorder, Iterator a, Iterator b
+ , std::vector<int>::difference_type x = 0)
{
- BOOST_CHECK_EQUAL(*a++, 3);
- BOOST_CHECK_EQUAL(*a++, 1);
- BOOST_CHECK_EQUAL(*a++, 6);
- BOOST_CHECK_EQUAL(*a++, 4);
- BOOST_CHECK_EQUAL(*a++, 7);
- BOOST_CHECK(a == b);
-}
+ std::vector<int> preorder(11);
+ preorder[0] = 8;
+ preorder[1] = 3;
+ preorder[2] = 1;
+ preorder[3] = 6;
+ preorder[4] = 4;
+ preorder[5] = 7;
+ preorder[6] = 10;
+ preorder[7] = 14;
+ preorder[8] = 13;
+ preorder[9] = 11;
+ preorder[10] = 12;
+
+ BOOST_CHECK(std::equal(a, b, preorder.begin() + x));
+}
+
+//template <class Iterator>
+//void test_subtree_traversal(boost::tree::preorder, Iterator a, Iterator b)
+//{
+// BOOST_CHECK_EQUAL(*a++, 3);
+// BOOST_CHECK_EQUAL(*a++, 1);
+// BOOST_CHECK_EQUAL(*a++, 6);
+// BOOST_CHECK_EQUAL(*a++, 4);
+// BOOST_CHECK_EQUAL(*a++, 7);
+// BOOST_CHECK(a == b);
+//}
template <class Iterator>
void test_traversal(boost::tree::inorder, Iterator a, Iterator b)
@@ -206,6 +226,25 @@
BOOST_CHECK(a == b);
}
+template <class Iterator>
+void test_subtree_traversal(boost::tree::inorder, Iterator a, Iterator b
+ , std::vector<int>::difference_type x = 0)
+{
+ std::vector<int> inorder(11);
+ inorder[0] = 1;
+ inorder[1] = 3;
+ inorder[2] = 4;
+ inorder[3] = 6;
+ inorder[4] = 7;
+ inorder[5] = 8;
+ inorder[6] = 10;
+ inorder[7] = 11;
+ inorder[8] = 12;
+ inorder[9] = 13;
+ inorder[10] = 14;
+
+ BOOST_CHECK(std::equal(a, b, inorder.begin() + x));
+}
template <class Iterator>
void test_traversal(boost::tree::postorder, Iterator a, Iterator b)
@@ -242,6 +281,26 @@
}
template <class Iterator>
+void test_subtree_traversal(boost::tree::postorder, Iterator a, Iterator b
+ , std::vector<int>::difference_type x = 0)
+{
+ std::vector<int> postorder(11);
+ postorder[0] = 1;
+ postorder[1] = 4;
+ postorder[2] = 7;
+ postorder[3] = 6;
+ postorder[4] = 3;
+ postorder[5] = 12;
+ postorder[6] = 11;
+ postorder[7] = 13;
+ postorder[8] = 14;
+ postorder[9] = 10;
+ postorder[10] = 8;
+
+ BOOST_CHECK(std::equal(a, b, postorder.begin() + x));
+}
+
+template <class Iterator>
void test_traversal_from_leaf4(Iterator a, Iterator b)
{
BOOST_CHECK_EQUAL(*a, 4);