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

Subject: [Boost-commit] svn:boost r50430 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-01 07:53:33

Author: bernhard.reiter
Date: 2009-01-01 07:53:32 EST (Thu, 01 Jan 2009)
New Revision: 50430
URL: http://svn.boost.org/trac/boost/changeset/50430

Log:
Start changing forest semantics.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                |     5                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp          |    68 +++++++++--                             
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp |   226 ++++++++++++++++++++--------------------
   3 files changed, 170 insertions(+), 129 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-01-01 07:53:32 EST (Thu, 01 Jan 2009)
@@ -14,6 +14,11 @@
 [section TODO]
 
 General:
+* Re-do forest (again!). No root(); begin() and end() instead. No default element at
+  construction time (that would really suck). Rename forest_tree to forest, 
+  as it's going to be a forest, not just "one" tree.
+  This seems to raise one issue, though: subtree algorithms operate on subtree root cursors,
+  not ranges. (They might, however, work for "subforests".)
 * Improve cursor_archetype. Currently, there's trouble eg with constructors.
 * Remove a cursor's cursor, const_cursor, iterator and const_iterator typedefs?
   The latter two only make sense in a range algorithm context, where they might actually be

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp	2009-01-01 07:53:32 EST (Thu, 01 Jan 2009)
@@ -63,20 +63,20 @@
      *  @brief    The default constructor creates one element at the root.
      *  @param    val   The value the root will be assigned. 
      */
-    forest_tree(value_type const& val = value_type()) : h(Hierarchy())
-    {
-        h.insert(h.root(), val);
-    }
+//    forest_tree(/*value_type const& val = value_type()*/) : h(Hierarchy())
+//    {
+//        //h.insert(h.root(), val);
+//    }
 
     /**
      *  @brief    The default constructor creates no elements.
      *  @param    hier    A hierarchy object that will be used as a base to
      *                    construct this forest_tree.
      */
-    explicit forest_tree(Hierarchy const& hier) : h(hier)
+    explicit forest_tree(Hierarchy const& hier = Hierarchy()) : h(hier)
     {
-        if (h.empty())
-            h.insert(h.root(), value_type());
+//        if (h.empty())
+//            h.insert(h.root(), value_type());
     }
 
     /**
@@ -88,27 +88,63 @@
     }
     
     /**
-     * Returns a read/write ("mutable") cursor to the %forest_tree's root.
+     * Returns a read/write ("mutable") cursor to the %forest_tree's 
+     * first element.
+     */     
+    cursor begin()
+    {
+        cursor c(h.root());
+        return c.begin();
+    }
+
+    /**
+     * Returns a read-only const_cursor to the %forest_tree's
+     * first element.
+     */     
+    const_cursor begin() const
+    {
+        return cbegin();
+    }
+    
+    /**
+     * Returns a read-only const_cursor to the %forest_tree's
+     * first element.
+     */     
+    const_cursor cbegin() const
+    {
+        const_cursor c(h.croot());
+        return c.begin();
+    }
+
+    // TODO: end.
+
+    /**
+     * Returns a read/write ("mutable") cursor past the %forest_tree's
+     * last element.
      */     
-    cursor root()
+    cursor end()
     {
-        return cursor(h.root());
+        cursor c(h.root());
+        return c.end();
     }
 
     /**
-     * Returns a read-only const_cursor to the %forest_tree's root.
+     * Returns a read-only const_cursor past the %forest_tree's
+     * last element.
      */     
-    const_cursor root() const
+    const_cursor end() const
     {
-        return croot();
+        return cend();
     }
     
     /**
-     * Returns a read-only const_cursor to the %forest_tree's root.
+     * Returns a read-only const_cursor past the %forest_tree's
+     * last element.
      */     
