Subject: [Boost-commit] svn:boost r50515 - in sandbox/SOC/2006/tree/trunk: boost/tree boost/tree/detail libs/tree/test
From: ockham_at_[hidden]
Date: 2009-01-08 08:53:06
Author: bernhard.reiter
Date: 2009-01-08 08:53:06 EST (Thu, 08 Jan 2009)
New Revision: 50515
URL: http://svn.boost.org/trac/boost/changeset/50515
Log:
Some binary_tree and node implementation cleanup.
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 38 ++++++--------------------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp | 3 +
sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp | 57 +++++++++++++++++++++------------------
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 4 +-
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 3 --
5 files changed, 43 insertions(+), 62 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-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -68,23 +68,13 @@
explicit binary_tree (allocator_type const& alloc = allocator_type())
: m_header(), m_value_alloc(alloc)
{
- m_header.m_children[0] = node_base_type::nil();
- m_header.m_children[1] = &m_header;
}
-// explicit binary_tree (size_type n, value_type const& value = value_type(),
-// allocator_type const& alloc = allocator_type())
-// : m_header(), m_value_alloc(alloc)
-// {}
-
template <class InputCursor>
binary_tree (InputCursor subtree,
allocator_type const& alloc = allocator_type())
: m_header(), m_value_alloc(alloc)
{
- m_header.m_children[0] = node_base_type::nil();
- m_header.m_children[1] = &m_header;
-
insert(root(), subtree);
}
@@ -98,9 +88,6 @@
binary_tree (self_type const& x)
: m_header(), m_value_alloc(x.m_value_alloc)
{
- m_header.m_children[0] = node_base_type::nil();
- m_header.m_children[1] = &m_header;
-
if (!x.empty())
insert(root(), x.root());
}
@@ -207,14 +194,10 @@
*/
cursor insert(cursor pos, value_type const& val)
{
- void* val_hint = 0;//TODO: need some method to obtain hints from cursor
void* node_hint = 0;
- pointer p_val = m_value_alloc.allocate(1, val_hint);
- m_value_alloc.construct(p_val, val);
-
node_pointer p_node = m_node_alloc.allocate(1, node_hint);
- m_node_alloc.construct(p_node, p_val);
+ m_node_alloc.construct(p_node, val);
p_node->init();
pos.attach(p_node);
@@ -316,9 +299,6 @@
if (!position.empty()) {
node_pointer pos_node =
static_cast<node_pointer>(position.base_node()->m_children[position.m_pos]);
- // delete the value position points to
- m_value_alloc.destroy(pos_node->data());
- m_value_alloc.deallocate(pos_node->data(), 1);
// recurse
clear(position.begin());
@@ -357,7 +337,7 @@
m_header.m_children[1] = other.m_header.m_children[1];
//m_header.m_parent = other.m_header.m_parent;
- other.m_header.m_children[0] = node_base_type::nil();
+ other.m_header.m_children[0] = 0;
other.m_header.m_children[1] = &other.m_header;
//other.m_header.m_parent = &other.m_header;
@@ -371,7 +351,7 @@
other.m_header.m_children[1] = m_header.m_children[1];
//other.m_header.m_parent = m_header.m_parent;
- m_header.m_children[0] = node_base_type::nil();
+ m_header.m_children[0] = 0;
m_header.m_children[1] = &m_header;
//m_header.m_parent = &m_header;
@@ -391,9 +371,9 @@
*/
void clear()
{
- clear(this->root());
- m_header.m_parent = &m_header;
- m_header.m_children[0] = node_base_type::nil();
+ clear(this->root());
+ m_header.m_parent = &m_header;
+ m_header.m_children[0] = 0;
m_header.m_children[1] = &m_header;
}
@@ -418,7 +398,7 @@
position.base_node()->m_children[position.m_pos] = x.m_header.m_children[0];
//TODO: replace the following by some temporary-swapping?
- x.m_header.m_children[0] = node_base_type::nil();
+ x.m_header.m_children[0] = 0;
x.m_header.m_children[1] = &x.m_header;
x.m_header.m_parent = &x.m_header;
}
@@ -444,12 +424,12 @@
position.base_node()->node_base_type::operator[](position.m_pos) = root.base_node();
- root.base_node()->m_children[0] = node_base_type::nil();
+ root.base_node()->m_children[0] = 0;
if (root == x.root()) {
x.m_header.m_children[1] = &x.m_header;
x.m_header.m_parent = &x.m_header;
} else
- root.base_node()->m_children[1] = node_base_type::nil();
+ root.base_node()->m_children[1] = 0;
}
}
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-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -149,7 +149,8 @@
// Container specific
bool empty_() const
{
- return this->base_reference()->m_children[m_pos] == node_type::nil(); //->empty();
+ return //this->base_reference()->m_children[m_pos] == node_type::nil() ||
+ this->base_reference()->m_children[m_pos] == 0; //->empty()
//return this->base_reference()->get_index();
}
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-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -110,6 +110,16 @@
public:
typedef array<node_base*, 2> children_type;
+ node_with_children_base()
+ {
+ init();
+ }
+
+ inline void init()
+ {
+ for (children_type::size_type i=0; i<children_type::size(); ++i)
+ m_children[i] = 0;
+ }
//protected:
children_type m_children;
};
@@ -124,24 +134,24 @@
typedef self_type const* const_base_pointer;
node_base() : node_with_parent_base(), node_with_children_base()
- { }
+ {
+// m_children[0] = 0;
+// m_children[1] = 0;
+ }
node_base(node_with_parent_base* p)
: node_with_parent_base(p), node_with_children_base()
- { }
-
- static base_pointer nil()
- {
- static self_type m_nil_obj;
- static base_pointer m_nil = &m_nil_obj;
- return m_nil;
- }
-
- void init()
{
- for (children_type::size_type i=0; i<children_type::max_size(); ++i)
- m_children[i] = nil();
+// m_children[0] = 0;
+// m_children[1] = 0;
}
+
+// static base_pointer nil()
+// {
+// static self_type m_nil_obj;
+// static base_pointer m_nil = &m_nil_obj;
+// return m_nil;
+// }
// This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
// bool const empty() const
@@ -179,7 +189,7 @@
m_children[m_pos] =
m_children[m_pos]
->m_children[((m_children[m_pos])
- ->m_children[0] == node_base::nil() ? 1 : 0)];
+ ->m_children[0] == 0 /*node_base::nil()*/ ? 1 : 0)];
m_children[m_pos]->m_parent = this;
return q;
}
@@ -235,24 +245,17 @@
//enum size_t { first = 0, second = 1 };
//typedef std::size_t size_type;
-
- // TODO: add observers.
- reference operator*() { return *m_data; }
+ reference operator*() { return m_data; }
- const_reference operator*() const { return *m_data; }
+ const_reference operator*() const { return m_data; }
- ascending_node(pointer data) : base_type(), m_data(data) {}
+ ascending_node(value_type data) : base_type(), m_data(data) {}
- ascending_node(pointer data, base_pointer p) : base_type(p), m_data(data) {}
-
- pointer data()
- {
- return m_data;
- }
+ ascending_node(value_type data, base_pointer p) : base_type(p), m_data(data) {}
- private:
- pointer m_data;
+private:
+ value_type m_data;
};
} // namespace detail
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp 2009-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -89,8 +89,8 @@
// m_header.push_back(node_base_type::nil());
// m_header.push_back(&m_header);
- m_header.m_children[0] = node_base_type::nil();
- m_header.m_children[1] = &m_header;
+// m_header.m_children[0] = node_base_type::nil();
+// m_header.m_children[1] = &m_header;
}
explicit nary_tree (size_type n, value_type const& value = value_type(),
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-01-08 08:53:06 EST (Thu, 08 Jan 2009)
@@ -24,7 +24,6 @@
binary_tree<int> bt0;
BOOST_CHECK(bt0.root().empty());
//BOOST_CHECK(bt0.root().begin() == bt0.root().end()); //FIXME
-
// test with allocator?
}
@@ -58,7 +57,6 @@
BOOST_CHECK(bt0.root().begin().begin().empty());
BOOST_CHECK(++c == bt0.root().begin().end());
- //BOOST_CHECK_EQUAL(1, 2);
}
BOOST_AUTO_TEST_SUITE_END()
@@ -127,7 +125,6 @@
//c1 = mytree.erase(c1);
//BOOST_CHECK_EQUAL(*c1, 2);
-
}
template <class Cursor>