Add `lower_bound`, `upper_bound` and `equal_range` for slices where T: Ord to complement `binary_search`

[alkis]

Motivation

Fom discussion on rust-lang/rust#45333.

There is demand for lower_bound, upper_bound and equal_range especially for sorted sequences of non-unique elements. In such sequences the aforementioned operations are more interesting and useful than binary_search. The addition of these three ops will complement the support of sorted slices in the standard library.

Proposed APIs

lower_bound

/// Finds the first element in the sorted slice that is _not less_ than `x`.
///
/// Returns the index `a` such that all elements in `self[..a]` are less than `x` and all elements in `self[a..]` are greater or equal to `x`.
///
/// # Examples
/// ```
/// let a = [10, 11, 13, 13, 15];
/// assert_eq!(a.lower_bound(9), 0);
/// assert_eq!(a.lower_bound(10), 0);
/// assert_eq!(a.lower_bound(11), 1);
/// assert_eq!(a.lower_bound(12), 2);
/// assert_eq!(a.lower_bound(13), 2);
/// assert_eq!(a.lower_bound(14), 4);
/// assert_eq!(a.lower_bound(15), 4);
/// assert_eq!(a.lower_bound(16), 5);
/// ```
fn lower_bound(&self, x: &T) -> usize 
where
    T: Ord;

