[−][src]Crate ingrid

Dynamic two-dimensional array with its algorithms

This crate provides a self-contained complete set of features to work with grids, which is simply another term for two-dimensional arrays.

Unlike regular arrays (or vectors), a grid cannot guarantee contiguity of the memory from both rows and columns perspectives at the same time. Therefore, we cannot consistently work with slices (which strictly are for contiguous sequences) and benefits from their useful features. The solution is to emulate slices for rows and columns, and implement their functionalities whenever they make sense in order to work with an unified interface, free from the internal representation of the grid. Iterators are also implemented and adapted to iterate over the grids, their rows, columns and cells, just like one would expect to do it with regular arrays.

But this crate isn't limited to the emulation of slices for rows and columns. It attempts to provide a standard container and its common algorithms, with most importantly, a consistent interface following the STL conventions, that is generic and good enough for most use cases. It's documented from tail to head and has complete test coverage.

Quick preview

Before digging in and have a look at each concept separately, here is a snippet to get an idea of what it looks like to work with Ingrid.

use ingrid::{Coordinate, Size};
use ingrid::Grid;
use ingrid::GridIterator;
use ingrid::{coord, size}; // Macros to shorten the syntax

// Create a grid with enough allocated memory to contain 9 elements.
let mut grid = Grid::<char>::with_capacity(size!(3, 3));

// Resize the grid to be 2x2 and fill it with a default value.
grid.resize(size!(2, 3), '😞');

// Change the content of the grid with the direct accessors.
grid[coord!(0, 0)] = '😄'; // Top-left element (first element)
grid[coord!(1, 2)] = '😄'; // Bottom-right element (last element)

// Insert a column right in the middle.
grid.insert_column(1, vec!['😮', '😮', '😮']);

// Iterate over the elements of the last row
for (coordinate, emoticon) in grid.row(2).iterator().enumerate_coordinate() {
    println!("Emoticon at {:?} is {}", coordinate, emoticon);
}

From now, you can either jump right in the documentation, or read this short introduction.

Coordinates and sizes

Because the notion of "coordinate" and "size" are intrinsic to the grid, this crate defines two very simple structures, Coordinate and Size to deal with those kind of values.

let coordinate = Coordinate::new(0, 0); // The top-left corner of a grid.
// ... or ...
let coordinate = Coordinate::zero();

let size = Size::new(3, 3);

You will notice they're a little bit verbose, and this is why macros are there to have a shorter syntax.

let coordinate = coord!(0, 0);
let size = size!(0, 0);

It's worth nothing that their type is usize and isize because they're pointers to memory location and that they have the copy semantic enabled because memory usage is not a concern.

let coord = coord!(0, 0);
let copy_coord = coord; // It creates a copy.
println!("coord {:?}", coord); // The proof is the initial variable is still accessible.

Additionally, there is also the Offset structure to use when you resize a grid and want its content to be shifted by a given number of rows and columns.

let offset = Offset::new(-1, 1);
// ... or ...
let offset = offset!(-1, 1);

Grid and its elements

Grids are made of rows, columns and cells, which are widespread terms and need no explanation. However, this crate distinguishes cells and elements as the former is an intermediary construct to access the elements of the grid.

Just like vectors, the grid owns the elements but unlike vectors, they're indexed with coordinates.

let mut grid = Grid::with_size(size!(3, 3), 0);
grid[coord!(1, 1)] = 42;

A grid can be filled with a given value, resized and cleared out.

let mut grid = Grid::with_size(size!(3, 3), 0);

// Fill the grid with a given value, replacing (and dropping) all existing elements.
grid.fill(42);

// Resize the grid, and fill the new space with a given value.
grid.resize(size!(5, 5), 1);

// Clear the grid, removing all elements and setting the grid size to 0.
grid.clear();
assert_eq!(grid.size(), size!(0, 0));

Note that if the width or height of the grid is equal to 0, it's said to be an "empty" grid. Therefore, a grid with size (3, 0) is perfectly valid but will contain no element.

let mut grid = Grid::zero();
assert_eq!(grid.size(), size!(0, 0));

// The grid has a width, but because height is zero, it still holds no element.
grid.resize(size!(3, 0), 42);
assert_eq!(grid.size(), size!(3, 0));

