devela/data/layout/array/
coord.rs

1// devela::data::layout::array::coord
2//
3//! Logical array-coordinate traversal.
4//
5// > A finite exhaustive traversal of a rectangular n-dimensional coordinate domain.
6
7use crate::{ArrayShape, IteratorFused, is, whilst};
8
9#[doc = crate::_tags!(data_structure iterator)]
10/// An iterator over the coordinates of an array shape.
11#[doc = crate::_doc_meta!{
12    location("data/layout/array", struct ArrayCoordIter),
13    #[cfg(target_pointer_width = "32")]
14    test_size_of(ArrayCoordIter<2> = 28|224; niche !Option),
15    #[cfg(target_pointer_width = "64")]
16    test_size_of(ArrayCoordIter<2> = 56|448; niche !Option),
17}]
18/// Coordinates are yielded in canonical logical order,
19/// with axis `0` changing fastest.
20///
21/// This matches physical storage order for a dense-first layout. For other
22/// layouts, logical coordinate order and physical storage order may differ.
23///
24/// For a shape with lengths `[2, 3]`, the sequence is:
25///
26/// ```text
27/// [0, 0]
28/// [1, 0]
29/// [0, 1]
30/// [1, 1]
31/// [0, 2]
32/// [1, 2]
33/// ```
34///
35/// This iterator describes only the logical coordinate domain.
36/// It does not inspect an [`ArrayLayout`][crate::ArrayLayout]'s
37/// offset or strides and does not access any physical storage.
38///
39/// A rank-zero shape yields its sole coordinate, `[]`, once.
40/// A shape with any zero-length axis yields no coordinates.
41///
42/// The inherent [`next`][Self::next] method is `const`. The [`Iterator`]
43/// implementation delegates to it for ordinary runtime iteration.
44#[must_use]
45#[derive(Clone, Debug, PartialEq, Eq, Hash)]
46pub struct ArrayCoordIter<const RANK: usize> {
47    shape: ArrayShape<RANK>,
48    front: [usize; RANK],
49    back: [usize; RANK],
50    remaining: usize,
51}
52
53impl<const RANK: usize> ArrayCoordIter<RANK> {
54    /// Creates an iterator with a previously validated element count.
55    pub(crate) const fn new(shape: ArrayShape<RANK>, remaining: usize) -> Self {
56        let mut back = [0; RANK];
57        if remaining != 0 {
58            let lengths = shape.lengths();
59            whilst! { axis in 0..RANK; {
60                back[axis] = lengths[axis] - 1;
61            }}
62        }
63        Self { shape, front: [0; RANK], back, remaining }
64    }
65
66    /// Returns the number of coordinates not yet yielded.
67    #[must_use]
68    pub const fn len(&self) -> usize {
69        self.remaining
70    }
71    /// Returns whether no coordinates remain.
72    #[must_use]
73    pub const fn is_empty(&self) -> bool {
74        self.remaining == 0
75    }
76
77    /// Returns the complete logical shape being traversed.
78    pub const fn shape(&self) -> ArrayShape<RANK> {
79        self.shape
80    }
81
82    /// Advances the iterator and returns the next coordinate from the front.
83    #[must_use]
84    pub const fn next(&mut self) -> Option<[usize; RANK]> {
85        is! { self.remaining == 0, return None }
86        let coord = self.front;
87        self.remaining -= 1;
88        is! { self.remaining != 0, self.advance_front() }
89        Some(coord)
90    }
91
92    /// Advances the iterator and returns the next coordinate from the back.
93    #[must_use]
94    pub const fn next_back(&mut self) -> Option<[usize; RANK]> {
95        is! { self.remaining == 0, return None }
96        let coord = self.back;
97        self.remaining -= 1;
98        is! { self.remaining != 0, self.advance_back() }
99        Some(coord)
100    }
101
102    /// Returns the next coordinate from the front without advancing the iterator.
103    pub const fn peek(&self) -> Option<[usize; RANK]> {
104        is! { self.remaining == 0, None, Some(self.front) }
105    }
106    /// Returns the next coordinate from the back without advancing the iterator.
107    pub const fn peek_back(&self) -> Option<[usize; RANK]> {
108        is! { self.remaining == 0, None, Some(self.back) }
109    }
110
111    const fn advance_front(&mut self) {
112        let lengths = self.shape.lengths();
113        whilst! { axis in 0..RANK; {
114            self.front[axis] += 1;
115            if self.front[axis] < lengths[axis] { return; }
116            self.front[axis] = 0;
117        }}
118    }
119    const fn advance_back(&mut self) {
120        let lengths = self.shape.lengths();
121        whilst! { axis in 0..RANK; {
122            if self.back[axis] != 0 {
123                self.back[axis] -= 1;
124                return;
125            }
126            self.back[axis] = lengths[axis] - 1;
127        }}
128    }
129}
130
131/* impl traits */
132
133impl<const RANK: usize> Iterator for ArrayCoordIter<RANK> {
134    type Item = [usize; RANK];
135
136    fn next(&mut self) -> Option<Self::Item> {
137        Self::next(self)
138    }
139    fn count(self) -> usize {
140        self.remaining
141    }
142    fn size_hint(&self) -> (usize, Option<usize>) {
143        let len = self.remaining;
144        (len, Some(len))
145    }
146}
147impl<const RANK: usize> DoubleEndedIterator for ArrayCoordIter<RANK> {
148    fn next_back(&mut self) -> Option<Self::Item> {
149        Self::next_back(self)
150    }
151}
152impl<const RANK: usize> ExactSizeIterator for ArrayCoordIter<RANK> {
153    fn len(&self) -> usize {
154        Self::len(self)
155    }
156}
157impl<const RANK: usize> IteratorFused for ArrayCoordIter<RANK> {}
158
159#[cfg(test)]
160mod _test {
161    use super::*;
162    #[cfg(feature = "alloc")]
163    use crate::Vec;
164    use crate::{Array, ArrayLayout, const_assert};
165
166    const COORDS_2_3: [[usize; 2]; 6] = {
167        let shape = ArrayShape::new([2, 3]);
168        let layout = match ArrayLayout::dense_first(shape) {
169            Ok(layout) => layout,
170            Err(_) => panic!("unexpected layout overflow"),
171        };
172        let mut iter = layout.coords();
173        let mut output = [[0; 2]; 6];
174        let mut index = 0;
175        while let Some(coord) = iter.next() {
176            output[index] = coord;
177            index += 1;
178        }
179        assert!(index == 6);
180        assert!(iter.is_empty());
181        output
182    };
183    const LAST_2_3: [usize; 2] = {
184        let shape = ArrayShape::new([2, 3]);
185        let layout = match ArrayLayout::dense_first(shape) {
186            Ok(layout) => layout,
187            Err(_) => panic!("unexpected layout overflow"),
188        };
189        let mut iter = layout.coords();
190        match iter.next_back() {
191            Some(coord) => coord,
192            None => panic!("missing coordinate"),
193        }
194    };
195    #[test]
196    const fn const_coordinate_iteration() {
197        const_assert!(eq COORDS_2_3[0][0], 0);
198        const_assert!(eq COORDS_2_3[0][1], 0);
199        const_assert!(eq COORDS_2_3[1][0], 1);
200        const_assert!(eq COORDS_2_3[1][1], 0);
201        const_assert!(eq COORDS_2_3[2][0], 0);
202        const_assert!(eq COORDS_2_3[2][1], 1);
203        const_assert!(eq COORDS_2_3[5][0], 1);
204        const_assert!(eq COORDS_2_3[5][1], 2);
205    }
206    #[test]
207    const fn const_back_coordinate_iteration() {
208        const_assert!(eq LAST_2_3[0], 1);
209        const_assert!(eq LAST_2_3[1], 2);
210    }
211
212    #[test]
213    #[cfg(feature = "alloc")]
214    fn shape_coordinate_sequence() {
215        let coords: Vec<_> = ArrayShape::new([2, 3]).try_coords().unwrap().collect();
216        assert_eq!(coords, [[0, 0], [1, 0], [0, 1], [1, 1], [0, 2], [1, 2],]);
217    }
218    #[test]
219    #[cfg(feature = "alloc")]
220    fn coordinate_order_is_layout_independent() {
221        let shape = ArrayShape::new([2, 3]);
222        let first: Vec<_> = ArrayLayout::dense_first(shape).unwrap().coords().collect();
223        let last: Vec<_> = ArrayLayout::dense_last(shape).unwrap().coords().collect();
224        assert_eq!(first, last);
225    }
226    #[test]
227    fn scalar_coordinate() {
228        let mut iter = ArrayShape::<0>::new([]).try_coords().unwrap();
229        assert_eq!(iter.len(), 1);
230        assert_eq!(iter.next(), Some([]));
231        assert_eq!(iter.next(), None);
232        assert_eq!(iter.next(), None);
233    }
234    #[test]
235    fn empty_shape_has_no_coordinates() {
236        let mut iter = ArrayShape::new([4, 0, 8]).try_coords().unwrap();
237        assert!(iter.is_empty());
238        assert_eq!(iter.next(), None);
239    }
240    #[test]
241    fn overflowing_shape_rejects_exact_iteration() {
242        let shape = ArrayShape::new([usize::MAX, 2]);
243        assert!(shape.try_coords().is_err());
244    }
245    #[test]
246    fn exact_size_tracks_remaining_coordinates() {
247        let mut iter = ArrayShape::new([2, 2]).try_coords().unwrap();
248        assert_eq!(iter.len(), 4);
249        assert_eq!(iter.size_hint(), (4, Some(4)));
250        assert_eq!(iter.next(), Some([0, 0]));
251        assert_eq!(iter.len(), 3);
252        assert_eq!(iter.next(), Some([1, 0]));
253        assert_eq!(iter.len(), 2);
254    }
255    #[test]
256    fn array_coords_do_not_depend_on_backing() {
257        let layout = ArrayLayout::dense_first(ArrayShape::new([2, 2])).unwrap();
258        let array = Array::try_from_array([0, 1, 2, 3], layout).unwrap();
259        let mut coords = array.coords();
260
261        assert_eq!(coords.next(), Some([0, 0]));
262        assert_eq!(coords.next(), Some([1, 0]));
263        assert_eq!(coords.next(), Some([0, 1]));
264        assert_eq!(coords.next(), Some([1, 1]));
265        assert_eq!(coords.next(), None);
266    }
267}
devela/data/layout/array/coord.rs

devela/data/layout/array/
coord.rs
