spiral/
lib.rs

1//! Iterators to iterate 2D structures in spiral patterns
2//!
3//! # Usage
4//!
5//! This crate is [on crates.io](htpps://crates.io/crates/spiral) and can be used by adding
6//! `spiral` to the dependencies in your project's `Cargo.toml`.
7//!
8//! ```toml
9//! [dependencies]
10//! spiral = "0.2"
11//! ```
12//!
13//! # Examples
14//!
15//! ```rust
16//! use spiral::ChebyshevIterator;
17//!
18//! let center_x = 3;
19//! let center_y = 3;
20//! let radius = 4;
21//! let iterator = ChebyshevIterator::new(center_x, center_y, radius);
22//! for (x, y) in iterator {
23//!     // Iterates over a 7x7 2D array with `x` & `y`.
24//! }
25//! ```
26//!
27//! ```rust
28//! use spiral::ManhattanIterator;
29//!
30//! let center_x = 3;
31//! let center_y = 3;
32//! let radius = 4;
33//! for (x, y) in ManhattanIterator::new(center_x, center_y, radius) {
34//!     // Iterates over a 7x7 2D array with `x` & `y`.
35//! }
36//! ```
37
38use num_traits::{FromPrimitive, PrimInt, WrappingAdd, WrappingSub};
39
40/// Simple trait so we don't have to wrap write all the num signatures that we want every time.
41pub trait Int: PrimInt + FromPrimitive + WrappingAdd + WrappingSub {}
42impl<I: PrimInt + FromPrimitive + WrappingAdd + WrappingSub> Int for I {}
43
44/// Which leg the iterator is in.
45#[derive(Debug, Copy, Clone)]
46enum Leg {
47    /// Center of the iterator, should only be triggered once.
48    Center,
49    Right,
50    Top,
51    Left,
52    Bottom,
53}
54
55/// An iterator iterating in a spiral fashion with the Chebyshev distance function.
56///
57/// The distance function is defined as:
58///
59/// `distance = max(absolute x offset from center, absolute y offset from center)`.
60///
61/// This creates a rectangular-shaped spiral.
62#[derive(Debug, Clone)]
63pub struct ChebyshevIterator<I: Int> {
64    max_distance: I,
65    start_x: I,
66    start_y: I,
67
68    x: I,
69    y: I,
70    layer: I,
71    leg: Leg,
72}
73
74impl<I: Int> ChebyshevIterator<I> {
75    /// Create a new iterator using the Chebyshev distance function
76    ///
77    /// # Arguments
78    ///
79    /// * `x` - The x position of the center of the spiral
80    /// * `y` - The y position of the center of the spiral
81    /// * `max_distance` - The radius of the spiral
82    ///
83    /// # Example
84    /// ```
85    /// use spiral::ChebyshevIterator;
86    ///
87    /// let spiral = ChebyshevIterator::new(3, 3, 4);
88    /// for (x, y) in spiral {
89    ///     // Iterates over 7x7 2D array with 'x' & 'y' following this pattern:
90    ///
91    ///     // 43  44  45  46  47  48  49
92    ///     // 42  21  22  23  24  25  26
93    ///     // 41  20   7   8   9  10  27
94    ///     // 40  19   6   1   2  11  28
95    ///     // 39  18   5   4   3  12  29
96    ///     // 38  17  16  15  14  13  30
97    ///     // 37  36  35  34  33  32  31
98    /// }
99    /// ```
100    pub fn new(x: I, y: I, max_distance: I) -> Self {
101        ChebyshevIterator {
102            max_distance,
103            start_x: x,
104            start_y: y,
105
106            x: I::zero(),
107            y: I::zero(),
108            layer: I::one(),
109            leg: Leg::Center,
110        }
111    }
112}
113
114impl<I: Int> Iterator for ChebyshevIterator<I> {
115    type Item = (I, I);
116
117    fn next(&mut self) -> Option<(I, I)> {
118        match self.leg {
119            Leg::Center => {
120                self.leg = Leg::Right;
121            }
122            Leg::Right => {
123                self.x = self.x.wrapping_add(&I::one());
124
125                if self.x == self.layer {
126                    self.leg = Leg::Top;
127
128                    if self.layer == self.max_distance {
129                        return None;
130                    }
131                }
132            }
133            Leg::Top => {
134                self.y = self.y.wrapping_add(&I::one());
135
136                if self.y == self.layer {
137                    self.leg = Leg::Left;
138                }
139            }
140            Leg::Left => {
141                self.x = self.x.wrapping_sub(&I::one());
142
143                // -self.x == self.layer
144                if self.x.wrapping_add(&self.layer).is_zero() {
145                    self.leg = Leg::Bottom;
146                }
147            }
148            Leg::Bottom => {
149                self.y = self.y.wrapping_sub(&I::one());
150
151                // -self.y == self.layer
152                if self.y.wrapping_add(&self.layer).is_zero() {
153                    self.leg = Leg::Right;
154
155                    self.layer = self.layer.add(I::one());
156                }
157            }
158        }
159
160        Some((
161            self.start_x.wrapping_add(&self.x),
162            self.start_y.wrapping_add(&self.y),
163        ))
164    }
165}
166
167/// An iterator iterating in a spiral fashion with the Manhattan distance function.
168///
169/// The distance function is defined as:
170///
171/// `distance = absolute x offset from center + absolute y offset from center`.
172///
173/// This creates a diamond-shaped spiral.
174#[derive(Debug, Clone)]
175pub struct ManhattanIterator<I: Int> {
176    max_distance: I,
177    start_x: I,
178    start_y: I,
179
180    x: I,
181    y: I,
182    layer: I,
183    leg: Leg,
184}
185
186impl<I: Int> ManhattanIterator<I> {
187    /// Create a new iterator using the Manhattan distance function
188    ///
189    /// # Arguments
190    ///
191    /// * `x` - The x position of the center of the spiral
192    /// * `y` - The y position of the center of the spiral
193    /// * `max_distance` - The radius of the spiral
194    ///
195    /// # Example
196    /// ```
197    /// use spiral::ManhattanIterator;
198    ///
199    /// let spiral = ManhattanIterator::new(3, 3, 4);
200    /// for (x, y) in spiral {
201    ///     // Iterates over 7x7 2D array with 'x' & 'y' following this pattern:
202    ///
203    ///     //  0   0   0  23   0   0   0
204    ///     //  0   0  22  12  24   0   0
205    ///     //  0  21  11   5  13  25   0
206    ///     // 20  10   4   1   2   6  14
207    ///     //  0  19   9   3   7  15   0
208    ///     //  0   0  18   8  16   0   0
209    ///     //  0   0   0  17   0   0   0
210    /// }
211    /// ```
212    pub fn new(x: I, y: I, max_distance: I) -> Self {
213        ManhattanIterator {
214            max_distance,
215            start_x: x,
216            start_y: y,
217
218            x: I::from_u8(2).expect("Could not instantiate number"),
219            // -1
220            y: I::zero().wrapping_sub(&I::one()),
221
222            layer: I::one(),
223            leg: Leg::Center,
224        }
225    }
226}
227
228impl<I: Int> Iterator for ManhattanIterator<I> {
229    type Item = (I, I);
230
231    fn next(&mut self) -> Option<(I, I)> {
232        match self.leg {
233            Leg::Center => {
234                self.leg = Leg::Right;
235
236                return Some((self.start_x, self.start_y));
237            }
238            Leg::Right => {
239                if self.max_distance == I::one() {
240                    return None;
241                }
242
243                self.x = self.x.wrapping_sub(&I::one());
244                self.y = self.y.wrapping_add(&I::one());
245
246                if self.x.is_zero() {
247                    self.leg = Leg::Top;
248                }
249            }
250            Leg::Top => {
251                self.x = self.x.wrapping_sub(&I::one());
252                self.y = self.y.wrapping_sub(&I::one());
253
254                if self.y.is_zero() {
255                    self.leg = Leg::Left;
256                }
257            }
258            Leg::Left => {
259                self.x = self.x.wrapping_add(&I::one());
260                self.y = self.y.wrapping_sub(&I::one());
261
262                if self.x.is_zero() {
263                    self.leg = Leg::Bottom;
264                }
265            }
266            Leg::Bottom => {
267                self.x = self.x.wrapping_add(&I::one());
268                self.y = self.y.wrapping_add(&I::one());
269
270                if self.y.is_zero() {
271                    self.x = self.x.wrapping_add(&I::one());
272                    self.leg = Leg::Right;
273
274                    self.layer = self.layer.wrapping_add(&I::one());
275
276                    if self.layer == self.max_distance {
277                        return None;
278                    }
279                }
280            }
281        }
282
283        Some((self.start_x + self.x, self.start_y + self.y))
284    }
285}
286
287#[cfg(test)]
288mod tests {
289    use super::*;
290
291    #[test]
292    fn output() {
293        const SIZE: usize = 7;
294
295        println!("Manhattan");
296        let mut output: [i32; SIZE * SIZE] = [0; SIZE * SIZE];
297
298        let mut current = 0;
299        let spiral = ManhattanIterator::new(3, 3, 4);
300        for (x, y) in spiral {
301            current += 1;
302
303            let index = x as usize + (y as usize * SIZE);
304            output[index] = current;
305        }
306
307        for y in 0..SIZE {
308            for x in 0..SIZE {
309                let index = x as usize + (y as usize * SIZE);
310                let output_val = output[index];
311
312                print!("{:3} ", output_val);
313            }
314            println!();
315        }
316
317        println!("Chebyshev");
318        output = [0; SIZE * SIZE];
319
320        current = 0;
321        let spiral = ChebyshevIterator::new(3, 3, 4);
322        for (x, y) in spiral {
323            current += 1;
324
325            let index = x as usize + (y as usize * SIZE);
326            output[index] = current;
327        }
328
329        for y in 0..SIZE {
330            for x in 0..SIZE {
331                let index = x as usize + (y as usize * SIZE);
332                let output_val = output[index];
333
334                print!("{:3} ", output_val);
335            }
336            println!();
337        }
338    }
339
340    #[test]
341    fn manhattan_bounds() {
342        for size in 1..100 {
343            let max_distance = size + 1;
344            for (x, y) in ManhattanIterator::new(0i16, 0i16, size) {
345                let distance = x.abs() + y.abs();
346                assert!(
347                    distance <= max_distance,
348                    "spiral was out of bounds: distance {}, size: {}, x: {}, y: {}",
349                    distance,
350                    size,
351                    x,
352                    y
353                );
354            }
355        }
356    }
357
358    #[test]
359    fn chebyshev_bounds() {
360        for size in 1..100 {
361            let max_distance = (size + 1) as i32;
362            for (x, y) in ChebyshevIterator::new(0i32, 0i32, size) {
363                let distance = std::cmp::max(x.abs(), y.abs());
364                assert!(
365                    distance <= max_distance,
366                    "spiral was out of bounds: distance {}, size: {}, x: {}, y: {}",
367                    distance,
368                    size,
369                    x,
370                    y
371                );
372            }
373        }
374    }
375
376    #[test]
377    fn manhattan() {
378        let expected: [i32; 3 * 3] = [0, 5, 0, 4, 1, 2, 0, 3, 0];
379
380        let mut current = 0;
381        for (x, y) in ManhattanIterator::new(1, 1, 2) {
382            current += 1;
383
384            let index = x + y * 3;
385
386            assert_eq!(expected[index as usize], current);
387        }
388
389        let expected: [i32; 5 * 5] = [
390            0, 0, 12, 0, 0, 0, 11, 5, 13, 0, 10, 4, 1, 2, 6, 0, 9, 3, 7, 0, 0, 0, 8, 0, 0,
391        ];
392
393        current = 0;
394        for (x, y) in ManhattanIterator::new(2, 2, 3) {
395            current += 1;
396
397            let index = x + y * 5;
398
399            assert_eq!(expected[index as usize], current);
400        }
401    }
402
403    #[test]
404    fn manhattan_unsigned() {
405        ManhattanIterator::new(0u32, 0u32, 4u32).for_each(drop);
406    }
407
408    #[test]
409    fn chebyshev() {
410        let expected: [i32; 5 * 5] = [
411            21, 22, 23, 24, 25, 20, 7, 8, 9, 10, 19, 6, 1, 2, 11, 18, 5, 4, 3, 12, 17, 16, 15, 14,
412            13,
413        ];
414
415        let mut current = 0;
416        for (x, y) in ChebyshevIterator::new(2i32, 2i32, 3i32) {
417            current += 1;
418
419            let index = x + y * 5;
420
421            assert_eq!(expected[index as usize], current);
422        }
423    }
424
425    #[test]
426    fn chebyshev_unsigned() {
427        let expected: [u32; 5 * 5] = [
428            21, 22, 23, 24, 25, 20, 7, 8, 9, 10, 19, 6, 1, 2, 11, 18, 5, 4, 3, 12, 17, 16, 15, 14,
429            13,
430        ];
431
432        let mut current = 0;
433        for (x, y) in ChebyshevIterator::new(2u32, 2u32, 3u32) {
434            current += 1;
435
436            let index = x + y * 5;
437
438            assert_eq!(expected[index as usize], current);
439        }
440    }
441}
spiral/lib.rs

spiral/
lib.rs
