Subject: [Boost-commit] svn:boost r54468 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-06-28 11:30:42
Author: bernhard.reiter
Date: 2009-06-28 11:30:41 EDT (Sun, 28 Jun 2009)
New Revision: 54468
URL: http://svn.boost.org/trac/boost/changeset/54468
Log:
Towards new erase semantics. inorder_erase -> erase
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 75 +++++----------------------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 14 +++---
3 files changed, 20 insertions(+), 73 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-06-28 11:30:41 EDT (Sun, 28 Jun 2009)
@@ -522,8 +522,8 @@
cursor c = position.base().base();
cursor d = balancer_type::remove(h, c);
// if (c == d)
- return iterator(h.inorder_erase(c));
-// return iterator(h.inorder_erase(d,c));
+ return iterator(h.erase(c));
+// return iterator(h.erase(d,c));
}
/**
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-06-28 11:30:41 EDT (Sun, 28 Jun 2009)
@@ -428,87 +428,34 @@
}
/**
- * @brief Erases the value of the given cursor, keeping the binary_tree's
- * inorder, and returns the given cursor's inorder successor.
+ * @brief Erases the value of the given cursor.
* @param position Cursor that is empty or at least one of whose children is
- * @return The inorder successor of position
+ *
*/
- cursor inorder_erase(cursor position)
+ cursor erase(cursor position)
{
node_pointer parent_node
= static_cast<node_pointer>(position.parent().base_node());
- size_type idx = index(position.parent());
+ size_type idx = index(position);
+ size_type parent_idx = index(position.parent());
node_pointer p_node = static_cast<node_pointer>(position.base_node());
- cursor orig_pos = position;
- ++position;
-
- if (position.is_leaf()) {
- if (!orig_pos.is_leaf()) { // Set child's parent only if there _is_ a child
- static_cast<node_base_pointer>(p_node->m_children[0])->m_parent
- = parent_node;
- }
- parent_node->m_children[idx] = p_node->m_children[0];
-
- // to_leftmost_parent(position);
- while (index(position))
- position = position.parent();
- } else {
- position.to_begin();
- position.base_node()->m_parent = parent_node;
- parent_node->m_children[idx] = position.base_node();
-
- to_leftmost(position);
+
+ if (!position.is_leaf()) { // Set child's parent only if there _is_ a child
+ static_cast<node_base_pointer>(p_node->m_children[idx])->m_parent
+ = parent_node;
}
+ parent_node->m_children[parent_idx] = p_node->m_children[idx];
m_node_alloc.destroy(p_node);
m_node_alloc.deallocate(p_node, 1);
- return position;
+ return cursor(static_cast<node_base_pointer>(parent_node->m_children[parent_idx]),idx);
}
- cursor inorder_erase(cursor position, cursor descendant)
- {
- node_pointer p_node = static_cast<node_pointer>(descendant.base_node());
- ++descendant;
-
- if (descendant.is_leaf()) {
- (*p_node)[0]->m_parent = p_node->m_parent;
- static_cast<node_base_pointer>(p_node->m_parent)
- ->node_base_type::operator[](0) = (*p_node)[0];
- } else {
- descendant = descendant.begin();
- descendant.base_node()->m_parent = p_node->m_parent;
- static_cast<node_base_pointer>(p_node->m_parent)
- ->node_base_type::operator[](1) = descendant.base_node();
- }
-
- cursor pos_parent = position.parent();
- pos_parent.base_node()->node_base_type::operator[](pos_parent.m_pos)
- = descendant.base_node();
- descendant.base_node()->m_parent = pos_parent.base_node();
- descendant.base_node()->node_base_type::operator[](0)
- = position.base_node()->node_base_type::operator[](0);
- descendant.base_node()->node_base_type::operator[](1)
- = position.base_node()->node_base_type::operator[](1);
- descendant.base_node()->node_base_type::operator[](0)->m_parent
- = descendant.base_node();
- descendant.base_node()->node_base_type::operator[](1)->m_parent
- = descendant.base_node();
-
- p_node =
- static_cast<node_pointer>(position.base_node()->node_base_type::operator[](position.m_pos));
-
- m_node_alloc.destroy(p_node);
- m_node_alloc.deallocate(p_node, 1);
-
- return descendant;
- }
-
private:
node_base_type m_header;
-
node_allocator_type m_node_alloc;
};
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-06-28 11:30:41 EDT (Sun, 28 Jun 2009)
@@ -171,7 +171,7 @@
}
-BOOST_AUTO_TEST_CASE( inorder_erase_non_leaf_node_test )
+BOOST_AUTO_TEST_CASE( erase_non_leaf_node_test )
{
binary_tree<int>::cursor c = bt.root().end().begin();
BOOST_CHECK_EQUAL(*c, 10);
@@ -179,16 +179,16 @@
// Left child empty
BOOST_CHECK(c.is_leaf());
BOOST_CHECK(!(++c).is_leaf());
- --c;
+ //--c;
binary_tree<int>::size_type sz = size(bt.root());
- c = bt.inorder_erase(c);
+ c = bt.erase(c);
BOOST_CHECK_EQUAL(--sz, size(bt.root()));
- BOOST_CHECK_EQUAL(*c, 11);
+ BOOST_CHECK_EQUAL(*c, 14);
}
-BOOST_AUTO_TEST_CASE( inorder_erase_leaf_node_test )
+BOOST_AUTO_TEST_CASE( erase_leaf_node_test )
{
binary_tree<int>::cursor c = bt.root().end().end().begin().begin().end().begin();
BOOST_CHECK_EQUAL(*c, 12);
@@ -199,10 +199,10 @@
--c;
binary_tree<int>::size_type sz = size(bt.root());
- c = bt.inorder_erase(c);
+ c = bt.erase(c);
BOOST_CHECK_EQUAL(--sz, size(bt.root()));
- BOOST_CHECK_EQUAL(*c, 13);
+ //BOOST_CHECK(c == );
}
BOOST_AUTO_TEST_CASE( clear_test )