n_circular_array

N Circular Array

An n-dimensional circular array.

Features

• Fixed dimension arrays of any size.
• Element retrieval by N dimensional index, range or slice.
• Element insertion to the front or back of any axis.
• N dimensional translation over a source array.
• Element iteration in sequentual or contiguous order.
• Support for external types through AsRef<[T]> and AsMut<[T]>.
• Thorough testing for arrays of smaller dimensionality.
• No external dependencies.

Mutation

n_circular_array supports the following mutating operations:

• Insert elements to either side of an axis.
• Translate over a source array.
• Mutate individual elements.

Insertion

Elements are inserted by providing a row-major slice or iterator with a length equal to an exact multiple of the given axis length. That is, a call to insert two rows must be provided exactly two rows of elements.

// A 2-dimensional circular array of 3*3 elements.
let mut array = CircularArrayVec::new([3, 3], vec![
    0, 1, 2,
    3, 4, 5,
    6, 7, 8
]);

// Push the elements 9..12 (one row) to the front of axis 1.
array.push_front(1, &[
     9, 10, 11,
]);
assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
     3,  4,  5,
     6,  7,  8,
     9, 10, 11,
]);

// Push the elements 12..18 (two columns) to the front of axis 0.
let axis_len = array.shape()[0];
array.push_front(0, &[12, 13, 14, 15, 16, 17]);
assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
      5, 12, 13,
      8, 14, 15,
     11, 16, 17,
]);

// Push the elements 19..22 (one row) to the back of axis 1.
array.push_back(1, &[
     19, 20, 21,
]);
assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
     19, 20, 21,
      5, 12, 13,
      8, 14, 15,
]);

Translation

Translation methods simplify mapping the elements of a source array to the circular array. Translation methods expect the array origin, or the position of the [0; N] element within the source array, and a translation on an axis. The provided el_fn function will recieve contiguous [Range<usize>; N] slices for mapping the new elements from the source to the circular array. CircularArray only handles slicing and mutation, and translation logic (the current translation, out of bound translation etc.) must be maintained by the user.

In the following example, rather than passing the [Range<usize>; N] slice to a 3rd-party crate, we define the source array Strides, then call Strides::flatten_range to get a single contiguous range for slicing (requires feature strides).

// A [5, 5] source array.
let src = [
     0,  1,  2,  3,  4,
     5,  6,  7,  8,  9,
    10, 11, 12, 13, 14,
    15, 16, 17, 18, 19,
    20, 21, 22, 23, 24,
];
// Strides used for flattening `N` dimensional indices.
let src_strides = Strides::new(&[5, 5]);

// Slice function.
let el_fn = |mut index: [Range<usize>; 2]| {
    &src[src_strides.flatten_range(index)]
};

// A [3, 3] circular array positioned at `[0, 0]`.
let mut origin = [0, 0];
let mut dst = CircularArray::new([3, 3], vec![
     0,  1,  2,
     5,  6,  7,
    10, 11, 12
]);

// Translate by 2 on axis 0 (Pushes 2 columns to front of axis 0).
let axis = 0;
let n = 2;
dst.translate_front(axis, n, origin, el_fn);
origin[axis] += n as usize;

assert_eq!(dst.iter().cloned().collect::<Vec<usize>>(), &[
     2,  3,  4,
     7,  8,  9,
    12, 13, 14,
]);

// Translate by 1 on axis 1 (Pushes 1 row to front of axis 1).
let axis = 1;
let n = 1;
dst.translate_front(axis, n, origin, el_fn);
origin[axis] += n as usize;

assert_eq!(dst.iter().cloned().collect::<Vec<usize>>(), &[
     7,  8,  9,
    12, 13, 14,
    17, 18, 19,
]);

assert_eq!(origin, [2, 1]);

Indexing and Slicing

n_circular_array supports the following indexing operations:

• Access elements by axis slice.
• Access elements by N dimensional slice.
• Access individual elements by index.

Slicing an axis

All elements of an axis can be iterated over by index or range. Calling [CircularIndex::iter_index] returns an iterator of elements of a shape equal to the shape of the circular array, with the specified axis set to 1. Calling [CircularIndex::iter_range] returns an iterator of elements of a shape equal to the shape of the circular array, with the specified axis set to the length of the given range.

// A 3-dimensional circular array of 3*3*2 elements.
let array = CircularArrayVec::new([3, 3, 2], vec![
     0,  1,  2,
     3,  4,  5,
     6,  7,  8,

     9, 10, 11,
    12, 13, 14,
    15, 16, 17,
]);

// Iterate over index 1 of axis 0 (shape [1, 3, 2]).
assert_eq!(array.iter_index(0, 1).cloned().collect::<Vec<usize>>(), &[
     1,
     4,
     7,

    10,
    13,
    16,
]);
// Iterate over indices 1..3 of axis 1 (shape [3, 2, 2]).
assert_eq!(array.iter_range(1, 1..3).cloned().collect::<Vec<usize>>(), &[
     3,  4,  5,
     6,  7,  8,

    12, 13, 14,
    15, 16, 17,
]);

