|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r51461 - in sandbox/SOC/2006/tree/trunk: . boost/tree boost/tree/detail boost/tree/detail/balancers libs/tree/test
From: ockham_at_[hidden]
Date: 2009-02-26 15:28:05
Author: bernhard.reiter
Date: 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
New Revision: 51461
URL: http://svn.boost.org/trac/boost/changeset/51461
Log:
rename cursor empty() to is_leaf()
Text files modified:
sandbox/SOC/2006/tree/trunk/TODO | 1 +
sandbox/SOC/2006/tree/trunk/boost/tree/algorithm.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/balance.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 18 +++++++++---------
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp | 4 ++--
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/forest_cursor.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_cursor.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/detail/nary_node.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_inorder_algorithms.hpp | 12 ++++++------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp | 12 ++++++------
sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp | 12 ++++++------
sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp | 8 ++++----
sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp | 18 +++++++++---------
sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp | 2 +-
sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/nary_tree.hpp | 6 +++---
sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp | 14 +++++++-------
sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp | 10 +++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 36 ++++++++++++++++++------------------
sandbox/SOC/2006/tree/trunk/libs/tree/test/forest_test.cpp | 10 +++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp | 14 +++++++-------
sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp | 5 +++++
sandbox/SOC/2006/tree/trunk/libs/tree/test/nary_tree_test.cpp | 10 +++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp | 2 --
sandbox/SOC/2006/tree/trunk/libs/tree/test/test_tree_traversal_data.hpp | 20 ++++++++++----------
sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp | 2 +-
34 files changed, 132 insertions(+), 128 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/TODO
==============================================================================
--- sandbox/SOC/2006/tree/trunk/TODO (original)
+++ sandbox/SOC/2006/tree/trunk/TODO 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -14,6 +14,7 @@
[section TODO]
General:
+* In case of forest cursor, is_leaf() should really be empty().
* Further reduce test data redundancy: make mock cursor use the data from fake_binary_tree,
and give it an Order template argument. Calculate *order positions from level order indices
as of fake_binary_tree. Possibly change fake_binary_tree internal representation to a
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -103,7 +103,7 @@
to_forest_end(BinaryCursor& c)
{
c.to_begin();
- while (!c.empty())
+ while (!c.is_leaf())
c.to_end();
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/ascending_cursor.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -147,7 +147,7 @@
// Container specific
bool const empty_() const
{
- return m_s.top().empty();
+ return m_s.top().is_leaf();
}
size_type size_()
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -493,7 +493,7 @@
// If yes, we could just insert at pos.
cursor c = pos.base().base();
- while (!c.empty())
+ while (!c.is_leaf())
c = c.end();
c = h.insert(c, data_type(val));
@@ -560,9 +560,9 @@
* Returns true if the %balance is empty. (Thus begin() would
* equal end().)
*/
- bool empty() const
+ bool is_leaf() const
{
- return h.empty();
+ return h.is_leaf();
}
void rotate(iterator& i)
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -176,7 +176,7 @@
*/
bool empty() const
{
- return root().empty(); //m_header.m_children[1] == &m_header;
+ return root().is_leaf(); //m_header.m_children[1] == &m_header;
}
// Hierarchy-specific
@@ -229,9 +229,9 @@
subtree.to_begin();
insert(pos, *subtree);
- if (!subtree.empty())
+ if (!subtree.is_leaf())
insert(pos.begin(), subtree);
- if (!(++subtree).empty())
+ if (!(++subtree).is_leaf())
insert(pos.end(), subtree);
return pos;
}
@@ -264,7 +264,7 @@
// static void destroy_node(cursor position)
// {
-// if (!position.empty()) {
+// 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
@@ -294,7 +294,7 @@
// , destroy_node
// , descending_vertical_traversal_tag()));
- if (!position.empty()) {
+ if (!position.is_leaf()) {
node_pointer pos_node =
static_cast<node_pointer>(position.base_node()->m_children[position.m_pos]);
@@ -414,7 +414,7 @@
void splice(cursor position, binary_tree& x,
cursor root, cursor inorder_first)
{
- if (!x.empty()) {
+ if (!x.is_leaf()) {
if (inorder_first == x.inorder_first())
x.m_header.m_children[1] = inorder_first.base_node();
if (position == inorder_first()) // Readjust inorder_first to x's
@@ -474,7 +474,7 @@
node_pointer p_node = static_cast<node_pointer>(position.base_node());
++position;
- if (position.empty()) {
+ if (position.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];
@@ -487,7 +487,7 @@
static_cast<node_base_pointer>(p_node->m_parent)
->node_base_type::operator[](1) = position.base_node();
- while (!position.empty())
+ while (!position.is_leaf())
position = position.begin();
}
@@ -505,7 +505,7 @@
node_pointer p_node = static_cast<node_pointer>(descendant.base_node());
++descendant;
- if (descendant.empty()) {
+ 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];
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_adaptor.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -181,7 +181,7 @@
bool const empty_() const
{
- return m_cursor.empty();
+ return m_cursor.is_leaf();
}
bool const is_root_() const
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_archetypes.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -29,7 +29,7 @@
descendingCursor_archetype begin() const { return *this; }
descendingCursor_archetype end() const { return *this; }
- bool empty() const { return true; }
+ bool is_leaf() const { return true; }
};
class ascendingCursor_archetype
@@ -89,7 +89,7 @@
self_type begin() const { return *this; }
self_type end() const { return *this; }
- bool empty() const { return true; }
+ bool is_leaf() const { return true; }
};
template <
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_concepts.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -40,7 +40,7 @@
X e = d.end();
- bool m = b.empty();
+ bool m = b.is_leaf();
m = false; // Avoid compiler warning about unused variable
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/cursor_facade.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -138,7 +138,7 @@
//>::type
vertical_traversal;
- bool const empty() const
+ bool const is_leaf() const
{
return cursor_core_access::empty_(this->derived());
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/treap.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -64,7 +64,7 @@
typename Tree::cursor q;
while((q = ((p.begin()->metadata().get_priority()
> p.end()->metadata().get_priority())
- ? p.begin() : p.end())).empty())
+ ? p.begin() : p.end())).is_leaf())
t.rotate(q);
p = q;
return p;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/balancers/unbalanced.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -30,7 +30,7 @@
static typename Tree::cursor remove(Tree& t, typename Tree::cursor& x)
{
//typename Tree::cursor y = x;
- if (x.begin().empty() || x.end().empty())
+ if (x.begin().is_leaf() || x.end().is_leaf())
return x;
//successor(inorder, x);
return next(inorder(), x);
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -90,7 +90,7 @@
bool empty_() const
{
- return this->base().begin().empty() && this->base().end().empty();
+ return this->base().begin().is_leaf() && this->base().end().is_leaf();
}
typename forest_cursor::cursor_adaptor_::reference dereference() const
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -150,7 +150,7 @@
bool empty_() const
{
return //this->base_reference()->m_children[m_pos] == node_type::nil() ||
- this->base_reference()->m_children[m_pos] == 0; //->empty()
+ this->base_reference()->m_children[m_pos] == 0; //->is_leaf()
//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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -89,9 +89,9 @@
// }
//
// // This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
-// bool const empty() const
+// bool const is_leaf() const
// {
-// return ((this == nil()) || this->base_type::empty());
+// return ((this == nil()) || this->base_type::is_leaf());
// }
//
// // O(n); n is number of parent's children
@@ -154,7 +154,7 @@
// }
// This injures Meyers' Item 36. OTOH, iterator adaptors do that, too, right?
-// bool const empty() const
+// bool const is_leaf() const
// {
// return (this == nil());
// }
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_inorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_inorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_inorder_algorithms.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -39,13 +39,13 @@
MultiwayCursor t = s.end();
for (s.to_begin(); s!=t; ++s) {
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(inorder(), s, f);
f(*s);
}
// Multiway cursor
- if (!t.empty())
+ if (!t.is_leaf())
for_each_recursive(inorder(), t, f);
}
@@ -69,13 +69,13 @@
MultiwayCursor t = s.end();
for (s.to_begin(); s!=t; ++s) {
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(inorder(), s, f);
f(*s);
}
// Multiway cursor
- if (!t.empty())
+ if (!t.is_leaf())
for_each_recursive(inorder(), t, f);
return f;
}
@@ -107,13 +107,13 @@
t.to_begin();
for (; s != r; ++s, ++t) {
- if (!s.empty())
+ if (!s.is_leaf())
transform(inorder(), s, t, op, descending_vertical_traversal_tag());
*t=op(*s);
}
// Multiway cursor
- if (!r.empty())
+ if (!r.is_leaf())
transform(inorder(), r, t, op, descending_vertical_traversal_tag());
return t;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_postorder_algorithms.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -38,11 +38,11 @@
{
Cursor t = s;
for (s.to_begin(); s != t.end(); ++s)
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(postorder(), s, f);
// Multiway cursor
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(postorder(), s, f);
f(*t.to_begin());
@@ -66,11 +66,11 @@
{
Cursor t = s;
for (s.to_begin(); s != t.end(); ++s)
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(postorder(), s, f);
// Multiway cursor
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(postorder(), s, f);
f(*t.to_begin());
@@ -104,11 +104,11 @@
OutCursor t2 = t;
for (; s != r.end(); ++s, ++t)
- if (!s.empty())
+ if (!s.is_leaf())
transform(postorder(), s, t, op, descending_vertical_traversal_tag());
// Multiway cursor
- if (!s.empty())
+ if (!s.is_leaf())
transform(postorder(), s, t, op, descending_vertical_traversal_tag());
*t2 = op(*r.to_begin());
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/detail/recursive_preorder_algorithms.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -39,12 +39,12 @@
Cursor t = s.end();
for (s.to_begin(); s != t; ++s) {
f(*s);
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(preorder(), s, f);
}
// Multiway cursor
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(preorder(), s, f);
}
@@ -67,12 +67,12 @@
Cursor t = s.end();
for (s.to_begin(); s != t; ++s) {
f(*s);
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(preorder(), s, f);
}
// Multiway cursor
- if (!s.empty())
+ if (!s.is_leaf())
for_each_recursive(preorder(), s, f);
return f;
@@ -105,12 +105,12 @@
t.to_begin();
for (; s != r; ++s, ++t) {
*t = op(*s);
- if (!s.empty())
+ if (!s.is_leaf())
transform(preorder(), s, t, op, descending_vertical_traversal_tag());
}
// Multiway cursor
- if (!s.empty())
+ if (!s.is_leaf())
transform(preorder(), s, t, op, descending_vertical_traversal_tag());
return t;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/forest.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -75,7 +75,7 @@
*/
explicit forest(Hierarchy const& hier = Hierarchy()) : h(hier)
{
-// if (h.empty())
+// if (h.is_leaf())
// h.insert(h.root(), value_type());
}
@@ -125,7 +125,7 @@
cursor end()
{
base_cursor b(h.root());
- while (!b.empty())
+ while (!b.is_leaf())
b.to_end();
return cursor(b);
}
@@ -146,7 +146,7 @@
const_cursor cend() const
{
base_const_cursor b(h.croot());
- while (!b.empty())
+ while (!b.is_leaf())
b.to_end();
return const_cursor(b);
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/general_algorithms.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -49,7 +49,7 @@
if (!(*c1 == *c2))
return false;
do {
- if (!c1.empty())
+ if (!c1.is_leaf())
if (!equal(c1, c2))
return false;
++c2;
@@ -80,7 +80,7 @@
if (!p(*c1,*c2))
return false;
do {
- if (!c1.empty())
+ if (!c1.is_leaf())
if (!equal(c1, c2))
return false;
++c2;
@@ -103,7 +103,7 @@
c.to_begin();
++s;
do
- if (!c.empty())
+ if (!c.is_leaf())
size(c, s);
while (c++ != d);
}
@@ -123,7 +123,7 @@
c.to_begin();
++s;
do
- if (!c.empty())
+ if (!c.is_leaf())
size(c, s);
while (c++ != d);
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/graph.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -191,7 +191,7 @@
template <class Tree>
bool empty_cursor(typename Tree::cursor u, Tree)
{
- return u.empty();
+ return u.is_leaf();
}
} // namespace boost
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/inorder_algorithms.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -45,8 +45,8 @@
(void)) // return type
successor(inorder, MultiwayCursor& c)
{
- if (!(++c).empty()) {
- while (!c.to_begin().empty());
+ if (!(++c).is_leaf()) {
+ while (!c.to_begin().is_leaf());
return;
}
@@ -67,8 +67,8 @@
(void)) // return type
predecessor(inorder, MultiwayCursor& c)
{
- if (!c.empty()) {
- while (!c.to_end().empty());
+ if (!c.is_leaf()) {
+ while (!c.to_end().is_leaf());
--c;
return;
}
@@ -91,7 +91,7 @@
(void)) // return type
to_first(inorder, Cursor& c)
{
- while (!c.empty())
+ while (!c.is_leaf())
c.to_begin();
}
@@ -128,7 +128,7 @@
//]
{
MultiwayCursor y = x;
- while (!x.empty()) {
+ while (!x.is_leaf()) {
x = std::lower_bound(x.begin(), x.end(), val);
if (x.index() == 0)
y = x;
@@ -157,7 +157,7 @@
//]
{
MultiwayCursor y = x;
- while (!x.empty()) {
+ while (!x.is_leaf()) {
x = std::lower_bound(x.begin(), x.end(), val, cmp);
if (index(x) == 0)
y = x;
@@ -184,7 +184,7 @@
//]
{
MultiwayCursor y = x;
- while (!x.empty()) {
+ while (!x.is_leaf()) {
x = std::upper_bound(x.begin(), x.end(), val);
if (index(x) == 0)
y = x;
@@ -213,7 +213,7 @@
//]
{
MultiwayCursor y = x;
- while (!x.empty()) {
+ while (!x.is_leaf()) {
x = std::upper_bound(x.begin(), x.end(), val, cmp);
if (index(x) == 0)
y = x;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/insert_cursor.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -90,7 +90,7 @@
void left()
{
- if (this->base_reference().empty())
+ if (this->base_reference().is_leaf())
// this->base_reference() =
tree.insert(this->base_reference(), typename Tr::value_type());
this->base_reference().to_begin();
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/multiway_tree.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -79,9 +79,9 @@
explicit multiway_tree(Hierarchy const& hier = Hierarchy()) : h(hier)
{ }
- bool empty()
+ bool is_leaf()
{
- return h.empty();
+ return h.is_leaf();
}
size_type size() const
@@ -124,7 +124,7 @@
//h.insert(bc, val);
//if (bc == h.root())
// bc =
- if (bc->empty()) {
+ if (bc->is_leaf()) {
bc->push_back(val);
bc.m_pos = 0;
}
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -192,7 +192,7 @@
if (pos.m_node->operator[](pos.m_pos) == node_type::nil())
static_cast<node_pointer>(pos.m_node)->operator[](pos.m_pos) = p_node;
else
- if (static_cast<node_pointer>(pos.m_node)->empty()) {
+ if (static_cast<node_pointer>(pos.m_node)->is_leaf()) {
static_cast<node_pointer>(pos.m_node)->push_back(p_node);
pos.m_pos = 0;
} else
@@ -210,7 +210,7 @@
*/
void clear(cursor c)
{
- if (!c.empty()) {
+ if (!c.is_leaf()) {
// delete the value this c points to
m_value_alloc.destroy(c.node()->data());
@@ -238,7 +238,7 @@
m_header[1] = &m_header;
}
- bool empty() const
+ bool is_leaf() const
{
return m_header.m_parent == &m_header;
}
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/postorder_algorithms.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -54,9 +54,9 @@
// Left child.
++c;
- while (!c.empty()) {
+ while (!c.is_leaf()) {
c.to_begin();
- if (c.empty())
+ if (c.is_leaf())
++c;
}
if (index(c))
@@ -81,11 +81,11 @@
return;
}
- if (!(++c).empty()) { // Right
+ if (!(++c).is_leaf()) { // Right
c.to_begin();
return;
}
- if (!(--c).empty()) { // Left
+ if (!(--c).is_leaf()) { // Left
c.to_begin();
return;
}
@@ -95,7 +95,7 @@
while (!c.is_root()) {
c.to_parent();
if (index(c))
- if (!(--c).empty()) {
+ if (!(--c).is_leaf()) {
c.to_begin();
return;
}
@@ -115,9 +115,9 @@
to_first(postorder, Cursor& c)
{
while (true)
- if (!c.empty())
+ if (!c.is_leaf())
c.to_begin();
- else if (!(++c).empty())
+ else if (!(++c).is_leaf())
c.to_begin();
else {
--c;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/preorder_algorithms.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -43,13 +43,13 @@
successor(preorder, Cursor& c)
{
// If we have a left child, go there.
- if (!c.empty()) {
+ if (!c.is_leaf()) {
c.to_begin();
return;
}
// No left child. So if we have a right child, go there.
- if (!(++c).empty()) {
+ if (!(++c).is_leaf()) {
c.to_begin();
return;
}
@@ -62,7 +62,7 @@
while (!c.is_root()) { // Doesn't work with subtrees!
c.to_parent();
if (!c.is_root() && !index(c)) {
- if (!(++c).empty()) {
+ if (!(++c).is_leaf()) {
c.to_begin();
return;
}
@@ -95,8 +95,8 @@
}
// Same for root (=end) and right children:
- while (!c.empty())
- if (!c.end().empty())
+ while (!c.is_leaf())
+ if (!c.end().is_leaf())
c.to_end();
else
c.to_begin();
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -23,7 +23,7 @@
BOOST_AUTO_TEST_CASE( constructors_test )
{
binary_tree<int> bt0;
- BOOST_CHECK(bt0.root().empty());
+ BOOST_CHECK(bt0.root().is_leaf());
//BOOST_CHECK(bt0.root().begin() == bt0.root().end()); //FIXME
// test with allocator?
}
@@ -31,31 +31,31 @@
BOOST_AUTO_TEST_CASE( insert_value_test )
{
binary_tree<int> bt0;
- BOOST_CHECK(bt0.root().empty());
+ BOOST_CHECK(bt0.root().is_leaf());
binary_tree<int>::cursor c = bt0.insert(bt0.root()/*.begin()*/, 8); //FIXME
c.to_begin();
BOOST_CHECK(c == bt0.root().begin());
BOOST_CHECK(bt0.root().begin().parent() == bt0.root());
- BOOST_CHECK(!bt0.root().empty());
+ BOOST_CHECK(!bt0.root().is_leaf());
BOOST_CHECK_EQUAL(*bt0.root().begin(), 8);
- BOOST_CHECK(bt0.root().begin().empty());
+ BOOST_CHECK(bt0.root().begin().is_leaf());
c = bt0.insert(c, 3);
c.to_begin();
// The 8 valued cursor still ok?
BOOST_CHECK(bt0.root().begin().parent() == bt0.root());
- BOOST_CHECK(!bt0.root().empty());
+ BOOST_CHECK(!bt0.root().is_leaf());
BOOST_CHECK_EQUAL(*bt0.root().begin(), 8);
// The 3 valued cursor.
BOOST_CHECK(c == bt0.root().begin().begin());
BOOST_CHECK(bt0.root().begin().begin().parent() == bt0.root().begin());
- BOOST_CHECK(!bt0.root().begin().empty());
+ BOOST_CHECK(!bt0.root().begin().is_leaf());
BOOST_CHECK_EQUAL(*bt0.root().begin().begin(), 3);
- BOOST_CHECK(bt0.root().begin().begin().empty());
+ BOOST_CHECK(bt0.root().begin().begin().is_leaf());
BOOST_CHECK(++c == bt0.root().begin().end());
}
@@ -98,22 +98,22 @@
c = mytree.root();
- BOOST_CHECK(c.empty());
+ BOOST_CHECK(c.is_leaf());
c1 = mytree.insert(c, 1);
c1.to_begin();
BOOST_CHECK_EQUAL(*c1, 1);
- BOOST_CHECK(!c.empty());
+ BOOST_CHECK(!c.is_leaf());
BOOST_CHECK(c1.parent() == c);
c2 = mytree.insert(c1, 2);
c2.to_begin();
- BOOST_CHECK(!c.empty());
- BOOST_CHECK(c2.empty());
+ BOOST_CHECK(!c.is_leaf());
+ BOOST_CHECK(c2.is_leaf());
BOOST_CHECK_EQUAL(*c1, 1);
BOOST_CHECK_EQUAL(*c2, 2);
*c1 = 14;
@@ -143,11 +143,11 @@
--c4;
BOOST_CHECK_EQUAL(*c4, 2);
BOOST_CHECK(c4.parent() == c1);
- BOOST_CHECK(c4.empty());
+ BOOST_CHECK(c4.is_leaf());
BOOST_CHECK_EQUAL(*c1, 14);
- BOOST_CHECK(c1.begin().empty() || c1.end().empty());
+ BOOST_CHECK(c1.begin().is_leaf() || c1.end().is_leaf());
//c1 = mytree.erase(c1);
//BOOST_CHECK_EQUAL(*c1, 2);
@@ -158,7 +158,7 @@
{
Cursor c = cur;
- BOOST_CHECK(!c.empty());
+ BOOST_CHECK(!c.is_leaf());
c.to_begin();
BOOST_CHECK(c.parent() == cur);
@@ -182,8 +182,8 @@
c = c.parent().parent();
BOOST_CHECK_EQUAL(*(c.begin()), 10);
- BOOST_CHECK(c.begin().empty());
- BOOST_CHECK(!c.end().empty());
+ BOOST_CHECK(c.begin().is_leaf());
+ BOOST_CHECK(!c.end().is_leaf());
BOOST_CHECK_EQUAL(*c.end().begin(), 14);
c = c.begin();
@@ -193,8 +193,8 @@
++c;
BOOST_CHECK_EQUAL(*c.begin(), 12);
- BOOST_CHECK(c.begin().empty());
- BOOST_CHECK(c.end().empty());
+ BOOST_CHECK(c.begin().is_leaf());
+ BOOST_CHECK(c.end().is_leaf());
c = c.begin();
// Both children empty
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -64,8 +64,8 @@
// BOOST_CHECK(c == ft0.begin());
// BOOST_CHECK(++c == ft0.end());
//// BOOST_CHECK(ft0.begin().parent() == ft0.root());
-// BOOST_CHECK(!ft0.empty());
-// BOOST_CHECK(ft0.begin().empty());
+// BOOST_CHECK(!ft0.is_leaf());
+// BOOST_CHECK(ft0.begin().is_leaf());
//
// c = ft0.insert(ft0.end(), 6);
// BOOST_CHECK_EQUAL(*c, 6);
@@ -73,7 +73,7 @@
// BOOST_CHECK(c != ft0.end());
//// BOOST_CHECK(c.base() == ft0.begin().end());
//// BOOST_CHECK(c.parent() == ft0.root());
-// BOOST_CHECK(!ft0.empty());
+// BOOST_CHECK(!ft0.is_leaf());
// BOOST_CHECK(++c == ft0.end());
// ----c;
// BOOST_CHECK(c == ft0.begin());
@@ -82,7 +82,7 @@
// c = ft0.insert(ft0.end(), 7);
// BOOST_CHECK_EQUAL(*c, 7);
//// BOOST_CHECK(c.parent() == ft0.root());
-// BOOST_CHECK(!ft0.empty());
+// BOOST_CHECK(!ft0.is_leaf());
// BOOST_CHECK(++c == ft0.end());
// ----c;
// BOOST_CHECK_EQUAL(*c, 6);
@@ -112,7 +112,7 @@
// BOOST_CHECK_EQUAL(*c, 8);
// BOOST_CHECK_EQUAL(*c.to_begin(), 3);
// BOOST_CHECK_EQUAL(*c.to_begin(), 1);
-// BOOST_CHECK(c.empty());
+// BOOST_CHECK(c.is_leaf());
//
// //validate_corresponding_forest(ft0);
//}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -33,7 +33,7 @@
BOOST_CHECK_EQUAL(c, my_tree.begin());
// searcher_t::cursor cur = searcher_t::cursor(c);
-// BOOST_CHECK(cur.empty());
+// BOOST_CHECK(cur.is_leaf());
// BOOST_CHECK_EQUAL(cur, searcher_t::cursor(my_tree.end()));
c1 = my_tree.insert(c, 8);
@@ -44,7 +44,7 @@
BOOST_CHECK(c1 != my_tree.end());
// cur = searcher_t::cursor(c1);
-// BOOST_CHECK((++cur).empty());
+// BOOST_CHECK((++cur).is_leaf());
// BOOST_CHECK(cur.index());
//
// cur = cur.parent(); //header-cursor(,1) (root)
@@ -66,7 +66,7 @@
//
// BOOST_CHECK_EQUAL(*cur, 8);
//
-// BOOST_CHECK((++cur).empty());
+// BOOST_CHECK((++cur).is_leaf());
// BOOST_CHECK(!(--cur).parent().index()); // root's index...
//
// BOOST_CHECK_EQUAL(*(searcher_t::cursor(c).begin()), 8);
@@ -114,8 +114,8 @@
// searcher_t::cursor tree_cur = boost::tree::lower_bound(the_tree.root(),
// 39, std::less<int>());
//
-// BOOST_CHECK(tree_cur.empty());
-// BOOST_CHECK((++tree_cur).empty());
+// BOOST_CHECK(tree_cur.is_leaf());
+// BOOST_CHECK((++tree_cur).is_leaf());
// --tree_cur;
// BOOST_CHECK_EQUAL(*tree_cur, 39);
//
@@ -123,8 +123,8 @@
// BOOST_CHECK_EQUAL(*tree_cur, 18);
//
// tree_cur = boost::tree::lower_bound(the_tree.root(), 30);
-// BOOST_CHECK(tree_cur.empty());
-// BOOST_CHECK(!(++tree_cur).empty());
+// BOOST_CHECK(tree_cur.is_leaf());
+// BOOST_CHECK(!(++tree_cur).is_leaf());
// --tree_cur;
// BOOST_CHECK_EQUAL(*tree_cur, 31);
//
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/mock_binary_cursor.hpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -102,6 +102,11 @@
{
return (m_pos + 1) % 2;
}
+
+ bool is_root_() const
+ {
+ return true;
+ }
};
#endif // LIBS_TREE_TEST_MOCK_BINARY_CURSOR_HPP
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/nary_tree_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/nary_tree_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/nary_tree_test.cpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -17,13 +17,13 @@
typedef nary_tree<int> tree_type;
tree_type mytree;
tree_type::cursor c = mytree.root();
- BOOST_CHECK(mytree.root().empty());
- BOOST_CHECK(c.empty());
+ BOOST_CHECK(mytree.root().is_leaf());
+ BOOST_CHECK(c.is_leaf());
c = mytree.insert(c, 4);
BOOST_CHECK_EQUAL(*c, 4);
BOOST_CHECK_EQUAL(c, mytree.root());
- BOOST_CHECK(c.empty());
+ BOOST_CHECK(c.is_leaf());
c = mytree.insert(c, 5);
BOOST_CHECK_EQUAL(*c, 5);
@@ -31,12 +31,12 @@
++c;
BOOST_CHECK_EQUAL(*c, 4);
BOOST_CHECK(c != mytree.root());
- BOOST_CHECK(c.empty());
+ BOOST_CHECK(c.is_leaf());
// BOOST_CHECK(c.m_cur != tree_type::node_type::nil());
mytree.insert(c.end(), 3);
BOOST_CHECK_EQUAL(*(c.begin()), 3);
- BOOST_CHECK(!c.empty());
+ BOOST_CHECK(!c.is_leaf());
BOOST_CHECK_EQUAL(c, c.begin().parent());
}
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/successor_test.cpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -10,9 +10,7 @@
#include <boost/test/included/unit_test.hpp>
#include <boost/test/test_case_template.hpp>
-
#include "test_tree_traversal_data.hpp"
-
#include "fake_binary_tree.hpp"
using namespace boost::tree;
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-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -60,26 +60,26 @@
BOOST_CHECK_EQUAL(*cur.begin(), 8);
BOOST_CHECK_EQUAL(*cur.begin().begin(), 3);
BOOST_CHECK_EQUAL(*cur.begin().begin().begin(), 1);
- BOOST_CHECK(cur.begin().begin().end().empty());
- BOOST_CHECK(cur.begin().begin().begin().empty()); //Leaf
+ BOOST_CHECK(cur.begin().begin().end().is_leaf());
+ BOOST_CHECK(cur.begin().begin().begin().is_leaf()); //Leaf
BOOST_CHECK_EQUAL(*cur.begin().end().begin(), 6);
BOOST_CHECK_EQUAL(*cur.begin().end().begin().begin(), 4);
- BOOST_CHECK(cur.begin().end().begin().begin().empty()); //Leaf
+ BOOST_CHECK(cur.begin().end().begin().begin().is_leaf()); //Leaf
BOOST_CHECK_EQUAL(*cur.begin().end().end().begin(), 7);
- BOOST_CHECK(cur.begin().end().end().begin().empty()); //Leaf
+ BOOST_CHECK(cur.begin().end().end().begin().is_leaf()); //Leaf
BOOST_CHECK_EQUAL(*cur.end().begin(), 10);
- BOOST_CHECK(cur.end().begin().empty());
+ BOOST_CHECK(cur.end().begin().is_leaf());
BOOST_CHECK_EQUAL(*cur.end().end().begin(), 14);
- BOOST_CHECK(cur.end().end().end().empty());
+ BOOST_CHECK(cur.end().end().end().is_leaf());
BOOST_CHECK_EQUAL(*cur.end().end().begin().begin(), 13);
- BOOST_CHECK(cur.end().end().begin().end().empty());
+ BOOST_CHECK(cur.end().end().begin().end().is_leaf());
BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().begin(), 11);
- BOOST_CHECK(cur.end().end().begin().begin().begin().empty());
+ BOOST_CHECK(cur.end().end().begin().begin().begin().is_leaf());
BOOST_CHECK_EQUAL(*cur.end().end().begin().begin().end().begin(), 12);
- BOOST_CHECK(cur.end().end().begin().begin().end().begin().empty()); //Leaf
+ BOOST_CHECK(cur.end().end().begin().begin().end().begin().is_leaf()); //Leaf
}
static void validate_test_dataset1_minus_1_tree(typename boost::tree::binary_tree<T>::const_cursor cur)
@@ -108,7 +108,7 @@
BOOST_CHECK_EQUAL(*c, 8);
BOOST_CHECK_EQUAL(*c.to_begin(), 3);
BOOST_CHECK_EQUAL(*c.to_begin(), 1);
- BOOST_CHECK(c.empty());
+ BOOST_CHECK(c.is_leaf());
BOOST_CHECK(++c == t.root().begin().begin().end());
--c;
c.to_parent();
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/test/treap_test.cpp 2009-02-26 15:28:02 EST (Thu, 26 Feb 2009)
@@ -43,7 +43,7 @@
for (treap_t::iterator ci = my_balancer.begin(); ci != my_balancer.end(); ++ci) {
treap_t::hierarchy_type::cursor c = ci.base().base();
// int priority = c->metadata().get_priority(); // FIXME: Segfaults!
-// if (!c.empty()) {
+// if (!c.is_leaf()) {
// BOOST_CHECK(priority
// > c.begin()->metadata().get_priority());
// }
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