Skip to main content

Ext

wt_slice

Trait Ext 

Source 
pub trait Ext {
    type Item;


Show 13 methods    // 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;
    fn next_permutation(&mut self) -> bool
       where Self::Item: Ord;
    fn prev_permutation(&mut self) -> bool
       where Self::Item: Ord;
    fn apply_permutation(&mut self, permutation: &mut [isize]);
    fn apply_inverse_permutation(&mut self, permutation: &mut [isize]);

}
Expand description

Extends slice with fast operations on ordered slices.

Required Associated Types§

Source

type Item

Required Methods§

Source

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);
Source

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)));
Source

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));
Source

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);
Source

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)));
Source

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));
Source

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)));
}
Source

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)));
}
Source

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));
}
Source

fn next_permutation(&mut self) -> bool
where Self::Item: Ord,

Transforms the slice into the next permutation from the set of all permutations that are lexicographically ordered with respect to the natural order of T. Returns true if such permutation exists, otherwise transforms the range into the first permutation and returns false.

§Example:
let mut b = [2, 1, 3];
let mut v = Vec::new();
for _ in 0..6 {
    let x = b.next_permutation();
    v.push((x, b.to_vec()));
}
assert_eq!(v, &[(true, [2, 3, 1].to_vec()),
                (true, [3, 1, 2].to_vec()),
                (true, [3, 2, 1].to_vec()),
                (false, [1, 2, 3].to_vec()),
                (true, [1, 3, 2].to_vec()),
                (true, [2, 1, 3].to_vec())]);
Source

fn prev_permutation(&mut self) -> bool
where Self::Item: Ord,

Transforms the slice into the previous permutation from the set of all permutations that are lexicographically ordered with respect to the natural order of T. Returns true if such permutation exists, otherwise transforms the range into the last permutation and returns false.

§Example:
let mut b = [2, 1, 3];
let mut v = Vec::new();
for _ in 0..6 {
    let x = b.prev_permutation();
    v.push((x, b.to_vec()));
}
assert_eq!(v, &[(true, [1, 3, 2].to_vec()),
                (true, [1, 2, 3].to_vec()),
                (false, [3, 2, 1].to_vec()),
                (true, [3, 1, 2].to_vec()),
                (true, [2, 3, 1].to_vec()),
                (true, [2, 1, 3].to_vec())]);
Source

fn apply_permutation(&mut self, permutation: &mut [isize])

Applies permutation to the slice. For each element at index i the following holds:

new_self[i] == old_self[permutation[i]]

The transformation happens in O(N) time and O(1) space. permutation is mutated during the transformation but it is restored to its original state on return.

§Panics

This function panics if self and permutation do not have the same length or any value in permutation is not in 0..self.len().

§Example:
let mut b = ['d', 'a', 'c', 'b'];
let mut p = [1, 3, 2, 0];
b.apply_permutation(&mut p);
assert_eq!(b, ['a', 'b', 'c', 'd']);
assert_eq!(p, [1, 3, 2, 0]);
Source

fn apply_inverse_permutation(&mut self, permutation: &mut [isize])

Applies the inverse of permutation to the slice. For each element at index i the following holds:

new_self[permutation[i]] == old_self[i]

The transformation happens in O(N) time and O(1) space. permutation is mutated during the transformation but it is restored to its original state on return.

§Panics

This function panics if self and permutation do not have the same length or any value in permutation is not in 0..self.len().

§Example:
let mut b = ['d', 'a', 'c', 'b'];
let mut p = [3, 0, 2, 1];
b.apply_inverse_permutation(&mut p);
assert_eq!(b, ['a', 'b', 'c', 'd']);
assert_eq!(p, [3, 0, 2, 1]);

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety".

Implementations on Foreign Types§

Source§

impl<T> Ext for [T]

Source§

type Item = T

Source§

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

Source§

fn lower_bound_by<'a, F>(&'a self, f: F) -> usize
where F: FnMut(&'a Self::Item) -> Ordering,

Source§

fn lower_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize
where F: FnMut(&'a Self::Item) -> K, K: Ord,

Source§

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

Source§

fn upper_bound_by<'a, F>(&'a self, f: F) -> usize
where F: FnMut(&'a Self::Item) -> Ordering,

Source§

fn upper_bound_by_key<'a, K, F>(&'a self, k: &K, f: F) -> usize
where F: FnMut(&'a Self::Item) -> K, K: Ord,

Source§

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

Source§

fn equal_range_by<'a, F>(&'a self, f: F) -> Range<usize>
where F: FnMut(&'a Self::Item) -> Ordering,

Source§

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,

Source§

fn next_permutation(&mut self) -> bool
where Self::Item: Ord,

Source§

fn prev_permutation(&mut self) -> bool
where Self::Item: Ord,

Source§

fn apply_permutation(&mut self, perm: &mut [isize])

Source§

fn apply_inverse_permutation(&mut self, perm: &mut [isize])

Implementors§