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 crate::util::point::*;
28use std::ops::{Index, IndexMut};
29
30#[derive(Clone, PartialEq, Eq, Hash)]
31pub struct Grid<T> {
32    pub width: i32,
33    pub height: i32,
34    pub bytes: Vec<T>,
35}
36
37impl Grid<u8> {
38    #[inline]
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        Grid { 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    #[inline]
64    #[must_use]
65    pub fn find(&self, needle: T) -> Option<Point> {
66        self.bytes.iter().position(|&h| h == needle).map(|index| {
67            let index = index as i32;
68            Point::new(index % self.width, index / self.width)
69        })
70    }
71}
72
73impl<T: Copy> Grid<T> {
74    #[must_use]
75    pub fn new(width: i32, height: i32, value: T) -> Grid<T> {
76        Grid { width, height, bytes: vec![value; (width * height) as usize] }
77    }
78}
79
80impl<T> Grid<T> {
81    #[inline]
82    #[must_use]
83    pub fn same_size_with<U: Copy>(&self, value: U) -> Grid<U> {
84        Grid {
85            width: self.width,
86            height: self.height,
87            bytes: vec![value; (self.width * self.height) as usize],
88        }
89    }
90
91    #[inline]
92    #[must_use]
93    pub fn contains(&self, point: Point) -> bool {
94        point.x >= 0 && point.x < self.width && point.y >= 0 && point.y < self.height
95    }
96}
97
98impl<T> Index<Point> for Grid<T> {
99    type Output = T;
100
101    #[inline]
102    fn index(&self, index: Point) -> &Self::Output {
103        &self.bytes[(self.width * index.y + index.x) as usize]
104    }
105}
106
107impl<T> IndexMut<Point> for Grid<T> {
108    #[inline]
109    fn index_mut(&mut self, index: Point) -> &mut Self::Output {
110        &mut self.bytes[(self.width * index.y + index.x) as usize]
111    }
112}
aoc/util/grid.rs

aoc/util/
grid.rs
