n_circular_array

N Circular Array

An n-dimensional circular array.

Features

• Fixed dimension arrays of any size.
• Element insertion to the front or back of any dimension.
• Indexing, range and slicing operations.
• Optimized for contiguous memory.
• Support for external types through AsRef<[T]> and AsMut<[T]>.
• Thorough testing for arrays of smaller dimensionality.
• No external dependencies.

Usage

The following example demonstrates the basic functionality offered by this crate.

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

array.push_front(0, &[6, 7]);
assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[2, 3, 4, 5, 6, 7]);
array.push_back(0, &[0, 1]);
assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[0, 1, 2, 3, 4, 5]);

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

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

// Push to the back of axis 1.
array.push_back(1, &[12, 13, 14]);
assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
    12, 13, 14,
     1,  2,  9,
     4,  5, 10
]);

// Iterate over index 1 of axis 0 (The second column).
assert_eq!(array.iter_index(0, 1).cloned().collect::<Vec<usize>>(), &[
    13,
     2,
     5
]);

Mutation

n_circular_array allows for mutating single elements, or inserting any number of slices to an axis. Insertion operations expect elements of row-major ordering. Operations accept either an array slice &[T], or an ExactSizeIterator of &T elements for _iter suffixed methods.

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

// Push two columns to the front of axis 0.
array.push_front(0, &[
     9, 10,
    11, 12,
    13, 14
]);

// Mutate the last element of the array (equivalent to `array.get_mut([2, 2])`).
assert_eq!(array[[2, 2]], 14);
array[[2, 2]] = 99;

assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
    2,  9, 10,
    5, 11, 12,
    8, 13, 99
]);

// Push two rows of zero to the front of axis 1.
let axis_len = array.shape()[1];
array.push_front_iter(1, std::iter::repeat(&0).take(2 * axis_len));

assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
    8, 13, 99,
    0,  0,  0,
    0,  0,  0,
]);

See [CircularArrayMut].

Indexing

n_circular_array allows for elements to be accessed by index or slice. Note that indexing operations take a fixed size array of N indices/ranges where N is the dimensionality of the array.

// A 3-dimensional array of 3*3*2 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
]);

// Get the first element at index 1 of axis 2 (equivalent to `array.get([0, 0, 1])`).
assert_eq!(array[[0, 0, 1]], 9);

// Get the second and third row.
assert_eq!(array.iter_range(1, 1..3).cloned().collect::<Vec<_>>(), &[
     3,  4,  5,
     6,  7,  8,

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

// All columns of row 2, slice 1.
assert_eq!(array.iter_slice([0..3, 2..3, 1..2]).cloned().collect::<Vec<_>>(), &[
    15, 16, 17
]);

See [CircularArrayIndex] and [CircularArrayIndexMut].

Resizing/Reshaping

Resizing or reshaping can be achieved by iterating and collecting into a new CircularArray. This functionality is not offered from within the crate to make the performance implications explicit.

// A 3-dimensional array of 3*3*2 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
]);

// Insert a row at index 0.
array.push_front(0, &[3, 6, 9, 12, 15, 18]);
assert_eq!(array.iter().cloned().collect::<Vec<_>>(), &[
     1,  2,  3,
     4,  5,  6,
     7,  8,  9,

    10, 11, 12,
    13, 14, 15,
    16, 17, 18
]);
assert_eq!(array.offset(), &[1, 0, 0]);

// Iterate over index 1 of axis 2 into a 2-dimensional array of shape [3, 3].
let iter = array.iter_slice([0..3, 0..3, 1..2]);
// Operations return `ExactSizeIterator` implementations.
assert_eq!(iter.len(), 9);
let array_2 = CircularArrayVec::from_iter([3, 3], iter.cloned());

assert_eq!(array_2.iter().cloned().collect::<Vec<_>>(), &[
    10, 11, 12,
    13, 14, 15,
    16, 17, 18
]);
assert_eq!(array_2.offset(), &[0, 0]);

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]> may also 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