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

Subject: [Boost-commit] svn:boost r51462 - in sandbox/SOC/2006/tree/trunk: . libs/tree/test
From: ockham_at_[hidden]
Date: 2009-02-26 17:28:43

Author: bernhard.reiter
Date: 2009-02-26 17:28:42 EST (Thu, 26 Feb 2009)
New Revision: 51462
URL: http://svn.boost.org/trac/boost/changeset/51462

Log:
forest insert test
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                        |     2                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp              |   200 +-------------------------------------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |    62 +++++++++--                             
   3 files changed, 59 insertions(+), 205 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-02-26 17:28:42 EST (Thu, 26 Feb 2009)
@@ -208,6 +208,8 @@
 
 Documentation:
 
+* Add images - there's quite a lot of public domain tree related stuff on Wikipedia!
+  (acknowledge their authors).
 * algorithms.qbk is rather pointless right now. Better use doygen for
   an algorithm group.
 * Add a rationale for binary tree cursor semantics.

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp	2009-02-26 17:28:42 EST (Thu, 26 Feb 2009)
@@ -34,204 +34,22 @@
     BOOST_CHECK(ft0.begin() == ft0.end());
 }
 
-//BOOST_AUTO_TEST_CASE( insert_value_test )
-//{
-//    using namespace boost::tree;
-//
-////    forest<int> mytree;
-////    
-////    forest<int>::cursor c = mytree.root();
-////    c = mytree.insert(c, 6);
-////    BOOST_CHECK_EQUAL(*c, 6);
-////
-////    c = mytree.insert(c, 5);    
-////    BOOST_CHECK_EQUAL(*c, 5);
-////
-////    c = mytree.insert(c, 4);    
-////    BOOST_CHECK_EQUAL(*c, 4);
-////    BOOST_CHECK(c == mytree.root().begin());
-////
-////    ++c;
-////    BOOST_CHECK_EQUAL(*c, 5);
-////    ++c;
-////    BOOST_CHECK_EQUAL(*c, 6);
-//    
-//    forest<int> ft0;
-//
-//    forest<int>::cursor c = ft0.insert(ft0.end(), 8); //FIXME
-//    
-//    BOOST_CHECK_EQUAL(*c, 8);
-//    BOOST_CHECK(c == ft0.begin());
-//    BOOST_CHECK(++c == ft0.end());
-////    BOOST_CHECK(ft0.begin().parent() == ft0.root());
-//    BOOST_CHECK(!ft0.is_leaf());
-//    BOOST_CHECK(ft0.begin().is_leaf());
-//    
-//    c = ft0.insert(ft0.end(), 6);
-//    BOOST_CHECK_EQUAL(*c, 6);
-//    BOOST_CHECK(ft0.begin() != ft0.end());
-//    BOOST_CHECK(c != ft0.end());
-////    BOOST_CHECK(c.base() == ft0.begin().end());
-////    BOOST_CHECK(c.parent() == ft0.root());
-//    BOOST_CHECK(!ft0.is_leaf());
-//    BOOST_CHECK(++c == ft0.end()); 
-//    ----c;
-//    BOOST_CHECK(c == ft0.begin());
-//    BOOST_CHECK_EQUAL(*c, 8);
-//
-//    c = ft0.insert(ft0.end(), 7);  
-//    BOOST_CHECK_EQUAL(*c, 7);
-////    BOOST_CHECK(c.parent() == ft0.root());
-//    BOOST_CHECK(!ft0.is_leaf());
-//    BOOST_CHECK(++c == ft0.end());
-//    ----c;
-//    BOOST_CHECK_EQUAL(*c, 6);
-////    BOOST_CHECK(c.parent() == ft0.root());
-//    --c;
-//    BOOST_CHECK(c == ft0.begin());
-////    BOOST_CHECK(c.parent() == ft0.root());
-//    BOOST_CHECK_EQUAL(*c, 8);
-//    c = ft0.begin().begin();
-//    BOOST_CHECK(c.parent() == ft0.begin());
-//
-//    c = ft0.insert(ft0.begin().begin(), 3);
-//    BOOST_CHECK_EQUAL(*c, 3);
-//    BOOST_CHECK(c == ft0.begin().begin());
-//    BOOST_CHECK(ft0.begin().begin().parent() == ft0.begin());
-//
-//    // Need more checks after this line...
-//    c = ft0.insert(ft0.begin().begin().begin(), 1);
-//    c = ft0.begin();
-//    (++c).to_end();
-//
-//    c = ft0.insert(c, 4);
-//    BOOST_CHECK_EQUAL(*c, 4);
-//    BOOST_CHECK(--(c.to_parent()) == ft0.begin());
-//
-//    c = ft0.begin();
-//    BOOST_CHECK_EQUAL(*c, 8);
-//    BOOST_CHECK_EQUAL(*c.to_begin(), 3);
-//    BOOST_CHECK_EQUAL(*c.to_begin(), 1);
-//    BOOST_CHECK(c.is_leaf());
-//    
-//    //validate_corresponding_forest(ft0);
-//}
-
 BOOST_AUTO_TEST_SUITE_END()
 
