Lis: keyed list diffing for VDOMs, 0.2.0 released


#1

lis is a crate for efficiently diffing two lists. One of the strengths of virtual DOM:s is that you only have to perform minimal updates to the real DOM. However I have seen that many VDOM Rust libraries are pretty inefficient when it comes to this. lis makes it trivial to implement keyed child reconciliation.

Backing the diffing is the longest increasing subsequence algorithm that is also exposed by the crate through the LisExt extension trait. Hence the name.

crates.io: https://crates.io/crates/lis
docs.io: https://docs.rs/lis

Requires, currently, the nightly compiler since it makes use of generators.

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:

#![feature(generator_trait)]
use lis::{diff_by_key, DiffAction};
use std::ops::{Generator, GeneratorState};
let mut generator = diff_by_key(1..2, 1..3, |x| x);
assert_eq!(unsafe { generator.resume() }, GeneratorState::Yielded(DiffAction::Unchanged(1, 1)));
assert_eq!(unsafe { generator.resume() }, GeneratorState::Yielded(DiffAction::Insert(2)));
assert_eq!(unsafe { generator.resume() }, GeneratorState::Complete(()));