Crate flatk

Expand description

Flat layout abstraction toolkit.

This library defines low level primitives for organizing flat ordered data collections (like Vecs and slices) into meaningful structures without cloning the data.

More specifically, flatk provides a few core composable types intended for building more complex data structures out of existing data:

UniChunked: Subdivides a collection into a number of uniformly sized (at compile time or run-time) contiguous chunks. For example if we have a Vec of floats representing 3D positions, we may wish to interpret them as triplets:

use flatk::Chunked3;

let pos_data = vec![0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 1.0, 0.0];

let pos = Chunked3::from_flat(pos_data);

assert_eq!(pos[0], [0.0; 3]);
assert_eq!(pos[1], [1.0; 3]);
assert_eq!(pos[2], [0.0, 1.0, 0.0]);

For dynamically determined chunks sizes, the type alias ChunkedN can be used instead. The previous example can then be reproduced as:

use flatk::ChunkedN;

let pos_data = vec![0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 0.0, 1.0, 0.0];

let pos = ChunkedN::from_flat_with_stride(3, pos_data);

assert_eq!(pos[0], [0.0; 3]);
assert_eq!(pos[1], [1.0; 3]);
assert_eq!(pos[2], [0.0, 1.0, 0.0]);

Chunked: Subdivides a collection into a number of unstructured (non-uniformly sized) chunks. For example we may have a non-uniform grouping of nodes stored in a Vec, which can represent a directed graph:

use flatk::Chunked;
 
let neighbours = vec![1, 2, 0, 1, 0, 1, 2];
 
let neigh = Chunked::from_sizes(vec![1,2,1,3], neighbours);

assert_eq!(&neigh[0][..], &[1][..]);
assert_eq!(&neigh[1][..], &[2, 0][..]);
assert_eq!(&neigh[2][..], &[1][..]);
assert_eq!(&neigh[3][..], &[0, 1, 2][..]);

Here neigh defines the following graph:

0<--->1<--->2
^     ^     ^
 \    |    /
  \   |   /
   \  |  /
    \ | /
     \|/
      3

Clumped: A hybrid between UniChunked and Chunked, this type aggregates references to uniformly spaced chunks where possible. This makes it preferable for collections with mostly uniformly spaced chunks.

For example, polygons can be represented as indices into some global vertex array. Polygonal meshes are often made from a combination of triangles and quadrilaterals, so we can’t represent the vertex indices as a UniChunked vector, and it would be too wastefull to keep track of each chunk using a plain Chunked vector. Clumped, however, is perfect for this use case since it only stores an additional pair of offsets (usize integers) for each type of polygon. In code this may look like the following:

use flatk::{Clumped, Get, View};
 
// Indices into some vertex array (depicted below): 6 triangles followed by 2 quadrilaterals.
let indices = vec![0,1,2, 2,1,3, 7,1,0, 3,5,10, 9,8,7, 4,6,5, 7,8,4,1, 1,4,5,3];
 
let polys = Clumped::from_sizes_and_counts(vec![3,4], vec![6,2], indices);
let polys_view = polys.view();

assert_eq!(&polys_view.at(0)[..], &[0,1,2][..]);
assert_eq!(&polys_view.at(1)[..], &[2,1,3][..]);
assert_eq!(&polys_view.at(2)[..], &[7,1,0][..]);
assert_eq!(&polys_view.at(3)[..], &[3,5,10][..]);
assert_eq!(&polys_view.at(4)[..], &[9,8,7][..]);
assert_eq!(&polys_view.at(5)[..], &[4,6,5][..]);
assert_eq!(&polys_view.at(6)[..], &[7,8,4,1][..]);
assert_eq!(&polys_view.at(7)[..], &[1,4,5,3][..]);

These polygons could represent a mesh like below, where each number corresponds to a vertex index.

0 ---- 2 ---- 3 --10
|\     |     / \  |
| \    |    /   \ |
|  \   |   /     \|
|   \  |  /       5
|    \ | /       /|
|     \|/       / |
7 ---- 1       /  |
|\      \     /   |
| \      \   /    |
|  \      \ /     |
9 - 8 ---- 4 ---- 6

Select: An ordered selection (with replacement) of elements from a given random access collection. This is usually realized with a Vec<usize> representing indices into the original data collection.

For example one may wish to select game pieces in a board game:

use flatk::Select;
 
let pieces = vec!["Pawn", "Knight", "Bishop", "Rook", "Queen", "King"];
 
let white_pieces = Select::new(vec![3, 1, 2, 5, 4, 2, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0], pieces.as_slice());
let black_pieces = Select::new(vec![0, 0, 0, 0, 0, 0, 0, 0, 3, 1, 2, 5, 4, 2, 1, 3], pieces.as_slice());

assert_eq!(white_pieces[0], "Rook");
assert_eq!(white_pieces[4], "Queen");
assert_eq!(black_pieces[0], "Pawn");
assert_eq!(black_pieces[11], "King");

