Trait lis::LisExt

pub trait LisExt<T>: AsRef<[T]> {
    fn longest_increasing_subsequence(&self) -> Vec<usize>
    where
        T: Ord,
    { ... }
    fn longest_increasing_subsequence_by<F, P>(
        &self, 
        f: F, 
        filter: P
    ) -> Vec<usize>
    where
        F: FnMut(&T, &T) -> Ordering,
        P: FnMut(&T) -> bool,
    { ... }
}

Extends AsRef<[T]> with methods for generating longest increasing subsequences.

Provided methods

fn longest_increasing_subsequence(&self) -> Vec<usize> where
    T: Ord, 

Returns indices of the longest increasing subsequence.

See longest_increasing_subsequence_by.

fn longest_increasing_subsequence_by<F, P>(&self, f: F, filter: P) -> Vec<usize> where
    F: FnMut(&T, &T) -> Ordering,
    P: FnMut(&T) -> bool, 

Returns indices of the longest increasing subsequence with a comparator function.

The closure filter is called on each element. If it returns false the element is skipped, however indices are left intact.

This is O(n log n) worst-case and allocates at most 2 * size_of<usize>() * n bytes. It is based on the method described by Michael L. Fredman (1975) in On computing the length of longest increasing subsequences.

Example

use lis::LisExt;
assert_eq!([2, 1, 4, 3, 5].longest_increasing_subsequence_by(|a, b| a.cmp(b), |_| true), [1, 3, 4]);

Loading content...

Implementors

impl<S: ?Sized, T> LisExt<T> for S where
    S: AsRef<[T]>, 

Loading content...