|
|
Boost-Commit : |
From: ockham_at_[hidden]
Date: 2008-06-12 09:52:19
Author: bernhard.reiter
Date: 2008-06-12 09:52:18 EDT (Thu, 12 Jun 2008)
New Revision: 46353
URL: http://svn.boost.org/trac/boost/changeset/46353
Log:
Further fixes to recursive *order algorithms.
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 13 ++++++++++++-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp | 18 +++++++++---------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp | 13 +++++++------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp | 5 ++---
sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp | 39 ++++++---------------------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp | 39 ++++++++++++++++++++++++++++++++-------
6 files changed, 68 insertions(+), 59 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2008-06-12 09:52:18 EDT (Thu, 12 Jun 2008)
@@ -14,12 +14,22 @@
[section TODO]
General:
+* Re-organize traversal tests:
+ * Verify recursive algorithms to work
+ * 1. with a tree filled with given data
+ * 2. with an empty tree
+ * Same for iterators
+ * Start with an empty tree, fill it with data. At each step, check if
+ cursor and iterator algorithms yield the same result.
+ (Or, alternatively, if neither is to be trusted: compare to subsets of
+ the complete test data.)
+ * With the tree complete, do the same recursively for all its subtrees.
* Also test copy with two trees (not just one tree and a container/output iterator)
* Rename parity() (which looks somewhat binary-related) to index (more general for forest
trees etc)?
* _Possibly_ move detail/algorithm/cursor/ to detail/cursor/algorithm/ or even just
detail/cursor/ (same for iterator).
-* Make *order iterators work with empty subtrees.
+* Make *order iterators work with empty subtrees; same for cursor algorithms.
* Get rid of checks for/assignments to root in pre/post/inorder algorithms,
as they are otherwise limited to "whole" trees and cannot be applied to subtrees.
In order to work for subtrees, it's probable that we need at least an int to store
@@ -63,6 +73,7 @@
(and output_cursor_iterator_wrapper?) proposal.
* Add a revision log:
* Add to_parent() (replaces operator!()), to_begin() and to_end() descending cursor members.
+ * Remove shoot()
* Add (subtree) cursor algorithms.
* Probably split up cursor categories into: cursor (value access) category, vertical traversal
and horizontal traversal (along the lines of the new iterator concepts).
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp 2008-06-12 09:52:18 EDT (Thu, 12 Jun 2008)
@@ -37,7 +37,7 @@
return;
}
- while (c.parity()) // Doesn't work with subtrees whose root's parity != 0
+ while (c.parity() && !c.is_root())
c.to_parent();
return;
}
@@ -122,8 +122,8 @@
template <class MultiwayCursor, class Op>
void for_each_recursive(MultiwayCursor s, Op& f)
{
- MultiwayCursor t = s;
- t.to_end();
+ MultiwayCursor t = s.end();
+
for (s.to_begin(); s!=t; ++s) {
if (!s.empty())
for_each_recursive(s, f);
@@ -147,8 +147,8 @@
template <class MultiwayCursor, class Op>
Op for_each(MultiwayCursor s, Op f)
{
- MultiwayCursor t = s;
- t.to_end();
+ MultiwayCursor t = s.end();
+
for (s.to_begin(); s!=t; ++s) {
if (!s.empty())
for_each_recursive(s, f);
@@ -168,8 +168,8 @@
template <class InCursor, class OutCursor>
OutCursor copy (InCursor s, OutCursor t)
{
- InCursor r = s;
- r.to_end();
+ InCursor r = s.end();
+
s.to_begin();
t.to_begin();
@@ -199,8 +199,8 @@
template <class InCursor, class OutCursor, class Op>
OutCursor transform (InCursor s, OutCursor t, Op op)
{
- InCursor r = s;
- r.to_end();
+ InCursor r = s.end();
+
s.to_begin();
t.to_begin();
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp 2008-06-12 09:52:18 EDT (Thu, 12 Jun 2008)
@@ -33,14 +33,14 @@
{
c.to_parent();
+ if (c.is_root())
+ return;
+
if (c.parity()) { // Right child? Return parent.
--c;
return;
}
-
- if (c.is_root()) // Root?
- return;
-
+
// Left child.
++c;
while (!c.empty()) {
@@ -88,7 +88,7 @@
// Move up in the hierarchy until we find a descendant that has a right
// child (which is what we'll return) or we land at root.
- while (true) { // revisit
+ while (!c.is_root()) { // revisit
c.to_parent();
if (c.parity())
if (!(--c).empty()) {
@@ -182,6 +182,7 @@
for_each_recursive(s, f);
while (s++ != t.end());
f(*t.to_begin());
+
return f;
}
//]
@@ -228,7 +229,7 @@
t.to_begin();
do {
if (!s.empty())
- transform(s, t, op);
+ copy(s, t);
++t;
} while (s++ != r.end());
*t = op(*r.to_begin());
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-06-12 09:52:18 EDT (Thu, 12 Jun 2008)
@@ -155,8 +155,7 @@
template <class Cursor, class Op>
void for_each_recursive(Cursor s, Op& f)
{
- Cursor t = s;
- t.to_end();
+ Cursor t = s.end();
s.to_begin();
f(*s);
do
@@ -185,7 +184,7 @@
if (!s.empty())
for_each_recursive(s, f);
while (s++ != t);
-
+
return f;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/subtree_algorithms_checks.hpp 2008-06-12 09:52:18 EDT (Thu, 12 Jun 2008)
@@ -7,8 +7,6 @@
#include <boost/tree/algorithm.hpp>
#include <boost/tree/binary_tree.hpp>
-#include <boost/tree/ascending_cursor.hpp>
-
#include <boost/lambda/bind.hpp>
#include <list>
@@ -36,8 +34,8 @@
template <class Cursor, class OutCursor, class Container>
void test_copy(Cursor c, OutCursor& o, Container& cont)
{
- boost::tree::preorder::copy(c, o);
- test::preorder::traversal(cont.begin(), cont.end());
+ boost::tree::ORDER::copy(c, o);
+ test::ORDER::traversal(cont.begin(), cont.end());
}
template <class Cursor, class OutCursor, class Container>
@@ -46,10 +44,8 @@
// First copy test_tree to test_tree2, by adding 1 to each element,
// then copy test_tree2 to test_list, by subtracting 1 - so
// test_list should hold test_tree's original elements in ORDER.
- boost::tree::ORDER::transform(c, d,
- std::bind2nd(std::plus<int>(),1));
- boost::tree::ORDER::transform(d, o,
- std::bind2nd(std::minus<int>(),1));
+ boost::tree::ORDER::transform(c, d, std::bind2nd(std::plus<int>(),1));
+ boost::tree::ORDER::transform(d, o, std::bind2nd(std::minus<int>(),1));
test::ORDER::traversal(cont.begin(), cont.end());
}
@@ -71,12 +67,8 @@
test_transform(c, d, oc_test_list, test_list);
}
-void compare_cursor_to_iterator_traversal(boost::tree::binary_tree<int>::const_cursor cur) {
-
- using boost::tree::ascending_cursor;
-
- typedef boost::tree::binary_tree<int>::const_cursor cursor;
-
+template <class Cursor>
+void compare_cursor_to_iterator_traversal(Cursor cur) {
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;
@@ -106,25 +98,6 @@
boost::tree::ORDER::rend(cur)) ==
std::distance(test_list.rbegin(), test_list.rend()));
- //Now same for iterators wrapped around "explicit stack"-based cursors
- BOOST_CHECK(std::equal( boost::tree::ORDER::begin(make_ascending_cursor(cur)),
- boost::tree::ORDER::end(make_ascending_cursor(cur)),
- test_list.begin()
- ));
-
- BOOST_CHECK(std::distance(boost::tree::ORDER::begin(make_ascending_cursor(cur)),
- boost::tree::ORDER::end(make_ascending_cursor(cur))) ==
- std::distance(test_list.begin(), test_list.end()));
-
- BOOST_CHECK(std::equal( boost::tree::ORDER::rbegin(make_ascending_cursor(cur)),
- boost::tree::ORDER::rend(make_ascending_cursor(cur)),
- test_list.rbegin()
- ));
-
- BOOST_CHECK(std::distance(boost::tree::ORDER::rbegin(make_ascending_cursor(cur)),
- boost::tree::ORDER::rend(make_ascending_cursor(cur))) ==
- std::distance(test_list.rbegin(), test_list.rend()));
-
}
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 2008-06-12 09:52:18 EDT (Thu, 12 Jun 2008)
@@ -16,6 +16,8 @@
#include <boost/tree/iterator.hpp>
#include <boost/tree/algorithm.hpp>
+#include <boost/tree/ascending_cursor.hpp>
+
#include <boost/test/minimal.hpp>
#include <list>
@@ -45,8 +47,7 @@
template <class Cursor, class Op>
void underefed_for_each_recursive(Cursor s, Op& f)
{
- Cursor t = s;
- t.to_end();
+ Cursor t = s.end();
s.to_begin();
f(s);
do
@@ -70,9 +71,19 @@
}
void comparisons(binary_tree<int>::const_cursor c) {
- test::preorder::compare_cursor_to_iterator_traversal(c);
- test::inorder::compare_cursor_to_iterator_traversal(c);
- test::postorder::compare_cursor_to_iterator_traversal(c);
+ using boost::tree::ascending_cursor;
+
+ //if (!c.empty()) {
+ test::preorder::compare_cursor_to_iterator_traversal(c);
+ test::inorder::compare_cursor_to_iterator_traversal(c);
+ test::postorder::compare_cursor_to_iterator_traversal(c);
+
+ //Now same for iterators wrapped around "explicit stack"-based cursors
+ ascending_cursor<binary_tree<int>::const_cursor> ac(c);
+ test::preorder::compare_cursor_to_iterator_traversal(ac);
+ test::inorder::compare_cursor_to_iterator_traversal(ac);
+ test::postorder::compare_cursor_to_iterator_traversal(ac);
+ //}
return;
}
@@ -84,6 +95,7 @@
*/
void compare_cursor_to_iterator_traversal() {
binary_tree<int> test_tree2;
+ //comparisons(test_tree2.root());
binary_tree<int>::cursor c = test_tree2.insert(test_tree2.root(), 8);
comparisons(test_tree2.root());
@@ -117,9 +129,13 @@
c = test_tree2.insert(++c, 12);
comparisons(test_tree2.root());
- //underefed_for_each(test_tree2.root(), comparisons);
+// underefed_for_each(test_tree2.root(), comparisons);
- //comparisons(test_tree2.root().begin());
+// comparisons(test_tree2.root().begin());
+// comparisons(test_tree2.root().begin().begin());
+//
+// comparisons(test_tree2.root().end());
+// comparisons(test_tree2.root().end().end());
}
int test_main(int, char* [])
@@ -127,6 +143,15 @@
typedef boost::tree::binary_tree<int>::cursor cursor;
binary_tree<int> test_tree;
+// std::list<int> test_list;
+//
+// // TODO: Put this into a better testing context.
+// boost::tree::preorder::for_each(
+// test_tree.root(),
+// boost::lambda::bind(&std::list<int>::push_back, &test_list, boost::lambda::_1)
+// );
+// BOOST_CHECK(test_list.empty());
+
create_test_data_tree(test_tree);
//Preorder
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