Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r51613 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-03-04 17:11:05


Author: bernhard.reiter
Date: 2009-03-04 17:11:04 EST (Wed, 04 Mar 2009)
New Revision: 51613
URL: http://svn.boost.org/trac/boost/changeset/51613

Log:
Fix non-leaf insertion (both in binary_tree and also in fake_tree)
Text files modified:
   sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 10 ++++++++++
   sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 3 +--
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp | 2 ++
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp | 12 ------------
   sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp | 14 +++++++++++++-
   sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp | 19 ++++++++++++++++++-
   sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp | 2 ++
   sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 5 ++++-
   8 files changed, 50 insertions(+), 17 deletions(-)

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp 2009-03-04 17:11:04 EST (Wed, 04 Mar 2009)
@@ -107,6 +107,16 @@
         c.to_end();
 }
 
+//template <class BinaryCursor>
+//BOOST_CONCEPT_REQUIRES(
+// ((AscendingCursor<BinaryCursor>)),
+// (void)) // return type
+//to_forest_end(BinaryCursor& c)
+//{
+// to_last(inorder(), c);
+// predecessor(inorder(), c); // requires AscendingCursor
+// ++c;
+//}
 
 template <class BinaryCursor>
 BOOST_CONCEPT_REQUIRES(

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-03-04 17:11:04 EST (Wed, 04 Mar 2009)
@@ -196,9 +196,8 @@
         node_pointer p_node = m_node_alloc.allocate(1, node_hint);
         //m_node_alloc.construct(p_node, val);
         *p_node = node_type(val);
- p_node->init();
         
- pos.attach(p_node);
+ pos.base_node()->attach(p_node, pos.m_pos);
 
         // Readjust begin
 // if ((pos == this->inorder_first()))

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp 2009-03-04 17:11:04 EST (Wed, 04 Mar 2009)
@@ -14,6 +14,7 @@
 
 #include <boost/tree/cursor.hpp>
 #include <boost/tree/cursor_adaptor.hpp>
+//#include <boost/tree/inorder_algorithms.hpp>
 
 #include <boost/type_traits/is_convertible.hpp>
 #include <boost/utility/enable_if.hpp>
@@ -83,6 +84,7 @@
     {
         return forest_cursor::cursor_adaptor_::base();
     }
+
 private:
     
     friend class cursor_core_access;

Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp 2009-03-04 17:11:04 EST (Wed, 04 Mar 2009)
@@ -214,18 +214,6 @@
     {
         return this->base_reference();
     }
-
- // TODO: protect?
- void attach(node_pointer p_node)
- {
- p_node->m_parent = this->base_reference();
-
- // Only forest-relevant:
-// p_node->operator[](1) = this->base_reference()->operator[](m_pos);
-// this->base_reference()->operator[](m_pos)->m_parent = p_node;
-
- this->base_reference()->m_children[m_pos] = p_node;
- }
 
 // /**
 // * Detaches the node this cursor points to and returns a pointer to it;

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-03-04 17:11:04 EST (Wed, 04 Mar 2009)
@@ -182,6 +182,18 @@
         return qp;
         //return (c ? 0 : 1);
     }
+
+ void attach(base_pointer p_node, children_type::size_type m_pos)
+ {
+ p_node->m_parent = this;
+
+ // Only relevant for non-leaf insertion:
+ if (m_children[m_pos] != 0)
+ m_children[m_pos]->m_parent = p_node;
+ p_node->m_children[m_pos] = m_children[m_pos];
+
+ m_children[m_pos] = p_node;
+ }
     
     base_pointer detach(children_type::size_type m_pos)
     {
@@ -189,7 +201,7 @@
         m_children[m_pos] =
             m_children[m_pos]
           ->m_children[((m_children[m_pos])
- ->m_children[0] == 0 /*node_base::nil()*/ ? 1 : 0)];
+ ->m_children[0] == 0 ? 1 : 0)];
         m_children[m_pos]->m_parent = this;
         return q;
     }

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/fake_binary_tree.hpp 2009-03-04 17:11:04 EST (Wed, 04 Mar 2009)
@@ -45,7 +45,7 @@
     typedef fake_root_tracking_binary_cursor<T> root_tracking_cursor;
     typedef fake_root_tracking_binary_cursor<T const> const_root_tracking_cursor;
         
- fake_binary_tree(typename std::vector<T>::size_type s = 0) : m_data(s)
+ fake_binary_tree(size_type s = 0) : m_data(s)
     { }
     
     descending_cursor descending_root()
@@ -77,6 +77,23 @@
     {
         if (c.m_pos >= m_data.size())
             m_data.resize(c.m_pos + 1);
+ else {
+ value_type tmp;
+ size_type s = c.m_pos;
+
+ while (m_data[s]) {
+ tmp = m_data[s];
+ s = 2*s + 1 + c.index();
+
+ if (s >= m_data.size()) {
+ m_data.resize(s + 1);
+ m_data[s] = tmp;
+ break;
+ }
+ m_data[s] = tmp;
+ }
+ }
+
         m_data[c.m_pos] = v;
         return c;
     }

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-03-04 17:11:04 EST (Wed, 04 Mar 2009)
@@ -30,10 +30,12 @@
     // For augmented trees. (Why is this necessary? Nothing here is explicit!)
     typedef typename Forest::value_type value_type;
     
+ // Insert top level elements in their proper order.
     typename Forest::cursor cur = f.insert(f.end(), value_type(8));
     cur = f.insert(f.end(), value_type(10));
     cur = f.insert(f.end(), value_type(14));
 
+ // Insert 8's child elements in a more random order to test if this also works.
     cur = f.begin().begin();
     cur = f.insert(cur, value_type(3));
     cur = f.insert(++cur, value_type(7));

Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp 2009-03-04 17:11:04 EST (Wed, 04 Mar 2009)
@@ -49,9 +49,12 @@
         ret.insert(++cur, value_type(7));
         cur = ret.insert(ret.root().end(), value_type(10));
         cur = ret.insert(ret.root().end().end(), value_type(14));
- cur = ret.insert(cur.to_begin(), value_type(13));
+ //cur = ret.insert(cur.to_begin(), value_type(13));
+ // First insert 11 as left child of 14, 12 as child of 11
         cur = ret.insert(cur.to_begin(), value_type(11));
         cur = ret.insert(++cur.to_begin(), value_type(12));
+ // Now insert 13 as left child of 14, which makes it 11's parent
+ ret.insert(ret.root().end().end().begin(), value_type(13));
     }
     
     template <class Cursor>


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk