# HG changeset patch # User Tuomo Valkonen # Date 1745783293 18000 # Node ID 9cb8225a3a41fb5674e5d327883c1179a219b90a # Parent 8513a10c5dd937c3fed7159cf9ca04ef46c2a981# Parent 123f7f38e16111947fc5d12021ccca7c2258f813 Start work on 0.4.0(-dev). diff -r 8513a10c5dd9 -r 9cb8225a3a41 Cargo.lock --- a/Cargo.lock Thu Jan 23 23:38:40 2025 +0100 +++ b/Cargo.lock Sun Apr 27 14:48:13 2025 -0500 @@ -4,7 +4,7 @@ [[package]] name = "alg_tools" -version = "0.3.0" +version = "0.3.1" dependencies = [ "anyhow", "colored", diff -r 8513a10c5dd9 -r 9cb8225a3a41 Cargo.toml --- a/Cargo.toml Thu Jan 23 23:38:40 2025 +0100 +++ b/Cargo.toml Sun Apr 27 14:48:13 2025 -0500 @@ -1,6 +1,6 @@ [package] name = "alg_tools" -version = "0.3.0" +version = "0.4.0-dev" edition = "2021" rust-version = "1.85" authors = ["Tuomo Valkonen "] @@ -8,7 +8,13 @@ homepage = "https://tuomov.iki.fi/software/alg_tools/" repository = "https://tuomov.iki.fi/repos/alg_tools/" license-file = "LICENSE" -keywords = ["iterative", "optimization", "bisection", "branch-and-bound", "numerical"] +keywords = [ + "iterative", + "optimization", + "bisection", + "branch-and-bound", + "numerical", +] categories = ["mathematics", "data-structures"] [dependencies] @@ -27,7 +33,7 @@ anyhow = "1.0.95" [package.metadata.docs.rs] -rustdoc-args = [ "--html-in-header", "katex-header.html" ] +rustdoc-args = ["--html-in-header", "katex-header.html"] [profile.release] @@ -36,5 +42,4 @@ [features] default = ["nightly"] use_custom_thread_pool = [] -nightly = [] # enable for higher-performance implementations of some things - +nightly = [] # enable for higher-performance implementations of some things diff -r 8513a10c5dd9 -r 9cb8225a3a41 src/lib.rs --- a/src/lib.rs Thu Jan 23 23:38:40 2025 +0100 +++ b/src/lib.rs Sun Apr 27 14:48:13 2025 -0500 @@ -8,7 +8,7 @@ #![allow(confusable_idents)] #![cfg_attr(feature = "nightly", - feature(maybe_uninit_uninit_array,maybe_uninit_array_assume_init,maybe_uninit_slice), + feature(maybe_uninit_array_assume_init,maybe_uninit_slice), feature(float_minimum_maximum), feature(get_mut_unchecked), feature(cow_is_borrowed), diff -r 8513a10c5dd9 -r 9cb8225a3a41 src/linsolve.rs --- a/src/linsolve.rs Thu Jan 23 23:38:40 2025 +0100 +++ b/src/linsolve.rs Sun Apr 27 14:48:13 2025 -0500 @@ -8,33 +8,33 @@ /// Gaussian elimination for $AX=B$, where $A$ and $B$ are both stored in `ab`, /// $A \in \mathbb{R}^{M \times M}$ and $X, B \in \mathbb{R}^{M \times K}$. -pub fn linsolve0( - mut ab : [[F; N]; M] +pub fn linsolve0( + mut ab: [[F; N]; M], ) -> [[F; K]; M] { - assert_eq!(M + K , N); + assert_eq!(M + K, N); let mut k = 0; // Convert to row-echelon form - for h in 0..(M-1) { + for h in 0..(M - 1) { // Find pivotable column (has some non-zero entries in rows ≥ h) 'find_pivot: while k < N { let (mut î, mut v) = (h, ab[h][k].abs()); // Find row ≥ h of maximum absolute value in this column - for i in (h+1)..M { + for i in (h + 1)..M { let ṽ = ab[i][k].abs(); - if ṽ > v { + if ṽ > v { î = i; v = ṽ; } } if v > F::ZERO { ab.swap(h, î); - for i in (h+1)..M { + for i in (h + 1)..M { let f = ab[i][k] / ab[h][k]; ab[i][k] = F::ZERO; - for j in (k+1)..N { - ab[i][j] -= ab[h][j]*f; + for j in (k + 1)..N { + ab[i][j] -= ab[h][j] * f; } } k += 1; @@ -52,12 +52,12 @@ // This use of MaybeUninit assumes F : Copy. Otherwise undefined behaviour may occur. #[cfg(feature = "nightly")] { - let mut x : [[MaybeUninit; K]; M] = core::array::from_fn(|_| MaybeUninit::uninit_array::() ); + let mut x: [[MaybeUninit; K]; M] = [[const { MaybeUninit::uninit() }; K]; M]; //unsafe { std::mem::MaybeUninit::uninit().assume_init() }; for i in (0..M).rev() { for 𝓁 in 0..K { - let mut tmp = ab[i][M+𝓁]; - for j in (i+1)..M { + let mut tmp = ab[i][M + 𝓁]; + for j in (i + 1)..M { tmp -= ab[i][j] * unsafe { *(x[j][𝓁].assume_init_ref()) }; } tmp /= ab[i][i]; @@ -71,11 +71,11 @@ } #[cfg(not(feature = "nightly"))] { - let mut x : [[F; K]; M] = [[F::ZERO; K]; M]; + let mut x: [[F; K]; M] = [[F::ZERO; K]; M]; for i in (0..M).rev() { for 𝓁 in 0..K { - let mut tmp = ab[i][M+𝓁]; - for j in (i+1)..M { + let mut tmp = ab[i][M + 𝓁]; + for j in (i + 1)..M { tmp -= ab[i][j] * x[j][𝓁]; } tmp /= ab[i][i]; @@ -89,12 +89,11 @@ /// Gaussian elimination for $Ax=b$, where $A$ and $b$ are both stored in `ab`, /// $A \in \mathbb{R}^{M \times M}$ and $x, b \in \mathbb{R}^M$. #[inline] -pub fn linsolve(ab : [[F; N]; M]) -> [F; M] { - let x : [[F; 1]; M] = linsolve0(ab); - unsafe { *((&x as *const [F; 1]) as *const [F; M] ) } +pub fn linsolve(ab: [[F; N]; M]) -> [F; M] { + let x: [[F; 1]; M] = linsolve0(ab); + unsafe { *((&x as *const [F; 1]) as *const [F; M]) } } - #[cfg(test)] mod tests { use super::*; @@ -103,8 +102,11 @@ fn linsolve_test() { let ab1 = [[1.0, 2.0, 3.0], [2.0, 1.0, 6.0]]; assert_eq!(linsolve(ab1), [3.0, 0.0]); - let ab2 = [[1.0, 2.0, 0.0, 1.0], [4.0, 0.0, 0.0, 0.0], [0.0, 0.0, 1.0, 0.0]]; + let ab2 = [ + [1.0, 2.0, 0.0, 1.0], + [4.0, 0.0, 0.0, 0.0], + [0.0, 0.0, 1.0, 0.0], + ]; assert_eq!(linsolve(ab2), [0.0, 0.5, 0.0]); } } - diff -r 8513a10c5dd9 -r 9cb8225a3a41 src/maputil.rs --- a/src/maputil.rs Thu Jan 23 23:38:40 2025 +0100 +++ b/src/maputil.rs Sun Apr 27 14:48:13 2025 -0500 @@ -2,34 +2,36 @@ Utilities for mapping over various container types. */ +use itertools::izip; #[cfg(feature = "nightly")] use std::mem::MaybeUninit; -use itertools::izip; /// Trait for a fixed-length container type. -/// +/// /// Implemented by [`Loc`][crate::loc::Loc] vectors, [`Cube`][crate::sets::Cube]s, /// and basic arrays. -pub trait FixedLength { +pub trait FixedLength { /// Type of elements of the container. type Elem; /// Type of iterators over the elements of the container. - type Iter : Iterator; + type Iter: Iterator; /// Returns an iteartor over the elements of the container. fn fl_iter(self) -> Self::Iter; } /// Trait for a mutable fixed-length container type. -pub trait FixedLengthMut : FixedLength { +pub trait FixedLengthMut: FixedLength { /// Type of iterators over references to mutable elements of the container. - type IterMut<'a> : Iterator where Self : 'a; + type IterMut<'a>: Iterator + where + Self: 'a; /// Returns an iterator over mutable references to elements of the container. fn fl_iter_mut(&mut self) -> Self::IterMut<'_>; } -impl FixedLength for [A; N] { +impl FixedLength for [A; N] { type Elem = A; type Iter = std::array::IntoIter; #[inline] @@ -38,15 +40,18 @@ } } -impl FixedLengthMut for [A; N] { - type IterMut<'a> = std::slice::IterMut<'a, A> where A : 'a; +impl FixedLengthMut for [A; N] { + type IterMut<'a> + = std::slice::IterMut<'a, A> + where + A: 'a; #[inline] fn fl_iter_mut(&mut self) -> Self::IterMut<'_> { self.iter_mut() } } -impl<'a, A, const N : usize> FixedLength for &'a [A; N] { +impl<'a, A, const N: usize> FixedLength for &'a [A; N] { type Elem = &'a A; type Iter = std::slice::Iter<'a, A>; #[inline] @@ -157,10 +162,9 @@ make_mapmany_mut!(map5_mut, map5_indexed_mut, a b c d e; A B C D E, CA CB CC CD CE); make_mapmany_mut!(map6_mut, map6_indexed_mut, a b c d e f; A B C D E F, CA CB CC CD CE CF); - /// Initialise an array of length `N` by calling `f` multiple times. #[inline] -pub fn array_init A, const N : usize>(f : F) -> [A; N] { +pub fn array_init A, const N: usize>(f: F) -> [A; N] { //[(); N].map(|_| f()) core::array::from_fn(|_| f()) } @@ -172,17 +176,17 @@ // core::array::from_fn(f) // } - - /// Iterator returned by [`foldmap`][FoldMappable::foldmap] applied to an iterator. -pub struct FoldMap, A, B, J : Copy, F : Fn(J, A) -> (J, B)> { - iter : I, - f : F, - j : J, +pub struct FoldMap, A, B, J: Copy, F: Fn(J, A) -> (J, B)> { + iter: I, + f: F, + j: J, } -impl, J : Copy, F : Fn(J, A) -> (J, B)> Iterator for FoldMap { +impl, J: Copy, F: Fn(J, A) -> (J, B)> Iterator + for FoldMap +{ type Item = B; #[inline] fn next(&mut self) -> Option { @@ -195,19 +199,19 @@ } /// Iterator returned by [`indexmap`][IndexMappable::indexmap] applied to an iterator. -pub struct IndexMap, A, B, F : Fn(usize, A) -> B> { - iter : I, - f : F, - j : usize, +pub struct IndexMap, A, B, F: Fn(usize, A) -> B> { + iter: I, + f: F, + j: usize, } -impl, F : Fn(usize, A) -> B> Iterator for IndexMap { +impl, F: Fn(usize, A) -> B> Iterator for IndexMap { type Item = B; #[inline] fn next(&mut self) -> Option { self.iter.next().map(|a| { let b = (self.f)(self.j, a); - self.j = self.j+1; + self.j = self.j + 1; b }) } @@ -216,68 +220,90 @@ /// Trait for things that can be foldmapped. /// /// `A` is the type of elements of `Self`, and `J` the accumulator type for the folding. -pub trait FoldMappable : Sized { - type Output where F : Fn(J, A) -> (J, B); +pub trait FoldMappable: Sized { + type Output + where + F: Fn(J, A) -> (J, B); /// Fold and map over `self` with `f`. `j` is the initial accumulator for folding. /// /// The output type depends on the implementation, but will generally have elements of /// type `B`. - fn foldmap (J, B)>(self, j : J, f : F) -> Self::Output; + fn foldmap (J, B)>(self, j: J, f: F) -> Self::Output; } /// Trait for things that can be indexmapped. /// /// `A` is the type of elements of `Self`. -pub trait IndexMappable : Sized { - type Output where F : Fn(usize, A) -> B; +pub trait IndexMappable : Sized { + type Output + where + F: Fn(usize, A) -> B; /// Map over element indices and elements of `self`. /// /// The output type depends on the implementation, but will generally have elements of /// type `B`. - fn indexmap B>(self, f : F) -> Self::Output; + fn indexmap B>(self, f: F) -> Self::Output; } -impl<'a, A, J : Copy> FoldMappable<&'a A, J> -for std::slice::Iter<'a, A> { - type Output = FoldMap where F : Fn(J, &'a A) -> (J, B); +impl<'a, A, J: Copy> FoldMappable<&'a A, J> for std::slice::Iter<'a, A> { + type Output + = FoldMap + where + F: Fn(J, &'a A) -> (J, B); #[inline] - fn foldmap (J, B)>(self, j : J, f : F) -> Self::Output { - FoldMap { iter : self, j, f } + fn foldmap (J, B)>(self, j: J, f: F) -> Self::Output { + FoldMap { iter: self, j, f } } } -impl<'a, A> IndexMappable<&'a A> -for std::slice::Iter<'a, A> { - type Output = IndexMap where F : Fn(usize, &'a A) -> B; +impl<'a, A> IndexMappable<&'a A> for std::slice::Iter<'a, A> { + type Output + = IndexMap + where + F: Fn(usize, &'a A) -> B; #[inline] - fn indexmap B>(self, f : F) -> Self::Output { - IndexMap { iter : self, j : 0, f } + fn indexmap B>(self, f: F) -> Self::Output { + IndexMap { + iter: self, + j: 0, + f, + } } } - -impl FoldMappable -for std::array::IntoIter { - type Output = FoldMap where F : Fn(J, A) -> (J, B); +impl FoldMappable for std::array::IntoIter { + type Output + = FoldMap + where + F: Fn(J, A) -> (J, B); #[inline] - fn foldmap (J, B)>(self, j : J, f : F) -> Self::Output { - FoldMap { iter : self, j, f } + fn foldmap (J, B)>(self, j: J, f: F) -> Self::Output { + FoldMap { iter: self, j, f } } } -impl<'a, A, const N : usize> IndexMappable -for std::array::IntoIter { - type Output = IndexMap where F : Fn(usize, A) -> B; +impl<'a, A, const N: usize> IndexMappable for std::array::IntoIter { + type Output + = IndexMap + where + F: Fn(usize, A) -> B; #[inline] - fn indexmap B>(self, f : F) -> Self::Output { - IndexMap { iter : self, j : 0, f } + fn indexmap B>(self, f: F) -> Self::Output { + IndexMap { + iter: self, + j: 0, + f, + } } } -impl FoldMappable for [A; N] { - type Output = [B; N] where F : Fn(J, A) -> (J, B); +impl FoldMappable for [A; N] { + type Output + = [B; N] + where + F: Fn(J, A) -> (J, B); #[inline] - fn foldmap (J, B)>(self, j : J, f : F) -> [B; N] { + fn foldmap (J, B)>(self, j: J, f: F) -> [B; N] { // //let mut res : [MaybeUninit; N] = unsafe { MaybeUninit::uninit().assume_init() }; // let mut res = MaybeUninit::uninit_array::(); // for (a, i) in self.into_iter().zip(0..N) { @@ -292,10 +318,13 @@ } } -impl IndexMappable for [A; N] { - type Output = [B; N] where F : Fn(usize, A) -> B; +impl IndexMappable for [A; N] { + type Output + = [B; N] + where + F: Fn(usize, A) -> B; #[inline] - fn indexmap B>(self, f : F) -> [B; N] { + fn indexmap B>(self, f: F) -> [B; N] { // //let mut res : [MaybeUninit; N] = unsafe { MaybeUninit::uninit().assume_init() }; // let mut res = MaybeUninit::uninit_array::(); // for (a, i) in self.into_iter().zip(0..N) { @@ -325,12 +354,9 @@ /// dropped. #[cfg(feature = "nightly")] #[inline] -pub(crate) fn collect_into_array_unchecked< - T, - I : Iterator, - const N: usize ->(mut iter: I) -> [T; N] -{ +pub(crate) fn collect_into_array_unchecked, const N: usize>( + mut iter: I, +) -> [T; N] { if N == 0 { // SAFETY: An empty array is always inhabited and has no validity invariants. return unsafe { core::mem::zeroed() }; @@ -348,22 +374,28 @@ // SAFETY: this slice will contain only initialized objects. unsafe { - core::ptr::drop_in_place(MaybeUninit::slice_assume_init_mut( - &mut self.array_mut.get_unchecked_mut(..self.initialized), - )); + for elem in self.array_mut.get_unchecked_mut(..self.initialized) { + elem.assume_init_drop(); + } } } } - let mut array = MaybeUninit::uninit_array::(); - let mut guard = Guard { array_mut: &mut array, initialized: 0 }; + let mut array = [const { MaybeUninit::uninit() }; N]; + let mut guard = Guard { + array_mut: &mut array, + initialized: 0, + }; while let Some(item) = iter.next() { // SAFETY: `guard.initialized` starts at 0, is increased by one in the // loop and the loop is aborted once it reaches N (which is // `array.len()`). unsafe { - guard.array_mut.get_unchecked_mut(guard.initialized).write(item); + guard + .array_mut + .get_unchecked_mut(guard.initialized) + .write(item); } guard.initialized += 1; @@ -383,12 +415,9 @@ #[cfg(not(feature = "nightly"))] #[inline] -pub(crate) fn collect_into_array_unchecked< - T, - I : Iterator, - const N: usize ->(iter: I) -> [T; N] -{ +pub(crate) fn collect_into_array_unchecked, const N: usize>( + iter: I, +) -> [T; N] { match iter.collect::>().try_into() { Ok(a) => a, Err(_) => panic!("collect_into_array failure: should not happen"), @@ -401,12 +430,12 @@ #[test] fn mapx_test() { - let a = [0,1,2]; - let mut b = [2,1,0]; - assert_eq!(map1(a, |x| x+1), [1,2,3]); - assert_eq!(map2(a, b, |x, y| x+y), [2,2,2]); - assert_eq!(map1_indexed(a, |i, y| y-i), [0,0,0]); - map1_indexed_mut(&mut b, |i, y| *y=i); + let a = [0, 1, 2]; + let mut b = [2, 1, 0]; + assert_eq!(map1(a, |x| x + 1), [1, 2, 3]); + assert_eq!(map2(a, b, |x, y| x + y), [2, 2, 2]); + assert_eq!(map1_indexed(a, |i, y| y - i), [0, 0, 0]); + map1_indexed_mut(&mut b, |i, y| *y = i); assert_eq!(b, a); } }