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

Subject: [Boost-commit] svn:boost r55575 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail boost/tree/detail/balancers libs/tree/test
From: ockham_at_[hidden]
Date: 2009-08-13 18:41:09

Author: bernhard.reiter
Date: 2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
New Revision: 55575
URL: http://svn.boost.org/trac/boost/changeset/55575

Log:
Some work on balance (and related).
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp                         |   111 +++++++++------------------------------ 
   sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp                  |     5 -                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmented_iterator.hpp       |     6 +-                                      
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp          |     5 -                                       
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp              |     9 +-                                      
   sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2                      |     4                                         
   sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp       |    19 ++++++                                  
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp            |    18 ++++++                                  
   sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp                  |    11 +--                                     
   sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp |    40 ++++++++-----                           
   10 files changed, 106 insertions(+), 122 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -31,9 +31,6 @@
 namespace boost {
 namespace tree {
 
-using detail::ascending_node;
-using detail::ascending_nary_cursor;
-
 using detail::augmented_iterator;
 
 using boost::multi_index::member;
@@ -80,68 +77,23 @@
     typedef typename augmented_type<Val,Meta,Meta2>::metadata_type type;
 };
 
-
-template <class Cursor>
+template <class Cursor> 
 class is_on_top_cursor
-: public Cursor {
+: public cursor_adaptor<is_on_top_cursor<Cursor>, Cursor>
+{
 public:
     is_on_top_cursor()
-    : Cursor() {}
+    : is_on_top_cursor::cursor_adaptor_() {}
 
     is_on_top_cursor(Cursor p)
-    : Cursor(p) {}
+    : is_on_top_cursor::cursor_adaptor_(p) {}
     
     bool is_root() const
     {
-        return this->is_on_top();
+        return this->base_reference().is_on_top();
     }
 };
 
-//template <class Cursor> 
-//class is_on_top_cursor
-//: public cursor_adaptor<is_on_top_cursor<Cursor>
-//      , Cursor
-//      , boost::use_default
-//      , bidirectional_traversal_tag
-//      , bidirectional_traversal_tag
-//    > {
-//private:
-//    struct enabler {};
-//
-//public:
-//     //TODO: Tidy up typedefs
-//
-//    typedef Cursor base_cursor;
-//    
-//     typedef is_on_top_cursor<Cursor> cursor;
-//     typedef is_on_top_cursor<Cursor const> const_cursor; //FIXME (?)
-//
-//    //typedef typename cursor_size<base_cursor>::type size_type;
-//
-//    //typedef bidirectional_traversal_tag cursor_category;
-//        
-//    // Container-specific:
-//    typedef cursor iterator;  // For (range) concepts' sake, mainly
-////    typedef const_cursor const_iterator;
-//    
-//     // Common iterator facade stuff
-//    is_on_top_cursor()
-//     : is_on_top_cursor::cursor_adaptor_() {}
-//
-//    explicit is_on_top_cursor(base_cursor p)
-//     : is_on_top_cursor::cursor_adaptor_(p) {}
-//    
-//private:
-//    friend class cursor_core_access;
-//    friend class iterator_core_access;
-//
-//public:
-//    bool is_root() const
-//    {
-//        return this->base_reference().is_on_top();
-//    }
-//};
-
 template <class Cursor>
 typename is_on_top_cursor<Cursor>::size_type
 index(is_on_top_cursor<Cursor> const& cur)
@@ -149,22 +101,6 @@
     return cur.index();
 }
 
-template <class Cursor>
-class balance_iterator
-: public iterator<inorder, is_on_top_cursor<Cursor> > {
-public:
-    balance_iterator()
-    : iterator<inorder, is_on_top_cursor<Cursor> >() {}
-    
-    explicit balance_iterator(Cursor p)
-    : iterator<inorder, is_on_top_cursor<Cursor> >(p) {}
-    
-    operator Cursor()
-    {
-        return Cursor(this->base());
-    }
-}; 
-
 /** 
  * @brief A %balance.
  * This class models the hierarchy concept, the container concept and the
@@ -192,9 +128,9 @@
     typedef typename hierarchy_type::cursor cursor;
     typedef typename hierarchy_type::const_cursor const_cursor;
 
- public:    
-    typedef augmented_iterator<balance_iterator<cursor>, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
-    typedef augmented_iterator<balance_iterator<const_cursor>, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
+public:    
+    typedef augmented_iterator<boost::tree::iterator<inorder, is_on_top_cursor<cursor> >, typename data_type::extract_data, bidirectional_traversal_tag> iterator;
+    typedef augmented_iterator<boost::tree::iterator<inorder, is_on_top_cursor<const_cursor> >, typename data_type::extract_data, bidirectional_traversal_tag> const_iterator;
     
     typedef std::reverse_iterator<iterator> reverse_iterator;
     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
@@ -211,14 +147,17 @@
     
     // TODO: 3rd arg...?
     explicit balance (size_type n, value_type const& value = value_type(), 
-        hierarchy_type const& hier = hierarchy_type())
+                      hierarchy_type const& hier = hierarchy_type())
     : h(hier)
-    {}
+    {
+        for (n; n!=0; --n)
+            this->insert(this->end(), value);
+    }
 
     template <class InputIterator>
-        balance (InputIterator first, InputIterator last, 
-            hierarchy_type const& hier = hierarchy_type())
-            : h(hier)
+    balance (InputIterator first, InputIterator last, 
+             hierarchy_type const& hier = hierarchy_type())
+    : h(hier)
     {
         while (first++ != last)
             this->insert(this->end(), *first);
@@ -243,8 +182,10 @@
      */      
     iterator begin()
     {
-        return iterator(first(inorder(), h.root()));
-
+        cursor c = h.root();
+        to_first(inorder(), c);
+        return iterator(c);
+        //return iterator(first(inorder(), h.root()));
     }
     
     /**
@@ -260,7 +201,10 @@
      */      
     const_iterator cbegin() const
     {
-        return const_iterator(h.inorder_cfirst());
+        const_cursor c = h.root();
+        to_first(inorder(), c);
+        return const_iterator(c);
+        //return const_iterator(h.inorder_cfirst());
     }
 
     /**
@@ -492,9 +436,8 @@
         // Do balancers have to work for non-leaf newly inserted elements?
         // If yes, we could just insert at pos.
         
-        cursor c = pos.base().base();
-        while (!c.is_leaf())
-            c = c.end();
+        cursor c = pos.base().base().base();
+        to_rightmost(c);
         
         c = h.insert(c, data_type(val));
         

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -139,10 +139,9 @@
     typedef typename cursor_facade_::difference_type difference_type;
     typedef typename cursor_facade_::size_type size_type;
  
-//    cursor_adaptor() {}
+    cursor_adaptor() {}
     
-    explicit cursor_adaptor(Base const& cur) : m_cursor(cur)
-    { }
+    explicit cursor_adaptor(Base const& cur) : m_cursor(cur) {}
     
     Base const& base() const
     { return m_cursor; }

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmented_iterator.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmented_iterator.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/augmented_iterator.hpp	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -47,13 +47,13 @@
     struct enabler {};
  public:
     augmented_iterator()
-      : augmented_iterator::iterator_adaptor_() {}
+    : augmented_iterator::iterator_adaptor_() {}
 
     explicit augmented_iterator(InorderIter p)
-      : augmented_iterator::iterator_adaptor_(p) {}
+    : augmented_iterator::iterator_adaptor_(p) {}
 
     explicit augmented_iterator(typename InorderIter::base_type c)
-      : augmented_iterator::iterator_adaptor_(InorderIter(c)) {}
+    : augmented_iterator::iterator_adaptor_(InorderIter(c)) {}
 
     template <class OtherInorderIter>
     augmented_iterator(

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -40,7 +40,6 @@
     int m_priority;
 };
 
-
 class treap {
  public:
     typedef treap_metadata metadata_type;
@@ -50,12 +49,12 @@
     {
         int priority = x->metadata().get_priority();
         
-        x = x.parent();
+        x.to_parent();
         while ((x != t.root()) && (priority > x->metadata().get_priority())) {
             t.rotate(x);
             priority = x->metadata().get_priority();
         }
-        x = x.begin();
+        x.to_begin();
     }
       
     template <class Tree>

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -92,7 +92,7 @@
     ascending_nary_cursor(
         ascending_nary_cursor<OtherNode> const& other
       , typename boost::enable_if<
-            boost::is_convertible<OtherNode*, node_type*>
+            boost::is_convertible<typename OtherNode::value_type*, value_type*>
           , enabler
         >::type = enabler()
     )
@@ -190,17 +190,18 @@
         //this->base_reference() = this->base_reference()->parent();
     }
     
-protected:
+//protected:
+public:
     bool is_on_top() const
     {
         node_base_type* parent_begin_node = 
+            static_cast<node_base_type*>(
             static_cast<node_base_type*>(this->base_reference()->parent())
-            ->m_children[this->base_reference()->get_index()];
+            ->m_children[this->base_reference()->get_index()]);
         return (!m_pos && (this->base_reference() != parent_begin_node));
         // (*this != this->parent().begin())
     }
 
-public:
     node_base_type* const& parent_node() const
     {
         return this->base_reference();

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/Jamfile.v2	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -44,10 +44,10 @@
         [ run cursor_algorithm_test.cpp ]
         [ run iterator_algorithm_test.cpp ]
 #	[ run red_black_tree_test.cpp ]
-#	[ run treap_test.cpp ]
+	[ run treap_test.cpp ]
         [ run forest_test.cpp ]
 #	[ run nary_tree_test.cpp ]
         [ run multiway_tree_test.cpp ]
-#	[ run unbalanced_binary_tree_test.cpp ]
+	[ run unbalanced_binary_tree_test.cpp ]
         [ run graph_test.cpp ]
         ;

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/ascending_cursor_test.cpp	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -15,6 +15,25 @@
 
 BOOST_FIXTURE_TEST_SUITE( ascending_cursor_test, fake_binary_tree_fixture<int> )
 
+BOOST_AUTO_TEST_CASE( test_ascending_cursor_constructors )
+{
+    typedef fake_binary_tree<int>::descending_cursor dc_t;
+    typedef fake_binary_tree<int>::const_descending_cursor cdc_t;
+
+    ascending_cursor<dc_t> ac1;
+    ascending_cursor<dc_t> ac2(ac1);
+    
+    BOOST_CHECK(ac1 == ac2);
+    
+    ascending_cursor<cdc_t> cac1;
+    ascending_cursor<cdc_t> cac2(cac1);
+
+    BOOST_CHECK(cac1 == cac2);
+
+    ascending_cursor<cdc_t> cac3(ac1);
+    BOOST_CHECK(cac3 == ac1);
+}
+
 BOOST_AUTO_TEST_CASE( test_ascending_cursor )
 {
     typedef fake_binary_tree<int>::descending_cursor dc_t;

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-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -22,7 +22,7 @@
 {
     binary_tree<int> bt0;
     BOOST_CHECK(bt0.root().is_leaf());
-    
+
 //    binary_tree<int>::node_base_type::descending_node_base** x = bt0.m_header.m_children.data();
 //    BOOST_CHECK_EQUAL(++x, &bt0.m_header.m_children.data()[1]);
 
@@ -30,6 +30,22 @@
     // test with allocator? 
 }
 
+BOOST_AUTO_TEST_CASE( cursor_test )
+{
+    binary_tree<int>::cursor c1;
+    binary_tree<int>::cursor c2(c1);
+
+    BOOST_CHECK(c1 == c2);
+
+    binary_tree<int>::const_cursor cc1;
+    binary_tree<int>::const_cursor cc2(cc1);
+
+    BOOST_CHECK(cc1 == cc2);
+
+    //binary_tree<int>::const_cursor cc3(c1);
+    //BOOST_CHECK(cc3 == c1);
+}
+
 BOOST_AUTO_TEST_CASE( insert_value_test )
 {
     binary_tree<int> bt0;

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -16,8 +16,7 @@
 //#define BOOST_TEST_DYN_LINK
 #include <boost/test/included/unit_test.hpp>
 
-//TODO: Make this a test suite.
-
+//TODO: Use a mock_binary_tree
 BOOST_AUTO_TEST_CASE( treap_test )
 {
     using namespace boost::tree;
@@ -28,19 +27,19 @@
     typedef balance<binary_tree<int>, balancers::treap> treap_t;
     
     //searcher_t my_searcher;
-    treap_t my_balancer;
+    treap_t my_balance;
     //tree_t my_tree;
     
     //create_test_data_searcher(my_searcher);
-    create_test_data_sequence(my_balancer);
+    //create_test_data_sequence(my_balancer);
     //create_test_data_sequence(my_vector);
 
 //    Segfaults:    
 //    BOOST_CHECK(std::equal(my_balancer.begin(), my_balancer.end(), my_vector.begin()));
 
     //TODO: More tests?
-    for (treap_t::iterator ci = my_balancer.begin(); ci != my_balancer.end(); ++ci) {
-        treap_t::hierarchy_type::cursor c = ci.base().base();
+    for (treap_t::iterator ci = my_balance.begin(); ci != my_balance.end(); ++ci) {
+        treap_t::hierarchy_type::cursor c = ci.base().base().base();
 //        int priority = c->metadata().get_priority(); // FIXME: Segfaults!
 //        if (!c.is_leaf()) {
 //            BOOST_CHECK(priority

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp	(original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/unbalanced_binary_tree_test.cpp	2009-08-13 18:41:08 EDT (Thu, 13 Aug 2009)
@@ -8,21 +8,40 @@
 #include <boost/tree/detail/balancers/unbalanced.hpp>
 #include <boost/tree/binary_tree.hpp>
 
-
-
 #define BOOST_TEST_MODULE unbalanced_binary_tree test
 //#define BOOST_TEST_DYN_LINK
 #include <boost/test/included/unit_test.hpp>
 
+// TODO: Use a mock_binary_tree.
+BOOST_AUTO_TEST_CASE( unbalanced_binary_tree_constructors_test )
+{
+    using namespace boost::tree;
+    typedef binary_tree<int> tree_t;
+    typedef balance<tree_t, balancers::unbalanced> balance_t;
+    balance_t t1;
+    
+    balance_t t2(t1);
+}
+
+BOOST_AUTO_TEST_CASE( unbalanced_binary_tree_iterator_test )
+{
+    using namespace boost::tree;
+    typedef binary_tree<int> tree_t;
+    typedef balance<tree_t, balancers::unbalanced> balance_t;
+    
+    balance_t::iterator it1;
+    balance_t::iterator it2(it1);
+}
+
 BOOST_AUTO_TEST_CASE( unbalanced_binary_tree_test )
 {
     using namespace boost::tree;
     
     typedef binary_tree<int> tree_t;
-    typedef balance<tree_t, balancers::unbalanced> balancer_t;
-    balancer_t my_tree; 
+    typedef balance<tree_t, balancers::unbalanced> balance_t;
+    balance_t my_tree; 
     
-    balancer_t::iterator c, c1, c2, c3, c4, c5;
+    balance_t::iterator c, c1, c2, c3, c4, c5;
 
     c = my_tree.end();
     BOOST_CHECK(c == my_tree.end());
@@ -66,14 +85,3 @@
     BOOST_CHECK_EQUAL(*c, 7);
     
 }
-
-//boost::unit_test::test_suite*
-//init_unit_test_suite( int argc, char* argv[] )
-//{
-//    boost::unit_test::test_suite* key_search_test = 
-//            BOOST_TEST_SUITE( "Key search binary vector test" );
-//
-//    key_search_test->add( BOOST_TEST_CASE( &key_search_binary_balancer_test ) );
-//
-//    return key_search_test;
-//}