|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-08-07 08:26:38
Author: bernhard.reiter
Date: 2008-08-07 08:26:37 EDT (Thu, 07 Aug 2008)
New Revision: 48016
URL: http://svn.boost.org/trac/boost/changeset/48016
Log:
Fix preorder cursor algorithms for use with forest_tree.
inorder and postorder remain to be fixed!
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 3 +
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp | 35 ++++++++++++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/cursor_algorithm_test.cpp | 5 +-
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp | 70 +++++++++++++--------------------------
4 files changed, 54 insertions(+), 59 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-08-07 08:26:37 EDT (Thu, 07 Aug 2008)
@@ -15,6 +15,9 @@
General:
+* Remove the word "recursive" from *order subtree algorithms context, as we might
+ implement these using iterative versions. Rename *_recursive algorithms to
+ *_with_references or so; and use something like #ifdef BOOST_RECURSIVE_ORDER_ALGORITHMS
* Check if Cursor(balanced_tree_iterator) rellay has no is_root member()!
* Revisit binary_tree (inorder::)iterator functions
* Possibly sort out some more concepts, like trees with "downwards" or "upwards" insertion
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp 2008-08-07 08:26:37 EDT (Thu, 07 Aug 2008)
@@ -156,11 +156,15 @@
{
Cursor t = s.end();
s.to_begin();
- f(*s);
- do
+ do {
+ f(*s);
if (!s.empty())
for_each_recursive(s, f);
- while (s++ != t);
+ ++s;
+ } while (s != t);
+
+ if (!s.empty())
+ for_each_recursive(s, f);
}
/**
@@ -178,11 +182,15 @@
{
Cursor t = s.end();
s.to_begin();
- f(*s);
- do
+ do {
+ f(*s);
if (!s.empty())
for_each_recursive(s, f);
- while (s++ != t);
+ ++s;
+ } while (s != t);
+
+ if (!s.empty())
+ for_each_recursive(s, f);
return f;
}
@@ -197,8 +205,11 @@
OutCursor copy (InCursor s, OutCursor t)
{
InCursor r = s.end();
- *t.to_begin() = *s.to_begin();
+ s.to_begin();
+ t.to_begin();
+
do {
+ *t = *s;
if (!s.empty())
copy(s, t);
++t;
@@ -228,13 +239,19 @@
OutCursor transform (InCursor s, OutCursor t, Op op)
{
InCursor r = s.end();
- *t.to_begin() = op(*s.to_begin());
+ s.to_begin();
+ t.to_begin();
do {
+ *t = op(*s);
if (!s.empty())
transform(s, t, op);
+ ++s;
++t;
- } while (s++ != r);
+ } while (s != r);
+ if (!s.empty())
+ transform(s, t, op);
+
return t;
}
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-08-07 08:26:37 EDT (Thu, 07 Aug 2008)
@@ -26,15 +26,14 @@
#define ORDER preorder
#include "subtree_algorithms_checks.hpp"
-
#undef ORDER
+
#define ORDER inorder
#include "subtree_algorithms_checks.hpp"
-
#undef ORDER
+
#define ORDER postorder
#include "subtree_algorithms_checks.hpp"
-
#undef ORDER
int test_main(int, char* [])
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp 2008-08-07 08:26:37 EDT (Thu, 07 Aug 2008)
@@ -7,12 +7,18 @@
#include <boost/tree/forest_tree.hpp>
#include <boost/tree/algorithm.hpp>
-#include <boost/test/minimal.hpp>
+#include <boost/lambda/bind.hpp>
#include <list>
+#include <boost/test/minimal.hpp>
+
#include "test_tree_traversal_data.hpp"
+#define ORDER preorder
+#include "subtree_algorithms_checks.hpp"
+#undef ORDER
+
//TODO: Make this a test suite.
void test_forest_tree()
@@ -73,59 +79,29 @@
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);
-// Preliminary checks, delete as soon as issues are resolved
-
-// forest_tree_type::cursor s = ft.root();
-// forest_tree_type::cursor r = s.end();
-// *t.to_begin() = *s.to_begin();
-// BOOST_CHECK(!s.empty());
-// if (!s.empty()) {
-// r = s.end();
-// *t.to_begin() = *s.to_begin();
-// }
-//
-// BOOST_CHECK(!s.empty());
-// if (!s.empty()) {
-// r = s.end();
-// *t.to_begin() = *s.to_begin();
-// }
-//
-// BOOST_CHECK(s.empty());
-// ++t;
-//
-// BOOST_CHECK(s != r);
-// BOOST_CHECK(s++ != r);
-// BOOST_CHECK(s == r);
-//
-// BOOST_CHECK(s.empty());
-// ++t;
-
- //BOOST_CHECK(s++ == r);
-
-// do {
-// if (!s.empty())
-// *t = *s;
-// //copy(s, t);
-// ++t;
-// } while (s++ != r);
-
+ boost::tree::preorder::for_each(
+ ft.root(),
+ boost::lambda::bind(&std::list<int>::push_back, &test_list, boost::lambda::_1)
+ );
+ test::preorder::traversal(test_list.begin(), test_list.end());
+ BOOST_CHECK(test_list.size() == 11);
+ test_list.clear();
boost::tree::preorder::copy(ft.root(), oc_test_list);
- //test::preorder::traversal(test_list.begin(), test_list.end());
+ test::preorder::traversal(test_list.begin(), test_list.end());
+ BOOST_CHECK(test_list.size() == 11);
+ test_list.clear();
- BOOST_CHECK(test_list.size() == 6);
+ boost::tree::preorder::transform(ft.root(), oc_test_list, std::bind2nd(std::plus<int>(),0));
+ test::preorder::traversal(test_list.begin(), test_list.end());
+ BOOST_CHECK(test_list.size() == 11);
+ test_list.clear();
- std::list<int>::const_iterator lci = test_list.begin();
- BOOST_CHECK(*lci == 8);
- BOOST_CHECK(*++lci == 3);
- BOOST_CHECK(*++lci == 1);
-// BOOST_CHECK(*++lci != 4); // wrong!
-// BOOST_CHECK(*++lci != 13 ); // wrong!
-// BOOST_CHECK(*++lci != 11); // wrong!
+ //test::preorder::algorithms(ft.root(), ft.root()); // FIXME: Fix algorithms for use in here.
- test_list.clear();
//boost::tree::postorder::copy(ft.root(), oc_test_list);
//test::inorder::traversal(test_list.begin(), test_list.end());
+ //BOOST_CHECK(test_list.size() == 11);
}
int test_main(int, char* [])
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk