circular_buffer/
iter.rs

1// Copyright © 2023-2025 Andrea Corbellini and contributors
2// SPDX-License-Identifier: BSD-3-Clause
3
4use crate::CircularBuffer;
5use core::fmt;
6use core::iter::FusedIterator;
7use core::ops::Bound;
8use core::ops::RangeBounds;
9
10/// An owning [iterator](core::iter::Iterator) over the elements of a [`CircularBuffer`].
11///
12/// This yields the elements of a `CircularBuffer` from front to back.
13///
14/// This struct is created when iterating over a `CircularBuffer`. See the documentation for
15/// [`IntoIterator`] for more details.
16#[derive(Clone)]
17pub struct IntoIter<const N: usize, T> {
18    inner: CircularBuffer<N, T>,
19}
20
21impl<const N: usize, T> IntoIter<N, T> {
22    pub(crate) const fn new(inner: CircularBuffer<N, T>) -> Self {
23        Self { inner }
24    }
25}
26
27impl<const N: usize, T> Iterator for IntoIter<N, T> {
28    type Item = T;
29
30    fn next(&mut self) -> Option<Self::Item> {
31        self.inner.pop_front()
32    }
33
34    #[inline]
35    fn size_hint(&self) -> (usize, Option<usize>) {
36        let len = self.inner.len();
37        (len, Some(len))
38    }
39}
40
41impl<const N: usize, T> ExactSizeIterator for IntoIter<N, T> {
42    #[inline]
43    fn len(&self) -> usize {
44        self.inner.len()
45    }
46}
47
48impl<const N: usize, T> FusedIterator for IntoIter<N, T> {}
49
50impl<const N: usize, T> DoubleEndedIterator for IntoIter<N, T> {
51    fn next_back(&mut self) -> Option<Self::Item> {
52        self.inner.pop_back()
53    }
54}
55
56impl<const N: usize, T> fmt::Debug for IntoIter<N, T>
57where
58    T: fmt::Debug,
59{
60    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
61        self.inner.fmt(f)
62    }
63}
64
65pub(crate) fn translate_range_bounds<const N: usize, T, R>(
66    buf: &CircularBuffer<N, T>,
67    range: R,
68) -> (usize, usize)
69where
70    R: RangeBounds<usize>,
71{
72    let start = match range.start_bound() {
73        Bound::Included(x) => *x,
74        Bound::Excluded(x) => x
75            .checked_add(1)
76            .expect("range start index exceeds maximum usize"),
77        Bound::Unbounded => 0,
78    };
79
80    let end = match range.end_bound() {
81        Bound::Included(x) => x
82            .checked_add(1)
83            .expect("range end index exceeds maximum usize"),
84        Bound::Excluded(x) => *x,
85        Bound::Unbounded => buf.len(),
86    };
87
88    assert!(
89        end <= buf.len(),
90        "range end index {} out of range for buffer of length {}",
91        end,
92        buf.len()
93    );
94    assert!(
95        start <= end,
96        "range starts at index {start} but ends at index {end}"
97    );
98
99    (start, end)
100}
101
102#[inline(always)]
103#[cfg(feature = "unstable")]
104fn slice_take<'a, T, R: core::ops::OneSidedRange<usize>>(
105    slice: &mut &'a [T],
106    range: R,
107) -> Option<&'a [T]> {
108    slice.split_off(range)
109}
110
111#[cfg(not(feature = "unstable"))]
112fn slice_take<'a, T, R: RangeBounds<usize>>(slice: &mut &'a [T], range: R) -> Option<&'a [T]> {
113    match (range.start_bound(), range.end_bound()) {
114        (Bound::Unbounded, Bound::Excluded(index)) => {
115            if *index > slice.len() {
116                return None;
117            }
118            let (left, right) = slice.split_at(*index);
119            *slice = right;
120            Some(left)
121        }
122        (Bound::Included(index), Bound::Unbounded) => {
123            if *index > slice.len() {
124                return None;
125            }
126            let (left, right) = slice.split_at(*index);
127            *slice = left;
128            Some(right)
129        }
130        _ => unimplemented!(),
131    }
132}
133
134#[inline(always)]
135#[cfg(feature = "unstable")]
136fn slice_take_mut<'a, T, R: core::ops::OneSidedRange<usize>>(
137    slice: &mut &'a mut [T],
138    range: R,
139) -> Option<&'a mut [T]> {
140    slice.split_off_mut(range)
141}
142
143#[cfg(not(feature = "unstable"))]
144fn slice_take_mut<'a, T, R: RangeBounds<usize>>(
145    slice: &mut &'a mut [T],
146    range: R,
147) -> Option<&'a mut [T]> {
148    match (range.start_bound(), range.end_bound()) {
149        (Bound::Unbounded, Bound::Excluded(index)) => {
150            if *index > slice.len() {
151                return None;
152            }
153            let (left, right) = core::mem::take(slice).split_at_mut(*index);
154            *slice = right;
155            Some(left)
156        }
157        (Bound::Included(index), Bound::Unbounded) => {
158            if *index > slice.len() {
159                return None;
160            }
161            let (left, right) = core::mem::take(slice).split_at_mut(*index);
162            *slice = left;
163            Some(right)
164        }
165        _ => unimplemented!(),
166    }
167}
168
169#[inline(always)]
170#[cfg(feature = "unstable")]
171fn slice_take_first<'a, T>(slice: &mut &'a [T]) -> Option<&'a T> {
172    slice.split_off_first()
173}
174
175#[cfg(not(feature = "unstable"))]
176fn slice_take_first<'a, T>(slice: &mut &'a [T]) -> Option<&'a T> {
177    let (item, rest) = slice.split_first()?;
178    *slice = rest;
179    Some(item)
180}
181
182#[inline(always)]
183#[cfg(feature = "unstable")]
184fn slice_take_first_mut<'a, T>(slice: &mut &'a mut [T]) -> Option<&'a mut T> {
185    slice.split_off_first_mut()
186}
187
188#[cfg(not(feature = "unstable"))]
189fn slice_take_first_mut<'a, T>(slice: &mut &'a mut [T]) -> Option<&'a mut T> {
190    let (item, rest) = core::mem::take(slice).split_first_mut()?;
191    *slice = rest;
192    Some(item)
193}
194
195#[inline(always)]
196#[cfg(feature = "unstable")]
197fn slice_take_last<'a, T>(slice: &mut &'a [T]) -> Option<&'a T> {
198    slice.split_off_last()
199}
200
201#[cfg(not(feature = "unstable"))]
202fn slice_take_last<'a, T>(slice: &mut &'a [T]) -> Option<&'a T> {
203    let (item, rest) = slice.split_last()?;
204    *slice = rest;
205    Some(item)
206}
207
208#[inline(always)]
209#[cfg(feature = "unstable")]
210fn slice_take_last_mut<'a, T>(slice: &mut &'a mut [T]) -> Option<&'a mut T> {
211    slice.split_off_last_mut()
212}
213
214#[cfg(not(feature = "unstable"))]
215fn slice_take_last_mut<'a, T>(slice: &mut &'a mut [T]) -> Option<&'a mut T> {
216    let (item, rest) = core::mem::take(slice).split_last_mut()?;
217    *slice = rest;
218    Some(item)
219}
220
221/// An [iterator](core::iter::Iterator) over the elements of a `CircularBuffer`.
222///
223/// This struct is created by [`CircularBuffer::iter()`] and [`CircularBuffer::range()`]. See
224/// their documentation for more details.
225pub struct Iter<'a, T> {
226    pub(crate) right: &'a [T],
227    pub(crate) left: &'a [T],
228}
229
230impl<'a, T> Iter<'a, T> {
231    pub(crate) const fn empty() -> Self {
232        Self {
233            right: &[],
234            left: &[],
235        }
236    }
237
238    pub(crate) fn new<const N: usize>(buf: &'a CircularBuffer<N, T>) -> Self {
239        let (right, left) = buf.as_slices();
240        Self { right, left }
241    }
242
243    pub(crate) fn over_range<const N: usize, R>(buf: &'a CircularBuffer<N, T>, range: R) -> Self
244    where
245        R: RangeBounds<usize>,
246    {
247        let (start, end) = translate_range_bounds(buf, range);
248        if start >= end {
249            Self::empty()
250        } else {
251            let len = buf.len();
252            let mut it = Self::new(buf);
253            it.advance_front_by(start);
254            it.advance_back_by(len - end);
255            it
256        }
257    }
258
259    fn advance_front_by(&mut self, count: usize) {
260        if self.right.len() > count {
261            slice_take(&mut self.right, ..count);
262        } else {
263            let take_left = count - self.right.len();
264            debug_assert!(
265                take_left <= self.left.len(),
266                "attempted to advance past the back of the buffer"
267            );
268            slice_take(&mut self.left, ..take_left);
269            self.right = &[];
270        }
271    }
272
273    fn advance_back_by(&mut self, count: usize) {
274        if self.left.len() > count {
275            let take_left = self.left.len() - count;
276            slice_take(&mut self.left, take_left..);
277        } else {
278            let take_right = self.right.len() - (count - self.left.len());
279            debug_assert!(
280                take_right <= self.right.len(),
281                "attempted to advance past the front of the buffer"
282            );
283            slice_take(&mut self.right, take_right..);
284            self.left = &[];
285        }
286    }
287}
288
289impl<T> Default for Iter<'_, T> {
290    #[inline]
291    fn default() -> Self {
292        Self::empty()
293    }
294}
295
296impl<'a, T> Iterator for Iter<'a, T> {
297    type Item = &'a T;
298
299    fn next(&mut self) -> Option<Self::Item> {
300        if let Some(item) = slice_take_first(&mut self.right) {
301            Some(item)
302        } else if let Some(item) = slice_take_first(&mut self.left) {
303            Some(item)
304        } else {
305            None
306        }
307    }
308
309    #[inline]
310    fn size_hint(&self) -> (usize, Option<usize>) {
311        let len = self.len();
312        (len, Some(len))
313    }
314}
315
316impl<T> ExactSizeIterator for Iter<'_, T> {
317    #[inline]
318    fn len(&self) -> usize {
319        self.right.len() + self.left.len()
320    }
321}
322
323impl<T> FusedIterator for Iter<'_, T> {}
324
325impl<T> DoubleEndedIterator for Iter<'_, T> {
326    fn next_back(&mut self) -> Option<Self::Item> {
327        if let Some(item) = slice_take_last(&mut self.left) {
328            Some(item)
329        } else if let Some(item) = slice_take_last(&mut self.right) {
330            Some(item)
331        } else {
332            None
333        }
334    }
335}
336
337impl<T> Clone for Iter<'_, T> {
338    fn clone(&self) -> Self {
339        Self {
340            right: self.right,
341            left: self.left,
342        }
343    }
344}
345
346impl<T> fmt::Debug for Iter<'_, T>
347where
348    T: fmt::Debug,
349{
350    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
351        f.debug_list().entries(self.clone()).finish()
352    }
353}
354
355/// A mutable [iterator](core::iter::Iterator) over the elements of a `CircularBuffer`.
356///
357/// This struct is created by [`CircularBuffer::iter_mut()`] and [`CircularBuffer::range_mut()`].
358/// See their documentation for more details.
359pub struct IterMut<'a, T> {
360    right: &'a mut [T],
361    left: &'a mut [T],
362}
363
364impl<'a, T> IterMut<'a, T> {
365    pub(crate) fn empty() -> Self {
366        Self {
367            right: &mut [],
368            left: &mut [],
369        }
370    }
371
372    pub(crate) fn new<const N: usize>(buf: &'a mut CircularBuffer<N, T>) -> Self {
373        let (right, left) = buf.as_mut_slices();
374        Self { right, left }
375    }
376
377    pub(crate) fn over_range<const N: usize, R>(buf: &'a mut CircularBuffer<N, T>, range: R) -> Self
378    where
379        R: RangeBounds<usize>,
380    {
381        let (start, end) = translate_range_bounds(buf, range);
382        if start >= end {
383            Self::empty()
384        } else {
385            let len = buf.len();
386            let mut it = Self::new(buf);
387            it.advance_front_by(start);
388            it.advance_back_by(len - end);
389            it
390        }
391    }
392
393    fn advance_front_by(&mut self, count: usize) {
394        if self.right.len() > count {
395            slice_take_mut(&mut self.right, ..count);
396        } else {
397            let take_left = count - self.right.len();
398            debug_assert!(
399                take_left <= self.left.len(),
400                "attempted to advance past the back of the buffer"
401            );
402            slice_take_mut(&mut self.left, ..take_left);
403            self.right = &mut [];
404        }
405    }
406
407    fn advance_back_by(&mut self, count: usize) {
408        if self.left.len() > count {
409            let take_left = self.left.len() - count;
410            slice_take_mut(&mut self.left, take_left..);
411        } else {
412            let take_right = self.right.len() - (count - self.left.len());
413            debug_assert!(
414                take_right <= self.right.len(),
415                "attempted to advance past the front of the buffer"
416            );
417            slice_take_mut(&mut self.right, take_right..);
418            self.left = &mut [];
419        }
420    }
421}
422
423impl<T> Default for IterMut<'_, T> {
424    #[inline]
425    fn default() -> Self {
426        Self::empty()
427    }
428}
429
430impl<'a, T> Iterator for IterMut<'a, T> {
431    type Item = &'a mut T;
432
433    fn next(&mut self) -> Option<Self::Item> {
434        if let Some(item) = slice_take_first_mut(&mut self.right) {
435            Some(item)
436        } else if let Some(item) = slice_take_first_mut(&mut self.left) {
437            Some(item)
438        } else {
439            None
440        }
441    }
442
443    #[inline]
444    fn size_hint(&self) -> (usize, Option<usize>) {
445        let len = self.len();
446        (len, Some(len))
447    }
448}
449
450impl<T> ExactSizeIterator for IterMut<'_, T> {
451    #[inline]
452    fn len(&self) -> usize {
453        self.right.len() + self.left.len()
454    }
455}
456
457impl<T> FusedIterator for IterMut<'_, T> {}
458
459impl<T> DoubleEndedIterator for IterMut<'_, T> {
460    fn next_back(&mut self) -> Option<Self::Item> {
461        if let Some(item) = slice_take_last_mut(&mut self.left) {
462            Some(item)
463        } else if let Some(item) = slice_take_last_mut(&mut self.right) {
464            Some(item)
465        } else {
466            None
467        }
468    }
469}
470
471impl<T> fmt::Debug for IterMut<'_, T>
472where
473    T: fmt::Debug,
474{
475    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
476        let it = Iter {
477            right: self.right,
478            left: self.left,
479        };
480        it.fmt(f)
481    }
482}
circular_buffer/iter.rs

circular_buffer/
iter.rs
