digitalmars.D.learn - RedBlackTree.lowerBound

• Ellery Newcomer (47/47) Feb 19 2012 Is it just me or are lowerBound and upperBound really unintuitively
```Is it just me or are lowerBound and upperBound really unintuitively
named? From DDOC:

c.lowerBound(v)   Returns a range of all elements strictly less than v
c.upperBound(v)   Returns a range of all elements strictly greater than v.

So c.lowerBound(v) will return a range for which v is the .. upper bound
noninclusive. And c.upperBound(v) the lower bound noninclusive.

Over in the STL, we have set::lower_bound and set::upper_bound, but
these are different in two ways

1) they return iterators
1.a) lower_bound is kinda meant to be a starting iterator, upper_bound
is kinda meant to be a ending iterator. kinda. Anyways:
c.lower_bound(v)  points to the first element less than or equal to v
c.upper_bound(v)  points to the first element strictly greater than v

So iterators are like these half-ranges, they aren't really useful by
themselves but you can pair them up and stuff.

Consider the ordered set C = {1,2,3,4,5}.

if you want the range [3,inf) intersect C, over in the STL you'd use the
pair (C.lower_bound(3), C.end()). Here, I guess you'd use
C.upperBound(2). Similarly,

(-inf, 3) -> (C.begin(), C.lower_bound(3))   vs   C.lowerBound(3)
(-inf, 3] -> (C.begin(), C.upper_bound(3))   vs   C.lowerBound(4)
(3, inf)  -> (C.upper_bound(3), C.end())     vs   C.upperBound(3)
[3, inf)  -> (C.lower_bound(3), C.end())     vs   C.upperBound(4)  //
yeah, well I couldn't find it in the text above quickly enough
[2, 4)    -> (C.lower_bound(2), C.lower_bound(4))    vs     ???
(2, 4)    -> (C.upper_bound(2), C.lower_bound(4))    vs     ???
[2, 4]    -> (C.lower_bound(2), C.upper_bound(4))    vs     ???
(2, 4]    -> (C.upper_bound(2), C.upper_bound(4))    vs     ???

So now two things emerge that I wasn't exactly going for when I started
this rumination, but hey:

1) lowerBound and upperBound are actually not especially useful as they
capture only a small subset of the functionality of lower_bound and
upper_bound

2) lower_bound and upper_bound are versatile, but rather unreadable

3) D can do better than this.

Suppose instead of having lowerBound and upperBound we have

bound!(string boundary = "[")(one_end)  // possible: "[","(","]",")"
bounds!(string boundaries = "[]")(lower, upper) // kinda like
std.random.uniform

Anyways, back to the topic at hand.

I don't see much if any correlation between STL's lower bound and upper
bound and std.container's, and I don't see much use of the current
names/semantics except for confusing people, so I think at the very
least the names should be changed to something like

belowBound
aboveBound

Am I missing anything?
```
Feb 19 2012
```Note: I have written the following by ignoring the RedBlackTree in the
title. I have been thinking about std.range.lowerBound, but I think they
have the same semantics.

On 02/19/2012 01:44 PM, Ellery Newcomer wrote:
Is it just me or are lowerBound and upperBound really unintuitively
named? From DDOC:

Perhaps. Though I have grown to appreciate historical accidents in
general. They give character to everything. :)

c.lowerBound(v) Returns a range of all elements strictly less than v
c.upperBound(v) Returns a range of all elements strictly greater than v.

So c.lowerBound(v) will return a range for which v is the .. upper bound
noninclusive. And c.upperBound(v) the lower bound noninclusive.

Over in the STL, we have set::lower_bound and set::upper_bound, but
these are different in two ways

1) they return iterators
1.a) lower_bound is kinda meant to be a starting iterator,

If we go with the convention of open-ended ranges, lower_bound can be
seen as the end iterator. So, the pair of c.begin() and c.lower_bound()
is the equivalent of C.lowerBound().

upper_bound
is kinda meant to be a ending iterator. kinda.

With the same logic above, the pair of c.upper_bound() and c.end() make
another range where c.upper_bound() is included in the range. And that
is the equivalent of C.upperBound()

That's how I have been seeing lower_bound and upper_bound.

Anyways:
c.lower_bound(v) points to the first element less than or equal to v
c.upper_bound(v) points to the first element strictly greater than v

So iterators are like these half-ranges, they aren't really useful by
themselves but you can pair them up and stuff.

Consider the ordered set C = {1,2,3,4,5}.

if you want the range [3,inf) intersect C, over in the STL you'd use the
pair (C.lower_bound(3), C.end()).

Personally, I've never thought of lower_bound() as the beginning of a range.

Here, I guess you'd use
C.upperBound(2). Similarly,

(-inf, 3) -> (C.begin(), C.lower_bound(3)) vs C.lowerBound(3)
(-inf, 3] -> (C.begin(), C.upper_bound(3)) vs C.lowerBound(4)
(3, inf) -> (C.upper_bound(3), C.end()) vs C.upperBound(3)
[3, inf) -> (C.lower_bound(3), C.end()) vs C.upperBound(4) // yeah, well
I couldn't find it in the text above quickly enough
[2, 4) -> (C.lower_bound(2), C.lower_bound(4)) vs ???
(2, 4) -> (C.upper_bound(2), C.lower_bound(4)) vs ???
[2, 4] -> (C.lower_bound(2), C.upper_bound(4)) vs ???
(2, 4] -> (C.upper_bound(2), C.upper_bound(4)) vs ???

So now two things emerge that I wasn't exactly going for when I started
this rumination, but hey:

1) lowerBound and upperBound are actually not especially useful as they
capture only a small subset of the functionality of lower_bound and
upper_bound

Iterators look more capable because they are a lower-lever abstraction.
But I don't think closed-ended ranges are natural to C++ or D
programmers anyway, so we should exclude those cases.

Phobos has other ranges that provide what lowerBound() and
C.upperBound() seemingly lack. For example std.range.trisect() is very
useful.

2) lower_bound and upper_bound are versatile, but rather unreadable

I will again refer to Andrei's article:

http://www.informit.com/articles/printerfriendly.aspx?p=1407357

Andrei acknowledges the power of iterators under the heading
"Weaknesses" and points at some range solutions.

3) D can do better than this.

Suppose instead of having lowerBound and upperBound we have

bound!(string boundary = "[")(one_end) // possible: "[","(","]",")"
bounds!(string boundaries = "[]")(lower, upper) // kinda like
std.random.uniform

Yes, that looks powerful but open-ended'ness is the norm. (Except, when
we really want to include the T.max value. :-/)

Anyways, back to the topic at hand.

I don't see much if any correlation between STL's lower bound and upper
bound and std.container's, and I don't see much use of the current
names/semantics except for confusing people, so I think at the very
least the names should be changed to something like

belowBound
aboveBound

Am I missing anything?

They are valid points but I think it is because you are seeing
lower_bound and upper_bound more flexible than they are intended use. At
least that's always been my understanding.

Ali
```
Feb 19 2012    "Steven Schveighoffer" <schveiguy yahoo.com> writes:
```On Sun, 19 Feb 2012 16:44:05 -0500, Ellery Newcomer
<ellery-newcomer utulsa.edu> wrote:

Is it just me or are lowerBound and upperBound really unintuitively
named?

It's not just you.  Quoting from one of my proposed implementation of
std.container.RedBlackTree (I hope Andrei doesn't mind, but I have
included his response, which I think explains rather well the reasoning
behind the naming):

----------------------

The attached version has added upperBound(Elem e) and lowerBound(Elem e).

I found the docs to be confusing regarding upperBound and lowerBound.
According to the docs, lowerBound is supposed to return all keys less than
e, but wouldn't that make e the upper bound?  Ditto for upperBound.

Also, shouldn't one of these ranges actually include e?

In any case, I made lowerBound(e) return all elements >= e and
upperBound(e) returns all elements < e, that seemed like the most
intuitive.  Let me know if I'm wrong.

----------------------
Andrei's response:
----------------------

STL docs are written in a confusing manner but after you get used they are
pretty logical. The docs at
http://www.cplusplus.com/reference/stl/map/lower_bound/ say:

"Returns an iterator pointing to the first element in the container whose
key does not compare less than x (using the container's comparison
object), i.e. it is either equal or greater."

The idea is that everything in the range

[begin(), lower_bound(x))

is strictly less than x. Of course we need to return a range instead, and
I think we should return exactly the range above: all elements strictly
less than x.

Then upperBound would return all elements strictly greater than x.

Finally equalRange would return all elements neither less nor greater than
x.

The beauty of it is that the three ranges are disjoint and cover the map
completely.

----------------------

Note that dcollections uses slice notation instead of
upperBound/lowerBound, which I find vastly more intuitive.  But they are
not as powerful.

-Steve
```
Mar 05 2012