/// `lower_bound` with a comparator.
fn lower_bound_by<'a, F>(&'a self, f: F) -> usize
where
    F: FnMut(&'a T) -> Ordering;

/// `lower_bound` with key extraction.
fn lower_bound_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> usize
where
    B: Ord,
    F: FnMut(&'a T) -> B

upper_bound

/// Finds the first element in the sorted slice that is _greater_ than `x`.
///
/// Returns the index `a` such that all elements in `self[..a]` are less or equal to `x` and all elements in `self[a..]` are greater than `x`.
///
/// # Examples
/// ```
/// let a = [10, 11, 13, 13, 15];
/// assert_eq!(a.upper_bound(9), 0);
/// assert_eq!(a.upper_bound(10), 1);
/// assert_eq!(a.upper_bound(11), 2);
/// assert_eq!(a.upper_bound(12), 2);
/// assert_eq!(a.upper_bound(13), 4);
/// assert_eq!(a.upper_bound(14), 4);
/// assert_eq!(a.upper_bound(15), 5);
/// assert_eq!(a.upper_bound(16), 5);
/// ```
fn upper_bound(&self, x: &T) -> usize
where
    T: Ord;

/// `upper_bound` with a comparator.
fn upper_bound_by<'a, F>(&'a self, f: F) -> usize
where
    F: FnMut(&'a T) -> Ordering;

/// `upper_bound` with key extraction.
fn upper_bound_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> usize
where
    B: Ord,
    F: FnMut(&'a T) -> B

equal_range

/// Finds all elements _equal_ to `x`.
///
/// Returns the `Range` `a..b` such that all elements in `self[..a]` are less than `x`, all elements in `self[a..b]` are equal to `x`, and all elements in `self[b..]` are greater than `x`.
///
/// # Examples
/// ```
/// let a = [10, 11, 13, 13, 15];
///  for i in (9..17) {
///    assert_eq!(a.equal_range(i), (a.lower_bound(i), a.upper_bound(i)));
///  }
/// ```

fn equal_range(&self, x: &T) -> std::ops::Range<usize> 
where
    T: Ord;

/// `equal_range` with a comparator.
fn equal_range_by<'a, F>(&'a self, f: F) -> std::ops::Range<usize> 
where
    F: FnMut(&'a T) -> Ordering;

/// `equal_range` with key extraction.
fn equal_range_by_key<'a, B, F>(&'a self, b: &B, f: F)  -> std::ops::Range<usize> 
where
    B: Ord,
    F: FnMut(&'a T) -> B

[ranma42]

Is is more convenient to have an Option return value or to just return the appropriate slice boundary?
There are use cases for both, it is not clear to me which one would be more ergonomic.
Also, how about returning a Range in equal_range*?

[alkis]

Returning a Range in equal_range sounds great. I updated the original post.

I don't understand the question about Option. What should we be the return types for upper_bound and lower_bound?

[ranma42]

Since they are looking for "the first element in the sorted slice that is ..." I would return the length of the slice. This would make it easy to use these function to find the position that would be the insertion point of an element so that the order is preserved (and the element is added as the first/last of a streak of elements that compare as equal).
I am unsure if my explanation is comprehensible... I will check it again tomorrow morning XD

[alkis]

We return the length of the slice or the position of the lower bound? What happens if the element does not exist (past the end of the slice)? Do you think returning 0 for lower bound and self.len() for upper bound makes sense in that case?

[ranma42]

I think 0 would not be a suitable substitute for None if the slice is not empty, because it would identify an element that does not satisfy the property.

For example, [21, 23, 23].lower_bound(26) should not return 0, because 21 is not "the first element in the sorted slice that is not less than" 26. Instead I think returning 3 would be ok, as it would correctly indicate that we could find no element that is not less then 26.

A similar reasoning also applies to upper_bound. This approach could be summarized in the following table:

x	lower_bound	upper_bound	equal_range
20-	0	0	any empty range (ex: Range(0, 0))
21	0	1	Range(0, 1)
22	1	1	any empty range (ex: Range(1, 1))
23	1	3 (or None)	Range(1, 3)
24+	3 (or None)	3 (or None)	any empty range (ex: Range(3, 3))

Note that while the current definition of equal_range allows for any empty range to be returned, we might constrain it more and require that it always returns the range that corresponds to the would-be position of the x elements, even when there are none.

[alkis]

Thanks Andrea. I updated the code above with examples. Let me know if you agree.

equal_range(x) is equivalent to (lower_bound(x), upper_bound(x)) so everything just follows if we nail down what lower_bound and upper_bound return.

[ranma42]

Yep, the examples match my expectations :)

Some nits (I think most of these are basically just typos):

• upper_bound is still marked as returning Some<usize>
• the descriptions for {lower,upper}_bound still state "If such an element exists it returns Some with the index of such element. Otherwise it returns None.". I would expect something like "If such an element exists it returns the index of such element. Otherwise it returns the length of the slice."
• the description for equal_range does not match returning (lower_bound(x), upper_bound(x)) (12 does not exist in the example slice, yet the equal_range would not be (0, 0) nor (5, 5)).

Some proposals for an alternative wording of the description (very slice-oriented):

• lower_bound returns the index a such that all elements in self[..a] are less than x and all elements in self[a..] are greater or equal to x.
• upper_bound returns the index b such that all elements in self[..b] are less or equal to x and all elements in self[b..] are greater than x.
• equal_range returns the Range a..b such that all elements in self[..a] are less than x, all elements in self[a..b] are equal to x, and all elements in self[b..] are greater than x.

This wording is more verbose, but it shows why the "element not found" is not actually a special case for these functions and highlights in a very direct way the relationship between equal_range and {lower,upper}_bound.

[alkis]

I like the new wording. Incorporated.

[scottmcm]

I think "any empty range" is unfortunate, because there's very useful information that throws away.

The other use of equal_range is, with an obviously-placeholder name,

/// Returns the range of positions at which `x` could be inserted such
/// that the sequence would remain sorted.
fn where_to_insert_in_sorted(&self, x: &T) -> RangeInclusive<usize>;

That return value would have the same start and end as equal_range. (C++ avoids this distinction by returning a pair that can be considered as [a,b) for "the items" and [a,b] for "the insertion positions".)

Phrased differently, I think it's important that upper_bound and lower_bound are the .start and .end of the equal_range return value (just calculated a bit more efficiently).

[arthurprs]

Isn't there any meaningful data to be returned from a "not found" lower_bound? Can't it behave similar to binary_search?

Same for upper_bound.

[alkis]

@scottmcm equal_range does not return "any empty range". What is returned is defined as your first suggestion.

@arthurprs can you give an example?

[arthurprs]

@alkis nevermind, that was a confusion moment.

I think lower_bound should return 0 and upper_bound should return slice.len() if no range can be found. Same as you proposed on #2184 (comment)

[alkis]

@arthurprs this is what it will return given the description. The examples also show these cases.

[arthurprs]

I see, it's just that fn upper_bound(&self, x: &T) -> Option<usize> still has the Option<> in the result type.

[alkis]

Fixed.