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

Subject: [Boost-commit] svn:boost r57241 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-10-29 19:54:42

Author: bernhard.reiter
Date: 2009-10-29 19:54:41 EDT (Thu, 29 Oct 2009)
New Revision: 57241
URL: http://svn.boost.org/trac/boost/changeset/57241

Log:
Towards the new to_last (and successor/predecessor) design.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp  |    10 ++-                                     
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp           |    98 ++++++++++++++++++++++++++++++++------- 
   sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp         |    20 ++++----                                
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp          |    25 +++++----                               
   sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp         |    15 ++++--                                  
   sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp           |     7 ++                                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |     9 ++                                      
   7 files changed, 133 insertions(+), 51 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/iterative_algorithms.hpp	2009-10-29 19:54:41 EDT (Thu, 29 Oct 2009)
@@ -53,8 +53,12 @@
     root_tracking_cursor<Cursor> s(is);
     root_tracking_cursor<Cursor> s2(is);
     to_first(Order(), s);
-    to_last(Order(), s2);
-    return detail::for_each(Order(), s, s2, f, ascending_vertical_traversal_tag());
+//    to_last(Order(), s2);
+//    return detail::for_each(Order(), s, s2, f, ascending_vertical_traversal_tag());
+    do {
+        f(*s);
+    } while (successor(Order(), s));
+    return f;
 }
 
 template <class Order, class InCursor, class OutCursor, class Op>
@@ -86,4 +90,4 @@
 } // namespace tree
 } // namespace boost
 
-#endif //BOOST_TREE_DETAIL_ITERATIVE_ALGORITHMS_HPP
\ No newline at end of file
+#endif //BOOST_TREE_DETAIL_ITERATIVE_ALGORITHMS_HPP

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-10-29 19:54:41 EDT (Thu, 29 Oct 2009)
@@ -43,23 +43,25 @@
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<MultiwayCursor>))
     ((RootTrackingCursor<MultiwayCursor>)),
-    (void)) // return type
+    (bool)) // return type
 successor(inorder, MultiwayCursor& c)
 {
     if (!c.to_end().is_leaf()) {
         to_first(inorder(),c);
-        return;
+        return true;
     }
 
-    MultiwayCursor d = c;
+    //MultiwayCursor d = c;
     while (index(c) && !c.is_root())
         c.to_parent();
 
-    if (!c.is_root())
+    if (!c.is_root()) {
         c.to_parent();
+        return true;
+    }
     else // Move past the last inorder element
-        c = d; //to_last(inorder(), c);
-    return;
+        return false; //c = d; //to_last(inorder(), c);
+    return true;
 }
 
 /**
@@ -71,22 +73,23 @@
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<MultiwayCursor>))
     ((RootTrackingCursor<MultiwayCursor>)),
-    (void)) // return type
+    (bool)) // return type
 predecessor(inorder, MultiwayCursor& c)
 {
-    if (!c.is_leaf()) {
-        if (!c.to_begin().is_leaf()) {
-            to_rightmost(c);
-            c.to_parent();
-            return;
-        }
-    }
+	if (!c.to_begin().is_leaf()) {
+		to_last(inorder(), c);
+		return true;
+	}
 
     while (!index(c) && !c.is_root())
         c.to_parent();
-    if (!c.is_root())
+
+    if (!c.is_root()) {
         c.to_parent();
-    return;
+        return true;
+    }
+    else // Move past the last inorder element
+        return false; //c = d; //to_last(inorder(), c);
 }
 
 /**
@@ -128,17 +131,76 @@
 }
 
 /**
+ * @brief   Last element of a subtree in inorder traversal
+ * @param c Subtree root cursor that will be set to the last inorder 
+ *          position in the subtree.
+ */
+template <class Cursor>
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+to_last(inorder, Cursor& c)
+{
+    return to_last(inorder(), c
+                  , typename cursor_vertical_traversal<Cursor>::type());
+}
+
+template <class Cursor>
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+to_last(inorder, Cursor& c, descending_vertical_traversal_tag)
+{
+    Cursor d = c;
+    while (!d.is_leaf()) {
+        c = d;
+        d.to_end();
+    }
+}
+
+template <class Cursor>
+BOOST_CONCEPT_REQUIRES(
+    ((AscendingCursor<Cursor>)),
+    (void)) // return type
+to_last(inorder, Cursor& c, ascending_vertical_traversal_tag)
+{
+    to_rightmost(c);
+    c.to_parent();
+}
+
+/**
  * @brief   One position past the last element of a subtree in inorder 
  *          traversal
- * @param c Subtree root cursor that will be set to the last inorder 
+ * @param c Subtree root cursor that will be set past the last inorder 
  *          position in the subtree.
  */
 template <class Cursor>
-void to_last(inorder, Cursor& c)
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+to_past(inorder, Cursor& c)
 {
     to_rightmost(c);
 }
 
+template <class Cursor>
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+last_to_past(inorder, Cursor& c)
+{
+    c.to_end();
+}
+
+template <class Cursor>
+BOOST_CONCEPT_REQUIRES(
+    ((AscendingCursor<Cursor>)),
+    (void)) // return type
+past_to_last(inorder, Cursor& c)
+{
+    c.to_parent();
+}
+
 /*\@}*/
 
 /// Search

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp	2009-10-29 19:54:41 EDT (Thu, 29 Oct 2009)
@@ -41,15 +41,15 @@
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<Cursor>))
     ((RootTrackingCursor<Cursor>)),
-    (void)) // return type
+    (bool)) // return type
 successor(postorder, Cursor& c)
 {
     if (c.is_root())
-        return;
+        return false;
 
     if (index(c)) { // Right child? Return parent.
         c.to_parent();
-        return;
+        return true;
     }
         
     // Left child.
@@ -60,7 +60,7 @@
             ++c;
     }
     c.to_parent();
