[−][src]Trait superslice::Ext

pub trait Ext {
    type Item;
    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]);
}

Extends slice with fast operations on ordered slices.

Associated Types

type Item

Loading content...

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

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())]);

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())]);

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

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]);
Loading content...

Implementations on Foreign Types

impl<T> Ext for [T][src]

type Item = T

Loading content...

Implementors

Loading content...