# 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.
```rust
// 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`](strides::Strides),
then call [`Strides::flatten_range`](strides::Strides::flatten_range) to get
a single contiguous range for slicing (requires feature `strides`).
```rust
// 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.
```rust
// 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.
```rust
// 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.
```rust
// 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.
```rust
// 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.
```rust
// 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
`strides` | Exports [`Strides`](strides::Strides) for flattening `N` dimensional indices during translation.
### Performance
Initial version of `n_circular_array` prioritized functionality over performance.
In the current state, performance can be significantly improved. If performance is
found to make `n_circular_array` impractical, please open an issue and optimization
can be prioritized.
Circular arrays fragment sequentual data over axis bound(s). The following can
improve performance:
- If possible, orient an array 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.
- 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