Trait eytzinger::SliceExt [−][src]
Eytzinger extension methods for slices.
Required methods
fn eytzingerize<P: Permutator<T, PermutationGenerator>>(
&mut self,
permutator: &mut P
)
[src]
&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>,
[src]
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,
[src]
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,
[src]
&'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);
Implementations on Foreign Types
impl<T> SliceExt<T> for [T]
[src]
fn eytzingerize<P: Permutator<T, PermutationGenerator>>(
&mut self,
permutator: &mut P
)
[src]
&mut self,
permutator: &mut P
)
fn eytzinger_search<Q: ?Sized>(&self, x: &Q) -> Option<usize> where
Q: Ord,
T: Borrow<Q>,
[src]
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,
[src]
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,
[src]
&'a self,
b: &Q,
f: F
) -> Option<usize> where
B: Borrow<Q>,
F: FnMut(&'a T) -> B,
Q: Ord,
T: 'a,