[Boost-commit] svn:boost r51702 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/test

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();