Subset: Similar to Select but Subset enforces an unordered selection without replacement.

For example we can choose a hand from a deck of cards:

use flatk::{Subset, Get, View};

let rank = vec!["Ace", "2", "3", "4", "5", "6", "7", "8", "9", "10", "Jack", "Queen", "King"];
let suit = vec!["Clubs", "Diamonds", "Hearts", "Spades"];

// Natural handling of structure of arrays (SoA) style data.
let deck: (Vec<_>, Vec<_>) = (
    rank.into_iter().cycle().take(52).collect(),
    suit.into_iter().cycle().take(52).collect()
);

let hand = Subset::from_indices(vec![4, 19, 23, 1, 0, 5], deck);
let hand_view = hand.view();
assert_eq!(hand_view.at(0), (&"Ace", &"Clubs"));
assert_eq!(hand_view.at(1), (&"2", &"Diamonds"));
assert_eq!(hand_view.at(2), (&"5", &"Clubs"));
assert_eq!(hand_view.at(3), (&"6", &"Diamonds"));
assert_eq!(hand_view.at(4), (&"7", &"Spades"));
assert_eq!(hand_view.at(5), (&"Jack", &"Spades"));

Sparse: A sparse data assignment to another collection. Effectively this type attaches another data set to a Selection. See Sparse for examples.

§Indexing

Due to the nature of type composition and the indexing mechanism in Rust, it is not always possible to use the Index and IndexMut traits for indexing into the flatk collection types. To facilitate indexing, flatk defines two traits for indexing: Get and Isolate, which fill the roles of Index and IndexMut respectively. These traits work mainly on viewed collections (what is returned by calling .view() and .view_mut()). Isolate can also work with collections that own their data, however it is not recommended since methods provided by Isolate are destructive (they consume self).

Modules§

consts: Type aliases for many constants.

Macros§

U: A simple macro constructing U# types given an expression.
zip: Zip multiple iterators.

Structs§

Chunked: A partitioning of the collection S into distinct chunks.
ChunkedIter: A special iterator capable of iterating over a Chunked type.
ChunkedNIter
Chunks: A generic version of the Chunks iterator used by slices. This is used by uniformly (but not statically) chunked collections.
ClumpedOffsets: A collection of clumped offsets into another collection.
OffsetValueRanges: Iterator over ranges of offset values.
OffsetValues: An iterator over offset values.
OffsetValuesAndSizes
Offsets: A collection of offsets into another collection. This newtype is intended to verify basic invariants about offsets into another collection, namely that the collection is monotonically increasing and non-empty.
OffsetsAndSizes
Ranges: Iterator over ranges of offsets.
Select: A Set that is a non-contiguous, unordered and possibly duplicated selection of some larger collection. S can be any borrowed collection type that implements Set. Note that it doesn’t make much sense to have a Select type own the data that it selects from, although it’s possible to create one.
Sizes
Sparse: A Sparse data set S where the sparsity pattern is given by I as select indices into a larger range.
SparseIter
StaticRange: A type of range whose size is determined at compile time. This represents a range [start..start + N::value()]. This aids UniChunked types when indexing.
StructIter: A wraper for a zip iterator that unwraps its contents into a custom struct.
Subset: A Set that is a non-contiguous subset of some larger collection. B can be any borrowed collection type that implements the Set, and RemovePrefix traits. For iteration of subsets, the underlying type must also implement SplitFirst and SplitAt traits.
SubsetIter
U: Wrapper around typenum types to prevent downstream trait implementations.
UnclumpedOffsetValues
UnclumpedOffsetValuesAndSizes: Iterator over offset value and size pairs representing unclumped chunks.
UnclumpedOffsetsAndSizes: Iterator over offsets and size pairs representing unclumped chunks.
UnclumpedSizes: Iterator over unclumped chunk sizes.
UniChunked: UniChunked Assigns a stride N to the specified collection.
UniChunkedIter: Generic static sized chunk iterater appropriate for any lightweight view type collection.
VarIntoIter: IntoIter for Chunked.

Enums§

SubsetIndexIter

Traits§

Array
AsFlatSlice
AsIndexSlice: A wrapper trait for sequences of immutable indices.
AsIndexSliceMut: A wrapper trait for sequences of mutable indices.
AtomIterator
AtomMutIterator
BinarySearch
BoundedRange: A definition of a bounded range.
ChunkSize: This trait is used to produce the chunk size of a collection if it contains uniformly chunked elements.
Clear
CloneIntoOther: Clone self into a potentially different collection.
CloneWithStorage: Clone the structure of a set replacing its storage with a new one.
Dimension
Dummy: A helper trait for constructing placeholder sets for use in std::mem::replace.
DynamicRangeIndexType: A marker trait to identify types whose range indices give a dynamically sized type even if the range index is given as a StaticRange.
ExtendFromSlice
Get: An index trait for collection types. Here 'i indicates the lifetime of the input while 'o indicates that of the output.
GetIndex: A helper trait analogous to SliceIndex from the standard library.
GetOffset: Manipulate a non-empty collection of offsets.
IndexRange
IntBound: A helper trait to identify valid types for Range bounds for use as Sets.
IntoChunkIterator: This trait generalizes the method chunks available on slices in the standard library. Collections that can be chunked by a runtime stride should implement this behaviour such that they can be composed with ChunkedN types.
IntoOffsetValuesAndSizes
IntoOwned: An analog to the ToOwned trait from std that works for chunked views. As the name suggests, this version of ToOwned takes self by value.
IntoOwnedData: In contrast to IntoOwned, this trait produces a clone with owned data, but potentially borrowed structure of the collection.
IntoParChunkIterator: Parallel version of IntoChunkIterator.
IntoParOffsetValuesAndSizes
IntoRanges
IntoSizes
IntoStaticChunkIterator: Iterate over chunks whose size is determined at compile time.
IntoStorage: Convert a collection into its underlying representation, effectively stripping any organizational info.
IntoValues
IntoView
Isolate: Since we cannot alias mutable references, in order to index a mutable view of elements, we must consume the original mutable reference. Since we can’t use slices for general composable collections, its impossible to match against a &mut self in the getter function to be able to use it with owned collections, so we opt to have an interface that is designed specifically for mutably borrowed collections. For composable collections, this is better described by a subview operator, which is precisely what this trait represents. Incidentally this can also work for owned collections, which is why it’s called Isolate instead of SubView.
IsolateIndex: A helper trait like GetIndex but for Isolate types.
MapStorage: Map the storage type into another given a conversion function.
OwnedSet
PermuteInPlace
Push: Abstraction for pushing elements of type T onto a collection.
PushArrayTo
PushArrayToVec
PushChunk
ReadSet
ReinterpretAsGrouped
RemovePrefix: A helper trait used to help implement the Subset. This trait allows abstract collections to remove a number of elements from the beginning, which is what we need for subsets.
Reserve: A trait that allows the container to allocate additional space without changing any of the data. The container should allocate space for at least n additional elements.
Set: A trait defining a raw buffer of data. This data is typed but not annotated so it can represent anything. For example a buffer of floats can represent a set of vertex colours or vertex positions.
Sort
SplitAt: A helper trait to split a set into two sets at a given index. This trait is used to implement iteration over ChunkedViews.
SplitFirst: Split out the first element of a collection.
SplitOff: A helper trait to split owned sets into two sets at a given index. This trait is used to implement iteration over Chunkeds.
SplitOffsetsAt
SplitPrefix: Split off a number of elements from the beginning of the collection where the number is determined at compile time.
StaticallySplittable: A marker trait to indicate a collection type that can be chunked. More precisely this is a type that can be composed with types in this crate.
Storage: Get an immutable reference to the underlying storage type.
StorageInto: Convert the storage type into another using the Into trait.
StorageMut: Get a mutable reference to the underlying storage type.
StorageView
SwapChunks
Truncate: Truncate the collection to be a specified length.
TrustedRandomAccess: An iterator whose items are random-accessible efficiently
UniChunkable: A trait intended to be implemented on collection types to define the type of a statically sized chunk in this collection. This trait is required for composing with UniChunked.
Unsigned: The marker trait for compile time unsigned integers.
ValueType: A marker trait to indicate an owned collection type. This is to distinguish them from borrowed types, which is essential to resolve implementation collisions.
View: A trait defining a collection that can be accessed via an immutable (shared) view. This type of view can be cloned and copied.
ViewIterator: A convenience trait to allow generic implementations to call an iterator over the view. This is necessary because the View trait has an explicit lifetime parameter, which makes it difficult or impossible to use in generic functions. For instance it becomes difficult/impossible to impose constraints like Set on View::Type.
ViewMut: A trait defining a collection that can be accessed via a mutable (unique) view.
ViewMutIterator
Viewed: A marker trait to indicate a viewed collection type. Note that collections can be partially viewed, but only completely viewed collections are marked by Viewed.
WriteSet

Type Aliases§

Chunked1
Chunked2
Chunked3
Chunked4
Chunked5
Chunked6
Chunked7
Chunked8
Chunked9
ChunkedN: Define aliases for common uniform chunked types.
ChunkedView
Clumped: Clumped is a variation of Chunked that compactly represents equidistant offsets as “clumps”, hence the name.
ClumpedView: A view of a Clumped collection.
SelectView: A borrowed selection.
SparseView: A borrowed view of a sparse collection.
SubsetView: A borrowed subset.
U1
U2
U3
U4
U5
U6
U7
U8
U9
U10
U11
U12
U13
U14
U15
U16

Derive Macros§

Component

Crate flatk

Crate flatk Copy item path

§Indexing

Modules§

Macros§

Structs§

Enums§

Traits§

Type Aliases§

Derive Macros§

Crate flatk