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

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

Author: bernhard.reiter
Date: 2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
New Revision: 57007
URL: http://svn.boost.org/trac/boost/changeset/57007

Log:
Fix predecessor.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                        |     2 ++                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp           |     6 +++---                                  
   sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp         |    29 +++++++++++------------------           
   sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp          |    40 ++++++++++++++++++++--------------------
   sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp               |     3 +++                                     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp         |    28 ++++++++++++++--------------            
   sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp           |     9 +++++----                               
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |    35 ++++++++++++++++++++++++++++++++++-     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp            |     3 +++                                     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp             |     7 +++++--                                 
   10 files changed, 100 insertions(+), 62 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -14,6 +14,8 @@
 [section TODO]
 
 General:
+* 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)
 * Apply all binary_tree_test cchecks also to fake_binary_tree in order to check if semantics
   are mapped properly.

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-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -69,16 +69,16 @@
     (void)) // return type
 predecessor(inorder, MultiwayCursor& c)
 {
-    if (!c.is_leaf()) {
+    if (!c.to_begin().is_leaf()) {
         to_rightmost(c);
-        --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())
-        --c;
+        c.to_parent();
     return;
 }
 

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-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -31,8 +31,10 @@
 };
 
 /**
- * @brief    Postorder successor
- * @param c    Cursor to be set to its postorder successor
+ * @brief   Postorder successor
+ * @param c Cursor to be set to its postorder successor
+ * 
+ * Note that this is the reverse preorder predecessor. 
  */
 template <class Cursor>
 inline
@@ -62,8 +64,10 @@
 }
 
 /**
- * @brief    Postorder predecessor
- * @param c    Cursor to be set to its postorder predecessor
+ * @brief   Postorder predecessor
+ * @param c Cursor to be set to its postorder predecessor
+ * 
+ * Note that this is the reverse preorder successor. 
  */
 template <class Cursor>
 inline
@@ -73,29 +77,18 @@
     (void)) // return type
 predecessor(postorder, Cursor& c)
 {
-    if (c.is_root()) { // Root?
-        c.to_begin();
-        return;
-    }
-    
-    if (!(++c).is_leaf()) { // Right
-        c.to_begin();
+    if (!c.to_end().is_leaf()) // Right
         return;
-    }
-    if (!(--c).is_leaf()) { // Left
-        c.to_begin();
+    if (!(--c).is_leaf()) // Left
         return;
-    }
     
     // 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_leaf()) {
-                c.to_begin();
+            if (!(--c).is_leaf())
                 return;
-            }
     }
     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-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -33,6 +33,8 @@
 /**
  * @brief   Preorder successor
  * @param c Cursor to be set to its preorder successor
+ * 
+ * Note that this is the reverse postorder predecessor. 
  */
 template <typename Cursor>
 inline
@@ -66,7 +68,7 @@
 
 /**
  * @brief   Preorder successor
- * @param c Cursor to be set to its preorder successor
+ * @param c Cursor to be set to its preorder successor 
  */
 template <typename Cursor>
 inline
@@ -106,8 +108,10 @@
 }
 
 /**
- * @brief    Preorder predecessor
- * @param c    Cursor to be set to its preorder predecessor
+ * @brief   Preorder predecessor
+ * @param c Cursor to be set to its preorder predecessor
+ * 
+ * Note that this is the reverse postorder successor. 
  */
 template <class Cursor>
 inline
@@ -117,26 +121,22 @@
     (void)) // return type
 predecessor(preorder, Cursor& c)
 {
-    if (!c.is_root()) {
+    if (c.is_root())
+        return;
+
+    if (!index(c)) { // Left child? Return parent.
         c.to_parent();
+        return;
+    }
         
-        // If a left child was given, just move to its parent.
-        if (!index(c))
-            return;
-        
-        // So this is a right child.
-        --c;
+    // Right child.
+    --c;
+    while (!c.is_leaf()) {
+        c.to_end();
+        if (c.is_leaf())
+            --c;
     }
-    
-    // Same for root (=end) and right children:
-    while (!c.is_leaf())
-        if (!c.end().is_leaf())
-            c.to_end();
-        else
-            c.to_begin();
-
-    if (index(c))
-        --c;
+    c.to_parent();
     return;
 }
 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/equal_test.cpp	2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -26,11 +26,14 @@
 BOOST_AUTO_TEST_CASE( test_equal )
 {
     BOOST_CHECK(equal(fbt1.root(), fbt1.root()));
+    BOOST_CHECK(!equal(fbt1.root(), fbt2.root()));
+    // TODO: Also check with empty trees
 }
 
 BOOST_AUTO_TEST_CASE( test_equal_pred )
 {
     BOOST_CHECK(boost::tree::equal(fbt1.root(), fbt1.root(), std::equal_to<int>()));
+    BOOST_CHECK(!boost::tree::equal(fbt1.root(), fbt2.root(), std::equal_to<int>()));
 }
 
 BOOST_AUTO_TEST_CASE( test_size )

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-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -19,24 +19,20 @@
 
 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());
