From: ockham_at_[hidden]
Date: 2008-06-07 11:21:34
Author: bernhard.reiter
Date: 2008-06-07 11:21:33 EDT (Sat, 07 Jun 2008)
New Revision: 46214
URL: http://svn.boost.org/trac/boost/changeset/46214
Log:
More lower_bound() related fixes.
Text files modified:
sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp | 4 ++--
sandbox/SOC/2006/tree/trunk/boost/tree/binary_tree.hpp | 3 +--
sandbox/SOC/2006/tree/trunk/boost/tree/search.hpp | 11 ++++++-----
sandbox/SOC/2006/tree/trunk/libs/tree/test/binary_tree_test.cpp | 2 +-
sandbox/SOC/2006/tree/trunk/libs/tree/test/key_search_binary_tree_test.cpp | 10 +++++-----
5 files changed, 15 insertions(+), 15 deletions(-)
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/balanced_tree.hpp 2008-06-07 11:21:33 EDT (Sat, 07 Jun 2008)
@@ -244,7 +244,7 @@
template <class Cmp>
iterator lower_bound(value_type const& k, Cmp cmp)
{
- return iterator(boost::tree::lower_bound(h.root(), k,
+ return iterator(boost::tree::inorder::lower_bound(h.root(), k,
bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
}
@@ -261,7 +261,7 @@
template <class Cmp>
const_iterator lower_bound(value_type const& k, Cmp cmp) const
{
- return const_iterator(boost::tree::lower_bound(h.croot(), k,
+ return const_iterator(boost::tree::inorder::lower_bound(h.croot(), k,
bind<bool>(cmp, bind(typename data_type::extract_data(), _1), _2)));
}
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 2008-06-07 11:21:33 EDT (Sat, 07 Jun 2008)
@@ -44,7 +44,6 @@
private:
typedef node<value_type, detail::binary_array> node_type;
- //typedef node<value_type, detail::binary_array> const_node_type;
typedef typename Alloc::template rebind<node_type>::other
node_allocator_type;
@@ -54,7 +53,7 @@
public:
typedef nary_tree_cursor<node_type> cursor;
- typedef /*const_*/ nary_tree_cursor<node_type const> const_cursor;
+ typedef nary_tree_cursor<node_type const> const_cursor;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::reference reference;
Modified: sandbox/SOC/2006/tree/trunk/boost/tree/search.hpp
==============================================================================
--- sandbox/SOC/2006/tree/trunk/boost/tree/search.hpp (original)
+++ sandbox/SOC/2006/tree/trunk/boost/tree/search.hpp 2008-06-07 11:21:33 EDT (Sat, 07 Jun 2008)
@@ -14,7 +14,7 @@
// * add versions without cmp argument (just using <)
// concept checks etc. ATM binary only, generalize for actual Multiway.
-// 2/3 argument versions (using tree instead of root/shoot)
+// 2/3 argument versions (using tree instead of root)
//(and specialize again using "trivial lower bound" instead of std::lower_bound)
//internally - or provide one lower bound for all. (for example a range version)
// (See "exercises"!)
@@ -27,12 +27,12 @@
namespace boost {
namespace tree {
+namespace inorder {
/**
* @brief Finds the first position in a multiway subtree in which @a val
* could be inserted without changing the ordering, using < (less
- * than)
- * for comparisons.
+ * than) for comparisons.
* @param x The subtree's root
* @param val The search term
* @return A multiway cursor pointing to the first element not less than
@@ -45,7 +45,7 @@
MultiwayCursor y = x;
while (!x.empty()) {
x = std::lower_bound(x.begin(), x.end(), val);
- if (x.parity() == 0)
+ if (x.parity() == 0)
y = x;
}
return y;
@@ -68,12 +68,13 @@
MultiwayCursor y = x;
while (!x.empty()) {
x = std::lower_bound(x.begin(), x.end(), val, cmp);
- if (x.parity() == 0)
+ if (x.parity() == 0)
y = x;
}
return y;
}
+} // namespace inorder
} // namespace tree
} // namespace boost
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 2008-06-07 11:21:33 EDT (Sat, 07 Jun 2008)
@@ -66,7 +66,7 @@
--c4;
BOOST_CHECK(*c4 == 2);
BOOST_CHECK(c4.parent() == c1);
- c = boost::tree::lower_bound(mytree.root(), 2, std::less<int>());
+ c = boost::tree::inorder::lower_bound(mytree.root(), 2, std::less<int>());
BOOST_CHECK(*c == 2);
BOOST_CHECK(c4.empty());
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 2008-06-07 11:21:33 EDT (Sat, 07 Jun 2008)
@@ -115,23 +115,23 @@
// searcher_t::container_type& the_tree = my_tree.container();
// searcher_t::cursor tree_cur = boost::tree::lower_bound(the_tree.root(),
-// the_tree.shoot(), 39, std::less<int>());
+// 39, std::less<int>());
//
// BOOST_CHECK(tree_cur.empty());
// BOOST_CHECK((++tree_cur).empty());
// --tree_cur;
// BOOST_CHECK(*tree_cur == 39);
//
-// tree_cur = boost::tree::lower_bound(the_tree.root(), the_tree.shoot(), 18);
+// tree_cur = boost::tree::lower_bound(the_tree.root(), 18);
// BOOST_CHECK(*tree_cur == 18);
//
-// tree_cur = boost::tree::lower_bound(the_tree.root(), the_tree.shoot(), 30);
+// tree_cur = boost::tree::lower_bound(the_tree.root(), 30);
// BOOST_CHECK(tree_cur.empty());
// BOOST_CHECK(!(++tree_cur).empty());
// --tree_cur;
// BOOST_CHECK(*tree_cur == 31);
//
-// tree_cur = boost::tree::lower_bound(the_tree.root(), the_tree.shoot(), 3);
+// tree_cur = boost::tree::lower_bound(the_tree.root(), 3);
// BOOST_CHECK(*tree_cur == 7);
c = my_tree.begin();
@@ -160,7 +160,7 @@
//BOOST_CHECK(*c == 39);
-// tree_cur = boost::tree::lower_bound(the_tree.root(), the_tree.shoot(), 412);
+// tree_cur = boost::tree::lower_bound(the_tree.root(), 412);
// BOOST_CHECK(*tree_cur == 412);
// BOOST_CHECK(*tree_cur.parent() == 18);
//