Mon, 24 Oct 2022 09:41:43 +0300
Allow step closure of AlgIterators to indicate succesfull termination or failure.
0 | 1 | ///! Presetnation of cubes $[a_1, b_1] × ⋯ × [a_n, b_n]$ |
2 | ||
3 | use serde::ser::{Serialize, Serializer, SerializeTupleStruct}; | |
4 | use crate::types::*; | |
5 | use crate::loc::Loc; | |
6 | use crate::sets::SetOrd; | |
7 | use crate::maputil::{ | |
8 | FixedLength, | |
9 | FixedLengthMut, | |
10 | map1, | |
11 | map1_indexed, | |
12 | map2, | |
13 | }; | |
14 | ||
15 | /// A half-open `N`-cube of elements of type `U`. | |
16 | #[derive(Copy, Clone, Debug, Eq, PartialEq)] | |
17 | pub struct Cube<U : Num, const N : usize>(pub(super) [[U; 2]; N]); | |
18 | ||
19 | // Need to manually implement as [F; N] serialisation is provided only for some N. | |
20 | impl<F : Num + Serialize, const N : usize> Serialize for Cube<F, N> | |
21 | where | |
22 | F: Serialize, | |
23 | { | |
24 | fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> | |
25 | where | |
26 | S: Serializer, | |
27 | { | |
28 | let mut ts = serializer.serialize_tuple_struct("Cube", N)?; | |
29 | for e in self.0.iter() { | |
30 | ts.serialize_field(e)?; | |
31 | } | |
32 | ts.end() | |
33 | } | |
34 | } | |
35 | ||
36 | impl<A : Num, const N : usize> FixedLength<N> for Cube<A,N> { | |
37 | type Iter = std::array::IntoIter<[A; 2], N>; | |
38 | type Elem = [A; 2]; | |
39 | #[inline] | |
40 | fn fl_iter(self) -> Self::Iter { | |
41 | self.0.into_iter() | |
42 | } | |
43 | } | |
44 | ||
45 | impl<A : Num, const N : usize> FixedLengthMut<N> for Cube<A,N> { | |
46 | type IterMut<'a> = std::slice::IterMut<'a, [A; 2]>; | |
47 | #[inline] | |
48 | fn fl_iter_mut(&mut self) -> Self::IterMut<'_> { | |
49 | self.0.iter_mut() | |
50 | } | |
51 | } | |
52 | ||
53 | impl<'a, A : Num, const N : usize> FixedLength<N> for &'a Cube<A,N> { | |
54 | type Iter = std::slice::Iter<'a, [A; 2]>; | |
55 | type Elem = &'a [A; 2]; | |
56 | #[inline] | |
57 | fn fl_iter(self) -> Self::Iter { | |
58 | self.0.iter() | |
59 | } | |
60 | } | |
61 | ||
62 | ||
63 | /// Iterator for [`Cube`] corners. | |
64 | pub struct CubeCornersIter<'a, U : Num, const N : usize> { | |
65 | index : usize, | |
66 | cube : &'a Cube<U, N>, | |
67 | } | |
68 | ||
69 | impl<'a, U : Num, const N : usize> Iterator for CubeCornersIter<'a, U, N> { | |
70 | type Item = Loc<U, N>; | |
71 | #[inline] | |
72 | fn next(&mut self) -> Option<Self::Item> { | |
73 | if self.index >= N { | |
74 | None | |
75 | } else { | |
76 | let i = self.index; | |
77 | self.index += 1; | |
78 | let arr = self.cube.map_indexed(|k, a, b| if (i>>k)&1 == 0 { a } else { b }); | |
79 | Some(arr.into()) | |
80 | } | |
81 | } | |
82 | } | |
83 | ||
84 | impl<U : Num, const N : usize> Cube<U, N> { | |
85 | #[inline] | |
86 | pub fn map_indexed<T>(&self, f : impl Fn(usize, U, U) -> T) -> [T; N] { | |
87 | map1_indexed(self, |i, &[a, b]| f(i, a, b)) | |
88 | } | |
89 | ||
90 | #[inline] | |
91 | pub fn map<T>(&self, f : impl Fn(U, U) -> T) -> [T; N] { | |
92 | map1(self, |&[a, b]| f(a, b)) | |
93 | } | |
94 | ||
95 | #[inline] | |
96 | pub fn iter_coords(&self) -> std::slice::Iter<'_, [U; 2]> { | |
97 | self.0.iter() | |
98 | } | |
99 | ||
100 | #[inline] | |
101 | pub fn start(&self, i : usize) -> U { | |
102 | self.0[i][0] | |
103 | } | |
104 | ||
105 | #[inline] | |
106 | pub fn end(&self, i : usize) -> U { | |
107 | self.0[i][1] | |
108 | } | |
109 | ||
110 | #[inline] | |
111 | pub fn span_start(&self) -> Loc<U, N> { | |
112 | Loc::new(self.map(|a, _b| a)) | |
113 | } | |
114 | ||
115 | #[inline] | |
116 | pub fn span_end(&self) -> Loc<U, N> { | |
117 | Loc::new(self.map(|_a, b| b)) | |
118 | } | |
119 | ||
120 | #[inline] | |
121 | pub fn iter_corners(&self) -> CubeCornersIter<'_, U, N> { | |
122 | CubeCornersIter{ index : 0, cube : self } | |
123 | } | |
124 | ||
125 | #[inline] | |
126 | pub fn width(&self) -> Loc<U, N> { | |
127 | Loc::new(self.map(|a, b| b-a)) | |
128 | } | |
129 | ||
130 | #[inline] | |
131 | pub fn shift(&self, shift : &Loc<U, N>) -> Self { | |
132 | let mut cube = self.clone(); | |
133 | for i in 0..N { | |
134 | cube.0[i][0] += shift[i]; | |
135 | cube.0[i][1] += shift[i]; | |
136 | } | |
137 | cube | |
138 | } | |
139 | ||
140 | #[inline] | |
141 | pub fn new(data : [[U; 2]; N]) -> Self { | |
142 | Cube(data) | |
143 | } | |
144 | } | |
145 | ||
146 | impl<F : Float, const N : usize> Cube<F, N> { | |
147 | /// Returns the centre of the cube | |
148 | pub fn center(&self) -> Loc<F, N> { | |
149 | map1(self, |&[a, b]| (a + b) / F::TWO).into() | |
150 | } | |
151 | } | |
152 | ||
153 | impl<U : Num> Cube<U, 1> { | |
154 | /// Get the corners of the cube. | |
155 | /// TODO: generic implementation once const-generics can be involved in | |
156 | /// calculations. | |
157 | #[inline] | |
158 | pub fn corners(&self) -> [Loc<U, 1>; 2] { | |
159 | let [[a, b]] = self.0; | |
160 | [a.into(), b.into()] | |
161 | } | |
162 | } | |
163 | ||
164 | impl<U : Num> Cube<U, 2> { | |
165 | /// Get the corners of the cube in counter-clockwise order. | |
166 | /// TODO: generic implementation once const-generics can be involved in | |
167 | /// calculations. | |
168 | #[inline] | |
169 | pub fn corners(&self) -> [Loc<U, 2>; 4] { | |
170 | let [[a1, b1], [a2, b2]]=self.0; | |
171 | [[a1, a2].into(), | |
172 | [b1, a2].into(), | |
173 | [b1, b2].into(), | |
174 | [a1, b2].into()] | |
175 | } | |
176 | } | |
177 | ||
178 | impl<U : Num> Cube<U, 3> { | |
179 | /// Get the corners of the cube. | |
180 | /// TODO: generic implementation once const-generics can be involved in | |
181 | /// calculations. | |
182 | #[inline] | |
183 | pub fn corners(&self) -> [Loc<U, 3>; 8] { | |
184 | let [[a1, b1], [a2, b2], [a3, b3]]=self.0; | |
185 | [[a1, a2, a3].into(), | |
186 | [b1, a2, a3].into(), | |
187 | [b1, b2, a3].into(), | |
188 | [a1, b2, a3].into(), | |
189 | [a1, b2, b3].into(), | |
190 | [b1, b2, b3].into(), | |
191 | [b1, a2, b3].into(), | |
192 | [a1, a2, b3].into()] | |
193 | } | |
194 | } | |
195 | ||
196 | // TODO: Implement Add and Sub of Loc to Cube, and Mul and Div by U : Num. | |
197 | ||
198 | impl<U : Num, const N : usize> From<[[U; 2]; N]> for Cube<U, N> { | |
199 | #[inline] | |
200 | fn from(data : [[U; 2]; N]) -> Self { | |
201 | Cube(data) | |
202 | } | |
203 | } | |
204 | ||
205 | impl<U : Num, const N : usize> From<Cube<U, N>> for [[U; 2]; N] { | |
206 | #[inline] | |
207 | fn from(Cube(data) : Cube<U, N>) -> Self { | |
208 | data | |
209 | } | |
210 | } | |
211 | ||
212 | ||
213 | impl<U, const N : usize> Cube<U, N> where U : Num + PartialOrd { | |
214 | /// Checks whether the cube is non-degenerate, i.e., the start coordinate | |
215 | /// of each axis is strictly less than the end coordinate. | |
216 | #[inline] | |
217 | pub fn nondegenerate(&self) -> bool { | |
218 | self.0.iter().all(|range| range[0] < range[1]) | |
219 | } | |
220 | ||
221 | /// Checks whether the cube intersects some `other` cube. | |
222 | /// Matching boundary points are not counted, so `U` is ideally a [`Float`]. | |
223 | #[inline] | |
224 | pub fn intersects(&self, other : &Cube<U, N>) -> bool { | |
225 | self.iter_coords().zip(other.iter_coords()).all(|([a1, b1], [a2, b2])| { | |
226 | a1 < b2 && a2 < b1 | |
227 | }) | |
228 | } | |
229 | ||
230 | /// Checks whether the cube contains some `other` cube. | |
231 | pub fn contains_set(&self, other : &Cube<U, N>) -> bool { | |
232 | self.iter_coords().zip(other.iter_coords()).all(|([a1, b1], [a2, b2])| { | |
233 | a1 <= a2 && b1 >= b2 | |
234 | }) | |
235 | } | |
236 | ||
237 | /// Produces the point of minimum $ℓ^p$-norm within the cube `self` for any $p$-norm. | |
238 | /// This is the point where each coordinate is closest to zero. | |
239 | #[inline] | |
240 | pub fn minnorm_point(&self) -> Loc<U, N> { | |
241 | let z = U::ZERO; | |
242 | // As always, we assume that a ≤ b. | |
243 | self.map(|a, b| { | |
244 | debug_assert!(a <= b); | |
245 | match (a < z, z < b) { | |
246 | (false, _) => a, | |
247 | (_, false) => b, | |
248 | (true, true) => z | |
249 | } | |
250 | }).into() | |
251 | } | |
252 | ||
253 | /// Produces the point of maximum $ℓ^p$-norm within the cube `self` for any $p$-norm. | |
254 | /// This is the point where each coordinate is furthest from zero. | |
255 | #[inline] | |
256 | pub fn maxnorm_point(&self) -> Loc<U, N> { | |
257 | let z = U::ZERO; | |
258 | // As always, we assume that a ≤ b. | |
259 | self.map(|a, b| { | |
260 | debug_assert!(a <= b); | |
261 | match (a < z, z < b) { | |
262 | (false, _) => b, | |
263 | (_, false) => a, | |
264 | // A this stage we must have a < 0 (so U must be signed), and want to check | |
265 | // whether |a| > |b|. We can do this without assuming U to actually implement | |
266 | // `Neg` by comparing whether 0 > a + b. | |
267 | (true, true) => if z > a + b { a } else { b } | |
268 | } | |
269 | }).into() | |
270 | } | |
271 | } | |
272 | ||
273 | macro_rules! impl_common { | |
274 | ($($t:ty)*, $min:ident, $max:ident) => { $( | |
275 | impl<const N : usize> SetOrd for Cube<$t, N> { | |
276 | #[inline] | |
277 | fn common(&self, other : &Self) -> Self { | |
278 | map2(self, other, |&[a1, b1], &[a2, b2]| { | |
279 | debug_assert!(a1 <= b1 && a2 <= b2); | |
280 | [a1.$min(a2), b1.$max(b2)] | |
281 | }).into() | |
282 | } | |
283 | ||
284 | #[inline] | |
285 | fn intersect(&self, other : &Self) -> Option<Self> { | |
286 | let arr = map2(self, other, |&[a1, b1], &[a2, b2]| { | |
287 | debug_assert!(a1 <= b1 && a2 <= b2); | |
288 | [a1.$max(a2), b1.$min(b2)] | |
289 | }); | |
290 | arr.iter().all(|&[a, b]| a >= b).then(|| arr.into()) | |
291 | } | |
292 | } | |
293 | )* } | |
294 | } | |
295 | ||
296 | impl_common!(u8 u16 u32 u64 u128 usize | |
297 | i8 i16 i32 i64 i128 isize, min, max); | |
298 | // Any NaN yields NaN | |
299 | impl_common!(f32 f64, minimum, maximum); | |
300 | ||
301 | impl<U : Num, const N : usize> std::ops::Index<usize> for Cube<U, N> { | |
302 | type Output = [U; 2]; | |
303 | #[inline] | |
304 | fn index(&self, index: usize) -> &Self::Output { | |
305 | &self.0[index] | |
306 | } | |
307 | } | |
308 | ||
309 | impl<U : Num, const N : usize> std::ops::IndexMut<usize> for Cube<U, N> { | |
310 | #[inline] | |
311 | fn index_mut(&mut self, index: usize) -> &mut Self::Output { | |
312 | &mut self.0[index] | |
313 | } | |
314 | } |