Subject: [Boost-commit] svn:boost r54590 - in sandbox/SOC/2006/tree/trunk: boost/tree libs/tree/test
From: ockham_at_[hidden]
Date: 2009-07-02 07:06:28
Author: bernhard.reiter
Date: 2009-07-02 07:06:26 EDT (Thu, 02 Jul 2009)
New Revision: 54590
URL: http://svn.boost.org/trac/boost/changeset/54590
Log:
Fix binary_tree::clear(cursor)
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 49 +++++++++++++++++++++++++++++++--------
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 27 ++++++++++++++++++++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp | 1
3 files changed, 65 insertions(+), 12 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-07-02 07:06:26 EDT (Thu, 02 Jul 2009)
@@ -91,7 +91,7 @@
~binary_tree()
{
- clear();
+ this->clear();
}
/**
@@ -240,7 +240,7 @@
* @param c Cursor pointing to the node to be removed.
*/
// TODO: Take care of header-pointers
- void clear(cursor position)
+ cursor clear(cursor position)
{
// return cursor(boost::tree::for_each(boost::tree::postorder()
// , direct_cursor(position)
@@ -250,19 +250,49 @@
if (!position.is_leaf()) {
node_pointer pos_node =
static_cast<node_pointer>(
- position.base_node()->m_children[position.m_pos]
+ position.base_node()->m_children[position.m_pos]
);
+ size_type parent_idx = index(position.parent());
+
// recurse
- clear(position.begin());
- clear(position.end());
-
- // delete the node position points to
+ _clear(position.begin());
+ _clear(position.end());
+
+ // Make this node a leaf
+ static_cast<node_base_pointer>(pos_node->m_parent)->m_children[parent_idx] = 0;
+
m_node_alloc.destroy(pos_node);
m_node_alloc.deallocate(pos_node, 1);
+ }
+
+ if (position == root()) {
+ m_header.m_parent = &m_header;
+ m_header.m_children[0] = 0;
+ m_header.m_children[1] = &m_header;
}
+
+ return position;
}
-
+
+private:
+ void _clear(cursor position) {
+ if (!position.is_leaf()) {
+ node_pointer pos_node =
+ static_cast<node_pointer>(
+ position.base_node()->m_children[position.m_pos]
+ );
+
+ // recurse
+ _clear(position.begin());
+ _clear(position.end());
+
+ m_node_alloc.destroy(pos_node);
+ m_node_alloc.deallocate(pos_node, 1);
+ }
+ }
+
+public:
void rotate(cursor& pos)
{
//TODO: Take care of inorder_first pointer!
@@ -325,9 +355,6 @@
void clear()
{
clear(this->root());
- m_header.m_parent = &m_header;
- m_header.m_children[0] = 0;
- m_header.m_children[1] = &m_header;
}
// splice operations
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-07-02 07:06:26 EDT (Thu, 02 Jul 2009)
@@ -282,10 +282,37 @@
//BOOST_AUTO_TEST_SUITE_END()
+BOOST_AUTO_TEST_CASE( clear_subtree_test )
+{
+ binary_tree<int>::size_type sz = size(bt.root());
+ binary_tree<int>::cursor c = bt.root().begin();
+ BOOST_CHECK(!c.is_leaf());
+ sz -= size(c);
+
+ BOOST_CHECK(!c.is_leaf());
+ c = bt.clear(c);
+ BOOST_CHECK(c == bt.root().begin());
+ BOOST_CHECK(c.is_leaf());
+ BOOST_CHECK_EQUAL(*c, 8);
+ BOOST_CHECK_EQUAL(sz, size(bt.root()));
+}
+
+BOOST_AUTO_TEST_CASE( clear_root_test )
+{
+ binary_tree<int>::cursor c = bt.root();
+
+ BOOST_CHECK(!c.is_leaf());
+ c = bt.clear(c);
+ BOOST_CHECK(c.is_leaf());
+ BOOST_CHECK(c == bt.root());
+ BOOST_CHECK(bt.empty());
+}
+
BOOST_AUTO_TEST_CASE( clear_test )
{
bt.clear();
BOOST_CHECK(bt.empty());
+ BOOST_CHECK(bt.root().is_leaf());
}
BOOST_AUTO_TEST_CASE( swap_binary_tree_test )
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp 2009-07-02 07:06:26 EDT (Thu, 02 Jul 2009)
@@ -83,7 +83,6 @@
BOOST_AUTO_TEST_CASE( constructors_test )
{
forest<int> ft0;
- //BOOST_CHECK_EQUAL(*ft0.root(), 0);
BOOST_CHECK(ft0.empty());
BOOST_CHECK(ft0.begin() == ft0.end());
}