[Boost-commit] svn:boost r49707 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/cursor libs/tree/doc libs/tree/test

Subject: [Boost-commit] svn:boost r49707 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail/cursor libs/tree/doc libs/tree/test
From: ockham_at_[hidden]
Date: 2008-11-12 19:10:24

Author: bernhard.reiter
Date: 2008-11-12 19:10:23 EST (Wed, 12 Nov 2008)
New Revision: 49707
URL: http://svn.boost.org/trac/boost/changeset/49707

Log:
Fix forest_tree cursor (conceptually).
Properties modified: 
   sandbox/SOC/2006/tree/trunk/libs/tree/doc/   (props changed)
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                |     5                                         
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp          |    12 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp |    35 +++--                                   
   sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp          |    67 +++++++----                             
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp |    51 +++++++-                                
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp |   219 +++++++++++++++++++++++++++------------ 
   6 files changed, 264 insertions(+), 125 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2008-11-12 19:10:23 EST (Wed, 12 Nov 2008)
@@ -18,7 +18,10 @@
   context dependent thing; so merge it into the general iterative algorithm versions.
 * Move some of the secondary stuff to a util/ dir? Is that what they're used for?
 * Redo testing. Right now, it's just chaotic.
-* Fix recursive algorithms for use with forest.
+* Fix algorithms for use with forest:
+  * Recursive preorder: OK.
+  * Recursive postorder: TBD.
+  * Iterative pre- and postorder: TBD.
 * Implement a real output cursor (if possible) and use preorder::copy to build a new tree.
   Then, do some performance measurements comparing
   * Different *orders;

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp	2008-11-12 19:10:23 EST (Wed, 12 Nov 2008)
@@ -199,12 +199,12 @@
     // Hierarchy-specific
     
     /**
-     * @brief        Inserts val in front of @a pos, or, if @a pos' parent is
-     *                 already full, creates a new child node containing @a val 
-     *                 instead.
-     * @param pos    The %binary_tree cursor in front of which to insert.
-     * @param val    The value to insert.
-     * @return        A cursor that points to the inserted data.
+     * @brief       Inserts val in front of @a pos, or, if @a pos' parent is
+     *              already full, creates a new child node containing @a val 
+     *              instead.
+     * @param pos   The %binary_tree cursor in front of which to insert.
+     * @param val   The value to insert.
+     * @return      A cursor that points to the inserted data.
      */
     cursor insert(cursor pos, value_type const& val)
     {

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/cursor/forest.hpp	2008-11-12 19:10:23 EST (Wed, 12 Nov 2008)
@@ -79,32 +79,36 @@
 
     operator base_cursor()
     {
-        return this->base();
+        return forest_cursor::cursor_adaptor_::base();
     }
     
+    Cursor const& base() const
+    {
+        return forest_cursor::cursor_adaptor_::base();
+    }
 private:
     
     friend class cursor_core_access;
     friend class iterator_core_access;
 
-//    bool empty_() const
-//    {
-//        if (this->base().index())
-//            return true;
-//        return this->base().empty();
-//    }
+    bool empty_() const
+    {
+        return this->base().begin().empty() && this->base().end().empty();
+    }
+
+    typename forest_cursor::cursor_adaptor_::reference dereference() const
+    {
+        return *this->base_reference().begin();
+    }
 
     void increment()
     {
-         if (!(++this->base_reference()).empty())
-             this->base_reference().to_begin();
+        this->base_reference().to_end();
     }
     
     void decrement()
     {
-        if (!index(this->base()))
-            this->base_reference().to_parent();
-        --this->base_reference();
+        this->base_reference().to_parent();
     }
     
     // Range stuff.
@@ -113,15 +117,18 @@
 
     void right()
     {
-        while (!this->base_reference().to_end().empty());
+        this->base_reference().to_begin();
+        while (!this->base_reference().empty())
+            this->base_reference().to_end();
     }
     
     // Cursor stuff. 
     
     void up()
     {
-        if (!index(this->base()))
+        while (index(this->base_reference()))
             this->base_reference().to_parent();
+        this->base_reference().to_parent();
     }
 };
 

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	2008-11-12 19:10:23 EST (Wed, 12 Nov 2008)
@@ -46,26 +46,36 @@
     typedef typename cursor_size<cursor>::type size_type;
     typedef typename cursor_difference<cursor>::type difference_type;
 
