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 dimenionsal set of
20//! ASCII characters, a common occurence in Advent of Code inputs. The [`same_size_with`] function
21//! creates a grid of the same size, that can be used for in BFS algorithms for tracking visited
22//! location or for tracking cost in Djikstra.
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    pub fn parse(input: &str) -> Self {
40        let raw: Vec<_> = input.lines().map(str::as_bytes).collect();
41        let width = raw[0].len() as i32;
42        let height = raw.len() as i32;
43        let mut bytes = Vec::with_capacity((width * height) as usize);
44        raw.iter().for_each(|slice| bytes.extend_from_slice(slice));
45        Grid { width, height, bytes }
46    }
47
48    pub fn print(&self) {
49        for y in 0..self.height {
50            for x in 0..self.width {
51                let point = Point::new(x, y);
52                print!("{}", self[point] as char);
53            }
54            println!();
55        }
56        println!();
57    }
58}
59
60impl<T: Copy + PartialEq> Grid<T> {
61    #[inline]
62    pub fn find(&self, needle: T) -> Option<Point> {
63        let to_point = |index| {
64            let x = (index as i32) % self.width;
65            let y = (index as i32) / self.width;
66            Point::new(x, y)
67        };
68        self.bytes.iter().position(|&h| h == needle).map(to_point)
69    }
70}
71
72impl<T: Copy> Grid<T> {
73    pub fn new(width: i32, height: i32, value: T) -> Grid<T> {
74        Grid { width, height, bytes: vec![value; (width * height) as usize] }
75    }
76}
77
78impl<T> Grid<T> {
79    #[inline]
80    pub fn same_size_with<U: Copy>(&self, value: U) -> Grid<U> {
81        Grid {
82            width: self.width,
83            height: self.height,
84            bytes: vec![value; (self.width * self.height) as usize],
85        }
86    }
87
88    #[inline]
89    pub fn contains(&self, point: Point) -> bool {
90        point.x >= 0 && point.x < self.width && point.y >= 0 && point.y < self.height
91    }
92}
93
94impl<T> Index<Point> for Grid<T> {
95    type Output = T;
96
97    #[inline]
98    fn index(&self, index: Point) -> &Self::Output {
99        &self.bytes[(self.width * index.y + index.x) as usize]
100    }
101}
102
103impl<T> IndexMut<Point> for Grid<T> {
104    #[inline]
105    fn index_mut(&mut self, index: Point) -> &mut Self::Output {
106        &mut self.bytes[(self.width * index.y + index.x) as usize]
107    }
108}
aoc/util/grid.rs

aoc/util/
grid.rs
