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