Subject: [Boost-commit] svn:boost r51702 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-03-11 10:46:22
Author: bernhard.reiter
Date: 2009-03-11 10:46:20 EDT (Wed, 11 Mar 2009)
New Revision: 51702
URL: http://svn.boost.org/trac/boost/changeset/51702
Log:
Introduce leftmost() and rightmost() functions
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 4 +---
sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp | 30 ++++++++++++++++++++++++++++++
sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp | 5 +++--
sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp | 7 +++++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp | 7 +++++++
5 files changed, 48 insertions(+), 5 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp 2009-03-11 10:46:20 EDT (Wed, 11 Mar 2009)
@@ -102,9 +102,7 @@
(void)) // return type
to_forest_end(BinaryCursor& c)
{
- c.to_begin();
- while (!c.is_leaf())
- c.to_end();
+ rightmost(c.to_begin());
}
//template <class BinaryCursor>
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp 2009-03-11 10:46:20 EDT (Wed, 11 Mar 2009)
@@ -21,6 +21,36 @@
using namespace boost_concepts;
+/**
+ * @brief The leftmost descendant of the given cursor
+ * @param c Cursor to be set to its leftmost descendant
+ * @ingroup traversal
+ */
+template <class Cursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+ ((DescendingCursor<Cursor>)),
+ (void)) // return type
+leftmost(Cursor& c)
+{
+ while (!c.to_begin().is_leaf());
+}
+
+/**
+ * @brief The rightmost descendant of the given cursor
+ * @param c Cursor to be set to its rightmost descendant
+ * @ingroup traversal
+ */
+template <class Cursor>
+inline
+BOOST_CONCEPT_REQUIRES(
+ ((DescendingCursor<Cursor>)),
+ (void)) // return type
+rightmost(Cursor& c)
+{
+ while (!c.to_end().is_leaf());
+}
+
// These algorithms are actually mostly preorder, as it's most efficient, but I
// think it doesn't make much sense having in- and postorder versions of them.
// The only reason I can think of is that there might be some cases
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp 2009-03-11 10:46:20 EDT (Wed, 11 Mar 2009)
@@ -12,6 +12,7 @@
#ifndef BOOST_TREE_INORDER_ALGORITHMS_HPP
#define BOOST_TREE_INORDER_ALGORITHMS_HPP
+#include <boost/tree/general_algorithms.hpp>
#include <boost/tree/root_tracking_cursor.hpp>
#include <boost/tree/ascending_cursor.hpp>
#include <boost/tree/cursor_concepts.hpp>
@@ -46,7 +47,7 @@
successor(inorder, MultiwayCursor& c)
{
if (!(++c).is_leaf()) {
- while (!c.to_begin().is_leaf());
+ leftmost(c);
return;
}
@@ -68,7 +69,7 @@
predecessor(inorder, MultiwayCursor& c)
{
if (!c.is_leaf()) {
- while (!c.to_end().is_leaf());
+ rightmost(c);
--c;
return;
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp 2009-03-11 10:46:20 EDT (Wed, 11 Mar 2009)
@@ -19,6 +19,13 @@
BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
+BOOST_AUTO_TEST_CASE( test_rightmost )
+{
+ fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
+ rightmost(c);
+ BOOST_CHECK_EQUAL(*c, 14);
+}
+
BOOST_AUTO_TEST_CASE_TEMPLATE( test_predecessor, Order, orders )
{
fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp 2009-03-11 10:46:20 EDT (Wed, 11 Mar 2009)
@@ -17,6 +17,13 @@
BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
+BOOST_AUTO_TEST_CASE( test_leftmost )
+{
+ fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
+ leftmost(c);
+ BOOST_CHECK_EQUAL(*c, 1);
+}
+
BOOST_AUTO_TEST_CASE_TEMPLATE( test_successor, Order, orders )
{
fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();