-    return;
+    return true;
 }
 
 /**
@@ -74,23 +74,23 @@
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<Cursor>))
     ((RootTrackingCursor<Cursor>)),
-    (void)) // return type
+    (bool)) // return type
 predecessor(postorder, Cursor& c)
 {
     if (!c.to_end().is_leaf()) // Right
-        return;
+        return true;
     if (!(--c).is_leaf()) // Left
-        return;
+        return true;
     
     // 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()) {
         c.to_parent();
-        if (index(c))
+        if (!c.is_root() && index(c))
             if (!(--c).is_leaf())
-                return;
+                return true;
     }
-    return;
+    return false;
 }
 
 /**

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp	2009-10-29 19:54:41 EDT (Thu, 29 Oct 2009)
@@ -41,16 +41,16 @@
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<Cursor>))
     ((RootTrackingCursor<Cursor>)),
-    (void)) // return type
+    (bool)) // return type
 successor(preorder, Cursor& c)
 {
     // If we have a left child, go there.
     if (!c.to_begin().is_leaf())
-        return;
+        return true;
     
     // No left child. So if we have a right child, go there.
     if (!(++c).is_leaf())
-        return;
+        return true;
     
     // (Here's where we'd need to check if this is the end().)
     
@@ -61,11 +61,11 @@
         c.to_parent();
         if (!c.is_root() && !index(c))
             if (!(++c).is_leaf())
-                return;
+                return true;
     }
     
-    to_last(preorder(), c);
-    return;
+    //to_last(preorder(), c);
+    return false;
 }
 
 /**
@@ -120,15 +120,15 @@
 BOOST_CONCEPT_REQUIRES(
     ((DescendingCursor<Cursor>))
     ((RootTrackingCursor<Cursor>)),
-    (void)) // return type
+    (bool)) // return type
 predecessor(preorder, Cursor& c)
 {
     if (c.is_root())
-        return;
+        return false;
 
     if (!index(c)) { // Left child? Return parent.
         c.to_parent();
-        return;
+        return true;
     }
         
     // Right child.
@@ -139,7 +139,7 @@
             --c;
     }
     c.to_parent();
-    return;
+    return true;
 }
 
 /**
@@ -166,8 +166,9 @@
     while (!c.is_leaf())
         if (c.to_end().is_leaf())
             --c;
-    if (!index(c))
-        ++c;
+    //if (!index(c))
+    //    ++c;
+    c.to_parent();
 }
 
 /*\@}*/

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-10-29 19:54:41 EDT (Thu, 29 Oct 2009)
@@ -28,10 +28,10 @@
     BOOST_CHECK(c == frbt1.root().end().end().end());
 }
 
-typedef boost::mpl::list<boost::tree::preorder
-                        ,boost::tree::inorder> preandinorders;
+//typedef boost::mpl::list<boost::tree::preorder
+//                        ,boost::tree::inorder> preandinorders;
 
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_predecessor, Order, preandinorders )
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_predecessor, Order, orders )
 {
     fake_root_tracking_binary_tree<int> frbt1(fbt1);
     fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
@@ -46,13 +46,18 @@
     typename container_type::const_reverse_iterator ci = order_index.rbegin();
     typename container_type::const_reverse_iterator cie = order_index.rend();
 
+    //BOOST_CHECK_EQUAL(*c, ci->val);
+    --cie;
     for (; ci!=cie; ++ci) {
-        boost::tree::predecessor(Order(), c);
         BOOST_CHECK_EQUAL(*c, ci->val);
+        BOOST_CHECK_EQUAL(boost::tree::predecessor(Order(), c), true);
     }
+
     fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
     fake_to_first(Order(), d);
     BOOST_CHECK(c == d);
+    
+    BOOST_CHECK_EQUAL(boost::tree::predecessor(Order(), c), false);
 }
 
-BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
+BOOST_AUTO_TEST_SUITE_END()

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-10-29 19:54:41 EDT (Thu, 29 Oct 2009)
@@ -41,14 +41,19 @@
     typename container_type::const_iterator ci = order_index.begin();
     typename container_type::const_iterator cie = order_index.end();
 
+    --cie;
     for (; ci!=cie; ++ci) {
         BOOST_CHECK_EQUAL(*c, ci->val);
-        boost::tree::successor(Order(), c);
+        BOOST_CHECK_EQUAL(boost::tree::successor(Order(), c), true);
     }
 
+    BOOST_CHECK_EQUAL(*c, ci->val);
+
     fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
     fake_to_last(Order(), d);
     BOOST_CHECK(c == d);
+    
+    BOOST_CHECK_EQUAL(boost::tree::successor(Order(), c), false);
 }
 
 BOOST_AUTO_TEST_CASE( test_successor_ascending )

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	2009-10-29 19:54:41 EDT (Thu, 29 Oct 2009)
@@ -90,18 +90,23 @@
 template <class Cursor>
 void fake_to_last(boost::tree::preorder, Cursor& c)
 {
-    c.to_end().to_end().to_begin().to_begin().to_end().to_end();
+    c.to_end().to_end().to_begin().to_begin().to_end();
 }
 
 template <class Cursor>
 void fake_to_last(boost::tree::inorder, Cursor& c)
 {
-    c.to_end().to_end().to_end();
+    c.to_end().to_end();
 }
 
 template <class Cursor>
 void fake_to_last(boost::tree::postorder, Cursor& c)
 {}
 
+template <class Cursor>
+void fake_to_past(boost::tree::inorder, Cursor& c)
+{
+    c.to_end().to_end().to_end();
+}
 
 #endif // LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_DATA_HPP