diff options
Diffstat (limited to 'vendor/smawk/src/recursive.rs')
| -rw-r--r-- | vendor/smawk/src/recursive.rs | 191 |
1 files changed, 0 insertions, 191 deletions
diff --git a/vendor/smawk/src/recursive.rs b/vendor/smawk/src/recursive.rs deleted file mode 100644 index 9df8b9c..0000000 --- a/vendor/smawk/src/recursive.rs +++ /dev/null @@ -1,191 +0,0 @@ -//! 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); - } -} |