RedBlackTree.lowerBound

[Ali Çehreli]

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