Trait Ext

pub trait Ext {
    type Item;

    // Required methods
    fn lower_bound(&self, x: &Self::Item) -> usize
       where Self::Item: Ord;
    fn lower_bound_by<'a, F>(&'a self, f: F) -> usize
       where F: FnMut(&'a Self::Item) -> Ordering;
    fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize
       where F: FnMut(&'a Self::Item) -> K,
             K: Ord;
    fn upper_bound(&self, x: &Self::Item) -> usize
       where Self::Item: Ord;
    fn upper_bound_by<'a, F>(&'a self, f: F) -> usize
       where F: FnMut(&'a Self::Item) -> Ordering;
    fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize
       where F: FnMut(&'a Self::Item) -> K,
             K: Ord;
    fn equal_range(&self, x: &Self::Item) -> Range<usize>
       where Self::Item: Ord;
    fn equal_range_by<'a, F>(&'a self, f: F) -> Range<usize>
       where F: FnMut(&'a Self::Item) -> Ordering;
    fn equal_range_by_key<'a, K, F>(&'a self, k: &K, f: F) -> Range<usize>
       where F: FnMut(&'a Self::Item) -> K,
             K: Ord;
}

Extends slice with fast operations on ordered slices.

Required Associated Types

type Item

Required Methods

fn lower_bound(&self, x: &Self::Item) -> usize

where Self::Item: Ord,

Returns the index i pointing to the first element in the ordered slice that is not less than x.

The slice MUST be ordered by the order defined by its elements.

Example:

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_by<'a, F>(&'a self, f: F) -> usize

where F: FnMut(&'a Self::Item) -> Ordering,

Returns the index i pointing to the first element in the ordered slice for which f(self[i]) != Less.

The slice MUST be ordered by the order defined by the comparator function. The comparator function should take an element and return Ordering that is consistent with the ordering of the slice.

Example:

let b = [1, 2, 3, 6, 9, 9];
assert_eq!(b.lower_bound(&3), b.lower_bound_by(|x| x.cmp(&3)));

fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize

where F: FnMut(&'a Self::Item) -> K, K: Ord,

Returns the index i pointing to the first element in the ordered slice for which f(self[i]) >= k.

The slice MUST be ordered by the order defined by the keys of its elements.

Example:

let b = [1, 2, 3, 6, 9, 9];
assert_eq!(b.lower_bound(&3), b.lower_bound_by_key(&6, |x| x * 2));

fn upper_bound(&self, x: &Self::Item) -> usize

where Self::Item: Ord,

Returns the index i pointing to the first element in the ordered slice that is greater than x.

The slice MUST be ordered by the order defined by its elements.

Example:

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_by<'a, F>(&'a self, f: F) -> usize

where F: FnMut(&'a Self::Item) -> Ordering,

Returns the index i pointing to the first element in the ordered slice for which f(self[i]) == Greater.

The slice MUST be ordered by the order defined by the comparator function. The comparator function should take an element and return Ordering that is consistent with the ordering of the slice.

Example:

let b = [1, 2, 3, 6, 9, 9];
assert_eq!(b.upper_bound(&3), b.upper_bound_by(|x| x.cmp(&3)));

fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize

where F: FnMut(&'a Self::Item) -> K, K: Ord,

Returns the index i pointing to the first element in the ordered slice for which f(self[i]) > k.

The slice MUST be ordered by the order defined by the keys of its elements.

Example:

let b = [1, 2, 3, 6, 9, 9];
assert_eq!(b.lower_bound(&3), b.lower_bound_by_key(&6, |x| x * 2));

fn equal_range(&self, x: &Self::Item) -> Range<usize>

where Self::Item: Ord,

Returns the Range a..b such that all elements in self[a..b] are equal to x.

The slice MUST be ordered by the order defined by its elements.

Example:

let b = [10, 11, 13, 13, 15];
for i in 9..17 {
    assert_eq!(b.equal_range(&i), (b.lower_bound(&i)..b.upper_bound(&i)));
}

fn equal_range_by<'a, F>(&'a self, f: F) -> Range<usize>

where F: FnMut(&'a Self::Item) -> Ordering,

Returns the Range a..b such that for all elements e in self[a..b] f(e) == Equal.

The slice MUST be ordered by the order defined by the comparator function. The comparator function should take an element and return Ordering that is consistent with the ordering of the slice.

Example:

let b = [10, 11, 13, 13, 15];
for i in 9..17 {
    assert_eq!(b.equal_range(&i), b.equal_range_by(|x| x.cmp(&i)));
}

fn equal_range_by_key<'a, K, F>(&'a self, k: &K, f: F) -> Range<usize>

where F: FnMut(&'a Self::Item) -> K, K: Ord,

Returns the Range a..b such that for all elements e in self[a..b] f(e) == k.

The slice MUST be ordered by the order defined by the keys of its elements.

Example:

let b = [10, 11, 13, 13, 15];
for i in 9..17 {
    let i2 = i * 2;
    assert_eq!(b.equal_range(&i), b.equal_range_by_key(&i2, |x| x * 2));
}

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementations on Foreign Types

impl<T> Ext for [T]

type Item = T

fn lower_bound(&self, x: &Self::Item) -> usize

where T: Ord,

fn lower_bound_by<'a, F>(&'a self, f: F) -> usize

where F: FnMut(&'a Self::Item) -> Ordering,

fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize

where F: FnMut(&'a Self::Item) -> K, K: Ord,

fn upper_bound(&self, x: &Self::Item) -> usize

where T: Ord,

fn upper_bound_by<'a, F>(&'a self, f: F) -> usize

where F: FnMut(&'a Self::Item) -> Ordering,

fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize

where F: FnMut(&'a Self::Item) -> K, K: Ord,

fn equal_range(&self, x: &Self::Item) -> Range<usize>

where T: Ord,

fn equal_range_by<'a, F>(&'a self, f: F) -> Range<usize>

where F: FnMut(&'a Self::Item) -> Ordering,

fn equal_range_by_key<'a, K, F>(&'a self, k: &K, f: F) -> Range<usize>

where F: FnMut(&'a Self::Item) -> K, K: Ord,

Implementors