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:

#![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(()));

Enums

DiffAction

A fragment of a diff.

Traits

LisExt

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

Functions

diff_by_key

Computes the difference between the two iterators with a key extraction function.