aoc/util/
grid.rs

1//! Fast 2-dimensional Grid backed by a single `vec`, designed to work with [`Point`].
2//!
3//! The traits [`Index`] and [`IndexMut`] are implemented for [`Point`] to allow usage like:
4//!
5//! ```
6//! # use aoc::util::grid::Grid;
7//! # use aoc::util::point::Point;
8//!
9//! let mut grid = Grid::parse("1");
10//! let point = Point::new(0, 0);
11//!
12//! let foo = grid[point];
13//! assert_eq!(foo, b'1');
14//!
15//! grid[point] = foo + 1;
16//! assert_eq!(grid[point], b'2');
17//! ```
18//!
19//! Two convenience methods, [`parse`] and [`parse_with_border`], create a `Grid` directly from a
20//! 2-dimensional set of ASCII characters, a common occurrence in Advent of Code inputs. The former
21//! strips all newlines, and [`contains`] is then useful to prevent accidental wraparound between
22//! lines. The latter not only preserves newlines in the input, but adds a row of newlines above and
23//! below, for algorithms where newline serves as a natural barrier without needing to use
24//! [`contains`]. The [`same_size_with`] function creates a grid of the same size that can be used
25//! in BFS algorithms for tracking visited locations or for tracking cost in Dijkstra.
26//!
27//! [`Point`]: crate::util::point
28//! [`parse`]: Grid::parse
29//! [`parse_with_border`]: Grid::parse_with_border
30//! [`contains`]: Grid::contains
31//! [`same_size_with`]: Grid::same_size_with
32use std::ops::{Index, IndexMut};
33
34use crate::util::point::*;
35
36#[derive(Clone, Eq, Hash, PartialEq)]
37pub struct Grid<T> {
38    pub width: i32,
39    pub height: i32,
40    pub bytes: Vec<T>,
41}
42
43impl Grid<u8> {
44    #[must_use]
45    pub fn parse(input: &str) -> Self {
46        let raw: Vec<_> = input.lines().map(str::as_bytes).collect();
47
48        let width = raw[0].len() as i32;
49        let height = raw.len() as i32;
50        let bytes = raw.concat();
51
52        Self { width, height, bytes }
53    }
54
55    #[must_use]
56    pub fn parse_with_border(input: &str) -> Self {
57        // Size things large enough so that both orthogonal and diagonal access hits a newline.
58        // This shifts 0,0 to 1,1. Non-newline iteration would be `1..height-1` and `1..width`,
59        // although it still often faster to iterate `0..height` and `0..width` when visiting
60        // newline is harmless. For convenience, the allocation is oversized to compensate for unit
61        // tests that omit a trailing newline.
62        let width = input.lines().next().unwrap().len() + 1;
63        let height = input.len().div_ceil(width) + 2;
64        let size = width * height + 1;
65        let mut bytes = Vec::with_capacity(size);
66
67        bytes.resize(width + 1, b'\n');
68        bytes.extend_from_slice(input.as_bytes());
69        bytes.resize(size, b'\n');
70
71        Self { width: width as i32, height: height as i32, bytes }
72    }
73
74    pub fn print(&self) {
75        for row in self.bytes.chunks(self.width as usize) {
76            println!("{}", str::from_utf8(row).unwrap());
77        }
78    }
79}
80
81impl<T: Copy + PartialEq> Grid<T> {
82    #[must_use]
83    pub fn find(&self, needle: T) -> Option<Point> {
84        self.bytes
85            .iter()
86            .position(|&h| h == needle)
87            .map(|index| Point::new(index as i32 % self.width, index as i32 / self.width))
88    }
89}
90
91impl<T: Copy> Grid<T> {
92    #[must_use]
93    pub fn new(width: i32, height: i32, value: T) -> Self {
94        Self { width, height, bytes: vec![value; (width * height) as usize] }
95    }
96
97    #[must_use]
98    pub fn same_size_with<U: Copy>(&self, value: U) -> Grid<U> {
99        Grid::new(self.width, self.height, value)
100    }
101}
102
103impl<T> Grid<T> {
104    #[inline]
105    #[must_use]
106    pub fn contains(&self, point: Point) -> bool {
107        point.x >= 0 && point.x < self.width && point.y >= 0 && point.y < self.height
108    }
109}
110
111impl<T> Index<Point> for Grid<T> {
112    type Output = T;
113
114    #[inline]
115    fn index(&self, index: Point) -> &Self::Output {
116        &self.bytes[(self.width * index.y + index.x) as usize]
117    }
118}
119
120impl<T> IndexMut<Point> for Grid<T> {
121    #[inline]
122    fn index_mut(&mut self, index: Point) -> &mut Self::Output {
123        &mut self.bytes[(self.width * index.y + index.x) as usize]
124    }
125}
aoc/util/grid.rs

aoc/util/
grid.rs
