grid_area/
lib.rs

1//! A library for manipulating 2d grids
2//!
3//! Grids are given as vecs of rows which are vecs of cells
4
5#![deny(clippy::all, clippy::pedantic)]
6#![allow(
7    clippy::enum_glob_use,
8    clippy::many_single_char_names,
9    clippy::must_use_candidate
10)]
11#![forbid(missing_docs)]
12
13/// A type of topology
14#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
15pub enum Topology {
16    /// A bounded grid, with no wrap-around
17    Bounded,
18
19    /// A grid that wraps around, preserving the axis not moved in. e.g. Pacman
20    Torus,
21}
22
23use Topology::*;
24
25/// One of the four cardinal directions
26#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
27pub enum Direction {
28    /// North.
29    North,
30
31    /// South.
32    South,
33
34    /// East.
35    East,
36
37    /// West.
38    West,
39}
40
41use Direction::*;
42
43/// Neighborhoods around a point. They do not contain the point itself
44#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
45pub enum Neighborhood {
46    /// The neighborhood consisting of the points directly North, South, East, and West of a point.
47    Orthogonal,
48
49    /// The neighborhood consisting of the points directly diagonal to a point.
50    Diagonal,
51
52    /// The neighborhood consisting of the square directly around the point.
53    Square,
54}
55
56use Neighborhood::*;
57
58/// Get the adjacent point to a point in a given direction
59pub fn adjacent_cell(
60    t: Topology,
61    width: usize,
62    height: usize,
63    x: usize,
64    y: usize,
65    d: Direction,
66) -> Option<(usize, usize)> {
67    match t {
68        Bounded => match d {
69            North => Some((x, y.checked_sub(1)?)),
70            South => {
71                if y + 1 < height {
72                    Some((x, y + 1))
73                } else {
74                    None
75                }
76            }
77            East => {
78                if x + 1 < width {
79                    Some((x + 1, y))
80                } else {
81                    None
82                }
83            }
84            West => Some((x.checked_sub(1)?, y)),
85        },
86        Torus => match d {
87            North => Some((x, y.checked_sub(1).unwrap_or(height - 1))),
88            South => Some((x, (y + 1) % height)),
89            East => Some(((x + 1) % width, y)),
90            West => Some((x.checked_sub(1).unwrap_or(width - 1), y)),
91        },
92    }
93}
94
95/// Is a given point on an edge of a grid
96pub fn is_edge(t: Topology, width: usize, height: usize, x: usize, y: usize) -> bool {
97    t == Bounded && (x == 0 || x + 1 == width || y == 0 || y + 1 == height)
98}
99
100/// Is a given point a corner of a grid
101pub fn is_corner(t: Topology, width: usize, height: usize, x: usize, y: usize) -> bool {
102    t == Bounded && (x == 0 || x + 1 == width) && (y == 0 || y + 1 == height)
103}
104
105/// Returns an iterator over the points of a grid
106pub fn points(width: usize, height: usize) -> impl Iterator<Item = (usize, usize)> {
107    (0..width).flat_map(move |x| (0..height).map(move |y| (x, y)))
108}
109
110/// Returns an iterator over the points in a neighborhood around a point
111pub fn neighborhood(
112    t: Topology,
113    width: usize,
114    height: usize,
115    x: usize,
116    y: usize,
117    n: Neighborhood,
118) -> impl Iterator<Item = (usize, usize)> {
119    match n {
120        Orthogonal => vec![
121            adjacent_cell(t, width, height, x, y, North),
122            adjacent_cell(t, width, height, x, y, South),
123            adjacent_cell(t, width, height, x, y, East),
124            adjacent_cell(t, width, height, x, y, West),
125        ],
126        Diagonal => {
127            let n = adjacent_cell(t, width, height, x, y, North);
128            let s = adjacent_cell(t, width, height, x, y, South);
129            vec![
130                n.and_then(|(x, y)| adjacent_cell(t, width, height, x, y, East)),
131                s.and_then(|(x, y)| adjacent_cell(t, width, height, x, y, East)),
132                n.and_then(|(x, y)| adjacent_cell(t, width, height, x, y, West)),
133                s.and_then(|(x, y)| adjacent_cell(t, width, height, x, y, West)),
134            ]
135        }
136        Square => {
137            let n = adjacent_cell(t, width, height, x, y, North);
138            let s = adjacent_cell(t, width, height, x, y, South);
139            vec![
140                adjacent_cell(t, width, height, x, y, North),
141                adjacent_cell(t, width, height, x, y, South),
142                adjacent_cell(t, width, height, x, y, East),
143                adjacent_cell(t, width, height, x, y, West),
144                n.and_then(|(x, y)| adjacent_cell(t, width, height, x, y, East)),
145                s.and_then(|(x, y)| adjacent_cell(t, width, height, x, y, East)),
146                n.and_then(|(x, y)| adjacent_cell(t, width, height, x, y, West)),
147                s.and_then(|(x, y)| adjacent_cell(t, width, height, x, y, West)),
148            ]
149        }
150    }
151    .into_iter()
152    .flatten()
153}
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158
159    #[test]
160    fn adjacent_bounded() {
161        assert_eq!(adjacent_cell(Bounded, 3, 3, 1, 0, North), None);
162        assert_eq!(adjacent_cell(Bounded, 3, 3, 1, 1, North), Some((1, 0)));
163
164        assert_eq!(adjacent_cell(Bounded, 3, 3, 2, 2, South), None);
165        assert_eq!(adjacent_cell(Bounded, 3, 3, 0, 0, South), Some((0, 1)));
166
167        assert_eq!(adjacent_cell(Bounded, 3, 3, 2, 2, East), None);
168        assert_eq!(adjacent_cell(Bounded, 3, 3, 1, 1, East), Some((2, 1)));
169
170        assert_eq!(adjacent_cell(Bounded, 3, 3, 0, 0, West), None);
171        assert_eq!(adjacent_cell(Bounded, 3, 3, 1, 1, West), Some((0, 1)));
172    }
173
174    #[test]
175    fn adjacent_torus() {
176        assert_eq!(adjacent_cell(Torus, 3, 3, 1, 0, North), Some((1, 2)));
177        assert_eq!(adjacent_cell(Torus, 3, 3, 1, 1, North), Some((1, 0)));
178
179        assert_eq!(adjacent_cell(Torus, 3, 3, 2, 2, South), Some((2, 0)));
180        assert_eq!(adjacent_cell(Torus, 3, 3, 0, 0, South), Some((0, 1)));
181
182        assert_eq!(adjacent_cell(Torus, 3, 3, 2, 2, East), Some((0, 2)));
183        assert_eq!(adjacent_cell(Torus, 3, 3, 1, 1, East), Some((2, 1)));
184
185        assert_eq!(adjacent_cell(Torus, 3, 3, 0, 0, West), Some((2, 0)));
186        assert_eq!(adjacent_cell(Torus, 3, 3, 1, 1, West), Some((0, 1)));
187    }
188
189    #[test]
190    fn edge() {
191        assert!(is_edge(Bounded, 3, 3, 1, 0));
192        assert!(is_edge(Bounded, 3, 3, 0, 1));
193        assert!(is_edge(Bounded, 3, 3, 1, 2));
194        assert!(is_edge(Bounded, 3, 3, 2, 1));
195
196        assert!(!is_edge(Bounded, 3, 3, 1, 1));
197
198        assert!(!is_edge(Torus, 3, 3, 2, 1));
199    }
200
201    #[test]
202    fn pts() {
203        assert_eq!(points(3, 3).count(), 9);
204    }
205
206    #[test]
207    fn neighborino() {
208        assert_eq!(
209            neighborhood(Torus, 5, 5, 0, 0, Square).collect::<Vec<(usize, usize)>>(),
210            [
211                (0, 4),
212                (0, 1),
213                (1, 0),
214                (4, 0),
215                (1, 4),
216                (1, 1),
217                (4, 4),
218                (4, 1)
219            ],
220        );
221        assert_eq!(
222            neighborhood(Bounded, 5, 5, 0, 0, Square).collect::<Vec<(usize, usize)>>(),
223            [(0, 1), (1, 0), (1, 1)],
224        );
225    }
226}
grid_area/lib.rs

grid_area/
lib.rs
