Skip to main content

smawk

competitive::math::min_plus_convolution::convex

Function smawk 

Source 
fn smawk<T, F>(rows: usize, cols: usize, cost: &F) -> Vec<usize>
where
    T: Ord,
    F: Fn(usize, usize) -> T,
Examples found in repository?
crates/competitive/src/math/min_plus_convolution/convex.rs (line 285)
273pub(super) fn convex_smawk<T>(arbitrary: &[T], convex: &[T]) -> Vec<T>
274where
275    T: Signed,
276{
277    let len = output_len(arbitrary.len(), convex.len());
278    let cost = |row: usize, col: usize| {
279        row.checked_sub(col)
280            .filter(|&index| index < convex.len())
281            .map_or(MatrixValue::Infinite, |index| {
282                MatrixValue::Finite(arbitrary[col] + convex[index])
283            })
284    };
285    let argmins = smawk(len, arbitrary.len(), &cost);
286    argmins
287        .into_iter()
288        .enumerate()
289        .map(|(row, col)| {
290            row.checked_sub(col)
291                .filter(|&index| index < convex.len())
292                .map(|index| arbitrary[col] + convex[index])
293                .expect("SMAWK minimum must be a valid convolution entry")
294        })
295        .collect()
296}