Slicing the array

Calling [CircularIndex::iter_slice] can be used to iterate over an N dimensional slice of the array. This can be used to limit iteration to an exact subset of elements.

// A 3-dimensional circular array of 3*3*2 elements.
let array = CircularArrayVec::new([3, 3, 2], vec![
     0,  1,  2,
     3,  4,  5,
     6,  7,  8,

     9, 10, 11,
    12, 13, 14,
    15, 16, 17,
]);

// Iterate over:
//     - index 1 of axis 0,
//     - range 0..3 of axis 1 (all elements),
//     - index 1 of axis 2.
// (shape [1, 2, 1], equivalent to [2]).
assert_eq!(array.iter_slice([1..2, 0..3, 1..2]).cloned().collect::<Vec<usize>>(), &[
    10,
    13,
    16,
]);
// Iterate over:
//     - range 0..2 of axis 0,
//     - range 1..3 of axis 1,
//     - index 0 of axis 2.
// (shape [2, 2, 1], equivalent to [2, 2]).
assert_eq!(array.iter_slice([0..2, 1..3, 0..1]).cloned().collect::<Vec<usize>>(), &[
     3,  4,
     6,  7,
]);

n_circular_array resizing or reshaping functionality can be achieved by using [CircularIndex::iter_slice] and collecting into a new array.

// A 3-dimensional circular array of 3*3*2 elements.
let array3 = CircularArrayVec::new([3, 3, 2], vec![
     0,  1,  2,
     3,  4,  5,
     6,  7,  8,

     9, 10, 11,
    12, 13, 14,
    15, 16, 17,
]);

// Iterate over:
//     - range 0..2 of axis 0,
//     - range 1..3 of axis 1,
//     - index 0 of axis 2.
// (shape [2, 2, 1], equivalent to [2, 2]).
let iter = array3.iter_slice([0..2, 1..3, 0..1]).cloned();

// A 2-dimensional circular array of 3*2 elements.
let array2 = CircularArrayVec::from_iter([2, 2], iter);

assert_eq!(array2.iter().cloned().collect::<Vec<usize>>(), &[
     3,  4,
     6,  7,
]);

Index and IndexMut

Finally, n_circular_array supports [std::ops::Index] and [std::ops::IndexMut] taking an N dimensional index ([usize; N]) as argument.

// A 2-dimensional circular array of 3*3 elements.
let mut array = CircularArrayVec::new([3, 3], vec![
    0, 1, 2,
    3, 4, 5,
    6, 7, 8
]);

array[[1, 1]] += 10;
assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
    0,  1, 2,
    3, 14, 5,
    6,  7, 8
]);

Raw and Contiguous Operations

n_circular_array also include operations for iterating over elements of the array while only offsetting the data of a subset of axes. _contiguous suffixed operations return identical elements to their offset counterpart, however element order is contiguous (arbitrary for most cases). _raw suffixed operations consider data as having no offset and therefore all elements are contiguous. Both _contiguous and _raw operations are more performant than their fully offset counterparts, although the difference is negligable for smaller arrays.

// A 2-dimensional circular array of 3*3 elements.
let mut array = CircularArrayVec::new([3, 3, 2], vec![
     0,  1,  2,
     3,  4,  5,
     6,  7,  8,

     9, 10, 11,
    12, 13, 14,
    15, 16, 17,
]);

array.push_front(0, &[100].repeat(6));
array.push_front(1, &[100].repeat(6));

assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
      4,   5, 100,
      7,   8, 100,
    100, 100, 100,

     13,  14, 100,
     16,  17, 100,
    100, 100, 100
]);
// All axes are offset.
assert_eq!(array.iter_index(1, 0).cloned().collect::<Vec<usize>>(), &[
      4,   5, 100,
     13,  14, 100,
]);
// Identical to above, however element order is arbitrary.
assert_eq!(array.iter_index_contiguous(1, 0).cloned().collect::<Vec<usize>>(), &[
     100,  4,   5,
     100, 13,  14,
]);

// Our operation does not care about order.
assert_eq!(array.iter_index_contiguous(0, 0).filter(|val| **val >= 100).count(), 2);

Feature Flags

Feature	Description
strides	Exports Strides for flattening N dimensional indices during translation.

Performance

Wrapping contigous slices over the bounds of an axis reduces cache locality, especially for the innermost dimensions of any n > 1 array. Where possible, an array should be oriented where the majority of operations are performed on the outermost dimension(s). This will allow n_circular_array to take contiguous slices of memory where possible, which can result in operations being reduced to as little as a single iteration over a contiguous slice, or a single call to copy_from_slice during mutation.

External types implementing AsRef<[T]> and AsMut<[T]> can improve performance over Vec<T> or Box<T>. If necessary, AsRef<[T]> and AsMut<[T]> can be delegated to unsafe methods, although this is discouraged.

Finally, for smaller arrays, avoiding a circular array and simply copying (or cloning) an array window may outperform n_circular_array. Benchmark if unsure whether your use case benefits from n_circular_array.

License: MIT OR Apache-2.0