summaryrefslogtreecommitdiffstats
path: root/third_party/rust/smawk/tests
diff options
context:
space:
mode:
authorDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-15 03:35:49 +0000
committerDaniel Baumann <daniel.baumann@progress-linux.org>2024-05-15 03:35:49 +0000
commitd8bbc7858622b6d9c278469aab701ca0b609cddf (patch)
treeeff41dc61d9f714852212739e6b3738b82a2af87 /third_party/rust/smawk/tests
parentReleasing progress-linux version 125.0.3-1~progress7.99u1. (diff)
downloadfirefox-d8bbc7858622b6d9c278469aab701ca0b609cddf.tar.xz
firefox-d8bbc7858622b6d9c278469aab701ca0b609cddf.zip
Merging upstream version 126.0.
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/rust/smawk/tests')
-rw-r--r--third_party/rust/smawk/tests/agreement.rs104
-rw-r--r--third_party/rust/smawk/tests/complexity.rs83
-rw-r--r--third_party/rust/smawk/tests/monge.rs83
-rw-r--r--third_party/rust/smawk/tests/random_monge/mod.rs83
-rw-r--r--third_party/rust/smawk/tests/version-numbers.rs9
5 files changed, 362 insertions, 0 deletions
diff --git a/third_party/rust/smawk/tests/agreement.rs b/third_party/rust/smawk/tests/agreement.rs
new file mode 100644
index 0000000000..2e0343a59a
--- /dev/null
+++ b/third_party/rust/smawk/tests/agreement.rs
@@ -0,0 +1,104 @@
+#![cfg(feature = "ndarray")]
+
+use ndarray::{s, Array2};
+use rand::SeedableRng;
+use rand_chacha::ChaCha20Rng;
+use smawk::{brute_force, online_column_minima, recursive};
+
+mod random_monge;
+use random_monge::random_monge_matrix;
+
+/// Check that the brute force, recursive, and SMAWK functions
+/// give identical results on a large number of randomly generated
+/// Monge matrices.
+#[test]
+fn column_minima_agree() {
+ let sizes = vec![1, 2, 3, 4, 5, 10, 15, 20, 30];
+ let mut rng = ChaCha20Rng::seed_from_u64(0);
+ for _ in 0..4 {
+ for m in sizes.clone().iter() {
+ for n in sizes.clone().iter() {
+ let matrix: Array2<i32> = random_monge_matrix(*m, *n, &mut rng);
+
+ // Compute and test row minima.
+ let brute_force = brute_force::row_minima(&matrix);
+ let recursive = recursive::row_minima(&matrix);
+ let smawk = smawk::row_minima(&matrix);
+ assert_eq!(
+ brute_force, recursive,
+ "recursive and brute force differs on:\n{:?}",
+ matrix
+ );
+ assert_eq!(
+ brute_force, smawk,
+ "SMAWK and brute force differs on:\n{:?}",
+ matrix
+ );
+
+ // Do the same for the column minima.
+ let brute_force = brute_force::column_minima(&matrix);
+ let recursive = recursive::column_minima(&matrix);
+ let smawk = smawk::column_minima(&matrix);
+ assert_eq!(
+ brute_force, recursive,
+ "recursive and brute force differs on:\n{:?}",
+ matrix
+ );
+ assert_eq!(
+ brute_force, smawk,
+ "SMAWK and brute force differs on:\n{:?}",
+ matrix
+ );
+ }
+ }
+ }
+}
+
+/// Check that the brute force and online SMAWK functions give
+/// identical results on a large number of randomly generated
+/// Monge matrices.
+#[test]
+fn online_agree() {
+ let sizes = vec![1, 2, 3, 4, 5, 10, 15, 20, 30, 50];
+ let mut rng = ChaCha20Rng::seed_from_u64(0);
+ for _ in 0..5 {
+ for &size in &sizes {
+ // Random totally monotone square matrix of the
+ // desired size.
+ let mut matrix: Array2<i32> = random_monge_matrix(size, size, &mut rng);
+
+ // Adjust matrix so the column minima are above the
+ // diagonal. The brute_force::column_minima will still
+ // work just fine on such a mangled Monge matrix.
+ let max = *matrix.iter().max().unwrap_or(&0);
+ for idx in 0..(size as isize) {
+ // Using the maximum value of the matrix instead
+ // of i32::max_value() makes for prettier matrices
+ // in case we want to print them.
+ matrix.slice_mut(s![idx..idx + 1, ..idx + 1]).fill(max);
+ }
+
+ // The online algorithm always returns the initial
+ // value for the left-most column -- without
+ // inspecting the column at all. So we fill the
+ // left-most column with this value to have the brute
+ // force algorithm do the same.
+ let initial = 42;
+ matrix.slice_mut(s![0.., ..1]).fill(initial);
+
+ // Brute-force computation of column minima, returned
+ // in the same form as online_column_minima.
+ let brute_force = brute_force::column_minima(&matrix)
+ .iter()
+ .enumerate()
+ .map(|(j, &i)| (i, matrix[[i, j]]))
+ .collect::<Vec<_>>();
+ let online = online_column_minima(initial, size, |_, i, j| matrix[[i, j]]);
+ assert_eq!(
+ brute_force, online,
+ "brute force and online differ on:\n{:3?}",
+ matrix
+ );
+ }
+ }
+}
diff --git a/third_party/rust/smawk/tests/complexity.rs b/third_party/rust/smawk/tests/complexity.rs
new file mode 100644
index 0000000000..c9881eaeac
--- /dev/null
+++ b/third_party/rust/smawk/tests/complexity.rs
@@ -0,0 +1,83 @@
+#![cfg(feature = "ndarray")]
+
+use ndarray::{Array1, Array2};
+use rand::SeedableRng;
+use rand_chacha::ChaCha20Rng;
+use smawk::online_column_minima;
+
+mod random_monge;
+use random_monge::random_monge_matrix;
+
+#[derive(Debug)]
+struct LinRegression {
+ alpha: f64,
+ beta: f64,
+ r_squared: f64,
+}
+
+/// Square an expression. Works equally well for floats and matrices.
+macro_rules! squared {
+ ($x:expr) => {
+ $x * $x
+ };
+}
+
+/// Compute the mean of a 1-dimensional array.
+macro_rules! mean {
+ ($a:expr) => {
+ $a.mean().expect("Mean of empty array")
+ };
+}
+
+/// Compute a simple linear regression from the list of values.
+///
+/// See <https://en.wikipedia.org/wiki/Simple_linear_regression>.
+fn linear_regression(values: &[(usize, i32)]) -> LinRegression {
+ let xs = values.iter().map(|&(x, _)| x as f64).collect::<Array1<_>>();
+ let ys = values.iter().map(|&(_, y)| y as f64).collect::<Array1<_>>();
+
+ let xs_mean = mean!(&xs);
+ let ys_mean = mean!(&ys);
+ let xs_ys_mean = mean!(&xs * &ys);
+
+ let cov_xs_ys = ((&xs - xs_mean) * (&ys - ys_mean)).sum();
+ let var_xs = squared!(&xs - xs_mean).sum();
+
+ let beta = cov_xs_ys / var_xs;
+ let alpha = ys_mean - beta * xs_mean;
+ let r_squared = squared!(xs_ys_mean - xs_mean * ys_mean)
+ / ((mean!(&xs * &xs) - squared!(xs_mean)) * (mean!(&ys * &ys) - squared!(ys_mean)));
+
+ LinRegression {
+ alpha: alpha,
+ beta: beta,
+ r_squared: r_squared,
+ }
+}
+
+/// Check that the number of matrix accesses in `online_column_minima`
+/// grows as O(*n*) for *n* ✕ *n* matrix.
+#[test]
+fn online_linear_complexity() {
+ let mut rng = ChaCha20Rng::seed_from_u64(0);
+ let mut data = vec![];
+
+ for &size in &[1, 2, 3, 4, 5, 10, 15, 20, 30, 40, 50, 60, 70, 80, 90, 100] {
+ let matrix: Array2<i32> = random_monge_matrix(size, size, &mut rng);
+ let count = std::cell::RefCell::new(0);
+ online_column_minima(0, size, |_, i, j| {
+ *count.borrow_mut() += 1;
+ matrix[[i, j]]
+ });
+ data.push((size, count.into_inner()));
+ }
+
+ let lin_reg = linear_regression(&data);
+ assert!(
+ lin_reg.r_squared > 0.95,
+ "r² = {:.4} is lower than expected for a linear fit\nData points: {:?}\n{:?}",
+ lin_reg.r_squared,
+ data,
+ lin_reg
+ );
+}
diff --git a/third_party/rust/smawk/tests/monge.rs b/third_party/rust/smawk/tests/monge.rs
new file mode 100644
index 0000000000..67058a75a5
--- /dev/null
+++ b/third_party/rust/smawk/tests/monge.rs
@@ -0,0 +1,83 @@
+#![cfg(feature = "ndarray")]
+
+use ndarray::{arr2, Array, Array2};
+use rand::SeedableRng;
+use rand_chacha::ChaCha20Rng;
+use smawk::monge::is_monge;
+
+mod random_monge;
+use random_monge::{random_monge_matrix, MongePrim};
+
+#[test]
+fn random_monge() {
+ let mut rng = ChaCha20Rng::seed_from_u64(0);
+ let matrix: Array2<u8> = random_monge_matrix(5, 5, &mut rng);
+
+ assert!(is_monge(&matrix));
+ assert_eq!(
+ matrix,
+ arr2(&[
+ [2, 3, 4, 4, 5],
+ [5, 5, 6, 6, 7],
+ [3, 3, 4, 4, 5],
+ [5, 2, 3, 3, 4],
+ [5, 2, 3, 3, 4]
+ ])
+ );
+}
+
+#[test]
+fn monge_constant_rows() {
+ let mut rng = ChaCha20Rng::seed_from_u64(0);
+ let matrix: Array2<u8> = MongePrim::ConstantRows.to_matrix(5, 4, &mut rng);
+ assert!(is_monge(&matrix));
+ for row in matrix.rows() {
+ let elem = row[0];
+ assert_eq!(row, Array::from_elem(matrix.ncols(), elem));
+ }
+}
+
+#[test]
+fn monge_constant_cols() {
+ let mut rng = ChaCha20Rng::seed_from_u64(0);
+ let matrix: Array2<u8> = MongePrim::ConstantCols.to_matrix(5, 4, &mut rng);
+ assert!(is_monge(&matrix));
+ for column in matrix.columns() {
+ let elem = column[0];
+ assert_eq!(column, Array::from_elem(matrix.nrows(), elem));
+ }
+}
+
+#[test]
+fn monge_upper_right_ones() {
+ let mut rng = ChaCha20Rng::seed_from_u64(1);
+ let matrix: Array2<u8> = MongePrim::UpperRightOnes.to_matrix(5, 4, &mut rng);
+ assert!(is_monge(&matrix));
+ assert_eq!(
+ matrix,
+ arr2(&[
+ [0, 0, 1, 1],
+ [0, 0, 1, 1],
+ [0, 0, 1, 1],
+ [0, 0, 0, 0],
+ [0, 0, 0, 0]
+ ])
+ );
+}
+
+#[test]
+fn monge_lower_left_ones() {
+ let mut rng = ChaCha20Rng::seed_from_u64(1);
+ let matrix: Array2<u8> = MongePrim::LowerLeftOnes.to_matrix(5, 4, &mut rng);
+ assert!(is_monge(&matrix));
+ assert_eq!(
+ matrix,
+ arr2(&[
+ [0, 0, 0, 0],
+ [0, 0, 0, 0],
+ [1, 1, 0, 0],
+ [1, 1, 0, 0],
+ [1, 1, 0, 0]
+ ])
+ );
+}
diff --git a/third_party/rust/smawk/tests/random_monge/mod.rs b/third_party/rust/smawk/tests/random_monge/mod.rs
new file mode 100644
index 0000000000..50a932fbeb
--- /dev/null
+++ b/third_party/rust/smawk/tests/random_monge/mod.rs
@@ -0,0 +1,83 @@
+//! Test functionality for generating random Monge matrices.
+
+// The code is put here so we can reuse it in different integration
+// tests, without Cargo finding it when `cargo test` is run. See the
+// section on "Submodules in Integration Tests" in
+// https://doc.rust-lang.org/book/ch11-03-test-organization.html
+
+use ndarray::{s, Array2};
+use num_traits::PrimInt;
+use rand::distributions::{Distribution, Standard};
+use rand::Rng;
+
+/// A Monge matrix can be decomposed into one of these primitive
+/// building blocks.
+#[derive(Copy, Clone)]
+pub enum MongePrim {
+ ConstantRows,
+ ConstantCols,
+ UpperRightOnes,
+ LowerLeftOnes,
+}
+
+impl MongePrim {
+ /// Generate a Monge matrix from a primitive.
+ pub fn to_matrix<T: PrimInt, R: Rng>(&self, m: usize, n: usize, rng: &mut R) -> Array2<T>
+ where
+ Standard: Distribution<T>,
+ {
+ let mut matrix = Array2::from_elem((m, n), T::zero());
+ // Avoid panic in UpperRightOnes and LowerLeftOnes below.
+ if m == 0 || n == 0 {
+ return matrix;
+ }
+
+ match *self {
+ MongePrim::ConstantRows => {
+ for mut row in matrix.rows_mut() {
+ if rng.gen::<bool>() {
+ row.fill(T::one())
+ }
+ }
+ }
+ MongePrim::ConstantCols => {
+ for mut col in matrix.columns_mut() {
+ if rng.gen::<bool>() {
+ col.fill(T::one())
+ }
+ }
+ }
+ MongePrim::UpperRightOnes => {
+ let i = rng.gen_range(0..(m + 1) as isize);
+ let j = rng.gen_range(0..(n + 1) as isize);
+ matrix.slice_mut(s![..i, -j..]).fill(T::one());
+ }
+ MongePrim::LowerLeftOnes => {
+ let i = rng.gen_range(0..(m + 1) as isize);
+ let j = rng.gen_range(0..(n + 1) as isize);
+ matrix.slice_mut(s![-i.., ..j]).fill(T::one());
+ }
+ }
+
+ matrix
+ }
+}
+
+/// Generate a random Monge matrix.
+pub fn random_monge_matrix<R: Rng, T: PrimInt>(m: usize, n: usize, rng: &mut R) -> Array2<T>
+where
+ Standard: Distribution<T>,
+{
+ let monge_primitives = [
+ MongePrim::ConstantRows,
+ MongePrim::ConstantCols,
+ MongePrim::LowerLeftOnes,
+ MongePrim::UpperRightOnes,
+ ];
+ let mut matrix = Array2::from_elem((m, n), T::zero());
+ for _ in 0..(m + n) {
+ let monge = monge_primitives[rng.gen_range(0..monge_primitives.len())];
+ matrix = matrix + monge.to_matrix(m, n, rng);
+ }
+ matrix
+}
diff --git a/third_party/rust/smawk/tests/version-numbers.rs b/third_party/rust/smawk/tests/version-numbers.rs
new file mode 100644
index 0000000000..288592d02f
--- /dev/null
+++ b/third_party/rust/smawk/tests/version-numbers.rs
@@ -0,0 +1,9 @@
+#[test]
+fn test_readme_deps() {
+ version_sync::assert_markdown_deps_updated!("README.md");
+}
+
+#[test]
+fn test_html_root_url() {
+ version_sync::assert_html_root_url_updated!("src/lib.rs");
+}