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

Subject: [Boost-commit] svn:boost r50505 - in sandbox/SOC/2006/tree/trunk: . boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-07 15:57:06

Author: bernhard.reiter
Date: 2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
New Revision: 50505
URL: http://svn.boost.org/trac/boost/changeset/50505

Log:
Add checks for leaf nodes.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/TODO                                        |     6 ++-                                     
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp                       |    44 ++++++++++++++--------------            
   sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp                |     9 ++---                                   
   sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp                |     6 +--                                     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp         |    61 ++++++++++++++++++++++++++++++++++----- 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp       |    33 +++++++++------------                   
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp |    22 +++++++++++---                          
   7 files changed, 115 insertions(+), 66 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO	(original)
+++ sandbox/SOC/2006/tree/trunk/TODO	2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -15,7 +15,6 @@
 
 General:
 * preorder_insert_cursor: hopefully easy to implement...
-* Fix insert cursor (test) to work with fake_binary_tree
 * 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!
@@ -131,8 +130,11 @@
   the STL's linear algorithms should there be a hierarchical version?
 
 Pre-release:
+* Look into 
+  * boost/graph/tree_traits.hpp
+  * Matt Austern's segmented iterators paper (maybe relevant for level order algos).
 * Make directory structure reflect namespaces and vice versa.
-* Cleanup headers/ #include dependencies.
+* Cleanup headers/ #include dependencies, whitespace, indentation.
 * Run Boost Inspect.
 
 Future: 

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor.hpp	2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -89,28 +89,28 @@
 };
 
 // Deprecate?
-struct cursor_tag {};
-
-struct descending_tag {}; 
-struct descending_cursor_tag
-    : public cursor_tag, public descending_tag, 
-      public input_iterator_tag, public output_iterator_tag {};
-struct descending_forward_cursor_tag
-    : public cursor_tag, public descending_tag, public forward_iterator_tag {};
-struct descending_bidirectional_cursor_tag
-    : public cursor_tag, public descending_tag, public bidirectional_iterator_tag {};
-struct descending_random_access_cursor_tag
-    : public cursor_tag, public descending_tag, public random_access_iterator_tag {};
-
-struct ascending_tag {};
-struct ascending_cursor_tag
-    : public descending_cursor_tag, public ascending_tag {};
-struct ascending_forward_cursor_tag
-    : public descending_forward_cursor_tag, public ascending_tag {};
-struct ascending_bidirectional_cursor_tag
-    : public descending_bidirectional_cursor_tag, public ascending_tag {};
-struct ascending_random_access_cursor_tag
-    : public descending_random_access_cursor_tag, public ascending_tag {};
+//struct cursor_tag {};
+//
+//struct descending_tag {}; 
+//struct descending_cursor_tag
+//    : public cursor_tag, public descending_tag, 
+//      public input_iterator_tag, public output_iterator_tag {};
+//struct descending_forward_cursor_tag
+//    : public cursor_tag, public descending_tag, public forward_iterator_tag {};
+//struct descending_bidirectional_cursor_tag
+//    : public cursor_tag, public descending_tag, public bidirectional_iterator_tag {};
+//struct descending_random_access_cursor_tag
+//    : public cursor_tag, public descending_tag, public random_access_iterator_tag {};
+//
+//struct ascending_tag {};
+//struct ascending_cursor_tag
+//    : public descending_cursor_tag, public ascending_tag {};
+//struct ascending_forward_cursor_tag
+//    : public descending_forward_cursor_tag, public ascending_tag {};
+//struct ascending_bidirectional_cursor_tag
+//    : public descending_bidirectional_cursor_tag, public ascending_tag {};
+//struct ascending_random_access_cursor_tag
+//    : public descending_random_access_cursor_tag, public ascending_tag {};
 
 /*
 template <class Hor, class Vert>

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp	2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -41,7 +41,6 @@
  * in saving keystrokes.
  */
 // TODO: Complete this.
-// Shouldn't we be using cursor_facade?
 template <class Tr>
 class insert_cursor
 : public cursor_adaptor<insert_cursor<Tr>
