Trait LisExt

pub trait LisExt<T>: AsRef<[T]> {
    // Provided methods
    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]);

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<S, T> LisExt<T> for S

where S: AsRef<[T]> + ?Sized,