Struct gridly_grids::SparseGrid

pub struct SparseGrid<T: Clone + PartialEq> { /* fields omitted */ }

A sparse grid, where most of the cells are some default grid.

Sparse grids are backed by a hash table and a default value, and all elements not present in the hash table are considered to be the default value. These are colloquially called "unoccupied cells", though from the point of view of the gridly interface, they are indistinguishable from other cells. When reading from the grid, references to unoccupied cells will (usually) be to the same stored default value.

Whenever possible, cells that are set to the default value (as determined by PartialEq) will be removed from the hash table. Conversely, getting a mutable reference to an unnocupied cell will insert a clone of the default at that location, which can then be mutated.

Note about interior mutability: When a user gets a reference to an unoccupied cell, the reference will (usually) be to the stored default value. This means that if the user mutates the cell somehow (for instance, with a RefCell), those changes will appear in all unoccupied cells.

This is a trivial implementation of a Sparse Grid, intended for simple use cases and as an example Grid implementation. More complex implementations are possible that track dirtied cells and clear them from the internal storage more aggressively.

Implementations

impl<T: Clone + PartialEq> SparseGrid<T>

pub fn new_default(dimensions: impl VectorLike, default: T) -> Self

Create a new SparseGrid with the given dimensions, rooted at (0, 0), filled with the given default value

pub fn new_rooted_default(
    root: impl LocationLike,
    dimensions: impl VectorLike,
    default: T
) -> Self

Create a new SparseGrid with the given dimensions and root location, filled with the default value

pub fn get_default(&self) -> &T

Get a reference to the default value.

pub fn clean(&mut self)

Remove all entries from the underlying hash table that compare equal to the default

pub fn clear(&mut self)

Remove all non-default entries from the grid

pub fn occuppied_entries(
    &self
) -> impl Iterator<Item = (&Location, &T)> + FusedIterator + Clone

Get an iterator over all of the occupied (non-default) entries in the grid, in an arbitrary order.

pub fn occuppied_entries_mut(
    &mut self
) -> impl Iterator<Item = (&Location, &mut T)> + FusedIterator

Get an iterator of mutable references to the occupied (non-default) entries in the grid, in an arbitrary order.

pub fn occuppied_entries_mut_cleaned(
    &mut self
) -> impl Iterator<Item = (&Location, &mut T)> + FusedIterator + ExactSizeIterator

Get an iterator of mutable references to the occupied (non-default) entries in the grid, in an arbitrary order.

The difference between this method and occuppied_entries_mut is that this one first cleans the underlying storage. This means there's a higher up-front cost, but has the benefit of providing an ExactSizeIterator.

pub fn insert(&mut self, location: impl LocationLike, value: T) -> T

Insert a value into this grid at an arbitrary location. If the location is outside the grid's bounds, the grid's bounds are updated to include this value. Returns the previous value.

Example

use gridly_grids::SparseGrid;
use gridly::prelude::*;

let mut grid: SparseGrid<isize> = SparseGrid::new((0, 0));

assert_eq!(grid.root(), (0, 0));
assert_eq!(grid.dimensions(), (0, 0));

grid.insert((-1, 0), 10);

assert_eq!(grid.root(), (-1, 0));
assert_eq!(grid.dimensions(), (1, 1));
assert_eq!(grid[(-1, 0)], 10);

grid.insert((0, 1), 5);

assert_eq!(grid.root(), (-1, 0));
assert_eq!(grid.dimensions(), (2, 2));
assert_eq!(grid[(0, 1)], 5);

grid.insert((1, 0), 4);

assert_eq!(grid.root(), (-1, 0));
assert_eq!(grid.dimensions(), (3, 2));
assert_eq!(grid[(1, 0)], 4);

grid.insert((0, -1), 3);

assert_eq!(grid.root(), (-1, -1));
assert_eq!(grid.dimensions(), (3, 3));
assert_eq!(grid[(0, -1)], 3);

impl<T: Clone + PartialEq + Default> SparseGrid<T>

pub fn new_rooted(root: impl LocationLike, dimensions: impl VectorLike) -> Self

