1 //! Definitions of a bunch of iterators for `[T]`.
3 #[macro_use] // import iterator! and forward_iterator!
7 use crate::cmp::Ordering;
9 use crate::intrinsics::{assume, exact_div, unchecked_sub};
10 use crate::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
11 use crate::marker::{PhantomData, Send, Sized, Sync};
12 use crate::mem::{self, SizedTypeProperties};
13 use crate::num::NonZeroUsize;
14 use crate::ptr::NonNull;
16 use super::{from_raw_parts, from_raw_parts_mut};
18 #[stable(feature = "rust1", since = "1.0.0")]
19 impl<'a, T> IntoIterator for &'a [T] {
21 type IntoIter = Iter<'a, T>;
23 fn into_iter(self) -> Iter<'a, T> {
28 #[stable(feature = "rust1", since = "1.0.0")]
29 impl<'a, T> IntoIterator for &'a mut [T] {
30 type Item = &'a mut T;
31 type IntoIter = IterMut<'a, T>;
33 fn into_iter(self) -> IterMut<'a, T> {
38 // Macro helper functions
40 fn size_from_ptr<T>(_: *const T) -> usize {
44 /// Immutable slice iterator
46 /// This struct is created by the [`iter`] method on [slices].
53 /// // First, we declare a type which has `iter` method to get the `Iter` struct (`&[usize]` here):
54 /// let slice = &[1, 2, 3];
56 /// // Then, we iterate over it:
57 /// for element in slice.iter() {
58 /// println!("{element}");
62 /// [`iter`]: slice::iter
64 #[stable(feature = "rust1", since = "1.0.0")]
65 #[must_use = "iterators are lazy and do nothing unless consumed"]
66 pub struct Iter<'a, T: 'a> {
68 end: *const T, // If T is a ZST, this is actually ptr+len. This encoding is picked so that
69 // ptr == end is a quick test for the Iterator being empty, that works
70 // for both ZST and non-ZST.
71 _marker: PhantomData<&'a T>,
74 #[stable(feature = "core_impl_debug", since = "1.9.0")]
75 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
76 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
77 f.debug_tuple("Iter").field(&self.as_slice()).finish()
81 #[stable(feature = "rust1", since = "1.0.0")]
82 unsafe impl<T: Sync> Sync for Iter<'_, T> {}
83 #[stable(feature = "rust1", since = "1.0.0")]
84 unsafe impl<T: Sync> Send for Iter<'_, T> {}
86 impl<'a, T> Iter<'a, T> {
88 pub(super) fn new(slice: &'a [T]) -> Self {
89 let ptr = slice.as_ptr();
90 // SAFETY: Similar to `IterMut::new`.
92 assume(!ptr.is_null());
95 if T::IS_ZST { ptr.wrapping_byte_add(slice.len()) } else { ptr.add(slice.len()) };
97 Self { ptr: NonNull::new_unchecked(ptr as *mut T), end, _marker: PhantomData }
101 /// Views the underlying data as a subslice of the original data.
103 /// This has the same lifetime as the original slice, and so the
104 /// iterator can continue to be used while this exists.
111 /// // First, we declare a type which has the `iter` method to get the `Iter`
112 /// // struct (`&[usize]` here):
113 /// let slice = &[1, 2, 3];
115 /// // Then, we get the iterator:
116 /// let mut iter = slice.iter();
117 /// // So if we print what `as_slice` method returns here, we have "[1, 2, 3]":
118 /// println!("{:?}", iter.as_slice());
120 /// // Next, we move to the second element of the slice:
122 /// // Now `as_slice` returns "[2, 3]":
123 /// println!("{:?}", iter.as_slice());
126 #[stable(feature = "iter_to_slice", since = "1.4.0")]
128 pub fn as_slice(&self) -> &'a [T] {
133 iterator! {struct Iter -> *const T, &'a T, const, {/* no mut */}, {
134 fn is_sorted_by<F>(self, mut compare: F) -> bool
137 F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>,
139 self.as_slice().windows(2).all(|w| {
140 compare(&&w[0], &&w[1]).map(|o| o != Ordering::Greater).unwrap_or(false)
145 #[stable(feature = "rust1", since = "1.0.0")]
146 impl<T> Clone for Iter<'_, T> {
148 fn clone(&self) -> Self {
149 Iter { ptr: self.ptr, end: self.end, _marker: self._marker }
153 #[stable(feature = "slice_iter_as_ref", since = "1.13.0")]
154 impl<T> AsRef<[T]> for Iter<'_, T> {
156 fn as_ref(&self) -> &[T] {
161 /// Mutable slice iterator.
163 /// This struct is created by the [`iter_mut`] method on [slices].
170 /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
171 /// // struct (`&[usize]` here):
172 /// let mut slice = &mut [1, 2, 3];
174 /// // Then, we iterate over it and increment each element value:
175 /// for element in slice.iter_mut() {
179 /// // We now have "[2, 3, 4]":
180 /// println!("{slice:?}");
183 /// [`iter_mut`]: slice::iter_mut
185 #[stable(feature = "rust1", since = "1.0.0")]
186 #[must_use = "iterators are lazy and do nothing unless consumed"]
187 pub struct IterMut<'a, T: 'a> {
189 end: *mut T, // If T is a ZST, this is actually ptr+len. This encoding is picked so that
190 // ptr == end is a quick test for the Iterator being empty, that works
191 // for both ZST and non-ZST.
192 _marker: PhantomData<&'a mut T>,
195 #[stable(feature = "core_impl_debug", since = "1.9.0")]
196 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
197 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
198 f.debug_tuple("IterMut").field(&self.make_slice()).finish()
202 #[stable(feature = "rust1", since = "1.0.0")]
203 unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
204 #[stable(feature = "rust1", since = "1.0.0")]
205 unsafe impl<T: Send> Send for IterMut<'_, T> {}
207 impl<'a, T> IterMut<'a, T> {
209 pub(super) fn new(slice: &'a mut [T]) -> Self {
210 let ptr = slice.as_mut_ptr();
211 // SAFETY: There are several things here:
213 // `ptr` has been obtained by `slice.as_ptr()` where `slice` is a valid
214 // reference thus it is non-NUL and safe to use and pass to
215 // `NonNull::new_unchecked` .
217 // Adding `slice.len()` to the starting pointer gives a pointer
218 // at the end of `slice`. `end` will never be dereferenced, only checked
219 // for direct pointer equality with `ptr` to check if the iterator is
222 // In the case of a ZST, the end pointer is just the start pointer plus
223 // the length, to also allows for the fast `ptr == end` check.
225 // See the `next_unchecked!` and `is_empty!` macros as well as the
226 // `post_inc_start` method for more information.
228 assume(!ptr.is_null());
231 if T::IS_ZST { ptr.wrapping_byte_add(slice.len()) } else { ptr.add(slice.len()) };
233 Self { ptr: NonNull::new_unchecked(ptr), end, _marker: PhantomData }
237 /// Views the underlying data as a subslice of the original data.
239 /// To avoid creating `&mut` references that alias, this is forced
240 /// to consume the iterator.
247 /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
248 /// // struct (`&[usize]` here):
249 /// let mut slice = &mut [1, 2, 3];
252 /// // Then, we get the iterator:
253 /// let mut iter = slice.iter_mut();
254 /// // We move to next element:
256 /// // So if we print what `into_slice` method returns here, we have "[2, 3]":
257 /// println!("{:?}", iter.into_slice());
260 /// // Now let's modify a value of the slice:
262 /// // First we get back the iterator:
263 /// let mut iter = slice.iter_mut();
264 /// // We change the value of the first element of the slice returned by the `next` method:
265 /// *iter.next().unwrap() += 1;
267 /// // Now slice is "[2, 2, 3]":
268 /// println!("{slice:?}");
270 #[must_use = "`self` will be dropped if the result is not used"]
271 #[stable(feature = "iter_to_slice", since = "1.4.0")]
272 pub fn into_slice(self) -> &'a mut [T] {
273 // SAFETY: the iterator was created from a mutable slice with pointer
274 // `self.ptr` and length `len!(self)`. This guarantees that all the prerequisites
275 // for `from_raw_parts_mut` are fulfilled.
276 unsafe { from_raw_parts_mut(self.ptr.as_ptr(), len!(self)) }
279 /// Views the underlying data as a subslice of the original data.
281 /// To avoid creating `&mut [T]` references that alias, the returned slice
282 /// borrows its lifetime from the iterator the method is applied on.
289 /// let mut slice: &mut [usize] = &mut [1, 2, 3];
291 /// // First, we get the iterator:
292 /// let mut iter = slice.iter_mut();
293 /// // So if we check what the `as_slice` method returns here, we have "[1, 2, 3]":
294 /// assert_eq!(iter.as_slice(), &[1, 2, 3]);
296 /// // Next, we move to the second element of the slice:
298 /// // Now `as_slice` returns "[2, 3]":
299 /// assert_eq!(iter.as_slice(), &[2, 3]);
302 #[stable(feature = "slice_iter_mut_as_slice", since = "1.53.0")]
304 pub fn as_slice(&self) -> &[T] {
308 /// Views the underlying data as a mutable subslice of the original data.
310 /// To avoid creating `&mut [T]` references that alias, the returned slice
311 /// borrows its lifetime from the iterator the method is applied on.
318 /// #![feature(slice_iter_mut_as_mut_slice)]
320 /// let mut slice: &mut [usize] = &mut [1, 2, 3];
322 /// // First, we get the iterator:
323 /// let mut iter = slice.iter_mut();
324 /// // Then, we get a mutable slice from it:
325 /// let mut_slice = iter.as_mut_slice();
326 /// // So if we check what the `as_mut_slice` method returned, we have "[1, 2, 3]":
327 /// assert_eq!(mut_slice, &mut [1, 2, 3]);
329 /// // We can use it to mutate the slice:
330 /// mut_slice[0] = 4;
331 /// mut_slice[2] = 5;
333 /// // Next, we can move to the second element of the slice, checking that
334 /// // it yields the value we just wrote:
335 /// assert_eq!(iter.next(), Some(&mut 4));
336 /// // Now `as_mut_slice` returns "[2, 5]":
337 /// assert_eq!(iter.as_mut_slice(), &mut [2, 5]);
340 // FIXME: Uncomment the `AsMut<[T]>` impl when this gets stabilized.
341 #[unstable(feature = "slice_iter_mut_as_mut_slice", issue = "93079")]
342 pub fn as_mut_slice(&mut self) -> &mut [T] {
343 // SAFETY: the iterator was created from a mutable slice with pointer
344 // `self.ptr` and length `len!(self)`. This guarantees that all the prerequisites
345 // for `from_raw_parts_mut` are fulfilled.
346 unsafe { from_raw_parts_mut(self.ptr.as_ptr(), len!(self)) }
350 #[stable(feature = "slice_iter_mut_as_slice", since = "1.53.0")]
351 impl<T> AsRef<[T]> for IterMut<'_, T> {
353 fn as_ref(&self) -> &[T] {
358 // #[stable(feature = "slice_iter_mut_as_mut_slice", since = "FIXME")]
359 // impl<T> AsMut<[T]> for IterMut<'_, T> {
360 // fn as_mut(&mut self) -> &mut [T] {
361 // self.as_mut_slice()
365 iterator! {struct IterMut -> *mut T, &'a mut T, mut, {mut}, {}}
367 /// An internal abstraction over the splitting iterators, so that
368 /// splitn, splitn_mut etc can be implemented once.
370 pub(super) trait SplitIter: DoubleEndedIterator {
371 /// Marks the underlying iterator as complete, extracting the remaining
372 /// portion of the slice.
373 fn finish(&mut self) -> Option<Self::Item>;
376 /// An iterator over subslices separated by elements that match a predicate
379 /// This struct is created by the [`split`] method on [slices].
384 /// let slice = [10, 40, 33, 20];
385 /// let mut iter = slice.split(|num| num % 3 == 0);
388 /// [`split`]: slice::split
390 #[stable(feature = "rust1", since = "1.0.0")]
391 #[must_use = "iterators are lazy and do nothing unless consumed"]
392 pub struct Split<'a, T: 'a, P>
394 P: FnMut(&T) -> bool,
396 // Used for `SplitWhitespace` and `SplitAsciiWhitespace` `as_str` methods
397 pub(crate) v: &'a [T],
399 // Used for `SplitAsciiWhitespace` `as_str` method
400 pub(crate) finished: bool,
403 impl<'a, T: 'a, P: FnMut(&T) -> bool> Split<'a, T, P> {
405 pub(super) fn new(slice: &'a [T], pred: P) -> Self {
406 Self { v: slice, pred, finished: false }
408 /// Returns a slice which contains items not yet handled by split.
412 /// #![feature(split_as_slice)]
413 /// let slice = [1,2,3,4,5];
414 /// let mut split = slice.split(|v| v % 2 == 0);
415 /// assert!(split.next().is_some());
416 /// assert_eq!(split.as_slice(), &[3,4,5]);
418 #[unstable(feature = "split_as_slice", issue = "96137")]
419 pub fn as_slice(&self) -> &'a [T] {
420 if self.finished { &[] } else { &self.v }
424 #[stable(feature = "core_impl_debug", since = "1.9.0")]
425 impl<T: fmt::Debug, P> fmt::Debug for Split<'_, T, P>
427 P: FnMut(&T) -> bool,
429 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
430 f.debug_struct("Split").field("v", &self.v).field("finished", &self.finished).finish()
434 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
435 #[stable(feature = "rust1", since = "1.0.0")]
436 impl<T, P> Clone for Split<'_, T, P>
438 P: Clone + FnMut(&T) -> bool,
440 fn clone(&self) -> Self {
441 Split { v: self.v, pred: self.pred.clone(), finished: self.finished }
445 #[stable(feature = "rust1", since = "1.0.0")]
446 impl<'a, T, P> Iterator for Split<'a, T, P>
448 P: FnMut(&T) -> bool,
453 fn next(&mut self) -> Option<&'a [T]> {
458 match self.v.iter().position(|x| (self.pred)(x)) {
459 None => self.finish(),
461 let ret = Some(&self.v[..idx]);
462 self.v = &self.v[idx + 1..];
469 fn size_hint(&self) -> (usize, Option<usize>) {
473 // If the predicate doesn't match anything, we yield one slice.
474 // If it matches every element, we yield `len() + 1` empty slices.
475 (1, Some(self.v.len() + 1))
480 #[stable(feature = "rust1", since = "1.0.0")]
481 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P>
483 P: FnMut(&T) -> bool,
486 fn next_back(&mut self) -> Option<&'a [T]> {
491 match self.v.iter().rposition(|x| (self.pred)(x)) {
492 None => self.finish(),
494 let ret = Some(&self.v[idx + 1..]);
495 self.v = &self.v[..idx];
502 impl<'a, T, P> SplitIter for Split<'a, T, P>
504 P: FnMut(&T) -> bool,
507 fn finish(&mut self) -> Option<&'a [T]> {
511 self.finished = true;
517 #[stable(feature = "fused", since = "1.26.0")]
518 impl<T, P> FusedIterator for Split<'_, T, P> where P: FnMut(&T) -> bool {}
520 /// An iterator over subslices separated by elements that match a predicate
521 /// function. Unlike `Split`, it contains the matched part as a terminator
524 /// This struct is created by the [`split_inclusive`] method on [slices].
529 /// let slice = [10, 40, 33, 20];
530 /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
533 /// [`split_inclusive`]: slice::split_inclusive
535 #[stable(feature = "split_inclusive", since = "1.51.0")]
536 #[must_use = "iterators are lazy and do nothing unless consumed"]
537 pub struct SplitInclusive<'a, T: 'a, P>
539 P: FnMut(&T) -> bool,
546 impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitInclusive<'a, T, P> {
548 pub(super) fn new(slice: &'a [T], pred: P) -> Self {
549 let finished = slice.is_empty();
550 Self { v: slice, pred, finished }
554 #[stable(feature = "split_inclusive", since = "1.51.0")]
555 impl<T: fmt::Debug, P> fmt::Debug for SplitInclusive<'_, T, P>
557 P: FnMut(&T) -> bool,
559 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
560 f.debug_struct("SplitInclusive")
562 .field("finished", &self.finished)
567 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
568 #[stable(feature = "split_inclusive", since = "1.51.0")]
569 impl<T, P> Clone for SplitInclusive<'_, T, P>
571 P: Clone + FnMut(&T) -> bool,
573 fn clone(&self) -> Self {
574 SplitInclusive { v: self.v, pred: self.pred.clone(), finished: self.finished }
578 #[stable(feature = "split_inclusive", since = "1.51.0")]
579 impl<'a, T, P> Iterator for SplitInclusive<'a, T, P>
581 P: FnMut(&T) -> bool,
586 fn next(&mut self) -> Option<&'a [T]> {
592 self.v.iter().position(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(self.v.len());
593 if idx == self.v.len() {
594 self.finished = true;
596 let ret = Some(&self.v[..idx]);
597 self.v = &self.v[idx..];
602 fn size_hint(&self) -> (usize, Option<usize>) {
606 // If the predicate doesn't match anything, we yield one slice.
607 // If it matches every element, we yield `len()` one-element slices,
608 // or a single empty slice.
609 (1, Some(cmp::max(1, self.v.len())))
614 #[stable(feature = "split_inclusive", since = "1.51.0")]
615 impl<'a, T, P> DoubleEndedIterator for SplitInclusive<'a, T, P>
617 P: FnMut(&T) -> bool,
620 fn next_back(&mut self) -> Option<&'a [T]> {
625 // The last index of self.v is already checked and found to match
626 // by the last iteration, so we start searching a new match
627 // one index to the left.
628 let remainder = if self.v.is_empty() { &[] } else { &self.v[..(self.v.len() - 1)] };
629 let idx = remainder.iter().rposition(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(0);
631 self.finished = true;
633 let ret = Some(&self.v[idx..]);
634 self.v = &self.v[..idx];
639 #[stable(feature = "split_inclusive", since = "1.51.0")]
640 impl<T, P> FusedIterator for SplitInclusive<'_, T, P> where P: FnMut(&T) -> bool {}
642 /// An iterator over the mutable subslices of the vector which are separated
643 /// by elements that match `pred`.
645 /// This struct is created by the [`split_mut`] method on [slices].
650 /// let mut v = [10, 40, 30, 20, 60, 50];
651 /// let iter = v.split_mut(|num| *num % 3 == 0);
654 /// [`split_mut`]: slice::split_mut
656 #[stable(feature = "rust1", since = "1.0.0")]
657 #[must_use = "iterators are lazy and do nothing unless consumed"]
658 pub struct SplitMut<'a, T: 'a, P>
660 P: FnMut(&T) -> bool,
667 impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitMut<'a, T, P> {
669 pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
670 Self { v: slice, pred, finished: false }
674 #[stable(feature = "core_impl_debug", since = "1.9.0")]
675 impl<T: fmt::Debug, P> fmt::Debug for SplitMut<'_, T, P>
677 P: FnMut(&T) -> bool,
679 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
680 f.debug_struct("SplitMut").field("v", &self.v).field("finished", &self.finished).finish()
684 impl<'a, T, P> SplitIter for SplitMut<'a, T, P>
686 P: FnMut(&T) -> bool,
689 fn finish(&mut self) -> Option<&'a mut [T]> {
693 self.finished = true;
694 Some(mem::replace(&mut self.v, &mut []))
699 #[stable(feature = "rust1", since = "1.0.0")]
700 impl<'a, T, P> Iterator for SplitMut<'a, T, P>
702 P: FnMut(&T) -> bool,
704 type Item = &'a mut [T];
707 fn next(&mut self) -> Option<&'a mut [T]> {
712 match self.v.iter().position(|x| (self.pred)(x)) {
713 None => self.finish(),
715 let tmp = mem::take(&mut self.v);
716 // idx is the index of the element we are splitting on. We want to set self to the
717 // region after idx, and return the subslice before and not including idx.
718 // So first we split after idx
719 let (head, tail) = tmp.split_at_mut(idx + 1);
721 // Then return the subslice up to but not including the found element
722 Some(&mut head[..idx])
728 fn size_hint(&self) -> (usize, Option<usize>) {
732 // If the predicate doesn't match anything, we yield one slice.
733 // If it matches every element, we yield `len() + 1` empty slices.
734 (1, Some(self.v.len() + 1))
739 #[stable(feature = "rust1", since = "1.0.0")]
740 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P>
742 P: FnMut(&T) -> bool,
745 fn next_back(&mut self) -> Option<&'a mut [T]> {
751 // work around borrowck limitations
752 let pred = &mut self.pred;
753 self.v.iter().rposition(|x| (*pred)(x))
756 None => self.finish(),
758 let tmp = mem::replace(&mut self.v, &mut []);
759 let (head, tail) = tmp.split_at_mut(idx);
767 #[stable(feature = "fused", since = "1.26.0")]
768 impl<T, P> FusedIterator for SplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
770 /// An iterator over the mutable subslices of the vector which are separated
771 /// by elements that match `pred`. Unlike `SplitMut`, it contains the matched
772 /// parts in the ends of the subslices.
774 /// This struct is created by the [`split_inclusive_mut`] method on [slices].
779 /// let mut v = [10, 40, 30, 20, 60, 50];
780 /// let iter = v.split_inclusive_mut(|num| *num % 3 == 0);
783 /// [`split_inclusive_mut`]: slice::split_inclusive_mut
785 #[stable(feature = "split_inclusive", since = "1.51.0")]
786 #[must_use = "iterators are lazy and do nothing unless consumed"]
787 pub struct SplitInclusiveMut<'a, T: 'a, P>
789 P: FnMut(&T) -> bool,
796 impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitInclusiveMut<'a, T, P> {
798 pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
799 let finished = slice.is_empty();
800 Self { v: slice, pred, finished }
804 #[stable(feature = "split_inclusive", since = "1.51.0")]
805 impl<T: fmt::Debug, P> fmt::Debug for SplitInclusiveMut<'_, T, P>
807 P: FnMut(&T) -> bool,
809 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
810 f.debug_struct("SplitInclusiveMut")
812 .field("finished", &self.finished)
817 #[stable(feature = "split_inclusive", since = "1.51.0")]
818 impl<'a, T, P> Iterator for SplitInclusiveMut<'a, T, P>
820 P: FnMut(&T) -> bool,
822 type Item = &'a mut [T];
825 fn next(&mut self) -> Option<&'a mut [T]> {
831 // work around borrowck limitations
832 let pred = &mut self.pred;
833 self.v.iter().position(|x| (*pred)(x))
835 let idx = idx_opt.map(|idx| idx + 1).unwrap_or(self.v.len());
836 if idx == self.v.len() {
837 self.finished = true;
839 let tmp = mem::replace(&mut self.v, &mut []);
840 let (head, tail) = tmp.split_at_mut(idx);
846 fn size_hint(&self) -> (usize, Option<usize>) {
850 // If the predicate doesn't match anything, we yield one slice.
851 // If it matches every element, we yield `len()` one-element slices,
852 // or a single empty slice.
853 (1, Some(cmp::max(1, self.v.len())))
858 #[stable(feature = "split_inclusive", since = "1.51.0")]
859 impl<'a, T, P> DoubleEndedIterator for SplitInclusiveMut<'a, T, P>
861 P: FnMut(&T) -> bool,
864 fn next_back(&mut self) -> Option<&'a mut [T]> {
869 let idx_opt = if self.v.is_empty() {
872 // work around borrowck limitations
873 let pred = &mut self.pred;
875 // The last index of self.v is already checked and found to match
876 // by the last iteration, so we start searching a new match
877 // one index to the left.
878 let remainder = &self.v[..(self.v.len() - 1)];
879 remainder.iter().rposition(|x| (*pred)(x))
881 let idx = idx_opt.map(|idx| idx + 1).unwrap_or(0);
883 self.finished = true;
885 let tmp = mem::replace(&mut self.v, &mut []);
886 let (head, tail) = tmp.split_at_mut(idx);
892 #[stable(feature = "split_inclusive", since = "1.51.0")]
893 impl<T, P> FusedIterator for SplitInclusiveMut<'_, T, P> where P: FnMut(&T) -> bool {}
895 /// An iterator over subslices separated by elements that match a predicate
896 /// function, starting from the end of the slice.
898 /// This struct is created by the [`rsplit`] method on [slices].
903 /// let slice = [11, 22, 33, 0, 44, 55];
904 /// let iter = slice.rsplit(|num| *num == 0);
907 /// [`rsplit`]: slice::rsplit
909 #[stable(feature = "slice_rsplit", since = "1.27.0")]
910 #[must_use = "iterators are lazy and do nothing unless consumed"]
911 pub struct RSplit<'a, T: 'a, P>
913 P: FnMut(&T) -> bool,
915 inner: Split<'a, T, P>,
918 impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplit<'a, T, P> {
920 pub(super) fn new(slice: &'a [T], pred: P) -> Self {
921 Self { inner: Split::new(slice, pred) }
925 #[stable(feature = "slice_rsplit", since = "1.27.0")]
926 impl<T: fmt::Debug, P> fmt::Debug for RSplit<'_, T, P>
928 P: FnMut(&T) -> bool,
930 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
931 f.debug_struct("RSplit")
932 .field("v", &self.inner.v)
933 .field("finished", &self.inner.finished)
938 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
939 #[stable(feature = "slice_rsplit", since = "1.27.0")]
940 impl<T, P> Clone for RSplit<'_, T, P>
942 P: Clone + FnMut(&T) -> bool,
944 fn clone(&self) -> Self {
945 RSplit { inner: self.inner.clone() }
949 #[stable(feature = "slice_rsplit", since = "1.27.0")]
950 impl<'a, T, P> Iterator for RSplit<'a, T, P>
952 P: FnMut(&T) -> bool,
957 fn next(&mut self) -> Option<&'a [T]> {
958 self.inner.next_back()
962 fn size_hint(&self) -> (usize, Option<usize>) {
963 self.inner.size_hint()
967 #[stable(feature = "slice_rsplit", since = "1.27.0")]
968 impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P>
970 P: FnMut(&T) -> bool,
973 fn next_back(&mut self) -> Option<&'a [T]> {
978 #[stable(feature = "slice_rsplit", since = "1.27.0")]
979 impl<'a, T, P> SplitIter for RSplit<'a, T, P>
981 P: FnMut(&T) -> bool,
984 fn finish(&mut self) -> Option<&'a [T]> {
989 #[stable(feature = "slice_rsplit", since = "1.27.0")]
990 impl<T, P> FusedIterator for RSplit<'_, T, P> where P: FnMut(&T) -> bool {}
992 /// An iterator over the subslices of the vector which are separated
993 /// by elements that match `pred`, starting from the end of the slice.
995 /// This struct is created by the [`rsplit_mut`] method on [slices].
1000 /// let mut slice = [11, 22, 33, 0, 44, 55];
1001 /// let iter = slice.rsplit_mut(|num| *num == 0);
1004 /// [`rsplit_mut`]: slice::rsplit_mut
1006 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1007 #[must_use = "iterators are lazy and do nothing unless consumed"]
1008 pub struct RSplitMut<'a, T: 'a, P>
1010 P: FnMut(&T) -> bool,
1012 inner: SplitMut<'a, T, P>,
1015 impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitMut<'a, T, P> {
1017 pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
1018 Self { inner: SplitMut::new(slice, pred) }
1022 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1023 impl<T: fmt::Debug, P> fmt::Debug for RSplitMut<'_, T, P>
1025 P: FnMut(&T) -> bool,
1027 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1028 f.debug_struct("RSplitMut")
1029 .field("v", &self.inner.v)
1030 .field("finished", &self.inner.finished)
1035 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1036 impl<'a, T, P> SplitIter for RSplitMut<'a, T, P>
1038 P: FnMut(&T) -> bool,
1041 fn finish(&mut self) -> Option<&'a mut [T]> {
1046 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1047 impl<'a, T, P> Iterator for RSplitMut<'a, T, P>
1049 P: FnMut(&T) -> bool,
1051 type Item = &'a mut [T];
1054 fn next(&mut self) -> Option<&'a mut [T]> {
1055 self.inner.next_back()
1059 fn size_hint(&self) -> (usize, Option<usize>) {
1060 self.inner.size_hint()
1064 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1065 impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P>
1067 P: FnMut(&T) -> bool,
1070 fn next_back(&mut self) -> Option<&'a mut [T]> {
1075 #[stable(feature = "slice_rsplit", since = "1.27.0")]
1076 impl<T, P> FusedIterator for RSplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
1078 /// An private iterator over subslices separated by elements that
1079 /// match a predicate function, splitting at most a fixed number of
1082 struct GenericSplitN<I> {
1087 impl<T, I: SplitIter<Item = T>> Iterator for GenericSplitN<I> {
1091 fn next(&mut self) -> Option<T> {
1106 fn size_hint(&self) -> (usize, Option<usize>) {
1107 let (lower, upper_opt) = self.iter.size_hint();
1109 cmp::min(self.count, lower),
1110 Some(upper_opt.map_or(self.count, |upper| cmp::min(self.count, upper))),
1115 /// An iterator over subslices separated by elements that match a predicate
1116 /// function, limited to a given number of splits.
1118 /// This struct is created by the [`splitn`] method on [slices].
1123 /// let slice = [10, 40, 30, 20, 60, 50];
1124 /// let iter = slice.splitn(2, |num| *num % 3 == 0);
1127 /// [`splitn`]: slice::splitn
1129 #[stable(feature = "rust1", since = "1.0.0")]
1130 #[must_use = "iterators are lazy and do nothing unless consumed"]
1131 pub struct SplitN<'a, T: 'a, P>
1133 P: FnMut(&T) -> bool,
1135 inner: GenericSplitN<Split<'a, T, P>>,
1138 impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitN<'a, T, P> {
1140 pub(super) fn new(s: Split<'a, T, P>, n: usize) -> Self {
1141 Self { inner: GenericSplitN { iter: s, count: n } }
1145 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1146 impl<T: fmt::Debug, P> fmt::Debug for SplitN<'_, T, P>
1148 P: FnMut(&T) -> bool,
1150 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1151 f.debug_struct("SplitN").field("inner", &self.inner).finish()
1155 /// An iterator over subslices separated by elements that match a
1156 /// predicate function, limited to a given number of splits, starting
1157 /// from the end of the slice.
1159 /// This struct is created by the [`rsplitn`] method on [slices].
1164 /// let slice = [10, 40, 30, 20, 60, 50];
1165 /// let iter = slice.rsplitn(2, |num| *num % 3 == 0);
1168 /// [`rsplitn`]: slice::rsplitn
1170 #[stable(feature = "rust1", since = "1.0.0")]
1171 #[must_use = "iterators are lazy and do nothing unless consumed"]
1172 pub struct RSplitN<'a, T: 'a, P>
1174 P: FnMut(&T) -> bool,
1176 inner: GenericSplitN<RSplit<'a, T, P>>,
1179 impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitN<'a, T, P> {
1181 pub(super) fn new(s: RSplit<'a, T, P>, n: usize) -> Self {
1182 Self { inner: GenericSplitN { iter: s, count: n } }
1186 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1187 impl<T: fmt::Debug, P> fmt::Debug for RSplitN<'_, T, P>
1189 P: FnMut(&T) -> bool,
1191 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1192 f.debug_struct("RSplitN").field("inner", &self.inner).finish()
1196 /// An iterator over subslices separated by elements that match a predicate
1197 /// function, limited to a given number of splits.
1199 /// This struct is created by the [`splitn_mut`] method on [slices].
1204 /// let mut slice = [10, 40, 30, 20, 60, 50];
1205 /// let iter = slice.splitn_mut(2, |num| *num % 3 == 0);
1208 /// [`splitn_mut`]: slice::splitn_mut
1210 #[stable(feature = "rust1", since = "1.0.0")]
1211 #[must_use = "iterators are lazy and do nothing unless consumed"]
1212 pub struct SplitNMut<'a, T: 'a, P>
1214 P: FnMut(&T) -> bool,
1216 inner: GenericSplitN<SplitMut<'a, T, P>>,
1219 impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitNMut<'a, T, P> {
1221 pub(super) fn new(s: SplitMut<'a, T, P>, n: usize) -> Self {
1222 Self { inner: GenericSplitN { iter: s, count: n } }
1226 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1227 impl<T: fmt::Debug, P> fmt::Debug for SplitNMut<'_, T, P>
1229 P: FnMut(&T) -> bool,
1231 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1232 f.debug_struct("SplitNMut").field("inner", &self.inner).finish()
1236 /// An iterator over subslices separated by elements that match a
1237 /// predicate function, limited to a given number of splits, starting
1238 /// from the end of the slice.
1240 /// This struct is created by the [`rsplitn_mut`] method on [slices].
1245 /// let mut slice = [10, 40, 30, 20, 60, 50];
1246 /// let iter = slice.rsplitn_mut(2, |num| *num % 3 == 0);
1249 /// [`rsplitn_mut`]: slice::rsplitn_mut
1251 #[stable(feature = "rust1", since = "1.0.0")]
1252 #[must_use = "iterators are lazy and do nothing unless consumed"]
1253 pub struct RSplitNMut<'a, T: 'a, P>
1255 P: FnMut(&T) -> bool,
1257 inner: GenericSplitN<RSplitMut<'a, T, P>>,
1260 impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitNMut<'a, T, P> {
1262 pub(super) fn new(s: RSplitMut<'a, T, P>, n: usize) -> Self {
1263 Self { inner: GenericSplitN { iter: s, count: n } }
1267 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1268 impl<T: fmt::Debug, P> fmt::Debug for RSplitNMut<'_, T, P>
1270 P: FnMut(&T) -> bool,
1272 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1273 f.debug_struct("RSplitNMut").field("inner", &self.inner).finish()
1277 forward_iterator! { SplitN: T, &'a [T] }
1278 forward_iterator! { RSplitN: T, &'a [T] }
1279 forward_iterator! { SplitNMut: T, &'a mut [T] }
1280 forward_iterator! { RSplitNMut: T, &'a mut [T] }
1282 /// An iterator over overlapping subslices of length `size`.
1284 /// This struct is created by the [`windows`] method on [slices].
1289 /// let slice = ['r', 'u', 's', 't'];
1290 /// let iter = slice.windows(2);
1293 /// [`windows`]: slice::windows
1296 #[stable(feature = "rust1", since = "1.0.0")]
1297 #[must_use = "iterators are lazy and do nothing unless consumed"]
1298 pub struct Windows<'a, T: 'a> {
1303 impl<'a, T: 'a> Windows<'a, T> {
1305 pub(super) fn new(slice: &'a [T], size: NonZeroUsize) -> Self {
1306 Self { v: slice, size }
1310 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1311 #[stable(feature = "rust1", since = "1.0.0")]
1312 impl<T> Clone for Windows<'_, T> {
1313 fn clone(&self) -> Self {
1314 Windows { v: self.v, size: self.size }
1318 #[stable(feature = "rust1", since = "1.0.0")]
1319 impl<'a, T> Iterator for Windows<'a, T> {
1320 type Item = &'a [T];
1323 fn next(&mut self) -> Option<&'a [T]> {
1324 if self.size.get() > self.v.len() {
1327 let ret = Some(&self.v[..self.size.get()]);
1328 self.v = &self.v[1..];
1334 fn size_hint(&self) -> (usize, Option<usize>) {
1335 if self.size.get() > self.v.len() {
1338 let size = self.v.len() - self.size.get() + 1;
1344 fn count(self) -> usize {
1349 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1350 let (end, overflow) = self.size.get().overflowing_add(n);
1351 if end > self.v.len() || overflow {
1355 let nth = &self.v[n..end];
1356 self.v = &self.v[n + 1..];
1362 fn last(self) -> Option<Self::Item> {
1363 if self.size.get() > self.v.len() {
1366 let start = self.v.len() - self.size.get();
1367 Some(&self.v[start..])
1371 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1372 // SAFETY: since the caller guarantees that `i` is in bounds,
1373 // which means that `i` cannot overflow an `isize`, and the
1374 // slice created by `from_raw_parts` is a subslice of `self.v`
1375 // thus is guaranteed to be valid for the lifetime `'a` of `self.v`.
1376 unsafe { from_raw_parts(self.v.as_ptr().add(idx), self.size.get()) }
1380 #[stable(feature = "rust1", since = "1.0.0")]
1381 impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
1383 fn next_back(&mut self) -> Option<&'a [T]> {
1384 if self.size.get() > self.v.len() {
1387 let ret = Some(&self.v[self.v.len() - self.size.get()..]);
1388 self.v = &self.v[..self.v.len() - 1];
1394 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1395 let (end, overflow) = self.v.len().overflowing_sub(n);
1396 if end < self.size.get() || overflow {
1400 let ret = &self.v[end - self.size.get()..end];
1401 self.v = &self.v[..end - 1];
1407 #[stable(feature = "rust1", since = "1.0.0")]
1408 impl<T> ExactSizeIterator for Windows<'_, T> {}
1410 #[unstable(feature = "trusted_len", issue = "37572")]
1411 unsafe impl<T> TrustedLen for Windows<'_, T> {}
1413 #[stable(feature = "fused", since = "1.26.0")]
1414 impl<T> FusedIterator for Windows<'_, T> {}
1417 #[unstable(feature = "trusted_random_access", issue = "none")]
1418 unsafe impl<'a, T> TrustedRandomAccess for Windows<'a, T> {}
1421 #[unstable(feature = "trusted_random_access", issue = "none")]
1422 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Windows<'a, T> {
1423 const MAY_HAVE_SIDE_EFFECT: bool = false;
1426 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
1427 /// time), starting at the beginning of the slice.
1429 /// When the slice len is not evenly divided by the chunk size, the last slice
1430 /// of the iteration will be the remainder.
1432 /// This struct is created by the [`chunks`] method on [slices].
1437 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1438 /// let iter = slice.chunks(2);
1441 /// [`chunks`]: slice::chunks
1444 #[stable(feature = "rust1", since = "1.0.0")]
1445 #[must_use = "iterators are lazy and do nothing unless consumed"]
1446 pub struct Chunks<'a, T: 'a> {
1451 impl<'a, T: 'a> Chunks<'a, T> {
1453 pub(super) fn new(slice: &'a [T], size: usize) -> Self {
1454 Self { v: slice, chunk_size: size }
1458 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1459 #[stable(feature = "rust1", since = "1.0.0")]
1460 impl<T> Clone for Chunks<'_, T> {
1461 fn clone(&self) -> Self {
1462 Chunks { v: self.v, chunk_size: self.chunk_size }
1466 #[stable(feature = "rust1", since = "1.0.0")]
1467 impl<'a, T> Iterator for Chunks<'a, T> {
1468 type Item = &'a [T];
1471 fn next(&mut self) -> Option<&'a [T]> {
1472 if self.v.is_empty() {
1475 let chunksz = cmp::min(self.v.len(), self.chunk_size);
1476 let (fst, snd) = self.v.split_at(chunksz);
1483 fn size_hint(&self) -> (usize, Option<usize>) {
1484 if self.v.is_empty() {
1487 let n = self.v.len() / self.chunk_size;
1488 let rem = self.v.len() % self.chunk_size;
1489 let n = if rem > 0 { n + 1 } else { n };
1495 fn count(self) -> usize {
1500 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1501 let (start, overflow) = n.overflowing_mul(self.chunk_size);
1502 if start >= self.v.len() || overflow {
1506 let end = match start.checked_add(self.chunk_size) {
1507 Some(sum) => cmp::min(self.v.len(), sum),
1508 None => self.v.len(),
1510 let nth = &self.v[start..end];
1511 self.v = &self.v[end..];
1517 fn last(self) -> Option<Self::Item> {
1518 if self.v.is_empty() {
1521 let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
1522 Some(&self.v[start..])
1526 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1527 let start = idx * self.chunk_size;
1528 // SAFETY: the caller guarantees that `i` is in bounds,
1529 // which means that `start` must be in bounds of the
1530 // underlying `self.v` slice, and we made sure that `len`
1531 // is also in bounds of `self.v`. Thus, `start` cannot overflow
1532 // an `isize`, and the slice constructed by `from_raw_parts`
1533 // is a subslice of `self.v` which is guaranteed to be valid
1534 // for the lifetime `'a` of `self.v`.
1536 let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size);
1537 from_raw_parts(self.v.as_ptr().add(start), len)
1542 #[stable(feature = "rust1", since = "1.0.0")]
1543 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
1545 fn next_back(&mut self) -> Option<&'a [T]> {
1546 if self.v.is_empty() {
1549 let remainder = self.v.len() % self.chunk_size;
1550 let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
1551 // SAFETY: split_at_unchecked requires the argument be less than or
1552 // equal to the length. This is guaranteed, but subtle: `chunksz`
1553 // will always either be `self.v.len() % self.chunk_size`, which
1554 // will always evaluate to strictly less than `self.v.len()` (or
1555 // panic, in the case that `self.chunk_size` is zero), or it can be
1556 // `self.chunk_size`, in the case that the length is exactly
1557 // divisible by the chunk size.
1559 // While it seems like using `self.chunk_size` in this case could
1560 // lead to a value greater than `self.v.len()`, it cannot: if
1561 // `self.chunk_size` were greater than `self.v.len()`, then
1562 // `self.v.len() % self.chunk_size` would return nonzero (note that
1563 // in this branch of the `if`, we already know that `self.v` is
1565 let (fst, snd) = unsafe { self.v.split_at_unchecked(self.v.len() - chunksz) };
1572 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1573 let len = self.len();
1578 let start = (len - 1 - n) * self.chunk_size;
1579 let end = match start.checked_add(self.chunk_size) {
1580 Some(res) => cmp::min(self.v.len(), res),
1581 None => self.v.len(),
1583 let nth_back = &self.v[start..end];
1584 self.v = &self.v[..start];
1590 #[stable(feature = "rust1", since = "1.0.0")]
1591 impl<T> ExactSizeIterator for Chunks<'_, T> {}
1593 #[unstable(feature = "trusted_len", issue = "37572")]
1594 unsafe impl<T> TrustedLen for Chunks<'_, T> {}
1596 #[stable(feature = "fused", since = "1.26.0")]
1597 impl<T> FusedIterator for Chunks<'_, T> {}
1600 #[unstable(feature = "trusted_random_access", issue = "none")]
1601 unsafe impl<'a, T> TrustedRandomAccess for Chunks<'a, T> {}
1604 #[unstable(feature = "trusted_random_access", issue = "none")]
1605 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Chunks<'a, T> {
1606 const MAY_HAVE_SIDE_EFFECT: bool = false;
1609 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
1610 /// elements at a time), starting at the beginning of the slice.
1612 /// When the slice len is not evenly divided by the chunk size, the last slice
1613 /// of the iteration will be the remainder.
1615 /// This struct is created by the [`chunks_mut`] method on [slices].
1620 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
1621 /// let iter = slice.chunks_mut(2);
1624 /// [`chunks_mut`]: slice::chunks_mut
1627 #[stable(feature = "rust1", since = "1.0.0")]
1628 #[must_use = "iterators are lazy and do nothing unless consumed"]
1629 pub struct ChunksMut<'a, T: 'a> {
1631 /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
1632 /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
1633 /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
1634 /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
1635 /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
1638 _marker: PhantomData<&'a mut T>,
1641 impl<'a, T: 'a> ChunksMut<'a, T> {
1643 pub(super) fn new(slice: &'a mut [T], size: usize) -> Self {
1644 Self { v: slice, chunk_size: size, _marker: PhantomData }
1648 #[stable(feature = "rust1", since = "1.0.0")]
1649 impl<'a, T> Iterator for ChunksMut<'a, T> {
1650 type Item = &'a mut [T];
1653 fn next(&mut self) -> Option<&'a mut [T]> {
1654 if self.v.is_empty() {
1657 let sz = cmp::min(self.v.len(), self.chunk_size);
1658 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1659 let (head, tail) = unsafe { self.v.split_at_mut(sz) };
1661 // SAFETY: Nothing else points to or will point to the contents of this slice.
1662 Some(unsafe { &mut *head })
1667 fn size_hint(&self) -> (usize, Option<usize>) {
1668 if self.v.is_empty() {
1671 let n = self.v.len() / self.chunk_size;
1672 let rem = self.v.len() % self.chunk_size;
1673 let n = if rem > 0 { n + 1 } else { n };
1679 fn count(self) -> usize {
1684 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
1685 let (start, overflow) = n.overflowing_mul(self.chunk_size);
1686 if start >= self.v.len() || overflow {
1690 let end = match start.checked_add(self.chunk_size) {
1691 Some(sum) => cmp::min(self.v.len(), sum),
1692 None => self.v.len(),
1694 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1695 let (head, tail) = unsafe { self.v.split_at_mut(end) };
1696 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1697 let (_, nth) = unsafe { head.split_at_mut(start) };
1699 // SAFETY: Nothing else points to or will point to the contents of this slice.
1700 Some(unsafe { &mut *nth })
1705 fn last(self) -> Option<Self::Item> {
1706 if self.v.is_empty() {
1709 let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
1710 // SAFETY: Nothing else points to or will point to the contents of this slice.
1711 Some(unsafe { &mut *self.v.get_unchecked_mut(start..) })
1715 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1716 let start = idx * self.chunk_size;
1717 // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`.
1719 // Also note that the caller also guarantees that we're never called
1720 // with the same index again, and that no other methods that will
1721 // access this subslice are called, so it is valid for the returned
1722 // slice to be mutable.
1724 let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size);
1725 from_raw_parts_mut(self.v.as_mut_ptr().add(start), len)
1730 #[stable(feature = "rust1", since = "1.0.0")]
1731 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
1733 fn next_back(&mut self) -> Option<&'a mut [T]> {
1734 if self.v.is_empty() {
1737 let remainder = self.v.len() % self.chunk_size;
1738 let sz = if remainder != 0 { remainder } else { self.chunk_size };
1739 let len = self.v.len();
1740 // SAFETY: Similar to `Chunks::next_back`
1741 let (head, tail) = unsafe { self.v.split_at_mut_unchecked(len - sz) };
1743 // SAFETY: Nothing else points to or will point to the contents of this slice.
1744 Some(unsafe { &mut *tail })
1749 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1750 let len = self.len();
1755 let start = (len - 1 - n) * self.chunk_size;
1756 let end = match start.checked_add(self.chunk_size) {
1757 Some(res) => cmp::min(self.v.len(), res),
1758 None => self.v.len(),
1760 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1761 let (temp, _tail) = unsafe { self.v.split_at_mut(end) };
1762 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1763 let (head, nth_back) = unsafe { temp.split_at_mut(start) };
1765 // SAFETY: Nothing else points to or will point to the contents of this slice.
1766 Some(unsafe { &mut *nth_back })
1771 #[stable(feature = "rust1", since = "1.0.0")]
1772 impl<T> ExactSizeIterator for ChunksMut<'_, T> {}
1774 #[unstable(feature = "trusted_len", issue = "37572")]
1775 unsafe impl<T> TrustedLen for ChunksMut<'_, T> {}
1777 #[stable(feature = "fused", since = "1.26.0")]
1778 impl<T> FusedIterator for ChunksMut<'_, T> {}
1781 #[unstable(feature = "trusted_random_access", issue = "none")]
1782 unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {}
1785 #[unstable(feature = "trusted_random_access", issue = "none")]
1786 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksMut<'a, T> {
1787 const MAY_HAVE_SIDE_EFFECT: bool = false;
1790 #[stable(feature = "rust1", since = "1.0.0")]
1791 unsafe impl<T> Send for ChunksMut<'_, T> where T: Send {}
1793 #[stable(feature = "rust1", since = "1.0.0")]
1794 unsafe impl<T> Sync for ChunksMut<'_, T> where T: Sync {}
1796 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
1797 /// time), starting at the beginning of the slice.
1799 /// When the slice len is not evenly divided by the chunk size, the last
1800 /// up to `chunk_size-1` elements will be omitted but can be retrieved from
1801 /// the [`remainder`] function from the iterator.
1803 /// This struct is created by the [`chunks_exact`] method on [slices].
1808 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1809 /// let iter = slice.chunks_exact(2);
1812 /// [`chunks_exact`]: slice::chunks_exact
1813 /// [`remainder`]: ChunksExact::remainder
1816 #[stable(feature = "chunks_exact", since = "1.31.0")]
1817 #[must_use = "iterators are lazy and do nothing unless consumed"]
1818 pub struct ChunksExact<'a, T: 'a> {
1824 impl<'a, T> ChunksExact<'a, T> {
1826 pub(super) fn new(slice: &'a [T], chunk_size: usize) -> Self {
1827 let rem = slice.len() % chunk_size;
1828 let fst_len = slice.len() - rem;
1829 // SAFETY: 0 <= fst_len <= slice.len() by construction above
1830 let (fst, snd) = unsafe { slice.split_at_unchecked(fst_len) };
1831 Self { v: fst, rem: snd, chunk_size }
1834 /// Returns the remainder of the original slice that is not going to be
1835 /// returned by the iterator. The returned slice has at most `chunk_size-1`
1841 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1842 /// let mut iter = slice.chunks_exact(2);
1843 /// assert_eq!(iter.remainder(), &['m'][..]);
1844 /// assert_eq!(iter.next(), Some(&['l', 'o'][..]));
1845 /// assert_eq!(iter.remainder(), &['m'][..]);
1846 /// assert_eq!(iter.next(), Some(&['r', 'e'][..]));
1847 /// assert_eq!(iter.remainder(), &['m'][..]);
1848 /// assert_eq!(iter.next(), None);
1849 /// assert_eq!(iter.remainder(), &['m'][..]);
1852 #[stable(feature = "chunks_exact", since = "1.31.0")]
1853 pub fn remainder(&self) -> &'a [T] {
1858 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1859 #[stable(feature = "chunks_exact", since = "1.31.0")]
1860 impl<T> Clone for ChunksExact<'_, T> {
1861 fn clone(&self) -> Self {
1862 ChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
1866 #[stable(feature = "chunks_exact", since = "1.31.0")]
1867 impl<'a, T> Iterator for ChunksExact<'a, T> {
1868 type Item = &'a [T];
1871 fn next(&mut self) -> Option<&'a [T]> {
1872 if self.v.len() < self.chunk_size {
1875 let (fst, snd) = self.v.split_at(self.chunk_size);
1882 fn size_hint(&self) -> (usize, Option<usize>) {
1883 let n = self.v.len() / self.chunk_size;
1888 fn count(self) -> usize {
1893 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1894 let (start, overflow) = n.overflowing_mul(self.chunk_size);
1895 if start >= self.v.len() || overflow {
1899 let (_, snd) = self.v.split_at(start);
1906 fn last(mut self) -> Option<Self::Item> {
1910 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1911 let start = idx * self.chunk_size;
1912 // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
1913 unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) }
1917 #[stable(feature = "chunks_exact", since = "1.31.0")]
1918 impl<'a, T> DoubleEndedIterator for ChunksExact<'a, T> {
1920 fn next_back(&mut self) -> Option<&'a [T]> {
1921 if self.v.len() < self.chunk_size {
1924 let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
1931 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1932 let len = self.len();
1937 let start = (len - 1 - n) * self.chunk_size;
1938 let end = start + self.chunk_size;
1939 let nth_back = &self.v[start..end];
1940 self.v = &self.v[..start];
1946 #[stable(feature = "chunks_exact", since = "1.31.0")]
1947 impl<T> ExactSizeIterator for ChunksExact<'_, T> {
1948 fn is_empty(&self) -> bool {
1953 #[unstable(feature = "trusted_len", issue = "37572")]
1954 unsafe impl<T> TrustedLen for ChunksExact<'_, T> {}
1956 #[stable(feature = "chunks_exact", since = "1.31.0")]
1957 impl<T> FusedIterator for ChunksExact<'_, T> {}
1960 #[unstable(feature = "trusted_random_access", issue = "none")]
1961 unsafe impl<'a, T> TrustedRandomAccess for ChunksExact<'a, T> {}
1964 #[unstable(feature = "trusted_random_access", issue = "none")]
1965 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExact<'a, T> {
1966 const MAY_HAVE_SIDE_EFFECT: bool = false;
1969 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
1970 /// elements at a time), starting at the beginning of the slice.
1972 /// When the slice len is not evenly divided by the chunk size, the last up to
1973 /// `chunk_size-1` elements will be omitted but can be retrieved from the
1974 /// [`into_remainder`] function from the iterator.
1976 /// This struct is created by the [`chunks_exact_mut`] method on [slices].
1981 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
1982 /// let iter = slice.chunks_exact_mut(2);
1985 /// [`chunks_exact_mut`]: slice::chunks_exact_mut
1986 /// [`into_remainder`]: ChunksExactMut::into_remainder
1989 #[stable(feature = "chunks_exact", since = "1.31.0")]
1990 #[must_use = "iterators are lazy and do nothing unless consumed"]
1991 pub struct ChunksExactMut<'a, T: 'a> {
1993 /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
1994 /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
1995 /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
1996 /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
1997 /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
1999 rem: &'a mut [T], // The iterator never yields from here, so this can be unique
2001 _marker: PhantomData<&'a mut T>,
2004 impl<'a, T> ChunksExactMut<'a, T> {
2006 pub(super) fn new(slice: &'a mut [T], chunk_size: usize) -> Self {
2007 let rem = slice.len() % chunk_size;
2008 let fst_len = slice.len() - rem;
2009 // SAFETY: 0 <= fst_len <= slice.len() by construction above
2010 let (fst, snd) = unsafe { slice.split_at_mut_unchecked(fst_len) };
2011 Self { v: fst, rem: snd, chunk_size, _marker: PhantomData }
2014 /// Returns the remainder of the original slice that is not going to be
2015 /// returned by the iterator. The returned slice has at most `chunk_size-1`
2017 #[must_use = "`self` will be dropped if the result is not used"]
2018 #[stable(feature = "chunks_exact", since = "1.31.0")]
2019 pub fn into_remainder(self) -> &'a mut [T] {
2024 #[stable(feature = "chunks_exact", since = "1.31.0")]
2025 impl<'a, T> Iterator for ChunksExactMut<'a, T> {
2026 type Item = &'a mut [T];
2029 fn next(&mut self) -> Option<&'a mut [T]> {
2030 if self.v.len() < self.chunk_size {
2033 // SAFETY: self.chunk_size is inbounds because we compared above against self.v.len()
2034 let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) };
2036 // SAFETY: Nothing else points to or will point to the contents of this slice.
2037 Some(unsafe { &mut *head })
2042 fn size_hint(&self) -> (usize, Option<usize>) {
2043 let n = self.v.len() / self.chunk_size;
2048 fn count(self) -> usize {
2053 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
2054 let (start, overflow) = n.overflowing_mul(self.chunk_size);
2055 if start >= self.v.len() || overflow {
2059 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2060 let (_, snd) = unsafe { self.v.split_at_mut(start) };
2067 fn last(mut self) -> Option<Self::Item> {
2071 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2072 let start = idx * self.chunk_size;
2073 // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`.
2074 unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) }
2078 #[stable(feature = "chunks_exact", since = "1.31.0")]
2079 impl<'a, T> DoubleEndedIterator for ChunksExactMut<'a, T> {
2081 fn next_back(&mut self) -> Option<&'a mut [T]> {
2082 if self.v.len() < self.chunk_size {
2085 // SAFETY: This subtraction is inbounds because of the check above
2086 let (head, tail) = unsafe { self.v.split_at_mut(self.v.len() - self.chunk_size) };
2088 // SAFETY: Nothing else points to or will point to the contents of this slice.
2089 Some(unsafe { &mut *tail })
2094 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2095 let len = self.len();
2100 let start = (len - 1 - n) * self.chunk_size;
2101 let end = start + self.chunk_size;
2102 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2103 let (temp, _tail) = unsafe { mem::replace(&mut self.v, &mut []).split_at_mut(end) };
2104 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2105 let (head, nth_back) = unsafe { temp.split_at_mut(start) };
2107 // SAFETY: Nothing else points to or will point to the contents of this slice.
2108 Some(unsafe { &mut *nth_back })
2113 #[stable(feature = "chunks_exact", since = "1.31.0")]
2114 impl<T> ExactSizeIterator for ChunksExactMut<'_, T> {
2115 fn is_empty(&self) -> bool {
2120 #[unstable(feature = "trusted_len", issue = "37572")]
2121 unsafe impl<T> TrustedLen for ChunksExactMut<'_, T> {}
2123 #[stable(feature = "chunks_exact", since = "1.31.0")]
2124 impl<T> FusedIterator for ChunksExactMut<'_, T> {}
2127 #[unstable(feature = "trusted_random_access", issue = "none")]
2128 unsafe impl<'a, T> TrustedRandomAccess for ChunksExactMut<'a, T> {}
2131 #[unstable(feature = "trusted_random_access", issue = "none")]
2132 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExactMut<'a, T> {
2133 const MAY_HAVE_SIDE_EFFECT: bool = false;
2136 #[stable(feature = "chunks_exact", since = "1.31.0")]
2137 unsafe impl<T> Send for ChunksExactMut<'_, T> where T: Send {}
2139 #[stable(feature = "chunks_exact", since = "1.31.0")]
2140 unsafe impl<T> Sync for ChunksExactMut<'_, T> where T: Sync {}
2142 /// A windowed iterator over a slice in overlapping chunks (`N` elements at a
2143 /// time), starting at the beginning of the slice
2145 /// This struct is created by the [`array_windows`] method on [slices].
2150 /// #![feature(array_windows)]
2152 /// let slice = [0, 1, 2, 3];
2153 /// let iter = slice.array_windows::<2>();
2156 /// [`array_windows`]: slice::array_windows
2158 #[derive(Debug, Clone, Copy)]
2159 #[unstable(feature = "array_windows", issue = "75027")]
2160 #[must_use = "iterators are lazy and do nothing unless consumed"]
2161 pub struct ArrayWindows<'a, T: 'a, const N: usize> {
2162 slice_head: *const T,
2164 marker: PhantomData<&'a [T; N]>,
2167 impl<'a, T: 'a, const N: usize> ArrayWindows<'a, T, N> {
2169 pub(super) fn new(slice: &'a [T]) -> Self {
2170 let num_windows = slice.len().saturating_sub(N - 1);
2171 Self { slice_head: slice.as_ptr(), num: num_windows, marker: PhantomData }
2175 #[unstable(feature = "array_windows", issue = "75027")]
2176 impl<'a, T, const N: usize> Iterator for ArrayWindows<'a, T, N> {
2177 type Item = &'a [T; N];
2180 fn next(&mut self) -> Option<Self::Item> {
2185 // This is safe because it's indexing into a slice guaranteed to be length > N.
2186 let ret = unsafe { &*self.slice_head.cast::<[T; N]>() };
2187 // SAFETY: Guaranteed that there are at least 1 item remaining otherwise
2188 // earlier branch would've been hit
2189 self.slice_head = unsafe { self.slice_head.add(1) };
2196 fn size_hint(&self) -> (usize, Option<usize>) {
2197 (self.num, Some(self.num))
2201 fn count(self) -> usize {
2206 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2212 // This is safe because it's indexing into a slice guaranteed to be length > N.
2213 let ret = unsafe { &*self.slice_head.add(n).cast::<[T; N]>() };
2214 // SAFETY: Guaranteed that there are at least n items remaining
2215 self.slice_head = unsafe { self.slice_head.add(n + 1) };
2222 fn last(mut self) -> Option<Self::Item> {
2223 self.nth(self.num.checked_sub(1)?)
2227 #[unstable(feature = "array_windows", issue = "75027")]
2228 impl<'a, T, const N: usize> DoubleEndedIterator for ArrayWindows<'a, T, N> {
2230 fn next_back(&mut self) -> Option<&'a [T; N]> {
2234 // SAFETY: Guaranteed that there are n items remaining, n-1 for 0-indexing.
2235 let ret = unsafe { &*self.slice_head.add(self.num - 1).cast::<[T; N]>() };
2241 fn nth_back(&mut self, n: usize) -> Option<&'a [T; N]> {
2246 // SAFETY: Guaranteed that there are n items remaining, n-1 for 0-indexing.
2247 let ret = unsafe { &*self.slice_head.add(self.num - (n + 1)).cast::<[T; N]>() };
2253 #[unstable(feature = "array_windows", issue = "75027")]
2254 impl<T, const N: usize> ExactSizeIterator for ArrayWindows<'_, T, N> {
2255 fn is_empty(&self) -> bool {
2260 /// An iterator over a slice in (non-overlapping) chunks (`N` elements at a
2261 /// time), starting at the beginning of the slice.
2263 /// When the slice len is not evenly divided by the chunk size, the last
2264 /// up to `N-1` elements will be omitted but can be retrieved from
2265 /// the [`remainder`] function from the iterator.
2267 /// This struct is created by the [`array_chunks`] method on [slices].
2272 /// #![feature(array_chunks)]
2274 /// let slice = ['l', 'o', 'r', 'e', 'm'];
2275 /// let iter = slice.array_chunks::<2>();
2278 /// [`array_chunks`]: slice::array_chunks
2279 /// [`remainder`]: ArrayChunks::remainder
2282 #[unstable(feature = "array_chunks", issue = "74985")]
2283 #[must_use = "iterators are lazy and do nothing unless consumed"]
2284 pub struct ArrayChunks<'a, T: 'a, const N: usize> {
2285 iter: Iter<'a, [T; N]>,
2289 impl<'a, T, const N: usize> ArrayChunks<'a, T, N> {
2291 pub(super) fn new(slice: &'a [T]) -> Self {
2292 let (array_slice, rem) = slice.as_chunks();
2293 Self { iter: array_slice.iter(), rem }
2296 /// Returns the remainder of the original slice that is not going to be
2297 /// returned by the iterator. The returned slice has at most `N-1`
2300 #[unstable(feature = "array_chunks", issue = "74985")]
2301 pub fn remainder(&self) -> &'a [T] {
2306 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2307 #[unstable(feature = "array_chunks", issue = "74985")]
2308 impl<T, const N: usize> Clone for ArrayChunks<'_, T, N> {
2309 fn clone(&self) -> Self {
2310 ArrayChunks { iter: self.iter.clone(), rem: self.rem }
2314 #[unstable(feature = "array_chunks", issue = "74985")]
2315 impl<'a, T, const N: usize> Iterator for ArrayChunks<'a, T, N> {
2316 type Item = &'a [T; N];
2319 fn next(&mut self) -> Option<&'a [T; N]> {
2324 fn size_hint(&self) -> (usize, Option<usize>) {
2325 self.iter.size_hint()
2329 fn count(self) -> usize {
2334 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2339 fn last(self) -> Option<Self::Item> {
2343 unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> &'a [T; N] {
2344 // SAFETY: The safety guarantees of `__iterator_get_unchecked` are
2345 // transferred to the caller.
2346 unsafe { self.iter.__iterator_get_unchecked(i) }
2350 #[unstable(feature = "array_chunks", issue = "74985")]
2351 impl<'a, T, const N: usize> DoubleEndedIterator for ArrayChunks<'a, T, N> {
2353 fn next_back(&mut self) -> Option<&'a [T; N]> {
2354 self.iter.next_back()
2358 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2359 self.iter.nth_back(n)
2363 #[unstable(feature = "array_chunks", issue = "74985")]
2364 impl<T, const N: usize> ExactSizeIterator for ArrayChunks<'_, T, N> {
2365 fn is_empty(&self) -> bool {
2366 self.iter.is_empty()
2370 #[unstable(feature = "trusted_len", issue = "37572")]
2371 unsafe impl<T, const N: usize> TrustedLen for ArrayChunks<'_, T, N> {}
2373 #[unstable(feature = "array_chunks", issue = "74985")]
2374 impl<T, const N: usize> FusedIterator for ArrayChunks<'_, T, N> {}
2377 #[unstable(feature = "array_chunks", issue = "74985")]
2378 unsafe impl<'a, T, const N: usize> TrustedRandomAccess for ArrayChunks<'a, T, N> {}
2381 #[unstable(feature = "array_chunks", issue = "74985")]
2382 unsafe impl<'a, T, const N: usize> TrustedRandomAccessNoCoerce for ArrayChunks<'a, T, N> {
2383 const MAY_HAVE_SIDE_EFFECT: bool = false;
2386 /// An iterator over a slice in (non-overlapping) mutable chunks (`N` elements
2387 /// at a time), starting at the beginning of the slice.
2389 /// When the slice len is not evenly divided by the chunk size, the last
2390 /// up to `N-1` elements will be omitted but can be retrieved from
2391 /// the [`into_remainder`] function from the iterator.
2393 /// This struct is created by the [`array_chunks_mut`] method on [slices].
2398 /// #![feature(array_chunks)]
2400 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
2401 /// let iter = slice.array_chunks_mut::<2>();
2404 /// [`array_chunks_mut`]: slice::array_chunks_mut
2405 /// [`into_remainder`]: ../../std/slice/struct.ArrayChunksMut.html#method.into_remainder
2408 #[unstable(feature = "array_chunks", issue = "74985")]
2409 #[must_use = "iterators are lazy and do nothing unless consumed"]
2410 pub struct ArrayChunksMut<'a, T: 'a, const N: usize> {
2411 iter: IterMut<'a, [T; N]>,
2415 impl<'a, T, const N: usize> ArrayChunksMut<'a, T, N> {
2417 pub(super) fn new(slice: &'a mut [T]) -> Self {
2418 let (array_slice, rem) = slice.as_chunks_mut();
2419 Self { iter: array_slice.iter_mut(), rem }
2422 /// Returns the remainder of the original slice that is not going to be
2423 /// returned by the iterator. The returned slice has at most `N-1`
2425 #[must_use = "`self` will be dropped if the result is not used"]
2426 #[unstable(feature = "array_chunks", issue = "74985")]
2427 pub fn into_remainder(self) -> &'a mut [T] {
2432 #[unstable(feature = "array_chunks", issue = "74985")]
2433 impl<'a, T, const N: usize> Iterator for ArrayChunksMut<'a, T, N> {
2434 type Item = &'a mut [T; N];
2437 fn next(&mut self) -> Option<&'a mut [T; N]> {
2442 fn size_hint(&self) -> (usize, Option<usize>) {
2443 self.iter.size_hint()
2447 fn count(self) -> usize {
2452 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2457 fn last(self) -> Option<Self::Item> {
2461 unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> &'a mut [T; N] {
2462 // SAFETY: The safety guarantees of `__iterator_get_unchecked` are transferred to
2464 unsafe { self.iter.__iterator_get_unchecked(i) }
2468 #[unstable(feature = "array_chunks", issue = "74985")]
2469 impl<'a, T, const N: usize> DoubleEndedIterator for ArrayChunksMut<'a, T, N> {
2471 fn next_back(&mut self) -> Option<&'a mut [T; N]> {
2472 self.iter.next_back()
2476 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2477 self.iter.nth_back(n)
2481 #[unstable(feature = "array_chunks", issue = "74985")]
2482 impl<T, const N: usize> ExactSizeIterator for ArrayChunksMut<'_, T, N> {
2483 fn is_empty(&self) -> bool {
2484 self.iter.is_empty()
2488 #[unstable(feature = "trusted_len", issue = "37572")]
2489 unsafe impl<T, const N: usize> TrustedLen for ArrayChunksMut<'_, T, N> {}
2491 #[unstable(feature = "array_chunks", issue = "74985")]
2492 impl<T, const N: usize> FusedIterator for ArrayChunksMut<'_, T, N> {}
2495 #[unstable(feature = "array_chunks", issue = "74985")]
2496 unsafe impl<'a, T, const N: usize> TrustedRandomAccess for ArrayChunksMut<'a, T, N> {}
2499 #[unstable(feature = "array_chunks", issue = "74985")]
2500 unsafe impl<'a, T, const N: usize> TrustedRandomAccessNoCoerce for ArrayChunksMut<'a, T, N> {
2501 const MAY_HAVE_SIDE_EFFECT: bool = false;
2504 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
2505 /// time), starting at the end of the slice.
2507 /// When the slice len is not evenly divided by the chunk size, the last slice
2508 /// of the iteration will be the remainder.
2510 /// This struct is created by the [`rchunks`] method on [slices].
2515 /// let slice = ['l', 'o', 'r', 'e', 'm'];
2516 /// let iter = slice.rchunks(2);
2519 /// [`rchunks`]: slice::rchunks
2522 #[stable(feature = "rchunks", since = "1.31.0")]
2523 #[must_use = "iterators are lazy and do nothing unless consumed"]
2524 pub struct RChunks<'a, T: 'a> {
2529 impl<'a, T: 'a> RChunks<'a, T> {
2531 pub(super) fn new(slice: &'a [T], size: usize) -> Self {
2532 Self { v: slice, chunk_size: size }
2536 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2537 #[stable(feature = "rchunks", since = "1.31.0")]
2538 impl<T> Clone for RChunks<'_, T> {
2539 fn clone(&self) -> Self {
2540 RChunks { v: self.v, chunk_size: self.chunk_size }
2544 #[stable(feature = "rchunks", since = "1.31.0")]
2545 impl<'a, T> Iterator for RChunks<'a, T> {
2546 type Item = &'a [T];
2549 fn next(&mut self) -> Option<&'a [T]> {
2550 if self.v.is_empty() {
2553 let len = self.v.len();
2554 let chunksz = cmp::min(len, self.chunk_size);
2555 // SAFETY: split_at_unchecked just requires the argument be less
2556 // than the length. This could only happen if the expression `len -
2557 // chunksz` overflows. This could only happen if `chunksz > len`,
2558 // which is impossible as we initialize it as the `min` of `len` and
2559 // `self.chunk_size`.
2560 let (fst, snd) = unsafe { self.v.split_at_unchecked(len - chunksz) };
2567 fn size_hint(&self) -> (usize, Option<usize>) {
2568 if self.v.is_empty() {
2571 let n = self.v.len() / self.chunk_size;
2572 let rem = self.v.len() % self.chunk_size;
2573 let n = if rem > 0 { n + 1 } else { n };
2579 fn count(self) -> usize {
2584 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2585 let (end, overflow) = n.overflowing_mul(self.chunk_size);
2586 if end >= self.v.len() || overflow {
2590 // Can't underflow because of the check above
2591 let end = self.v.len() - end;
2592 let start = match end.checked_sub(self.chunk_size) {
2596 let nth = &self.v[start..end];
2597 self.v = &self.v[0..start];
2603 fn last(self) -> Option<Self::Item> {
2604 if self.v.is_empty() {
2607 let rem = self.v.len() % self.chunk_size;
2608 let end = if rem == 0 { self.chunk_size } else { rem };
2609 Some(&self.v[0..end])
2613 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2614 let end = self.v.len() - idx * self.chunk_size;
2615 let start = match end.checked_sub(self.chunk_size) {
2617 Some(start) => start,
2619 // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
2620 unsafe { from_raw_parts(self.v.as_ptr().add(start), end - start) }
2624 #[stable(feature = "rchunks", since = "1.31.0")]
2625 impl<'a, T> DoubleEndedIterator for RChunks<'a, T> {
2627 fn next_back(&mut self) -> Option<&'a [T]> {
2628 if self.v.is_empty() {
2631 let remainder = self.v.len() % self.chunk_size;
2632 let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
2633 // SAFETY: similar to Chunks::next_back
2634 let (fst, snd) = unsafe { self.v.split_at_unchecked(chunksz) };
2641 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2642 let len = self.len();
2647 // can't underflow because `n < len`
2648 let offset_from_end = (len - 1 - n) * self.chunk_size;
2649 let end = self.v.len() - offset_from_end;
2650 let start = end.saturating_sub(self.chunk_size);
2651 let nth_back = &self.v[start..end];
2652 self.v = &self.v[end..];
2658 #[stable(feature = "rchunks", since = "1.31.0")]
2659 impl<T> ExactSizeIterator for RChunks<'_, T> {}
2661 #[unstable(feature = "trusted_len", issue = "37572")]
2662 unsafe impl<T> TrustedLen for RChunks<'_, T> {}
2664 #[stable(feature = "rchunks", since = "1.31.0")]
2665 impl<T> FusedIterator for RChunks<'_, T> {}
2668 #[unstable(feature = "trusted_random_access", issue = "none")]
2669 unsafe impl<'a, T> TrustedRandomAccess for RChunks<'a, T> {}
2672 #[unstable(feature = "trusted_random_access", issue = "none")]
2673 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunks<'a, T> {
2674 const MAY_HAVE_SIDE_EFFECT: bool = false;
2677 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
2678 /// elements at a time), starting at the end of the slice.
2680 /// When the slice len is not evenly divided by the chunk size, the last slice
2681 /// of the iteration will be the remainder.
2683 /// This struct is created by the [`rchunks_mut`] method on [slices].
2688 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
2689 /// let iter = slice.rchunks_mut(2);
2692 /// [`rchunks_mut`]: slice::rchunks_mut
2695 #[stable(feature = "rchunks", since = "1.31.0")]
2696 #[must_use = "iterators are lazy and do nothing unless consumed"]
2697 pub struct RChunksMut<'a, T: 'a> {
2699 /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
2700 /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
2701 /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
2702 /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
2703 /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
2706 _marker: PhantomData<&'a mut T>,
2709 impl<'a, T: 'a> RChunksMut<'a, T> {
2711 pub(super) fn new(slice: &'a mut [T], size: usize) -> Self {
2712 Self { v: slice, chunk_size: size, _marker: PhantomData }
2716 #[stable(feature = "rchunks", since = "1.31.0")]
2717 impl<'a, T> Iterator for RChunksMut<'a, T> {
2718 type Item = &'a mut [T];
2721 fn next(&mut self) -> Option<&'a mut [T]> {
2722 if self.v.is_empty() {
2725 let sz = cmp::min(self.v.len(), self.chunk_size);
2726 let len = self.v.len();
2727 // SAFETY: split_at_mut_unchecked just requires the argument be less
2728 // than the length. This could only happen if the expression
2729 // `len - sz` overflows. This could only happen if `sz >
2730 // len`, which is impossible as we initialize it as the `min` of
2731 // `self.v.len()` (e.g. `len`) and `self.chunk_size`.
2732 let (head, tail) = unsafe { self.v.split_at_mut_unchecked(len - sz) };
2734 // SAFETY: Nothing else points to or will point to the contents of this slice.
2735 Some(unsafe { &mut *tail })
2740 fn size_hint(&self) -> (usize, Option<usize>) {
2741 if self.v.is_empty() {
2744 let n = self.v.len() / self.chunk_size;
2745 let rem = self.v.len() % self.chunk_size;
2746 let n = if rem > 0 { n + 1 } else { n };
2752 fn count(self) -> usize {
2757 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
2758 let (end, overflow) = n.overflowing_mul(self.chunk_size);
2759 if end >= self.v.len() || overflow {
2763 // Can't underflow because of the check above
2764 let end = self.v.len() - end;
2765 let start = match end.checked_sub(self.chunk_size) {
2769 // SAFETY: This type ensures that self.v is a valid pointer with a correct len.
2770 // Therefore the bounds check in split_at_mut guarantees the split point is inbounds.
2771 let (head, tail) = unsafe { self.v.split_at_mut(start) };
2772 // SAFETY: This type ensures that self.v is a valid pointer with a correct len.
2773 // Therefore the bounds check in split_at_mut guarantees the split point is inbounds.
2774 let (nth, _) = unsafe { tail.split_at_mut(end - start) };
2776 // SAFETY: Nothing else points to or will point to the contents of this slice.
2777 Some(unsafe { &mut *nth })
2782 fn last(self) -> Option<Self::Item> {
2783 if self.v.is_empty() {
2786 let rem = self.v.len() % self.chunk_size;
2787 let end = if rem == 0 { self.chunk_size } else { rem };
2788 // SAFETY: Nothing else points to or will point to the contents of this slice.
2789 Some(unsafe { &mut *self.v.get_unchecked_mut(0..end) })
2793 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2794 let end = self.v.len() - idx * self.chunk_size;
2795 let start = match end.checked_sub(self.chunk_size) {
2797 Some(start) => start,
2799 // SAFETY: see comments for `RChunks::__iterator_get_unchecked` and
2800 // `ChunksMut::__iterator_get_unchecked`, `self.v`.
2801 unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start) }
2805 #[stable(feature = "rchunks", since = "1.31.0")]
2806 impl<'a, T> DoubleEndedIterator for RChunksMut<'a, T> {
2808 fn next_back(&mut self) -> Option<&'a mut [T]> {
2809 if self.v.is_empty() {
2812 let remainder = self.v.len() % self.chunk_size;
2813 let sz = if remainder != 0 { remainder } else { self.chunk_size };
2814 // SAFETY: Similar to `Chunks::next_back`
2815 let (head, tail) = unsafe { self.v.split_at_mut_unchecked(sz) };
2817 // SAFETY: Nothing else points to or will point to the contents of this slice.
2818 Some(unsafe { &mut *head })
2823 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2824 let len = self.len();
2829 // can't underflow because `n < len`
2830 let offset_from_end = (len - 1 - n) * self.chunk_size;
2831 let end = self.v.len() - offset_from_end;
2832 let start = end.saturating_sub(self.chunk_size);
2833 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2834 let (tmp, tail) = unsafe { self.v.split_at_mut(end) };
2835 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2836 let (_, nth_back) = unsafe { tmp.split_at_mut(start) };
2838 // SAFETY: Nothing else points to or will point to the contents of this slice.
2839 Some(unsafe { &mut *nth_back })
2844 #[stable(feature = "rchunks", since = "1.31.0")]
2845 impl<T> ExactSizeIterator for RChunksMut<'_, T> {}
2847 #[unstable(feature = "trusted_len", issue = "37572")]
2848 unsafe impl<T> TrustedLen for RChunksMut<'_, T> {}
2850 #[stable(feature = "rchunks", since = "1.31.0")]
2851 impl<T> FusedIterator for RChunksMut<'_, T> {}
2854 #[unstable(feature = "trusted_random_access", issue = "none")]
2855 unsafe impl<'a, T> TrustedRandomAccess for RChunksMut<'a, T> {}
2858 #[unstable(feature = "trusted_random_access", issue = "none")]
2859 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksMut<'a, T> {
2860 const MAY_HAVE_SIDE_EFFECT: bool = false;
2863 #[stable(feature = "rchunks", since = "1.31.0")]
2864 unsafe impl<T> Send for RChunksMut<'_, T> where T: Send {}
2866 #[stable(feature = "rchunks", since = "1.31.0")]
2867 unsafe impl<T> Sync for RChunksMut<'_, T> where T: Sync {}
2869 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
2870 /// time), starting at the end of the slice.
2872 /// When the slice len is not evenly divided by the chunk size, the last
2873 /// up to `chunk_size-1` elements will be omitted but can be retrieved from
2874 /// the [`remainder`] function from the iterator.
2876 /// This struct is created by the [`rchunks_exact`] method on [slices].
2881 /// let slice = ['l', 'o', 'r', 'e', 'm'];
2882 /// let iter = slice.rchunks_exact(2);
2885 /// [`rchunks_exact`]: slice::rchunks_exact
2886 /// [`remainder`]: RChunksExact::remainder
2889 #[stable(feature = "rchunks", since = "1.31.0")]
2890 #[must_use = "iterators are lazy and do nothing unless consumed"]
2891 pub struct RChunksExact<'a, T: 'a> {
2897 impl<'a, T> RChunksExact<'a, T> {
2899 pub(super) fn new(slice: &'a [T], chunk_size: usize) -> Self {
2900 let rem = slice.len() % chunk_size;
2901 // SAFETY: 0 <= rem <= slice.len() by construction above
2902 let (fst, snd) = unsafe { slice.split_at_unchecked(rem) };
2903 Self { v: snd, rem: fst, chunk_size }
2906 /// Returns the remainder of the original slice that is not going to be
2907 /// returned by the iterator. The returned slice has at most `chunk_size-1`
2913 /// let slice = ['l', 'o', 'r', 'e', 'm'];
2914 /// let mut iter = slice.rchunks_exact(2);
2915 /// assert_eq!(iter.remainder(), &['l'][..]);
2916 /// assert_eq!(iter.next(), Some(&['e', 'm'][..]));
2917 /// assert_eq!(iter.remainder(), &['l'][..]);
2918 /// assert_eq!(iter.next(), Some(&['o', 'r'][..]));
2919 /// assert_eq!(iter.remainder(), &['l'][..]);
2920 /// assert_eq!(iter.next(), None);
2921 /// assert_eq!(iter.remainder(), &['l'][..]);
2924 #[stable(feature = "rchunks", since = "1.31.0")]
2925 pub fn remainder(&self) -> &'a [T] {
2930 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2931 #[stable(feature = "rchunks", since = "1.31.0")]
2932 impl<'a, T> Clone for RChunksExact<'a, T> {
2933 fn clone(&self) -> RChunksExact<'a, T> {
2934 RChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
2938 #[stable(feature = "rchunks", since = "1.31.0")]
2939 impl<'a, T> Iterator for RChunksExact<'a, T> {
2940 type Item = &'a [T];
2943 fn next(&mut self) -> Option<&'a [T]> {
2944 if self.v.len() < self.chunk_size {
2947 let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
2954 fn size_hint(&self) -> (usize, Option<usize>) {
2955 let n = self.v.len() / self.chunk_size;
2960 fn count(self) -> usize {
2965 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2966 let (end, overflow) = n.overflowing_mul(self.chunk_size);
2967 if end >= self.v.len() || overflow {
2971 let (fst, _) = self.v.split_at(self.v.len() - end);
2978 fn last(mut self) -> Option<Self::Item> {
2982 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2983 let end = self.v.len() - idx * self.chunk_size;
2984 let start = end - self.chunk_size;
2985 // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
2986 unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) }
2990 #[stable(feature = "rchunks", since = "1.31.0")]
2991 impl<'a, T> DoubleEndedIterator for RChunksExact<'a, T> {
2993 fn next_back(&mut self) -> Option<&'a [T]> {
2994 if self.v.len() < self.chunk_size {
2997 let (fst, snd) = self.v.split_at(self.chunk_size);
3004 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
3005 let len = self.len();
3010 // now that we know that `n` corresponds to a chunk,
3011 // none of these operations can underflow/overflow
3012 let offset = (len - n) * self.chunk_size;
3013 let start = self.v.len() - offset;
3014 let end = start + self.chunk_size;
3015 let nth_back = &self.v[start..end];
3016 self.v = &self.v[end..];
3022 #[stable(feature = "rchunks", since = "1.31.0")]
3023 impl<'a, T> ExactSizeIterator for RChunksExact<'a, T> {
3024 fn is_empty(&self) -> bool {
3029 #[unstable(feature = "trusted_len", issue = "37572")]
3030 unsafe impl<T> TrustedLen for RChunksExact<'_, T> {}
3032 #[stable(feature = "rchunks", since = "1.31.0")]
3033 impl<T> FusedIterator for RChunksExact<'_, T> {}
3036 #[unstable(feature = "trusted_random_access", issue = "none")]
3037 unsafe impl<'a, T> TrustedRandomAccess for RChunksExact<'a, T> {}
3040 #[unstable(feature = "trusted_random_access", issue = "none")]
3041 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExact<'a, T> {
3042 const MAY_HAVE_SIDE_EFFECT: bool = false;
3045 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
3046 /// elements at a time), starting at the end of the slice.
3048 /// When the slice len is not evenly divided by the chunk size, the last up to
3049 /// `chunk_size-1` elements will be omitted but can be retrieved from the
3050 /// [`into_remainder`] function from the iterator.
3052 /// This struct is created by the [`rchunks_exact_mut`] method on [slices].
3057 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
3058 /// let iter = slice.rchunks_exact_mut(2);
3061 /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut
3062 /// [`into_remainder`]: RChunksExactMut::into_remainder
3065 #[stable(feature = "rchunks", since = "1.31.0")]
3066 #[must_use = "iterators are lazy and do nothing unless consumed"]
3067 pub struct RChunksExactMut<'a, T: 'a> {
3069 /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
3070 /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
3071 /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
3072 /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
3073 /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
3079 impl<'a, T> RChunksExactMut<'a, T> {
3081 pub(super) fn new(slice: &'a mut [T], chunk_size: usize) -> Self {
3082 let rem = slice.len() % chunk_size;
3083 // SAFETY: 0 <= rem <= slice.len() by construction above
3084 let (fst, snd) = unsafe { slice.split_at_mut_unchecked(rem) };
3085 Self { v: snd, rem: fst, chunk_size }
3088 /// Returns the remainder of the original slice that is not going to be
3089 /// returned by the iterator. The returned slice has at most `chunk_size-1`
3091 #[must_use = "`self` will be dropped if the result is not used"]
3092 #[stable(feature = "rchunks", since = "1.31.0")]
3093 pub fn into_remainder(self) -> &'a mut [T] {
3098 #[stable(feature = "rchunks", since = "1.31.0")]
3099 impl<'a, T> Iterator for RChunksExactMut<'a, T> {
3100 type Item = &'a mut [T];
3103 fn next(&mut self) -> Option<&'a mut [T]> {
3104 if self.v.len() < self.chunk_size {
3107 let len = self.v.len();
3108 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3109 let (head, tail) = unsafe { self.v.split_at_mut(len - self.chunk_size) };
3111 // SAFETY: Nothing else points to or will point to the contents of this slice.
3112 Some(unsafe { &mut *tail })
3117 fn size_hint(&self) -> (usize, Option<usize>) {
3118 let n = self.v.len() / self.chunk_size;
3123 fn count(self) -> usize {
3128 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
3129 let (end, overflow) = n.overflowing_mul(self.chunk_size);
3130 if end >= self.v.len() || overflow {
3134 let len = self.v.len();
3135 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3136 let (fst, _) = unsafe { self.v.split_at_mut(len - end) };
3143 fn last(mut self) -> Option<Self::Item> {
3147 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
3148 let end = self.v.len() - idx * self.chunk_size;
3149 let start = end - self.chunk_size;
3150 // SAFETY: see comments for `RChunksMut::__iterator_get_unchecked` and `self.v`.
3151 unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) }
3155 #[stable(feature = "rchunks", since = "1.31.0")]
3156 impl<'a, T> DoubleEndedIterator for RChunksExactMut<'a, T> {
3158 fn next_back(&mut self) -> Option<&'a mut [T]> {
3159 if self.v.len() < self.chunk_size {
3162 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3163 let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) };
3165 // SAFETY: Nothing else points to or will point to the contents of this slice.
3166 Some(unsafe { &mut *head })
3171 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
3172 let len = self.len();
3177 // now that we know that `n` corresponds to a chunk,
3178 // none of these operations can underflow/overflow
3179 let offset = (len - n) * self.chunk_size;
3180 let start = self.v.len() - offset;
3181 let end = start + self.chunk_size;
3182 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3183 let (tmp, tail) = unsafe { self.v.split_at_mut(end) };
3184 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3185 let (_, nth_back) = unsafe { tmp.split_at_mut(start) };
3187 // SAFETY: Nothing else points to or will point to the contents of this slice.
3188 Some(unsafe { &mut *nth_back })
3193 #[stable(feature = "rchunks", since = "1.31.0")]
3194 impl<T> ExactSizeIterator for RChunksExactMut<'_, T> {
3195 fn is_empty(&self) -> bool {
3200 #[unstable(feature = "trusted_len", issue = "37572")]
3201 unsafe impl<T> TrustedLen for RChunksExactMut<'_, T> {}
3203 #[stable(feature = "rchunks", since = "1.31.0")]
3204 impl<T> FusedIterator for RChunksExactMut<'_, T> {}
3207 #[unstable(feature = "trusted_random_access", issue = "none")]
3208 unsafe impl<'a, T> TrustedRandomAccess for RChunksExactMut<'a, T> {}
3211 #[unstable(feature = "trusted_random_access", issue = "none")]
3212 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExactMut<'a, T> {
3213 const MAY_HAVE_SIDE_EFFECT: bool = false;
3216 #[stable(feature = "rchunks", since = "1.31.0")]
3217 unsafe impl<T> Send for RChunksExactMut<'_, T> where T: Send {}
3219 #[stable(feature = "rchunks", since = "1.31.0")]
3220 unsafe impl<T> Sync for RChunksExactMut<'_, T> where T: Sync {}
3223 #[unstable(feature = "trusted_random_access", issue = "none")]
3224 unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {}
3227 #[unstable(feature = "trusted_random_access", issue = "none")]
3228 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Iter<'a, T> {
3229 const MAY_HAVE_SIDE_EFFECT: bool = false;
3233 #[unstable(feature = "trusted_random_access", issue = "none")]
3234 unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {}
3237 #[unstable(feature = "trusted_random_access", issue = "none")]
3238 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for IterMut<'a, T> {
3239 const MAY_HAVE_SIDE_EFFECT: bool = false;
3242 /// An iterator over slice in (non-overlapping) chunks separated by a predicate.
3244 /// This struct is created by the [`group_by`] method on [slices].
3246 /// [`group_by`]: slice::group_by
3248 #[unstable(feature = "slice_group_by", issue = "80552")]
3249 #[must_use = "iterators are lazy and do nothing unless consumed"]
3250 pub struct GroupBy<'a, T: 'a, P> {
3255 #[unstable(feature = "slice_group_by", issue = "80552")]
3256 impl<'a, T: 'a, P> GroupBy<'a, T, P> {
3257 pub(super) fn new(slice: &'a [T], predicate: P) -> Self {
3258 GroupBy { slice, predicate }
3262 #[unstable(feature = "slice_group_by", issue = "80552")]
3263 impl<'a, T: 'a, P> Iterator for GroupBy<'a, T, P>
3265 P: FnMut(&T, &T) -> bool,
3267 type Item = &'a [T];
3270 fn next(&mut self) -> Option<Self::Item> {
3271 if self.slice.is_empty() {
3275 let mut iter = self.slice.windows(2);
3276 while let Some([l, r]) = iter.next() {
3277 if (self.predicate)(l, r) { len += 1 } else { break }
3279 let (head, tail) = self.slice.split_at(len);
3286 fn size_hint(&self) -> (usize, Option<usize>) {
3287 if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
3291 fn last(mut self) -> Option<Self::Item> {
3296 #[unstable(feature = "slice_group_by", issue = "80552")]
3297 impl<'a, T: 'a, P> DoubleEndedIterator for GroupBy<'a, T, P>
3299 P: FnMut(&T, &T) -> bool,
3302 fn next_back(&mut self) -> Option<Self::Item> {
3303 if self.slice.is_empty() {
3307 let mut iter = self.slice.windows(2);
3308 while let Some([l, r]) = iter.next_back() {
3309 if (self.predicate)(l, r) { len += 1 } else { break }
3311 let (head, tail) = self.slice.split_at(self.slice.len() - len);
3318 #[unstable(feature = "slice_group_by", issue = "80552")]
3319 impl<'a, T: 'a, P> FusedIterator for GroupBy<'a, T, P> where P: FnMut(&T, &T) -> bool {}
3321 #[unstable(feature = "slice_group_by", issue = "80552")]
3322 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for GroupBy<'a, T, P> {
3323 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3324 f.debug_struct("GroupBy").field("slice", &self.slice).finish()
3328 /// An iterator over slice in (non-overlapping) mutable chunks separated
3331 /// This struct is created by the [`group_by_mut`] method on [slices].
3333 /// [`group_by_mut`]: slice::group_by_mut
3335 #[unstable(feature = "slice_group_by", issue = "80552")]
3336 #[must_use = "iterators are lazy and do nothing unless consumed"]
3337 pub struct GroupByMut<'a, T: 'a, P> {
3342 #[unstable(feature = "slice_group_by", issue = "80552")]
3343 impl<'a, T: 'a, P> GroupByMut<'a, T, P> {
3344 pub(super) fn new(slice: &'a mut [T], predicate: P) -> Self {
3345 GroupByMut { slice, predicate }
3349 #[unstable(feature = "slice_group_by", issue = "80552")]
3350 impl<'a, T: 'a, P> Iterator for GroupByMut<'a, T, P>
3352 P: FnMut(&T, &T) -> bool,
3354 type Item = &'a mut [T];
3357 fn next(&mut self) -> Option<Self::Item> {
3358 if self.slice.is_empty() {
3362 let mut iter = self.slice.windows(2);
3363 while let Some([l, r]) = iter.next() {
3364 if (self.predicate)(l, r) { len += 1 } else { break }
3366 let slice = mem::take(&mut self.slice);
3367 let (head, tail) = slice.split_at_mut(len);
3374 fn size_hint(&self) -> (usize, Option<usize>) {
3375 if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
3379 fn last(mut self) -> Option<Self::Item> {
3384 #[unstable(feature = "slice_group_by", issue = "80552")]
3385 impl<'a, T: 'a, P> DoubleEndedIterator for GroupByMut<'a, T, P>
3387 P: FnMut(&T, &T) -> bool,
3390 fn next_back(&mut self) -> Option<Self::Item> {
3391 if self.slice.is_empty() {
3395 let mut iter = self.slice.windows(2);
3396 while let Some([l, r]) = iter.next_back() {
3397 if (self.predicate)(l, r) { len += 1 } else { break }
3399 let slice = mem::take(&mut self.slice);
3400 let (head, tail) = slice.split_at_mut(slice.len() - len);
3407 #[unstable(feature = "slice_group_by", issue = "80552")]
3408 impl<'a, T: 'a, P> FusedIterator for GroupByMut<'a, T, P> where P: FnMut(&T, &T) -> bool {}
3410 #[unstable(feature = "slice_group_by", issue = "80552")]
3411 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for GroupByMut<'a, T, P> {
3412 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3413 f.debug_struct("GroupByMut").field("slice", &self.slice).finish()