-//    forest_tree()
-//    {
-//        h.insert(h.root(), );
-//    }
-    
-    explicit forest_tree(Hierarchy const& hier = Hierarchy()) : h(hier)
-    { }
-    
-    bool empty()
+    /**
+     *  @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())
     {
-        return h.empty();
+        h.insert(h.root(), val);
     }
-    
-    size_type size() const
+
+    /**
+     *  @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)
     {
-        return h.size();
+        if (h.empty())
+            h.insert(h.root(), value_type());
+    }
+
+    /**
+     * Returns true if the %forest_tree is empty.
+     */
+    bool empty()
+    {
+        return h.empty();
     }
     
     /**
-     * Returns a read/write ("mutable") cursor to the %binary_tree's root.
+     * Returns a read/write ("mutable") cursor to the %forest_tree's root.
      */     
     cursor root()
     {
@@ -73,7 +83,7 @@
     }
 
     /**
-     * Returns a read-only const_cursor to the %binary_tree's root.
+     * Returns a read-only const_cursor to the %forest_tree's root.
      */     
     const_cursor root() const
     {
@@ -81,27 +91,34 @@
     }
     
     /**
-     * Returns a read-only const_cursor to the %binary_tree's root.
+     * Returns a read-only const_cursor to the %forest_tree's root.
      */     
     const_cursor croot() const
     {
         return const_cursor(h.croot());
     }
 
+    /**
+     * @brief       Inserts val in front of @a pos.
+     * @param pos   The %forest_tree cursor in front of which to insert.
+     * @param val   The value to insert.
+     * @return      A cursor that points to the inserted data.
+     */
     cursor insert(cursor pos, value_type const& val)
     {
-        // TODO: Could we remove the root-checking part if root.parent() 
-        // returned root? Or don't we even want root?
-        base_cursor bc = base_cursor(pos);
-        if (bc != h.root())
-            bc = bc.parent();
-        //if (index(bc))
-        return cursor(h.insert(bc, val));
+        return cursor(h.insert(base_cursor(pos), val).to_parent());
     }
+
+    /**
+     * @brief Clears all data from the forest tree.
+     */
+     void clear()
+     {
+        h.clear();
+     }
     
- protected:
+protected:
     hierarchy_type h;
-     
 };
 
 

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp	2008-11-12 19:10:23 EST (Wed, 12 Nov 2008)
@@ -15,6 +15,48 @@
 #include "helpers.hpp"
 #include "test_tree_traversal_data.hpp"
 
+BOOST_AUTO_TEST_SUITE( basic_binary_tree_test )
+
+BOOST_AUTO_TEST_CASE( constructors_test )
+{
+    binary_tree<int> bt0;
+    BOOST_CHECK(bt0.root().empty());
+    
+    // test with allocator? 
+}
+
+BOOST_AUTO_TEST_CASE( insert_value_test )
+{
+    binary_tree<int> bt0;
+    BOOST_CHECK(bt0.root().empty());
+    
+    binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8);
+    
+    BOOST_CHECK(c == bt0.root().begin());
+    BOOST_CHECK(bt0.root().begin().parent() == bt0.root());
+    BOOST_CHECK(!bt0.root().empty());
+    BOOST_CHECK_EQUAL(*bt0.root().begin(), 8);
+    BOOST_CHECK(bt0.root().begin().empty());
+    
+    c = bt0.insert(c, 3);
+    
+    // The 8 valued cursor still ok?
+    BOOST_CHECK(bt0.root().begin().parent() == bt0.root());
+    BOOST_CHECK(!bt0.root().empty());
+    BOOST_CHECK_EQUAL(*bt0.root().begin(), 8);
+    
+    // The 3 valued cursor.
+    BOOST_CHECK(c == bt0.root().begin().begin());
+    BOOST_CHECK(bt0.root().begin().begin().parent() == bt0.root().begin());
+    BOOST_CHECK(!bt0.root().begin().empty());
+    BOOST_CHECK_EQUAL(*bt0.root().begin().begin(), 3);
+    BOOST_CHECK(bt0.root().begin().begin().empty());
+    
+    BOOST_CHECK(++c == bt0.root().begin().end());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
 BOOST_FIXTURE_TEST_SUITE(binary_tree_test, test_binary_tree_with_list_fixture<int>)
 
 using namespace boost::tree;
@@ -131,15 +173,6 @@
     BOOST_CHECK(bt.empty());
 }
 
