Trait eytzinger::SliceExt

pub trait SliceExt<T> {
    fn eytzingerize<P: Permutator<T, PermutationGenerator>>(
        &mut self, 
        permutator: &mut P
    );
    fn eytzinger_search<Q: ?Sized>(&self, x: &Q) -> Option<usize>
    where
        Q: Ord,
        T: Borrow<Q>;
    fn eytzinger_search_by<'a, F>(&'a self, f: F) -> Option<usize>
    where
        F: FnMut(&'a T) -> Ordering,
        T: 'a;
    fn eytzinger_search_by_key<'a, B, F, Q: ?Sized>(
        &'a self, 
        b: &Q, 
        f: F
    ) -> Option<usize>
    where
        B: Borrow<Q>,
        F: FnMut(&'a T) -> B,
        Q: Ord,
        T: 'a;
}

Eytzinger extension methods for slices.

Required methods

fn eytzingerize<P: Permutator<T, PermutationGenerator>>(
    &mut self,
    permutator: &mut P
)

Converts an already sorted array to its eytzinger representation.

Example

use eytzinger::SliceExt;
let mut data = [0, 1, 2, 3, 4, 5, 6];
data.eytzingerize(&mut eytzinger::permutation::InplacePermutator);
assert_eq!(data, [3, 1, 5, 0, 2, 4, 6]);

fn eytzinger_search<Q: ?Sized>(&self, x: &Q) -> Option<usize> where
    Q: Ord,
    T: Borrow<Q>, 

Binary searches this eytzinger slice for a given element.

If the value is found then Some is returned, containing the index of the matching element; if the value is not found then None is returned.

Example

use eytzinger::SliceExt;
let s = [3, 1, 5, 0, 2, 4, 6];
assert_eq!(s.eytzinger_search(&5), Some(2));
assert_eq!(s.eytzinger_search(&6), Some(6));
assert_eq!(s.eytzinger_search(&7), None);

fn eytzinger_search_by<'a, F>(&'a self, f: F) -> Option<usize> where
    F: FnMut(&'a T) -> Ordering,
    T: 'a, 

Binary searches this eytzinger slice with a comparator function.

The comparator function should implement an order consistent with the sort order of the underlying eytzinger slice, returning an order code that indicates whether its argument is Less, Equal or Greater than the desired target.

If a matching value is found then Some is returned, containing the index of the matching element; if no match is found then None is returned.

Examples

use eytzinger::SliceExt;
let s = [3, 1, 5, 0, 2, 4, 6];
assert_eq!(s.eytzinger_search_by(|x| x.cmp(&5)), Some(2));
assert_eq!(s.eytzinger_search_by(|x| x.cmp(&6)), Some(6));
assert_eq!(s.eytzinger_search_by(|x| x.cmp(&7)), None);

fn eytzinger_search_by_key<'a, B, F, Q: ?Sized>(
    &'a self,
    b: &Q,
    f: F
) -> Option<usize> where
    B: Borrow<Q>,
    F: FnMut(&'a T) -> B,
    Q: Ord,
    T: 'a, 

Binary searches this sorted slice with a key extraction function.

Assumes that the slice is eytzinger-sorted by the key, for instance with slice::sort_by_key combined with eytzinger::eytzingerize using the same key extraction function.

If a matching value is found then Some is returned, containing the index of the matching element; if no match is found then None is returned.

Examples

use eytzinger::SliceExt;
let s = [(3, 'd'), (1, 'b'), (5, 'f'), (0, 'a'), (2, 'c'), (4, 'e'), (6, 'g')];
assert_eq!(s.eytzinger_search_by_key(&'f', |&(_, b)| b), Some(2));
assert_eq!(s.eytzinger_search_by_key(&'g', |&(_, b)| b), Some(6));
assert_eq!(s.eytzinger_search_by_key(&'x', |&(_, b)| b), None);

Loading content...

Implementations on Foreign Types

impl<T> SliceExt<T> for [T]

fn eytzingerize<P: Permutator<T, PermutationGenerator>>(
    &mut self,
    permutator: &mut P
)

fn eytzinger_search<Q: ?Sized>(&self, x: &Q) -> Option<usize> where
    Q: Ord,
    T: Borrow<Q>, 

fn eytzinger_search_by<'a, F>(&'a self, f: F) -> Option<usize> where
    F: FnMut(&'a T) -> Ordering,
    T: 'a, 

fn eytzinger_search_by_key<'a, B, F, Q: ?Sized>(
    &'a self,
    b: &Q,
    f: F
) -> Option<usize> where
    B: Borrow<Q>,
    F: FnMut(&'a T) -> B,
    Q: Ord,
    T: 'a, 

Loading content...

Implementors

Loading content...