diff options
Diffstat (limited to 'vendor/smawk/src/recursive.rs')
| -rw-r--r-- | vendor/smawk/src/recursive.rs | 191 |
1 files changed, 191 insertions, 0 deletions
diff --git a/vendor/smawk/src/recursive.rs b/vendor/smawk/src/recursive.rs new file mode 100644 index 0000000..9df8b9c --- /dev/null +++ b/vendor/smawk/src/recursive.rs @@ -0,0 +1,191 @@ +//! Recursive algorithm for finding column minima. +//! +//! The functions here are mostly meant to be used for testing +//! correctness of the SMAWK implementation. +//! +//! **Note: this module is only available if you enable the `ndarray` +//! Cargo feature.** + +use ndarray::{s, Array2, ArrayView2, Axis}; + +/// Compute row minima in O(*m* + *n* log *m*) time. +/// +/// This function computes row minima in a totally monotone matrix +/// using a recursive algorithm. +/// +/// Running time on an *m* ✕ *n* matrix: O(*m* + *n* log *m*). +/// +/// # Examples +/// +/// ``` +/// let matrix = ndarray::arr2(&[[4, 2, 4, 3], +/// [5, 3, 5, 3], +/// [5, 3, 3, 1]]); +/// assert_eq!(smawk::recursive::row_minima(&matrix), +/// vec![1, 1, 3]); +/// ``` +/// +/// # Panics +/// +/// It is an error to call this on a matrix with zero columns. +pub fn row_minima<T: Ord>(matrix: &Array2<T>) -> Vec<usize> { + let mut minima = vec![0; matrix.nrows()]; + recursive_inner(matrix.view(), &|| Direction::Row, 0, &mut minima); + minima +} + +/// Compute column minima in O(*n* + *m* log *n*) time. +/// +/// This function computes column minima in a totally monotone matrix +/// using a recursive algorithm. +/// +/// Running time on an *m* ✕ *n* matrix: O(*n* + *m* log *n*). +/// +/// # Examples +/// +/// ``` +/// let matrix = ndarray::arr2(&[[4, 2, 4, 3], +/// [5, 3, 5, 3], +/// [5, 3, 3, 1]]); +/// assert_eq!(smawk::recursive::column_minima(&matrix), +/// vec![0, 0, 2, 2]); +/// ``` +/// +/// # Panics +/// +/// It is an error to call this on a matrix with zero rows. +pub fn column_minima<T: Ord>(matrix: &Array2<T>) -> Vec<usize> { + let mut minima = vec![0; matrix.ncols()]; + recursive_inner(matrix.view(), &|| Direction::Column, 0, &mut minima); + minima +} + +/// The type of minima (row or column) we compute. +enum Direction { + Row, + Column, +} + +/// Compute the minima along the given direction (`Direction::Row` for +/// row minima and `Direction::Column` for column minima). +/// +/// The direction is given as a generic function argument to allow +/// monomorphization to kick in. The function calls will be inlined +/// and optimized away and the result is that the compiler generates +/// differnet code for finding row and column minima. +fn recursive_inner<T: Ord, F: Fn() -> Direction>( + matrix: ArrayView2<'_, T>, + dir: &F, + offset: usize, + minima: &mut [usize], +) { + if matrix.is_empty() { + return; + } + + let axis = match dir() { + Direction::Row => Axis(0), + Direction::Column => Axis(1), + }; + let mid = matrix.len_of(axis) / 2; + let min_idx = crate::brute_force::lane_minimum(matrix.index_axis(axis, mid)); + minima[mid] = offset + min_idx; + + if mid == 0 { + return; // Matrix has a single row or column, so we're done. + } + + let top_left = match dir() { + Direction::Row => matrix.slice(s![..mid, ..(min_idx + 1)]), + Direction::Column => matrix.slice(s![..(min_idx + 1), ..mid]), + }; + let bot_right = match dir() { + Direction::Row => matrix.slice(s![(mid + 1).., min_idx..]), + Direction::Column => matrix.slice(s![min_idx.., (mid + 1)..]), + }; + recursive_inner(top_left, dir, offset, &mut minima[..mid]); + recursive_inner(bot_right, dir, offset + min_idx, &mut minima[mid + 1..]); +} + +#[cfg(test)] +mod tests { + use super::*; + use ndarray::arr2; + + #[test] + fn recursive_1x1() { + let matrix = arr2(&[[2]]); + let minima = vec![0]; + assert_eq!(row_minima(&matrix), minima); + assert_eq!(column_minima(&matrix.reversed_axes()), minima); + } + + #[test] + fn recursive_2x1() { + let matrix = arr2(&[ + [3], // + [2], + ]); + let minima = vec![0, 0]; + assert_eq!(row_minima(&matrix), minima); + assert_eq!(column_minima(&matrix.reversed_axes()), minima); + } + + #[test] + fn recursive_1x2() { + let matrix = arr2(&[[2, 1]]); + let minima = vec![1]; + assert_eq!(row_minima(&matrix), minima); + assert_eq!(column_minima(&matrix.reversed_axes()), minima); + } + + #[test] + fn recursive_2x2() { + let matrix = arr2(&[ + [3, 2], // + [2, 1], + ]); + let minima = vec![1, 1]; + assert_eq!(row_minima(&matrix), minima); + assert_eq!(column_minima(&matrix.reversed_axes()), minima); + } + + #[test] + fn recursive_3x3() { + let matrix = arr2(&[ + [3, 4, 4], // + [3, 4, 4], + [2, 3, 3], + ]); + let minima = vec![0, 0, 0]; + assert_eq!(row_minima(&matrix), minima); + assert_eq!(column_minima(&matrix.reversed_axes()), minima); + } + + #[test] + fn recursive_4x4() { + let matrix = arr2(&[ + [4, 5, 5, 5], // + [2, 3, 3, 3], + [2, 3, 3, 3], + [2, 2, 2, 2], + ]); + let minima = vec![0, 0, 0, 0]; + assert_eq!(row_minima(&matrix), minima); + assert_eq!(column_minima(&matrix.reversed_axes()), minima); + } + + #[test] + fn recursive_5x5() { + let matrix = arr2(&[ + [3, 2, 4, 5, 6], + [2, 1, 3, 3, 4], + [2, 1, 3, 3, 4], + [3, 2, 4, 3, 4], + [4, 3, 2, 1, 1], + ]); + let minima = vec![1, 1, 1, 1, 3]; + assert_eq!(row_minima(&matrix), minima); + assert_eq!(column_minima(&matrix.reversed_axes()), minima); + } +} |