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

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 )