+
 BOOST_FIXTURE_TEST_SUITE(forest_fixture_test, fake_binary_tree_fixture<int>)
 
 BOOST_AUTO_TEST_CASE( binary_tree_constructor_test )
 {
     forest<int, fake_binary_tree<int> > ft0(fbt1);
-    forest<int, fake_binary_tree<int> >::const_cursor c = ft0.begin();
-   
-    //TODO: validate
-    BOOST_CHECK_EQUAL(*c, 8);
-    BOOST_CHECK_EQUAL(*c.to_begin(), 3);
-    BOOST_CHECK_EQUAL(*++c, 6);
-    BOOST_CHECK_EQUAL(*++c, 7);
-    BOOST_CHECK(++c == ft0.begin().end());
-    
-    c = ft0.begin().begin();
-    BOOST_CHECK_EQUAL(*c.to_begin(), 1);
-    BOOST_CHECK(++c == ft0.begin().begin().end());
-
-    c = ft0.begin().begin();
-    ++c;
-    forest<int, fake_binary_tree<int> >::const_cursor d = c; 
-    BOOST_CHECK_EQUAL(*c.to_begin(), 4);
-    BOOST_CHECK(++c == d.end());
-    
-    c = ft0.begin();
-    BOOST_CHECK_EQUAL(*++c, 10);
-    BOOST_CHECK_EQUAL(*++c, 14);
-    d = c;
-    BOOST_CHECK(++c == ft0.end());
-    c = d;
-    BOOST_CHECK_EQUAL(*c.to_begin(), 13);
-    BOOST_CHECK(++c == d.end());
-    c = d.to_begin();
-    BOOST_CHECK_EQUAL(*c.to_begin(), 11);
-    BOOST_CHECK_EQUAL(*++c, 12);
-    BOOST_CHECK(++c == d.end());
+    validate_test_dataset1_forest(ft0.begin(), ft0.end());
 }
 
-BOOST_AUTO_TEST_SUITE_END()
+BOOST_AUTO_TEST_CASE( insert_test )
+{
+    forest<int, fake_binary_tree<int> > ft0;
+    create_test_dataset1_forest(ft0);
+    validate_test_dataset1_forest(ft0.begin(), ft0.end());
+}
 
-//BOOST_FIXTURE_TEST_SUITE(forest_algorithms_test, test_binary_tree_with_list_fixture<int>)
-//
-//// Test *order correspondence:
-//// forest   binary
-//// pre      pre
-//// post     in
-//typedef boost::mpl::list< boost::mpl::pair<preorder, preorder>
-//                        , boost::mpl::pair<postorder, inorder> > corresponding_orders;
-//
-//BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence_for_each, Order
-//                             , corresponding_orders )
-//{
-//    using namespace boost::tree;
-//
-//    forest<int> ft(bt);
-//    
-//    //validate_corresponding_forest(ft);
-//    
-//    std::list<int> test_list;
-//    typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
-//    typedef output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
-//    back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
-//    oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
-//    
-//    boost::tree::for_each(
-//        typename Order::first()
-//      , ft
-//      , boost::lambda::bind(&std::list<int>::push_back, &test_list, boost::lambda::_1)
-//    );
-//    test_traversal(typename Order::second(), test_list.begin(), test_list.end());
-//    BOOST_CHECK_EQUAL(test_list.size(), 11);
-//    
-//}
-
-//BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence_copy, Order
-//                             , corresponding_orders )
-//{
-//    using namespace boost::tree;
-//
-//    forest<int> ft(bt);
-//    
-//    //validate_corresponding_forest(ft);
-//    
-//    std::list<int> test_list;
-//    typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
-//    typedef output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
-//    back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
-//    oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
-//    
-//    boost::tree::copy(typename Order::first(), ft.root(), oc_test_list);
-//    test_traversal(typename Order::second(), test_list.begin(), test_list.end());
-//    BOOST_CHECK_EQUAL(test_list.size(), 11);
-//    test_list.clear();
-//}
-
-//BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence_transform, Order
-//                             , corresponding_orders )
-//{
-//    using namespace boost::tree;
-//
-//    forest<int> ft(bt);
-//    
-//    //validate_corresponding_forest(ft);
-//    
-//    std::list<int> test_list;
-//    typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
-//    typedef output_iterator_cursor<back_insert_iter_list_int> oc_bi_lst_type;
-//    back_insert_iter_list_int it_test_list = std::back_inserter(test_list);
-//    oc_bi_lst_type oc_test_list = oc_bi_lst_type(it_test_list);
-//    boost::tree::transform(typename Order::first(), ft.root(), oc_test_list
-//                         , std::bind2nd(std::plus<int>(),0));
-//    test_traversal(typename Order::second(), test_list.begin(), test_list.end());
-//    BOOST_CHECK_EQUAL(test_list.size(), 11);
-//}
-//
-//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/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-26 17:28:42 EST (Thu, 26 Feb 2009)
@@ -101,31 +101,65 @@
     boost::tree::binary_tree<T> bt, bt2;
 };
 