// Now it's holding 3 elements.
grid.insert_row(0, vec![1, 2, 3]);
assert_eq!(grid.size(), size!(3, 1));

For more complex algorithm, using cells instead of directly accessing elements can be advantageous as they retain their coordinates and comes with an handy interface to do stuff like surveying the adjacent cells.

Capacity and reallocation

Just like vectors has the notion of capacity, this crate also offers you similar control over the allocated memory of grids that grows and shrinks.

The capacity of a grid is the amount of space allocated for any future elements that will be added. This is not to be confused with the size of a grid, which specifies the number of actual elements within the grid. If a grid's size exceeds its capacity, its capacity will automatically be increased, but its elements will have to be reallocated.

For example, a grid with capacity (10, 10) and size (0, 0) would be an empty grid with space for 100 more elements. Inserting rows and columns onto the grid will not change its capacity or cause reallocation to occur. However, if the grid's size is increased to (11, 10) or (10, 11), it will have to reallocate, which can be slow. For this reason, it is recommended to use Grid<T>::with_capacity() whenever possible to specify how big the grid is expected to get.

Rows and columns

Rows and columns are slice-like objects for the grid. They come in two versions, immutable and immutable and can be constructed from the grid itself.

let mut grid = Grid::from_rows(vec![vec![1, 0, 3],
                                    vec![0, 0, 0],
                                    vec![7, 0, 9]]);

// Fix the grid to be 1, 2, 3, 4, 5, 6, 7, 8, 9.
{
    let mut row = grid.row_mut(1);
    row[0] = 4;
    row[1] = 5;
    row[2] = 6;
}

{
    let mut column = grid.column_mut(1);
    column[0] = 2;
    column[2] = 8;
}

let row = grid.row(1);
assert_eq!(row.values(), vec![&4, &5, &6]);

let column = grid.column(1);
assert_eq!(column.values(), vec![&2, &5, &8]);

As shown per the example, you need a mutable version of the row or column if you want to make changes to it.

Set of iterators

You will legitimately be iterating grids in all sort of ways and iterators are there for that.

let grid = Grid::from_rows(vec![vec![1, 2],
                                vec![3, 4]]);

let mut iterator = grid.iterator();
assert_eq!(iterator.next(), Some(&1));
assert_eq!(iterator.next(), Some(&2));
assert_eq!(iterator.next(), Some(&3));
assert_eq!(iterator.next(), Some(&4));
assert_eq!(iterator.next(), None);

Below is a snippet showing how to iterate over specific rows and columns.

let mut grid = Grid::from_rows(vec![vec![1, 2],
                                    vec![3, 4]]);

let mut row_iterator = grid.row(0).iterator();
assert_eq!(row_iterator.next(), Some(&1));
assert_eq!(row_iterator.next(), Some(&2));
assert_eq!(row_iterator.next(), None);

let mut column_iterator = grid.column(1).iterator();
assert_eq!(column_iterator.next(), Some(&2));
assert_eq!(column_iterator.next(), Some(&4));
assert_eq!(column_iterator.next(), None);

The Enumerate iterator adaptor comes in handy to yield the index of a slice. However, the index of a grid is a coordinate, therefore, use the provided EnumerateCoordinate iterator adaptor to yield coordinate of the elements during your iterations.

for (coordinate, value) in grid.iterator().enumerate() {
    // Now you also have access to the coordinate of the elements; you don't
    // have to keep track of it yourself.
    println!("Value of element at {:?} is {}", coordinate, value);
}

The cell intermediary accessor

This part of the crate isn't implemented yet.

Macros

coord	A coordinate instantiation helper.
offset	An offset instantiation helper.
size	A size instantiation helper.

Structs

Cell	A cell intermediary accessor
Column	A view onto a column of a grid
ColumnMut	A mutable view onto a column of a grid
Coordinate	A two-dimensional coordinate
EnumerateCoordinate	An iterator that yields the current coordinate
Grid	A dynamic two-dimensional array
IteratorColumn	An iterator over a column
IteratorGrid	An iterator over a grid
IteratorRow	An iterator over a row
Offset	A two-dimensional offset
Row	A view onto a row of a grid
RowMut	A mutable view onto a row of a grid
Size	A two-dimensional size

Traits

GridIterator

An interface to implement grid iterators