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>