axelf4/lis

🦊 Longest increasing subsequence algorithm in Rust

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);

lis's Issues

PartialEq for keys is enough?

Hi, I am not good in math, but I think that in:

pub fn diff_by_key<S, T, K: Eq + Hash>()

K: PartialEq is enough. Do you think so?

Also, I think old/new... is better than a/b... (names of diff_by_key arguments).

Side talk: I am the one who talked to you in axelf4/dumle#1. The last few months I switch my focus to Mika. Now I am trying to implement a fallback mode to handle list change for Mika. The first try is to use your lis crate, hoping that goes well. If you are still interested in a frontend framework, you may want to have a look at its page - with integrated demo.