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

Subject: [Boost-commit] svn:boost r54469 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-06-28 15:26:55

Author: bernhard.reiter
Date: 2009-06-28 15:26:54 EDT (Sun, 28 Jun 2009)
New Revision: 54469
URL: http://svn.boost.org/trac/boost/changeset/54469

Log:
Delegate binary_tree::erase implementation to nary_node_base::detach.
Text files modified: 
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp          |   144 +++++++++++++-------------------------- 
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp     |    38 ++-------                               
   sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp |     6                                         
   3 files changed, 61 insertions(+), 127 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-06-28 15:26:54 EDT (Sun, 28 Jun 2009)
@@ -13,7 +13,7 @@
 #define BOOST_TREE_BINARY_TREE_HPP
 
 #include <boost/tree/cursor.hpp>
-#include <boost/tree/algorithm.hpp>
+//#include <boost/tree/algorithm.hpp>
 #include <boost/tree/insert_cursor.hpp>
 
 #include <boost/tree/detail/node_traits.hpp>
@@ -235,49 +235,8 @@
         return pos;
     }
 
-//    //erase operations must rebalance; clear doesn't need to.    
-//    //TODO: Can/Should remove (and erase) return the next cursor's position ?
-//    //(There may be some DR concerning this for associative containers)
-//     void erase (cursor pos)
-//     {
-//         cursor ret; // = this->root();
-////         pos = pos.parent();
-//
-//        // TODO: Get the following to work properly.
-//         //balancer_type::remove(*this, pos);
-//         node_pointer p_node;
-////         if (pos == ret) {
-////             augmentor_type::pre_detach(*this, pos);
-//             p_node = pos.detach();
-////         } else {
-////             augmentor_type::pre_detach(*this, pos, ret,);
-////             p_node = pos.detach(ret);
-////         }
-//        
-//        m_node_alloc.destroy(p_node);
-//        m_node_alloc.deallocate(p_node, 1);
-//    }
-     
-//     static void destroy_node(cursor position)
-//     {
-//        if (!position.is_leaf()) {
-//             node_pointer pos_node = 
-//                 static_cast<node_pointer>(position.m_node->operator[](position.m_pos));
-//             // delete the value position points to    
-//             
-//            // recurse
-////             clear(position.begin());
-////             clear(position.end());
-//             
-//             // delete the node position points to
-//            m_node_alloc.destroy(pos_node);
-//            m_node_alloc.deallocate(pos_node, 1);         
-//          }
-//     }
-     
      /** 
-      * Removes a node and its descendants recursively in postorder
-      * without rebalancing
+      * @brief      Removes a node and its descendants recursively in postorder
       * @param c    Cursor pointing to the node to be removed.
       */
      // TODO: Take care of header-pointers
@@ -361,7 +320,7 @@
     }
 
     /**
-     * @brief Clears all data from the tree (without any rebalancing).
+     * @brief Clears all data from the tree.
      */
      void clear()
      {
@@ -428,30 +387,23 @@
     }
 
     /**
-     * @brief  Erases the value of the given cursor.
-     * @param  position  Cursor that is empty or at least one of whose children is
-     * 
+     * @brief  Erases an element.
+     * @param  position  Cursor indicating the element to be erased.
+     * @return Child element assuming the erased element's position.
      */
     cursor erase(cursor position)
     {
-        node_pointer parent_node
-        = static_cast<node_pointer>(position.parent().base_node());
-
         size_type idx = index(position);
-        size_type parent_idx = index(position.parent());
-
         node_pointer p_node = static_cast<node_pointer>(position.base_node());
 
-        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];
+        p_node = static_cast<node_pointer>(p_node->detach(idx));
+
+        position.base_node() = static_cast<node_base_pointer>(p_node->m_children[idx]);
 
         m_node_alloc.destroy(p_node);
         m_node_alloc.deallocate(p_node, 1);
 
-        return cursor(static_cast<node_base_pointer>(parent_node->m_children[parent_idx]),idx);
+        return position;
     }
 
 private:
@@ -491,44 +443,44 @@
      return (!(x == y));
 }
 
