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

Subject: [Boost-commit] svn:boost r57084 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-10-22 20:25:17

Author: bernhard.reiter
Date: 2009-10-22 20:25:16 EDT (Thu, 22 Oct 2009)
New Revision: 57084
URL: http://svn.boost.org/trac/boost/changeset/57084

Log:
More predecessor (and to_last) fixes (also to the tests!). Should do for pre- and inorder now.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp           |     9 +++++----                               
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp          |    10 +++++++++-                              
   sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp         |    27 +++++++++++++++------------             
   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 +-                                      
   5 files changed, 30 insertions(+), 19 deletions(-)

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 20:25:16 EDT (Thu, 22 Oct 2009)
@@ -51,13 +51,14 @@
         return;
     }
 
+    MultiwayCursor d = c;
     while (index(c) && !c.is_root())
         c.to_parent();
 
-    if (c.is_root())    // Move past the last inorder element
-        to_last(inorder(), c);
-    else
+    if (!c.is_root())
         c.to_parent();
+    else // Move past the last inorder element
+        c = d; //to_last(inorder(), c);
     return;
 }
 
@@ -76,7 +77,7 @@
     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)
+            c.to_parent();
             return;
         }
     }

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 20:25:16 EDT (Thu, 22 Oct 2009)
@@ -63,6 +63,8 @@
             if (!(++c).is_leaf())
                 return;
     }
+    
+    to_last(preorder(), c);
     return;
 }
 
@@ -160,7 +162,13 @@
  */
 template <class Cursor>
 void to_last(preorder, Cursor& c)
-{}
+{
+    while (!c.is_leaf())
+        if (c.to_end().is_leaf())
+            --c;
+    if (!index(c))
+        ++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 20:25:16 EDT (Thu, 22 Oct 2009)
@@ -19,16 +19,19 @@
 
 BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
 
-//BOOST_AUTO_TEST_CASE( test_rightmost )
-//{
-//    fake_root_tracking_binary_tree<int> frbt1(fbt1);
-//    fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
-//    to_rightmost(c);
-//    BOOST_CHECK(c.is_leaf());
-//    BOOST_CHECK(c == frbt1.root().end().end().end());
-//}
+BOOST_AUTO_TEST_CASE( test_rightmost )
+{
+    fake_root_tracking_binary_tree<int> frbt1(fbt1);
+    fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
+    to_rightmost(c);
+    BOOST_CHECK(c.is_leaf());
+    BOOST_CHECK(c == frbt1.root().end().end().end());
+}
+
+typedef boost::mpl::list<boost::tree::preorder
+                        ,boost::tree::inorder> preandinorders;
 
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_predecessor, Order, orders )
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_predecessor, Order, preandinorders )
 {
     fake_root_tracking_binary_tree<int> frbt1(fbt1);
     fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
@@ -40,10 +43,10 @@
     typedef typename test_data_set::index<Order>::type container_type;
     const container_type& order_index = mpo.get<Order>();
 
-    typename container_type::const_iterator cib = order_index.begin();
-    typename container_type::const_iterator ci = order_index.end();
+    typename container_type::const_reverse_iterator ci = order_index.rbegin();
+    typename container_type::const_reverse_iterator cie = order_index.rend();
 
-    for (--ci; ci!=cib; --ci) {
+    for (; ci!=cie; ++ci) {
         boost::tree::predecessor(Order(), c);
         BOOST_CHECK_EQUAL(*c, ci->val);
     }

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 20:25:16 EDT (Thu, 22 Oct 2009)
@@ -49,7 +49,6 @@
     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 20:25:16 EDT (Thu, 22 Oct 2009)
@@ -90,7 +90,7 @@
 template <class Cursor>
 void fake_to_last(boost::tree::preorder, Cursor& c)
 {
-    c.to_end().to_end().to_begin().to_begin().to_end();
+    c.to_end().to_end().to_begin().to_begin().to_end().to_end();
 }
 
 template <class Cursor>