Boost logo

Boost-Commit :

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();
 


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk