Crate flatk

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