Create a new SparseGrid with the given dimensions and root location, filled with the default value for T

pub fn new(dimensions: impl VectorLike) -> Self

Create a new SparseGrid with the given dimensions, rooted at (0, 0), filled with the default value for T

Trait Implementations

impl<T: Clone + PartialEq> Clone for SparseGrid<T>

fn clone(&self) -> SparseGrid<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Clone + PartialEq> Debug for SparseGrid<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Clone + PartialEq> Grid for SparseGrid<T>

type Item = T

The item type stored in the grid

unsafe fn get_unchecked(&self, loc: Location) -> &T

Get a reference to a value in the grid. If the location is not present in the hash table, return a reference to the grid's default value.

fn get(&self, location: impl LocationLike) -> Result<&Self::Item, BoundsError>

Get a reference to a cell in a grid. Returns an error if the location is out of bounds with the specific boundary violation.

fn view<T>(&self) -> View<'_, Self, T> where
    T: Component, 

Get a view of a grid, over its rows or columns. A view of a grid is similar to a slice, but instead of being a view over specific elements, it's a view over the rows and columns. See [View] for details.

fn rows(&self) -> View<'_, Self, Row>

Get a view of a grid's rows. See [View] for details.

fn columns(&self) -> View<'_, Self, Column>

Get a view of a grid's columns. See [View] for details.

unsafe fn single_view_unchecked<T>(&self, index: T) -> SingleView<'_, Self, T> where
    T: Component, 

Get a view of a single row or column in a grid, without bounds checking that row or column index.

unsafe fn row_unchecked(&self, row: Row) -> SingleView<'_, Self, Row>

Get a view of a single row in a grid, without bounds checking that row's index.

unsafe fn column_unchecked(
    &self,
    column: Column
) -> SingleView<'_, Self, Column>

Get a view of a single column in a grid, without bounds checking that column's index.

fn single_view<T>(
    &self,
    index: T
) -> Result<SingleView<'_, Self, T>, RangeError<T>> where
    T: Component, 

Get a view of a single row or column in a grid. Returns an error if the index of the row or column is out of bounds for the grid.

fn row(
    &self,
    row: impl Into<Row>
) -> Result<SingleView<'_, Self, Row>, RangeError<Row>>

Get a view of a single row in a grid. Returns an error if the index of the row is out of bounds for the grid.

fn column(
    &self,
    column: impl Into<Column>
) -> Result<SingleView<'_, Self, Column>, RangeError<Column>>

Get a view of a single column in a grid. Returns an error if the index of the column is out of bounds for the grid.

fn display_with<T, F>(&self, func: F) -> DisplayAdapter<&Self, F> where
    F: Fn(&Self::Item) -> T,
    T: Display, 

Make a grid Displayable, using a function that defines how each of its cells are printed. For each row, the adapter simply prints each cell in the row, followed by a newline.

impl<T: Clone + PartialEq> GridBounds for SparseGrid<T>

fn dimensions(&self) -> Vector

Get the dimensions of the grid, as a Vector. The dimensions of must be >= 0.

fn root(&self) -> Location

Return the root location (ie, the top left) of the grid. All valid locations on the grid have location >= root. For most grids, this can just be Location::zero

#[must_use]fn outer_bound(&self) -> Location

Get the outer bound of the grid; that is, the location for which all valid locations in the grid have row < outer.row && column < outer.column

#[must_use]fn num_rows(&self) -> Rows

Get the height of the grid in Rows.

#[must_use]fn num_columns(&self) -> Columns

Get the width of the grid, in Columns.

#[must_use]fn dimension<C>(&self) -> C where
    C: Component, 

Get the height or width of this grid.

#[must_use]fn root_row(&self) -> Row

Return the index of the topmost row of this grid. For most grids, this is 0, but some grids may include negatively indexed locations, or even offsets.

#[must_use]fn root_column(&self) -> Column

Return the index of the leftmost column of this grid. For most grids, this is 0, but some grids may include negatively indexed locations, or even offsets.

#[must_use]fn root_component<C>(&self) -> C where
    C: Component, 

