1 //! Recursive algorithm for finding column minima.
2 //!
3 //! The functions here are mostly meant to be used for testing
4 //! correctness of the SMAWK implementation.
5 //!
6 //! **Note: this module is only available if you enable the `ndarray`
7 //! Cargo feature.**
8
9 use ndarray::{s, Array2, ArrayView2, Axis};
10
11 /// Compute row minima in O(*m* + *n* log *m*) time.
12 ///
13 /// # Panics
14 ///
15 /// It is an error to call this on a matrix with zero columns.
row_minima<T: Ord>(matrix: &Array2<T>) -> Vec<usize>16 pub fn row_minima<T: Ord>(matrix: &Array2<T>) -> Vec<usize> {
17 let mut minima = vec![0; matrix.nrows()];
18 recursive_inner(matrix.view(), &|| Direction::Row, 0, &mut minima);
19 minima
20 }
21
22 /// Compute column minima in O(*n* + *m* log *n*) time.
23 ///
24 /// # Panics
25 ///
26 /// It is an error to call this on a matrix with zero rows.
column_minima<T: Ord>(matrix: &Array2<T>) -> Vec<usize>27 pub fn column_minima<T: Ord>(matrix: &Array2<T>) -> Vec<usize> {
28 let mut minima = vec![0; matrix.ncols()];
29 recursive_inner(matrix.view(), &|| Direction::Column, 0, &mut minima);
30 minima
31 }
32
33 /// The type of minima (row or column) we compute.
34 enum Direction {
35 Row,
36 Column,
37 }
38
39 /// Compute the minima along the given direction (`Direction::Row` for
40 /// row minima and `Direction::Column` for column minima).
41 ///
42 /// The direction is given as a generic function argument to allow
43 /// monomorphization to kick in. The function calls will be inlined
44 /// and optimized away and the result is that the compiler generates
45 /// differnet code for finding row and column minima.
recursive_inner<T: Ord, F: Fn() -> Direction>( matrix: ArrayView2<'_, T>, dir: &F, offset: usize, minima: &mut [usize], )46 fn recursive_inner<T: Ord, F: Fn() -> Direction>(
47 matrix: ArrayView2<'_, T>,
48 dir: &F,
49 offset: usize,
50 minima: &mut [usize],
51 ) {
52 if matrix.is_empty() {
53 return;
54 }
55
56 let axis = match dir() {
57 Direction::Row => Axis(0),
58 Direction::Column => Axis(1),
59 };
60 let mid = matrix.len_of(axis) / 2;
61 let min_idx = crate::brute_force::lane_minimum(matrix.index_axis(axis, mid));
62 minima[mid] = offset + min_idx;
63
64 if mid == 0 {
65 return; // Matrix has a single row or column, so we're done.
66 }
67
68 let top_left = match dir() {
69 Direction::Row => matrix.slice(s![..mid, ..(min_idx + 1)]),
70 Direction::Column => matrix.slice(s![..(min_idx + 1), ..mid]),
71 };
72 let bot_right = match dir() {
73 Direction::Row => matrix.slice(s![(mid + 1).., min_idx..]),
74 Direction::Column => matrix.slice(s![min_idx.., (mid + 1)..]),
75 };
76 recursive_inner(top_left, dir, offset, &mut minima[..mid]);
77 recursive_inner(bot_right, dir, offset + min_idx, &mut minima[mid + 1..]);
78 }
79
80 #[cfg(test)]
81 mod tests {
82 use super::*;
83 use ndarray::arr2;
84
85 #[test]
recursive_1x1()86 fn recursive_1x1() {
87 let matrix = arr2(&[[2]]);
88 let minima = vec![0];
89 assert_eq!(row_minima(&matrix), minima);
90 assert_eq!(column_minima(&matrix.reversed_axes()), minima);
91 }
92
93 #[test]
recursive_2x1()94 fn recursive_2x1() {
95 let matrix = arr2(&[
96 [3], //
97 [2],
98 ]);
99 let minima = vec![0, 0];
100 assert_eq!(row_minima(&matrix), minima);
101 assert_eq!(column_minima(&matrix.reversed_axes()), minima);
102 }
103
104 #[test]
recursive_1x2()105 fn recursive_1x2() {
106 let matrix = arr2(&[[2, 1]]);
107 let minima = vec![1];
108 assert_eq!(row_minima(&matrix), minima);
109 assert_eq!(column_minima(&matrix.reversed_axes()), minima);
110 }
111
112 #[test]
recursive_2x2()113 fn recursive_2x2() {
114 let matrix = arr2(&[
115 [3, 2], //
116 [2, 1],
117 ]);
118 let minima = vec![1, 1];
119 assert_eq!(row_minima(&matrix), minima);
120 assert_eq!(column_minima(&matrix.reversed_axes()), minima);
121 }
122
123 #[test]
recursive_3x3()124 fn recursive_3x3() {
125 let matrix = arr2(&[
126 [3, 4, 4], //
127 [3, 4, 4],
128 [2, 3, 3],
129 ]);
130 let minima = vec![0, 0, 0];
131 assert_eq!(row_minima(&matrix), minima);
132 assert_eq!(column_minima(&matrix.reversed_axes()), minima);
133 }
134
135 #[test]
recursive_4x4()136 fn recursive_4x4() {
137 let matrix = arr2(&[
138 [4, 5, 5, 5], //
139 [2, 3, 3, 3],
140 [2, 3, 3, 3],
141 [2, 2, 2, 2],
142 ]);
143 let minima = vec![0, 0, 0, 0];
144 assert_eq!(row_minima(&matrix), minima);
145 assert_eq!(column_minima(&matrix.reversed_axes()), minima);
146 }
147
148 #[test]
recursive_5x5()149 fn recursive_5x5() {
150 let matrix = arr2(&[
151 [3, 2, 4, 5, 6],
152 [2, 1, 3, 3, 4],
153 [2, 1, 3, 3, 4],
154 [3, 2, 4, 3, 4],
155 [4, 3, 2, 1, 1],
156 ]);
157 let minima = vec![1, 1, 1, 1, 3];
158 assert_eq!(row_minima(&matrix), minima);
159 assert_eq!(column_minima(&matrix.reversed_axes()), minima);
160 }
161 }
162