View mode: basic / threaded / horizontal-split · Log in · Help
February 19, 2012
RedBlackTree.lowerBound
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?
February 19, 2012
Re: RedBlackTree.lowerBound
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
March 05, 2012
Re: RedBlackTree.lowerBound
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
Top | Discussion index | About this forum | D home