Repository navigation
Add lower_bound, upper_bound and equal_range for slices where T: Ord to complement binary_search #2184
Description
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) -> Bupper_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) -> Bequal_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) -> BReacted by Arthur Silva, bluss, Ruud van Asseldonk, Clément Renault, Vlad Frolov, kgtkr, Michael Partheil, Tyler Neely, Vlad-Shcherbina, Alex Kladov and 64 more
Reacted by Alex Kladov, Anders Musikka, Gurwinder Singh, SOFe (Jonathan Chan Kwan Yin), Luis Miguel Báez, dpc, sym233, Hiroshi Kori, João Marcos, Ivan Mikhnovich and 5 more
Reacted by Felipe S. S. Schneider and Svetlin Zarev
Reacted by shionryuu and Felipe S. S. Schneider
Activity
ranma42 commentedon Oct 20, 2017
Is is more convenient to have an
Optionreturn 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
Rangeinequal_range*?alkis commentedon Oct 20, 2017
Returning a
Rangeinequal_rangesounds great. I updated the original post.I don't understand the question about
Option. What should we be the return types forupper_boundandlower_bound?ranma42 commentedon Oct 20, 2017
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 commentedon Oct 20, 2017
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 commentedon Oct 21, 2017
I think
0would not be a suitable substitute forNoneif 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 return0, because21is not "the first element in the sorted slice that is not less than"26. Instead I think returning3would be ok, as it would correctly indicate that we could find no element that is not less then26.A similar reasoning also applies to
upper_bound. This approach could be summarized in the following table:Range(0, 0))Range(0, 1)Range(1, 1))None)Range(1, 3)None)None)Range(3, 3))Note that while the current definition of
equal_rangeallows 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 thexelements, even when there are none.alkis commentedon Oct 21, 2017
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 whatlower_boundandupper_boundreturn.ranma42 commentedon Oct 21, 2017
Yep, the examples match my expectations :)
Some nits (I think most of these are basically just typos):
upper_boundis still marked as returningSome<usize>{lower,upper}_boundstill state "If such an element exists it returnsSomewith the index of such element. Otherwise it returnsNone.". 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."equal_rangedoes not match returning(lower_bound(x), upper_bound(x))(12does not exist in the example slice, yet theequal_rangewould not be(0, 0)nor(5, 5)).Some proposals for an alternative wording of the description (very slice-oriented):
lower_boundreturns the indexasuch that all elements inself[..a]are less thanxand all elements inself[a..]are greater or equal tox.upper_boundreturns the indexbsuch that all elements inself[..b]are less or equal toxand all elements inself[b..]are greater thanx.equal_rangereturns theRangea..bsuch that all elements inself[..a]are less thanx, all elements inself[a..b]are equal tox, and all elements inself[b..]are greater thanx.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_rangeand{lower,upper}_bound.alkis commentedon Oct 21, 2017
I like the new wording. Incorporated.
scottmcm commentedon Oct 25, 2017
I think "any empty range" is unfortunate, because there's very useful information that throws away.
The other use of
equal_rangeis, with an obviously-placeholder name,That return value would have the same
startandendasequal_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_boundandlower_boundare the.startand.endof theequal_rangereturn value (just calculated a bit more efficiently).arthurprs commentedon Oct 25, 2017
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 commentedon Oct 25, 2017
@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 commentedon Oct 25, 2017
@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 commentedon Oct 25, 2017
@arthurprs this is what it will return given the description. The examples also show these cases.
arthurprs commentedon Oct 25, 2017
I see, it's just that
fn upper_bound(&self, x: &T) -> Option<usize>still has theOption<>in the result type.alkis commentedon Oct 25, 2017
Fixed.
19 remaining items
Amanieu commentedon Feb 22, 2019
You need to think of the bounds in terms of a range of values that you are interested in. So
lower_boundmeans "the range of values that I am interested in starts at 92 (inclusive/exclusive depending on the bound), give me the index of the first value in that range".The definition for
upper_boundis similar: "the range of values that I am interested in ends at 173 (inclusive/exclusive), give me the index of the value in that range".Ixrec commentedon Feb 22, 2019
Interesting. I think that means the names are off.
lower_bound(x)seems like it'd mean the lower bound of values equal to x. If what we want is the first x value, then we should just call the method something obvious likefirst(x).But "upper bound"/"upper bound (inclusive)"/"lower bound (exclusive)" apparently means "the first non-x value after an x value" which is a super weird concept I don't know of a concise name for. Hm...
spacejam commentedon Feb 22, 2019
For a couple concrete "point" query examples I'm working with, consider a B+ tree where pointers to children are stored in a sorted slice as
(separator_key, child_node)where theseparator_keyis the lowest inclusive bound of values that may be present in that node. While traversing the tree, we need to find the child with the highestseparator_keythat is less than or equal to the key being searched for in the tree.In general, I find all of the below use cases useful for working with versioned trees:
All of the above can be expressed with iterators, but that prevents their compatibility with
binary_search*.matklad commentedon Feb 22, 2019
I believe that this is expressible with bound-less methods like this:
The first two seem trickier than ideal, but I don't think they can be better expressed with
Boundsemantics of #2184 (comment) (which I believe is what @Amanieu proposes and which coinsides with my intuition). The reason is that addingBounddoes not change the set of indices you can get, you still need to-1somehow.The version of @Ixrec (#2184 (comment)) does make this easier though.
On the meta level, if we can come up with two semantics for
Boundwhich are differ by1, that probably means thatBoundwould be a problematic API.Amanieu commentedon Feb 22, 2019
It's not just a simple
-1. If you have multiple identical values then the difference between an inclusive and exclusive lower bound can be more than 1 element:matklad commentedon Feb 22, 2019
@Amanieu sorry, I wasn't clear, the -1 referred to the difference between #2184 (comment) and #2184 (comment). That is, it's the difference between semantics one might thing
Boundhas, not the difference betweenLIandLE(which can be arbitrary in one semantics and zero or one in another semantics) .avl commentedon Sep 18, 2019
It would be nice if this could move forward somehow. I was surprised that there was a binary_search in std, but that it apparently selects an element at random if there are multiple elements with the same value.
VillSnow commentedon Jun 18, 2020
C++ has partition_point. It has clear definition like
I can use this when I cannot remember the definition of lower/upper_bound :)
It is basic and primitive edition of lower/upper_bound and I want it in Rust rather than lower/upper_bound. (both is great)
matklad commentedon Jun 19, 2020
@VillSnow this sounds like a great idea, as this is indeed more general than binary search, and has trivial design space. Would you like to send a PR to libcore to add this? I am not on the libs team, but seems like this API can be accepted without too much deliberation:
As basic check, rust also use
partitionandpartition_in_place, so cargo-culting the name from C++ seems fine.VillSnow commentedon Jun 21, 2020
@matklad
It would be my first PR in my life. How can I send a PR?
I cloned rust-lang/rust, passed
x.py check, implement my partition_point and passedx.py checkagain. (and accidentally my Linux machine downs so it tooks a bit time to recover :_(done)my understanding is; first make a issue "Traking issue for partition_point", set issue number of unstable attribute and send PR?
How to set feature of unstable attribute? Can I make as I like?
VillSnow/rust@4c8ce48
Rollup merge of rust-lang#73577 - VillSnow:master, r=Amanieu
kartva commentedon Jun 3, 2021
Maybe this issue can be closed, now that this has merged?
matklad commentedon Oct 22, 2022
I think
equal_rangeis the next thing we can obviously just do and perhaps also should do. It's not as frequently needed as partition point, but: