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