Crate lis

An implementation of the Longest increasing subsequence algorithm.

Examples

The main trait exposed by this crate is LisExt, which is implemented for, inter alia, arrays:

use lis::LisExt;
assert_eq!([2, 1, 4, 3, 5].longest_increasing_subsequence(), [1, 3, 4]);

Diffing two lists can be done with diff_by_key:

use lis::{diff_by_key, DiffCallback};
struct Cb;
impl DiffCallback<usize, usize> for Cb {
    fn inserted(&mut self, new: usize) {
        assert_eq!(new, 2);
    }
    fn removed(&mut self, old: usize) {}
    fn unchanged(&mut self, old: usize, new: usize) {
        assert_eq!(old, 1);
        assert_eq!(new, 1);
    }
}
diff_by_key(1..2, |x| x, 1..3, |x| x, &mut Cb);

Traits

DiffCallback

Gets notified for each step of the diffing process.

LisExt

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

Functions

diff_by_key

Computes the difference between the two iterators with key extraction functions.