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

Subject: [Boost-commit] svn:boost r55514 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-08-10 20:29:33

Author: bernhard.reiter
Date: 2009-08-10 20:29:32 EDT (Mon, 10 Aug 2009)
New Revision: 55514
URL: http://svn.boost.org/trac/boost/changeset/55514

Log:
Change rotate semantics (and implementation semantics).
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp          |    12 ++++-----                               
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp   |    10 ++++++++                                
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp     |    48 +++++++++++++++++++-------------------- 
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp |     4 ++                                      
   4 files changed, 41 insertions(+), 33 deletions(-)

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-08-10 20:29:32 EDT (Mon, 10 Aug 2009)
@@ -195,7 +195,7 @@
         //m_node_alloc.construct(p_node, val);
         *p_node = node_type(val);
         
-        detail::attach(pos.base_node(), pos.base_node()->m_children[pos.m_pos], p_node, p_node->m_children[pos.m_pos]);
+        detail::attach(pos.base_node(), pos.the_node(), p_node, p_node->m_children[pos.m_pos]);
 
         // Readjust begin
 //        if ((pos == this->inorder_first()))
@@ -248,7 +248,7 @@
         if (!position.is_leaf()) {
             node_pointer pos_node = 
                 static_cast<node_pointer>(
-                    position.base_node()->m_children[position.m_pos]
+                    position.the_node()
                 );
 
             size_type parent_idx = index(position.parent());
@@ -274,7 +274,7 @@
         if (!position.is_leaf()) {
             node_pointer pos_node = 
                 static_cast<node_pointer>(
-                     position.base_node()->m_children[position.m_pos]
+                     position.the_node()
                 );
 
             // recurse
@@ -289,9 +289,7 @@
 public:
     void rotate(cursor& pos)
     {
-        //TODO: Take care of inorder_first pointer!
-        pos.m_pos = pos.base_node()->rotate(pos.m_pos);
-        pos.base_node() = static_cast<node_base_pointer>(pos.base_node()->m_parent->m_parent);
+        pos.m_pos = detail::rotate(pos.the_node(), pos.base_node(), pos.m_pos);
     }
     
     /**
@@ -382,7 +380,7 @@
     void splice(cursor position, binary_tree& x, cursor root)
     {
         // x isn't actually used currently...
-        detail::splice(position.base_node(), position.base_node()->m_children[position.m_pos], root.base_node()->m_children[position.m_pos]);
+        detail::splice(position.base_node(), position.the_node(), root.the_node());
     }
 
     /**

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-10 20:29:32 EDT (Mon, 10 Aug 2009)
@@ -217,6 +217,16 @@
         return this->base_reference();
     }
 
+    typename node_type::node_with_children_base* const& the_node() const
+    {
+        return this->base_reference()->m_children[m_pos];
+    }
+
+    typename node_type::node_with_children_base*& the_node()
+    {
+        return this->base_reference()->m_children[m_pos];
+    }
+
 //    /** 
 //     * Detaches the node this cursor points to and returns a pointer to it;
 //     * this cursor will be set to its inorder successor afterwards (?)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp	(original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp	2009-08-10 20:29:32 EDT (Mon, 10 Aug 2009)
@@ -100,30 +100,6 @@
     node_base(node_with_parent_base* p)
     : node_with_parent_base(p), node_with_children_base() {}
     
-    // Binary specific
-    
-    children_type::size_type rotate(children_type::size_type const& c)
-    {
-        //TODO: Optimise.
-        base_pointer q = static_cast<node_base*>(m_children[c]);
-        
-        base_pointer B = static_cast<node_base*>(m_children[c]->m_children[(c ? 0 : 1)]);
-        //pre_rotate();
-        
-        //B swaps places with its m_parent:
-
-        m_children[c] = B;
-        B->m_parent = this;
-        q->m_parent = this->m_parent;
-
-        children_type::size_type qp = get_index();
-        static_cast<base_pointer>(q->m_parent)->m_children[qp] = q;
-        this->m_parent = q;
-        q->m_children[(c ? 0 : 1)] = this;
-        return qp;
-        //return (c ? 0 : 1);
-    }
-    
     base_pointer detach(children_type::size_type m_pos)
     {
         node_with_children_base::children_type::size_type parent_idx = get_index();
@@ -142,9 +118,31 @@
     {
         return (static_cast<base_pointer>(this->m_parent)->m_children[0] == this ? 0 : 1);
     }
-    
 };
 
+node_with_children_base::children_type::size_type rotate(node_with_children_base*& child, node_base* me, node_with_children_base::children_type::size_type const& c)
+{
+    //TODO: Optimise.
+    typedef node_base* base_pointer;
+    base_pointer q = static_cast<node_base*>(child);
+    
+    base_pointer B = static_cast<node_base*>(child->m_children[(c ? 0 : 1)]);
+    //pre_rotate();
+    
+    //B swaps places with its m_parent:
+
+    child = B;
+    B->m_parent = parent;
+    q->m_parent = parent->m_parent;
+
+    node_with_children_base::children_type::size_type qp = parent->get_index();
+    static_cast<base_pointer>(q->m_parent)->m_children[qp] = q;
+    parent->m_parent = q;
+    q->m_children[(c ? 0 : 1)] = parent;
+    return qp;
+    //return (c ? 0 : 1);
+}
+
 void attach(node_base* parent, node_with_children_base*& parent_child, node_base* child, node_with_children_base*& child_child)
 {
     attach(static_cast<node_with_parent_base*>(child), static_cast<node_with_parent_base*>(parent));

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-10 20:29:32 EDT (Mon, 10 Aug 2009)
@@ -405,6 +405,7 @@
     BOOST_CHECK_EQUAL(*c.begin(), 6);
         
     bt.rotate(c); // Left rotate
+    c.to_parent().to_parent();
 
     BOOST_CHECK_EQUAL(*c.begin(), 6);
     BOOST_CHECK_EQUAL(*c.parent().begin(), 8);
@@ -419,7 +420,8 @@
     BOOST_CHECK_EQUAL(*c.begin(), 3);
     
     bt.rotate(c); // Right rotate
-    
+    c.to_parent().to_parent();
+
     BOOST_CHECK_EQUAL(*c.begin(), 3);
     c = c.end();