Replace/Supplement ImmutableVector::bsearch with lower_bound and upper_bound

[kennytm]

Currently we have ImmutableVector::bsearch() and ImmutableOrdVector::bsearch_elem(), which uses binary search to find an element (I’ll use the term needle in the following post). It returns None if the needle is not found.

The problems:

1) The major problem is that often we would like to know the smallest index of an object “just next to” the needle, to establish a limit / threshold etc.

let container_sizes = [
    ("small", 20i), 
    ("medium", 35), 
    ("large", 75), 
    ("huge", 120),
];
let smallest_container_index = 
    container_sizes.bsearch(|&(_, i)| i.cmp(&40));
println!("{}", smallest_container_index);
// Wants to get index of "large", got None instead which provides no
// information.

2) And a minor annoyance is that when there is a range of values equals to the needle, it’s unspecified which one will be returned:

let a = [1i, 2, 2, 2, 2, 2, 2, 2, 3];
println!("{}", a.bsearch_elem(&2)); 
// Currently prints Some(4), but anything from Some(1) to Some(7) may 
// be possible.

In C++ we solve these tasks with std::upper_bound and std::lower_bound. Similarly we have bisect.bisect_left and .bisect_right in Python.

---

There are several ways to implement this. The most obvious way is to directly port the C++ method signatures into Rust:

/// Returns the smallest index `i` in `self` such that `f(self[i])` 
/// is Greater or Equal.
///
/// If `f` is Less for all elements, this method returns `self.len()`.
fn lower_bound(&self, f: |&T| -> Ordering) -> uint;

/// Returns the smallest index `i` in `self` such that `f(self[i])` 
/// is Greater.
///
/// If `f` is Less or Equal for all elements, this method returns
/// `self.len()`.
fn upper_bound(&self, f: |&T| -> Ordering) -> uint;

and the following methods to ImmutableOrdVector trait:

fn lower_bound_elem(&self, t: &T) -> uint;
fn upper_bound_elem(&self, t: &T) -> uint;

(I believe bsearch() can then be implemented in terms of lower_bound() in the trait, but I can’t make the compiler happy about the moved function yet.)

Suggestions?

[pczarn]

+1 if this proposal could help in my case. I wanted to retrieve a needle at index i with a random number in range: vec[i - 1].end_idx <= rand < vec[i].end_idx. I had to reimplement bsearch:

fn bsearch<'a>(&'a self, idx: uint) -> Option<&'a T> {
    let mut base: uint = 0;
    let mut lim: uint = self.inner.len();

    while lim != 0 {
        let ix = base + (lim >> 1);
        if idx > self.inner[ix].end_idx {
            base = ix + 1;
            lim -= 1;
        } else if ix == 0 || idx >= self.inner[ix - 1].end_idx {
            return Some(&self.inner[ix].item);
        }
        lim >>= 1;
    }
    Some(&self.inner[0].item)
}