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 y in 0..self.height {
76            for x in 0..self.width {
77                let point = Point::new(x, y);
78                print!("{}", self[point] as char);
79            }
80            println!();
81        }
82        println!();
83    }
84}
85
86impl<T: Copy + PartialEq> Grid<T> {
87    #[must_use]
88    pub fn find(&self, needle: T) -> Option<Point> {
89        self.bytes
90            .iter()
91            .position(|&h| h == needle)
92            .map(|index| Point::new(index as i32 % self.width, index as i32 / self.width))
93    }
94}
95
96impl<T: Copy> Grid<T> {
97    #[must_use]
98    pub fn new(width: i32, height: i32, value: T) -> Self {
99        Self { width, height, bytes: vec![value; (width * height) as usize] }
100    }
101
102    #[must_use]
103    pub fn same_size_with<U: Copy>(&self, value: U) -> Grid<U> {
104        Grid::new(self.width, self.height, value)
105    }
106}
107
108impl<T> Grid<T> {
109    #[inline]
110    #[must_use]
111    pub fn contains(&self, point: Point) -> bool {
112        point.x >= 0 && point.x < self.width && point.y >= 0 && point.y < self.height
113    }
114}
115
116impl<T> Index<Point> for Grid<T> {
117    type Output = T;
118
119    #[inline]
120    fn index(&self, index: Point) -> &Self::Output {
121        &self.bytes[(self.width * index.y + index.x) as usize]
122    }
123}
124
125impl<T> IndexMut<Point> for Grid<T> {
126    #[inline]
127    fn index_mut(&mut self, index: Point) -> &mut Self::Output {
128        &mut self.bytes[(self.width * index.y + index.x) as usize]
129    }
130}
aoc/util/grid.rs

aoc/util/
grid.rs
