
BoostCommit : 
From: ockham_at_[hidden]
Date: 20080607 08:04:58
Author: bernhard.reiter
Date: 20080607 08:04:57 EDT (Sat, 07 Jun 2008)
New Revision: 46212
URL: http://svn.boost.org/trac/boost/changeset/46212
Log:
Remove shoot argument from inorder::lower_bound  also in documentation.
Text files modified:
sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk  21 ++++++++++++
1 files changed, 12 insertions(+), 9 deletions()
Modified: sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk
==============================================================================
 sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk (original)
+++ sandbox/SOC/2006/tree/trunk/libs/tree/doc/overview.qbk 20080607 08:04:57 EDT (Sat, 07 Jun 2008)
@@ 145,15 +145,18 @@
If there is no such value in the entire (sub)tree (because all values
are less than the search value or because it is empty), we'd intuitively want to return something like
a "tree `end()`" to indicate the position where the search value could be inserted without changing the
ordering. As we normally depart from a `tree.root()` that makes hardly sense to be called `begin()`
instead in the given context, we provide a function `shoot()` that points one position past the rightmost
node in the tree. In order for the algorithm to work not only for trees but also for any given subtree
described by its root and shoot cursors, we state a version with two cursors instead of a tree as first
parameters:
+ordering. When searching, we will normally depart from a `tree.root()`
+(that makes hardly sense to be called `begin()`
+in the given context), which itself cannot be dereferenced (only its `tree.root().begin()` can).
+This suggests `root()` as return value if we cannot find the given value in the tree.
+In order for the algorithm to work not only for trees but also for any given subtree
+described by its root cursor, we state a version with a cursor instead of a tree as first
+parameter:
template <class TreeCursor, class T>
 TreeCursor lower_bound(TreeCursor x, TreeCursor y, T const& val)
+ TreeCursor lower_bound(TreeCursor x, T const& val)
{
+ TreeCursor y = x;
while (x.empty()) {
x = std::lower_bound(x.begin(), x.end(), val);
if (!x.parity())
@@ 177,10 +180,10 @@
# "Specialize" the above algorithm for search values of a string type. (cf. Austern et al.)
# Generalize the above algorithm for "multiway" trees.
# Implement `upper_bound` for multiway trees.
# Implement a twoargument version that takes a tree as the first (the search value as the second)
argument and uses the tree's `root` and `shoot` members in lieu of `x` and `y`. (You'll actually need
+# Implement a twoargument version that takes a tree as the first
+argument and uses the tree's `root` member in lieu of `x`. (You'll actually need
two versions of that algorithm, one for `const` trees and one for mutable ones.)
[/# Replace the member functions in the twoargument versions from the previous exercise by freestanding
+[/# Replace the member functions from the previous exercise by freestanding
ones. Implement them for noncursor iterators so that `empty(iter)` always returns true.]
[endsect] [/ Exercises]
BoostCommit 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