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