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
17KB
324 lines
lis
Rust implementation of the Longest increasing subsequence algorithm.
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