4 releases (1 stable)

1.0.0 Aug 5, 2019
0.2.0 Dec 26, 2018
0.1.1 Jul 30, 2018
0.1.0 Jul 29, 2018

#1497 in Algorithms

MIT license

17KB
324 lines

Logo

lis

Rust implementation of the Longest increasing subsequence algorithm.

Build Status Documentation

Also provides a function for diffing lists, that makes use of the LIS 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);

Dependencies

~130KB