1//! Definitions of a bunch of iterators for `[T]`.
2
3#[macro_use] // import iterator! and forward_iterator!
4mod macros;
5
6use super::{from_raw_parts, from_raw_parts_mut};
7use crate::hint::assert_unchecked;
8use crate::iter::{
9 FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, UncheckedIterator,
10};
11use crate::marker::PhantomData;
12use crate::mem::{self, SizedTypeProperties};
13use crate::num::NonZero;
14use crate::ptr::{NonNull, without_provenance, without_provenance_mut};
15use crate::{cmp, fmt};
16
17#[stable(feature = "boxed_slice_into_iter", since = "1.80.0")]
18impl<T> !Iterator for [T] {}
19
20#[stable(feature = "rust1", since = "1.0.0")]
21impl<'a, T> IntoIterator for &'a [T] {
22 type Item = &'a T;
23 type IntoIter = Iter<'a, T>;
24
25 fn into_iter(self) -> Iter<'a, T> {
26 self.iter()
27 }
28}
29
30#[stable(feature = "rust1", since = "1.0.0")]
31impl<'a, T> IntoIterator for &'a mut [T] {
32 type Item = &'a mut T;
33 type IntoIter = IterMut<'a, T>;
34
35 fn into_iter(self) -> IterMut<'a, T> {
36 self.iter_mut()
37 }
38}
39
40/// Immutable slice iterator
41///
42/// This struct is created by the [`iter`] method on [slices].
43///
44/// # Examples
45///
46/// Basic usage:
47///
48/// ```
49/// // First, we need a slice to call the `iter` method on:
50/// let slice = &[1, 2, 3];
51///
52/// // Then we call `iter` on the slice to get the `Iter` iterator,
53/// // and iterate over it:
54/// for element in slice.iter() {
55/// println!("{element}");
56/// }
57///
58/// // This for loop actually already works without calling `iter`:
59/// for element in slice {
60/// println!("{element}");
61/// }
62/// ```
63///
64/// [`iter`]: slice::iter
65/// [slices]: slice
66#[stable(feature = "rust1", since = "1.0.0")]
67#[must_use = "iterators are lazy and do nothing unless consumed"]
68#[rustc_diagnostic_item = "SliceIter"]
69pub struct Iter<'a, T: 'a> {
70 /// The pointer to the next element to return, or the past-the-end location
71 /// if the iterator is empty.
72 ///
73 /// This address will be used for all ZST elements, never changed.
74 ptr: NonNull<T>,
75 /// For non-ZSTs, the non-null pointer to the past-the-end element.
76 ///
77 /// For ZSTs, this is `ptr::without_provenance_mut(len)`.
78 end_or_len: *const T,
79 _marker: PhantomData<&'a T>,
80}
81
82#[stable(feature = "core_impl_debug", since = "1.9.0")]
83impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
84 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
85 f.debug_tuple(name:"Iter").field(&self.as_slice()).finish()
86 }
87}
88
89#[stable(feature = "rust1", since = "1.0.0")]
90unsafe impl<T: Sync> Sync for Iter<'_, T> {}
91#[stable(feature = "rust1", since = "1.0.0")]
92unsafe impl<T: Sync> Send for Iter<'_, T> {}
93
94impl<'a, T> Iter<'a, T> {
95 #[inline]
96 pub(super) fn new(slice: &'a [T]) -> Self {
97 let len = slice.len();
98 let ptr: NonNull<T> = NonNull::from(slice).cast();
99 // SAFETY: Similar to `IterMut::new`.
100 unsafe {
101 let end_or_len =
102 if T::IS_ZST { without_provenance(len) } else { ptr.as_ptr().add(len) };
103
104 Self { ptr, end_or_len, _marker: PhantomData }
105 }
106 }
107
108 /// Views the underlying data as a subslice of the original data.
109 ///
110 /// # Examples
111 ///
112 /// Basic usage:
113 ///
114 /// ```
115 /// // First, we need a slice to call the `iter` method on:
116 /// let slice = &[1, 2, 3];
117 ///
118 /// // Then we call `iter` on the slice to get the `Iter` iterator:
119 /// let mut iter = slice.iter();
120 /// // Here `as_slice` still returns the whole slice, so this prints "[1, 2, 3]":
121 /// println!("{:?}", iter.as_slice());
122 ///
123 /// // Now, we call the `next` method to remove the first element from the iterator:
124 /// iter.next();
125 /// // Here the iterator does not contain the first element of the slice any more,
126 /// // so `as_slice` only returns the last two elements of the slice,
127 /// // and so this prints "[2, 3]":
128 /// println!("{:?}", iter.as_slice());
129 ///
130 /// // The underlying slice has not been modified and still contains three elements,
131 /// // so this prints "[1, 2, 3]":
132 /// println!("{:?}", slice);
133 /// ```
134 #[must_use]
135 #[stable(feature = "iter_to_slice", since = "1.4.0")]
136 #[inline]
137 pub fn as_slice(&self) -> &'a [T] {
138 self.make_slice()
139 }
140}
141
142iterator! {struct Iter -> *const T, &'a T, const, {/* no mut */}, as_ref, {
143 fn is_sorted_by<F>(self, mut compare: F) -> bool
144 where
145 Self: Sized,
146 F: FnMut(&Self::Item, &Self::Item) -> bool,
147 {
148 self.as_slice().is_sorted_by(|a, b| compare(&a, &b))
149 }
150}}
151
152#[stable(feature = "rust1", since = "1.0.0")]
153impl<T> Clone for Iter<'_, T> {
154 #[inline]
155 fn clone(&self) -> Self {
156 Iter { ptr: self.ptr, end_or_len: self.end_or_len, _marker: self._marker }
157 }
158}
159
160#[stable(feature = "slice_iter_as_ref", since = "1.13.0")]
161impl<T> AsRef<[T]> for Iter<'_, T> {
162 #[inline]
163 fn as_ref(&self) -> &[T] {
164 self.as_slice()
165 }
166}
167
168/// Mutable slice iterator.
169///
170/// This struct is created by the [`iter_mut`] method on [slices].
171///
172/// # Examples
173///
174/// Basic usage:
175///
176/// ```
177/// // First, we need a slice to call the `iter_mut` method on:
178/// let slice = &mut [1, 2, 3];
179///
180/// // Then we call `iter_mut` on the slice to get the `IterMut` iterator,
181/// // iterate over it and increment each element value:
182/// for element in slice.iter_mut() {
183/// *element += 1;
184/// }
185///
186/// // We now have "[2, 3, 4]":
187/// println!("{slice:?}");
188/// ```
189///
190/// [`iter_mut`]: slice::iter_mut
191/// [slices]: slice
192#[stable(feature = "rust1", since = "1.0.0")]
193#[must_use = "iterators are lazy and do nothing unless consumed"]
194pub struct IterMut<'a, T: 'a> {
195 /// The pointer to the next element to return, or the past-the-end location
196 /// if the iterator is empty.
197 ///
198 /// This address will be used for all ZST elements, never changed.
199 ptr: NonNull<T>,
200 /// For non-ZSTs, the non-null pointer to the past-the-end element.
201 ///
202 /// For ZSTs, this is `ptr::without_provenance_mut(len)`.
203 end_or_len: *mut T,
204 _marker: PhantomData<&'a mut T>,
205}
206
207#[stable(feature = "core_impl_debug", since = "1.9.0")]
208impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
209 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
210 f.debug_tuple(name:"IterMut").field(&self.make_slice()).finish()
211 }
212}
213
214#[stable(feature = "rust1", since = "1.0.0")]
215unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
216#[stable(feature = "rust1", since = "1.0.0")]
217unsafe impl<T: Send> Send for IterMut<'_, T> {}
218
219impl<'a, T> IterMut<'a, T> {
220 #[inline]
221 pub(super) fn new(slice: &'a mut [T]) -> Self {
222 let len = slice.len();
223 let ptr: NonNull<T> = NonNull::from(slice).cast();
224 // SAFETY: There are several things here:
225 //
226 // `ptr` has been obtained by `slice.as_ptr()` where `slice` is a valid
227 // reference thus it is non-NUL and safe to use and pass to
228 // `NonNull::new_unchecked` .
229 //
230 // Adding `slice.len()` to the starting pointer gives a pointer
231 // at the end of `slice`. `end` will never be dereferenced, only checked
232 // for direct pointer equality with `ptr` to check if the iterator is
233 // done.
234 //
235 // In the case of a ZST, the end pointer is just the length. It's never
236 // used as a pointer at all, and thus it's fine to have no provenance.
237 //
238 // See the `next_unchecked!` and `is_empty!` macros as well as the
239 // `post_inc_start` method for more information.
240 unsafe {
241 let end_or_len =
242 if T::IS_ZST { without_provenance_mut(len) } else { ptr.as_ptr().add(len) };
243
244 Self { ptr, end_or_len, _marker: PhantomData }
245 }
246 }
247
248 /// Views the underlying data as a subslice of the original data.
249 ///
250 /// To avoid creating `&mut` references that alias, this is forced
251 /// to consume the iterator.
252 ///
253 /// # Examples
254 ///
255 /// Basic usage:
256 ///
257 /// ```
258 /// // First, we need a slice to call the `iter_mut` method on:
259 /// let mut slice = &mut [1, 2, 3];
260 ///
261 /// // Then we call `iter_mut` on the slice to get the `IterMut` struct:
262 /// let mut iter = slice.iter_mut();
263 /// // Now, we call the `next` method to remove the first element of the iterator,
264 /// // unwrap and dereference what we get from `next` and increase its value by 1:
265 /// *iter.next().unwrap() += 1;
266 /// // Here the iterator does not contain the first element of the slice any more,
267 /// // so `into_slice` only returns the last two elements of the slice,
268 /// // and so this prints "[2, 3]":
269 /// println!("{:?}", iter.into_slice());
270 /// // The underlying slice still contains three elements, but its first element
271 /// // was increased by 1, so this prints "[2, 2, 3]":
272 /// println!("{:?}", slice);
273 /// ```
274 #[must_use = "`self` will be dropped if the result is not used"]
275 #[stable(feature = "iter_to_slice", since = "1.4.0")]
276 pub fn into_slice(self) -> &'a mut [T] {
277 // SAFETY: the iterator was created from a mutable slice with pointer
278 // `self.ptr` and length `len!(self)`. This guarantees that all the prerequisites
279 // for `from_raw_parts_mut` are fulfilled.
280 unsafe { from_raw_parts_mut(self.ptr.as_ptr(), len!(self)) }
281 }
282
283 /// Views the underlying data as a subslice of the original data.
284 ///
285 /// # Examples
286 ///
287 /// Basic usage:
288 ///
289 /// ```
290 /// // First, we need a slice to call the `iter_mut` method on:
291 /// let slice = &mut [1, 2, 3];
292 ///
293 /// // Then we call `iter_mut` on the slice to get the `IterMut` iterator:
294 /// let mut iter = slice.iter_mut();
295 /// // Here `as_slice` still returns the whole slice, so this prints "[1, 2, 3]":
296 /// println!("{:?}", iter.as_slice());
297 ///
298 /// // Now, we call the `next` method to remove the first element from the iterator
299 /// // and increment its value:
300 /// *iter.next().unwrap() += 1;
301 /// // Here the iterator does not contain the first element of the slice any more,
302 /// // so `as_slice` only returns the last two elements of the slice,
303 /// // and so this prints "[2, 3]":
304 /// println!("{:?}", iter.as_slice());
305 ///
306 /// // The underlying slice still contains three elements, but its first element
307 /// // was increased by 1, so this prints "[2, 2, 3]":
308 /// println!("{:?}", slice);
309 /// ```
310 #[must_use]
311 #[stable(feature = "slice_iter_mut_as_slice", since = "1.53.0")]
312 #[inline]
313 pub fn as_slice(&self) -> &[T] {
314 self.make_slice()
315 }
316
317 /// Views the underlying data as a mutable subslice of the original data.
318 ///
319 /// # Examples
320 ///
321 /// Basic usage:
322 ///
323 /// ```
324 /// #![feature(slice_iter_mut_as_mut_slice)]
325 ///
326 /// let mut slice: &mut [usize] = &mut [1, 2, 3];
327 ///
328 /// // First, we get the iterator:
329 /// let mut iter = slice.iter_mut();
330 /// // Then, we get a mutable slice from it:
331 /// let mut_slice = iter.as_mut_slice();
332 /// // So if we check what the `as_mut_slice` method returned, we have "[1, 2, 3]":
333 /// assert_eq!(mut_slice, &mut [1, 2, 3]);
334 ///
335 /// // We can use it to mutate the slice:
336 /// mut_slice[0] = 4;
337 /// mut_slice[2] = 5;
338 ///
339 /// // Next, we can move to the second element of the slice, checking that
340 /// // it yields the value we just wrote:
341 /// assert_eq!(iter.next(), Some(&mut 4));
342 /// // Now `as_mut_slice` returns "[2, 5]":
343 /// assert_eq!(iter.as_mut_slice(), &mut [2, 5]);
344 /// ```
345 #[must_use]
346 // FIXME: Uncomment the `AsMut<[T]>` impl when this gets stabilized.
347 #[unstable(feature = "slice_iter_mut_as_mut_slice", issue = "93079")]
348 pub fn as_mut_slice(&mut self) -> &mut [T] {
349 // SAFETY: the iterator was created from a mutable slice with pointer
350 // `self.ptr` and length `len!(self)`. This guarantees that all the prerequisites
351 // for `from_raw_parts_mut` are fulfilled.
352 unsafe { from_raw_parts_mut(self.ptr.as_ptr(), len!(self)) }
353 }
354}
355
356#[stable(feature = "slice_iter_mut_as_slice", since = "1.53.0")]
357impl<T> AsRef<[T]> for IterMut<'_, T> {
358 #[inline]
359 fn as_ref(&self) -> &[T] {
360 self.as_slice()
361 }
362}
363
364// #[stable(feature = "slice_iter_mut_as_mut_slice", since = "FIXME")]
365// impl<T> AsMut<[T]> for IterMut<'_, T> {
366// fn as_mut(&mut self) -> &mut [T] {
367// self.as_mut_slice()
368// }
369// }
370
371iterator! {struct IterMut -> *mut T, &'a mut T, mut, {mut}, as_mut, {}}
372
373/// An internal abstraction over the splitting iterators, so that
374/// splitn, splitn_mut etc can be implemented once.
375#[doc(hidden)]
376pub(super) trait SplitIter: DoubleEndedIterator {
377 /// Marks the underlying iterator as complete, extracting the remaining
378 /// portion of the slice.
379 fn finish(&mut self) -> Option<Self::Item>;
380}
381
382/// An iterator over subslices separated by elements that match a predicate
383/// function.
384///
385/// This struct is created by the [`split`] method on [slices].
386///
387/// # Example
388///
389/// ```
390/// let slice = [10, 40, 33, 20];
391/// let mut iter = slice.split(|num| num % 3 == 0);
392/// assert_eq!(iter.next(), Some(&[10, 40][..]));
393/// assert_eq!(iter.next(), Some(&[20][..]));
394/// assert_eq!(iter.next(), None);
395/// ```
396///
397/// [`split`]: slice::split
398/// [slices]: slice
399#[stable(feature = "rust1", since = "1.0.0")]
400#[must_use = "iterators are lazy and do nothing unless consumed"]
401pub struct Split<'a, T: 'a, P>
402where
403 P: FnMut(&T) -> bool,
404{
405 // Used for `SplitWhitespace` and `SplitAsciiWhitespace` `as_str` methods
406 pub(crate) v: &'a [T],
407 pred: P,
408 // Used for `SplitAsciiWhitespace` `as_str` method
409 pub(crate) finished: bool,
410}
411
412impl<'a, T: 'a, P: FnMut(&T) -> bool> Split<'a, T, P> {
413 #[inline]
414 pub(super) fn new(slice: &'a [T], pred: P) -> Self {
415 Self { v: slice, pred, finished: false }
416 }
417 /// Returns a slice which contains items not yet handled by split.
418 /// # Example
419 ///
420 /// ```
421 /// #![feature(split_as_slice)]
422 /// let slice = [1,2,3,4,5];
423 /// let mut split = slice.split(|v| v % 2 == 0);
424 /// assert!(split.next().is_some());
425 /// assert_eq!(split.as_slice(), &[3,4,5]);
426 /// ```
427 #[unstable(feature = "split_as_slice", issue = "96137")]
428 pub fn as_slice(&self) -> &'a [T] {
429 if self.finished { &[] } else { &self.v }
430 }
431}
432
433#[stable(feature = "core_impl_debug", since = "1.9.0")]
434impl<T: fmt::Debug, P> fmt::Debug for Split<'_, T, P>
435where
436 P: FnMut(&T) -> bool,
437{
438 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
439 f.debug_struct("Split").field("v", &self.v).field(name:"finished", &self.finished).finish()
440 }
441}
442
443// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
444#[stable(feature = "rust1", since = "1.0.0")]
445impl<T, P> Clone for Split<'_, T, P>
446where
447 P: Clone + FnMut(&T) -> bool,
448{
449 fn clone(&self) -> Self {
450 Split { v: self.v, pred: self.pred.clone(), finished: self.finished }
451 }
452}
453
454#[stable(feature = "rust1", since = "1.0.0")]
455impl<'a, T, P> Iterator for Split<'a, T, P>
456where
457 P: FnMut(&T) -> bool,
458{
459 type Item = &'a [T];
460
461 #[inline]
462 fn next(&mut self) -> Option<&'a [T]> {
463 if self.finished {
464 return None;
465 }
466
467 match self.v.iter().position(|x| (self.pred)(x)) {
468 None => self.finish(),
469 Some(idx) => {
470 let (left, right) =
471 // SAFETY: if v.iter().position returns Some(idx), that
472 // idx is definitely a valid index for v
473 unsafe { (self.v.get_unchecked(..idx), self.v.get_unchecked(idx + 1..)) };
474 let ret = Some(left);
475 self.v = right;
476 ret
477 }
478 }
479 }
480
481 #[inline]
482 fn size_hint(&self) -> (usize, Option<usize>) {
483 if self.finished {
484 (0, Some(0))
485 } else {
486 // If the predicate doesn't match anything, we yield one slice.
487 // If it matches every element, we yield `len() + 1` empty slices.
488 (1, Some(self.v.len() + 1))
489 }
490 }
491}
492
493#[stable(feature = "rust1", since = "1.0.0")]
494impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P>
495where
496 P: FnMut(&T) -> bool,
497{
498 #[inline]
499 fn next_back(&mut self) -> Option<&'a [T]> {
500 if self.finished {
501 return None;
502 }
503
504 match self.v.iter().rposition(|x: &T| (self.pred)(x)) {
505 None => self.finish(),
506 Some(idx: usize) => {
507 let (left: &[T], right: &[T]) =
508 // SAFETY: if v.iter().rposition returns Some(idx), then
509 // idx is definitely a valid index for v
510 unsafe { (self.v.get_unchecked(..idx), self.v.get_unchecked(index:idx + 1..)) };
511 let ret: Option<&[T]> = Some(right);
512 self.v = left;
513 ret
514 }
515 }
516 }
517}
518
519impl<'a, T, P> SplitIter for Split<'a, T, P>
520where
521 P: FnMut(&T) -> bool,
522{
523 #[inline]
524 fn finish(&mut self) -> Option<&'a [T]> {
525 if self.finished {
526 None
527 } else {
528 self.finished = true;
529 Some(self.v)
530 }
531 }
532}
533
534#[stable(feature = "fused", since = "1.26.0")]
535impl<T, P> FusedIterator for Split<'_, T, P> where P: FnMut(&T) -> bool {}
536
537/// An iterator over subslices separated by elements that match a predicate
538/// function. Unlike `Split`, it contains the matched part as a terminator
539/// of the subslice.
540///
541/// This struct is created by the [`split_inclusive`] method on [slices].
542///
543/// # Example
544///
545/// ```
546/// let slice = [10, 40, 33, 20];
547/// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
548/// assert_eq!(iter.next(), Some(&[10, 40, 33][..]));
549/// assert_eq!(iter.next(), Some(&[20][..]));
550/// assert_eq!(iter.next(), None);
551/// ```
552///
553/// [`split_inclusive`]: slice::split_inclusive
554/// [slices]: slice
555#[stable(feature = "split_inclusive", since = "1.51.0")]
556#[must_use = "iterators are lazy and do nothing unless consumed"]
557pub struct SplitInclusive<'a, T: 'a, P>
558where
559 P: FnMut(&T) -> bool,
560{
561 v: &'a [T],
562 pred: P,
563 finished: bool,
564}
565
566impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitInclusive<'a, T, P> {
567 #[inline]
568 pub(super) fn new(slice: &'a [T], pred: P) -> Self {
569 let finished: bool = slice.is_empty();
570 Self { v: slice, pred, finished }
571 }
572}
573
574#[stable(feature = "split_inclusive", since = "1.51.0")]
575impl<T: fmt::Debug, P> fmt::Debug for SplitInclusive<'_, T, P>
576where
577 P: FnMut(&T) -> bool,
578{
579 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
580 f&mut DebugStruct<'_, '_>.debug_struct("SplitInclusive")
581 .field("v", &self.v)
582 .field(name:"finished", &self.finished)
583 .finish()
584 }
585}
586
587// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
588#[stable(feature = "split_inclusive", since = "1.51.0")]
589impl<T, P> Clone for SplitInclusive<'_, T, P>
590where
591 P: Clone + FnMut(&T) -> bool,
592{
593 fn clone(&self) -> Self {
594 SplitInclusive { v: self.v, pred: self.pred.clone(), finished: self.finished }
595 }
596}
597
598#[stable(feature = "split_inclusive", since = "1.51.0")]
599impl<'a, T, P> Iterator for SplitInclusive<'a, T, P>
600where
601 P: FnMut(&T) -> bool,
602{
603 type Item = &'a [T];
604
605 #[inline]
606 fn next(&mut self) -> Option<&'a [T]> {
607 if self.finished {
608 return None;
609 }
610
611 let idx =
612 self.v.iter().position(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(self.v.len());
613 if idx == self.v.len() {
614 self.finished = true;
615 }
616 let ret = Some(&self.v[..idx]);
617 self.v = &self.v[idx..];
618 ret
619 }
620
621 #[inline]
622 fn size_hint(&self) -> (usize, Option<usize>) {
623 if self.finished {
624 (0, Some(0))
625 } else {
626 // If the predicate doesn't match anything, we yield one slice.
627 // If it matches every element, we yield `len()` one-element slices,
628 // or a single empty slice.
629 (1, Some(cmp::max(1, self.v.len())))
630 }
631 }
632}
633
634#[stable(feature = "split_inclusive", since = "1.51.0")]
635impl<'a, T, P> DoubleEndedIterator for SplitInclusive<'a, T, P>
636where
637 P: FnMut(&T) -> bool,
638{
639 #[inline]
640 fn next_back(&mut self) -> Option<&'a [T]> {
641 if self.finished {
642 return None;
643 }
644
645 // The last index of self.v is already checked and found to match
646 // by the last iteration, so we start searching a new match
647 // one index to the left.
648 let remainder: &[T] = if self.v.is_empty() { &[] } else { &self.v[..(self.v.len() - 1)] };
649 let idx: usize = remainder.iter().rposition(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(default:0);
650 if idx == 0 {
651 self.finished = true;
652 }
653 let ret: Option<&[T]> = Some(&self.v[idx..]);
654 self.v = &self.v[..idx];
655 ret
656 }
657}
658
659#[stable(feature = "split_inclusive", since = "1.51.0")]
660impl<T, P> FusedIterator for SplitInclusive<'_, T, P> where P: FnMut(&T) -> bool {}
661
662/// An iterator over the mutable subslices of the vector which are separated
663/// by elements that match `pred`.
664///
665/// This struct is created by the [`split_mut`] method on [slices].
666///
667/// # Example
668///
669/// ```
670/// let mut v = [10, 40, 30, 20, 60, 50];
671/// let iter = v.split_mut(|num| *num % 3 == 0);
672/// ```
673///
674/// [`split_mut`]: slice::split_mut
675/// [slices]: slice
676#[stable(feature = "rust1", since = "1.0.0")]
677#[must_use = "iterators are lazy and do nothing unless consumed"]
678pub struct SplitMut<'a, T: 'a, P>
679where
680 P: FnMut(&T) -> bool,
681{
682 v: &'a mut [T],
683 pred: P,
684 finished: bool,
685}
686
687impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitMut<'a, T, P> {
688 #[inline]
689 pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
690 Self { v: slice, pred, finished: false }
691 }
692}
693
694#[stable(feature = "core_impl_debug", since = "1.9.0")]
695impl<T: fmt::Debug, P> fmt::Debug for SplitMut<'_, T, P>
696where
697 P: FnMut(&T) -> bool,
698{
699 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
700 f.debug_struct("SplitMut").field("v", &self.v).field(name:"finished", &self.finished).finish()
701 }
702}
703
704impl<'a, T, P> SplitIter for SplitMut<'a, T, P>
705where
706 P: FnMut(&T) -> bool,
707{
708 #[inline]
709 fn finish(&mut self) -> Option<&'a mut [T]> {
710 if self.finished {
711 None
712 } else {
713 self.finished = true;
714 Some(mem::take(&mut self.v))
715 }
716 }
717}
718
719#[stable(feature = "rust1", since = "1.0.0")]
720impl<'a, T, P> Iterator for SplitMut<'a, T, P>
721where
722 P: FnMut(&T) -> bool,
723{
724 type Item = &'a mut [T];
725
726 #[inline]
727 fn next(&mut self) -> Option<&'a mut [T]> {
728 if self.finished {
729 return None;
730 }
731
732 match self.v.iter().position(|x| (self.pred)(x)) {
733 None => self.finish(),
734 Some(idx) => {
735 let tmp = mem::take(&mut self.v);
736 // idx is the index of the element we are splitting on. We want to set self to the
737 // region after idx, and return the subslice before and not including idx.
738 // So first we split after idx
739 let (head, tail) = tmp.split_at_mut(idx + 1);
740 self.v = tail;
741 // Then return the subslice up to but not including the found element
742 Some(&mut head[..idx])
743 }
744 }
745 }
746
747 #[inline]
748 fn size_hint(&self) -> (usize, Option<usize>) {
749 if self.finished {
750 (0, Some(0))
751 } else {
752 // If the predicate doesn't match anything, we yield one slice.
753 // If it matches every element, we yield `len() + 1` empty slices.
754 (1, Some(self.v.len() + 1))
755 }
756 }
757}
758
759#[stable(feature = "rust1", since = "1.0.0")]
760impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P>
761where
762 P: FnMut(&T) -> bool,
763{
764 #[inline]
765 fn next_back(&mut self) -> Option<&'a mut [T]> {
766 if self.finished {
767 return None;
768 }
769
770 let idx_opt: Option = {
771 // work around borrowck limitations
772 let pred: &mut P = &mut self.pred;
773 self.v.iter().rposition(|x: &T| (*pred)(x))
774 };
775 match idx_opt {
776 None => self.finish(),
777 Some(idx: usize) => {
778 let tmp: &'a mut [T] = mem::take(&mut self.v);
779 let (head: &mut [T], tail: &mut [T]) = tmp.split_at_mut(mid:idx);
780 self.v = head;
781 Some(&mut tail[1..])
782 }
783 }
784 }
785}
786
787#[stable(feature = "fused", since = "1.26.0")]
788impl<T, P> FusedIterator for SplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
789
790/// An iterator over the mutable subslices of the vector which are separated
791/// by elements that match `pred`. Unlike `SplitMut`, it contains the matched
792/// parts in the ends of the subslices.
793///
794/// This struct is created by the [`split_inclusive_mut`] method on [slices].
795///
796/// # Example
797///
798/// ```
799/// let mut v = [10, 40, 30, 20, 60, 50];
800/// let iter = v.split_inclusive_mut(|num| *num % 3 == 0);
801/// ```
802///
803/// [`split_inclusive_mut`]: slice::split_inclusive_mut
804/// [slices]: slice
805#[stable(feature = "split_inclusive", since = "1.51.0")]
806#[must_use = "iterators are lazy and do nothing unless consumed"]
807pub struct SplitInclusiveMut<'a, T: 'a, P>
808where
809 P: FnMut(&T) -> bool,
810{
811 v: &'a mut [T],
812 pred: P,
813 finished: bool,
814}
815
816impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitInclusiveMut<'a, T, P> {
817 #[inline]
818 pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
819 let finished: bool = slice.is_empty();
820 Self { v: slice, pred, finished }
821 }
822}
823
824#[stable(feature = "split_inclusive", since = "1.51.0")]
825impl<T: fmt::Debug, P> fmt::Debug for SplitInclusiveMut<'_, T, P>
826where
827 P: FnMut(&T) -> bool,
828{
829 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
830 f&mut DebugStruct<'_, '_>.debug_struct("SplitInclusiveMut")
831 .field("v", &self.v)
832 .field(name:"finished", &self.finished)
833 .finish()
834 }
835}
836
837#[stable(feature = "split_inclusive", since = "1.51.0")]
838impl<'a, T, P> Iterator for SplitInclusiveMut<'a, T, P>
839where
840 P: FnMut(&T) -> bool,
841{
842 type Item = &'a mut [T];
843
844 #[inline]
845 fn next(&mut self) -> Option<&'a mut [T]> {
846 if self.finished {
847 return None;
848 }
849
850 let idx_opt = {
851 // work around borrowck limitations
852 let pred = &mut self.pred;
853 self.v.iter().position(|x| (*pred)(x))
854 };
855 let idx = idx_opt.map(|idx| idx + 1).unwrap_or(self.v.len());
856 if idx == self.v.len() {
857 self.finished = true;
858 }
859 let tmp = mem::take(&mut self.v);
860 let (head, tail) = tmp.split_at_mut(idx);
861 self.v = tail;
862 Some(head)
863 }
864
865 #[inline]
866 fn size_hint(&self) -> (usize, Option<usize>) {
867 if self.finished {
868 (0, Some(0))
869 } else {
870 // If the predicate doesn't match anything, we yield one slice.
871 // If it matches every element, we yield `len()` one-element slices,
872 // or a single empty slice.
873 (1, Some(cmp::max(1, self.v.len())))
874 }
875 }
876}
877
878#[stable(feature = "split_inclusive", since = "1.51.0")]
879impl<'a, T, P> DoubleEndedIterator for SplitInclusiveMut<'a, T, P>
880where
881 P: FnMut(&T) -> bool,
882{
883 #[inline]
884 fn next_back(&mut self) -> Option<&'a mut [T]> {
885 if self.finished {
886 return None;
887 }
888
889 let idx_opt = if self.v.is_empty() {
890 None
891 } else {
892 // work around borrowck limitations
893 let pred = &mut self.pred;
894
895 // The last index of self.v is already checked and found to match
896 // by the last iteration, so we start searching a new match
897 // one index to the left.
898 let remainder = &self.v[..(self.v.len() - 1)];
899 remainder.iter().rposition(|x| (*pred)(x))
900 };
901 let idx = idx_opt.map(|idx| idx + 1).unwrap_or(0);
902 if idx == 0 {
903 self.finished = true;
904 }
905 let tmp = mem::take(&mut self.v);
906 let (head, tail) = tmp.split_at_mut(idx);
907 self.v = head;
908 Some(tail)
909 }
910}
911
912#[stable(feature = "split_inclusive", since = "1.51.0")]
913impl<T, P> FusedIterator for SplitInclusiveMut<'_, T, P> where P: FnMut(&T) -> bool {}
914
915/// An iterator over subslices separated by elements that match a predicate
916/// function, starting from the end of the slice.
917///
918/// This struct is created by the [`rsplit`] method on [slices].
919///
920/// # Example
921///
922/// ```
923/// let slice = [11, 22, 33, 0, 44, 55];
924/// let mut iter = slice.rsplit(|num| *num == 0);
925/// assert_eq!(iter.next(), Some(&[44, 55][..]));
926/// assert_eq!(iter.next(), Some(&[11, 22, 33][..]));
927/// assert_eq!(iter.next(), None);
928/// ```
929///
930/// [`rsplit`]: slice::rsplit
931/// [slices]: slice
932#[stable(feature = "slice_rsplit", since = "1.27.0")]
933#[must_use = "iterators are lazy and do nothing unless consumed"]
934pub struct RSplit<'a, T: 'a, P>
935where
936 P: FnMut(&T) -> bool,
937{
938 inner: Split<'a, T, P>,
939}
940
941impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplit<'a, T, P> {
942 #[inline]
943 pub(super) fn new(slice: &'a [T], pred: P) -> Self {
944 Self { inner: Split::new(slice, pred) }
945 }
946}
947
948#[stable(feature = "slice_rsplit", since = "1.27.0")]
949impl<T: fmt::Debug, P> fmt::Debug for RSplit<'_, T, P>
950where
951 P: FnMut(&T) -> bool,
952{
953 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
954 f&mut DebugStruct<'_, '_>.debug_struct("RSplit")
955 .field("v", &self.inner.v)
956 .field(name:"finished", &self.inner.finished)
957 .finish()
958 }
959}
960
961// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
962#[stable(feature = "slice_rsplit", since = "1.27.0")]
963impl<T, P> Clone for RSplit<'_, T, P>
964where
965 P: Clone + FnMut(&T) -> bool,
966{
967 fn clone(&self) -> Self {
968 RSplit { inner: self.inner.clone() }
969 }
970}
971
972#[stable(feature = "slice_rsplit", since = "1.27.0")]
973impl<'a, T, P> Iterator for RSplit<'a, T, P>
974where
975 P: FnMut(&T) -> bool,
976{
977 type Item = &'a [T];
978
979 #[inline]
980 fn next(&mut self) -> Option<&'a [T]> {
981 self.inner.next_back()
982 }
983
984 #[inline]
985 fn size_hint(&self) -> (usize, Option<usize>) {
986 self.inner.size_hint()
987 }
988}
989
990#[stable(feature = "slice_rsplit", since = "1.27.0")]
991impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P>
992where
993 P: FnMut(&T) -> bool,
994{
995 #[inline]
996 fn next_back(&mut self) -> Option<&'a [T]> {
997 self.inner.next()
998 }
999}
1000
1001#[stable(feature = "slice_rsplit", since = "1.27.0")]
1002impl<'a, T, P> SplitIter for RSplit<'a, T, P>
1003where
1004 P: FnMut(&T) -> bool,
1005{
1006 #[inline]
1007 fn finish(&mut self) -> Option<&'a [T]> {
1008 self.inner.finish()
1009 }
1010}
1011
1012#[stable(feature = "slice_rsplit", since = "1.27.0")]
1013impl<T, P> FusedIterator for RSplit<'_, T, P> where P: FnMut(&T) -> bool {}
1014
1015/// An iterator over the subslices of the vector which are separated
1016/// by elements that match `pred`, starting from the end of the slice.
1017///
1018/// This struct is created by the [`rsplit_mut`] method on [slices].
1019///
1020/// # Example
1021///
1022/// ```
1023/// let mut slice = [11, 22, 33, 0, 44, 55];
1024/// let iter = slice.rsplit_mut(|num| *num == 0);
1025/// ```
1026///
1027/// [`rsplit_mut`]: slice::rsplit_mut
1028/// [slices]: slice
1029#[stable(feature = "slice_rsplit", since = "1.27.0")]
1030#[must_use = "iterators are lazy and do nothing unless consumed"]
1031pub struct RSplitMut<'a, T: 'a, P>
1032where
1033 P: FnMut(&T) -> bool,
1034{
1035 inner: SplitMut<'a, T, P>,
1036}
1037
1038impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitMut<'a, T, P> {
1039 #[inline]
1040 pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
1041 Self { inner: SplitMut::new(slice, pred) }
1042 }
1043}
1044
1045#[stable(feature = "slice_rsplit", since = "1.27.0")]
1046impl<T: fmt::Debug, P> fmt::Debug for RSplitMut<'_, T, P>
1047where
1048 P: FnMut(&T) -> bool,
1049{
1050 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1051 f&mut DebugStruct<'_, '_>.debug_struct("RSplitMut")
1052 .field("v", &self.inner.v)
1053 .field(name:"finished", &self.inner.finished)
1054 .finish()
1055 }
1056}
1057
1058#[stable(feature = "slice_rsplit", since = "1.27.0")]
1059impl<'a, T, P> SplitIter for RSplitMut<'a, T, P>
1060where
1061 P: FnMut(&T) -> bool,
1062{
1063 #[inline]
1064 fn finish(&mut self) -> Option<&'a mut [T]> {
1065 self.inner.finish()
1066 }
1067}
1068
1069#[stable(feature = "slice_rsplit", since = "1.27.0")]
1070impl<'a, T, P> Iterator for RSplitMut<'a, T, P>
1071where
1072 P: FnMut(&T) -> bool,
1073{
1074 type Item = &'a mut [T];
1075
1076 #[inline]
1077 fn next(&mut self) -> Option<&'a mut [T]> {
1078 self.inner.next_back()
1079 }
1080
1081 #[inline]
1082 fn size_hint(&self) -> (usize, Option<usize>) {
1083 self.inner.size_hint()
1084 }
1085}
1086
1087#[stable(feature = "slice_rsplit", since = "1.27.0")]
1088impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P>
1089where
1090 P: FnMut(&T) -> bool,
1091{
1092 #[inline]
1093 fn next_back(&mut self) -> Option<&'a mut [T]> {
1094 self.inner.next()
1095 }
1096}
1097
1098#[stable(feature = "slice_rsplit", since = "1.27.0")]
1099impl<T, P> FusedIterator for RSplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
1100
1101/// An private iterator over subslices separated by elements that
1102/// match a predicate function, splitting at most a fixed number of
1103/// times.
1104#[derive(Debug)]
1105struct GenericSplitN<I> {
1106 iter: I,
1107 count: usize,
1108}
1109
1110impl<T, I: SplitIter<Item = T>> Iterator for GenericSplitN<I> {
1111 type Item = T;
1112
1113 #[inline]
1114 fn next(&mut self) -> Option<T> {
1115 match self.count {
1116 0 => None,
1117 1 => {
1118 self.count -= 1;
1119 self.iter.finish()
1120 }
1121 _ => {
1122 self.count -= 1;
1123 self.iter.next()
1124 }
1125 }
1126 }
1127
1128 #[inline]
1129 fn size_hint(&self) -> (usize, Option<usize>) {
1130 let (lower, upper_opt) = self.iter.size_hint();
1131 (
1132 cmp::min(self.count, lower),
1133 Some(upper_opt.map_or(self.count, |upper| cmp::min(self.count, upper))),
1134 )
1135 }
1136}
1137
1138/// An iterator over subslices separated by elements that match a predicate
1139/// function, limited to a given number of splits.
1140///
1141/// This struct is created by the [`splitn`] method on [slices].
1142///
1143/// # Example
1144///
1145/// ```
1146/// let slice = [10, 40, 30, 20, 60, 50];
1147/// let mut iter = slice.splitn(2, |num| *num % 3 == 0);
1148/// assert_eq!(iter.next(), Some(&[10, 40][..]));
1149/// assert_eq!(iter.next(), Some(&[20, 60, 50][..]));
1150/// assert_eq!(iter.next(), None);
1151/// ```
1152///
1153/// [`splitn`]: slice::splitn
1154/// [slices]: slice
1155#[stable(feature = "rust1", since = "1.0.0")]
1156#[must_use = "iterators are lazy and do nothing unless consumed"]
1157pub struct SplitN<'a, T: 'a, P>
1158where
1159 P: FnMut(&T) -> bool,
1160{
1161 inner: GenericSplitN<Split<'a, T, P>>,
1162}
1163
1164impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitN<'a, T, P> {
1165 #[inline]
1166 pub(super) fn new(s: Split<'a, T, P>, n: usize) -> Self {
1167 Self { inner: GenericSplitN { iter: s, count: n } }
1168 }
1169}
1170
1171#[stable(feature = "core_impl_debug", since = "1.9.0")]
1172impl<T: fmt::Debug, P> fmt::Debug for SplitN<'_, T, P>
1173where
1174 P: FnMut(&T) -> bool,
1175{
1176 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1177 f.debug_struct("SplitN").field(name:"inner", &self.inner).finish()
1178 }
1179}
1180
1181/// An iterator over subslices separated by elements that match a
1182/// predicate function, limited to a given number of splits, starting
1183/// from the end of the slice.
1184///
1185/// This struct is created by the [`rsplitn`] method on [slices].
1186///
1187/// # Example
1188///
1189/// ```
1190/// let slice = [10, 40, 30, 20, 60, 50];
1191/// let mut iter = slice.rsplitn(2, |num| *num % 3 == 0);
1192/// assert_eq!(iter.next(), Some(&[50][..]));
1193/// assert_eq!(iter.next(), Some(&[10, 40, 30, 20][..]));
1194/// assert_eq!(iter.next(), None);
1195/// ```
1196///
1197/// [`rsplitn`]: slice::rsplitn
1198/// [slices]: slice
1199#[stable(feature = "rust1", since = "1.0.0")]
1200#[must_use = "iterators are lazy and do nothing unless consumed"]
1201pub struct RSplitN<'a, T: 'a, P>
1202where
1203 P: FnMut(&T) -> bool,
1204{
1205 inner: GenericSplitN<RSplit<'a, T, P>>,
1206}
1207
1208impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitN<'a, T, P> {
1209 #[inline]
1210 pub(super) fn new(s: RSplit<'a, T, P>, n: usize) -> Self {
1211 Self { inner: GenericSplitN { iter: s, count: n } }
1212 }
1213}
1214
1215#[stable(feature = "core_impl_debug", since = "1.9.0")]
1216impl<T: fmt::Debug, P> fmt::Debug for RSplitN<'_, T, P>
1217where
1218 P: FnMut(&T) -> bool,
1219{
1220 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1221 f.debug_struct("RSplitN").field(name:"inner", &self.inner).finish()
1222 }
1223}
1224
1225/// An iterator over subslices separated by elements that match a predicate
1226/// function, limited to a given number of splits.
1227///
1228/// This struct is created by the [`splitn_mut`] method on [slices].
1229///
1230/// # Example
1231///
1232/// ```
1233/// let mut slice = [10, 40, 30, 20, 60, 50];
1234/// let iter = slice.splitn_mut(2, |num| *num % 3 == 0);
1235/// ```
1236///
1237/// [`splitn_mut`]: slice::splitn_mut
1238/// [slices]: slice
1239#[stable(feature = "rust1", since = "1.0.0")]
1240#[must_use = "iterators are lazy and do nothing unless consumed"]
1241pub struct SplitNMut<'a, T: 'a, P>
1242where
1243 P: FnMut(&T) -> bool,
1244{
1245 inner: GenericSplitN<SplitMut<'a, T, P>>,
1246}
1247
1248impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitNMut<'a, T, P> {
1249 #[inline]
1250 pub(super) fn new(s: SplitMut<'a, T, P>, n: usize) -> Self {
1251 Self { inner: GenericSplitN { iter: s, count: n } }
1252 }
1253}
1254
1255#[stable(feature = "core_impl_debug", since = "1.9.0")]
1256impl<T: fmt::Debug, P> fmt::Debug for SplitNMut<'_, T, P>
1257where
1258 P: FnMut(&T) -> bool,
1259{
1260 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1261 f.debug_struct("SplitNMut").field(name:"inner", &self.inner).finish()
1262 }
1263}
1264
1265/// An iterator over subslices separated by elements that match a
1266/// predicate function, limited to a given number of splits, starting
1267/// from the end of the slice.
1268///
1269/// This struct is created by the [`rsplitn_mut`] method on [slices].
1270///
1271/// # Example
1272///
1273/// ```
1274/// let mut slice = [10, 40, 30, 20, 60, 50];
1275/// let iter = slice.rsplitn_mut(2, |num| *num % 3 == 0);
1276/// ```
1277///
1278/// [`rsplitn_mut`]: slice::rsplitn_mut
1279/// [slices]: slice
1280#[stable(feature = "rust1", since = "1.0.0")]
1281#[must_use = "iterators are lazy and do nothing unless consumed"]
1282pub struct RSplitNMut<'a, T: 'a, P>
1283where
1284 P: FnMut(&T) -> bool,
1285{
1286 inner: GenericSplitN<RSplitMut<'a, T, P>>,
1287}
1288
1289impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitNMut<'a, T, P> {
1290 #[inline]
1291 pub(super) fn new(s: RSplitMut<'a, T, P>, n: usize) -> Self {
1292 Self { inner: GenericSplitN { iter: s, count: n } }
1293 }
1294}
1295
1296#[stable(feature = "core_impl_debug", since = "1.9.0")]
1297impl<T: fmt::Debug, P> fmt::Debug for RSplitNMut<'_, T, P>
1298where
1299 P: FnMut(&T) -> bool,
1300{
1301 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1302 f.debug_struct("RSplitNMut").field(name:"inner", &self.inner).finish()
1303 }
1304}
1305
1306forward_iterator! { SplitN: T, &'a [T] }
1307forward_iterator! { RSplitN: T, &'a [T] }
1308forward_iterator! { SplitNMut: T, &'a mut [T] }
1309forward_iterator! { RSplitNMut: T, &'a mut [T] }
1310
1311/// An iterator over overlapping subslices of length `size`.
1312///
1313/// This struct is created by the [`windows`] method on [slices].
1314///
1315/// # Example
1316///
1317/// ```
1318/// let slice = ['r', 'u', 's', 't'];
1319/// let mut iter = slice.windows(2);
1320/// assert_eq!(iter.next(), Some(&['r', 'u'][..]));
1321/// assert_eq!(iter.next(), Some(&['u', 's'][..]));
1322/// assert_eq!(iter.next(), Some(&['s', 't'][..]));
1323/// assert_eq!(iter.next(), None);
1324/// ```
1325///
1326/// [`windows`]: slice::windows
1327/// [slices]: slice
1328#[derive(Debug)]
1329#[stable(feature = "rust1", since = "1.0.0")]
1330#[must_use = "iterators are lazy and do nothing unless consumed"]
1331pub struct Windows<'a, T: 'a> {
1332 v: &'a [T],
1333 size: NonZero<usize>,
1334}
1335
1336impl<'a, T: 'a> Windows<'a, T> {
1337 #[inline]
1338 pub(super) fn new(slice: &'a [T], size: NonZero<usize>) -> Self {
1339 Self { v: slice, size }
1340 }
1341}
1342
1343// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1344#[stable(feature = "rust1", since = "1.0.0")]
1345impl<T> Clone for Windows<'_, T> {
1346 fn clone(&self) -> Self {
1347 Windows { v: self.v, size: self.size }
1348 }
1349}
1350
1351#[stable(feature = "rust1", since = "1.0.0")]
1352impl<'a, T> Iterator for Windows<'a, T> {
1353 type Item = &'a [T];
1354
1355 #[inline]
1356 fn next(&mut self) -> Option<&'a [T]> {
1357 if self.size.get() > self.v.len() {
1358 None
1359 } else {
1360 let ret = Some(&self.v[..self.size.get()]);
1361 self.v = &self.v[1..];
1362 ret
1363 }
1364 }
1365
1366 #[inline]
1367 fn size_hint(&self) -> (usize, Option<usize>) {
1368 if self.size.get() > self.v.len() {
1369 (0, Some(0))
1370 } else {
1371 let size = self.v.len() - self.size.get() + 1;
1372 (size, Some(size))
1373 }
1374 }
1375
1376 #[inline]
1377 fn count(self) -> usize {
1378 self.len()
1379 }
1380
1381 #[inline]
1382 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1383 let (end, overflow) = self.size.get().overflowing_add(n);
1384 if end > self.v.len() || overflow {
1385 self.v = &[];
1386 None
1387 } else {
1388 let nth = &self.v[n..end];
1389 self.v = &self.v[n + 1..];
1390 Some(nth)
1391 }
1392 }
1393
1394 #[inline]
1395 fn last(self) -> Option<Self::Item> {
1396 if self.size.get() > self.v.len() {
1397 None
1398 } else {
1399 let start = self.v.len() - self.size.get();
1400 Some(&self.v[start..])
1401 }
1402 }
1403
1404 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1405 // SAFETY: since the caller guarantees that `i` is in bounds,
1406 // which means that `i` cannot overflow an `isize`, and the
1407 // slice created by `from_raw_parts` is a subslice of `self.v`
1408 // thus is guaranteed to be valid for the lifetime `'a` of `self.v`.
1409 unsafe { from_raw_parts(self.v.as_ptr().add(idx), self.size.get()) }
1410 }
1411}
1412
1413#[stable(feature = "rust1", since = "1.0.0")]
1414impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
1415 #[inline]
1416 fn next_back(&mut self) -> Option<&'a [T]> {
1417 if self.size.get() > self.v.len() {
1418 None
1419 } else {
1420 let ret = Some(&self.v[self.v.len() - self.size.get()..]);
1421 self.v = &self.v[..self.v.len() - 1];
1422 ret
1423 }
1424 }
1425
1426 #[inline]
1427 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1428 let (end, overflow) = self.v.len().overflowing_sub(n);
1429 if end < self.size.get() || overflow {
1430 self.v = &[];
1431 None
1432 } else {
1433 let ret = &self.v[end - self.size.get()..end];
1434 self.v = &self.v[..end - 1];
1435 Some(ret)
1436 }
1437 }
1438}
1439
1440#[stable(feature = "rust1", since = "1.0.0")]
1441impl<T> ExactSizeIterator for Windows<'_, T> {}
1442
1443#[unstable(feature = "trusted_len", issue = "37572")]
1444unsafe impl<T> TrustedLen for Windows<'_, T> {}
1445
1446#[stable(feature = "fused", since = "1.26.0")]
1447impl<T> FusedIterator for Windows<'_, T> {}
1448
1449#[doc(hidden)]
1450#[unstable(feature = "trusted_random_access", issue = "none")]
1451unsafe impl<'a, T> TrustedRandomAccess for Windows<'a, T> {}
1452
1453#[doc(hidden)]
1454#[unstable(feature = "trusted_random_access", issue = "none")]
1455unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Windows<'a, T> {
1456 const MAY_HAVE_SIDE_EFFECT: bool = false;
1457}
1458
1459/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
1460/// time), starting at the beginning of the slice.
1461///
1462/// When the slice len is not evenly divided by the chunk size, the last slice
1463/// of the iteration will be the remainder.
1464///
1465/// This struct is created by the [`chunks`] method on [slices].
1466///
1467/// # Example
1468///
1469/// ```
1470/// let slice = ['l', 'o', 'r', 'e', 'm'];
1471/// let mut iter = slice.chunks(2);
1472/// assert_eq!(iter.next(), Some(&['l', 'o'][..]));
1473/// assert_eq!(iter.next(), Some(&['r', 'e'][..]));
1474/// assert_eq!(iter.next(), Some(&['m'][..]));
1475/// assert_eq!(iter.next(), None);
1476/// ```
1477///
1478/// [`chunks`]: slice::chunks
1479/// [slices]: slice
1480#[derive(Debug)]
1481#[stable(feature = "rust1", since = "1.0.0")]
1482#[must_use = "iterators are lazy and do nothing unless consumed"]
1483pub struct Chunks<'a, T: 'a> {
1484 v: &'a [T],
1485 chunk_size: usize,
1486}
1487
1488impl<'a, T: 'a> Chunks<'a, T> {
1489 #[inline]
1490 pub(super) fn new(slice: &'a [T], size: usize) -> Self {
1491 Self { v: slice, chunk_size: size }
1492 }
1493}
1494
1495// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1496#[stable(feature = "rust1", since = "1.0.0")]
1497impl<T> Clone for Chunks<'_, T> {
1498 fn clone(&self) -> Self {
1499 Chunks { v: self.v, chunk_size: self.chunk_size }
1500 }
1501}
1502
1503#[stable(feature = "rust1", since = "1.0.0")]
1504impl<'a, T> Iterator for Chunks<'a, T> {
1505 type Item = &'a [T];
1506
1507 #[inline]
1508 fn next(&mut self) -> Option<&'a [T]> {
1509 if self.v.is_empty() {
1510 None
1511 } else {
1512 let chunksz = cmp::min(self.v.len(), self.chunk_size);
1513 let (fst, snd) = self.v.split_at(chunksz);
1514 self.v = snd;
1515 Some(fst)
1516 }
1517 }
1518
1519 #[inline]
1520 fn size_hint(&self) -> (usize, Option<usize>) {
1521 if self.v.is_empty() {
1522 (0, Some(0))
1523 } else {
1524 let n = self.v.len() / self.chunk_size;
1525 let rem = self.v.len() % self.chunk_size;
1526 let n = if rem > 0 { n + 1 } else { n };
1527 (n, Some(n))
1528 }
1529 }
1530
1531 #[inline]
1532 fn count(self) -> usize {
1533 self.len()
1534 }
1535
1536 #[inline]
1537 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1538 let (start, overflow) = n.overflowing_mul(self.chunk_size);
1539 if start >= self.v.len() || overflow {
1540 self.v = &[];
1541 None
1542 } else {
1543 let end = match start.checked_add(self.chunk_size) {
1544 Some(sum) => cmp::min(self.v.len(), sum),
1545 None => self.v.len(),
1546 };
1547 let nth = &self.v[start..end];
1548 self.v = &self.v[end..];
1549 Some(nth)
1550 }
1551 }
1552
1553 #[inline]
1554 fn last(self) -> Option<Self::Item> {
1555 if self.v.is_empty() {
1556 None
1557 } else {
1558 let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
1559 Some(&self.v[start..])
1560 }
1561 }
1562
1563 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1564 let start = idx * self.chunk_size;
1565 // SAFETY: the caller guarantees that `i` is in bounds,
1566 // which means that `start` must be in bounds of the
1567 // underlying `self.v` slice, and we made sure that `len`
1568 // is also in bounds of `self.v`. Thus, `start` cannot overflow
1569 // an `isize`, and the slice constructed by `from_raw_parts`
1570 // is a subslice of `self.v` which is guaranteed to be valid
1571 // for the lifetime `'a` of `self.v`.
1572 unsafe {
1573 let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size);
1574 from_raw_parts(self.v.as_ptr().add(start), len)
1575 }
1576 }
1577}
1578
1579#[stable(feature = "rust1", since = "1.0.0")]
1580impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
1581 #[inline]
1582 fn next_back(&mut self) -> Option<&'a [T]> {
1583 if self.v.is_empty() {
1584 None
1585 } else {
1586 let remainder = self.v.len() % self.chunk_size;
1587 let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
1588 // SAFETY: split_at_unchecked requires the argument be less than or
1589 // equal to the length. This is guaranteed, but subtle: `chunksz`
1590 // will always either be `self.v.len() % self.chunk_size`, which
1591 // will always evaluate to strictly less than `self.v.len()` (or
1592 // panic, in the case that `self.chunk_size` is zero), or it can be
1593 // `self.chunk_size`, in the case that the length is exactly
1594 // divisible by the chunk size.
1595 //
1596 // While it seems like using `self.chunk_size` in this case could
1597 // lead to a value greater than `self.v.len()`, it cannot: if
1598 // `self.chunk_size` were greater than `self.v.len()`, then
1599 // `self.v.len() % self.chunk_size` would return nonzero (note that
1600 // in this branch of the `if`, we already know that `self.v` is
1601 // non-empty).
1602 let (fst, snd) = unsafe { self.v.split_at_unchecked(self.v.len() - chunksz) };
1603 self.v = fst;
1604 Some(snd)
1605 }
1606 }
1607
1608 #[inline]
1609 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1610 let len = self.len();
1611 if n >= len {
1612 self.v = &[];
1613 None
1614 } else {
1615 let start = (len - 1 - n) * self.chunk_size;
1616 let end = match start.checked_add(self.chunk_size) {
1617 Some(res) => cmp::min(self.v.len(), res),
1618 None => self.v.len(),
1619 };
1620 let nth_back = &self.v[start..end];
1621 self.v = &self.v[..start];
1622 Some(nth_back)
1623 }
1624 }
1625}
1626
1627#[stable(feature = "rust1", since = "1.0.0")]
1628impl<T> ExactSizeIterator for Chunks<'_, T> {}
1629
1630#[unstable(feature = "trusted_len", issue = "37572")]
1631unsafe impl<T> TrustedLen for Chunks<'_, T> {}
1632
1633#[stable(feature = "fused", since = "1.26.0")]
1634impl<T> FusedIterator for Chunks<'_, T> {}
1635
1636#[doc(hidden)]
1637#[unstable(feature = "trusted_random_access", issue = "none")]
1638unsafe impl<'a, T> TrustedRandomAccess for Chunks<'a, T> {}
1639
1640#[doc(hidden)]
1641#[unstable(feature = "trusted_random_access", issue = "none")]
1642unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Chunks<'a, T> {
1643 const MAY_HAVE_SIDE_EFFECT: bool = false;
1644}
1645
1646/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
1647/// elements at a time), starting at the beginning of the slice.
1648///
1649/// When the slice len is not evenly divided by the chunk size, the last slice
1650/// of the iteration will be the remainder.
1651///
1652/// This struct is created by the [`chunks_mut`] method on [slices].
1653///
1654/// # Example
1655///
1656/// ```
1657/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
1658/// let iter = slice.chunks_mut(2);
1659/// ```
1660///
1661/// [`chunks_mut`]: slice::chunks_mut
1662/// [slices]: slice
1663#[derive(Debug)]
1664#[stable(feature = "rust1", since = "1.0.0")]
1665#[must_use = "iterators are lazy and do nothing unless consumed"]
1666pub struct ChunksMut<'a, T: 'a> {
1667 /// # Safety
1668 /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
1669 /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
1670 /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
1671 /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
1672 /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
1673 v: *mut [T],
1674 chunk_size: usize,
1675 _marker: PhantomData<&'a mut T>,
1676}
1677
1678impl<'a, T: 'a> ChunksMut<'a, T> {
1679 #[inline]
1680 pub(super) fn new(slice: &'a mut [T], size: usize) -> Self {
1681 Self { v: slice, chunk_size: size, _marker: PhantomData }
1682 }
1683}
1684
1685#[stable(feature = "rust1", since = "1.0.0")]
1686impl<'a, T> Iterator for ChunksMut<'a, T> {
1687 type Item = &'a mut [T];
1688
1689 #[inline]
1690 fn next(&mut self) -> Option<&'a mut [T]> {
1691 if self.v.is_empty() {
1692 None
1693 } else {
1694 let sz = cmp::min(self.v.len(), self.chunk_size);
1695 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1696 let (head, tail) = unsafe { self.v.split_at_mut(sz) };
1697 self.v = tail;
1698 // SAFETY: Nothing else points to or will point to the contents of this slice.
1699 Some(unsafe { &mut *head })
1700 }
1701 }
1702
1703 #[inline]
1704 fn size_hint(&self) -> (usize, Option<usize>) {
1705 if self.v.is_empty() {
1706 (0, Some(0))
1707 } else {
1708 let n = self.v.len() / self.chunk_size;
1709 let rem = self.v.len() % self.chunk_size;
1710 let n = if rem > 0 { n + 1 } else { n };
1711 (n, Some(n))
1712 }
1713 }
1714
1715 #[inline]
1716 fn count(self) -> usize {
1717 self.len()
1718 }
1719
1720 #[inline]
1721 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
1722 let (start, overflow) = n.overflowing_mul(self.chunk_size);
1723 if start >= self.v.len() || overflow {
1724 self.v = &mut [];
1725 None
1726 } else {
1727 let end = match start.checked_add(self.chunk_size) {
1728 Some(sum) => cmp::min(self.v.len(), sum),
1729 None => self.v.len(),
1730 };
1731 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1732 let (head, tail) = unsafe { self.v.split_at_mut(end) };
1733 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1734 let (_, nth) = unsafe { head.split_at_mut(start) };
1735 self.v = tail;
1736 // SAFETY: Nothing else points to or will point to the contents of this slice.
1737 Some(unsafe { &mut *nth })
1738 }
1739 }
1740
1741 #[inline]
1742 fn last(self) -> Option<Self::Item> {
1743 if self.v.is_empty() {
1744 None
1745 } else {
1746 let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
1747 // SAFETY: Nothing else points to or will point to the contents of this slice.
1748 Some(unsafe { &mut *self.v.get_unchecked_mut(start..) })
1749 }
1750 }
1751
1752 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1753 let start = idx * self.chunk_size;
1754 // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`.
1755 //
1756 // Also note that the caller also guarantees that we're never called
1757 // with the same index again, and that no other methods that will
1758 // access this subslice are called, so it is valid for the returned
1759 // slice to be mutable.
1760 unsafe {
1761 let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size);
1762 from_raw_parts_mut(self.v.as_mut_ptr().add(start), len)
1763 }
1764 }
1765}
1766
1767#[stable(feature = "rust1", since = "1.0.0")]
1768impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
1769 #[inline]
1770 fn next_back(&mut self) -> Option<&'a mut [T]> {
1771 if self.v.is_empty() {
1772 None
1773 } else {
1774 let remainder = self.v.len() % self.chunk_size;
1775 let sz = if remainder != 0 { remainder } else { self.chunk_size };
1776 let len = self.v.len();
1777 // SAFETY: Similar to `Chunks::next_back`
1778 let (head, tail) = unsafe { self.v.split_at_mut_unchecked(len - sz) };
1779 self.v = head;
1780 // SAFETY: Nothing else points to or will point to the contents of this slice.
1781 Some(unsafe { &mut *tail })
1782 }
1783 }
1784
1785 #[inline]
1786 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1787 let len = self.len();
1788 if n >= len {
1789 self.v = &mut [];
1790 None
1791 } else {
1792 let start = (len - 1 - n) * self.chunk_size;
1793 let end = match start.checked_add(self.chunk_size) {
1794 Some(res) => cmp::min(self.v.len(), res),
1795 None => self.v.len(),
1796 };
1797 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1798 let (temp, _tail) = unsafe { self.v.split_at_mut(end) };
1799 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
1800 let (head, nth_back) = unsafe { temp.split_at_mut(start) };
1801 self.v = head;
1802 // SAFETY: Nothing else points to or will point to the contents of this slice.
1803 Some(unsafe { &mut *nth_back })
1804 }
1805 }
1806}
1807
1808#[stable(feature = "rust1", since = "1.0.0")]
1809impl<T> ExactSizeIterator for ChunksMut<'_, T> {}
1810
1811#[unstable(feature = "trusted_len", issue = "37572")]
1812unsafe impl<T> TrustedLen for ChunksMut<'_, T> {}
1813
1814#[stable(feature = "fused", since = "1.26.0")]
1815impl<T> FusedIterator for ChunksMut<'_, T> {}
1816
1817#[doc(hidden)]
1818#[unstable(feature = "trusted_random_access", issue = "none")]
1819unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {}
1820
1821#[doc(hidden)]
1822#[unstable(feature = "trusted_random_access", issue = "none")]
1823unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksMut<'a, T> {
1824 const MAY_HAVE_SIDE_EFFECT: bool = false;
1825}
1826
1827#[stable(feature = "rust1", since = "1.0.0")]
1828unsafe impl<T> Send for ChunksMut<'_, T> where T: Send {}
1829
1830#[stable(feature = "rust1", since = "1.0.0")]
1831unsafe impl<T> Sync for ChunksMut<'_, T> where T: Sync {}
1832
1833/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
1834/// time), starting at the beginning of the slice.
1835///
1836/// When the slice len is not evenly divided by the chunk size, the last
1837/// up to `chunk_size-1` elements will be omitted but can be retrieved from
1838/// the [`remainder`] function from the iterator.
1839///
1840/// This struct is created by the [`chunks_exact`] method on [slices].
1841///
1842/// # Example
1843///
1844/// ```
1845/// let slice = ['l', 'o', 'r', 'e', 'm'];
1846/// let mut iter = slice.chunks_exact(2);
1847/// assert_eq!(iter.next(), Some(&['l', 'o'][..]));
1848/// assert_eq!(iter.next(), Some(&['r', 'e'][..]));
1849/// assert_eq!(iter.next(), None);
1850/// ```
1851///
1852/// [`chunks_exact`]: slice::chunks_exact
1853/// [`remainder`]: ChunksExact::remainder
1854/// [slices]: slice
1855#[derive(Debug)]
1856#[stable(feature = "chunks_exact", since = "1.31.0")]
1857#[must_use = "iterators are lazy and do nothing unless consumed"]
1858pub struct ChunksExact<'a, T: 'a> {
1859 v: &'a [T],
1860 rem: &'a [T],
1861 chunk_size: usize,
1862}
1863
1864impl<'a, T> ChunksExact<'a, T> {
1865 #[inline]
1866 pub(super) fn new(slice: &'a [T], chunk_size: usize) -> Self {
1867 let rem = slice.len() % chunk_size;
1868 let fst_len = slice.len() - rem;
1869 // SAFETY: 0 <= fst_len <= slice.len() by construction above
1870 let (fst, snd) = unsafe { slice.split_at_unchecked(fst_len) };
1871 Self { v: fst, rem: snd, chunk_size }
1872 }
1873
1874 /// Returns the remainder of the original slice that is not going to be
1875 /// returned by the iterator. The returned slice has at most `chunk_size-1`
1876 /// elements.
1877 ///
1878 /// # Example
1879 ///
1880 /// ```
1881 /// let slice = ['l', 'o', 'r', 'e', 'm'];
1882 /// let mut iter = slice.chunks_exact(2);
1883 /// assert_eq!(iter.remainder(), &['m'][..]);
1884 /// assert_eq!(iter.next(), Some(&['l', 'o'][..]));
1885 /// assert_eq!(iter.remainder(), &['m'][..]);
1886 /// assert_eq!(iter.next(), Some(&['r', 'e'][..]));
1887 /// assert_eq!(iter.remainder(), &['m'][..]);
1888 /// assert_eq!(iter.next(), None);
1889 /// assert_eq!(iter.remainder(), &['m'][..]);
1890 /// ```
1891 #[must_use]
1892 #[stable(feature = "chunks_exact", since = "1.31.0")]
1893 pub fn remainder(&self) -> &'a [T] {
1894 self.rem
1895 }
1896}
1897
1898// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1899#[stable(feature = "chunks_exact", since = "1.31.0")]
1900impl<T> Clone for ChunksExact<'_, T> {
1901 fn clone(&self) -> Self {
1902 ChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
1903 }
1904}
1905
1906#[stable(feature = "chunks_exact", since = "1.31.0")]
1907impl<'a, T> Iterator for ChunksExact<'a, T> {
1908 type Item = &'a [T];
1909
1910 #[inline]
1911 fn next(&mut self) -> Option<&'a [T]> {
1912 if self.v.len() < self.chunk_size {
1913 None
1914 } else {
1915 let (fst, snd) = self.v.split_at(self.chunk_size);
1916 self.v = snd;
1917 Some(fst)
1918 }
1919 }
1920
1921 #[inline]
1922 fn size_hint(&self) -> (usize, Option<usize>) {
1923 let n = self.v.len() / self.chunk_size;
1924 (n, Some(n))
1925 }
1926
1927 #[inline]
1928 fn count(self) -> usize {
1929 self.len()
1930 }
1931
1932 #[inline]
1933 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1934 let (start, overflow) = n.overflowing_mul(self.chunk_size);
1935 if start >= self.v.len() || overflow {
1936 self.v = &[];
1937 None
1938 } else {
1939 let (_, snd) = self.v.split_at(start);
1940 self.v = snd;
1941 self.next()
1942 }
1943 }
1944
1945 #[inline]
1946 fn last(mut self) -> Option<Self::Item> {
1947 self.next_back()
1948 }
1949
1950 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1951 let start = idx * self.chunk_size;
1952 // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
1953 unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) }
1954 }
1955}
1956
1957#[stable(feature = "chunks_exact", since = "1.31.0")]
1958impl<'a, T> DoubleEndedIterator for ChunksExact<'a, T> {
1959 #[inline]
1960 fn next_back(&mut self) -> Option<&'a [T]> {
1961 if self.v.len() < self.chunk_size {
1962 None
1963 } else {
1964 let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
1965 self.v = fst;
1966 Some(snd)
1967 }
1968 }
1969
1970 #[inline]
1971 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1972 let len = self.len();
1973 if n >= len {
1974 self.v = &[];
1975 None
1976 } else {
1977 let start = (len - 1 - n) * self.chunk_size;
1978 let end = start + self.chunk_size;
1979 let nth_back = &self.v[start..end];
1980 self.v = &self.v[..start];
1981 Some(nth_back)
1982 }
1983 }
1984}
1985
1986#[stable(feature = "chunks_exact", since = "1.31.0")]
1987impl<T> ExactSizeIterator for ChunksExact<'_, T> {
1988 fn is_empty(&self) -> bool {
1989 self.v.is_empty()
1990 }
1991}
1992
1993#[unstable(feature = "trusted_len", issue = "37572")]
1994unsafe impl<T> TrustedLen for ChunksExact<'_, T> {}
1995
1996#[stable(feature = "chunks_exact", since = "1.31.0")]
1997impl<T> FusedIterator for ChunksExact<'_, T> {}
1998
1999#[doc(hidden)]
2000#[unstable(feature = "trusted_random_access", issue = "none")]
2001unsafe impl<'a, T> TrustedRandomAccess for ChunksExact<'a, T> {}
2002
2003#[doc(hidden)]
2004#[unstable(feature = "trusted_random_access", issue = "none")]
2005unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExact<'a, T> {
2006 const MAY_HAVE_SIDE_EFFECT: bool = false;
2007}
2008
2009/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
2010/// elements at a time), starting at the beginning of the slice.
2011///
2012/// When the slice len is not evenly divided by the chunk size, the last up to
2013/// `chunk_size-1` elements will be omitted but can be retrieved from the
2014/// [`into_remainder`] function from the iterator.
2015///
2016/// This struct is created by the [`chunks_exact_mut`] method on [slices].
2017///
2018/// # Example
2019///
2020/// ```
2021/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
2022/// let iter = slice.chunks_exact_mut(2);
2023/// ```
2024///
2025/// [`chunks_exact_mut`]: slice::chunks_exact_mut
2026/// [`into_remainder`]: ChunksExactMut::into_remainder
2027/// [slices]: slice
2028#[derive(Debug)]
2029#[stable(feature = "chunks_exact", since = "1.31.0")]
2030#[must_use = "iterators are lazy and do nothing unless consumed"]
2031pub struct ChunksExactMut<'a, T: 'a> {
2032 /// # Safety
2033 /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
2034 /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
2035 /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
2036 /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
2037 /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
2038 v: *mut [T],
2039 rem: &'a mut [T], // The iterator never yields from here, so this can be unique
2040 chunk_size: usize,
2041 _marker: PhantomData<&'a mut T>,
2042}
2043
2044impl<'a, T> ChunksExactMut<'a, T> {
2045 #[inline]
2046 pub(super) fn new(slice: &'a mut [T], chunk_size: usize) -> Self {
2047 let rem: usize = slice.len() % chunk_size;
2048 let fst_len: usize = slice.len() - rem;
2049 // SAFETY: 0 <= fst_len <= slice.len() by construction above
2050 let (fst: &mut [T], snd: &mut [T]) = unsafe { slice.split_at_mut_unchecked(mid:fst_len) };
2051 Self { v: fst, rem: snd, chunk_size, _marker: PhantomData }
2052 }
2053
2054 /// Returns the remainder of the original slice that is not going to be
2055 /// returned by the iterator. The returned slice has at most `chunk_size-1`
2056 /// elements.
2057 #[must_use = "`self` will be dropped if the result is not used"]
2058 #[stable(feature = "chunks_exact", since = "1.31.0")]
2059 pub fn into_remainder(self) -> &'a mut [T] {
2060 self.rem
2061 }
2062}
2063
2064#[stable(feature = "chunks_exact", since = "1.31.0")]
2065impl<'a, T> Iterator for ChunksExactMut<'a, T> {
2066 type Item = &'a mut [T];
2067
2068 #[inline]
2069 fn next(&mut self) -> Option<&'a mut [T]> {
2070 if self.v.len() < self.chunk_size {
2071 None
2072 } else {
2073 // SAFETY: self.chunk_size is inbounds because we compared above against self.v.len()
2074 let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) };
2075 self.v = tail;
2076 // SAFETY: Nothing else points to or will point to the contents of this slice.
2077 Some(unsafe { &mut *head })
2078 }
2079 }
2080
2081 #[inline]
2082 fn size_hint(&self) -> (usize, Option<usize>) {
2083 let n = self.v.len() / self.chunk_size;
2084 (n, Some(n))
2085 }
2086
2087 #[inline]
2088 fn count(self) -> usize {
2089 self.len()
2090 }
2091
2092 #[inline]
2093 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
2094 let (start, overflow) = n.overflowing_mul(self.chunk_size);
2095 if start >= self.v.len() || overflow {
2096 self.v = &mut [];
2097 None
2098 } else {
2099 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2100 let (_, snd) = unsafe { self.v.split_at_mut(start) };
2101 self.v = snd;
2102 self.next()
2103 }
2104 }
2105
2106 #[inline]
2107 fn last(mut self) -> Option<Self::Item> {
2108 self.next_back()
2109 }
2110
2111 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2112 let start = idx * self.chunk_size;
2113 // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`.
2114 unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) }
2115 }
2116}
2117
2118#[stable(feature = "chunks_exact", since = "1.31.0")]
2119impl<'a, T> DoubleEndedIterator for ChunksExactMut<'a, T> {
2120 #[inline]
2121 fn next_back(&mut self) -> Option<&'a mut [T]> {
2122 if self.v.len() < self.chunk_size {
2123 None
2124 } else {
2125 // SAFETY: This subtraction is inbounds because of the check above
2126 let (head, tail) = unsafe { self.v.split_at_mut(self.v.len() - self.chunk_size) };
2127 self.v = head;
2128 // SAFETY: Nothing else points to or will point to the contents of this slice.
2129 Some(unsafe { &mut *tail })
2130 }
2131 }
2132
2133 #[inline]
2134 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2135 let len = self.len();
2136 if n >= len {
2137 self.v = &mut [];
2138 None
2139 } else {
2140 let start = (len - 1 - n) * self.chunk_size;
2141 let end = start + self.chunk_size;
2142 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2143 let (temp, _tail) = unsafe { mem::replace(&mut self.v, &mut []).split_at_mut(end) };
2144 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2145 let (head, nth_back) = unsafe { temp.split_at_mut(start) };
2146 self.v = head;
2147 // SAFETY: Nothing else points to or will point to the contents of this slice.
2148 Some(unsafe { &mut *nth_back })
2149 }
2150 }
2151}
2152
2153#[stable(feature = "chunks_exact", since = "1.31.0")]
2154impl<T> ExactSizeIterator for ChunksExactMut<'_, T> {
2155 fn is_empty(&self) -> bool {
2156 self.v.is_empty()
2157 }
2158}
2159
2160#[unstable(feature = "trusted_len", issue = "37572")]
2161unsafe impl<T> TrustedLen for ChunksExactMut<'_, T> {}
2162
2163#[stable(feature = "chunks_exact", since = "1.31.0")]
2164impl<T> FusedIterator for ChunksExactMut<'_, T> {}
2165
2166#[doc(hidden)]
2167#[unstable(feature = "trusted_random_access", issue = "none")]
2168unsafe impl<'a, T> TrustedRandomAccess for ChunksExactMut<'a, T> {}
2169
2170#[doc(hidden)]
2171#[unstable(feature = "trusted_random_access", issue = "none")]
2172unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExactMut<'a, T> {
2173 const MAY_HAVE_SIDE_EFFECT: bool = false;
2174}
2175
2176#[stable(feature = "chunks_exact", since = "1.31.0")]
2177unsafe impl<T> Send for ChunksExactMut<'_, T> where T: Send {}
2178
2179#[stable(feature = "chunks_exact", since = "1.31.0")]
2180unsafe impl<T> Sync for ChunksExactMut<'_, T> where T: Sync {}
2181
2182/// A windowed iterator over a slice in overlapping chunks (`N` elements at a
2183/// time), starting at the beginning of the slice
2184///
2185/// This struct is created by the [`array_windows`] method on [slices].
2186///
2187/// # Example
2188///
2189/// ```
2190/// #![feature(array_windows)]
2191///
2192/// let slice = [0, 1, 2, 3];
2193/// let mut iter = slice.array_windows::<2>();
2194/// assert_eq!(iter.next(), Some(&[0, 1]));
2195/// assert_eq!(iter.next(), Some(&[1, 2]));
2196/// assert_eq!(iter.next(), Some(&[2, 3]));
2197/// assert_eq!(iter.next(), None);
2198/// ```
2199///
2200/// [`array_windows`]: slice::array_windows
2201/// [slices]: slice
2202#[derive(Debug, Clone, Copy)]
2203#[unstable(feature = "array_windows", issue = "75027")]
2204#[must_use = "iterators are lazy and do nothing unless consumed"]
2205pub struct ArrayWindows<'a, T: 'a, const N: usize> {
2206 slice_head: *const T,
2207 num: usize,
2208 marker: PhantomData<&'a [T; N]>,
2209}
2210
2211impl<'a, T: 'a, const N: usize> ArrayWindows<'a, T, N> {
2212 #[inline]
2213 pub(super) fn new(slice: &'a [T]) -> Self {
2214 let num_windows: usize = slice.len().saturating_sub(N - 1);
2215 Self { slice_head: slice.as_ptr(), num: num_windows, marker: PhantomData }
2216 }
2217}
2218
2219#[unstable(feature = "array_windows", issue = "75027")]
2220impl<'a, T, const N: usize> Iterator for ArrayWindows<'a, T, N> {
2221 type Item = &'a [T; N];
2222
2223 #[inline]
2224 fn next(&mut self) -> Option<Self::Item> {
2225 if self.num == 0 {
2226 return None;
2227 }
2228 // SAFETY:
2229 // This is safe because it's indexing into a slice guaranteed to be length > N.
2230 let ret = unsafe { &*self.slice_head.cast::<[T; N]>() };
2231 // SAFETY: Guaranteed that there are at least 1 item remaining otherwise
2232 // earlier branch would've been hit
2233 self.slice_head = unsafe { self.slice_head.add(1) };
2234
2235 self.num -= 1;
2236 Some(ret)
2237 }
2238
2239 #[inline]
2240 fn size_hint(&self) -> (usize, Option<usize>) {
2241 (self.num, Some(self.num))
2242 }
2243
2244 #[inline]
2245 fn count(self) -> usize {
2246 self.num
2247 }
2248
2249 #[inline]
2250 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2251 if self.num <= n {
2252 self.num = 0;
2253 return None;
2254 }
2255 // SAFETY:
2256 // This is safe because it's indexing into a slice guaranteed to be length > N.
2257 let ret = unsafe { &*self.slice_head.add(n).cast::<[T; N]>() };
2258 // SAFETY: Guaranteed that there are at least n items remaining
2259 self.slice_head = unsafe { self.slice_head.add(n + 1) };
2260
2261 self.num -= n + 1;
2262 Some(ret)
2263 }
2264
2265 #[inline]
2266 fn last(mut self) -> Option<Self::Item> {
2267 self.nth(self.num.checked_sub(1)?)
2268 }
2269}
2270
2271#[unstable(feature = "array_windows", issue = "75027")]
2272impl<'a, T, const N: usize> DoubleEndedIterator for ArrayWindows<'a, T, N> {
2273 #[inline]
2274 fn next_back(&mut self) -> Option<&'a [T; N]> {
2275 if self.num == 0 {
2276 return None;
2277 }
2278 // SAFETY: Guaranteed that there are n items remaining, n-1 for 0-indexing.
2279 let ret: &[T; N] = unsafe { &*self.slice_head.add(self.num - 1).cast::<[T; N]>() };
2280 self.num -= 1;
2281 Some(ret)
2282 }
2283
2284 #[inline]
2285 fn nth_back(&mut self, n: usize) -> Option<&'a [T; N]> {
2286 if self.num <= n {
2287 self.num = 0;
2288 return None;
2289 }
2290 // SAFETY: Guaranteed that there are n items remaining, n-1 for 0-indexing.
2291 let ret: &[T; N] = unsafe { &*self.slice_head.add(self.num - (n + 1)).cast::<[T; N]>() };
2292 self.num -= n + 1;
2293 Some(ret)
2294 }
2295}
2296
2297#[unstable(feature = "array_windows", issue = "75027")]
2298impl<T, const N: usize> ExactSizeIterator for ArrayWindows<'_, T, N> {
2299 fn is_empty(&self) -> bool {
2300 self.num == 0
2301 }
2302}
2303
2304/// An iterator over a slice in (non-overlapping) chunks (`N` elements at a
2305/// time), starting at the beginning of the slice.
2306///
2307/// When the slice len is not evenly divided by the chunk size, the last
2308/// up to `N-1` elements will be omitted but can be retrieved from
2309/// the [`remainder`] function from the iterator.
2310///
2311/// This struct is created by the [`array_chunks`] method on [slices].
2312///
2313/// # Example
2314///
2315/// ```
2316/// #![feature(array_chunks)]
2317///
2318/// let slice = ['l', 'o', 'r', 'e', 'm'];
2319/// let mut iter = slice.array_chunks::<2>();
2320/// assert_eq!(iter.next(), Some(&['l', 'o']));
2321/// assert_eq!(iter.next(), Some(&['r', 'e']));
2322/// assert_eq!(iter.next(), None);
2323/// ```
2324///
2325/// [`array_chunks`]: slice::array_chunks
2326/// [`remainder`]: ArrayChunks::remainder
2327/// [slices]: slice
2328#[derive(Debug)]
2329#[unstable(feature = "array_chunks", issue = "74985")]
2330#[must_use = "iterators are lazy and do nothing unless consumed"]
2331pub struct ArrayChunks<'a, T: 'a, const N: usize> {
2332 iter: Iter<'a, [T; N]>,
2333 rem: &'a [T],
2334}
2335
2336impl<'a, T, const N: usize> ArrayChunks<'a, T, N> {
2337 #[inline]
2338 pub(super) fn new(slice: &'a [T]) -> Self {
2339 let (array_slice: &[[T; N]], rem: &[T]) = slice.as_chunks();
2340 Self { iter: array_slice.iter(), rem }
2341 }
2342
2343 /// Returns the remainder of the original slice that is not going to be
2344 /// returned by the iterator. The returned slice has at most `N-1`
2345 /// elements.
2346 #[must_use]
2347 #[unstable(feature = "array_chunks", issue = "74985")]
2348 pub fn remainder(&self) -> &'a [T] {
2349 self.rem
2350 }
2351}
2352
2353// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2354#[unstable(feature = "array_chunks", issue = "74985")]
2355impl<T, const N: usize> Clone for ArrayChunks<'_, T, N> {
2356 fn clone(&self) -> Self {
2357 ArrayChunks { iter: self.iter.clone(), rem: self.rem }
2358 }
2359}
2360
2361#[unstable(feature = "array_chunks", issue = "74985")]
2362impl<'a, T, const N: usize> Iterator for ArrayChunks<'a, T, N> {
2363 type Item = &'a [T; N];
2364
2365 #[inline]
2366 fn next(&mut self) -> Option<&'a [T; N]> {
2367 self.iter.next()
2368 }
2369
2370 #[inline]
2371 fn size_hint(&self) -> (usize, Option<usize>) {
2372 self.iter.size_hint()
2373 }
2374
2375 #[inline]
2376 fn count(self) -> usize {
2377 self.iter.count()
2378 }
2379
2380 #[inline]
2381 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2382 self.iter.nth(n)
2383 }
2384
2385 #[inline]
2386 fn last(self) -> Option<Self::Item> {
2387 self.iter.last()
2388 }
2389
2390 unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> &'a [T; N] {
2391 // SAFETY: The safety guarantees of `__iterator_get_unchecked` are
2392 // transferred to the caller.
2393 unsafe { self.iter.__iterator_get_unchecked(i) }
2394 }
2395}
2396
2397#[unstable(feature = "array_chunks", issue = "74985")]
2398impl<'a, T, const N: usize> DoubleEndedIterator for ArrayChunks<'a, T, N> {
2399 #[inline]
2400 fn next_back(&mut self) -> Option<&'a [T; N]> {
2401 self.iter.next_back()
2402 }
2403
2404 #[inline]
2405 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2406 self.iter.nth_back(n)
2407 }
2408}
2409
2410#[unstable(feature = "array_chunks", issue = "74985")]
2411impl<T, const N: usize> ExactSizeIterator for ArrayChunks<'_, T, N> {
2412 fn is_empty(&self) -> bool {
2413 self.iter.is_empty()
2414 }
2415}
2416
2417#[unstable(feature = "trusted_len", issue = "37572")]
2418unsafe impl<T, const N: usize> TrustedLen for ArrayChunks<'_, T, N> {}
2419
2420#[unstable(feature = "array_chunks", issue = "74985")]
2421impl<T, const N: usize> FusedIterator for ArrayChunks<'_, T, N> {}
2422
2423#[doc(hidden)]
2424#[unstable(feature = "array_chunks", issue = "74985")]
2425unsafe impl<'a, T, const N: usize> TrustedRandomAccess for ArrayChunks<'a, T, N> {}
2426
2427#[doc(hidden)]
2428#[unstable(feature = "array_chunks", issue = "74985")]
2429unsafe impl<'a, T, const N: usize> TrustedRandomAccessNoCoerce for ArrayChunks<'a, T, N> {
2430 const MAY_HAVE_SIDE_EFFECT: bool = false;
2431}
2432
2433/// An iterator over a slice in (non-overlapping) mutable chunks (`N` elements
2434/// at a time), starting at the beginning of the slice.
2435///
2436/// When the slice len is not evenly divided by the chunk size, the last
2437/// up to `N-1` elements will be omitted but can be retrieved from
2438/// the [`into_remainder`] function from the iterator.
2439///
2440/// This struct is created by the [`array_chunks_mut`] method on [slices].
2441///
2442/// # Example
2443///
2444/// ```
2445/// #![feature(array_chunks)]
2446///
2447/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
2448/// let iter = slice.array_chunks_mut::<2>();
2449/// ```
2450///
2451/// [`array_chunks_mut`]: slice::array_chunks_mut
2452/// [`into_remainder`]: ../../std/slice/struct.ArrayChunksMut.html#method.into_remainder
2453/// [slices]: slice
2454#[derive(Debug)]
2455#[unstable(feature = "array_chunks", issue = "74985")]
2456#[must_use = "iterators are lazy and do nothing unless consumed"]
2457pub struct ArrayChunksMut<'a, T: 'a, const N: usize> {
2458 iter: IterMut<'a, [T; N]>,
2459 rem: &'a mut [T],
2460}
2461
2462impl<'a, T, const N: usize> ArrayChunksMut<'a, T, N> {
2463 #[inline]
2464 pub(super) fn new(slice: &'a mut [T]) -> Self {
2465 let (array_slice: &mut [[T; N]], rem: &mut [T]) = slice.as_chunks_mut();
2466 Self { iter: array_slice.iter_mut(), rem }
2467 }
2468
2469 /// Returns the remainder of the original slice that is not going to be
2470 /// returned by the iterator. The returned slice has at most `N-1`
2471 /// elements.
2472 #[must_use = "`self` will be dropped if the result is not used"]
2473 #[unstable(feature = "array_chunks", issue = "74985")]
2474 pub fn into_remainder(self) -> &'a mut [T] {
2475 self.rem
2476 }
2477}
2478
2479#[unstable(feature = "array_chunks", issue = "74985")]
2480impl<'a, T, const N: usize> Iterator for ArrayChunksMut<'a, T, N> {
2481 type Item = &'a mut [T; N];
2482
2483 #[inline]
2484 fn next(&mut self) -> Option<&'a mut [T; N]> {
2485 self.iter.next()
2486 }
2487
2488 #[inline]
2489 fn size_hint(&self) -> (usize, Option<usize>) {
2490 self.iter.size_hint()
2491 }
2492
2493 #[inline]
2494 fn count(self) -> usize {
2495 self.iter.count()
2496 }
2497
2498 #[inline]
2499 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2500 self.iter.nth(n)
2501 }
2502
2503 #[inline]
2504 fn last(self) -> Option<Self::Item> {
2505 self.iter.last()
2506 }
2507
2508 unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> &'a mut [T; N] {
2509 // SAFETY: The safety guarantees of `__iterator_get_unchecked` are transferred to
2510 // the caller.
2511 unsafe { self.iter.__iterator_get_unchecked(i) }
2512 }
2513}
2514
2515#[unstable(feature = "array_chunks", issue = "74985")]
2516impl<'a, T, const N: usize> DoubleEndedIterator for ArrayChunksMut<'a, T, N> {
2517 #[inline]
2518 fn next_back(&mut self) -> Option<&'a mut [T; N]> {
2519 self.iter.next_back()
2520 }
2521
2522 #[inline]
2523 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2524 self.iter.nth_back(n)
2525 }
2526}
2527
2528#[unstable(feature = "array_chunks", issue = "74985")]
2529impl<T, const N: usize> ExactSizeIterator for ArrayChunksMut<'_, T, N> {
2530 fn is_empty(&self) -> bool {
2531 self.iter.is_empty()
2532 }
2533}
2534
2535#[unstable(feature = "trusted_len", issue = "37572")]
2536unsafe impl<T, const N: usize> TrustedLen for ArrayChunksMut<'_, T, N> {}
2537
2538#[unstable(feature = "array_chunks", issue = "74985")]
2539impl<T, const N: usize> FusedIterator for ArrayChunksMut<'_, T, N> {}
2540
2541#[doc(hidden)]
2542#[unstable(feature = "array_chunks", issue = "74985")]
2543unsafe impl<'a, T, const N: usize> TrustedRandomAccess for ArrayChunksMut<'a, T, N> {}
2544
2545#[doc(hidden)]
2546#[unstable(feature = "array_chunks", issue = "74985")]
2547unsafe impl<'a, T, const N: usize> TrustedRandomAccessNoCoerce for ArrayChunksMut<'a, T, N> {
2548 const MAY_HAVE_SIDE_EFFECT: bool = false;
2549}
2550
2551/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
2552/// time), starting at the end of the slice.
2553///
2554/// When the slice len is not evenly divided by the chunk size, the last slice
2555/// of the iteration will be the remainder.
2556///
2557/// This struct is created by the [`rchunks`] method on [slices].
2558///
2559/// # Example
2560///
2561/// ```
2562/// let slice = ['l', 'o', 'r', 'e', 'm'];
2563/// let mut iter = slice.rchunks(2);
2564/// assert_eq!(iter.next(), Some(&['e', 'm'][..]));
2565/// assert_eq!(iter.next(), Some(&['o', 'r'][..]));
2566/// assert_eq!(iter.next(), Some(&['l'][..]));
2567/// assert_eq!(iter.next(), None);
2568/// ```
2569///
2570/// [`rchunks`]: slice::rchunks
2571/// [slices]: slice
2572#[derive(Debug)]
2573#[stable(feature = "rchunks", since = "1.31.0")]
2574#[must_use = "iterators are lazy and do nothing unless consumed"]
2575pub struct RChunks<'a, T: 'a> {
2576 v: &'a [T],
2577 chunk_size: usize,
2578}
2579
2580impl<'a, T: 'a> RChunks<'a, T> {
2581 #[inline]
2582 pub(super) fn new(slice: &'a [T], size: usize) -> Self {
2583 Self { v: slice, chunk_size: size }
2584 }
2585}
2586
2587// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2588#[stable(feature = "rchunks", since = "1.31.0")]
2589impl<T> Clone for RChunks<'_, T> {
2590 fn clone(&self) -> Self {
2591 RChunks { v: self.v, chunk_size: self.chunk_size }
2592 }
2593}
2594
2595#[stable(feature = "rchunks", since = "1.31.0")]
2596impl<'a, T> Iterator for RChunks<'a, T> {
2597 type Item = &'a [T];
2598
2599 #[inline]
2600 fn next(&mut self) -> Option<&'a [T]> {
2601 if self.v.is_empty() {
2602 None
2603 } else {
2604 let len = self.v.len();
2605 let chunksz = cmp::min(len, self.chunk_size);
2606 // SAFETY: split_at_unchecked just requires the argument be less
2607 // than the length. This could only happen if the expression `len -
2608 // chunksz` overflows. This could only happen if `chunksz > len`,
2609 // which is impossible as we initialize it as the `min` of `len` and
2610 // `self.chunk_size`.
2611 let (fst, snd) = unsafe { self.v.split_at_unchecked(len - chunksz) };
2612 self.v = fst;
2613 Some(snd)
2614 }
2615 }
2616
2617 #[inline]
2618 fn size_hint(&self) -> (usize, Option<usize>) {
2619 if self.v.is_empty() {
2620 (0, Some(0))
2621 } else {
2622 let n = self.v.len() / self.chunk_size;
2623 let rem = self.v.len() % self.chunk_size;
2624 let n = if rem > 0 { n + 1 } else { n };
2625 (n, Some(n))
2626 }
2627 }
2628
2629 #[inline]
2630 fn count(self) -> usize {
2631 self.len()
2632 }
2633
2634 #[inline]
2635 fn nth(&mut self, n: usize) -> Option<Self::Item> {
2636 let (end, overflow) = n.overflowing_mul(self.chunk_size);
2637 if end >= self.v.len() || overflow {
2638 self.v = &[];
2639 None
2640 } else {
2641 // Can't underflow because of the check above
2642 let end = self.v.len() - end;
2643 let start = match end.checked_sub(self.chunk_size) {
2644 Some(sum) => sum,
2645 None => 0,
2646 };
2647 let nth = &self.v[start..end];
2648 self.v = &self.v[0..start];
2649 Some(nth)
2650 }
2651 }
2652
2653 #[inline]
2654 fn last(self) -> Option<Self::Item> {
2655 if self.v.is_empty() {
2656 None
2657 } else {
2658 let rem = self.v.len() % self.chunk_size;
2659 let end = if rem == 0 { self.chunk_size } else { rem };
2660 Some(&self.v[0..end])
2661 }
2662 }
2663
2664 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2665 let end = self.v.len() - idx * self.chunk_size;
2666 let start = match end.checked_sub(self.chunk_size) {
2667 None => 0,
2668 Some(start) => start,
2669 };
2670 // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
2671 unsafe { from_raw_parts(self.v.as_ptr().add(start), end - start) }
2672 }
2673}
2674
2675#[stable(feature = "rchunks", since = "1.31.0")]
2676impl<'a, T> DoubleEndedIterator for RChunks<'a, T> {
2677 #[inline]
2678 fn next_back(&mut self) -> Option<&'a [T]> {
2679 if self.v.is_empty() {
2680 None
2681 } else {
2682 let remainder = self.v.len() % self.chunk_size;
2683 let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
2684 // SAFETY: similar to Chunks::next_back
2685 let (fst, snd) = unsafe { self.v.split_at_unchecked(chunksz) };
2686 self.v = snd;
2687 Some(fst)
2688 }
2689 }
2690
2691 #[inline]
2692 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2693 let len = self.len();
2694 if n >= len {
2695 self.v = &[];
2696 None
2697 } else {
2698 // can't underflow because `n < len`
2699 let offset_from_end = (len - 1 - n) * self.chunk_size;
2700 let end = self.v.len() - offset_from_end;
2701 let start = end.saturating_sub(self.chunk_size);
2702 let nth_back = &self.v[start..end];
2703 self.v = &self.v[end..];
2704 Some(nth_back)
2705 }
2706 }
2707}
2708
2709#[stable(feature = "rchunks", since = "1.31.0")]
2710impl<T> ExactSizeIterator for RChunks<'_, T> {}
2711
2712#[unstable(feature = "trusted_len", issue = "37572")]
2713unsafe impl<T> TrustedLen for RChunks<'_, T> {}
2714
2715#[stable(feature = "rchunks", since = "1.31.0")]
2716impl<T> FusedIterator for RChunks<'_, T> {}
2717
2718#[doc(hidden)]
2719#[unstable(feature = "trusted_random_access", issue = "none")]
2720unsafe impl<'a, T> TrustedRandomAccess for RChunks<'a, T> {}
2721
2722#[doc(hidden)]
2723#[unstable(feature = "trusted_random_access", issue = "none")]
2724unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunks<'a, T> {
2725 const MAY_HAVE_SIDE_EFFECT: bool = false;
2726}
2727
2728/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
2729/// elements at a time), starting at the end of the slice.
2730///
2731/// When the slice len is not evenly divided by the chunk size, the last slice
2732/// of the iteration will be the remainder.
2733///
2734/// This struct is created by the [`rchunks_mut`] method on [slices].
2735///
2736/// # Example
2737///
2738/// ```
2739/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
2740/// let iter = slice.rchunks_mut(2);
2741/// ```
2742///
2743/// [`rchunks_mut`]: slice::rchunks_mut
2744/// [slices]: slice
2745#[derive(Debug)]
2746#[stable(feature = "rchunks", since = "1.31.0")]
2747#[must_use = "iterators are lazy and do nothing unless consumed"]
2748pub struct RChunksMut<'a, T: 'a> {
2749 /// # Safety
2750 /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
2751 /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
2752 /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
2753 /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
2754 /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
2755 v: *mut [T],
2756 chunk_size: usize,
2757 _marker: PhantomData<&'a mut T>,
2758}
2759
2760impl<'a, T: 'a> RChunksMut<'a, T> {
2761 #[inline]
2762 pub(super) fn new(slice: &'a mut [T], size: usize) -> Self {
2763 Self { v: slice, chunk_size: size, _marker: PhantomData }
2764 }
2765}
2766
2767#[stable(feature = "rchunks", since = "1.31.0")]
2768impl<'a, T> Iterator for RChunksMut<'a, T> {
2769 type Item = &'a mut [T];
2770
2771 #[inline]
2772 fn next(&mut self) -> Option<&'a mut [T]> {
2773 if self.v.is_empty() {
2774 None
2775 } else {
2776 let sz = cmp::min(self.v.len(), self.chunk_size);
2777 let len = self.v.len();
2778 // SAFETY: split_at_mut_unchecked just requires the argument be less
2779 // than the length. This could only happen if the expression
2780 // `len - sz` overflows. This could only happen if `sz >
2781 // len`, which is impossible as we initialize it as the `min` of
2782 // `self.v.len()` (e.g. `len`) and `self.chunk_size`.
2783 let (head, tail) = unsafe { self.v.split_at_mut_unchecked(len - sz) };
2784 self.v = head;
2785 // SAFETY: Nothing else points to or will point to the contents of this slice.
2786 Some(unsafe { &mut *tail })
2787 }
2788 }
2789
2790 #[inline]
2791 fn size_hint(&self) -> (usize, Option<usize>) {
2792 if self.v.is_empty() {
2793 (0, Some(0))
2794 } else {
2795 let n = self.v.len() / self.chunk_size;
2796 let rem = self.v.len() % self.chunk_size;
2797 let n = if rem > 0 { n + 1 } else { n };
2798 (n, Some(n))
2799 }
2800 }
2801
2802 #[inline]
2803 fn count(self) -> usize {
2804 self.len()
2805 }
2806
2807 #[inline]
2808 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
2809 let (end, overflow) = n.overflowing_mul(self.chunk_size);
2810 if end >= self.v.len() || overflow {
2811 self.v = &mut [];
2812 None
2813 } else {
2814 // Can't underflow because of the check above
2815 let end = self.v.len() - end;
2816 let start = match end.checked_sub(self.chunk_size) {
2817 Some(sum) => sum,
2818 None => 0,
2819 };
2820 // SAFETY: This type ensures that self.v is a valid pointer with a correct len.
2821 // Therefore the bounds check in split_at_mut guarantees the split point is inbounds.
2822 let (head, tail) = unsafe { self.v.split_at_mut(start) };
2823 // SAFETY: This type ensures that self.v is a valid pointer with a correct len.
2824 // Therefore the bounds check in split_at_mut guarantees the split point is inbounds.
2825 let (nth, _) = unsafe { tail.split_at_mut(end - start) };
2826 self.v = head;
2827 // SAFETY: Nothing else points to or will point to the contents of this slice.
2828 Some(unsafe { &mut *nth })
2829 }
2830 }
2831
2832 #[inline]
2833 fn last(self) -> Option<Self::Item> {
2834 if self.v.is_empty() {
2835 None
2836 } else {
2837 let rem = self.v.len() % self.chunk_size;
2838 let end = if rem == 0 { self.chunk_size } else { rem };
2839 // SAFETY: Nothing else points to or will point to the contents of this slice.
2840 Some(unsafe { &mut *self.v.get_unchecked_mut(0..end) })
2841 }
2842 }
2843
2844 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2845 let end = self.v.len() - idx * self.chunk_size;
2846 let start = match end.checked_sub(self.chunk_size) {
2847 None => 0,
2848 Some(start) => start,
2849 };
2850 // SAFETY: see comments for `RChunks::__iterator_get_unchecked` and
2851 // `ChunksMut::__iterator_get_unchecked`, `self.v`.
2852 unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start) }
2853 }
2854}
2855
2856#[stable(feature = "rchunks", since = "1.31.0")]
2857impl<'a, T> DoubleEndedIterator for RChunksMut<'a, T> {
2858 #[inline]
2859 fn next_back(&mut self) -> Option<&'a mut [T]> {
2860 if self.v.is_empty() {
2861 None
2862 } else {
2863 let remainder = self.v.len() % self.chunk_size;
2864 let sz = if remainder != 0 { remainder } else { self.chunk_size };
2865 // SAFETY: Similar to `Chunks::next_back`
2866 let (head, tail) = unsafe { self.v.split_at_mut_unchecked(sz) };
2867 self.v = tail;
2868 // SAFETY: Nothing else points to or will point to the contents of this slice.
2869 Some(unsafe { &mut *head })
2870 }
2871 }
2872
2873 #[inline]
2874 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2875 let len = self.len();
2876 if n >= len {
2877 self.v = &mut [];
2878 None
2879 } else {
2880 // can't underflow because `n < len`
2881 let offset_from_end = (len - 1 - n) * self.chunk_size;
2882 let end = self.v.len() - offset_from_end;
2883 let start = end.saturating_sub(self.chunk_size);
2884 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2885 let (tmp, tail) = unsafe { self.v.split_at_mut(end) };
2886 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2887 let (_, nth_back) = unsafe { tmp.split_at_mut(start) };
2888 self.v = tail;
2889 // SAFETY: Nothing else points to or will point to the contents of this slice.
2890 Some(unsafe { &mut *nth_back })
2891 }
2892 }
2893}
2894
2895#[stable(feature = "rchunks", since = "1.31.0")]
2896impl<T> ExactSizeIterator for RChunksMut<'_, T> {}
2897
2898#[unstable(feature = "trusted_len", issue = "37572")]
2899unsafe impl<T> TrustedLen for RChunksMut<'_, T> {}
2900
2901#[stable(feature = "rchunks", since = "1.31.0")]
2902impl<T> FusedIterator for RChunksMut<'_, T> {}
2903
2904#[doc(hidden)]
2905#[unstable(feature = "trusted_random_access", issue = "none")]
2906unsafe impl<'a, T> TrustedRandomAccess for RChunksMut<'a, T> {}
2907
2908#[doc(hidden)]
2909#[unstable(feature = "trusted_random_access", issue = "none")]
2910unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksMut<'a, T> {
2911 const MAY_HAVE_SIDE_EFFECT: bool = false;
2912}
2913
2914#[stable(feature = "rchunks", since = "1.31.0")]
2915unsafe impl<T> Send for RChunksMut<'_, T> where T: Send {}
2916
2917#[stable(feature = "rchunks", since = "1.31.0")]
2918unsafe impl<T> Sync for RChunksMut<'_, T> where T: Sync {}
2919
2920/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
2921/// time), starting at the end of the slice.
2922///
2923/// When the slice len is not evenly divided by the chunk size, the last
2924/// up to `chunk_size-1` elements will be omitted but can be retrieved from
2925/// the [`remainder`] function from the iterator.
2926///
2927/// This struct is created by the [`rchunks_exact`] method on [slices].
2928///
2929/// # Example
2930///
2931/// ```
2932/// let slice = ['l', 'o', 'r', 'e', 'm'];
2933/// let mut iter = slice.rchunks_exact(2);
2934/// assert_eq!(iter.next(), Some(&['e', 'm'][..]));
2935/// assert_eq!(iter.next(), Some(&['o', 'r'][..]));
2936/// assert_eq!(iter.next(), None);
2937/// ```
2938///
2939/// [`rchunks_exact`]: slice::rchunks_exact
2940/// [`remainder`]: RChunksExact::remainder
2941/// [slices]: slice
2942#[derive(Debug)]
2943#[stable(feature = "rchunks", since = "1.31.0")]
2944#[must_use = "iterators are lazy and do nothing unless consumed"]
2945pub struct RChunksExact<'a, T: 'a> {
2946 v: &'a [T],
2947 rem: &'a [T],
2948 chunk_size: usize,
2949}
2950
2951impl<'a, T> RChunksExact<'a, T> {
2952 #[inline]
2953 pub(super) fn new(slice: &'a [T], chunk_size: usize) -> Self {
2954 let rem = slice.len() % chunk_size;
2955 // SAFETY: 0 <= rem <= slice.len() by construction above
2956 let (fst, snd) = unsafe { slice.split_at_unchecked(rem) };
2957 Self { v: snd, rem: fst, chunk_size }
2958 }
2959
2960 /// Returns the remainder of the original slice that is not going to be
2961 /// returned by the iterator. The returned slice has at most `chunk_size-1`
2962 /// elements.
2963 ///
2964 /// # Example
2965 ///
2966 /// ```
2967 /// let slice = ['l', 'o', 'r', 'e', 'm'];
2968 /// let mut iter = slice.rchunks_exact(2);
2969 /// assert_eq!(iter.remainder(), &['l'][..]);
2970 /// assert_eq!(iter.next(), Some(&['e', 'm'][..]));
2971 /// assert_eq!(iter.remainder(), &['l'][..]);
2972 /// assert_eq!(iter.next(), Some(&['o', 'r'][..]));
2973 /// assert_eq!(iter.remainder(), &['l'][..]);
2974 /// assert_eq!(iter.next(), None);
2975 /// assert_eq!(iter.remainder(), &['l'][..]);
2976 /// ```
2977 #[must_use]
2978 #[stable(feature = "rchunks", since = "1.31.0")]
2979 pub fn remainder(&self) -> &'a [T] {
2980 self.rem
2981 }
2982}
2983
2984// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2985#[stable(feature = "rchunks", since = "1.31.0")]
2986impl<'a, T> Clone for RChunksExact<'a, T> {
2987 fn clone(&self) -> RChunksExact<'a, T> {
2988 RChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
2989 }
2990}
2991
2992#[stable(feature = "rchunks", since = "1.31.0")]
2993impl<'a, T> Iterator for RChunksExact<'a, T> {
2994 type Item = &'a [T];
2995
2996 #[inline]
2997 fn next(&mut self) -> Option<&'a [T]> {
2998 if self.v.len() < self.chunk_size {
2999 None
3000 } else {
3001 let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
3002 self.v = fst;
3003 Some(snd)
3004 }
3005 }
3006
3007 #[inline]
3008 fn size_hint(&self) -> (usize, Option<usize>) {
3009 let n = self.v.len() / self.chunk_size;
3010 (n, Some(n))
3011 }
3012
3013 #[inline]
3014 fn count(self) -> usize {
3015 self.len()
3016 }
3017
3018 #[inline]
3019 fn nth(&mut self, n: usize) -> Option<Self::Item> {
3020 let (end, overflow) = n.overflowing_mul(self.chunk_size);
3021 if end >= self.v.len() || overflow {
3022 self.v = &[];
3023 None
3024 } else {
3025 let (fst, _) = self.v.split_at(self.v.len() - end);
3026 self.v = fst;
3027 self.next()
3028 }
3029 }
3030
3031 #[inline]
3032 fn last(mut self) -> Option<Self::Item> {
3033 self.next_back()
3034 }
3035
3036 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
3037 let end = self.v.len() - idx * self.chunk_size;
3038 let start = end - self.chunk_size;
3039 // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
3040 unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) }
3041 }
3042}
3043
3044#[stable(feature = "rchunks", since = "1.31.0")]
3045impl<'a, T> DoubleEndedIterator for RChunksExact<'a, T> {
3046 #[inline]
3047 fn next_back(&mut self) -> Option<&'a [T]> {
3048 if self.v.len() < self.chunk_size {
3049 None
3050 } else {
3051 let (fst, snd) = self.v.split_at(self.chunk_size);
3052 self.v = snd;
3053 Some(fst)
3054 }
3055 }
3056
3057 #[inline]
3058 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
3059 let len = self.len();
3060 if n >= len {
3061 self.v = &[];
3062 None
3063 } else {
3064 // now that we know that `n` corresponds to a chunk,
3065 // none of these operations can underflow/overflow
3066 let offset = (len - n) * self.chunk_size;
3067 let start = self.v.len() - offset;
3068 let end = start + self.chunk_size;
3069 let nth_back = &self.v[start..end];
3070 self.v = &self.v[end..];
3071 Some(nth_back)
3072 }
3073 }
3074}
3075
3076#[stable(feature = "rchunks", since = "1.31.0")]
3077impl<'a, T> ExactSizeIterator for RChunksExact<'a, T> {
3078 fn is_empty(&self) -> bool {
3079 self.v.is_empty()
3080 }
3081}
3082
3083#[unstable(feature = "trusted_len", issue = "37572")]
3084unsafe impl<T> TrustedLen for RChunksExact<'_, T> {}
3085
3086#[stable(feature = "rchunks", since = "1.31.0")]
3087impl<T> FusedIterator for RChunksExact<'_, T> {}
3088
3089#[doc(hidden)]
3090#[unstable(feature = "trusted_random_access", issue = "none")]
3091unsafe impl<'a, T> TrustedRandomAccess for RChunksExact<'a, T> {}
3092
3093#[doc(hidden)]
3094#[unstable(feature = "trusted_random_access", issue = "none")]
3095unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExact<'a, T> {
3096 const MAY_HAVE_SIDE_EFFECT: bool = false;
3097}
3098
3099/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
3100/// elements at a time), starting at the end of the slice.
3101///
3102/// When the slice len is not evenly divided by the chunk size, the last up to
3103/// `chunk_size-1` elements will be omitted but can be retrieved from the
3104/// [`into_remainder`] function from the iterator.
3105///
3106/// This struct is created by the [`rchunks_exact_mut`] method on [slices].
3107///
3108/// # Example
3109///
3110/// ```
3111/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
3112/// let iter = slice.rchunks_exact_mut(2);
3113/// ```
3114///
3115/// [`rchunks_exact_mut`]: slice::rchunks_exact_mut
3116/// [`into_remainder`]: RChunksExactMut::into_remainder
3117/// [slices]: slice
3118#[derive(Debug)]
3119#[stable(feature = "rchunks", since = "1.31.0")]
3120#[must_use = "iterators are lazy and do nothing unless consumed"]
3121pub struct RChunksExactMut<'a, T: 'a> {
3122 /// # Safety
3123 /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
3124 /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
3125 /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
3126 /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
3127 /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
3128 v: *mut [T],
3129 rem: &'a mut [T],
3130 chunk_size: usize,
3131}
3132
3133impl<'a, T> RChunksExactMut<'a, T> {
3134 #[inline]
3135 pub(super) fn new(slice: &'a mut [T], chunk_size: usize) -> Self {
3136 let rem: usize = slice.len() % chunk_size;
3137 // SAFETY: 0 <= rem <= slice.len() by construction above
3138 let (fst: &mut [T], snd: &mut [T]) = unsafe { slice.split_at_mut_unchecked(mid:rem) };
3139 Self { v: snd, rem: fst, chunk_size }
3140 }
3141
3142 /// Returns the remainder of the original slice that is not going to be
3143 /// returned by the iterator. The returned slice has at most `chunk_size-1`
3144 /// elements.
3145 #[must_use = "`self` will be dropped if the result is not used"]
3146 #[stable(feature = "rchunks", since = "1.31.0")]
3147 pub fn into_remainder(self) -> &'a mut [T] {
3148 self.rem
3149 }
3150}
3151
3152#[stable(feature = "rchunks", since = "1.31.0")]
3153impl<'a, T> Iterator for RChunksExactMut<'a, T> {
3154 type Item = &'a mut [T];
3155
3156 #[inline]
3157 fn next(&mut self) -> Option<&'a mut [T]> {
3158 if self.v.len() < self.chunk_size {
3159 None
3160 } else {
3161 let len = self.v.len();
3162 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3163 let (head, tail) = unsafe { self.v.split_at_mut(len - self.chunk_size) };
3164 self.v = head;
3165 // SAFETY: Nothing else points to or will point to the contents of this slice.
3166 Some(unsafe { &mut *tail })
3167 }
3168 }
3169
3170 #[inline]
3171 fn size_hint(&self) -> (usize, Option<usize>) {
3172 let n = self.v.len() / self.chunk_size;
3173 (n, Some(n))
3174 }
3175
3176 #[inline]
3177 fn count(self) -> usize {
3178 self.len()
3179 }
3180
3181 #[inline]
3182 fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
3183 let (end, overflow) = n.overflowing_mul(self.chunk_size);
3184 if end >= self.v.len() || overflow {
3185 self.v = &mut [];
3186 None
3187 } else {
3188 let len = self.v.len();
3189 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3190 let (fst, _) = unsafe { self.v.split_at_mut(len - end) };
3191 self.v = fst;
3192 self.next()
3193 }
3194 }
3195
3196 #[inline]
3197 fn last(mut self) -> Option<Self::Item> {
3198 self.next_back()
3199 }
3200
3201 unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
3202 let end = self.v.len() - idx * self.chunk_size;
3203 let start = end - self.chunk_size;
3204 // SAFETY: see comments for `RChunksMut::__iterator_get_unchecked` and `self.v`.
3205 unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) }
3206 }
3207}
3208
3209#[stable(feature = "rchunks", since = "1.31.0")]
3210impl<'a, T> DoubleEndedIterator for RChunksExactMut<'a, T> {
3211 #[inline]
3212 fn next_back(&mut self) -> Option<&'a mut [T]> {
3213 if self.v.len() < self.chunk_size {
3214 None
3215 } else {
3216 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3217 let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) };
3218 self.v = tail;
3219 // SAFETY: Nothing else points to or will point to the contents of this slice.
3220 Some(unsafe { &mut *head })
3221 }
3222 }
3223
3224 #[inline]
3225 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
3226 let len = self.len();
3227 if n >= len {
3228 self.v = &mut [];
3229 None
3230 } else {
3231 // now that we know that `n` corresponds to a chunk,
3232 // none of these operations can underflow/overflow
3233 let offset = (len - n) * self.chunk_size;
3234 let start = self.v.len() - offset;
3235 let end = start + self.chunk_size;
3236 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3237 let (tmp, tail) = unsafe { self.v.split_at_mut(end) };
3238 // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3239 let (_, nth_back) = unsafe { tmp.split_at_mut(start) };
3240 self.v = tail;
3241 // SAFETY: Nothing else points to or will point to the contents of this slice.
3242 Some(unsafe { &mut *nth_back })
3243 }
3244 }
3245}
3246
3247#[stable(feature = "rchunks", since = "1.31.0")]
3248impl<T> ExactSizeIterator for RChunksExactMut<'_, T> {
3249 fn is_empty(&self) -> bool {
3250 self.v.is_empty()
3251 }
3252}
3253
3254#[unstable(feature = "trusted_len", issue = "37572")]
3255unsafe impl<T> TrustedLen for RChunksExactMut<'_, T> {}
3256
3257#[stable(feature = "rchunks", since = "1.31.0")]
3258impl<T> FusedIterator for RChunksExactMut<'_, T> {}
3259
3260#[doc(hidden)]
3261#[unstable(feature = "trusted_random_access", issue = "none")]
3262unsafe impl<'a, T> TrustedRandomAccess for RChunksExactMut<'a, T> {}
3263
3264#[doc(hidden)]
3265#[unstable(feature = "trusted_random_access", issue = "none")]
3266unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExactMut<'a, T> {
3267 const MAY_HAVE_SIDE_EFFECT: bool = false;
3268}
3269
3270#[stable(feature = "rchunks", since = "1.31.0")]
3271unsafe impl<T> Send for RChunksExactMut<'_, T> where T: Send {}
3272
3273#[stable(feature = "rchunks", since = "1.31.0")]
3274unsafe impl<T> Sync for RChunksExactMut<'_, T> where T: Sync {}
3275
3276#[doc(hidden)]
3277#[unstable(feature = "trusted_random_access", issue = "none")]
3278unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {}
3279
3280#[doc(hidden)]
3281#[unstable(feature = "trusted_random_access", issue = "none")]
3282unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Iter<'a, T> {
3283 const MAY_HAVE_SIDE_EFFECT: bool = false;
3284}
3285
3286#[doc(hidden)]
3287#[unstable(feature = "trusted_random_access", issue = "none")]
3288unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {}
3289
3290#[doc(hidden)]
3291#[unstable(feature = "trusted_random_access", issue = "none")]
3292unsafe impl<'a, T> TrustedRandomAccessNoCoerce for IterMut<'a, T> {
3293 const MAY_HAVE_SIDE_EFFECT: bool = false;
3294}
3295
3296/// An iterator over slice in (non-overlapping) chunks separated by a predicate.
3297///
3298/// This struct is created by the [`chunk_by`] method on [slices].
3299///
3300/// [`chunk_by`]: slice::chunk_by
3301/// [slices]: slice
3302#[stable(feature = "slice_group_by", since = "1.77.0")]
3303#[must_use = "iterators are lazy and do nothing unless consumed"]
3304pub struct ChunkBy<'a, T: 'a, P> {
3305 slice: &'a [T],
3306 predicate: P,
3307}
3308
3309#[stable(feature = "slice_group_by", since = "1.77.0")]
3310impl<'a, T: 'a, P> ChunkBy<'a, T, P> {
3311 pub(super) fn new(slice: &'a [T], predicate: P) -> Self {
3312 ChunkBy { slice, predicate }
3313 }
3314}
3315
3316#[stable(feature = "slice_group_by", since = "1.77.0")]
3317impl<'a, T: 'a, P> Iterator for ChunkBy<'a, T, P>
3318where
3319 P: FnMut(&T, &T) -> bool,
3320{
3321 type Item = &'a [T];
3322
3323 #[inline]
3324 fn next(&mut self) -> Option<Self::Item> {
3325 if self.slice.is_empty() {
3326 None
3327 } else {
3328 let mut len = 1;
3329 let mut iter = self.slice.windows(2);
3330 while let Some([l, r]) = iter.next() {
3331 if (self.predicate)(l, r) { len += 1 } else { break }
3332 }
3333 let (head, tail) = self.slice.split_at(len);
3334 self.slice = tail;
3335 Some(head)
3336 }
3337 }
3338
3339 #[inline]
3340 fn size_hint(&self) -> (usize, Option<usize>) {
3341 if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
3342 }
3343
3344 #[inline]
3345 fn last(mut self) -> Option<Self::Item> {
3346 self.next_back()
3347 }
3348}
3349
3350#[stable(feature = "slice_group_by", since = "1.77.0")]
3351impl<'a, T: 'a, P> DoubleEndedIterator for ChunkBy<'a, T, P>
3352where
3353 P: FnMut(&T, &T) -> bool,
3354{
3355 #[inline]
3356 fn next_back(&mut self) -> Option<Self::Item> {
3357 if self.slice.is_empty() {
3358 None
3359 } else {
3360 let mut len: usize = 1;
3361 let mut iter: Windows<'_, T> = self.slice.windows(size:2);
3362 while let Some([l: &T, r: &T]) = iter.next_back() {
3363 if (self.predicate)(l, r) { len += 1 } else { break }
3364 }
3365 let (head: &[T], tail: &[T]) = self.slice.split_at(self.slice.len() - len);
3366 self.slice = head;
3367 Some(tail)
3368 }
3369 }
3370}
3371
3372#[stable(feature = "slice_group_by", since = "1.77.0")]
3373impl<'a, T: 'a, P> FusedIterator for ChunkBy<'a, T, P> where P: FnMut(&T, &T) -> bool {}
3374
3375#[stable(feature = "slice_group_by", since = "1.77.0")]
3376impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for ChunkBy<'a, T, P> {
3377 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3378 f.debug_struct("ChunkBy").field(name:"slice", &self.slice).finish()
3379 }
3380}
3381
3382/// An iterator over slice in (non-overlapping) mutable chunks separated
3383/// by a predicate.
3384///
3385/// This struct is created by the [`chunk_by_mut`] method on [slices].
3386///
3387/// [`chunk_by_mut`]: slice::chunk_by_mut
3388/// [slices]: slice
3389#[stable(feature = "slice_group_by", since = "1.77.0")]
3390#[must_use = "iterators are lazy and do nothing unless consumed"]
3391pub struct ChunkByMut<'a, T: 'a, P> {
3392 slice: &'a mut [T],
3393 predicate: P,
3394}
3395
3396#[stable(feature = "slice_group_by", since = "1.77.0")]
3397impl<'a, T: 'a, P> ChunkByMut<'a, T, P> {
3398 pub(super) fn new(slice: &'a mut [T], predicate: P) -> Self {
3399 ChunkByMut { slice, predicate }
3400 }
3401}
3402
3403#[stable(feature = "slice_group_by", since = "1.77.0")]
3404impl<'a, T: 'a, P> Iterator for ChunkByMut<'a, T, P>
3405where
3406 P: FnMut(&T, &T) -> bool,
3407{
3408 type Item = &'a mut [T];
3409
3410 #[inline]
3411 fn next(&mut self) -> Option<Self::Item> {
3412 if self.slice.is_empty() {
3413 None
3414 } else {
3415 let mut len = 1;
3416 let mut iter = self.slice.windows(2);
3417 while let Some([l, r]) = iter.next() {
3418 if (self.predicate)(l, r) { len += 1 } else { break }
3419 }
3420 let slice = mem::take(&mut self.slice);
3421 let (head, tail) = slice.split_at_mut(len);
3422 self.slice = tail;
3423 Some(head)
3424 }
3425 }
3426
3427 #[inline]
3428 fn size_hint(&self) -> (usize, Option<usize>) {
3429 if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
3430 }
3431
3432 #[inline]
3433 fn last(mut self) -> Option<Self::Item> {
3434 self.next_back()
3435 }
3436}
3437
3438#[stable(feature = "slice_group_by", since = "1.77.0")]
3439impl<'a, T: 'a, P> DoubleEndedIterator for ChunkByMut<'a, T, P>
3440where
3441 P: FnMut(&T, &T) -> bool,
3442{
3443 #[inline]
3444 fn next_back(&mut self) -> Option<Self::Item> {
3445 if self.slice.is_empty() {
3446 None
3447 } else {
3448 let mut len: usize = 1;
3449 let mut iter: Windows<'_, T> = self.slice.windows(size:2);
3450 while let Some([l: &T, r: &T]) = iter.next_back() {
3451 if (self.predicate)(l, r) { len += 1 } else { break }
3452 }
3453 let slice: &'a mut [T] = mem::take(&mut self.slice);
3454 let (head: &mut [T], tail: &mut [T]) = slice.split_at_mut(mid:slice.len() - len);
3455 self.slice = head;
3456 Some(tail)
3457 }
3458 }
3459}
3460
3461#[stable(feature = "slice_group_by", since = "1.77.0")]
3462impl<'a, T: 'a, P> FusedIterator for ChunkByMut<'a, T, P> where P: FnMut(&T, &T) -> bool {}
3463
3464#[stable(feature = "slice_group_by", since = "1.77.0")]
3465impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for ChunkByMut<'a, T, P> {
3466 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3467 f.debug_struct("ChunkByMut").field(name:"slice", &self.slice).finish()
3468 }
3469}
3470