Function longest_increasing_subsequence::lis_with

pub fn lis_with<T, S, F>(
    items: &[T],
    out_seq: &mut S,
    less_than: F,
    predecessors: &mut [usize],
    starts: &mut [usize]
)where
    S: Extend<usize>,
    F: FnMut(&T, &T) -> bool,

The low-level function for finding a longest increasing subsequence.

This low-level function allows you to:

• customize the comparator function to something other than T: Ord,

• bring your own allocations for the algorithm’s temporary scratch space (so you can reuse the same allocations across multiple lis_with calls, or use a custom allocator, etc…),

• and collect the resulting LIS into a custom collection data structure.

Note that the out_seq is given the indices of the LIS in reverse order from the end of the LIS first to the start of the LIS last.

Panics

Panics if items, predecessors, and starts do not all have the same length.

Example

use longest_increasing_subsequence::lis_with;
use std::collections::HashSet;

// Create allocations for the algorithm's scratch space.
let mut predecessors = Vec::new();
let mut starts = Vec::new();

// And a collection to contain the results.
let mut results = HashSet::new();

// A slice whose LIS we would like to find.
let xs = vec![9, 2, 8, 3, 5];

// Ensure our allocations have enough space.
predecessors.resize_with(xs.len(), Default::default);
starts.resize_with(xs.len(), Default::default);

lis_with(
    &xs,
    &mut results,
    |a, b| a < b,
    &mut predecessors,
    &mut starts,
);

assert_eq!(results, vec![1, 3, 4].into_iter().collect());

// Another slice whose LIS we would like to find.
let ys = vec![9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

// We are going to reuse our previous scratch space. Again, ensure we
// have enough space.
predecessors.resize_with(ys.len(), Default::default);
starts.resize_with(ys.len(), Default::default);

results.clear();
lis_with(
    &ys,
    &mut results,
    |a, b| a < b,
    &mut predecessors,
    &mut starts,
);

assert_eq!(results, vec![9, 10, 11, 12, 13, 14, 15, 16, 17, 18].into_iter().collect());