1 //! Functions for generating and checking Monge arrays.
2 //!
3 //! The functions here are mostly meant to be used for testing
4 //! correctness of the SMAWK implementation.
5
6 use crate::Matrix;
7 use std::num::Wrapping;
8 use std::ops::Add;
9
10 /// Verify that a matrix is a Monge matrix.
11 ///
12 /// A [Monge matrix] \(or array) is a matrix where the following
13 /// inequality holds:
14 ///
15 /// ```text
16 /// M[i, j] + M[i', j'] <= M[i, j'] + M[i', j] for all i < i', j < j'
17 /// ```
18 ///
19 /// The inequality says that the sum of the main diagonal is less than
20 /// the sum of the antidiagonal. Checking this condition is done by
21 /// checking *n* ✕ *m* submatrices, so the running time is O(*mn*).
22 ///
23 /// [Monge matrix]: https://en.wikipedia.org/wiki/Monge_array
is_monge<T: Ord + Copy, M: Matrix<T>>(matrix: &M) -> bool where Wrapping<T>: Add<Output = Wrapping<T>>,24 pub fn is_monge<T: Ord + Copy, M: Matrix<T>>(matrix: &M) -> bool
25 where
26 Wrapping<T>: Add<Output = Wrapping<T>>,
27 {
28 /// Returns `Ok(a + b)` if the computation can be done without
29 /// overflow, otherwise `Err(a + b - T::MAX - 1)` is returned.
30 fn checked_add<T: Ord + Copy>(a: Wrapping<T>, b: Wrapping<T>) -> Result<T, T>
31 where
32 Wrapping<T>: Add<Output = Wrapping<T>>,
33 {
34 let sum = a + b;
35 if sum < a {
36 Err(sum.0)
37 } else {
38 Ok(sum.0)
39 }
40 }
41
42 (0..matrix.nrows() - 1)
43 .flat_map(|row| (0..matrix.ncols() - 1).map(move |col| (row, col)))
44 .all(|(row, col)| {
45 let top_left = Wrapping(matrix.index(row, col));
46 let top_right = Wrapping(matrix.index(row, col + 1));
47 let bot_left = Wrapping(matrix.index(row + 1, col));
48 let bot_right = Wrapping(matrix.index(row + 1, col + 1));
49
50 match (
51 checked_add(top_left, bot_right),
52 checked_add(bot_left, top_right),
53 ) {
54 (Ok(a), Ok(b)) => a <= b, // No overflow.
55 (Err(a), Err(b)) => a <= b, // Double overflow.
56 (Ok(_), Err(_)) => true, // Antidiagonal overflow.
57 (Err(_), Ok(_)) => false, // Main diagonal overflow.
58 }
59 })
60 }
61
62 #[cfg(test)]
63 mod tests {
64 use super::*;
65
66 #[test]
is_monge_handles_overflow()67 fn is_monge_handles_overflow() {
68 // The x + y <= z + w computations will overflow for an u8
69 // matrix unless is_monge is careful.
70 let matrix: Vec<Vec<u8>> = vec![
71 vec![200, 200, 200, 200],
72 vec![200, 200, 200, 200],
73 vec![200, 200, 200, 200],
74 ];
75 assert!(is_monge(&matrix));
76 }
77
78 #[test]
monge_constant_rows()79 fn monge_constant_rows() {
80 let matrix = vec![
81 vec![42, 42, 42, 42],
82 vec![0, 0, 0, 0],
83 vec![100, 100, 100, 100],
84 vec![1000, 1000, 1000, 1000],
85 ];
86 assert!(is_monge(&matrix));
87 }
88
89 #[test]
monge_constant_cols()90 fn monge_constant_cols() {
91 let matrix = vec![
92 vec![42, 0, 100, 1000],
93 vec![42, 0, 100, 1000],
94 vec![42, 0, 100, 1000],
95 vec![42, 0, 100, 1000],
96 ];
97 assert!(is_monge(&matrix));
98 }
99
100 #[test]
monge_upper_right()101 fn monge_upper_right() {
102 let matrix = vec![
103 vec![10, 10, 42, 42, 42],
104 vec![10, 10, 42, 42, 42],
105 vec![10, 10, 10, 10, 10],
106 vec![10, 10, 10, 10, 10],
107 ];
108 assert!(is_monge(&matrix));
109 }
110
111 #[test]
monge_lower_left()112 fn monge_lower_left() {
113 let matrix = vec![
114 vec![10, 10, 10, 10, 10],
115 vec![10, 10, 10, 10, 10],
116 vec![42, 42, 42, 10, 10],
117 vec![42, 42, 42, 10, 10],
118 ];
119 assert!(is_monge(&matrix));
120 }
121 }
122