planus/vectors/
iterators.rs

1use core::num::NonZeroUsize;
2
3use super::Vector;
4use crate::VectorRead;
5
6fn div_ceil(lhs: usize, rhs: usize) -> usize {
7    let d = lhs / rhs;
8    let r = lhs % rhs;
9    if r > 0 && rhs > 0 {
10        d + 1
11    } else {
12        d
13    }
14}
15
16/// An iterator over the elements of a `Vector`.
17///
18/// This struct is created by the [`iter`][`Vector::iter`] method on [`Vector`]s.
19pub struct Iter<'buf, T> {
20    v: Vector<'buf, T>,
21}
22
23impl<'buf, T: VectorRead<'buf> + core::fmt::Debug> core::fmt::Debug for Iter<'buf, T> {
24    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
25        f.debug_struct("Iter").field("v", &self.v).finish()
26    }
27}
28
29impl<T> Clone for Iter<'_, T> {
30    #[inline]
31    fn clone(&self) -> Self {
32        Self { v: self.v }
33    }
34}
35
36impl<'buf, T: VectorRead<'buf>> Iter<'buf, T> {
37    #[inline]
38    pub(crate) fn new(v: Vector<'buf, T>) -> Self {
39        Self { v }
40    }
41}
42
43impl<'buf, T: VectorRead<'buf>> Iterator for Iter<'buf, T> {
44    type Item = T;
45
46    #[inline]
47    fn next(&mut self) -> Option<T> {
48        if let Some((first, remaining)) = self.v.split_first() {
49            self.v = remaining;
50            Some(first)
51        } else {
52            None
53        }
54    }
55
56    #[inline]
57    fn nth(&mut self, n: usize) -> Option<Self::Item> {
58        self.v = self.v.get(n..).unwrap_or_else(|| Vector::new_empty());
59        self.next()
60    }
61
62    #[inline]
63    fn size_hint(&self) -> (usize, Option<usize>) {
64        let len = self.len();
65        (len, Some(len))
66    }
67
68    #[inline]
69    fn count(self) -> usize {
70        self.len()
71    }
72
73    #[inline]
74    fn last(self) -> Option<Self::Item> {
75        self.v.last()
76    }
77}
78
79impl<'buf, T: VectorRead<'buf>> core::iter::DoubleEndedIterator for Iter<'buf, T> {
80    #[inline]
81    fn next_back(&mut self) -> Option<Self::Item> {
82        if let Some((last, remaining)) = self.v.split_last() {
83            self.v = remaining;
84            Some(last)
85        } else {
86            None
87        }
88    }
89
90    #[inline]
91    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
92        self.v = unsafe { self.v.get_unchecked(..self.v.len().saturating_sub(n)) };
93        self.next_back()
94    }
95}
96
97impl<'buf, T: VectorRead<'buf>> core::iter::ExactSizeIterator for Iter<'buf, T> {
98    #[inline]
99    fn len(&self) -> usize {
100        self.v.len()
101    }
102}
103
104impl<'buf, T: VectorRead<'buf>> core::iter::FusedIterator for Iter<'buf, T> {}
105
106/// An iterator over a [`Vector`] in (non-overlapping) chunks (`chunk_size`
107/// elements at a time), starting at the beginning of the [`Vector`].
108///
109/// When the [`Vector`] len is not evenly divided by the chunk size, the last
110/// [`Vector`] of the iteration will be the remainder.
111///
112/// This struct is created by the [`chunks`][`Vector::chunks`] method on [`Vector`]s.
113pub struct Chunks<'buf, T> {
114    v: Vector<'buf, T>,
115    chunk_size: NonZeroUsize,
116}
117
118impl<'buf, T: VectorRead<'buf> + core::fmt::Debug> core::fmt::Debug for Chunks<'buf, T> {
119    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
120        f.debug_struct("Chunks")
121            .field("v", &self.v)
122            .field("chunk_size", &self.chunk_size)
123            .finish()
124    }
125}
126
127impl<T> Clone for Chunks<'_, T> {
128    #[inline]
129    fn clone(&self) -> Self {
130        Self {
131            v: self.v,
132            chunk_size: self.chunk_size,
133        }
134    }
135}
136
137impl<'buf, T: VectorRead<'buf>> Chunks<'buf, T> {
138    #[inline]
139    pub(crate) fn new(v: Vector<'buf, T>, chunk_size: NonZeroUsize) -> Self {
140        Self { v, chunk_size }
141    }
142}
143
144impl<'buf, T: VectorRead<'buf>> Iterator for Chunks<'buf, T> {
145    type Item = Vector<'buf, T>;
146
147    #[inline]
148    fn next(&mut self) -> Option<Vector<'buf, T>> {
149        if self.v.is_empty() {
150            None
151        } else if let Some((first, remaining)) = self.v.split_at(self.chunk_size.get()) {
152            self.v = remaining;
153            Some(first)
154        } else {
155            Some(core::mem::replace(&mut self.v, Vector::new_empty()))
156        }
157    }
158
159    #[inline]
160    fn nth(&mut self, n: usize) -> Option<Self::Item> {
161        let skip = n.saturating_mul(self.chunk_size.get());
162        self.v = self.v.get(skip..).unwrap_or_else(|| Vector::new_empty());
163        self.next()
164    }
165
166    #[inline]
167    fn size_hint(&self) -> (usize, Option<usize>) {
168        let len = self.len();
169        (len, Some(len))
170    }
171
172    #[inline]
173    fn count(self) -> usize {
174        self.len()
175    }
176
177    #[inline]
178    fn last(mut self) -> Option<Self::Item> {
179        self.next_back()
180    }
181}
182
183impl<'buf, T: VectorRead<'buf>> core::iter::DoubleEndedIterator for Chunks<'buf, T> {
184    #[inline]
185    fn next_back(&mut self) -> Option<Self::Item> {
186        if self.v.is_empty() {
187            None
188        } else {
189            let split_point = (self.v.len() - 1) / self.chunk_size * self.chunk_size.get();
190            let (remaining, last) = unsafe { self.v.split_at_unchecked(split_point) };
191            self.v = remaining;
192            Some(last)
193        }
194    }
195
196    #[inline]
197    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
198        if n > 0 {
199            // This will be strictly lower than the len
200            let new_chunk_count = self.len().saturating_sub(n);
201            // Note that all of the remaining chunks will be full chunks
202            // This makes it easy to calculate the new size
203            self.v = unsafe {
204                self.v
205                    .get_unchecked(..new_chunk_count * self.chunk_size.get())
206            };
207        }
208        self.next_back()
209    }
210}
211
212impl<'buf, T: VectorRead<'buf>> core::iter::ExactSizeIterator for Chunks<'buf, T> {
213    #[inline]
214    fn len(&self) -> usize {
215        let len = self.v.len();
216        div_ceil(len, self.chunk_size.get())
217    }
218}
219
220impl<'buf, T: VectorRead<'buf>> core::iter::FusedIterator for Chunks<'buf, T> {}
221
222/// An iterator over a [`Vector`] in (non-overlapping) chunks (`chunk_size`
223/// elements at a time), starting at the end of the [`Vector`].
224///
225/// When the [`Vector`] len is not evenly divided by the chunk size, the last [`Vector`]
226/// of the iteration will be the remainder.
227///
228/// This struct is created by the [`rchunks`][`Vector::rchunks`] method on [`Vector`]s.
229pub struct RChunks<'buf, T> {
230    v: Vector<'buf, T>,
231    chunk_size: NonZeroUsize,
232}
233
234impl<'buf, T: VectorRead<'buf> + core::fmt::Debug> core::fmt::Debug for RChunks<'buf, T> {
235    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
236        f.debug_struct("RChunks")
237            .field("v", &self.v)
238            .field("chunk_size", &self.chunk_size)
239            .finish()
240    }
241}
242
243impl<T> Clone for RChunks<'_, T> {
244    #[inline]
245    fn clone(&self) -> Self {
246        Self {
247            v: self.v,
248            chunk_size: self.chunk_size,
249        }
250    }
251}
252
253impl<'buf, T: VectorRead<'buf>> RChunks<'buf, T> {
254    #[inline]
255    pub(crate) fn new(v: Vector<'buf, T>, chunk_size: NonZeroUsize) -> Self {
256        Self { v, chunk_size }
257    }
258}
259
260impl<'buf, T: VectorRead<'buf>> Iterator for RChunks<'buf, T> {
261    type Item = Vector<'buf, T>;
262
263    #[inline]
264    fn next(&mut self) -> Option<Vector<'buf, T>> {
265        if self.v.is_empty() {
266            None
267        } else {
268            let (remaining, cur) = unsafe {
269                self.v
270                    .split_at_unchecked(self.v.len().saturating_sub(self.chunk_size.get()))
271            };
272            self.v = remaining;
273            Some(cur)
274        }
275    }
276
277    #[inline]
278    fn nth(&mut self, n: usize) -> Option<Self::Item> {
279        self.v = unsafe {
280            self.v.get_unchecked(
281                ..self
282                    .v
283                    .len()
284                    .saturating_sub(n.saturating_mul(self.chunk_size.get())),
285            )
286        };
287        self.next()
288    }
289
290    #[inline]
291    fn size_hint(&self) -> (usize, Option<usize>) {
292        let len = self.len();
293        (len, Some(len))
294    }
295
296    #[inline]
297    fn count(self) -> usize {
298        self.len()
299    }
300
301    #[inline]
302    fn last(mut self) -> Option<Self::Item> {
303        self.next_back()
304    }
305}
306
307impl<'buf, T: VectorRead<'buf>> core::iter::DoubleEndedIterator for RChunks<'buf, T> {
308    #[inline]
309    fn next_back(&mut self) -> Option<Self::Item> {
310        if self.v.is_empty() {
311            None
312        } else {
313            let mid = ((self.v.len() - 1) % self.chunk_size) + 1;
314            let (start, remaining) = unsafe { self.v.split_at_unchecked(mid) };
315            self.v = remaining;
316            Some(start)
317        }
318    }
319
320    #[inline]
321    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
322        if n > 0 {
323            // This will be strictly lower than the len
324            let new_chunk_count = self.len().saturating_sub(n);
325            // Note that all of the remaining chunks will be full chunks
326            // This makes it easy to calculate the new size
327            self.v = unsafe {
328                self.v
329                    .get_unchecked(self.v.len() - (new_chunk_count * self.chunk_size.get())..)
330            };
331        }
332        self.next_back()
333    }
334}
335
336impl<'buf, T: VectorRead<'buf>> core::iter::ExactSizeIterator for RChunks<'buf, T> {
337    #[inline]
338    fn len(&self) -> usize {
339        div_ceil(self.v.len(), self.chunk_size.get())
340    }
341}
342
343impl<'buf, T: VectorRead<'buf>> core::iter::FusedIterator for RChunks<'buf, T> {}
344
345/// An iterator over a [`Vector`] in (non-overlapping) chunks (`chunk_size` elements
346/// at a time), starting at the beginning of the slice.
347///
348/// When the [`Vector`] len is not evenly divided by the chunk size, the last
349/// up to `chunk_size-1` elements will be omitted but can be retrieved from
350/// the [`remainder`] function from the iterator.
351///
352/// This struct is created by the [`chunks_exact`] method on [`Vector`]s.
353///
354/// [`chunks_exact`]: Vector::chunks_exact
355/// [`remainder`]: ChunksExact::remainder
356pub struct ChunksExact<'buf, T> {
357    v: Vector<'buf, T>,
358    rem: Vector<'buf, T>,
359    chunk_size: NonZeroUsize,
360}
361
362impl<'buf, T: VectorRead<'buf> + core::fmt::Debug> core::fmt::Debug for ChunksExact<'buf, T> {
363    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
364        f.debug_struct("ChunksExact")
365            .field("v", &self.v)
366            .field("rem", &self.rem)
367            .field("chunk_size", &self.chunk_size)
368            .finish()
369    }
370}
371
372impl<T> Clone for ChunksExact<'_, T> {
373    #[inline]
374    fn clone(&self) -> Self {
375        Self {
376            v: self.v,
377            rem: self.rem,
378            chunk_size: self.chunk_size,
379        }
380    }
381}
382
383impl<'buf, T: VectorRead<'buf>> ChunksExact<'buf, T> {
384    #[inline]
385    pub(crate) fn new(v: Vector<'buf, T>, chunk_size: NonZeroUsize) -> Self {
386        let len = v.len() / chunk_size.get() * chunk_size.get();
387        let (v, rem) = unsafe { v.split_at_unchecked(len) };
388        Self { v, rem, chunk_size }
389    }
390
391    /// Returns the remainder of the original vector that is not going to be
392    /// returned by the iterator. The returned vector has at most `chunk_size-1`
393    /// elements.
394    #[inline]
395    #[must_use]
396    pub fn remainder(&self) -> Vector<'buf, T> {
397        self.rem
398    }
399}
400
401impl<'buf, T: VectorRead<'buf>> Iterator for ChunksExact<'buf, T> {
402    type Item = Vector<'buf, T>;
403
404    #[inline]
405    fn next(&mut self) -> Option<Vector<'buf, T>> {
406        debug_assert!(self.v.len() % self.chunk_size == 0);
407        if self.v.is_empty() {
408            None
409        } else {
410            let (first, remaining) = unsafe { self.v.split_at_unchecked(self.chunk_size.get()) };
411            self.v = remaining;
412            Some(first)
413        }
414    }
415
416    #[inline]
417    fn nth(&mut self, n: usize) -> Option<Self::Item> {
418        let skip = n.saturating_mul(self.chunk_size.get());
419        self.v = self.v.get(skip..).unwrap_or_else(|| Vector::new_empty());
420        self.next()
421    }
422
423    #[inline]
424    fn size_hint(&self) -> (usize, Option<usize>) {
425        let len = self.len();
426        (len, Some(len))
427    }
428
429    #[inline]
430    fn count(self) -> usize {
431        self.len()
432    }
433
434    #[inline]
435    fn last(mut self) -> Option<Self::Item> {
436        self.next_back()
437    }
438}
439
440impl<'buf, T: VectorRead<'buf>> core::iter::DoubleEndedIterator for ChunksExact<'buf, T> {
441    #[inline]
442    fn next_back(&mut self) -> Option<Self::Item> {
443        debug_assert!(self.v.len() % self.chunk_size == 0);
444        if self.v.is_empty() {
445            None
446        } else {
447            let (remaining, last) = unsafe {
448                self.v
449                    .split_at_unchecked(self.v.len() - self.chunk_size.get())
450            };
451            self.v = remaining;
452            Some(last)
453        }
454    }
455
456    #[inline]
457    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
458        self.v = unsafe {
459            self.v.get_unchecked(
460                ..self
461                    .v
462                    .len()
463                    .saturating_sub(n.saturating_mul(self.chunk_size.get())),
464            )
465        };
466        self.next_back()
467    }
468}
469
470impl<'buf, T: VectorRead<'buf>> core::iter::ExactSizeIterator for ChunksExact<'buf, T> {
471    #[inline]
472    fn len(&self) -> usize {
473        self.v.len() / self.chunk_size
474    }
475}
476
477impl<'buf, T: VectorRead<'buf>> core::iter::FusedIterator for ChunksExact<'buf, T> {}
478
479/// An iterator over a [`Vector`] in (non-overlapping) chunks (`chunk_size`
480/// elements at a time), starting at the end of the slice.
481///
482/// When the [`Vector`] len is not evenly divided by the chunk size, the last
483/// up to `chunk_size-1` elements will be omitted but can be retrieved from
484/// the [`remainder`] function from the iterator.
485///
486/// This struct is created by the [`rchunks_exact`] method on [`Vector`]s.
487///
488/// [`remainder`]: RChunksExact::remainder
489/// [`rchunks_exact`]: Vector::rchunks_exact
490pub struct RChunksExact<'buf, T> {
491    v: Vector<'buf, T>,
492    rem: Vector<'buf, T>,
493    chunk_size: NonZeroUsize,
494}
495
496impl<'buf, T: VectorRead<'buf> + core::fmt::Debug> core::fmt::Debug for RChunksExact<'buf, T> {
497    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
498        f.debug_struct("RChunksExact")
499            .field("v", &self.v)
500            .field("rem", &self.rem)
501            .field("chunk_size", &self.chunk_size)
502            .finish()
503    }
504}
505
506impl<T> Clone for RChunksExact<'_, T> {
507    #[inline]
508    fn clone(&self) -> Self {
509        Self {
510            v: self.v,
511            rem: self.rem,
512            chunk_size: self.chunk_size,
513        }
514    }
515}
516
517impl<'buf, T: VectorRead<'buf>> RChunksExact<'buf, T> {
518    #[inline]
519    pub(crate) fn new(v: Vector<'buf, T>, chunk_size: NonZeroUsize) -> Self {
520        let rem_size = v.len() % chunk_size;
521        let (rem, v) = unsafe { v.split_at_unchecked(rem_size) };
522        Self { v, rem, chunk_size }
523    }
524
525    /// Returns the remainder of the original vector that is not going to be
526    /// returned by the iterator. The returned vector has at most `chunk_size-1`
527    /// elements.
528    #[inline]
529    #[must_use]
530    pub fn remainder(&self) -> Vector<'buf, T> {
531        self.rem
532    }
533}
534
535impl<'buf, T: VectorRead<'buf>> Iterator for RChunksExact<'buf, T> {
536    type Item = Vector<'buf, T>;
537
538    #[inline]
539    fn next(&mut self) -> Option<Vector<'buf, T>> {
540        debug_assert!(self.v.len() % self.chunk_size == 0);
541        if self.v.is_empty() {
542            None
543        } else {
544            let (remaining, last) = unsafe {
545                self.v
546                    .split_at_unchecked(self.v.len() - self.chunk_size.get())
547            };
548            self.v = remaining;
549            Some(last)
550        }
551    }
552
553    #[inline]
554    fn nth(&mut self, n: usize) -> Option<Self::Item> {
555        self.v = unsafe {
556            self.v.get_unchecked(
557                ..self
558                    .v
559                    .len()
560                    .saturating_sub(n.saturating_mul(self.chunk_size.get())),
561            )
562        };
563        self.next()
564    }
565
566    #[inline]
567    fn size_hint(&self) -> (usize, Option<usize>) {
568        let len = self.len();
569        (len, Some(len))
570    }
571
572    #[inline]
573    fn count(self) -> usize {
574        self.len()
575    }
576
577    #[inline]
578    fn last(mut self) -> Option<Self::Item> {
579        self.next_back()
580    }
581}
582
583impl<'buf, T: VectorRead<'buf>> core::iter::DoubleEndedIterator for RChunksExact<'buf, T> {
584    #[inline]
585    fn next_back(&mut self) -> Option<Self::Item> {
586        debug_assert!(self.v.len() % self.chunk_size == 0);
587        if self.v.is_empty() {
588            None
589        } else {
590            let (first, remaining) = unsafe { self.v.split_at_unchecked(self.chunk_size.get()) };
591            self.v = remaining;
592            Some(first)
593        }
594    }
595
596    #[inline]
597    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
598        let skip = n.saturating_mul(self.chunk_size.get());
599        self.v = self.v.get(skip..).unwrap_or_else(|| Vector::new_empty());
600        self.next_back()
601    }
602}
603
604impl<'buf, T: VectorRead<'buf>> core::iter::ExactSizeIterator for RChunksExact<'buf, T> {
605    #[inline]
606    fn len(&self) -> usize {
607        self.v.len() / self.chunk_size
608    }
609}
610
611impl<'buf, T: VectorRead<'buf>> core::iter::FusedIterator for RChunksExact<'buf, T> {}
612
613/// An iterator over overlapping sub-vectors of length `size`.
614///
615/// This struct is created by the [`windows`] method on [`Vector`]s.
616///
617/// [`windows`]: Vector::windows
618pub struct Windows<'buf, T> {
619    v: Vector<'buf, T>,
620    size: NonZeroUsize,
621}
622
623impl<'buf, T: VectorRead<'buf> + core::fmt::Debug> core::fmt::Debug for Windows<'buf, T> {
624    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
625        f.debug_struct("Windows")
626            .field("v", &self.v)
627            .field("size", &self.size)
628            .finish()
629    }
630}
631
632impl<T> Clone for Windows<'_, T> {
633    #[inline]
634    fn clone(&self) -> Self {
635        Self {
636            v: self.v,
637            size: self.size,
638        }
639    }
640}
641
642impl<'buf, T: VectorRead<'buf>> Windows<'buf, T> {
643    #[inline]
644    pub(crate) fn new(v: Vector<'buf, T>, size: NonZeroUsize) -> Self {
645        Self { v, size }
646    }
647}
648
649impl<'buf, T: VectorRead<'buf>> Iterator for Windows<'buf, T> {
650    type Item = Vector<'buf, T>;
651
652    #[inline]
653    fn next(&mut self) -> Option<Vector<'buf, T>> {
654        let window = self.v.get(..self.size.get())?;
655        self.v = unsafe { self.v.get_unchecked(1..) };
656        Some(window)
657    }
658
659    #[inline]
660    fn nth(&mut self, n: usize) -> Option<Self::Item> {
661        self.v = self.v.get(n..).unwrap_or_else(|| Vector::new_empty());
662        self.next()
663    }
664
665    #[inline]
666    fn size_hint(&self) -> (usize, Option<usize>) {
667        let len = self.len();
668        (len, Some(len))
669    }
670
671    #[inline]
672    fn count(self) -> usize {
673        self.len()
674    }
675
676    #[inline]
677    fn last(mut self) -> Option<Self::Item> {
678        self.next_back()
679    }
680}
681
682impl<'buf, T: VectorRead<'buf>> core::iter::DoubleEndedIterator for Windows<'buf, T> {
683    #[inline]
684    fn next_back(&mut self) -> Option<Self::Item> {
685        let index = self.v.len().checked_sub(self.size.get())?;
686        let window = unsafe { self.v.get_unchecked(index..) };
687        self.v = unsafe { self.v.get_unchecked(..self.v.len() - 1) };
688        Some(window)
689    }
690
691    #[inline]
692    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
693        self.v = unsafe { self.v.get_unchecked(..self.v.len().saturating_sub(n)) };
694        self.next_back()
695    }
696}
697
698impl<'buf, T: VectorRead<'buf>> core::iter::ExactSizeIterator for Windows<'buf, T> {
699    #[inline]
700    fn len(&self) -> usize {
701        self.v.len().saturating_sub(self.size.get() - 1)
702    }
703}
704
705impl<'buf, T: VectorRead<'buf>> core::iter::FusedIterator for Windows<'buf, T> {}
planus/vectors/iterators.rs

planus/vectors/
iterators.rs