-template <class Tree>
-void validate_corresponding_forest(Tree const& t)
+template <class Forest>
+static void create_test_dataset1_forest(Forest& f)
 {
-    typename Tree::const_cursor c = t.root().begin();
+    // For augmented trees. (Why is this necessary? Nothing here is explicit!)
+    typedef typename Forest::value_type value_type; 
+    
+    typename Forest::cursor cur = f.insert(f.end(), value_type(8));
+    cur = f.insert(f.end(), value_type(10));
+    cur = f.insert(f.end(), value_type(14));
+
+    cur = f.begin().begin();
+    cur = f.insert(cur, value_type(3));
+    cur = f.insert(++cur, value_type(7));
+    cur = f.insert(cur, value_type(6));
+
+    cur = f.begin().begin().begin();
+    cur = f.insert(cur, value_type(1));
+
+    cur = f.begin().begin();
+    cur = f.insert((++cur).to_begin(), value_type(4));
+
+    cur = f.begin();
+    cur = f.insert((++++cur).to_begin(), value_type(13));
+    cur = f.insert(cur.to_begin(), value_type(11));
+    cur = f.insert(++cur, value_type(12));
+}
+
+template <class Cursor>
+static void validate_test_dataset1_forest(Cursor cur, Cursor e)
+{
+    Cursor c = cur;
     BOOST_CHECK_EQUAL(*c, 8);
     BOOST_CHECK_EQUAL(*c.to_begin(), 3);
-    BOOST_CHECK_EQUAL(*c.to_begin(), 1);
-    BOOST_CHECK(c.is_leaf());
-    BOOST_CHECK(++c == t.root().begin().begin().end());
-    --c;
-    c.to_parent();
     BOOST_CHECK_EQUAL(*++c, 6);
-    BOOST_CHECK_EQUAL(*c.to_begin(), 4);
-    c.to_parent();
     BOOST_CHECK_EQUAL(*++c, 7);
-    BOOST_CHECK(++c == t.root().begin().end());
+    BOOST_CHECK(++c == cur.end());
+    
+    c = cur.begin();
+    BOOST_CHECK_EQUAL(*c.to_begin(), 1);
+    BOOST_CHECK(++c == cur.begin().end());
+
+    c = cur.begin();
+    ++c;
+    Cursor d = c; 
+    BOOST_CHECK_EQUAL(*c.to_begin(), 4);
+    BOOST_CHECK(++c == d.end());
     
-    c = t.root().begin();
+    c = cur;
     BOOST_CHECK_EQUAL(*++c, 10);
     BOOST_CHECK_EQUAL(*++c, 14);
-    BOOST_CHECK(++c == t.root().end());
-    --c;
+    d = c;
+    BOOST_CHECK(++c == e);
+    c = d;
     BOOST_CHECK_EQUAL(*c.to_begin(), 13);
+    BOOST_CHECK(++c == d.end());
+    c = d.to_begin();
     BOOST_CHECK_EQUAL(*c.to_begin(), 11);
     BOOST_CHECK_EQUAL(*++c, 12);
+    BOOST_CHECK(++c == d.end());
 }
 
 template <class Container>