From a990de90fe41456a23e58bd087d2f107d321f3a1 Mon Sep 17 00:00:00 2001 From: Valentin Popov Date: Fri, 19 Jul 2024 16:37:58 +0400 Subject: Deleted vendor folder --- vendor/smawk/tests/agreement.rs | 104 --------------------------------- vendor/smawk/tests/complexity.rs | 83 -------------------------- vendor/smawk/tests/monge.rs | 83 -------------------------- vendor/smawk/tests/random_monge/mod.rs | 83 -------------------------- vendor/smawk/tests/version-numbers.rs | 9 --- 5 files changed, 362 deletions(-) delete mode 100644 vendor/smawk/tests/agreement.rs delete mode 100644 vendor/smawk/tests/complexity.rs delete mode 100644 vendor/smawk/tests/monge.rs delete mode 100644 vendor/smawk/tests/random_monge/mod.rs delete mode 100644 vendor/smawk/tests/version-numbers.rs (limited to 'vendor/smawk/tests') 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 = 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 = 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::>(); - 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 . -fn linear_regression(values: &[(usize, i32)]) -> LinRegression { - let xs = values.iter().map(|&(x, _)| x as f64).collect::>(); - let ys = values.iter().map(|&(_, y)| y as f64).collect::>(); - - 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 = 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 = 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 = 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 = 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 = 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 = 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(&self, m: usize, n: usize, rng: &mut R) -> Array2 - where - Standard: Distribution, - { - 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::() { - row.fill(T::one()) - } - } - } - MongePrim::ConstantCols => { - for mut col in matrix.columns_mut() { - if rng.gen::() { - 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(m: usize, n: usize, rng: &mut R) -> Array2 -where - Standard: Distribution, -{ - 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"); -} -- cgit v1.2.3