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//! A convenience [`parse`] method creates a `Grid` directly from a 2-dimensional set of
20//! ASCII characters, a common occurrence in Advent of Code inputs. The [`same_size_with`] function
21//! creates a grid of the same size that can be used in BFS algorithms for tracking visited
22//! locations or for tracking cost in Dijkstra.
23//!
24//! [`Point`]: crate::util::point
25//! [`parse`]: Grid::parse
26//! [`same_size_with`]: Grid::same_size_with
27use std::ops::{Index, IndexMut};
28
29use crate::util::point::*;
30
31#[derive(Clone, Eq, Hash, PartialEq)]
32pub struct Grid<T> {
33    pub width: i32,
34    pub height: i32,
35    pub bytes: Vec<T>,
36}
37
38impl Grid<u8> {
39    #[must_use]
40    pub fn parse(input: &str) -> Self {
41        let raw: Vec<_> = input.lines().map(str::as_bytes).collect();
42
43        let width = raw[0].len() as i32;
44        let height = raw.len() as i32;
45        let bytes = raw.concat();
46
47        Self { width, height, bytes }
48    }
49
50    pub fn print(&self) {
51        for y in 0..self.height {
52            for x in 0..self.width {
53                let point = Point::new(x, y);
54                print!("{}", self[point] as char);
55            }
56            println!();
57        }
58        println!();
59    }
60}
61
62impl<T: Copy + PartialEq> Grid<T> {
63    #[must_use]
64    pub fn find(&self, needle: T) -> Option<Point> {
65        self.bytes
66            .iter()
67            .position(|&h| h == needle)
68            .map(|index| Point::new(index as i32 % self.width, index as i32 / self.width))
69    }
70}
71
72impl<T: Copy> Grid<T> {
73    #[must_use]
74    pub fn new(width: i32, height: i32, value: T) -> Self {
75        Self { width, height, bytes: vec![value; (width * height) as usize] }
76    }
77
78    #[must_use]
79    pub fn same_size_with<U: Copy>(&self, value: U) -> Grid<U> {
80        Grid::new(self.width, self.height, value)
81    }
82}
83
84impl<T> Grid<T> {
85    #[inline]
86    #[must_use]
87    pub fn contains(&self, point: Point) -> bool {
88        point.x >= 0 && point.x < self.width && point.y >= 0 && point.y < self.height
89    }
90}
91
92impl<T> Index<Point> for Grid<T> {
93    type Output = T;
94
95    #[inline]
96    fn index(&self, index: Point) -> &Self::Output {
97        &self.bytes[(self.width * index.y + index.x) as usize]
98    }
99}
100
101impl<T> IndexMut<Point> for Grid<T> {
102    #[inline]
103    fn index_mut(&mut self, index: Point) -> &mut Self::Output {
104        &mut self.bytes[(self.width * index.y + index.x) as usize]
105    }
106}
aoc/util/grid.rs

aoc/util/
grid.rs
