1 //! Functions for generating and checking Monge arrays.
3 //! The functions here are mostly meant to be used for testing
4 //! correctness of the SMAWK implementation.
7 use std::num::Wrapping;
10 /// Verify that a matrix is a Monge matrix.
12 /// A [Monge matrix] \(or array) is a matrix where the following
16 /// M[i, j] + M[i', j'] <= M[i, j'] + M[i', j] for all i < i', j < j'
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*).
23 /// [Monge matrix]: https://en.wikipedia.org/wiki/Monge_array
24 pub fn is_monge<T: Ord + Copy, M: Matrix<T>>(matrix: &M) -> bool
26 Wrapping<T>: Add<Output = Wrapping<T>>,
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>
32 Wrapping<T>: Add<Output = Wrapping<T>>,
42 (0..matrix.nrows() - 1)
43 .flat_map(|row| (0..matrix.ncols() - 1).map(move |col| (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));
51 checked_add(top_left, bot_right),
52 checked_add(bot_left, top_right),
54 (Ok(a), Ok(b)) => a <= b, // No overflow.
55 (Err(a), Err(b)) => a <= b, // Double overflow.
56 (Ok(_), Err(_)) => true, // Anti-diagonal overflow.
57 (Err(_), Ok(_)) => false, // Main diagonal 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],
75 assert!(is_monge(&matrix));
79 fn monge_constant_rows() {
83 vec![100, 100, 100, 100],
84 vec![1000, 1000, 1000, 1000],
86 assert!(is_monge(&matrix));
90 fn monge_constant_cols() {
92 vec![42, 0, 100, 1000],
93 vec![42, 0, 100, 1000],
94 vec![42, 0, 100, 1000],
95 vec![42, 0, 100, 1000],
97 assert!(is_monge(&matrix));
101 fn monge_upper_right() {
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],
108 assert!(is_monge(&matrix));
112 fn monge_lower_left() {
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],
119 assert!(is_monge(&matrix));