Trait indxvec::Search

pub trait Search<T> {
    // Required methods
    fn binary_any(&self, cmpr: &mut impl FnMut(&T) -> Ordering) -> (T, Range<T>);
    fn binary_all(
        &self,
        cmpr: &mut impl FnMut(&T) -> Ordering,
        ascending: bool
    ) -> Range<T>;
}

Lower level binary search algoritms implemented on RangeInclusive

Required Methods

fn binary_any(&self, cmpr: &mut impl FnMut(&T) -> Ordering) -> (T, Range<T>)

Unchecked first hit or insert order, and the final search range. The comparator must take into account the data order. Used internally by binary_all

fn binary_all( &self, cmpr: &mut impl FnMut(&T) -> Ordering, ascending: bool ) -> Range<T>

General Binary Search using a closure to sample and compare data, data order must be explicitly specified

Implementations on Foreign Types

impl<T> Search<T> for RangeInclusive<T>where T: PartialOrd + Copy + From<u8> + Add<Output = T> + Sub<Output = T> + Div<Output = T> + Mul<Output = T>,

fn binary_any(&self, cmpr: &mut impl FnMut(&T) -> Ordering) -> (T, Range<T>)

Binary search for an index of any item matching the target.
Searches specified RangeInclusive.
Comparator closure cmpr is comparing against the target specified (captured) in it. The sort order of the data can be either ascending or descending but it must be reflected by cmpr. Returns the index of the first hit that is PartiallyEqual to target and its last enclosing interval lo..=hi.
When the target is not found, then (ip, lo..=ip) is returned, where ip is the target’s insert position and lo is the last lower bound. The (indexing) range values can be of any generic type T satisfying the listed trait bounds. Typically usize for searching efficiently in-memory, u128 for searching whole disks or internet, or f64 for solving nonlinear equations.

fn binary_all( &self, cmpr: &mut impl FnMut(&T) -> Ordering, ascending: bool ) -> Range<T>

General Binary Search for finding all the matches. Search within the specified Range index, which is always ascending. The (indexing) range values can be of any generic type T satisfying the listed bounds. Typically usize for indexing efficiently in-memory, u128 for searching whole disks or internet, f64 for solving equations which might not converge using secant and other methods. Comparator closure cmpr is comparing against a target captured from its environment. The sort order of the data can be either ascending or descending (increasing/decreasing). The order must be specified by the ascending argument. When the target is in order before self.start, empty self self.start..self.start range is returned. When the target is in order after self.end, self.end..self.end is returned. When target is not found, then ip..ip is returned, where ip is its insert position. Otherwise the range of all consecutive values PartiallyEqual to the target is returned.

Implementors