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

Subject: [Boost-commit] svn:boost r51234 - in sandbox/SOC/2006/tree/trunk: . libs/tree/test
From: ockham_at_[hidden]
Date: 2009-02-12 21:21:11

Author: bernhard.reiter
Date: 2009-02-12 21:21:11 EST (Thu, 12 Feb 2009)
New Revision: 51234
URL: http://svn.boost.org/trac/boost/changeset/51234

Log:
successor and predecessor optimisation
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                        |     5 ++                                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/predecessor_test.cpp         |    89 ++++++------------------------------    
   sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp           |    97 +++++++-------------------------------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |     4 -                                       
   4 files changed, 38 insertions(+), 157 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-02-12 21:21:11 EST (Thu, 12 Feb 2009)
@@ -14,6 +14,11 @@
 [section TODO]
 
 General:
+* Further reduce test data redundancy: make mock cursor use the data from fake_binary_tree, 
+  and give it an Order template argument. Calculate *order positions from level order indices
+  as of fake_binary_tree. Possibly change fake_binary_tree internal representation to a 
+  vector<bool> with indices indicating the level order position (and also the value),
+  and values indicating "empty or not".
 * Re-merge algorithm tests into algorithm_test.cpp after they're all tidied up?
 * Add algorithms for construction of a tree based on two ranges specifying its
   pre-/in-/postorder linearization (see Knuth).

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-02-12 21:21:11 EST (Thu, 12 Feb 2009)
@@ -19,82 +19,25 @@
 
 BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
 
-BOOST_AUTO_TEST_CASE( test_predecessor_preorder )
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_predecessor, Order, orders )
 {
-    fake_binary_tree<int>::root_tracking_cursor c
-    = fbt1.root_tracking_root().end().end().begin().begin().end().begin();
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 11);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 13);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 14);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 10);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 7);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 4);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 6);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 1);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 3);
-    boost::tree::predecessor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 8);
-}
+    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
+    to_last(Order(), c);
+    // Replace by a fake_to_first 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(); 
 
-BOOST_AUTO_TEST_CASE( test_predecessor_inorder )
-{
-    fake_binary_tree<int>::root_tracking_cursor c
-    = fbt1.root_tracking_root().end().end().begin();
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 13);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 12);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 11);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 10);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 8);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 7);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 6);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 4);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 3);
-    boost::tree::predecessor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 1);
-}
+    typedef std::vector< std::pair<std::size_t, int> > container_type;
+    container_type po(11);
+    generate_mock_cursor_data(Order(), po);
+    container_type::const_iterator cib = po.begin();
+    container_type::const_iterator ci = po.end();
 
-BOOST_AUTO_TEST_CASE( test_predecessor_postorder )
-{
-    fake_binary_tree<int>::root_tracking_cursor c
-    = fbt1.root_tracking_root().begin();
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 10);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 14);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 13);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 11);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 12);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 3);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 6);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 7);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 4);
-    boost::tree::predecessor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 1);
+    for (--ci; ci!=cib; --ci) {
+        boost::tree::predecessor(Order(), c);
+        BOOST_CHECK_EQUAL(*c, ci->second);
+    }
 }
 
 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-02-12 21:21:11 EST (Thu, 12 Feb 2009)
@@ -19,87 +19,24 @@
 
 BOOST_FIXTURE_TEST_SUITE(cursor_algorithms_test, fake_binary_tree_fixture<int>)
 
-// TODO: iterate over all elements.
-
-BOOST_AUTO_TEST_CASE( test_successor_preorder )
-{
-    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root().begin();
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 3);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 1);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 6);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 4);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 7);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 10);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 14);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 13);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 11);
-    boost::tree::successor(preorder(), c);
-    BOOST_CHECK_EQUAL(*c, 12);
-}
-
-BOOST_AUTO_TEST_CASE( test_successor_inorder )
-{
-    fake_binary_tree<int>::root_tracking_cursor c
-    = fbt1.root_tracking_root().begin().begin().begin().begin();
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 1);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 3);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 4);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 6);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 7);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 8);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 10);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 11);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 12);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 13);
-    boost::tree::successor(inorder(), c);
-    BOOST_CHECK_EQUAL(*c, 14);
-}
-
-BOOST_AUTO_TEST_CASE( test_successor_postorder )
+BOOST_AUTO_TEST_CASE_TEMPLATE( test_successor, Order, orders )
 {
-    fake_binary_tree<int>::root_tracking_cursor c
-    = fbt1.root_tracking_root().begin().begin().begin().begin();
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 1);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 4);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 7);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 6);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 3);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 12);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 11);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 13);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 14);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 10);
-    boost::tree::successor(postorder(), c);
-    BOOST_CHECK_EQUAL(*c, 8);
+    fake_binary_tree<int>::root_tracking_cursor c = fbt1.root_tracking_root(); //.begin();
+    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(); 
+
+    typedef std::vector< std::pair<std::size_t, int> > container_type;
+    container_type po(11);
+    generate_mock_cursor_data(Order(), po);
+    container_type::const_iterator ci = po.begin();
+    container_type::const_iterator cie = po.end();
+
+    for (; ci!=cie; ++ci) {
+        BOOST_CHECK_EQUAL(*c, ci->second);
+        boost::tree::successor(Order(), c);
+    }
 }
 
 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-02-12 21:21:11 EST (Thu, 12 Feb 2009)
@@ -10,12 +10,8 @@
 #include <boost/tree/binary_tree.hpp>
 #include <boost/tree/algorithm.hpp>
 
-#include <vector>
-
 #include <boost/mpl/list.hpp>
 
-
-
 typedef boost::mpl::list<boost::tree::preorder
                         ,boost::tree::inorder
                         ,boost::tree::postorder> orders;