aboutsummaryrefslogtreecommitdiff
path: root/vendor/smawk/tests
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/smawk/tests')
-rw-r--r--vendor/smawk/tests/agreement.rs104
-rw-r--r--vendor/smawk/tests/complexity.rs83
-rw-r--r--vendor/smawk/tests/monge.rs83
-rw-r--r--vendor/smawk/tests/random_monge/mod.rs83
-rw-r--r--vendor/smawk/tests/version-numbers.rs9
5 files changed, 0 insertions, 362 deletions
diff --git a/vendor/smawk/tests/agreement.rs b/vendor/smawk/tests/agreement.rs
deleted file mode 100644
index 2e0343a..0000000
--- a/vendor/smawk/tests/agreement.rs
+++ /dev/null
@@ -1,104 +0,0 @@
-#![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/vendor/smawk/tests/complexity.rs b/vendor/smawk/tests/complexity.rs
deleted file mode 100644
index c9881ea..0000000
--- a/vendor/smawk/tests/complexity.rs
+++ /dev/null
@@ -1,83 +0,0 @@
-#![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/vendor/smawk/tests/monge.rs b/vendor/smawk/tests/monge.rs
deleted file mode 100644
index 67058a7..0000000
--- a/vendor/smawk/tests/monge.rs
+++ /dev/null
@@ -1,83 +0,0 @@
-#![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/vendor/smawk/tests/random_monge/mod.rs b/vendor/smawk/tests/random_monge/mod.rs
deleted file mode 100644
index 50a932f..0000000
--- a/vendor/smawk/tests/random_monge/mod.rs
+++ /dev/null
@@ -1,83 +0,0 @@
-//! 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/vendor/smawk/tests/version-numbers.rs b/vendor/smawk/tests/version-numbers.rs
deleted file mode 100644
index 288592d..0000000
--- a/vendor/smawk/tests/version-numbers.rs
+++ /dev/null
@@ -1,9 +0,0 @@
-#[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");
-}
Copyright © 2024 Valentin A. Popov. All Rights Reverse Engineered.