-/**
- * @brief   First element of a MultiwayTree in inorder traversal.
- *          O(1) overload for binary_tree
- * @param t A binary_tree
- * @return  Mutable cursor to the first element of @a t in inorder traversal
- */
-template <class T, class Alloc>
-typename binary_tree<T, Alloc>::cursor 
-first_cursor(inorder, binary_tree<T, Alloc>& t)
-{
-    return t.inorder_first();
-}
-
-/**
- * @brief   First element of a MultiwayTree in inorder traversal 
- *          (alias of cfirst()). O(1) overload for binary_tree.
- * @param t A binary_tree
- * @return  Read-only cursor to the first element of @a t in inorder traversal
- */
-template <class T, class Alloc>
-typename binary_tree<T, Alloc>::const_cursor 
-first_cursor(inorder, binary_tree<T, Alloc> const& t)
-{
-    return t.inorder_first();
-}
-
-/**
- * @brief   First element of a MultiwayTree in inorder traversal.
- *          O(1) overload for binary_tree
- * @param t A binary_tree
- * @return  Read-only cursor to the first element of @a t in inorder traversal
- */
-template <class T, class Alloc>
-typename binary_tree<T, Alloc>::const_cursor 
-cfirst_cursor(inorder, binary_tree<T, Alloc> const& t)
-{
-    return t.inorder_first();
-}
+///**
+// * @brief   First element of a MultiwayTree in inorder traversal.
+// *          O(1) overload for binary_tree
+// * @param t A binary_tree
+// * @return  Mutable cursor to the first element of @a t in inorder traversal
+// */
+//template <class T, class Alloc>
+//typename binary_tree<T, Alloc>::cursor 
+//first_cursor(inorder, binary_tree<T, Alloc>& t)
+//{
+//    return t.inorder_first();
+//}
+//
+///**
+// * @brief   First element of a MultiwayTree in inorder traversal 
+// *          (alias of cfirst()). O(1) overload for binary_tree.
+// * @param t A binary_tree
+// * @return  Read-only cursor to the first element of @a t in inorder traversal
+// */
+//template <class T, class Alloc>
+//typename binary_tree<T, Alloc>::const_cursor 
+//first_cursor(inorder, binary_tree<T, Alloc> const& t)
+//{
+//    return t.inorder_first();
+//}
+//
+///**
+// * @brief   First element of a MultiwayTree in inorder traversal.
+// *          O(1) overload for binary_tree
+// * @param t A binary_tree
+// * @return  Read-only cursor to the first element of @a t in inorder traversal
+// */
+//template <class T, class Alloc>
+//typename binary_tree<T, Alloc>::const_cursor 
+//cfirst_cursor(inorder, binary_tree<T, Alloc> const& t)
+//{
+//    return t.inorder_first();
+//}
 
 } // namespace tree
 } // namespace boost

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-06-28 15:26:54 EDT (Sun, 28 Jun 2009)
@@ -135,35 +135,17 @@
     
     base_pointer detach(children_type::size_type m_pos)
     {
-        base_pointer q = static_cast<node_base*>(m_children[m_pos]);
-        m_children[m_pos] = 
-            m_children[m_pos]
-          ->m_children[((m_children[m_pos])
-          ->m_children[0] == 0 ? 1 : 0)];
-        static_cast<node_base*>(m_children[m_pos])->m_parent = this;
-        return q;
-    }
-    
-    // TODO: actually implement this.
-    base_pointer detach(children_type::size_type index, 
-                        children_type::size_type other_index, 
-                        base_pointer other)
-    {
-        //Node::pre_splice(q, r);
-        // splice out q
-        base_pointer x = detach(index);
-
-        // q has been spliced out, now relink it in place of r.                
-        static_cast<base_pointer>(other->m_parent)->m_children[other_index] = this;
-        m_parent = other->m_parent;
-
-        for (children_type::size_type i=0; i<children_type::max_size(); ++i) {
-            m_children[i] = other->m_children[i];
-            static_cast<node_base*>(m_children[i])->m_parent = this;
-        }
-        return x;
+        node_with_children_base::children_type::size_type parent_idx = get_index();
+
+        if (m_children[m_pos] != 0) // Set child's parent only if there _is_ a child
+            static_cast<node_base*>(m_children[m_pos])->m_parent = m_parent;
+
+        static_cast<node_base*>(m_parent)->m_children[parent_idx]
+            = m_children[m_pos];
+        
+        return &*this;
     }
-    
+
     // O(1)
     children_type::size_type const get_index() const
     {

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 15:26:54 EDT (Sun, 28 Jun 2009)
@@ -179,13 +179,13 @@
     // Left child empty
     BOOST_CHECK(c.is_leaf());
     BOOST_CHECK(!(++c).is_leaf());
-    //--c;
 
     binary_tree<int>::size_type sz = size(bt.root());
     c = bt.erase(c);
     BOOST_CHECK_EQUAL(--sz, size(bt.root()));
     
-    BOOST_CHECK_EQUAL(*c, 14);
+    BOOST_CHECK(c == bt.root().end().end());
+    BOOST_CHECK_EQUAL(*--c, 14);
 }
 
 BOOST_AUTO_TEST_CASE( erase_leaf_node_test )
@@ -202,7 +202,7 @@
     c = bt.erase(c);
     BOOST_CHECK_EQUAL(--sz, size(bt.root()));
 
-    //BOOST_CHECK(c == );
+    BOOST_CHECK(c == bt.root().end().end().begin().end().begin());
 }
 
 BOOST_AUTO_TEST_CASE( clear_test )