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

Subject: [Boost-commit] svn:boost r50580 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-14 12:00:20

Author: bernhard.reiter
Date: 2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
New Revision: 50580
URL: http://svn.boost.org/trac/boost/changeset/50580

Log:
Add some tests.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                |     3 -                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp          |     3 +                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp |     4 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/forest_tree.hpp          |    20 +++++++++++-------                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp |    32 ++++++++++++++++++++---------           
   sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp |    12 +++++++---                              
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_tree_test.cpp |    43 +++++++++++++++++++++++++++++++++++++-- 
   7 files changed, 87 insertions(+), 30 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -15,8 +15,6 @@
 
 General:
 * preorder_insert_cursor: hopefully easy to implement...
-* Fix binary tree/node: empty() -> root.begin() == root.end() !
-* Check forest/binary_tree correspondence in a hard wired fashion.
 * Add checks for correspondence of concepts and archetypes!
 * 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, 
@@ -146,6 +144,7 @@
 * Optimise insert_cursor for use with binary_tree insert and copy ctor 
   (preorder copy; ideally, we can guarantee RAII for every single element)
   and clear/dtor (postorder for_each).
+* Deprecate non-preorder insert cursors.
 
 Ask on the mailing list:
 

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	2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -197,7 +197,8 @@
         void* node_hint = 0;
         
         node_pointer p_node = m_node_alloc.allocate(1, node_hint);
-        m_node_alloc.construct(p_node, val);
+        //m_node_alloc.construct(p_node, val);
+        *p_node = node_type(val);
         p_node->init();
         
         pos.attach(p_node);

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp	2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -67,8 +67,8 @@
     forest_cursor(
         forest_cursor<OtherCursor> const& other
       , typename boost::enable_if<
-            boost::is_convertible<OtherCursor*, 
-               typename Cursor::base_pointer>  // is that correct?
+            boost::is_convertible<OtherCursor, 
+               Cursor>  // is that correct?
           , enabler
         >::type = enabler()
     )

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-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -93,8 +93,8 @@
      */     
     cursor begin()
     {
-        cursor c(h.root());
-        return c.begin();
+        //cursor c(h.root());
+        return cursor(h.root());
     }
 
     /**
@@ -112,8 +112,8 @@
      */     
     const_cursor cbegin() const
     {
-        const_cursor c(h.croot());
-        return c.begin();
+        //const_cursor c(h.croot());
+        return const_cursor(h.croot());
     }
 
     // TODO: end.
@@ -124,8 +124,10 @@
      */     
     cursor end()
     {
-        cursor c(h.root());
-        return c.end();
+        base_cursor b(h.root());
+        while (!b.empty())
+            b.to_end();
+        return cursor(b);
     }
 
     /**
@@ -143,8 +145,10 @@
      */     
     const_cursor cend() const
     {
-        const_cursor c(h.croot());
-        return c.end();
+        base_const_cursor b(h.croot());
+        while (!b.empty())
+            b.to_end();
+        return const_cursor(b);
     }
 
     /**

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	2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -14,11 +14,12 @@
 
 //#include "helpers.hpp"
 #include "test_tree_traversal_data.hpp"
-
-BOOST_AUTO_TEST_SUITE( basic_binary_tree_test )
+#include "fake_binary_tree.hpp"
 
 using boost::tree::binary_tree;
 
+BOOST_AUTO_TEST_SUITE( basic_binary_tree_test )
+
 BOOST_AUTO_TEST_CASE( constructors_test )
 {
     binary_tree<int> bt0;
@@ -61,7 +62,25 @@
 
 BOOST_AUTO_TEST_SUITE_END()
 
-BOOST_FIXTURE_TEST_SUITE(binary_tree_test, test_binary_tree_with_list_fixture<int>)
+BOOST_FIXTURE_TEST_SUITE( binary_tree_using_fake_binary_tree_test
+                        , fake_binary_tree_fixture<int> )
+
+BOOST_AUTO_TEST_CASE( subtree_constructor_test )
+{
+    binary_tree<int> bt0(fbt1.root());
+    validate_test_dataset1_tree(bt0.root());
+}
+
+BOOST_AUTO_TEST_CASE( insert_subtree_test )
+{
+    binary_tree<int> bt0;
+    binary_tree<int>::cursor c = bt0.insert(bt0.root(), fbt1.root());    
+    validate_test_dataset1_tree(bt0.root());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
+
+BOOST_FIXTURE_TEST_SUITE( binary_tree_test, test_binary_tree_with_list_fixture<int> )
 
 using namespace boost::tree;
 
@@ -208,13 +227,6 @@
     validate_test_dataset2_tree(bt.root());
 }
 
-BOOST_AUTO_TEST_CASE( insert_subtree_test )
-{
-    binary_tree<int> bt0;
-    binary_tree<int>::cursor c = bt0.insert(bt0.root(), bt.root());    
-    validate_test_dataset1_tree(bt0.root());
-}
-
 BOOST_AUTO_TEST_CASE( copy_constructor_test )
 {
     binary_tree<int> bt0(bt);

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp	2009-01-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -75,6 +75,8 @@
 
     descending_cursor insert(descending_cursor c, value_type const& v)
     {
+        if (c.m_pos >= m_data.size())
+            m_data.resize(c.m_pos + 1);
         m_data[c.m_pos] = v;
         return c;
     }
@@ -123,14 +125,16 @@
 
     explicit fake_descending_binary_cursor(fake_binary_tree<T>& t, size_type p = 0)
     : m_tree(t), m_pos(p) {}
-
-//    explicit fake_descending_binary_cursor(fake_binary_tree<T> const& t, size_type p = 0)
-//    : m_tree(t), m_pos(p) {}
     
     fake_descending_binary_cursor(fake_descending_binary_cursor<T> const& other)
     : m_tree(other.m_tree), m_pos(other.m_pos) {}
 
-//    fake_descending_binary_cursor<T> operator=(fake_descending_binary_cursor<T> const&)
+    fake_descending_binary_cursor<T>& operator=(fake_descending_binary_cursor<T> const& other)
+    {
+        m_pos = other.m_pos;
+        return *this;
+    }
+    
 
     fake_binary_tree<T>& m_tree;
     typename fake_binary_tree<T>::size_type m_pos;

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-14 12:00:18 EST (Wed, 14 Jan 2009)
@@ -20,6 +20,7 @@
 #include <boost/test/test_case_template.hpp>
 
 #include "test_tree_traversal_data.hpp"
+#include "fake_binary_tree.hpp"
 
 using namespace boost::tree;
 
@@ -117,9 +118,45 @@
 
 BOOST_AUTO_TEST_SUITE_END()
 
-//BOOST_FIXTURE_TEST_SUITE(forest_fixture_test, fake_binary_tree_with_list_fixture<int>)
-//
-//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_tree<int, fake_binary_tree<int> > ft0(fbt1);
+    forest_tree<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_tree<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());
+}
+
+BOOST_AUTO_TEST_SUITE_END()
 
 //BOOST_FIXTURE_TEST_SUITE(forest_algorithms_test, test_binary_tree_with_list_fixture<int>)
 //