moore_neighborhood/
lib.rs

1#![cfg_attr(not(feature = "std"), no_std)]
2
3/// Obtains the Moore neighborhood for a region of width `RANGE` for in the specified number of `DIMENSIONS`.
4/// The returned array has length `LENGTH`, which is determined as `(2*RANGE+1).pow(DIMENSIONS) - 1`.
5///
6/// ## Example
7///
8/// Using the default range with two dimensions:
9///
10/// ```rust
11/// use moore_neighborhood::moore;
12///
13/// fn main() {
14///     let result: [[isize; 2]; 8] = moore!(1);
15///
16///     let expected = [
17///         [-1,-1], [ 0,-1], [ 1,-1],
18///         [-1, 0],          [ 1, 0],
19///         [-1, 1], [ 0, 1], [ 1, 1]
20///     ];
21///
22///     assert_eq!(result, expected);
23/// }
24/// ```
25///
26/// Using a custom range (here: `1`) with two dimensions:
27///
28/// ```rust
29/// use moore_neighborhood::moore;
30///
31/// fn main() {
32///     let result: [[isize; 2]; 8] = moore!(1);
33///
34///     let expected = [
35///         [-1,-1], [ 0,-1], [ 1,-1],
36///         [-1, 0],          [ 1, 0],
37///         [-1, 1], [ 0, 1], [ 1, 1]
38///     ];
39///
40///     assert_eq!(result, expected);
41/// }
42/// ```
43///
44/// Using a custom range (here: `1`) with custom dimensions (here: `2`):
45///
46/// ```rust
47/// use moore_neighborhood::moore;
48///
49/// fn main() {
50///     let result: [[isize; 2]; 8] = moore!(1, 2);
51///
52///     let expected = [
53///         [-1,-1], [ 0,-1], [ 1,-1],
54///         [-1, 0],          [ 1, 0],
55///         [-1, 1], [ 0, 1], [ 1, 1]
56///     ];
57///
58///     assert_eq!(result, expected);
59/// }
60/// ```
61#[macro_export]
62macro_rules! moore {
63    ($range: tt, $dims: tt) => {{
64        const RANGE: u32 = $range;
65        const DIMS: usize = $dims;
66        const NUM_FIELDS: usize = ((2 * RANGE as usize + 1).pow(DIMS as u32) - 1);
67        $crate::generic_full::moore::<RANGE, DIMS, NUM_FIELDS>()
68    }};
69
70    ($range: tt) => {{
71        const RANGE: u32 = $range;
72        const DIMS: usize = 2;
73        const NUM_FIELDS: usize = ((2 * RANGE as usize + 1).pow(DIMS as u32) - 1);
74        $crate::generic_full::moore::<RANGE, DIMS, NUM_FIELDS>()
75    }};
76
77    () => {{
78        const RANGE: u32 = 1;
79        const DIMS: usize = 2;
80        const NUM_FIELDS: usize = ((2 * RANGE as usize + 1).pow(DIMS as u32) - 1);
81        $crate::generic_full::moore::<RANGE, DIMS, NUM_FIELDS>()
82    }};
83}
84
85/// Moore neighborhoods for dynamic ranges and dynamic dimensionality.
86#[cfg(feature = "std")]
87pub mod dynamic {
88    /// Obtains the Moore neighborhood for a region of width `range` for in the specified number of `dimensions`.
89    ///
90    /// ## Example
91    ///
92    /// ```rust
93    /// use moore_neighborhood::dynamic::moore;
94    ///
95    /// let result: Vec<Vec<isize>> = moore(1, 2);
96    ///
97    /// let expected = [
98    ///     [-1,-1], [ 0,-1], [ 1,-1],
99    ///     [-1, 0],          [ 1, 0],
100    ///     [-1, 1], [ 0, 1], [ 1, 1]
101    /// ];
102    ///
103    /// assert_eq!(result, expected);
104    /// ```
105    pub fn moore(range: u32, dimensions: u32) -> Vec<Vec<isize>> {
106        let size: usize = range as usize * 2 + 1;
107        let length: usize = size.pow(dimensions) - 1;
108        let half_length = length / 2;
109        let mut neighbors = Vec::with_capacity(length as _);
110
111        for i in 0usize..length {
112            let mut neighbor = Vec::with_capacity(dimensions as _);
113            let mut index = if i < half_length { i } else { i + 1 };
114            let mut prev_divisor = 1;
115            for _dimension in 0..dimensions {
116                let divisor = prev_divisor * size;
117                let value = index % divisor;
118                neighbor.push((value / prev_divisor) as isize - range as isize);
119                prev_divisor = divisor;
120                index -= value;
121            }
122
123            neighbors.push(neighbor);
124        }
125        neighbors
126    }
127
128    #[cfg(test)]
129    mod tests {
130        use super::*;
131
132        #[test]
133        fn dyn_d1_r1_works() {
134            let result = moore(1, 1);
135            let expected = [[-1], [1]];
136            assert_eq!(result, expected);
137        }
138
139        #[test]
140        fn dyn_d2_r1_works() {
141            let result = moore(1, 2);
142
143            #[rustfmt::skip]
144                let expected = [
145                [-1,-1], [ 0,-1], [ 1,-1],
146                [-1, 0],          [ 1, 0],
147                [-1, 1], [ 0, 1], [ 1, 1]
148            ];
149
150            assert_eq!(result, expected);
151        }
152
153        #[test]
154        fn dyn_d3_r1_works() {
155            let result = moore(1, 3);
156
157            #[rustfmt::skip]
158            let expected = [
159                [-1,-1,-1], [ 0,-1,-1], [ 1,-1,-1],
160                [-1, 0,-1], [ 0, 0,-1], [ 1, 0,-1],
161                [-1, 1,-1], [ 0, 1,-1], [ 1, 1,-1],
162
163                [-1,-1, 0], [ 0,-1, 0], [ 1,-1, 0],
164                [-1, 0, 0],             [ 1, 0, 0],
165                [-1, 1, 0], [ 0, 1, 0], [ 1, 1, 0],
166
167                [-1,-1, 1], [ 0,-1, 1], [ 1,-1, 1],
168                [-1, 0, 1], [ 0, 0, 1], [ 1, 0, 1],
169                [-1, 1, 1], [ 0, 1, 1], [ 1, 1, 1]
170            ];
171
172            assert_eq!(result, expected);
173        }
174
175        #[test]
176        fn dyn_same_as_reference() {
177            let result = moore(3, 3);
178            let expected = reference(3, 3);
179            assert_eq!(result, expected);
180        }
181
182        fn reference(range: u32, dimensions: u32) -> Vec<Vec<isize>> {
183            let size: usize = range as usize * 2 + 1;
184            let length: usize = size.pow(dimensions) - 1;
185            let mut neighbors = Vec::with_capacity(length as _);
186
187            for i in 0usize..length {
188                let mut neighbor = Vec::with_capacity(dimensions as _);
189                let mut index = if i < length / 2 { i } else { i + 1 };
190                for dimension in 1..=dimensions {
191                    let value = index % size.pow(dimension as _);
192                    neighbor.push((value / size.pow(dimension - 1)) as isize - range as isize);
193                    index -= value;
194                }
195
196                neighbors.push(neighbor);
197            }
198
199            neighbors
200        }
201    }
202}
203
204/// Moore neighborhoods for dynamic ranges and statically known dimensionality.
205#[cfg(feature = "std")]
206pub mod generic_dimension {
207    /// Obtains the Moore neighborhood for a region of width `range` for in the specified number of `DIMENSIONS`.
208    ///
209    /// ## Example
210    ///
211    /// ```rust
212    /// use moore_neighborhood::generic_dimension::moore;
213    ///
214    /// let result: Vec<[isize; 2]> = moore(1);
215    ///
216    /// let expected = [
217    ///     [-1,-1], [ 0,-1], [ 1,-1],
218    ///     [-1, 0],          [ 1, 0],
219    ///     [-1, 1], [ 0, 1], [ 1, 1]
220    /// ];
221    ///
222    /// assert_eq!(result, expected);
223    /// ```
224    pub fn moore<const DIMENSIONS: usize>(range: u32) -> Vec<[isize; DIMENSIONS]> {
225        assert!(DIMENSIONS < u32::MAX as _);
226
227        let size: usize = range as usize * 2 + 1;
228        let length: usize = size.pow(DIMENSIONS as _) - 1;
229        let half_length = length / 2;
230        let mut neighbors = Vec::with_capacity(length as _);
231
232        for i in 0usize..length {
233            let mut neighbor = [0; DIMENSIONS];
234            let mut index = if i < half_length { i } else { i + 1 };
235            let mut prev_divisor = 1;
236            for dimension in neighbor.iter_mut().take(DIMENSIONS) {
237                let divisor = prev_divisor * size;
238                let value = index % divisor;
239                *dimension = (value / prev_divisor) as isize - range as isize;
240                prev_divisor = divisor;
241                index -= value;
242            }
243
244            neighbors.push(neighbor);
245        }
246        neighbors
247    }
248
249    #[cfg(test)]
250    mod tests {
251        use super::*;
252
253        #[test]
254        fn gen_dim_d2_r1_works() {
255            let result: Vec<[isize; 2]> = moore(1);
256
257            #[rustfmt::skip]
258            let expected = [
259                [-1, -1], [0, -1], [1, -1],
260                [-1, 0], [1, 0],
261                [-1, 1], [0, 1], [1, 1]
262            ];
263
264            assert_eq!(result, expected);
265        }
266
267        #[test]
268        fn gen_dim_d2_r2_works() {
269            let result: Vec<[isize; 2]> = moore(2);
270
271            #[rustfmt::skip]
272            let expected = [
273                [-2, -2], [-1, -2], [ 0, -2], [ 1, -2], [ 2, -2],
274                [-2, -1], [-1, -1], [ 0, -1], [ 1, -1], [ 2, -1],
275                [-2,  0], [-1,  0],           [ 1,  0], [ 2,  0],
276                [-2,  1], [-1,  1], [ 0,  1], [ 1,  1], [ 2,  1],
277                [-2,  2], [-1,  2], [ 0,  2], [ 1,  2], [ 2,  2]
278            ];
279
280            assert_eq!(result, expected);
281        }
282
283        #[test]
284        fn gen_dim_d3_r1_works() {
285            let result = moore::<3>(1);
286
287            #[rustfmt::skip]
288            let expected = [
289                [-1, -1, -1], [ 0, -1, -1], [ 1, -1, -1],
290                [-1,  0, -1], [ 0,  0, -1], [ 1,  0, -1],
291                [-1,  1, -1], [ 0,  1, -1], [ 1,  1, -1],
292
293                [-1, -1,  0], [ 0, -1,  0], [ 1, -1,  0],
294                [-1,  0,  0],               [ 1,  0,  0],
295                [-1,  1,  0], [ 0,  1,  0], [ 1,  1,  0],
296
297                [-1, -1,  1], [ 0, -1,  1], [ 1, -1,  1],
298                [-1,  0,  1], [ 0,  0,  1], [ 1,  0,  1],
299                [-1,  1,  1], [ 0,  1,  1], [ 1,  1,  1]
300            ];
301
302            assert_eq!(result, expected);
303        }
304    }
305}
306
307/// Fully generic Moore neighborhoods for statically known ranges and dimensionality.
308pub mod generic_full {
309    /// Obtains the Moore neighborhood for a region of width `RANGE` for in the specified number of `DIMENSIONS`.
310    /// The returned array has length `LENGTH`, which is determined as `(2*RANGE+1).pow(DIMENSIONS) - 1`.
311    ///
312    /// ## Example
313    ///
314    /// ```rust
315    /// use moore_neighborhood::generic_full::moore;
316    ///
317    /// let result: [[isize; 2]; 8] = moore::<1, 2, 8>();
318    ///
319    /// let expected = [
320    ///     [-1,-1], [ 0,-1], [ 1,-1],
321    ///     [-1, 0],          [ 1, 0],
322    ///     [-1, 1], [ 0, 1], [ 1, 1]
323    /// ];
324    ///
325    /// assert_eq!(result, expected);
326    /// ```
327    #[inline]
328    pub fn moore<const RANGE: u32, const DIMENSIONS: usize, const LENGTH: usize>(
329    ) -> [[isize; DIMENSIONS]; LENGTH] {
330        assert!(DIMENSIONS < u32::MAX as _);
331
332        {
333            let size: usize = RANGE as usize * 2 + 1;
334            debug_assert_eq!(LENGTH, size.pow(DIMENSIONS as _) - 1);
335        }
336
337        let mut neighbors = [[0isize; DIMENSIONS]; LENGTH];
338        moore_prealloc::<RANGE, DIMENSIONS, LENGTH>(&mut neighbors);
339        neighbors
340    }
341
342    /// Obtains the Moore neighborhood for a region of width `RANGE` for in the specified number of `DIMENSIONS`.
343    /// The provided array needs to have a length of at least `LENGTH`, which is required to be `(2*RANGE+1).pow(DIMENSIONS) - 1`.
344    ///
345    /// ## Example
346    ///
347    /// ```rust
348    /// use moore_neighborhood::generic_full::moore_prealloc;
349    ///
350    /// let mut neighbors = [[0isize; 2]; 8];
351    /// let length = moore_prealloc::<1, 2, 8>(&mut neighbors);
352    ///
353    /// let expected = [
354    ///     [-1,-1], [ 0,-1], [ 1,-1],
355    ///     [-1, 0],          [ 1, 0],
356    ///     [-1, 1], [ 0, 1], [ 1, 1]
357    /// ];
358    ///
359    /// assert_eq!(length, 8);
360    /// assert_eq!(neighbors, expected);
361    /// ```
362    pub fn moore_prealloc<const RANGE: u32, const DIMENSIONS: usize, const LENGTH: usize>(
363        neighbors: &mut [[isize; DIMENSIONS]; LENGTH],
364    ) -> usize {
365        assert!(DIMENSIONS < u32::MAX as _);
366
367        let size: usize = RANGE as usize * 2 + 1;
368        let length = size.pow(DIMENSIONS as _) - 1;
369        debug_assert!(LENGTH >= length);
370
371        let half_length = LENGTH / 2;
372        for (i, neighbor) in neighbors.iter_mut().enumerate().take(LENGTH) {
373            let mut index = if i < half_length { i } else { i + 1 };
374            let mut prev_divisor = 1;
375            for dimension in neighbor.iter_mut().take(DIMENSIONS) {
376                let divisor = prev_divisor * size;
377                let value = index % divisor;
378                *dimension = (value / prev_divisor) as isize - RANGE as isize;
379                prev_divisor = divisor;
380                index -= value;
381            }
382        }
383        length
384    }
385
386    #[cfg(test)]
387    mod tests {
388        use super::*;
389
390        #[test]
391        fn gen_x_d2_r1_works() {
392            let result: [[isize; 2]; 8] = moore::<1, 2, 8>();
393
394            #[rustfmt::skip]
395            let expected = [
396                [-1,-1], [ 0,-1], [ 1,-1],
397                [-1, 0],          [ 1, 0],
398                [-1, 1], [ 0, 1], [ 1, 1]
399            ];
400
401            assert_eq!(result, expected);
402        }
403
404        #[test]
405        fn gen_x_d3_r1_works() {
406            let result = moore::<1, 3, 26>();
407
408            #[rustfmt::skip]
409            let expected = [
410                [-1,-1,-1], [ 0,-1,-1], [ 1,-1,-1],
411                [-1, 0,-1], [ 0, 0,-1], [ 1, 0,-1],
412                [-1, 1,-1], [ 0, 1,-1], [ 1, 1,-1],
413
414                [-1,-1, 0], [ 0,-1, 0], [ 1,-1, 0],
415                [-1, 0, 0],             [ 1, 0, 0],
416                [-1, 1, 0], [ 0, 1, 0], [ 1, 1, 0],
417
418                [-1,-1, 1], [ 0,-1, 1], [ 1,-1, 1],
419                [-1, 0, 1], [ 0, 0, 1], [ 1, 0, 1],
420                [-1, 1, 1], [ 0, 1, 1], [ 1, 1, 1]
421            ];
422
423            assert_eq!(result, expected);
424        }
425    }
426}
427
428#[cfg(test)]
429mod tests {
430    use super::*;
431
432    #[test]
433    fn macro_d1_r1_works() {
434        let result: [[isize; 1]; 2] = moore!(1, 1);
435        let expected = [[-1], [1]];
436        assert_eq!(result, expected);
437    }
438
439    #[test]
440    fn macro_d2_r1_works() {
441        let result: [[isize; 2]; 8] = moore!(1, 2);
442
443        #[rustfmt::skip]
444        let expected = [
445            [-1,-1], [ 0,-1], [ 1,-1],
446            [-1, 0],          [ 1, 0],
447            [-1, 1], [ 0, 1], [ 1, 1]
448        ];
449
450        assert_eq!(result, expected);
451    }
452}
moore_neighborhood/lib.rs

moore_neighborhood/
lib.rs