+//}
 
 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();
-    to_last(Order(), c);
-    // Replace by a fake_to_last function for dependency minimization's sake?
-    // preorder: fbt1.root_tracking_root().end().end().begin().begin().end().begin();
-    // inorder: fbt1.root_tracking_root().end().end().begin();
-    // postorder: fbt1.root_tracking_root().begin(); 
+    fake_to_last(Order(), c);
 
     test_data_set mpo;
     mock_cursor_data(mpo);
@@ -48,9 +44,13 @@
     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);
+    BOOST_CHECK(c == d);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

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-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -30,10 +30,7 @@
 {
     fake_root_tracking_binary_tree<int> frbt1(fbt1);
     fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
-    to_first(Order(), c);
-    // Replace by a fake_to_first function for dependency minimization's sake?
-    // preorder: fbt1.root_tracking_root().begin();
-    // in- and postorder: fbt1.root_tracking_root().begin().begin().begin(); 
+    fake_to_first(Order(), c);
 
     test_data_set mpo;
     mock_cursor_data(mpo);
@@ -48,6 +45,10 @@
         BOOST_CHECK_EQUAL(*c, ci->val);
         boost::tree::successor(Order(), c);
     }
+
+    fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
+    fake_to_last(Order(), d);
+    BOOST_CHECK(c == d);
 }
 
 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-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -69,6 +69,39 @@
     BOOST_CHECK_EQUAL(*++a, 8);
     BOOST_CHECK(++a == b);
 
-} // namespace ascending
+}
+
+template <class Cursor>
+void fake_to_first(boost::tree::preorder, Cursor& c)
+{}
+
+template <class Cursor>
+void fake_to_first(boost::tree::inorder, Cursor& c)
+{
+    c.to_begin().to_begin();
+}
+
+template <class Cursor>
+void fake_to_first(boost::tree::postorder, Cursor& c)
+{
+    c.to_begin().to_begin();
+}
+
+template <class Cursor>
+void fake_to_last(boost::tree::preorder, Cursor& c)
+{
+    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();
+}
+
+template <class Cursor>
+void fake_to_last(boost::tree::postorder, Cursor& c)
+{}
+
 
 #endif // LIBS_TREE_TEST_TEST_TREE_TRAVERSAL_DATA_HPP

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/to_first_test.cpp	2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -26,7 +26,10 @@
     = mpo.get<Order>().begin();
     
     fake_binary_tree<int>::descending_cursor c = fbt1.descending_root();
+    fake_binary_tree<int>::descending_cursor d = fbt1.descending_root();
     boost::tree::to_first(Order(), c);
+    fake_to_first(Order(), d);
+    BOOST_CHECK(c == d);
     BOOST_CHECK_EQUAL(*c, ci->val);
 }
 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/to_last_test.cpp	2009-10-19 18:32:33 EDT (Mon, 19 Oct 2009)
@@ -28,9 +28,12 @@
 
     fake_root_tracking_binary_tree<int> frbt1(fbt1);
     fake_root_tracking_binary_tree<int>::cursor c = frbt1.root();
+    fake_root_tracking_binary_tree<int>::cursor d = frbt1.root();
     boost::tree::to_last(Order(), c);
-    boost::tree::predecessor(Order(), c);
-    BOOST_CHECK_EQUAL(*c, cie->val);
+    fake_to_last(Order(), d);
+    BOOST_CHECK(c == d);
+//    boost::tree::predecessor(Order(), c);
+//    BOOST_CHECK_EQUAL(*c, cie->val);
 }
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file