1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

use vek::*;

/// An iterator of coordinates that create a rectangular spiral out from the
/// origin
#[derive(Clone)]
pub struct Spiral2d {
    layer: i32,
    i: i32,
}

impl Spiral2d {
    #[allow(clippy::new_without_default)]
    /// Creates a new spiral starting at the origin
    pub fn new() -> Self { Self { layer: 0, i: 0 } }

    /// Creates an iterator over points in a spiral starting at the origin and
    /// going out to some radius
    pub fn with_radius(radius: i32) -> impl Iterator<Item = Vec2<i32>> {
        Self::new()
            .take((radius * 2 + 1).pow(2) as usize)
            .filter(move |pos| pos.magnitude_squared() < (radius + 1).pow(2))
    }

    /// Creates an iterator over points in the edge of a circle of some radius
    pub fn with_edge_radius(radius: i32) -> impl Iterator<Item = Vec2<i32>> {
        Self::new()
            .take((radius * 2 + 1).pow(2) as usize)
            .filter(move |pos| pos.magnitude_squared() < (radius + 1).pow(2))
            .filter(move |pos| pos.magnitude_squared() >= radius.pow(2))
    }

    /// Creates an iterator over points in the margin between two squares,
    /// inclusive of the inner_radius and exclusive of the outer_radius
    /// where outer_radius = inner_radius + margin
    /**
        Spiral2d iterates over the points in a square spiral pattern starting at the bottom left.
        In the ring spiral, the iteration starts at the bottom left of the inner square and
        does not include the outer square (if you think of the outer square as inner_radius + margin).
        +-----------------------+
        |        Margin         |
        |     +-----------+     |
        |     |           |     |
        |     |    Not    |     |
        |     | Included  |     |
        |     |           |     |
        |     +-----------+     |
        |                       |
        +-----------------------+
        For example, Spiral2d::with_ring(1, 2) yields the following output:
            Vec2 { x: -1, y: -1 }
            Vec2 { x: 0, y: -1 }
            Vec2 { x: 1, y: -1 }
            Vec2 { x: 1, y: 0 }
            Vec2 { x: 1, y: 1 }
            Vec2 { x: 0, y: 1 }
            Vec2 { x: -1, y: 1 }
            Vec2 { x: -1, y: 0 }
            Vec2 { x: -2, y: -2 }
            Vec2 { x: -1, y: -2 }
            Vec2 { x: 0, y: -2 }
            Vec2 { x: 1, y: -2 }
            Vec2 { x: 2, y: -2 }
            Vec2 { x: 2, y: -1 }
            Vec2 { x: 2, y: 0 }
            Vec2 { x: 2, y: 1 }
            Vec2 { x: 2, y: 2 }
            Vec2 { x: 1, y: 2 }
            Vec2 { x: 0, y: 2 }
            Vec2 { x: -1, y: 2 }
            Vec2 { x: -2, y: 2 }
            Vec2 { x: -2, y: 1 }
            Vec2 { x: -2, y: 0 }
            Vec2 { x: -2, y: -1 }
        Run the first test below to see this output.
    **/
    pub fn with_ring(inner_radius: u32, margin: u32) -> impl Iterator<Item = Vec2<i32>> {
        let outer_radius: u32 = inner_radius + margin - 1;
        let adjusted_inner_radius = if inner_radius > 0 {
            inner_radius - 1
        } else {
            0
        };
        Spiral2d {
            layer: inner_radius as i32,
            i: 0,
        }
        .take(
            (outer_radius * 2 + 1).pow(2) as usize
                - (adjusted_inner_radius * 2 + 1).pow(2) as usize,
        )
    }
}

impl Iterator for Spiral2d {
    type Item = Vec2<i32>;

    #[allow(clippy::erasing_op, clippy::identity_op)]
    fn next(&mut self) -> Option<Self::Item> {
        let layer_size = (self.layer * 8 + 4 * self.layer.min(1) - 4).max(1);
        if self.i >= layer_size {
            self.layer += 1;
            self.i = 0;
        }
        let layer_size = (self.layer * 8 + 4 * self.layer.min(1) - 4).max(1);

        let pos = Vec2::new(
            -self.layer + (self.i - (layer_size / 4) * 0).clamp(0, self.layer * 2)
                - (self.i - (layer_size / 4) * 2).clamp(0, self.layer * 2),
            -self.layer + (self.i - (layer_size / 4) * 1).clamp(0, self.layer * 2)
                - (self.i - (layer_size / 4) * 3).clamp(0, self.layer * 2),
        );

        self.i += 1;

        Some(pos)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn print_spiral_ring() {
        let spiral = Spiral2d::with_ring(1, 2);
        for pos in spiral {
            println!("{:?}", pos);
        }
    }

    #[test]
    fn empty_spiral_ring() {
        assert_eq!(Spiral2d::with_ring(0, 1).count(), 0);
        assert_eq!(Spiral2d::with_ring(0, 2).count(), 8);
    }

    #[test]
    fn minimum_spiral_ring() {
        let min_spiral_ring: Vec<Vec2<i32>> = vec![
            Vec2::new(-1, -1),
            Vec2::new(0, -1),
            Vec2::new(1, -1),
            Vec2::new(1, 0),
            Vec2::new(1, 1),
            Vec2::new(0, 1),
            Vec2::new(-1, 1),
            Vec2::new(-1, 0),
        ];
        let result: Vec<Vec2<i32>> = Spiral2d::with_ring(1, 1).collect();
        assert_eq!(result, min_spiral_ring);
    }
}