From: ockham_at_[hidden]
Date: 2007-10-10 18:21:52
Author: bernhard.reiter
Date: 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
New Revision: 39912
URL: http://svn.boost.org/trac/boost/changeset/39912
Log:
* output_cursor_iterator_wrapper:
Add more comments, change implementation to work with a pointer
(instead of a reference) to an output iterator.
* Re-organise some test files (mainly algorithm-related ones).
Added:
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp (contents, props changed)
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp (contents, props changed)
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp | 6 +
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp | 7 +
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp | 7 +
sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp | 57 ++++++++++---
sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 | 1
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 1
sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp | 36 --------
sandbox/SOC/2006/tree/trunk/libs/tree/test/rotate_binary_tree_test.cpp | 1
sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp | 169 ---------------------------------------
9 files changed, 68 insertions(+), 217 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/inorder.hpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -59,6 +59,12 @@
return f;
}
+/**
+ * @brief Copies the subtree s into t, by traversing s in inorder.
+ * @param s An input cursor.
+ * @param t An output cursor.
+ * @result A cursor past t's inorder end, after the copying operation.
+ */
template <class InCursor, class OutCursor>
OutCursor copy (InCursor s, OutCursor t)
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/postorder.hpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -62,7 +62,12 @@
}
//]
-// TODO: Should work with root() instead of root().begin()
+/**
+ * @brief Copies the subtree s into t, by traversing s in postorder.
+ * @param s An input cursor.
+ * @param t An output cursor.
+ * @result A cursor past t's postorder end, after the copying operation.
+ */
template <class InCursor, class OutCursor>
OutCursor copy (InCursor s, OutCursor t)
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm/preorder.hpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -58,6 +58,13 @@
return f;
}
+/**
+ * @brief Copies the subtree s into t, by traversing s in preorder.
+ * @param s An input cursor.
+ * @param t An output cursor.
+ * @result A cursor past t's preorder end, after the copying operation.
+ */
+ // TODO: Should work with root() instead of root().begin() (same for in- and postorder)
template <class InCursor, class OutCursor>
OutCursor copy (InCursor s, OutCursor t)
{
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -90,37 +90,68 @@
struct ascending_random_access_cursor_tag
: public descending_random_access_cursor_tag {};
+/**
+ * @brief Output cursor wrapper around an output iterator.
+ *
+ * This can be very useful e.g. to have cursor algorithms actually work on
+ * iterators, thus permitting some kind of linearization of a given subtree.
+ * (Modelled after std::insert_iterator and the like.)
+ *
+ * For construction, the outputter_cursor_iterator_wrapper might come in useful
+ * in saving keystrokes.
+ */
// TODO: Complete this.
template<class OutputIterator>
class output_cursor_iterator_wrapper {
protected:
- OutputIterator& iter;
+ OutputIterator* iter;
public:
- explicit output_cursor_iterator_wrapper(OutputIterator& i) : iter(i) {}
-
- output_cursor_iterator_wrapper& operator=(output_cursor_iterator_wrapper const& x)
- {
- iter = x.iter;
- return *this;
- }
-
- // Unfortunately, Output Iterators do not necessarily expose their
- // value_type (they just give void), so the following member
- // function has to be a template.
+ /// Make the iterator type publicly accessible.
+ typedef OutputIterator iterator;
+
+ /**
+ * For construction, we obviously need an Output Iterator to work on (i.e., write to).
+ */
+ explicit output_cursor_iterator_wrapper(OutputIterator& i) : iter(&i) {}
+
+ /**
+ * @param value A const& value of the value_type of container that iter is
+ * associated with.
+ * @return This cursor, for chained operations.
+ * Assigning a value to this cursor will insert it before iter, the iterator it is
+ * wrapped around.
+ *
+ * Unfortunately, Output Iterators do not necessarily expose their
+ * value_type (they might just give back void), so the following assignment operator
+ * has to be a template.
+ */
// TODO: Consult C++0x if this has been changed
template <class ValueType>
output_cursor_iterator_wrapper& operator=(ValueType const& value)
{
- *(iter++) = value;
+ *((*iter)++) = value;
return *this;
}
+ /// Returns *this.
output_cursor_iterator_wrapper& operator*() { return *this; }
+
+ /// Returns *this, as this %cursor doesn't "move".
output_cursor_iterator_wrapper& operator++() { return *this; }
+
+ /// Returns *this, as this %cursor doesn't "move".
output_cursor_iterator_wrapper operator++(int) { return *this; }
+
+ /// Returns *this, as this %cursor doesn't "move".
output_cursor_iterator_wrapper& begin() { return *this; }
};
+/**
+ * @param o An output iterator.
+ * @result An instance of output_cursor_iterator_wrapper working on o.
+ *
+ * Use as shortcut for cumbersome typenames, just as with std::inserter and the like.
+ */
template<class OutputIterator>
inline output_cursor_iterator_wrapper<OutputIterator>
outputter_cursor_iterator_wrapper(OutputIterator o)
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -23,6 +23,7 @@
[ run key_search_binary_tree_test.cpp ]
[ run rank_search_binary_tree_test.cpp ]
[ run traverse_binary_tree_test.cpp ]
+ [ run subtree_algorithms_test.cpp ]
[ run rotate_binary_tree_test.cpp ]
[ run string_search_binary_tree_test.cpp ]
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 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -11,6 +11,7 @@
#include <boost/test/minimal.hpp>
#include "helpers.hpp"
+#include "test_tree_traversal_data.hpp"
//TODO: Make this a test suite.
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/helpers.hpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -52,43 +52,7 @@
return this->c;
}
};
-// Test data from http://en.wikipedia.org/wiki/Image:Binary_search_tree.svg
-// (with root modified to carry 8 instead of 7, and with two additional nodes:
-// 11 inserted left of 13; 12 right of 11)
-// and in combination with http://en.wikipedia.org/wiki/Tree_traversal#Examples
-// (as tree shapes are equal [apart from the extra nodes])
-template <class Tree>
-void create_test_data_tree(Tree& ret)
-{
- typename Tree::cursor cur = ret.insert(ret.shoot(), 8);
- cur = ret.insert(cur, 3);
- ret.insert(cur, 1);
- cur = ret.insert(++cur, 6);
- ret.insert(cur, 4);
- ret.insert(++cur, 7);
- cur = ret.insert(ret.root().end(), 10);
- cur = ret.insert(ret.root().end().end(), 14);
- cur = ret.insert(cur, 13);
- cur = ret.insert(cur, 11);
- cur = ret.insert(++cur, 12);
-}
-template <class Tree>
-void validate_test_data_tree(Tree const& ret)
-{
- BOOST_CHECK(*ret.root().begin() == 8);
- BOOST_CHECK(*ret.root().begin().begin() == 3);
- BOOST_CHECK(*ret.root().begin().begin().begin() == 1);
- BOOST_CHECK(*ret.root().begin().end().begin() == 6);
- BOOST_CHECK(*ret.root().begin().end().begin().begin() == 4);
- BOOST_CHECK(*ret.root().begin().end().end().begin() == 7);
-
- BOOST_CHECK(*ret.root().end().begin() == 10);
- BOOST_CHECK(*ret.root().end().end().begin() == 14);
- BOOST_CHECK(*ret.root().end().end().begin().begin() == 13);
- BOOST_CHECK(*ret.root().end().end().begin().begin().begin() == 11);
- BOOST_CHECK(*ret.root().end().end().begin().begin().end().begin() == 12);
-}
template <class Searcher>
void create_test_data_searcher(Searcher& my_tree)
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/rotate_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/rotate_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/rotate_binary_tree_test.cpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -9,6 +9,7 @@
#include <boost/tree/searcher.hpp>
#include "helpers.hpp"
+#include "test_tree_traversal_data.hpp"
#include <boost/test/minimal.hpp>
Added: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_test.cpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -0,0 +1,84 @@
+// Copyright (c) 2006, Bernhard Reiter
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+//TODO: Make this a test suite.
+// Add iterator traversal tests - check if proper overloads (if present)
+// are used.
+
+// TODO: get timings. that makes that no testcase anymore, right?
+//does boost have timers? what does the austern et al one look like?
+
+#include <boost/tree/binary_tree.hpp>
+
+#include <boost/tree/iterator.hpp>
+#include <boost/tree/traversal.hpp>
+
+#include <boost/test/minimal.hpp>
+
+#include <list>
+#include <iterator>
+
+#include "helpers.hpp"
+#include "test_tree_traversal_data.hpp"
+
+using namespace boost::tree;
+
+
+int test_main(int, char* [])
+{
+ using boost::forward_traversal_tag;
+
+ binary_tree<int> test_tree, test_tree2;
+ create_test_data_tree(test_tree);
+ create_test_data_tree(test_tree2);
+// BOOST_CHECK(test_tree == test_tree2);
+
+ binary_tree<int>::cursor c = test_tree.root();
+ binary_tree<int>::cursor d = test_tree2.root();
+
+ d = d.begin().end().begin().begin();
+ *d = 29;
+
+ d = test_tree2.root();
+
+ // output_cursor_iterator_wrapper tests
+
+ // preorder::copy tests
+ std::list<int> test_list;
+ typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
+ typedef output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
+ back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
+ oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
+ preorder::copy(c.begin(), oc_test_list);
+ test_preorder_traversal(test_list.begin(), test_list.end());
+
+ // inorder::copy tests
+ test_list.clear();
+ it_test_list = std::back_inserter(test_list);
+ oc_test_list = oc_bi_lst_type(it_test_list);
+ inorder::copy(c.begin(), oc_test_list);
+ test_inorder_traversal(test_list.begin(), test_list.end());
+
+ // postorder::copy tests
+ test_list.clear();
+ it_test_list = std::back_inserter(test_list);
+ oc_test_list = oc_bi_lst_type(it_test_list);
+ postorder::copy(c.begin(), oc_test_list);
+ test_postorder_traversal(test_list.begin(), test_list.end());
+
+ // Using a list iterator
+ test_list.clear();
+ test_list.resize(11);
+ typedef output_cursor_iterator_wrapper<std::list<int>::iterator> oc_lst_type;
+ std::list<int>::iterator li = test_list.begin();
+ oc_lst_type oc_lst(li);
+ postorder::copy(c.begin(), oc_lst);
+ test_postorder_traversal(test_list.begin(), test_list.end());
+
+ return 0;
+}
+
+
Added: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -0,0 +1,157 @@
+// Copyright (c) 2006, Bernhard Reiter
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+
+#include <boost/test/minimal.hpp>
+
+// Test data from http://en.wikipedia.org/wiki/Image:Binary_search_tree.svg
+// (With two additional nodes: 11 inserted left of 13; 12 right of 11)
+// and in combination with http://en.wikipedia.org/wiki/Tree_traversal#Examples
+// (as tree shapes are equal [apart from the extra nodes])
+template <class Tree>
+void create_test_data_tree(Tree& ret)
+{
+ typename Tree::cursor cur = ret.insert(ret.shoot(), 8);
+ cur = ret.insert(cur, 3);
+ ret.insert(cur, 1);
+ cur = ret.insert(++cur, 6);
+ ret.insert(cur, 4);
+ ret.insert(++cur, 7);
+ cur = ret.insert(ret.root().end(), 10);
+ cur = ret.insert(ret.root().end().end(), 14);
+ cur = ret.insert(cur, 13);
+ cur = ret.insert(cur, 11);
+ cur = ret.insert(++cur, 12);
+}
+
+template <class Tree>
+void validate_test_data_tree(Tree const& ret)
+{
+ BOOST_CHECK(*ret.root().begin() == 8);
+ BOOST_CHECK(*ret.root().begin().begin() == 3);
+ BOOST_CHECK(*ret.root().begin().begin().begin() == 1);
+ BOOST_CHECK(*ret.root().begin().end().begin() == 6);
+ BOOST_CHECK(*ret.root().begin().end().begin().begin() == 4);
+ BOOST_CHECK(*ret.root().begin().end().end().begin() == 7);
+
+ BOOST_CHECK(*ret.root().end().begin() == 10);
+ BOOST_CHECK(*ret.root().end().end().begin() == 14);
+ BOOST_CHECK(*ret.root().end().end().begin().begin() == 13);
+ BOOST_CHECK(*ret.root().end().end().begin().begin().begin() == 11);
+ BOOST_CHECK(*ret.root().end().end().begin().begin().end().begin() == 12);
+}
+
+template <class Iterator>
+void test_preorder_traversal(Iterator a, Iterator b)
+{
+ BOOST_CHECK(*a++ == 8);
+ BOOST_CHECK(*a++ == 3);
+ BOOST_CHECK(*a++ == 1);
+ BOOST_CHECK(*a++ == 6);
+ BOOST_CHECK(*a++ == 4);
+ BOOST_CHECK(*a++ == 7);
+ BOOST_CHECK(*a++ == 10);
+ BOOST_CHECK(*a++ == 14);
+ BOOST_CHECK(*a++ == 13);
+ BOOST_CHECK(*a++ == 11);
+ BOOST_CHECK(*a++ == 12);
+ BOOST_CHECK(a == b);
+}
+
+template <class Iterator>
+void test_reverse_preorder_traversal(Iterator a, Iterator b)
+{
+ BOOST_CHECK(*--a == 12);
+ BOOST_CHECK(*--a == 11);
+ BOOST_CHECK(*--a == 13);
+ BOOST_CHECK(*--a == 14);
+ BOOST_CHECK(*--a == 10);
+ BOOST_CHECK(*--a == 7);
+ BOOST_CHECK(*--a == 4);
+ BOOST_CHECK(*--a == 6);
+ BOOST_CHECK(*--a == 1);
+ BOOST_CHECK(*--a == 3);
+ BOOST_CHECK(*--a == 8);
+ BOOST_CHECK(a == b);
+}
+
+template <class Iterator>
+void test_inorder_traversal(Iterator a, Iterator b)
+{
+ BOOST_CHECK(*a++ == 1);
+ BOOST_CHECK(*a++ == 3);
+ BOOST_CHECK(*a++ == 4);
+ BOOST_CHECK(*a++ == 6);
+ BOOST_CHECK(*a++ == 7);
+ BOOST_CHECK(*a++ == 8);
+ BOOST_CHECK(*a++ == 10);
+ BOOST_CHECK(*a++ == 11);
+ BOOST_CHECK(*a++ == 12);
+ BOOST_CHECK(*a++ == 13);
+ BOOST_CHECK(*a++ == 14);
+ BOOST_CHECK(a == b);
+}
+
+template <class Iterator>
+void test_reverse_inorder_traversal(Iterator a, Iterator b)
+{
+ BOOST_CHECK(*--a == 14);
+ BOOST_CHECK(*--a == 13);
+ BOOST_CHECK(*--a == 12);
+ BOOST_CHECK(*--a == 11);
+ BOOST_CHECK(*--a == 10);
+ BOOST_CHECK(*--a == 8);
+ BOOST_CHECK(*--a == 7);
+ BOOST_CHECK(*--a == 6);
+ BOOST_CHECK(*--a == 4);
+ BOOST_CHECK(*--a == 3);
+ BOOST_CHECK(*--a == 1);
+ BOOST_CHECK(a == b);
+}
+
+template <class Iterator>
+void test_postorder_traversal(Iterator a, Iterator b)
+{
+ BOOST_CHECK(*a++ == 1);
+ BOOST_CHECK(*a++ == 4);
+ BOOST_CHECK(*a++ == 7);
+ BOOST_CHECK(*a++ == 6);
+ BOOST_CHECK(*a++ == 3);
+ BOOST_CHECK(*a++ == 12);
+ BOOST_CHECK(*a++ == 11);
+ BOOST_CHECK(*a++ == 13);
+ BOOST_CHECK(*a++ == 14);
+ BOOST_CHECK(*a++ == 10);
+ BOOST_CHECK(*a++ == 8);
+ BOOST_CHECK(a == b);
+}
+
+template <class Iterator>
+void test_reverse_postorder_traversal(Iterator a, Iterator b)
+{
+ BOOST_CHECK(*--a == 8);
+ BOOST_CHECK(*--a == 10);
+ BOOST_CHECK(*--a == 14);
+ BOOST_CHECK(*--a == 13);
+ BOOST_CHECK(*--a == 11);
+ BOOST_CHECK(*--a == 12);
+ BOOST_CHECK(*--a == 3);
+ BOOST_CHECK(*--a == 6);
+ BOOST_CHECK(*--a == 7);
+ BOOST_CHECK(*--a == 4);
+ BOOST_CHECK(*--a == 1);
+ BOOST_CHECK(a == b);
+}
+
+template <class Iterator>
+void test_ascending_traversal_from_leaf4(Iterator a, Iterator b)
+{
+ BOOST_CHECK(*a == 4);
+ BOOST_CHECK(*++a == 6);
+ BOOST_CHECK(*++a == 3);
+ BOOST_CHECK(*++a == 8);
+ BOOST_CHECK(++a == b);
+}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp 2007-10-10 18:21:51 EDT (Wed, 10 Oct 2007)
@@ -22,126 +22,10 @@
#include <iterator>
#include "helpers.hpp"
+#include "test_tree_traversal_data.hpp"
using namespace boost::tree;
-
-//std::vector<int> preorder_data()
-//{
-// std::vector ret(9);
-// ret[0] = 8;
-// ret[1] = 3;
-// ret[2] = 1;
-// ret[3] = 6;
-// ret[4] = 4;
-// ret[5] = 7;
-// ret[6] = 10;
-// ret[7] = 14;
-// ret[8] = 13;
-//}
-
-template <class Iterator>
-void test_inorder_traversal(Iterator a, Iterator b)
-{
- BOOST_CHECK(*a++ == 1);
- BOOST_CHECK(*a++ == 3);
- BOOST_CHECK(*a++ == 4);
- BOOST_CHECK(*a++ == 6);
- BOOST_CHECK(*a++ == 7);
- BOOST_CHECK(*a++ == 8);
- BOOST_CHECK(*a++ == 10);
- BOOST_CHECK(*a++ == 11);
- BOOST_CHECK(*a++ == 12);
- BOOST_CHECK(*a++ == 13);
- BOOST_CHECK(*a++ == 14);
- BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_reverse_inorder_traversal(Iterator a, Iterator b)
-{
- BOOST_CHECK(*--a == 14);
- BOOST_CHECK(*--a == 13);
- BOOST_CHECK(*--a == 12);
- BOOST_CHECK(*--a == 11);
- BOOST_CHECK(*--a == 10);
- BOOST_CHECK(*--a == 8);
- BOOST_CHECK(*--a == 7);
- BOOST_CHECK(*--a == 6);
- BOOST_CHECK(*--a == 4);
- BOOST_CHECK(*--a == 3);
- BOOST_CHECK(*--a == 1);
- BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_preorder_traversal(Iterator a, Iterator b)
-{
- BOOST_CHECK(*a++ == 8);
- BOOST_CHECK(*a++ == 3);
- BOOST_CHECK(*a++ == 1);
- BOOST_CHECK(*a++ == 6);
- BOOST_CHECK(*a++ == 4);
- BOOST_CHECK(*a++ == 7);
- BOOST_CHECK(*a++ == 10);
- BOOST_CHECK(*a++ == 14);
- BOOST_CHECK(*a++ == 13);
- BOOST_CHECK(*a++ == 11);
- BOOST_CHECK(*a++ == 12);
- BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_reverse_preorder_traversal(Iterator a, Iterator b)
-{
- BOOST_CHECK(*--a == 12);
- BOOST_CHECK(*--a == 11);
- BOOST_CHECK(*--a == 13);
- BOOST_CHECK(*--a == 14);
- BOOST_CHECK(*--a == 10);
- BOOST_CHECK(*--a == 7);
- BOOST_CHECK(*--a == 4);
- BOOST_CHECK(*--a == 6);
- BOOST_CHECK(*--a == 1);
- BOOST_CHECK(*--a == 3);
- BOOST_CHECK(*--a == 8);
- BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_postorder_traversal(Iterator a, Iterator b)
-{
- BOOST_CHECK(*a++ == 1);
- BOOST_CHECK(*a++ == 4);
- BOOST_CHECK(*a++ == 7);
- BOOST_CHECK(*a++ == 6);
- BOOST_CHECK(*a++ == 3);
- BOOST_CHECK(*a++ == 12);
- BOOST_CHECK(*a++ == 11);
- BOOST_CHECK(*a++ == 13);
- BOOST_CHECK(*a++ == 14);
- BOOST_CHECK(*a++ == 10);
- BOOST_CHECK(*a++ == 8);
- BOOST_CHECK(a == b);
-}
-
-template <class Iterator>
-void test_reverse_postorder_traversal(Iterator a, Iterator b)
-{
- BOOST_CHECK(*--a == 8);
- BOOST_CHECK(*--a == 10);
- BOOST_CHECK(*--a == 14);
- BOOST_CHECK(*--a == 13);
- BOOST_CHECK(*--a == 11);
- BOOST_CHECK(*--a == 12);
- BOOST_CHECK(*--a == 3);
- BOOST_CHECK(*--a == 6);
- BOOST_CHECK(*--a == 7);
- BOOST_CHECK(*--a == 4);
- BOOST_CHECK(*--a == 1);
- BOOST_CHECK(a == b);
-}
-
int test_main(int, char* [])
{
using boost::forward_traversal_tag;
@@ -176,57 +60,8 @@
BOOST_CHECK(*c == 4);
ascending::iterator<binary_tree<int>::cursor> ais(c);
- BOOST_CHECK(*ais == 4);
- BOOST_CHECK(*++ais == 6);
- BOOST_CHECK(*++ais == 3);
- BOOST_CHECK(*++ais == 8);
- BOOST_CHECK(++ais == ai_root);
-
- binary_tree<int> test_tree2;
- create_test_data_tree(test_tree2);
-// BOOST_CHECK(test_tree == test_tree2);
-
- binary_tree<int>::cursor d = test_tree2.root();
- d = d.begin().end().begin().begin();
- *d = 29;
-
- c = test_tree.root();
- d = test_tree2.root();
+ test_ascending_traversal_from_leaf4(ais, ai_root);
- // output_cursor_iterator_wrapper tests
-
- // preorder::copy tests
- std::list<int> pre_lst;
- typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
- typedef output_cursor_iterator_wrapper<back_insert_iter_list_int> oc_bi_lst_type;
- back_insert_iter_list_int it_pre_lst = std::back_inserter(pre_lst);
- oc_bi_lst_type oc_pre_lst = oc_bi_lst_type(it_pre_lst);
- preorder::copy(c.begin(), oc_pre_lst);
- test_preorder_traversal(pre_lst.begin(), pre_lst.end());
-
- // inorder::copy tests
- std::list<int> in_lst;
- back_insert_iter_list_int it_in_lst = std::back_inserter(in_lst);
- oc_bi_lst_type oc_in_lst = oc_bi_lst_type(it_in_lst);
- inorder::copy(c.begin(), oc_in_lst);
- test_inorder_traversal(in_lst.begin(), in_lst.end());
-
- // postorder::copy tests
- // Using a list iterator
- std::list<int> lst(11);
- typedef output_cursor_iterator_wrapper<std::list<int>::iterator> oc_lst_type;
- std::list<int>::iterator li = lst.begin();
- oc_lst_type oc_lst(li);
- postorder::copy(c.begin(), oc_lst);
- test_postorder_traversal(lst.begin(), lst.end());
-
- // Using a list<int> back_inserter
- std::list<int> lst2;
- back_insert_iter_list_int bi_lst = std::back_inserter(lst2);
- oc_bi_lst_type oc_bi_lst = oc_bi_lst_type(bi_lst);
- postorder::copy(c.begin(), oc_bi_lst);
- test_postorder_traversal(lst2.begin(), lst2.end());
-
return 0;
}
