mod index;
#[cfg(feature = "linalg")]
pub mod linalg;
pub(crate) mod utils;
pub use index::GridIndex;
use index::LinearIndexError;
use std::collections::HashMap;
use utils::*;
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
#[non_exhaustive]
pub struct Grid<T> {
pub(crate) width: usize,
pub(crate) height: usize,
data: Vec<T>,
}
impl<T> Grid<T> {
pub fn new(width: usize, height: usize, data: Vec<T>) -> Self {
if width * height != data.len() {
panic!(
"width * height was {}, but must be equal to data.len(), which was {}",
width * height,
data.len()
);
}
panic_if_width_xor_height_is_zero(width, height);
Self {
width,
height,
data,
}
}
pub fn width(&self) -> usize {
self.width
}
pub fn height(&self) -> usize {
self.height
}
pub fn subgrid(
self,
column_start: usize,
row_start: usize,
width: usize,
height: usize,
) -> Grid<T> {
panic_if_width_xor_height_is_zero(width, height);
panic_if_column_out_of_bounds(&self, column_start);
panic_if_row_out_of_bounds(&self, row_start);
let column_end = column_start + width;
let row_end = row_start + height;
let is_within_bounds = |idx: GridIndex| {
idx.column() >= column_start
&& idx.column() < column_end
&& idx.row() >= row_start
&& idx.row() < row_end
};
let indices = self.indices();
let mut data = self.data;
for idx in indices.rev() {
if !is_within_bounds(idx) {
let linear_idx = GridIndex::to_linear_idx_in(self.width, idx);
data.remove(linear_idx);
}
}
Grid::new(column_end - column_start, row_end - row_start, data)
}
pub fn dimensions(&self) -> (usize, usize) {
(self.width, self.height)
}
pub fn is_square(&self) -> bool {
!self.is_empty() && self.width == self.height
}
fn is_empty(&self) -> bool {
let ans = self.width == 0 || self.height == 0;
if ans {
debug_assert!(self.width == 0);
debug_assert!(self.height == 0);
}
ans
}
pub fn area(&self) -> usize {
self.width * self.height
}
pub fn get<I>(&self, idx: I) -> Option<&T>
where
GridIndex: From<I>,
{
let index: usize = self.linear_idx(GridIndex::from(idx)).ok()?;
Some(&self.data[index])
}
pub fn get_mut<I>(&mut self, idx: I) -> Option<&mut T>
where
GridIndex: From<I>,
{
let index: usize = self.linear_idx(GridIndex::from(idx)).ok()?;
Some(&mut self.data[index])
}
pub fn cell_iter(&self) -> impl DoubleEndedIterator<Item = &T> {
self.data.iter()
}
pub fn row_iter(&self, row: usize) -> impl DoubleEndedIterator<Item = &T> {
panic_if_row_out_of_bounds(self, row);
(0..self.width).map(move |column| &self[(column, row)])
}
pub fn column_iter(&self, column: usize) -> impl DoubleEndedIterator<Item = &T> {
panic_if_column_out_of_bounds(self, column);
(0..self.height).map(move |row| &self[(column, row)])
}
pub fn insert_row(&mut self, row: usize, row_contents: Vec<T>) {
panic_if_row_is_empty(&row_contents);
if self.is_empty() && row == 0 {
self.width = row_contents.len();
self.height = 1;
self.data = row_contents;
return;
}
panic_if_row_length_is_not_equal_to_width(self, row_contents.len());
if row > self.height {
panic!(
"row insertion index (is {}) should be <= height (is {})",
row, self.height
);
}
let start_idx = GridIndex::to_linear_idx_in(self.width, GridIndex::new(0, row));
for (elem, idx) in row_contents.into_iter().zip(start_idx..) {
self.data.insert(idx, elem);
}
self.height += 1;
}
pub fn replace_row(&mut self, row: usize, data: Vec<T>) -> Vec<T> {
panic_if_row_out_of_bounds(self, row);
panic_if_row_length_is_not_equal_to_width(self, data.len());
let mut old = Vec::with_capacity(self.width);
for (column, elem) in data.into_iter().enumerate() {
let old_value = self.replace_cell((column, row), elem);
old.push(old_value);
}
old
}
pub fn remove_row(&mut self, row: usize) -> Vec<T> {
panic_if_row_out_of_bounds(self, row);
let start_idx = self.linear_idx(GridIndex::new(0, row)).unwrap();
let r: Vec<T> = self.data.drain(start_idx..start_idx + self.width).collect();
self.height -= 1;
if self.height == 0 {
self.width = 0;
}
r
}
pub fn swap_rows(&mut self, row1: usize, row2: usize) {
panic_if_row_out_of_bounds(self, row1);
panic_if_row_out_of_bounds(self, row2);
if row1 != row2 {
for column in self.columns() {
let linear_idx1 = self.linear_idx(GridIndex::new(column, row1)).unwrap();
let linear_idx2 = self.linear_idx(GridIndex::new(column, row2)).unwrap();
self.data.swap(linear_idx1, linear_idx2);
}
}
}
pub fn insert_column(&mut self, column: usize, column_contents: Vec<T>) {
panic_if_column_is_empty(&column_contents);
if self.is_empty() && column == 0 {
self.height = column_contents.len();
self.width = 1;
self.data = column_contents;
return;
}
panic_if_column_length_is_not_equal_to_height(self, column_contents.len());
if column > self.width {
panic!(
"column insertion index (is {}) should be <= width (is {})",
column, self.width
);
}
let indices: Vec<usize> = (0..column_contents.len())
.map(|row| GridIndex::to_linear_idx_in(self.width + 1, GridIndex::new(column, row)))
.collect();
for (elem, idx) in column_contents.into_iter().zip(indices.into_iter()) {
self.data.insert(idx, elem);
}
self.width += 1;
}
pub fn replace_column(&mut self, column: usize, data: Vec<T>) -> Vec<T> {
panic_if_column_out_of_bounds(self, column);
panic_if_column_length_is_not_equal_to_height(self, data.len());
let mut old = Vec::with_capacity(self.height);
for (row, elem) in data.into_iter().enumerate() {
let old_value = self.replace_cell((column, row), elem);
old.push(old_value);
}
old
}
pub fn swap_columns(&mut self, column1: usize, column2: usize) {
panic_if_column_out_of_bounds(self, column1);
panic_if_column_out_of_bounds(self, column2);
if column1 != column2 {
for row in self.rows() {
let linear_idx1 = self.linear_idx(GridIndex::new(column1, row)).unwrap();
let linear_idx2 = self.linear_idx(GridIndex::new(column2, row)).unwrap();
self.data.swap(linear_idx1, linear_idx2);
}
}
}
pub fn remove_column(&mut self, column: usize) -> Vec<T> {
panic_if_column_out_of_bounds(self, column);
let indices: Vec<usize> = self
.rows()
.map(|row| self.linear_idx(GridIndex::new(column, row)).unwrap())
.collect();
let mut c = Vec::with_capacity(self.height);
for idx in indices.into_iter().rev() {
let elem = self.data.remove(idx);
c.insert(0, elem);
}
self.width -= 1;
if self.width == 0 {
self.height = 0;
}
c
}
pub fn swap_cells<I>(&mut self, a: I, b: I)
where
GridIndex: From<I>,
{
let a_idx = GridIndex::from(a);
let b_idx = GridIndex::from(b);
panic_if_index_out_of_bounds(self, a_idx);
panic_if_index_out_of_bounds(self, b_idx);
let a_linear = self.linear_idx(a_idx).unwrap();
let b_linear = self.linear_idx(b_idx).unwrap();
self.data.swap(a_linear, b_linear);
}
pub fn replace_cell<I>(&mut self, idx: I, elem: T) -> T
where
GridIndex: From<I>,
{
let idx = GridIndex::from(idx);
panic_if_index_out_of_bounds(self, idx);
let linear = self.linear_idx_unchecked(idx);
std::mem::replace(&mut self.data[linear], elem)
}
pub fn rotate_ccw(&mut self) {
if self.is_empty() {
return;
}
let mut target_index = HashMap::new();
let mut current_target = 0;
for column in self.columns().rev() {
for row in self.rows() {
let from = self.linear_idx(GridIndex::new(column, row)).unwrap();
target_index.insert(from, current_target);
current_target += 1;
}
}
self.transform(target_index);
std::mem::swap(&mut self.width, &mut self.height);
}
pub fn rotate_cw(&mut self) {
if self.is_empty() {
return;
}
let mut target_index = HashMap::new();
let mut current_target = 0;
for column in self.columns() {
for row in self.rows().rev() {
let from = self.linear_idx(GridIndex::new(column, row)).unwrap();
target_index.insert(from, current_target);
current_target += 1;
}
}
self.transform(target_index);
std::mem::swap(&mut self.width, &mut self.height);
}
pub fn flip_horizontally(&mut self) {
if self.is_empty() {
return;
}
let mut target_index = HashMap::new();
let mut current_target = 0;
for row in self.rows() {
for column in self.columns().rev() {
let from = self.linear_idx(GridIndex::new(column, row)).unwrap();
target_index.insert(from, current_target);
current_target += 1;
}
}
self.transform(target_index);
}
pub fn flip_vertically(&mut self) {
if self.is_empty() {
return;
}
let mut target_index = HashMap::new();
let mut current_target = 0;
for row in self.rows().rev() {
for column in self.columns() {
let from = self.linear_idx(GridIndex::new(column, row)).unwrap();
target_index.insert(from, current_target);
current_target += 1;
}
}
self.transform(target_index);
}
pub fn transpose(&mut self) {
if self.is_empty() {
return;
}
let mut target_index = HashMap::new();
let mut current_target = 0;
for column in self.columns() {
for row in self.rows() {
let idx = GridIndex::new(column, row);
let from = self.linear_idx(idx).unwrap();
target_index.insert(from, current_target);
current_target += 1;
}
}
self.transform(target_index);
std::mem::swap(&mut self.width, &mut self.height);
}
fn transform(&mut self, mut target_index: HashMap<usize, usize>) {
while !target_index.is_empty() {
let current = *target_index.keys().next().unwrap();
let mut target = target_index.remove(¤t).unwrap();
loop {
self.data.swap(current, target);
match target_index.remove(&target) {
Some(t) => target = t,
None => {
break;
}
}
}
}
}
fn linear_idx(&self, idx: GridIndex) -> Result<usize, LinearIndexError> {
if idx.row() >= self.height {
Err(LinearIndexError::RowTooHigh)
} else if idx.column() >= self.width {
Err(LinearIndexError::ColumnTooHigh)
} else {
Ok(GridIndex::to_linear_idx_in(self.width, idx))
}
}
fn linear_idx_unchecked(&self, idx: GridIndex) -> usize {
panic_if_index_out_of_bounds(self, idx);
GridIndex::to_linear_idx_in(self.width, idx)
}
pub fn rows(&self) -> impl DoubleEndedIterator<Item = usize> {
0..self.height
}
pub fn columns(&self) -> impl DoubleEndedIterator<Item = usize> {
0..self.width
}
fn indices(&self) -> impl DoubleEndedIterator<Item = GridIndex> {
let height = self.height;
let width = self.width;
(0..height).flat_map(move |row| (0..width).map(move |column| GridIndex::new(column, row)))
}
}
impl<T> Grid<T>
where
T: Default,
{
pub fn new_default(width: usize, height: usize) -> Grid<T> {
let data = (0..width * height).map(|_| T::default()).collect();
Self::new(width, height, data)
}
}
impl<T> Grid<T>
where
T: PartialEq,
{
pub fn contains(&self, value: &T) -> bool {
self.cell_iter().any(|element| element == value)
}
}
impl<T> IntoIterator for Grid<T> {
type Item = T;
type IntoIter = std::vec::IntoIter<Self::Item>;
fn into_iter(self) -> Self::IntoIter {
self.data.into_iter()
}
}
impl<T, I> std::ops::Index<I> for Grid<T>
where
GridIndex: From<I>,
{
type Output = T;
fn index(&self, index: I) -> &Self::Output {
let index: GridIndex = GridIndex::from(index);
let linear = self.linear_idx_unchecked(index);
&self.data[linear]
}
}
impl<T, I> std::ops::IndexMut<I> for Grid<T>
where
GridIndex: From<I>,
{
fn index_mut(&mut self, index: I) -> &mut Self::Output {
let index: GridIndex = GridIndex::from(index);
let linear = self.linear_idx_unchecked(index);
&mut self.data[linear]
}
}
impl<T> std::fmt::Display for Grid<T>
where
T: std::fmt::Display,
{
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
let output = if let Some(max_length) = self.cell_iter().map(|c| c.to_string().len()).max() {
let padded_string = |orig: &str| {
let mut padding: String = std::iter::repeat(" ")
.take(max_length - orig.len())
.collect();
padding.push_str(orig);
padding
};
self.rows()
.map(|r| {
self.columns()
.map(|c| padded_string(&self[(c, r)].to_string()))
.collect::<Vec<String>>()
.join(" ")
})
.collect::<Vec<String>>()
.join("\n")
} else {
"".to_string()
};
write!(f, "{}", output)
}
}
#[cfg(test)]
#[allow(unused)]
mod tests {
use super::*;
use std::fmt::{Debug, Display};
fn example_grid_u32() -> Grid<u32> {
let grid = Grid::new(10, 10, (1..=100).collect());
println!("Grid<u32>: ");
println!("{}", grid);
grid
}
fn small_example_grid() -> Grid<char> {
let grid = Grid::new(2, 3, "abcdef".chars().collect());
println!("Grid<char>: ");
println!("{}", grid);
grid
}
#[test]
fn index_test() {
let grid = example_grid_u32();
assert_eq!(grid.get((5, 2)).unwrap(), &26);
let mut counter = 0;
for row in 0..grid.height {
for col in 0..grid.width {
counter += 1;
assert_eq!(grid[(col, row)], counter);
}
}
let result = std::panic::catch_unwind(|| grid[(11, 11)]);
assert!(result.is_err());
}
#[test]
fn set_value_test() {
let mut grid = small_example_grid();
*grid.get_mut((0, 1)).unwrap() = 'x';
assert_grid_equal(&grid, &Grid::new(2, 3, "abxdef".chars().collect()));
grid[(0, 2)] = 'y';
assert_grid_equal(&grid, &Grid::new(2, 3, "abxdyf".chars().collect()));
}
#[test]
fn row_iter_test() {
let grid = example_grid_u32();
let actual_items_in_row: Vec<u32> = grid.row_iter(2).copied().collect();
assert_eq!(
actual_items_in_row,
vec![21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
);
let actual_items_in_row_rev: Vec<u32> = grid.row_iter(2).rev().copied().collect();
assert_eq!(
actual_items_in_row_rev,
vec![30, 29, 28, 27, 26, 25, 24, 23, 22, 21]
);
}
#[test]
fn col_iter_test() {
let grid = example_grid_u32();
let actual_items_in_col: Vec<u32> = grid.column_iter(2).copied().collect();
assert_eq!(
actual_items_in_col,
vec![3, 13, 23, 33, 43, 53, 63, 73, 83, 93]
);
}
#[test]
fn new_default_test() {
let grid: Grid<u32> = Grid::new_default(10, 1);
assert_eq!(grid.data, vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0,]);
}
#[test]
fn insert_row_in_middle_test() {
let mut grid = example_grid_u32();
let items_in_row_1: Vec<u32> = grid.row_iter(1).copied().collect();
assert_eq!(items_in_row_1, vec![11, 12, 13, 14, 15, 16, 17, 18, 19, 20]);
assert_eq!(grid.height, 10);
grid.insert_row(1, vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1]);
assert_eq!(grid.height, 11);
}
#[test]
fn insert_row_at_end_test() {
let mut grid = small_example_grid();
let new_row: Vec<char> = "xx".chars().collect();
grid.insert_row(3, new_row.clone());
let items_in_bottom_row: Vec<char> = grid.row_iter(3).copied().collect();
assert_eq!(items_in_bottom_row, new_row);
assert_grid_equal(
&grid,
&Grid::new(2, 4, "abcdefxx".chars().collect::<Vec<_>>()),
);
}
#[test]
fn remove_row_test() {
let mut grid = small_example_grid();
let items_in_row_1: Vec<char> = grid.row_iter(1).cloned().collect();
assert_eq!(items_in_row_1, vec!['c', 'd']);
assert_eq!(grid.height, 3);
let removed_row = grid.remove_row(1);
assert_eq!(removed_row, items_in_row_1);
assert_eq!(grid.height, 2);
}
#[test]
fn remove_row_until_empty_test() {
let mut grid = small_example_grid();
grid.remove_row(0);
grid.remove_row(0);
grid.remove_row(0);
assert_grid_equal(&grid, &Grid::new(0, 0, Vec::new()));
assert_eq!(grid.height, 0);
assert_eq!(grid.width, 0);
assert!(grid.is_empty());
grid.insert_row(0, vec!['a', 'b', 'c']);
assert_grid_equal(&grid, &Grid::new(3, 1, vec!['a', 'b', 'c']));
}
#[test]
fn insert_column_in_middle_test() {
let mut grid = small_example_grid();
let items_in_column_1: Vec<char> = grid.column_iter(1).copied().collect();
assert_eq!(items_in_column_1, "bdf".chars().collect::<Vec<_>>());
assert_eq!(grid.width, 2);
grid.insert_column(1, "xxx".chars().collect());
let items_in_column_1: Vec<char> = grid.column_iter(1).copied().collect();
assert_eq!(items_in_column_1, "xxx".chars().collect::<Vec<_>>());
assert_eq!(grid.width, 3);
}
#[test]
fn insert_column_at_end_test() {
let mut grid = small_example_grid();
let new_column: Vec<char> = "xxx".chars().collect();
grid.insert_column(2, new_column.clone());
let items_in_column_2: Vec<char> = grid.column_iter(2).copied().collect();
assert_eq!(items_in_column_2, new_column);
assert_grid_equal(
&grid,
&Grid::new(3, 3, "abxcdxefx".chars().collect::<Vec<_>>()),
);
}
#[test]
fn remove_column_test() {
let mut grid = small_example_grid();
let items_in_column_1: Vec<_> = grid.column_iter(1).cloned().collect();
assert_eq!(items_in_column_1, vec!['b', 'd', 'f']);
assert_eq!(grid.width, 2);
let removed = grid.remove_column(1);
assert_eq!(removed, items_in_column_1);
assert_eq!(grid.width, 1);
}
#[test]
fn remove_column_until_empty_test() {
let mut grid = small_example_grid();
grid.remove_column(0);
grid.remove_column(0);
assert_grid_equal(&grid, &Grid::new(0, 0, Vec::new()));
assert_eq!(grid.height, 0);
assert_eq!(grid.width, 0);
assert!(grid.is_empty());
grid.insert_column(0, vec!['a', 'b', 'c']);
assert_grid_equal(&grid, &Grid::new(1, 3, vec!['a', 'b', 'c']));
}
#[test]
fn rotate_cw_test() {
let mut grid = small_example_grid();
grid.rotate_cw();
assert_grid_equal(&grid, &Grid::new(3, 2, vec!['e', 'c', 'a', 'f', 'd', 'b']));
}
#[test]
fn rotate_ccw_test() {
let mut grid = small_example_grid();
grid.rotate_ccw();
assert_grid_equal(&grid, &Grid::new(3, 2, vec!['b', 'd', 'f', 'a', 'c', 'e']));
}
#[test]
fn flip_horizontally_test() {
let mut grid = small_example_grid();
grid.flip_horizontally();
assert_grid_equal(&grid, &Grid::new(2, 3, vec!['b', 'a', 'd', 'c', 'f', 'e']));
}
#[test]
fn flip_vertically_test() {
let mut grid = small_example_grid();
grid.flip_vertically();
assert_grid_equal(&grid, &Grid::new(2, 3, vec!['e', 'f', 'c', 'd', 'a', 'b']));
}
#[test]
fn transpose_test() {
let original_grid = small_example_grid();
let mut grid = original_grid.clone();
grid.transpose();
assert_grid_equal(&grid, &Grid::new(3, 2, "acebdf".chars().collect()));
grid.transpose();
assert_grid_equal(&grid, &original_grid);
}
#[test]
fn contains_test() {
let grid = small_example_grid();
assert!(grid.contains(&'a'));
assert!(!grid.contains(&'g'));
}
#[test]
fn is_empty_test() {
let mut grid = small_example_grid();
assert!(!grid.is_empty());
grid.remove_row(0);
assert!(!grid.is_empty());
grid.remove_row(0);
assert!(!grid.is_empty());
grid.remove_row(0);
assert!(grid.is_empty());
grid.insert_row(0, vec!['g', 'h', 'i', 'j', 'k']);
assert!(!grid.is_empty());
assert_eq!(grid.width, 5);
}
#[test]
fn replace_row_test() {
let mut grid = small_example_grid();
let items_in_row_1: Vec<char> = grid.row_iter(1).copied().collect();
let old_row = grid.replace_row(1, vec!['x', 'x']);
assert_eq!(old_row, items_in_row_1);
assert_grid_equal(&grid, &Grid::new(2, 3, "abxxef".chars().collect()));
}
#[test]
fn replace_column_test() {
let mut grid = small_example_grid();
let items_in_column_0: Vec<char> = grid.column_iter(0).copied().collect();
let old_column = grid.replace_column(0, vec!['x', 'x', 'x']);
assert_eq!(old_column, items_in_column_0);
assert_grid_equal(&grid, &Grid::new(2, 3, "xbxdxf".chars().collect()));
}
#[test]
fn swap_columns_test() {
let mut grid = small_example_grid();
grid.swap_columns(0, 1);
assert_grid_equal(&grid, &Grid::new(2, 3, "badcfe".chars().collect()));
}
#[test]
fn swap_rows_test() {
let mut grid = small_example_grid();
grid.swap_rows(1, 2);
assert_grid_equal(&grid, &Grid::new(2, 3, "abefcd".chars().collect()));
}
#[test]
fn swap_cells_test() {
let mut grid = small_example_grid();
grid.swap_cells((1, 1), (0, 2));
assert_grid_equal(&grid, &Grid::new(2, 3, "abcedf".chars().collect()));
}
#[test]
fn subgrid_test() {
let grid = example_grid_u32();
let subgrid = grid.subgrid(2, 1, 3, 5);
assert_grid_equal(
&subgrid,
&Grid::new(
3,
5,
vec![13, 14, 15, 23, 24, 25, 33, 34, 35, 43, 44, 45, 53, 54, 55],
),
);
}
#[test]
fn replace_cell_test() {
let mut grid = small_example_grid();
let old_value = grid.replace_cell((0, 1), 'x');
assert_eq!(old_value, 'c');
assert_grid_equal(&grid, &Grid::new(2, 3, "abxdef".chars().collect()));
}
#[test]
#[cfg(feature = "serde")]
fn serialize_test() {
let mut grid = small_example_grid();
let json = serde_json::to_string(&grid).unwrap();
println!("{}", json);
}
fn assert_grid_equal<T>(actual: &Grid<T>, expected: &Grid<T>)
where
T: Display + PartialEq + Debug,
{
println!("actual:");
println!("{}", actual);
println!("expected:");
println!("{}", expected);
assert_eq!(actual, expected);
}
}