@@ -81,9 +80,9 @@
 
     typename insert_cursor::cursor_adaptor_::reference dereference() const
     {
-        if (index(this->base_reference())) {
-            const_cast<typename Tr::cursor&>(this->base_reference())
-            = tree.insert(this->base_reference(), typename Tr::value_type());
+        if (this->base_reference().index()) { // FIXME: use freestanding index!
+            //const_cast<typename Tr::cursor&>(this->base_reference()) =
+            tree.insert(this->base_reference(), typename Tr::value_type());
             const_cast<typename Tr::cursor&>(this->base_reference()).to_begin();
         }
         return *this->base_reference();
@@ -92,7 +91,7 @@
     void left()
     {
         if (this->base_reference().empty())
-            this->base_reference() = 
+//            this->base_reference() = 
                 tree.insert(this->base_reference(), typename Tr::value_type());
         this->base_reference().to_begin();
     }

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/tree_concepts.hpp	2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -25,14 +25,12 @@
 
     BOOST_CONCEPT_USAGE(Tree)
     {
-        c = t.root();
-        cc = t.root();
+        cursor c = t.root();
+        const_cursor cc = t.root(); // FIXME
     }
     
 private:
     X t;
-    cursor c;
-    const_cursor cc;
     
 };
 

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-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -26,8 +26,18 @@
 /// See http://en.wikipedia.org/wiki/Binary_Tree#Methods_for_storing_binary_trees
 template <class T>
 struct fake_binary_tree {
+    typedef std::vector<T> children_type;
+    typedef typename children_type::size_type size_type;
+    typedef typename children_type::value_type value_type;
+    typedef typename children_type::difference_type difference_type;
+    typedef typename children_type::pointer pointer;
+    typedef typename children_type::reference reference;
+
     typedef fake_descending_binary_cursor<T> descending_cursor;
-    typedef fake_descending_binary_cursor<T const> const_descending_cursor;
+    typedef fake_descending_binary_cursor<T/* const*/> const_descending_cursor; //FIXME
+
+    typedef descending_cursor cursor;
+    typedef const_descending_cursor const_cursor;
 
     typedef fake_ascending_binary_cursor<T> ascending_cursor;
     typedef fake_ascending_binary_cursor<T const> const_ascending_cursor;
@@ -35,7 +45,7 @@
     typedef fake_root_tracking_binary_cursor<T> root_tracking_cursor;
     typedef fake_root_tracking_binary_cursor<T const> const_root_tracking_cursor;
         
-    fake_binary_tree(typename std::vector<T>::size_type s) : m_data(s)
+    fake_binary_tree(typename std::vector<T>::size_type s = 0) : m_data(s)
     { }
     
     descending_cursor descending_root()
@@ -43,6 +53,16 @@
         return descending_cursor(*this, 0);
     }
 
+    descending_cursor root()
+    {
+        return descending_cursor(*this, 0);
+    }
+
+    const_descending_cursor root() const
+    {
+        return const_descending_cursor(*this, 0);
+    }
+
     ascending_cursor ascending_root()
     {
         return ascending_cursor(*this, 0);
@@ -53,12 +73,23 @@
         return root_tracking_cursor(*this, 0);
     }
 
-    typedef std::vector<T> children_type;
-    typedef typename children_type::size_type size_type;
-    typedef typename children_type::value_type value_type;
-    typedef typename children_type::difference_type difference_type;
-    typedef typename children_type::pointer pointer;
-    typedef typename children_type::reference reference;
+    descending_cursor insert(descending_cursor c, value_type const& v)
+    {
+        m_data[c.m_pos] = v;
+        return c;
+    }
+
+//    ascending_cursor insert(ascending_cursor c, value_type const& v)
+//    {
+//        m_data[c.m_pos] = v;
+//        return c;
+//    }
+//
+//    root_tracking_cursor insert(root_tracking_cursor c, value_type const& v)
+//    {
+//        m_data[c.m_pos] = v;
+//        return c;
+//    }
     
     children_type m_data;  
 };
@@ -86,16 +117,21 @@
 {
 public:
     typedef fake_descending_binary_cursor<T>cursor;
-    typedef fake_descending_binary_cursor<T const> const_cursor;
+    typedef fake_descending_binary_cursor<T/* const*/> const_cursor;
 
     typedef typename fake_descending_binary_cursor<T>::cursor_facade_::size_type size_type;
 
     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_binary_tree<T>& m_tree;
     typename fake_binary_tree<T>::size_type m_pos;
 
@@ -153,6 +189,13 @@
 };        
 
 template <class T>
+typename fake_descending_binary_cursor<T>::size_type
+index(fake_descending_binary_cursor<T> const& cur)
+{
+    return cur.index();
+}
+
+template <class T>
 struct fake_ascending_binary_cursor
 : public boost::tree::cursor_adaptor<fake_ascending_binary_cursor<T>
                                    , fake_descending_binary_cursor<T>

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/insert_cursor_test.cpp	2009-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -23,9 +23,6 @@
 
 using namespace boost::tree;
 
