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

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