From: ockham_at_[hidden]
Date: 2008-06-14 14:37:12
Author: bernhard.reiter
Date: 2008-06-14 14:37:11 EDT (Sat, 14 Jun 2008)
New Revision: 46395
URL: http://svn.boost.org/trac/boost/changeset/46395
Log:
Traversal test fixes.
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/inorder.hpp | 6 ++-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/postorder.hpp | 2
sandbox/SOC/2006/tree/trunk/boost/tree/detail/algorithm/cursor/preorder.hpp | 32 +++++++----------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp | 3 +
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp | 2 +
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp | 2 +
sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp | 2 +
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 10 ++--
sandbox/SOC/2006/tree/trunk/libs/tree/test/traverse_binary_tree_test.cpp | 74 ++++++++++++++++++++++-----------------
9 files changed, 74 insertions(+), 59 deletions(-)
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-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -67,9 +67,11 @@
--c;
return;
}
- while (!c.parity())
+
+ while (!c.parity() && !c.is_root())
c.to_parent();
- --c;
+ if (!c.is_root())
+ --c;
return;
}
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-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -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 (!c.is_root()) { // revisit
+ while (!c.is_root()) {
c.to_parent();
if (c.parity())
if (!(--c).empty()) {
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-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -48,14 +48,9 @@
// No children at all.
// As we've already visited all the ancestors, we'll move upwards until
// we find an ancestor that has a right child.
- while (true) { // Doesn't work with subtrees!
- if (c.is_root())
- return;
-
+ while (!c.is_root()) { // Doesn't work with subtrees!
c.to_parent();
- if (!c.parity()) {
- if (c.is_root())
- return;
+ if (!c.is_root() && !c.parity()) {
if (!(++c).empty()) {
c.to_begin();
return;
@@ -84,27 +79,26 @@
template <class Cursor>
inline void back(Cursor& c)
{
- if (!c.is_root()) { // Not root
+ if (!c.is_root()) {
c.to_parent();
- // If this is a left child, just move to its parent.
- if (!c.parity()) {
- c.to_parent();
- c.to_begin();
+ // If a left child was given, just move to its parent.
+ if (!c.parity())
return;
- }
// So this is a right child.
--c;
}
// Same for root (=end) and right children:
- if (!c.empty())
- while (!c.empty())
- if (!c.end().empty())
- c.to_end();
- else
- c.to_begin();
+ while (!c.empty())
+ if (!c.end().empty())
+ c.to_end();
+ else
+ c.to_begin();
+
+ if (c.parity())
+ --c;
return;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/_order.hpp 2008-06-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -22,6 +22,7 @@
*
* Only works with ascending cursors.
*/
+
template <class Cursor, class RootTracker = typename Cursor::root_tracker>
class iterator
: public boost::iterator_adaptor<iterator<Cursor>
@@ -59,10 +60,12 @@
void increment()
{
forward(this->base_reference());
+ //BOOST_ASSERT(!this->base_reference().parity() || this->base_reference().is_root());
}
void decrement()
{
back(this->base_reference());
+ //BOOST_ASSERT(!this->base_reference().parity() || this->base_reference().is_root());
}
};
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/inorder.hpp 2008-06-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -18,6 +18,8 @@
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
+//#include <boost/test/minimal.hpp>
+
namespace boost {
namespace tree {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/postorder.hpp 2008-06-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -18,6 +18,8 @@
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
+//#include <boost/test/minimal.hpp>
+
namespace boost {
namespace tree {
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterator/preorder.hpp 2008-06-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -19,6 +19,8 @@
#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>
+//#include <boost/test/minimal.hpp>
+
namespace boost {
namespace tree {
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-06-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -36,16 +36,16 @@
{
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().begin().begin() == 1); //Leaf
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().begin().end().begin().begin() == 4); //Leaf
+ BOOST_CHECK(*ret.root().begin().end().end().begin() == 7); //Leaf
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);
+ BOOST_CHECK(*ret.root().end().end().begin().begin().begin() == 11);
+ BOOST_CHECK(*ret.root().end().end().begin().begin().end().begin() == 12); //Leaf
}
namespace test {
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-14 14:37:11 EDT (Sat, 14 Jun 2008)
@@ -48,8 +48,8 @@
void underefed_for_each_recursive(Cursor s, Op& f)
{
Cursor t = s.end();
- s.to_begin();
- f(s);
+ 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);
@@ -60,8 +60,8 @@
Op underefed_for_each(Cursor s, Op f)
{
Cursor t = s.end();
- s.to_begin();
- f(s);
+ 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);
@@ -70,20 +70,16 @@
return f;
}
-void comparisons(binary_tree<int>::const_cursor 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);
-// }
+template <class Cursor>
+void comparisons(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);
+ return;
+}
+
+void comparisons_using_ac(binary_tree<int>::cursor c) {
+ comparisons(make_ascending_cursor(c));
return;
}
@@ -92,50 +88,64 @@
* 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.
+ * Do all that also using iterators wrapped around "explicit stack"-based cursors
*/
void compare_cursor_to_iterator_traversal() {
+ using boost::tree::make_ascending_cursor;
+
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());
+ comparisons(make_ascending_cursor(test_tree2.root()));
c = test_tree2.insert(c, 3);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
test_tree2.insert(c, 1);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
c = test_tree2.insert(++c, 6);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
test_tree2.insert(c, 4);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
test_tree2.insert(++c, 7);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
c = test_tree2.insert(test_tree2.root().end(), 10);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
c = test_tree2.insert(test_tree2.root().end().end(), 14);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
c = test_tree2.insert(c, 13);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
c = test_tree2.insert(c, 11);
comparisons(test_tree2.root());
-
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
c = test_tree2.insert(++c, 12);
comparisons(test_tree2.root());
-// underefed_for_each(test_tree2.root(), comparisons);
+ comparisons(make_ascending_cursor(test_tree2.root()));
+
+ typedef ascending_cursor<binary_tree<int>::cursor> ac;
- comparisons(test_tree2.root().begin());
- comparisons(test_tree2.root().begin().begin());
+ // FIXME: This requires subtree cursors to know their root.
+ //underefed_for_each(test_tree2.root(), comparisons<binary_tree<int>::cursor>);
- comparisons(test_tree2.root().end());
- comparisons(test_tree2.root().end().end());
+ underefed_for_each(test_tree2.root(), comparisons_using_ac);
}
int test_main(int, char* [])