n_circular_array/lib.rs
1//! # N Circular Array
2//! An n-dimensional circular array.
3//!
4//! ## Features
5//!
6//! - Fixed dimension arrays of any size.
7//! - Element insertion to the front or back of any dimension.
8//! - Indexing, range and slicing operations.
9//! - Optimized for contiguous memory.
10//! - Support for external types through `AsRef<[T]>` and `AsMut<[T]>`.
11//! - Thorough testing for arrays of smaller dimensionality.
12//! - No external dependencies.
13//!
14//! ## Usage
15//!
16//! The following example demonstrates the basic functionality offered by this
17//! crate.
18//!
19//! ```
20//! # use n_circular_array::CircularArrayVec;
21//! # use n_circular_array::CircularArrayMut;
22//! # use n_circular_array::CircularArrayIndex;
23//! // A 1-dimensional circular array of 6 elements.
24//! let mut array = CircularArrayVec::new([6], vec![0, 1, 2, 3, 4, 5]);
25//!
26//! array.push_front(0, &[6, 7]);
27//! assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[2, 3, 4, 5, 6, 7]);
28//! array.push_back(0, &[0, 1]);
29//! assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[0, 1, 2, 3, 4, 5]);
30//!
31//! // A 2-dimensional array of 3*3 elements.
32//! let mut array = CircularArrayVec::new([3, 3], vec![
33//! 0, 1, 2,
34//! 3, 4, 5,
35//! 6, 7, 8
36//! ]);
37//!
38//! // Push to the front of axis 0.
39//! array.push_front(0, &[9, 10, 11]);
40//! assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
41//! 1, 2, 9,
42//! 4, 5, 10,
43//! 7, 8, 11
44//! ]);
45//!
46//! // Push to the back of axis 1.
47//! array.push_back(1, &[12, 13, 14]);
48//! assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
49//! 12, 13, 14,
50//! 1, 2, 9,
51//! 4, 5, 10
52//! ]);
53//!
54//! // Iterate over index 1 of axis 0 (The second column).
55//! assert_eq!(array.iter_index(0, 1).cloned().collect::<Vec<usize>>(), &[
56//! 13,
57//! 2,
58//! 5
59//! ]);
60//! ```
61//!
62//! ## Mutation
63//!
64//! `n_circular_array` allows for mutating single elements, or inserting any number
65//! of slices to an axis. Insertion operations expect elements of **row-major**
66//! ordering. Operations accept either an array slice `&[T]`, or an `ExactSizeIterator`
67//! of `&T` elements for `_iter` suffixed methods.
68//! ```
69//! # use n_circular_array::CircularArrayVec;
70//! # use n_circular_array::CircularArrayMut;
71//! # use n_circular_array::CircularArrayIndex;
72//!
73//! // A 2-dimensional circular array of 3*2 elements.
74//! let mut array = CircularArrayVec::new([3, 3], vec![
75//! 0, 1, 2,
76//! 3, 4, 5,
77//! 6, 7, 8
78//! ]);
79//!
80//! // Push two columns to the front of axis 0.
81//! array.push_front(0, &[
82//! 9, 10,
83//! 11, 12,
84//! 13, 14
85//! ]);
86//!
87//! // Mutate the last element of the array (equivalent to `array.get_mut([2, 2])`).
88//! assert_eq!(array[[2, 2]], 14);
89//! array[[2, 2]] = 99;
90//!
91//! assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
92//! 2, 9, 10,
93//! 5, 11, 12,
94//! 8, 13, 99
95//! ]);
96//!
97//! // Push two rows of zero to the front of axis 1.
98//! let axis_len = array.shape()[1];
99//! array.push_front_iter(1, std::iter::repeat(&0).take(2 * axis_len));
100//!
101//! assert_eq!(array.iter().cloned().collect::<Vec<usize>>(), &[
102//! 8, 13, 99,
103//! 0, 0, 0,
104//! 0, 0, 0,
105//! ]);
106//! ```
107//! See `[CircularArrayMut]`.
108//!
109//! ## Indexing
110//!
111//! `n_circular_array` allows for elements to be accessed by index or slice. Note
112//! that indexing operations take a fixed size array of `N` indices/ranges where `N`
113//! is the dimensionality of the array.
114//!
115//! ```
116//! # use n_circular_array::CircularArrayVec;
117//! # use n_circular_array::CircularArrayMut;
118//! # use n_circular_array::CircularArrayIndex;
119//!
120//! // A 3-dimensional array of 3*3*2 elements.
121//! let mut array = CircularArrayVec::new([3, 3, 2], vec![
122//! 0, 1, 2,
123//! 3, 4, 5,
124//! 6, 7, 8,
125//!
126//! 9, 10, 11,
127//! 12, 13, 14,
128//! 15, 16, 17
129//! ]);
130//!
131//! // Get the first element at index 1 of axis 2 (equivalent to `array.get([0, 0, 1])`).
132//! assert_eq!(array[[0, 0, 1]], 9);
133//!
134//! // Get the second and third row.
135//! assert_eq!(array.iter_range(1, 1..3).cloned().collect::<Vec<_>>(), &[
136//! 3, 4, 5,
137//! 6, 7, 8,
138//!
139//! 12, 13, 14,
140//! 15, 16, 17
141//! ]);
142//!
143//! // All columns of row 2, slice 1.
144//! assert_eq!(array.iter_slice([0..3, 2..3, 1..2]).cloned().collect::<Vec<_>>(), &[
145//! 15, 16, 17
146//! ]);
147//! ```
148//! See `[CircularArrayIndex]` and `[CircularArrayIndexMut]`.
149//!
150//! ## Resizing/Reshaping
151//!
152//! Resizing or reshaping can be achieved by iterating and collecting into a new
153//! `CircularArray`. This functionality is not offered from within the crate to make the
154//! performance implications explicit.
155//!
156//! ```
157//! # use n_circular_array::CircularArrayVec;
158//! # use n_circular_array::CircularArrayIndex;
159//! # use n_circular_array::CircularArrayMut;
160//! // A 3-dimensional array of 3*3*2 elements.
161//! let mut array = CircularArrayVec::new([3, 3, 2], vec![
162//! 0, 1, 2,
163//! 3, 4, 5,
164//! 6, 7, 8,
165//!
166//! 9, 10, 11,
167//! 12, 13, 14,
168//! 15, 16, 17
169//! ]);
170//!
171//! // Insert a row at index 0.
172//! array.push_front(0, &[3, 6, 9, 12, 15, 18]);
173//! assert_eq!(array.iter().cloned().collect::<Vec<_>>(), &[
174//! 1, 2, 3,
175//! 4, 5, 6,
176//! 7, 8, 9,
177//!
178//! 10, 11, 12,
179//! 13, 14, 15,
180//! 16, 17, 18
181//! ]);
182//! assert_eq!(array.offset(), &[1, 0, 0]);
183//!
184//! // Iterate over index 1 of axis 2 into a 2-dimensional array of shape [3, 3].
185//! let iter = array.iter_slice([0..3, 0..3, 1..2]);
186//! // Operations return `ExactSizeIterator` implementations.
187//! assert_eq!(iter.len(), 9);
188//! let array_2 = CircularArrayVec::from_iter([3, 3], iter.cloned());
189//!
190//! assert_eq!(array_2.iter().cloned().collect::<Vec<_>>(), &[
191//! 10, 11, 12,
192//! 13, 14, 15,
193//! 16, 17, 18
194//! ]);
195//! assert_eq!(array_2.offset(), &[0, 0]);
196//! ```
197//!
198//! # Performance
199//!
200//! Wrapping contigous slices over the bounds of an axis reduces cache locality,
201//! especially for the innermost dimensions of any `n > 1` array. Where possible,
202//! an array should be oriented where the majority of operations are performed on the
203//! outermost dimension(s). This will allow `n_circular_array` to take contiguous
204//! slices of memory where possible, which can result in operations being reduced to
205//! as little as a single iteration over a contiguous slice, or a single call to
206//! `copy_from_slice` during mutation.
207//!
208//! External types implementing `AsRef<[T]>` and `AsMut<[T]>` may also improve performance
209//! over `Vec<T>` or `Box<T>`. If necessary, `AsRef<[T]>` and `AsMut<[T]>` can be delegated
210//! to `unsafe` methods, although this is discouraged.
211//!
212//! Finally, for smaller arrays, avoiding a circular array and simply copying (or cloning)
213//! an array window may outperform `n_circular_array`. Benchmark if unsure whether
214//! your use case benefits from `n_circular_array`.
215mod array;
216mod array_iter;
217
218#[macro_use]
219mod assertions;
220
221mod array_index;
222mod array_slice_mut;
223
224mod index;
225mod index_bounds;
226mod span;
227mod span_iter;
228mod strides;
229
230pub use array::{CircularArray, CircularArrayBox, CircularArrayVec};
231pub use array_index::{CircularArrayIndex, CircularArrayIndexMut};
232pub use array_slice_mut::CircularArrayMut;