[−][src]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());