aoc/util/
grid.rs

1//! Fast 2-dimensional Grid backed by a single `vec`. This module is 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 x = (index as i32) % self.width;
68            let y = (index as i32) / self.width;
69            Point::new(x, y)
70        })
71    }
72}
73
74impl<T: Copy> Grid<T> {
75    #[must_use]
76    pub fn new(width: i32, height: i32, value: T) -> Grid<T> {
77        Grid { width, height, bytes: vec![value; (width * height) as usize] }
78    }
79}
80
81impl<T> Grid<T> {
82    #[inline]
83    #[must_use]
84    pub fn same_size_with<U: Copy>(&self, value: U) -> Grid<U> {
85        Grid {
86            width: self.width,
87            height: self.height,
88            bytes: vec![value; (self.width * self.height) as usize],
89        }
90    }
91
92    #[inline]
93    #[must_use]
94    pub fn contains(&self, point: Point) -> bool {
95        point.x >= 0 && point.x < self.width && point.y >= 0 && point.y < self.height
96    }
97}
98
99impl<T> Index<Point> for Grid<T> {
100    type Output = T;
101
102    #[inline]
103    fn index(&self, index: Point) -> &Self::Output {
104        &self.bytes[(self.width * index.y + index.x) as usize]
105    }
106}
107
108impl<T> IndexMut<Point> for Grid<T> {
109    #[inline]
110    fn index_mut(&mut self, index: Point) -> &mut Self::Output {
111        &mut self.bytes[(self.width * index.y + index.x) as usize]
112    }
113}
aoc/util/grid.rs

aoc/util/
grid.rs
