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