-BOOST_FIXTURE_TEST_SUITE(insert_cursor_test, test_binary_tree_fixture<int>)
-
-
 template <class Cursor>
 void fill_subtree_with_data(Cursor cur)
 {
@@ -125,47 +122,45 @@
     *c8 = 8;
 }
 
+BOOST_FIXTURE_TEST_SUITE(insert_cursor_test, fake_binary_tree_fixture<int>)
+
 BOOST_AUTO_TEST_CASE ( test_desc_copy_using_insert_cursor_preorder )
 {
-    bt2.clear();
-    fill_subtree_with_data_in_preorder(tree_inserter(bt2, bt2.root()));
+    fill_subtree_with_data_in_preorder(tree_inserter(fbt2, fbt2.descending_root()));
 
-    validate_test_dataset1_tree(bt2.root());
+    validate_test_dataset1_tree(fbt2.descending_root());
 }
 
 BOOST_AUTO_TEST_CASE ( test_desc_copy_using_insert_cursor_inorder )
 {
-    bt2.clear();
-    fill_subtree_with_data_in_inorder(tree_inserter(bt2, bt2.root()));
+    fill_subtree_with_data_in_inorder(tree_inserter(fbt2, fbt2.descending_root()));
 
-    validate_test_dataset1_tree(bt2.root());
+    validate_test_dataset1_tree(fbt2.descending_root());
 }
 
 BOOST_AUTO_TEST_CASE ( test_desc_copy_using_insert_cursor_postorder )
 {
-    bt2.clear();
-    fill_subtree_with_data_in_postorder(tree_inserter(bt2, bt2.root()));
+    fill_subtree_with_data_in_postorder(tree_inserter(fbt2, fbt2.descending_root()));
 
-    validate_test_dataset1_tree(bt2.root());
+    validate_test_dataset1_tree(fbt2.descending_root());
 }
 
 BOOST_AUTO_TEST_CASE ( test_desc_copy_using_insert_cursor )
 {
-    bt2.clear();
-    fill_subtree_with_data(tree_inserter(bt2, bt2.root()));
+    fill_subtree_with_data(tree_inserter(fbt2, fbt2.descending_root()));
 
-    validate_test_dataset1_tree(bt2.root());
+    validate_test_dataset1_tree(fbt2.descending_root());
 }
 
 //BOOST_AUTO_TEST_CASE_TEMPLATE ( test_asc_copy_using_insert_cursor, Order, orders )
 //{    
-//    bt2.clear();
+//    fbt2.clear();
 //        
-//    boost::tree::copy(Order(), bt.root(), tree_inserter(bt2, bt2.root())
+//    boost::tree::copy(Order(), bt.root(), tree_inserter(fbt2, fbt2.root())
 //                    , boost::tree::ascending_vertical_traversal_tag());
 //
-//    validate_test_dataset1_tree(bt2.root());
-//    BOOST_CHECK_EQUAL(size(bt2.root()), size(bt.root())); 
+//    validate_test_dataset1_tree(fbt2.root());
+//    BOOST_CHECK_EQUAL(size(fbt2.root()), size(bt.root())); 
 //}
 
 BOOST_AUTO_TEST_SUITE_END()
\ No newline at end of file

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-01-07 15:57:05 EST (Wed, 07 Jan 2009)
@@ -63,15 +63,27 @@
     {
         BOOST_CHECK_EQUAL(*cur.begin(), 8);
         BOOST_CHECK_EQUAL(*cur.begin().begin(), 3);
-        BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 1);  //Leaf
+        BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 1);
+        BOOST_CHECK(cur.begin().begin().end().empty());
+        BOOST_CHECK(cur.begin().begin().begin().empty()); //Leaf
+        
         BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 6);
-        BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4); //Leaf
-        BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7); //Leaf
+        BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4);
+        BOOST_CHECK(cur.begin().end().begin().begin().empty()); //Leaf
+
+        BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7);
+        BOOST_CHECK(cur.begin().end().end().begin().empty()); //Leaf
+
         BOOST_CHECK_EQUAL(*cur.end().begin(), 10);
+        BOOST_CHECK(cur.end().begin().empty());
         BOOST_CHECK_EQUAL(*cur.end().end().begin(), 14);
+        BOOST_CHECK(cur.end().end().end().empty());
         BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 13);
-        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 11); 
-        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 12); //Leaf
+        BOOST_CHECK(cur.end().end().begin().end().empty());
+        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 11);
+        BOOST_CHECK(cur.end().end().begin().begin().begin().empty()); 
+        BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 12);
+        BOOST_CHECK(cur.end().end().begin().begin().end().begin().empty()); //Leaf
     }
 
     static void validate_test_dataset1_minus_1_tree(typename boost::tree::binary_tree<T>::const_cursor cur)