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.

Methods

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

pub fn new_default(dimensions: Vector, 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: Location,
    dimensions: Vector,
    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. Most cells in the grid have this 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.

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

pub fn new_rooted(root: Location, dimensions: Vector) -> Self

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

pub fn new(dimensions: Vector) -> 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: 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.

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> BaseGridBounds for SparseGrid<T>

fn dimensions(&self) -> Vector

Get the dimensions of the grid, as a [Vector].

fn root(&self) -> Location

Return the root location (ie, the top left) of the grid. For most grids, this is (0, 0), but some grids may include negatively indexed locations, or even offsets. All valid locations have location >= root.

impl<T: Clone + PartialEq> BaseGridSetter 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.

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

type Item = T

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.

impl<T: Clone + PartialEq> BaseGridMut 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.