1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
//! A quick, cache-conscious, blocked 2D array.
//!
//! `block-grid` gives you a fixed-size 2D array with a blocked / tiled memory representation.
//! This has the sweet benefit of being much more cache-friendly if you're often accessing nearby
//! coordinates. It also offers a bunch of utility methods and block access. If you don't care
//! about tiled memory and just want any 2D-grid, see the
//! ["Using without Blocks"](#using-without-blocks-good-ol-row-major) section below.
//!
//! # Example
//!
//! The following example offers a tour of basic usage and some features.
//!
//! ```
//! use block_grid::{BlockGrid, CoordsIterator, U2};
//!
//! let data: Vec<_> = (0..(4 * 6)).collect();
//!
//! // Construct from row-major ordered data
//! let grid = BlockGrid::<usize, U2>::from_row_major(4, 6, &data)?;
//!
//! // The 2D grid looks like:
//! // +-----------------------+
//! // | 0 1 | 2 3 | 4 5 |
//! // | 6 7 | 8 9 | 10 11 |
//! // |-------+-------+-------|
//! // | 12 13 | 14 15 | 16 17 |
//! // | 18 19 | 20 21 | 22 23 |
//! // +-----------------------+
//!
//! // Indexing
//! assert_eq!(grid[(1, 3)], 9);
//!
//! // Access raw array
//! let first_five = &grid.raw()[..5];
//! assert_eq!(first_five, &[0, 1, 6, 7, 2]);
//!
//! // Iterate over blocks, and access the last
//! let block = grid.block_iter().last().unwrap();
//! assert_eq!(block[(0, 1)], 17);
//!
//! // Iterate in row-major order
//! for (i, &x) in grid.row_major_iter().enumerate() {
//! assert_eq!(x, i);
//! }
//!
//! // Iterate in memory order, with coordinates
//! for ((row, col), &x) in grid.each_iter().coords() {
//! assert_eq!(row * 6 + col, x);
//! }
//!
//! # Ok::<(), ()>(())
//! ```
//!
//! # Usage
//!
//! ## Types
//!
//! The primary type is [`BlockGrid<T, B>`], where `T` is the stored type and `B` is a generic
//! parameter that controls the block size (all the `U*` types below). A view of a 2D block,
//! which is stored as a contiguous piece of memory, is a [`Block`] or [`BlockMut`].
//!
//! ## Indexing
//!
//! Indexing is by a pair of 2D coordinates, [`Coords`], which is simply a tuple `(row, column`).
//! You can use `[(i, j)]` or one of the many functions. When indexing elements in a specific
//! [`Block`] or [`BlockMut`], the coordinates are relative, meaning it's the row and column
//! *within* that block.
//!
//! ### Element Coordinates vs. Block Coordinates
//!
//! Coordinates typically refer to the locations of specific elements, but they can *also* be used
//! to index entire blocks. When using [`BlockGrid::block_iter`] chained by a
//! [`.coords()`][coords] call, or the [`Block::coords`] method, the returned *block coordinates*
//! instead refer to the entire block. This means that `(i, j`) would refer to the `i`-th *row of
//! blocks* and then the `j`-th block in that row. If you want the coordinates of the first
//! (top-left) element in a block, use the [`Block::starts_at`] method instead.
//!
//! [coords]: CoordsIterator::coords
//!
//! ## Iterating
//!
//! There are multiple ways of iterating over a 2D array. If you simply want to visit each
//! element, use [`BlockGrid::each_iter`]. You can alternatively iterate in row-major order using
//! [`BlockGrid::row_major_iter`]. Instead of iterating over elements, you can also iterate over
//! entire blocks with [`BlockGrid::block_iter`]. For any of these, if you also need coordinates
//! while iterating, you can chain a [`.coords()`][coords] call. If you only need a 1D iteration
//! count, then there's always [`Iterator::enumerate`].
//!
//! [coords]: CoordsIterator::coords
//!
//! ## Using without Blocks (Good Ol' Row-Major)
//!
//! If you wanna test performance against an non-blocked memory representation, you need both, or
//! you just like the rest of the interface but don't care about the blocks, we got you. Just use
//! the [`U1`] block size or the handy [`Grid<T>`] alias. All the block related methods still exist
//! and are correct, but are just functionally useless.
//!
//! # Optional Features
//!
//! ## Serde
//!
//! To use the [`serde`][serde] framework, enable the optional `serde` [feature] in your
//! `Cargo.toml`. There is an important subtlety to its usage. Because the block size is generic
//! and compile-time, you have to know `B` when deserializing. You *could* write it decide based
//! on the input data, but I think it would lead to a bunch of extra code-gen, so I've left it
//! out. It does, however, verify that `B` is the same value as the one originally used to
//! serialize. If you always know the `B` value, then this shouldn't matter at all.
//!
//! [serde]: https://crates.io/crates/serde
//! [feature]: https://doc.rust-lang.org/cargo/reference/features.html
#![warn(missing_docs)]
#![warn(missing_debug_implementations)]
#![warn(rust_2018_idioms)]
#![no_std]
extern crate alloc;
#[cfg(test)]
#[macro_use]
extern crate std;
mod block_grid;
mod block_width;
pub mod iters;
#[cfg(test)]
mod tests;
pub use crate::block_grid::*;
pub use crate::block_width::*;
pub use crate::iters::CoordsIterator;
/// Type alias for a 2-tuple of indices, representing 2D coordinates.
pub type Coords = (usize, usize);
/// Type alias for a typical 2D grid with standard row-major memory.
pub type Grid<T> = BlockGrid<T, U1>;