-    const_cursor croot() const
+    const_cursor cend() const
     {
-        return const_cursor(h.croot());
+        const_cursor c(h.croot());
+        return c.end();
     }
 
     /**

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp	2009-01-01 07:53:32 EST (Thu, 01 Jan 2009)
@@ -28,128 +28,128 @@
 BOOST_AUTO_TEST_CASE( constructors_test )
 {
     forest_tree<int> ft0;
-    BOOST_CHECK_EQUAL(*ft0.root(), 0);
-    BOOST_CHECK(ft0.root().empty());
+    //BOOST_CHECK_EQUAL(*ft0.root(), 0);
+    BOOST_CHECK(ft0.empty());
 }
 
-BOOST_AUTO_TEST_CASE( insert_value_test )
-{
-    using namespace boost::tree;
-
-//    forest_tree<int> mytree;
+//BOOST_AUTO_TEST_CASE( insert_value_test )
+//{
+//    using namespace boost::tree;
+//
+////    forest_tree<int> mytree;
+////    
+////    forest_tree<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_tree<int> ft0;
+//
+//    forest_tree<int>::cursor c = ft0.insert(ft0.root().end(), 8);
 //    
-//    forest_tree<int>::cursor c = mytree.root();
-//    c = mytree.insert(c, 6);
+//    BOOST_CHECK_EQUAL(*c, 8);
+//    BOOST_CHECK(c == ft0.root().begin());
+//    BOOST_CHECK(++c == ft0.root().end());
+//    BOOST_CHECK(ft0.root().begin().parent() == ft0.root());
+//    BOOST_CHECK(!ft0.root().empty());
+//    BOOST_CHECK(ft0.root().begin().empty());
+//    
+//    c = ft0.insert(ft0.root().end(), 6);
+//    BOOST_CHECK_EQUAL(*c, 6);
+//    BOOST_CHECK(ft0.root().begin() != ft0.root().end());
+//    BOOST_CHECK(c != ft0.root().end());
+//    BOOST_CHECK(c.base() == ft0.root().base().begin().end());
+//    BOOST_CHECK(c.parent() == ft0.root());
+//    BOOST_CHECK(!ft0.root().empty());
+//    BOOST_CHECK(++c == ft0.root().end()); 
+//    ----c;
+//    BOOST_CHECK(c == ft0.root().begin());
+//    BOOST_CHECK_EQUAL(*c, 8);
+//
+//    c = ft0.insert(ft0.root().end(), 7);  
+//    BOOST_CHECK_EQUAL(*c, 7);
+//    BOOST_CHECK(c.parent() == ft0.root());
+//    BOOST_CHECK(!ft0.root().empty());
+//    BOOST_CHECK(++c == ft0.root().end());
+//    ----c;
 //    BOOST_CHECK_EQUAL(*c, 6);
+//    BOOST_CHECK(c.parent() == ft0.root());
+//    --c;
+//    BOOST_CHECK(c == ft0.root().begin());
+//    BOOST_CHECK(c.parent() == ft0.root());
+//    BOOST_CHECK_EQUAL(*c, 8);
+//    c = ft0.root().begin().begin();
+//    BOOST_CHECK(c.parent() == ft0.root().begin());
 //
-//    c = mytree.insert(c, 5);    
-//    BOOST_CHECK_EQUAL(*c, 5);
+//    c = ft0.insert(ft0.root().begin().begin(), 3);
+//    BOOST_CHECK_EQUAL(*c, 3);
+//    BOOST_CHECK(c == ft0.root().begin().begin());
+//    BOOST_CHECK(ft0.root().begin().begin().parent() == ft0.root().begin());
 //
-//    c = mytree.insert(c, 4);    
+//    // Need more checks after this line...
+//    c = ft0.insert(ft0.root().begin().begin().begin(), 1);
+//    c = ft0.root().begin();
+//    (++c).to_end();
+//
+//    c = ft0.insert(c, 4);
 //    BOOST_CHECK_EQUAL(*c, 4);
-//    BOOST_CHECK(c == mytree.root().begin());
+//    BOOST_CHECK(--(c.to_parent()) == ft0.root().begin());
 //
-//    ++c;
-//    BOOST_CHECK_EQUAL(*c, 5);
-//    ++c;
-//    BOOST_CHECK_EQUAL(*c, 6);
-    
-    forest_tree<int> ft0;
-
-    forest_tree<int>::cursor c = ft0.insert(ft0.root().end(), 8);
-    
-    BOOST_CHECK_EQUAL(*c, 8);
-    BOOST_CHECK(c == ft0.root().begin());
-    BOOST_CHECK(++c == ft0.root().end());
-    BOOST_CHECK(ft0.root().begin().parent() == ft0.root());
-    BOOST_CHECK(!ft0.root().empty());
-    BOOST_CHECK(ft0.root().begin().empty());
-    
-    c = ft0.insert(ft0.root().end(), 6);
-    BOOST_CHECK_EQUAL(*c, 6);
-    BOOST_CHECK(ft0.root().begin() != ft0.root().end());
-    BOOST_CHECK(c != ft0.root().end());
-    BOOST_CHECK(c.base() == ft0.root().base().begin().end());
-    BOOST_CHECK(c.parent() == ft0.root());
-    BOOST_CHECK(!ft0.root().empty());
-    BOOST_CHECK(++c == ft0.root().end()); 
-    ----c;
-    BOOST_CHECK(c == ft0.root().begin());
-    BOOST_CHECK_EQUAL(*c, 8);
-
-    c = ft0.insert(ft0.root().end(), 7);  
-    BOOST_CHECK_EQUAL(*c, 7);
-    BOOST_CHECK(c.parent() == ft0.root());
-    BOOST_CHECK(!ft0.root().empty());
-    BOOST_CHECK(++c == ft0.root().end());
-    ----c;
-    BOOST_CHECK_EQUAL(*c, 6);
-    BOOST_CHECK(c.parent() == ft0.root());
-    --c;
-    BOOST_CHECK(c == ft0.root().begin());
-    BOOST_CHECK(c.parent() == ft0.root());
-    BOOST_CHECK_EQUAL(*c, 8);
-    c = ft0.root().begin().begin();
-    BOOST_CHECK(c.parent() == ft0.root().begin());
-
-    c = ft0.insert(ft0.root().begin().begin(), 3);
-    BOOST_CHECK_EQUAL(*c, 3);
-    BOOST_CHECK(c == ft0.root().begin().begin());
-    BOOST_CHECK(ft0.root().begin().begin().parent() == ft0.root().begin());
-
-    // Need more checks after this line...
-    c = ft0.insert(ft0.root().begin().begin().begin(), 1);
-    c = ft0.root().begin();
-    (++c).to_end();
-
-    c = ft0.insert(c, 4);
-    BOOST_CHECK_EQUAL(*c, 4);
-    BOOST_CHECK(--(c.to_parent()) == ft0.root().begin());
-
-    c = ft0.root().begin();
-    BOOST_CHECK_EQUAL(*c, 8);
-    BOOST_CHECK_EQUAL(*c.to_begin(), 3);
-    BOOST_CHECK_EQUAL(*c.to_begin(), 1);
-    BOOST_CHECK(c.empty());
-    
-    //validate_corresponding_forest_tree(ft0);
-}
+//    c = ft0.root().begin();
+//    BOOST_CHECK_EQUAL(*c, 8);
+//    BOOST_CHECK_EQUAL(*c.to_begin(), 3);
+//    BOOST_CHECK_EQUAL(*c.to_begin(), 1);
+//    BOOST_CHECK(c.empty());
+//    
+//    //validate_corresponding_forest_tree(ft0);
+//}
 
 BOOST_AUTO_TEST_SUITE_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_tree<int> ft(bt);
-    
-    //validate_corresponding_forest_tree(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.root()
-      , 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_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_tree<int> ft(bt);
+//    
+//    //validate_corresponding_forest_tree(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 )
@@ -191,5 +191,5 @@
 //    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()
\ No newline at end of file