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

Subject: [Boost-commit] svn:boost r57081 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-10-22 19:22:32

Author: bernhard.reiter
Date: 2009-10-22 19:22:31 EDT (Thu, 22 Oct 2009)
New Revision: 57081
URL: http://svn.boost.org/trac/boost/changeset/57081

Log:
Fix inorder to_last (and successor and predecessor), which leads to pre- and postorder regressions.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                        |     2 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp           |    42 +++++++++++++++++++++++++++++++++------ 
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp          |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp         |     3 -                                       
   sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp           |     1                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |     2                                         
   6 files changed, 41 insertions(+), 11 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-10-22 19:22:31 EDT (Thu, 22 Oct 2009)
@@ -14,6 +14,8 @@
 [section TODO]
 
 General:
+* iterator<postorder> probably needs to be overloaded and to contain a bool indicating if we're
+  dealing with "end" when we're at the root
 * In most algorithms, calls to index(c) appear after a c.to_parent() operation, so for 
   increased effciency, we need a to_parent_return_index(c) function.
 * Fix binary_tree_test (rotate)

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-22 19:22:31 EDT (Thu, 22 Oct 2009)
@@ -53,7 +53,11 @@
 
     while (index(c) && !c.is_root())
         c.to_parent();
-    c.to_parent();
+
+    if (c.is_root())    // Move past the last inorder element
+        to_last(inorder(), c);
+    else
+        c.to_parent();
     return;
 }
 
@@ -69,12 +73,14 @@
     (void)) // return type
 predecessor(inorder, MultiwayCursor& c)
 {
-    if (!c.to_begin().is_leaf()) {
-        to_rightmost(c);
-        c.to_parent(); //TODO: The latter two lines should probably be to_last(inorder(),c)
-        return;
+    if (!c.is_leaf()) {
+        if (!c.to_begin().is_leaf()) {
+            to_rightmost(c);
+            c.to_parent(); //TODO: The latter two lines should probably be to_last(inorder(),c)
+            return;
+        }
     }
-    
+
     while (!index(c) && !c.is_root())
         c.to_parent();
     if (!c.is_root())
@@ -93,6 +99,16 @@
     (void)) // return type
 to_first(inorder, Cursor& c)
 {
+    return to_first(inorder(), c
+                  , typename cursor_vertical_traversal<Cursor>::type());
+}
+
+template <class Cursor>
+BOOST_CONCEPT_REQUIRES(
+    ((DescendingCursor<Cursor>)),
+    (void)) // return type
+to_first(inorder, Cursor& c, descending_vertical_traversal_tag)
+{
     Cursor d = c;
     while (!d.is_leaf()) {
         c = d;
@@ -100,6 +116,16 @@
     }
 }
 
+template <class Cursor>
+BOOST_CONCEPT_REQUIRES(
+    ((AscendingCursor<Cursor>)),
+    (void)) // return type
+to_first(inorder, Cursor& c, ascending_vertical_traversal_tag)
+{
+    to_leftmost(c);
+    c.to_parent();
+}
+
 /**
  * @brief   One position past the last element of a subtree in inorder 
  *          traversal
@@ -108,7 +134,9 @@
  */
 template <class Cursor>
 void to_last(inorder, Cursor& c)
-{ }
+{
+    to_rightmost(c);
+}
 
 /*\@}*/
 

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-22 19:22:31 EDT (Thu, 22 Oct 2009)
@@ -160,7 +160,7 @@
  */
 template <class Cursor>
 void to_last(preorder, Cursor& c)
-{ }
+{}
 
 /*\@}*/
 

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-22 19:22:31 EDT (Thu, 22 Oct 2009)
@@ -44,9 +44,8 @@
     typename container_type::const_iterator ci = order_index.end();
 
     for (--ci; ci!=cib; --ci) {
-        BOOST_CHECK_EQUAL(*c, ci->val); //Change order of statements!
         boost::tree::predecessor(Order(), c);
-        
+        BOOST_CHECK_EQUAL(*c, ci->val);
     }
     fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
     fake_to_first(Order(), d);

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-22 19:22:31 EDT (Thu, 22 Oct 2009)
@@ -49,6 +49,7 @@
     fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
     fake_to_last(Order(), d);
     BOOST_CHECK(c == d);
+    //BOOST_CHECK_EQUAL(0,1);
 }
 
 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-22 19:22:31 EDT (Thu, 22 Oct 2009)
@@ -96,7 +96,7 @@
 template <class Cursor>
 void fake_to_last(boost::tree::inorder, Cursor& c)
 {
-    c.to_end().to_end();
+    c.to_end().to_end().to_end();
 }
 
 template <class Cursor>