Return the index of the leftmost column or topmost row of this grid.

#[must_use]fn row_range(&self) -> ComponentRange<Row>

Get a range iterator over all the Row indexes in this grid

#[must_use]fn column_range(&self) -> ComponentRange<Column>

Get a range iterator over all the Column indexes in this grid

#[must_use]fn range<C>(&self) -> ComponentRange<C> where
    C: Component, 

Get a range iterator over the row or column indexes

fn check_component<C>(&self, c: C) -> Result<C, RangeError<C>> where
    C: Component, 

Check that a Row or a Column is inside the bounds described by this grid. Returns the component if it's inside the bounds, or an error describing the violated boundary if not. This function is intended to help write more expressive code; ie, grid.check_component(Row(10)).and_then(|row| ...).

fn check_row(&self, row: impl Into<Row>) -> Result<Row, RangeError<Row>>

Check that a Row is inside the bounds described by this grid. Returns the component if it's inside the bounds, or an error describing the violated boundary if not. This function is intended to help write more expressive code; ie, grid.check_row(10).and_then(|row| ...).

fn check_column(
    &self,
    column: impl Into<Column>
) -> Result<Column, RangeError<Column>>

Check that a Column is inside the bounds described by this grid. Returns the component if it's inside the bounds, or an error describing the violated boundary if not. This function is intended to help write more expressive code; ie, grid.check_column(10).and_then(|row| ...).

#[must_use]fn component_in_bounds<C>(&self, c: C) -> bool where
    C: Component, 

Returns true if a Row or Column is inside the bounds described by this grid.

#[must_use]fn row_in_bounds(&self, row: impl Into<Row>) -> bool

Returns true if a Row is inside the bounds described by this grid.

#[must_use]fn column_in_bounds(&self, column: impl Into<Column>) -> bool

Returns true if a Column is inside the bounds described by this grid.

fn check_location(
    &self,
    location: impl LocationLike
) -> Result<Location, BoundsError>

Check that a location is inside the bounds of this grid.

#[must_use]fn location_in_bounds(&self, location: impl LocationLike) -> bool

Returns true if a locaton is inside the bounds of this grid.

impl<T: Clone + PartialEq> GridMut for SparseGrid<T>

unsafe fn get_unchecked_mut(&mut self, location: Location) -> &mut T

Get a mutable reference to a cell in the grid. If this cell is unoccupied, the default is cloned and inserted into the underlying hash table at this location.

fn get_mut(
    &mut self,
    location: impl LocationLike
) -> Result<&mut Self::Item, BoundsError>

Get a reference to a cell in a grid. Returns an error if the location is out of bounds with the specific boundary violation.

impl<T: Clone + PartialEq> GridSetter for SparseGrid<T>

unsafe fn replace_unchecked(
    &mut self,
    location: Location,
    value: Self::Item
) -> Self::Item

Set the value of a cell in the grid. If this value compares equal to the default, remove it from the underlying hash table. Return the previous value (which may be a clone of the default value if the cell was unoccupied)

unsafe fn set_unchecked(&mut self, location: Location, value: T)

Set the value of a cell in the grid. If this value compares equal to the default, remove it from the underlying hash table.

fn replace(
    &mut self,
    location: impl LocationLike,
    value: Self::Item
) -> Result<Self::Item, BoundsError>

Replace the value at the given location with value. Returns the previous value in the grid, or an error if the location was out of bounds.

fn set(
    &mut self,
    location: impl LocationLike,
    value: Self::Item
) -> Result<(), BoundsError>

Set the value at the given location in the grid. Returns an error if the location was out of bounds.

impl<T: Clone + PartialEq, L: LocationLike> Index<L> for SparseGrid<T>

type Output = T

The returned type after indexing.

fn index(&self, location: L) -> &T

Performs the indexing (container[index]) operation.

impl<T: Clone + PartialEq, L: LocationLike> IndexMut<L> for SparseGrid<T>

fn index_mut(&mut self, location: L) -> &mut T

Performs the mutable indexing (container[index]) operation.