-BOOST_AUTO_TEST_CASE( constructors_test )
-{
-    binary_tree<int> bt0;
-    BOOST_CHECK(bt0.root().empty());
-    //BOOST_CHECK_EQUAL(0, 1);
-    
-    // test with allocator 
-}
-
 BOOST_AUTO_TEST_CASE( swap_binary_tree_test )
 {
     using std::swap;

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	2008-11-12 19:10:23 EST (Wed, 12 Nov 2008)
@@ -23,91 +23,170 @@
 
 using namespace boost::tree;
 
-typedef boost::mpl::list< boost::mpl::pair<preorder, preorder>
-                        /*, boost::mpl::pair<postorder, inorder>*/ > corresponding_orders;
+BOOST_AUTO_TEST_SUITE( basic_forest_test )
 
-BOOST_FIXTURE_TEST_SUITE(forest_algorithms_test, test_binary_tree_with_list_fixture<int>)
+BOOST_AUTO_TEST_CASE( constructors_test )
+{
+    forest_tree<int> ft0;
+    BOOST_CHECK_EQUAL(*ft0.root(), 0);
+    BOOST_CHECK(ft0.root().empty());
+}
 
-BOOST_AUTO_TEST_CASE( forest_tree_test )
+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);
+    
+    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_EQUAL(*ft0.root().begin(), 8);
+    BOOST_CHECK(ft0.root().begin().empty());
+    
+    c = ft0.insert(ft0.root().end(), 6);
     
-    typedef forest_tree<int> tree_type;
-    tree_type mytree;
+    BOOST_CHECK(ft0.root().begin() != ft0.root().end());
+    BOOST_CHECK(c != ft0.root().end());
+    
+    BOOST_CHECK(c.base() == ft0.root().base().begin().end());
     
-    tree_type::cursor c = mytree.root();
-    c = mytree.insert(c, 6);    
     BOOST_CHECK_EQUAL(*c, 6);
+    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 = 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);
+    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());
     
-    tree_type forest;
-    //create_test_dataset1_tree(forest);
-    c = forest.insert(forest.root(), 8);
-    BOOST_CHECK(c == forest.root().begin());
+    ----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 = forest.insert(c, 3);
-    BOOST_CHECK_EQUAL(*c, 3);
-    BOOST_CHECK_EQUAL(*++c, 8);
-//    BOOST_CHECK_EQUAL(*forest.root().begin().begin(), 3);
 
-}
+    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());
 
-BOOST_AUTO_TEST_CASE_TEMPLATE( test_natural_correspondence, Order
-                             , corresponding_orders )
-{
-    using namespace boost::tree;
+    // Need more checks after this line...
+    c = ft0.insert(ft0.root().begin().begin().begin(), 1);
 
-    typedef forest_tree<int> forest_tree_type;
-    forest_tree_type ft(bt);
-    
-    validate_corresponding_forest_tree(ft);
-    
-    // Now test *order correspondence:
-    // forest    binary
-    // pre        pre
-    // post        in
-    std::list<int> test_list;
-    typedef std::back_insert_iterator< std::list<int> > back_insert_iter_list_int;
-    typedef output_cursor_iterator_wrapper<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);
-    test_list.clear();
-    
-    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::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);
-    test_list.clear();
+    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());
 
-    //test::preorder::algorithms(ft.root(), ft.root()); // FIXME: Fix algorithms for use in here.
+    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());
     
-//    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);
+    //validate_corresponding_forest_tree(ft0);
 }
 
+BOOST_AUTO_TEST_SUITE_END()
 
-BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file
+//BOOST_FIXTURE_TEST_SUITE(forest_algorithms_test, test_binary_tree_with_list_fixture<int>)
+//
+//// Test *order correspondence:
+//// forest   binary
+//// pre      pre
+//// post     in
+//// FIXME: should also check post-/inorder correspondence
+//
+//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_cursor_iterator_wrapper<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),
+//        boost::forward_traversal_tag() // FIXME: Also fix and test iterative versions!
+//    );
+//    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_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_cursor_iterator_wrapper<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
+//                    , boost::forward_traversal_tag()); // FIXME: Also fix and test iterative versions!
+//    test_traversal(typename Order::second(), test_list.begin(), test_list.end());
+//    BOOST_CHECK_EQUAL(test_list.size(), 11);
+//    test_list.clear();
+//    
+//    boost::tree::transform(typename Order::first(), ft.root(), oc_test_list
+//                         , std::bind2nd(std::plus<int>(),0)
+//                         , boost::forward_traversal_tag()); // FIXME: Also fix and test iterative versions!
+//    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