1 | //! Definitions of a bunch of iterators for `[T]`. |
2 | |
3 | #[macro_use ] // import iterator! and forward_iterator! |
4 | mod macros; |
5 | |
6 | use super::{from_raw_parts, from_raw_parts_mut}; |
7 | use crate::hint::assert_unchecked; |
8 | use crate::iter::{ |
9 | FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, UncheckedIterator, |
10 | }; |
11 | use crate::marker::PhantomData; |
12 | use crate::mem::{self, SizedTypeProperties}; |
13 | use crate::num::NonZero; |
14 | use crate::ptr::{NonNull, without_provenance, without_provenance_mut}; |
15 | use crate::{cmp, fmt}; |
16 | |
17 | #[stable (feature = "boxed_slice_into_iter" , since = "1.80.0" )] |
18 | impl<T> !Iterator for [T] {} |
19 | |
20 | #[stable (feature = "rust1" , since = "1.0.0" )] |
21 | impl<'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" )] |
31 | impl<'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" ] |
69 | pub 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" )] |
83 | impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { |
84 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
85 | f.debug_tuple(name:"Iter" ).field(&self.as_slice()).finish() |
86 | } |
87 | } |
88 | |
89 | #[stable (feature = "rust1" , since = "1.0.0" )] |
90 | unsafe impl<T: Sync> Sync for Iter<'_, T> {} |
91 | #[stable (feature = "rust1" , since = "1.0.0" )] |
92 | unsafe impl<T: Sync> Send for Iter<'_, T> {} |
93 | |
94 | impl<'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 | |
142 | iterator! {struct Iter -> *const T, &'a T, const, {/* no mut */}, as_ref, { |
143 | fn is_sorted_by<F>(self, mut compare: F) -> bool |
144 | where |
145 | Self: Sized, |
146 | F: FnMut(&Self::Item, &Self::Item) -> bool, |
147 | { |
148 | self.as_slice().is_sorted_by(|a, b| compare(&a, &b)) |
149 | } |
150 | }} |
151 | |
152 | #[stable (feature = "rust1" , since = "1.0.0" )] |
153 | impl<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" )] |
161 | impl<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" ] |
194 | pub 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" )] |
208 | impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { |
209 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
210 | f.debug_tuple(name:"IterMut" ).field(&self.make_slice()).finish() |
211 | } |
212 | } |
213 | |
214 | #[stable (feature = "rust1" , since = "1.0.0" )] |
215 | unsafe impl<T: Sync> Sync for IterMut<'_, T> {} |
216 | #[stable (feature = "rust1" , since = "1.0.0" )] |
217 | unsafe impl<T: Send> Send for IterMut<'_, T> {} |
218 | |
219 | impl<'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" )] |
357 | impl<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 | |
371 | iterator! {struct IterMut -> *mut T, &'a mut T, mut, {mut}, as_mut, {}} |
372 | |
373 | /// An internal abstraction over the splitting iterators, so that |
374 | /// splitn, splitn_mut etc can be implemented once. |
375 | #[doc (hidden)] |
376 | pub(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" ] |
401 | pub struct Split<'a, T: 'a, P> |
402 | where |
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 | |
412 | impl<'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" )] |
434 | impl<T: fmt::Debug, P> fmt::Debug for Split<'_, T, P> |
435 | where |
436 | P: FnMut(&T) -> bool, |
437 | { |
438 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
439 | f.debug_struct("Split" ).field("v" , &self.v).field(name:"finished" , &self.finished).finish() |
440 | } |
441 | } |
442 | |
443 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
444 | #[stable (feature = "rust1" , since = "1.0.0" )] |
445 | impl<T, P> Clone for Split<'_, T, P> |
446 | where |
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" )] |
455 | impl<'a, T, P> Iterator for Split<'a, T, P> |
456 | where |
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" )] |
494 | impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> |
495 | where |
496 | P: FnMut(&T) -> bool, |
497 | { |
498 | #[inline ] |
499 | fn next_back(&mut self) -> Option<&'a [T]> { |
500 | if self.finished { |
501 | return None; |
502 | } |
503 | |
504 | match self.v.iter().rposition(|x: &T| (self.pred)(x)) { |
505 | None => self.finish(), |
506 | Some(idx: usize) => { |
507 | let (left: &[T], right: &[T]) = |
508 | // SAFETY: if v.iter().rposition returns Some(idx), then |
509 | // idx is definitely a valid index for v |
510 | unsafe { (self.v.get_unchecked(..idx), self.v.get_unchecked(index:idx + 1..)) }; |
511 | let ret: Option<&[T]> = Some(right); |
512 | self.v = left; |
513 | ret |
514 | } |
515 | } |
516 | } |
517 | } |
518 | |
519 | impl<'a, T, P> SplitIter for Split<'a, T, P> |
520 | where |
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" )] |
535 | impl<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" ] |
557 | pub struct SplitInclusive<'a, T: 'a, P> |
558 | where |
559 | P: FnMut(&T) -> bool, |
560 | { |
561 | v: &'a [T], |
562 | pred: P, |
563 | finished: bool, |
564 | } |
565 | |
566 | impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitInclusive<'a, T, P> { |
567 | #[inline ] |
568 | pub(super) fn new(slice: &'a [T], pred: P) -> Self { |
569 | let finished: bool = slice.is_empty(); |
570 | Self { v: slice, pred, finished } |
571 | } |
572 | } |
573 | |
574 | #[stable (feature = "split_inclusive" , since = "1.51.0" )] |
575 | impl<T: fmt::Debug, P> fmt::Debug for SplitInclusive<'_, T, P> |
576 | where |
577 | P: FnMut(&T) -> bool, |
578 | { |
579 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
580 | f&mut DebugStruct<'_, '_>.debug_struct("SplitInclusive" ) |
581 | .field("v" , &self.v) |
582 | .field(name:"finished" , &self.finished) |
583 | .finish() |
584 | } |
585 | } |
586 | |
587 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
588 | #[stable (feature = "split_inclusive" , since = "1.51.0" )] |
589 | impl<T, P> Clone for SplitInclusive<'_, T, P> |
590 | where |
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" )] |
599 | impl<'a, T, P> Iterator for SplitInclusive<'a, T, P> |
600 | where |
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" )] |
635 | impl<'a, T, P> DoubleEndedIterator for SplitInclusive<'a, T, P> |
636 | where |
637 | P: FnMut(&T) -> bool, |
638 | { |
639 | #[inline ] |
640 | fn next_back(&mut self) -> Option<&'a [T]> { |
641 | if self.finished { |
642 | return None; |
643 | } |
644 | |
645 | // The last index of self.v is already checked and found to match |
646 | // by the last iteration, so we start searching a new match |
647 | // one index to the left. |
648 | let remainder: &[T] = if self.v.is_empty() { &[] } else { &self.v[..(self.v.len() - 1)] }; |
649 | let idx: usize = remainder.iter().rposition(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(default:0); |
650 | if idx == 0 { |
651 | self.finished = true; |
652 | } |
653 | let ret: Option<&[T]> = Some(&self.v[idx..]); |
654 | self.v = &self.v[..idx]; |
655 | ret |
656 | } |
657 | } |
658 | |
659 | #[stable (feature = "split_inclusive" , since = "1.51.0" )] |
660 | impl<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" ] |
678 | pub struct SplitMut<'a, T: 'a, P> |
679 | where |
680 | P: FnMut(&T) -> bool, |
681 | { |
682 | v: &'a mut [T], |
683 | pred: P, |
684 | finished: bool, |
685 | } |
686 | |
687 | impl<'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" )] |
695 | impl<T: fmt::Debug, P> fmt::Debug for SplitMut<'_, T, P> |
696 | where |
697 | P: FnMut(&T) -> bool, |
698 | { |
699 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
700 | f.debug_struct("SplitMut" ).field("v" , &self.v).field(name:"finished" , &self.finished).finish() |
701 | } |
702 | } |
703 | |
704 | impl<'a, T, P> SplitIter for SplitMut<'a, T, P> |
705 | where |
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" )] |
720 | impl<'a, T, P> Iterator for SplitMut<'a, T, P> |
721 | where |
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" )] |
760 | impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> |
761 | where |
762 | P: FnMut(&T) -> bool, |
763 | { |
764 | #[inline ] |
765 | fn next_back(&mut self) -> Option<&'a mut [T]> { |
766 | if self.finished { |
767 | return None; |
768 | } |
769 | |
770 | let idx_opt: Option = { |
771 | // work around borrowck limitations |
772 | let pred: &mut P = &mut self.pred; |
773 | self.v.iter().rposition(|x: &T| (*pred)(x)) |
774 | }; |
775 | match idx_opt { |
776 | None => self.finish(), |
777 | Some(idx: usize) => { |
778 | let tmp: &'a mut [T] = mem::take(&mut self.v); |
779 | let (head: &mut [T], tail: &mut [T]) = tmp.split_at_mut(mid:idx); |
780 | self.v = head; |
781 | Some(&mut tail[1..]) |
782 | } |
783 | } |
784 | } |
785 | } |
786 | |
787 | #[stable (feature = "fused" , since = "1.26.0" )] |
788 | impl<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" ] |
807 | pub struct SplitInclusiveMut<'a, T: 'a, P> |
808 | where |
809 | P: FnMut(&T) -> bool, |
810 | { |
811 | v: &'a mut [T], |
812 | pred: P, |
813 | finished: bool, |
814 | } |
815 | |
816 | impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitInclusiveMut<'a, T, P> { |
817 | #[inline ] |
818 | pub(super) fn new(slice: &'a mut [T], pred: P) -> Self { |
819 | let finished: bool = slice.is_empty(); |
820 | Self { v: slice, pred, finished } |
821 | } |
822 | } |
823 | |
824 | #[stable (feature = "split_inclusive" , since = "1.51.0" )] |
825 | impl<T: fmt::Debug, P> fmt::Debug for SplitInclusiveMut<'_, T, P> |
826 | where |
827 | P: FnMut(&T) -> bool, |
828 | { |
829 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
830 | f&mut DebugStruct<'_, '_>.debug_struct("SplitInclusiveMut" ) |
831 | .field("v" , &self.v) |
832 | .field(name:"finished" , &self.finished) |
833 | .finish() |
834 | } |
835 | } |
836 | |
837 | #[stable (feature = "split_inclusive" , since = "1.51.0" )] |
838 | impl<'a, T, P> Iterator for SplitInclusiveMut<'a, T, P> |
839 | where |
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" )] |
879 | impl<'a, T, P> DoubleEndedIterator for SplitInclusiveMut<'a, T, P> |
880 | where |
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" )] |
913 | impl<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" ] |
934 | pub struct RSplit<'a, T: 'a, P> |
935 | where |
936 | P: FnMut(&T) -> bool, |
937 | { |
938 | inner: Split<'a, T, P>, |
939 | } |
940 | |
941 | impl<'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" )] |
949 | impl<T: fmt::Debug, P> fmt::Debug for RSplit<'_, T, P> |
950 | where |
951 | P: FnMut(&T) -> bool, |
952 | { |
953 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
954 | f&mut DebugStruct<'_, '_>.debug_struct("RSplit" ) |
955 | .field("v" , &self.inner.v) |
956 | .field(name:"finished" , &self.inner.finished) |
957 | .finish() |
958 | } |
959 | } |
960 | |
961 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
962 | #[stable (feature = "slice_rsplit" , since = "1.27.0" )] |
963 | impl<T, P> Clone for RSplit<'_, T, P> |
964 | where |
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" )] |
973 | impl<'a, T, P> Iterator for RSplit<'a, T, P> |
974 | where |
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" )] |
991 | impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P> |
992 | where |
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" )] |
1002 | impl<'a, T, P> SplitIter for RSplit<'a, T, P> |
1003 | where |
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" )] |
1013 | impl<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" ] |
1031 | pub struct RSplitMut<'a, T: 'a, P> |
1032 | where |
1033 | P: FnMut(&T) -> bool, |
1034 | { |
1035 | inner: SplitMut<'a, T, P>, |
1036 | } |
1037 | |
1038 | impl<'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" )] |
1046 | impl<T: fmt::Debug, P> fmt::Debug for RSplitMut<'_, T, P> |
1047 | where |
1048 | P: FnMut(&T) -> bool, |
1049 | { |
1050 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1051 | f&mut DebugStruct<'_, '_>.debug_struct("RSplitMut" ) |
1052 | .field("v" , &self.inner.v) |
1053 | .field(name:"finished" , &self.inner.finished) |
1054 | .finish() |
1055 | } |
1056 | } |
1057 | |
1058 | #[stable (feature = "slice_rsplit" , since = "1.27.0" )] |
1059 | impl<'a, T, P> SplitIter for RSplitMut<'a, T, P> |
1060 | where |
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" )] |
1070 | impl<'a, T, P> Iterator for RSplitMut<'a, T, P> |
1071 | where |
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" )] |
1088 | impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P> |
1089 | where |
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" )] |
1099 | impl<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)] |
1105 | struct GenericSplitN<I> { |
1106 | iter: I, |
1107 | count: usize, |
1108 | } |
1109 | |
1110 | impl<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" ] |
1157 | pub struct SplitN<'a, T: 'a, P> |
1158 | where |
1159 | P: FnMut(&T) -> bool, |
1160 | { |
1161 | inner: GenericSplitN<Split<'a, T, P>>, |
1162 | } |
1163 | |
1164 | impl<'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" )] |
1172 | impl<T: fmt::Debug, P> fmt::Debug for SplitN<'_, T, P> |
1173 | where |
1174 | P: FnMut(&T) -> bool, |
1175 | { |
1176 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1177 | f.debug_struct("SplitN" ).field(name:"inner" , &self.inner).finish() |
1178 | } |
1179 | } |
1180 | |
1181 | /// An iterator over subslices separated by elements that match a |
1182 | /// predicate function, limited to a given number of splits, starting |
1183 | /// from the end of the slice. |
1184 | /// |
1185 | /// This struct is created by the [`rsplitn`] method on [slices]. |
1186 | /// |
1187 | /// # Example |
1188 | /// |
1189 | /// ``` |
1190 | /// let slice = [10, 40, 30, 20, 60, 50]; |
1191 | /// let mut iter = slice.rsplitn(2, |num| *num % 3 == 0); |
1192 | /// assert_eq!(iter.next(), Some(&[50][..])); |
1193 | /// assert_eq!(iter.next(), Some(&[10, 40, 30, 20][..])); |
1194 | /// assert_eq!(iter.next(), None); |
1195 | /// ``` |
1196 | /// |
1197 | /// [`rsplitn`]: slice::rsplitn |
1198 | /// [slices]: slice |
1199 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1200 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
1201 | pub struct RSplitN<'a, T: 'a, P> |
1202 | where |
1203 | P: FnMut(&T) -> bool, |
1204 | { |
1205 | inner: GenericSplitN<RSplit<'a, T, P>>, |
1206 | } |
1207 | |
1208 | impl<'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" )] |
1216 | impl<T: fmt::Debug, P> fmt::Debug for RSplitN<'_, T, P> |
1217 | where |
1218 | P: FnMut(&T) -> bool, |
1219 | { |
1220 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1221 | f.debug_struct("RSplitN" ).field(name:"inner" , &self.inner).finish() |
1222 | } |
1223 | } |
1224 | |
1225 | /// An iterator over subslices separated by elements that match a predicate |
1226 | /// function, limited to a given number of splits. |
1227 | /// |
1228 | /// This struct is created by the [`splitn_mut`] method on [slices]. |
1229 | /// |
1230 | /// # Example |
1231 | /// |
1232 | /// ``` |
1233 | /// let mut slice = [10, 40, 30, 20, 60, 50]; |
1234 | /// let iter = slice.splitn_mut(2, |num| *num % 3 == 0); |
1235 | /// ``` |
1236 | /// |
1237 | /// [`splitn_mut`]: slice::splitn_mut |
1238 | /// [slices]: slice |
1239 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1240 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
1241 | pub struct SplitNMut<'a, T: 'a, P> |
1242 | where |
1243 | P: FnMut(&T) -> bool, |
1244 | { |
1245 | inner: GenericSplitN<SplitMut<'a, T, P>>, |
1246 | } |
1247 | |
1248 | impl<'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" )] |
1256 | impl<T: fmt::Debug, P> fmt::Debug for SplitNMut<'_, T, P> |
1257 | where |
1258 | P: FnMut(&T) -> bool, |
1259 | { |
1260 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1261 | f.debug_struct("SplitNMut" ).field(name:"inner" , &self.inner).finish() |
1262 | } |
1263 | } |
1264 | |
1265 | /// An iterator over subslices separated by elements that match a |
1266 | /// predicate function, limited to a given number of splits, starting |
1267 | /// from the end of the slice. |
1268 | /// |
1269 | /// This struct is created by the [`rsplitn_mut`] method on [slices]. |
1270 | /// |
1271 | /// # Example |
1272 | /// |
1273 | /// ``` |
1274 | /// let mut slice = [10, 40, 30, 20, 60, 50]; |
1275 | /// let iter = slice.rsplitn_mut(2, |num| *num % 3 == 0); |
1276 | /// ``` |
1277 | /// |
1278 | /// [`rsplitn_mut`]: slice::rsplitn_mut |
1279 | /// [slices]: slice |
1280 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1281 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
1282 | pub struct RSplitNMut<'a, T: 'a, P> |
1283 | where |
1284 | P: FnMut(&T) -> bool, |
1285 | { |
1286 | inner: GenericSplitN<RSplitMut<'a, T, P>>, |
1287 | } |
1288 | |
1289 | impl<'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" )] |
1297 | impl<T: fmt::Debug, P> fmt::Debug for RSplitNMut<'_, T, P> |
1298 | where |
1299 | P: FnMut(&T) -> bool, |
1300 | { |
1301 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
1302 | f.debug_struct("RSplitNMut" ).field(name:"inner" , &self.inner).finish() |
1303 | } |
1304 | } |
1305 | |
1306 | forward_iterator! { SplitN: T, &'a [T] } |
1307 | forward_iterator! { RSplitN: T, &'a [T] } |
1308 | forward_iterator! { SplitNMut: T, &'a mut [T] } |
1309 | forward_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" ] |
1331 | pub struct Windows<'a, T: 'a> { |
1332 | v: &'a [T], |
1333 | size: NonZero<usize>, |
1334 | } |
1335 | |
1336 | impl<'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" )] |
1345 | impl<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" )] |
1352 | impl<'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" )] |
1416 | impl<'a, T> DoubleEndedIterator for Windows<'a, T> { |
1417 | #[inline ] |
1418 | fn next_back(&mut self) -> Option<&'a [T]> { |
1419 | if self.size.get() > self.v.len() { |
1420 | None |
1421 | } else { |
1422 | let ret = Some(&self.v[self.v.len() - self.size.get()..]); |
1423 | self.v = &self.v[..self.v.len() - 1]; |
1424 | ret |
1425 | } |
1426 | } |
1427 | |
1428 | #[inline ] |
1429 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
1430 | let (end, overflow) = self.v.len().overflowing_sub(n); |
1431 | if end < self.size.get() || overflow { |
1432 | self.v = &self.v[..0]; // cheaper than &[] |
1433 | None |
1434 | } else { |
1435 | let ret = &self.v[end - self.size.get()..end]; |
1436 | self.v = &self.v[..end - 1]; |
1437 | Some(ret) |
1438 | } |
1439 | } |
1440 | } |
1441 | |
1442 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1443 | impl<T> ExactSizeIterator for Windows<'_, T> {} |
1444 | |
1445 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
1446 | unsafe impl<T> TrustedLen for Windows<'_, T> {} |
1447 | |
1448 | #[stable (feature = "fused" , since = "1.26.0" )] |
1449 | impl<T> FusedIterator for Windows<'_, T> {} |
1450 | |
1451 | #[doc (hidden)] |
1452 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
1453 | unsafe impl<'a, T> TrustedRandomAccess for Windows<'a, T> {} |
1454 | |
1455 | #[doc (hidden)] |
1456 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
1457 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Windows<'a, T> { |
1458 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
1459 | } |
1460 | |
1461 | /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a |
1462 | /// time), starting at the beginning of the slice. |
1463 | /// |
1464 | /// When the slice len is not evenly divided by the chunk size, the last slice |
1465 | /// of the iteration will be the remainder. |
1466 | /// |
1467 | /// This struct is created by the [`chunks`] method on [slices]. |
1468 | /// |
1469 | /// # Example |
1470 | /// |
1471 | /// ``` |
1472 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1473 | /// let mut iter = slice.chunks(2); |
1474 | /// assert_eq!(iter.next(), Some(&['l' , 'o' ][..])); |
1475 | /// assert_eq!(iter.next(), Some(&['r' , 'e' ][..])); |
1476 | /// assert_eq!(iter.next(), Some(&['m' ][..])); |
1477 | /// assert_eq!(iter.next(), None); |
1478 | /// ``` |
1479 | /// |
1480 | /// [`chunks`]: slice::chunks |
1481 | /// [slices]: slice |
1482 | #[derive (Debug)] |
1483 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1484 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
1485 | pub struct Chunks<'a, T: 'a> { |
1486 | v: &'a [T], |
1487 | chunk_size: usize, |
1488 | } |
1489 | |
1490 | impl<'a, T: 'a> Chunks<'a, T> { |
1491 | #[inline ] |
1492 | pub(super) const fn new(slice: &'a [T], size: usize) -> Self { |
1493 | Self { v: slice, chunk_size: size } |
1494 | } |
1495 | } |
1496 | |
1497 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
1498 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1499 | impl<T> Clone for Chunks<'_, T> { |
1500 | fn clone(&self) -> Self { |
1501 | Chunks { v: self.v, chunk_size: self.chunk_size } |
1502 | } |
1503 | } |
1504 | |
1505 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1506 | impl<'a, T> Iterator for Chunks<'a, T> { |
1507 | type Item = &'a [T]; |
1508 | |
1509 | #[inline ] |
1510 | fn next(&mut self) -> Option<&'a [T]> { |
1511 | if self.v.is_empty() { |
1512 | None |
1513 | } else { |
1514 | let chunksz = cmp::min(self.v.len(), self.chunk_size); |
1515 | let (fst, snd) = self.v.split_at(chunksz); |
1516 | self.v = snd; |
1517 | Some(fst) |
1518 | } |
1519 | } |
1520 | |
1521 | #[inline ] |
1522 | fn size_hint(&self) -> (usize, Option<usize>) { |
1523 | if self.v.is_empty() { |
1524 | (0, Some(0)) |
1525 | } else { |
1526 | let n = self.v.len() / self.chunk_size; |
1527 | let rem = self.v.len() % self.chunk_size; |
1528 | let n = if rem > 0 { n + 1 } else { n }; |
1529 | (n, Some(n)) |
1530 | } |
1531 | } |
1532 | |
1533 | #[inline ] |
1534 | fn count(self) -> usize { |
1535 | self.len() |
1536 | } |
1537 | |
1538 | #[inline ] |
1539 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
1540 | let (start, overflow) = n.overflowing_mul(self.chunk_size); |
1541 | // min(len) makes a wrong start harmless, but enables optimizing this to brachless code |
1542 | let chunk_start = &self.v[start.min(self.v.len())..]; |
1543 | let (nth, remainder) = chunk_start.split_at(self.chunk_size.min(chunk_start.len())); |
1544 | if !overflow && start < self.v.len() { |
1545 | self.v = remainder; |
1546 | Some(nth) |
1547 | } else { |
1548 | self.v = &self.v[..0]; // cheaper than &[] |
1549 | None |
1550 | } |
1551 | } |
1552 | |
1553 | #[inline ] |
1554 | fn last(self) -> Option<Self::Item> { |
1555 | if self.v.is_empty() { |
1556 | None |
1557 | } else { |
1558 | let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size; |
1559 | Some(&self.v[start..]) |
1560 | } |
1561 | } |
1562 | |
1563 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
1564 | let start = idx * self.chunk_size; |
1565 | // SAFETY: the caller guarantees that `i` is in bounds, |
1566 | // which means that `start` must be in bounds of the |
1567 | // underlying `self.v` slice, and we made sure that `len` |
1568 | // is also in bounds of `self.v`. Thus, `start` cannot overflow |
1569 | // an `isize`, and the slice constructed by `from_raw_parts` |
1570 | // is a subslice of `self.v` which is guaranteed to be valid |
1571 | // for the lifetime `'a` of `self.v`. |
1572 | unsafe { |
1573 | let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size); |
1574 | from_raw_parts(self.v.as_ptr().add(start), len) |
1575 | } |
1576 | } |
1577 | } |
1578 | |
1579 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1580 | impl<'a, T> DoubleEndedIterator for Chunks<'a, T> { |
1581 | #[inline ] |
1582 | fn next_back(&mut self) -> Option<&'a [T]> { |
1583 | if self.v.is_empty() { |
1584 | None |
1585 | } else { |
1586 | let remainder = self.v.len() % self.chunk_size; |
1587 | let chunksz = if remainder != 0 { remainder } else { self.chunk_size }; |
1588 | // SAFETY: split_at_unchecked requires the argument be less than or |
1589 | // equal to the length. This is guaranteed, but subtle: `chunksz` |
1590 | // will always either be `self.v.len() % self.chunk_size`, which |
1591 | // will always evaluate to strictly less than `self.v.len()` (or |
1592 | // panic, in the case that `self.chunk_size` is zero), or it can be |
1593 | // `self.chunk_size`, in the case that the length is exactly |
1594 | // divisible by the chunk size. |
1595 | // |
1596 | // While it seems like using `self.chunk_size` in this case could |
1597 | // lead to a value greater than `self.v.len()`, it cannot: if |
1598 | // `self.chunk_size` were greater than `self.v.len()`, then |
1599 | // `self.v.len() % self.chunk_size` would return nonzero (note that |
1600 | // in this branch of the `if`, we already know that `self.v` is |
1601 | // non-empty). |
1602 | let (fst, snd) = unsafe { self.v.split_at_unchecked(self.v.len() - chunksz) }; |
1603 | self.v = fst; |
1604 | Some(snd) |
1605 | } |
1606 | } |
1607 | |
1608 | #[inline ] |
1609 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
1610 | let len = self.len(); |
1611 | if n >= len { |
1612 | self.v = &self.v[..0]; // cheaper than &[] |
1613 | None |
1614 | } else { |
1615 | let start = (len - 1 - n) * self.chunk_size; |
1616 | let end = match start.checked_add(self.chunk_size) { |
1617 | Some(res) => cmp::min(self.v.len(), res), |
1618 | None => self.v.len(), |
1619 | }; |
1620 | let nth_back = &self.v[start..end]; |
1621 | self.v = &self.v[..start]; |
1622 | Some(nth_back) |
1623 | } |
1624 | } |
1625 | } |
1626 | |
1627 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1628 | impl<T> ExactSizeIterator for Chunks<'_, T> {} |
1629 | |
1630 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
1631 | unsafe impl<T> TrustedLen for Chunks<'_, T> {} |
1632 | |
1633 | #[stable (feature = "fused" , since = "1.26.0" )] |
1634 | impl<T> FusedIterator for Chunks<'_, T> {} |
1635 | |
1636 | #[doc (hidden)] |
1637 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
1638 | unsafe impl<'a, T> TrustedRandomAccess for Chunks<'a, T> {} |
1639 | |
1640 | #[doc (hidden)] |
1641 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
1642 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Chunks<'a, T> { |
1643 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
1644 | } |
1645 | |
1646 | /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size` |
1647 | /// elements at a time), starting at the beginning of the slice. |
1648 | /// |
1649 | /// When the slice len is not evenly divided by the chunk size, the last slice |
1650 | /// of the iteration will be the remainder. |
1651 | /// |
1652 | /// This struct is created by the [`chunks_mut`] method on [slices]. |
1653 | /// |
1654 | /// # Example |
1655 | /// |
1656 | /// ``` |
1657 | /// let mut slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1658 | /// let iter = slice.chunks_mut(2); |
1659 | /// ``` |
1660 | /// |
1661 | /// [`chunks_mut`]: slice::chunks_mut |
1662 | /// [slices]: slice |
1663 | #[derive (Debug)] |
1664 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1665 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
1666 | pub struct ChunksMut<'a, T: 'a> { |
1667 | /// # Safety |
1668 | /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally, |
1669 | /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot |
1670 | /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing |
1671 | /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw |
1672 | /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap. |
1673 | v: *mut [T], |
1674 | chunk_size: usize, |
1675 | _marker: PhantomData<&'a mut T>, |
1676 | } |
1677 | |
1678 | impl<'a, T: 'a> ChunksMut<'a, T> { |
1679 | #[inline ] |
1680 | pub(super) const fn new(slice: &'a mut [T], size: usize) -> Self { |
1681 | Self { v: slice, chunk_size: size, _marker: PhantomData } |
1682 | } |
1683 | } |
1684 | |
1685 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1686 | impl<'a, T> Iterator for ChunksMut<'a, T> { |
1687 | type Item = &'a mut [T]; |
1688 | |
1689 | #[inline ] |
1690 | fn next(&mut self) -> Option<&'a mut [T]> { |
1691 | if self.v.is_empty() { |
1692 | None |
1693 | } else { |
1694 | let sz = cmp::min(self.v.len(), self.chunk_size); |
1695 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
1696 | let (head, tail) = unsafe { self.v.split_at_mut(sz) }; |
1697 | self.v = tail; |
1698 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
1699 | Some(unsafe { &mut *head }) |
1700 | } |
1701 | } |
1702 | |
1703 | #[inline ] |
1704 | fn size_hint(&self) -> (usize, Option<usize>) { |
1705 | if self.v.is_empty() { |
1706 | (0, Some(0)) |
1707 | } else { |
1708 | let n = self.v.len() / self.chunk_size; |
1709 | let rem = self.v.len() % self.chunk_size; |
1710 | let n = if rem > 0 { n + 1 } else { n }; |
1711 | (n, Some(n)) |
1712 | } |
1713 | } |
1714 | |
1715 | #[inline ] |
1716 | fn count(self) -> usize { |
1717 | self.len() |
1718 | } |
1719 | |
1720 | #[inline ] |
1721 | fn nth(&mut self, n: usize) -> Option<&'a mut [T]> { |
1722 | let (start, overflow) = n.overflowing_mul(self.chunk_size); |
1723 | if start >= self.v.len() || overflow { |
1724 | self.v = &mut []; |
1725 | None |
1726 | } else { |
1727 | let end = match start.checked_add(self.chunk_size) { |
1728 | Some(sum) => cmp::min(self.v.len(), sum), |
1729 | None => self.v.len(), |
1730 | }; |
1731 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
1732 | let (head, tail) = unsafe { self.v.split_at_mut(end) }; |
1733 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
1734 | let (_, nth) = unsafe { head.split_at_mut(start) }; |
1735 | self.v = tail; |
1736 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
1737 | Some(unsafe { &mut *nth }) |
1738 | } |
1739 | } |
1740 | |
1741 | #[inline ] |
1742 | fn last(self) -> Option<Self::Item> { |
1743 | if self.v.is_empty() { |
1744 | None |
1745 | } else { |
1746 | let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size; |
1747 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
1748 | Some(unsafe { &mut *self.v.get_unchecked_mut(start..) }) |
1749 | } |
1750 | } |
1751 | |
1752 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
1753 | let start = idx * self.chunk_size; |
1754 | // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`. |
1755 | // |
1756 | // Also note that the caller also guarantees that we're never called |
1757 | // with the same index again, and that no other methods that will |
1758 | // access this subslice are called, so it is valid for the returned |
1759 | // slice to be mutable. |
1760 | unsafe { |
1761 | let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size); |
1762 | from_raw_parts_mut(self.v.as_mut_ptr().add(start), len) |
1763 | } |
1764 | } |
1765 | } |
1766 | |
1767 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1768 | impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> { |
1769 | #[inline ] |
1770 | fn next_back(&mut self) -> Option<&'a mut [T]> { |
1771 | if self.v.is_empty() { |
1772 | None |
1773 | } else { |
1774 | let remainder = self.v.len() % self.chunk_size; |
1775 | let sz = if remainder != 0 { remainder } else { self.chunk_size }; |
1776 | let len = self.v.len(); |
1777 | // SAFETY: Similar to `Chunks::next_back` |
1778 | let (head, tail) = unsafe { self.v.split_at_mut_unchecked(len - sz) }; |
1779 | self.v = head; |
1780 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
1781 | Some(unsafe { &mut *tail }) |
1782 | } |
1783 | } |
1784 | |
1785 | #[inline ] |
1786 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
1787 | let len = self.len(); |
1788 | if n >= len { |
1789 | self.v = &mut []; |
1790 | None |
1791 | } else { |
1792 | let start = (len - 1 - n) * self.chunk_size; |
1793 | let end = match start.checked_add(self.chunk_size) { |
1794 | Some(res) => cmp::min(self.v.len(), res), |
1795 | None => self.v.len(), |
1796 | }; |
1797 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
1798 | let (temp, _tail) = unsafe { self.v.split_at_mut(end) }; |
1799 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
1800 | let (head, nth_back) = unsafe { temp.split_at_mut(start) }; |
1801 | self.v = head; |
1802 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
1803 | Some(unsafe { &mut *nth_back }) |
1804 | } |
1805 | } |
1806 | } |
1807 | |
1808 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1809 | impl<T> ExactSizeIterator for ChunksMut<'_, T> {} |
1810 | |
1811 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
1812 | unsafe impl<T> TrustedLen for ChunksMut<'_, T> {} |
1813 | |
1814 | #[stable (feature = "fused" , since = "1.26.0" )] |
1815 | impl<T> FusedIterator for ChunksMut<'_, T> {} |
1816 | |
1817 | #[doc (hidden)] |
1818 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
1819 | unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {} |
1820 | |
1821 | #[doc (hidden)] |
1822 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
1823 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksMut<'a, T> { |
1824 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
1825 | } |
1826 | |
1827 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1828 | unsafe impl<T> Send for ChunksMut<'_, T> where T: Send {} |
1829 | |
1830 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1831 | unsafe impl<T> Sync for ChunksMut<'_, T> where T: Sync {} |
1832 | |
1833 | /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a |
1834 | /// time), starting at the beginning of the slice. |
1835 | /// |
1836 | /// When the slice len is not evenly divided by the chunk size, the last |
1837 | /// up to `chunk_size-1` elements will be omitted but can be retrieved from |
1838 | /// the [`remainder`] function from the iterator. |
1839 | /// |
1840 | /// This struct is created by the [`chunks_exact`] method on [slices]. |
1841 | /// |
1842 | /// # Example |
1843 | /// |
1844 | /// ``` |
1845 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1846 | /// let mut iter = slice.chunks_exact(2); |
1847 | /// assert_eq!(iter.next(), Some(&['l' , 'o' ][..])); |
1848 | /// assert_eq!(iter.next(), Some(&['r' , 'e' ][..])); |
1849 | /// assert_eq!(iter.next(), None); |
1850 | /// ``` |
1851 | /// |
1852 | /// [`chunks_exact`]: slice::chunks_exact |
1853 | /// [`remainder`]: ChunksExact::remainder |
1854 | /// [slices]: slice |
1855 | #[derive (Debug)] |
1856 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1857 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
1858 | pub struct ChunksExact<'a, T: 'a> { |
1859 | v: &'a [T], |
1860 | rem: &'a [T], |
1861 | chunk_size: usize, |
1862 | } |
1863 | |
1864 | impl<'a, T> ChunksExact<'a, T> { |
1865 | #[inline ] |
1866 | pub(super) const fn new(slice: &'a [T], chunk_size: usize) -> Self { |
1867 | let rem = slice.len() % chunk_size; |
1868 | let fst_len = slice.len() - rem; |
1869 | // SAFETY: 0 <= fst_len <= slice.len() by construction above |
1870 | let (fst, snd) = unsafe { slice.split_at_unchecked(fst_len) }; |
1871 | Self { v: fst, rem: snd, chunk_size } |
1872 | } |
1873 | |
1874 | /// Returns the remainder of the original slice that is not going to be |
1875 | /// returned by the iterator. The returned slice has at most `chunk_size-1` |
1876 | /// elements. |
1877 | /// |
1878 | /// # Example |
1879 | /// |
1880 | /// ``` |
1881 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1882 | /// let mut iter = slice.chunks_exact(2); |
1883 | /// assert_eq!(iter.remainder(), &['m' ][..]); |
1884 | /// assert_eq!(iter.next(), Some(&['l' , 'o' ][..])); |
1885 | /// assert_eq!(iter.remainder(), &['m' ][..]); |
1886 | /// assert_eq!(iter.next(), Some(&['r' , 'e' ][..])); |
1887 | /// assert_eq!(iter.remainder(), &['m' ][..]); |
1888 | /// assert_eq!(iter.next(), None); |
1889 | /// assert_eq!(iter.remainder(), &['m' ][..]); |
1890 | /// ``` |
1891 | #[must_use ] |
1892 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1893 | pub fn remainder(&self) -> &'a [T] { |
1894 | self.rem |
1895 | } |
1896 | } |
1897 | |
1898 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
1899 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1900 | impl<T> Clone for ChunksExact<'_, T> { |
1901 | fn clone(&self) -> Self { |
1902 | ChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size } |
1903 | } |
1904 | } |
1905 | |
1906 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1907 | impl<'a, T> Iterator for ChunksExact<'a, T> { |
1908 | type Item = &'a [T]; |
1909 | |
1910 | #[inline ] |
1911 | fn next(&mut self) -> Option<&'a [T]> { |
1912 | if self.v.len() < self.chunk_size { |
1913 | None |
1914 | } else { |
1915 | let (fst, snd) = self.v.split_at(self.chunk_size); |
1916 | self.v = snd; |
1917 | Some(fst) |
1918 | } |
1919 | } |
1920 | |
1921 | #[inline ] |
1922 | fn size_hint(&self) -> (usize, Option<usize>) { |
1923 | let n = self.v.len() / self.chunk_size; |
1924 | (n, Some(n)) |
1925 | } |
1926 | |
1927 | #[inline ] |
1928 | fn count(self) -> usize { |
1929 | self.len() |
1930 | } |
1931 | |
1932 | #[inline ] |
1933 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
1934 | let (start, overflow) = n.overflowing_mul(self.chunk_size); |
1935 | if start >= self.v.len() || overflow { |
1936 | self.v = &self.v[..0]; // cheaper than &[] |
1937 | None |
1938 | } else { |
1939 | let (_, snd) = self.v.split_at(start); |
1940 | self.v = snd; |
1941 | self.next() |
1942 | } |
1943 | } |
1944 | |
1945 | #[inline ] |
1946 | fn last(mut self) -> Option<Self::Item> { |
1947 | self.next_back() |
1948 | } |
1949 | |
1950 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
1951 | let start = idx * self.chunk_size; |
1952 | // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`. |
1953 | unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) } |
1954 | } |
1955 | } |
1956 | |
1957 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1958 | impl<'a, T> DoubleEndedIterator for ChunksExact<'a, T> { |
1959 | #[inline ] |
1960 | fn next_back(&mut self) -> Option<&'a [T]> { |
1961 | if self.v.len() < self.chunk_size { |
1962 | None |
1963 | } else { |
1964 | let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size); |
1965 | self.v = fst; |
1966 | Some(snd) |
1967 | } |
1968 | } |
1969 | |
1970 | #[inline ] |
1971 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
1972 | let len = self.len(); |
1973 | if n >= len { |
1974 | self.v = &self.v[..0]; // cheaper than &[] |
1975 | None |
1976 | } else { |
1977 | let start = (len - 1 - n) * self.chunk_size; |
1978 | let end = start + self.chunk_size; |
1979 | let nth_back = &self.v[start..end]; |
1980 | self.v = &self.v[..start]; |
1981 | Some(nth_back) |
1982 | } |
1983 | } |
1984 | } |
1985 | |
1986 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1987 | impl<T> ExactSizeIterator for ChunksExact<'_, T> { |
1988 | fn is_empty(&self) -> bool { |
1989 | self.v.is_empty() |
1990 | } |
1991 | } |
1992 | |
1993 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
1994 | unsafe impl<T> TrustedLen for ChunksExact<'_, T> {} |
1995 | |
1996 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1997 | impl<T> FusedIterator for ChunksExact<'_, T> {} |
1998 | |
1999 | #[doc (hidden)] |
2000 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
2001 | unsafe impl<'a, T> TrustedRandomAccess for ChunksExact<'a, T> {} |
2002 | |
2003 | #[doc (hidden)] |
2004 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
2005 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExact<'a, T> { |
2006 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
2007 | } |
2008 | |
2009 | /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size` |
2010 | /// elements at a time), starting at the beginning of the slice. |
2011 | /// |
2012 | /// When the slice len is not evenly divided by the chunk size, the last up to |
2013 | /// `chunk_size-1` elements will be omitted but can be retrieved from the |
2014 | /// [`into_remainder`] function from the iterator. |
2015 | /// |
2016 | /// This struct is created by the [`chunks_exact_mut`] method on [slices]. |
2017 | /// |
2018 | /// # Example |
2019 | /// |
2020 | /// ``` |
2021 | /// let mut slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
2022 | /// let iter = slice.chunks_exact_mut(2); |
2023 | /// ``` |
2024 | /// |
2025 | /// [`chunks_exact_mut`]: slice::chunks_exact_mut |
2026 | /// [`into_remainder`]: ChunksExactMut::into_remainder |
2027 | /// [slices]: slice |
2028 | #[derive (Debug)] |
2029 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
2030 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
2031 | pub struct ChunksExactMut<'a, T: 'a> { |
2032 | /// # Safety |
2033 | /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally, |
2034 | /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot |
2035 | /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing |
2036 | /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw |
2037 | /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap. |
2038 | v: *mut [T], |
2039 | rem: &'a mut [T], // The iterator never yields from here, so this can be unique |
2040 | chunk_size: usize, |
2041 | _marker: PhantomData<&'a mut T>, |
2042 | } |
2043 | |
2044 | impl<'a, T> ChunksExactMut<'a, T> { |
2045 | #[inline ] |
2046 | pub(super) const fn new(slice: &'a mut [T], chunk_size: usize) -> Self { |
2047 | let rem: usize = slice.len() % chunk_size; |
2048 | let fst_len: usize = slice.len() - rem; |
2049 | // SAFETY: 0 <= fst_len <= slice.len() by construction above |
2050 | let (fst: &mut [T], snd: &mut [T]) = unsafe { slice.split_at_mut_unchecked(mid:fst_len) }; |
2051 | Self { v: fst, rem: snd, chunk_size, _marker: PhantomData } |
2052 | } |
2053 | |
2054 | /// Returns the remainder of the original slice that is not going to be |
2055 | /// returned by the iterator. The returned slice has at most `chunk_size-1` |
2056 | /// elements. |
2057 | #[must_use = "`self` will be dropped if the result is not used" ] |
2058 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
2059 | pub fn into_remainder(self) -> &'a mut [T] { |
2060 | self.rem |
2061 | } |
2062 | } |
2063 | |
2064 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
2065 | impl<'a, T> Iterator for ChunksExactMut<'a, T> { |
2066 | type Item = &'a mut [T]; |
2067 | |
2068 | #[inline ] |
2069 | fn next(&mut self) -> Option<&'a mut [T]> { |
2070 | if self.v.len() < self.chunk_size { |
2071 | None |
2072 | } else { |
2073 | // SAFETY: self.chunk_size is inbounds because we compared above against self.v.len() |
2074 | let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) }; |
2075 | self.v = tail; |
2076 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
2077 | Some(unsafe { &mut *head }) |
2078 | } |
2079 | } |
2080 | |
2081 | #[inline ] |
2082 | fn size_hint(&self) -> (usize, Option<usize>) { |
2083 | let n = self.v.len() / self.chunk_size; |
2084 | (n, Some(n)) |
2085 | } |
2086 | |
2087 | #[inline ] |
2088 | fn count(self) -> usize { |
2089 | self.len() |
2090 | } |
2091 | |
2092 | #[inline ] |
2093 | fn nth(&mut self, n: usize) -> Option<&'a mut [T]> { |
2094 | let (start, overflow) = n.overflowing_mul(self.chunk_size); |
2095 | if start >= self.v.len() || overflow { |
2096 | self.v = &mut []; |
2097 | None |
2098 | } else { |
2099 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
2100 | let (_, snd) = unsafe { self.v.split_at_mut(start) }; |
2101 | self.v = snd; |
2102 | self.next() |
2103 | } |
2104 | } |
2105 | |
2106 | #[inline ] |
2107 | fn last(mut self) -> Option<Self::Item> { |
2108 | self.next_back() |
2109 | } |
2110 | |
2111 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
2112 | let start = idx * self.chunk_size; |
2113 | // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`. |
2114 | unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) } |
2115 | } |
2116 | } |
2117 | |
2118 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
2119 | impl<'a, T> DoubleEndedIterator for ChunksExactMut<'a, T> { |
2120 | #[inline ] |
2121 | fn next_back(&mut self) -> Option<&'a mut [T]> { |
2122 | if self.v.len() < self.chunk_size { |
2123 | None |
2124 | } else { |
2125 | // SAFETY: This subtraction is inbounds because of the check above |
2126 | let (head, tail) = unsafe { self.v.split_at_mut(self.v.len() - self.chunk_size) }; |
2127 | self.v = head; |
2128 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
2129 | Some(unsafe { &mut *tail }) |
2130 | } |
2131 | } |
2132 | |
2133 | #[inline ] |
2134 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
2135 | let len = self.len(); |
2136 | if n >= len { |
2137 | self.v = &mut []; |
2138 | None |
2139 | } else { |
2140 | let start = (len - 1 - n) * self.chunk_size; |
2141 | let end = start + self.chunk_size; |
2142 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
2143 | let (temp, _tail) = unsafe { mem::replace(&mut self.v, &mut []).split_at_mut(end) }; |
2144 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
2145 | let (head, nth_back) = unsafe { temp.split_at_mut(start) }; |
2146 | self.v = head; |
2147 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
2148 | Some(unsafe { &mut *nth_back }) |
2149 | } |
2150 | } |
2151 | } |
2152 | |
2153 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
2154 | impl<T> ExactSizeIterator for ChunksExactMut<'_, T> { |
2155 | fn is_empty(&self) -> bool { |
2156 | self.v.is_empty() |
2157 | } |
2158 | } |
2159 | |
2160 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
2161 | unsafe impl<T> TrustedLen for ChunksExactMut<'_, T> {} |
2162 | |
2163 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
2164 | impl<T> FusedIterator for ChunksExactMut<'_, T> {} |
2165 | |
2166 | #[doc (hidden)] |
2167 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
2168 | unsafe impl<'a, T> TrustedRandomAccess for ChunksExactMut<'a, T> {} |
2169 | |
2170 | #[doc (hidden)] |
2171 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
2172 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExactMut<'a, T> { |
2173 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
2174 | } |
2175 | |
2176 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
2177 | unsafe impl<T> Send for ChunksExactMut<'_, T> where T: Send {} |
2178 | |
2179 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
2180 | unsafe impl<T> Sync for ChunksExactMut<'_, T> where T: Sync {} |
2181 | |
2182 | /// A windowed iterator over a slice in overlapping chunks (`N` elements at a |
2183 | /// time), starting at the beginning of the slice |
2184 | /// |
2185 | /// This struct is created by the [`array_windows`] method on [slices]. |
2186 | /// |
2187 | /// # Example |
2188 | /// |
2189 | /// ``` |
2190 | /// #![feature(array_windows)] |
2191 | /// |
2192 | /// let slice = [0, 1, 2, 3]; |
2193 | /// let mut iter = slice.array_windows::<2>(); |
2194 | /// assert_eq!(iter.next(), Some(&[0, 1])); |
2195 | /// assert_eq!(iter.next(), Some(&[1, 2])); |
2196 | /// assert_eq!(iter.next(), Some(&[2, 3])); |
2197 | /// assert_eq!(iter.next(), None); |
2198 | /// ``` |
2199 | /// |
2200 | /// [`array_windows`]: slice::array_windows |
2201 | /// [slices]: slice |
2202 | #[derive (Debug, Clone, Copy)] |
2203 | #[unstable (feature = "array_windows" , issue = "75027" )] |
2204 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
2205 | pub struct ArrayWindows<'a, T: 'a, const N: usize> { |
2206 | slice_head: *const T, |
2207 | num: usize, |
2208 | marker: PhantomData<&'a [T; N]>, |
2209 | } |
2210 | |
2211 | impl<'a, T: 'a, const N: usize> ArrayWindows<'a, T, N> { |
2212 | #[inline ] |
2213 | pub(super) const fn new(slice: &'a [T]) -> Self { |
2214 | let num_windows: usize = slice.len().saturating_sub(N - 1); |
2215 | Self { slice_head: slice.as_ptr(), num: num_windows, marker: PhantomData } |
2216 | } |
2217 | } |
2218 | |
2219 | #[unstable (feature = "array_windows" , issue = "75027" )] |
2220 | impl<'a, T, const N: usize> Iterator for ArrayWindows<'a, T, N> { |
2221 | type Item = &'a [T; N]; |
2222 | |
2223 | #[inline ] |
2224 | fn next(&mut self) -> Option<Self::Item> { |
2225 | if self.num == 0 { |
2226 | return None; |
2227 | } |
2228 | // SAFETY: |
2229 | // This is safe because it's indexing into a slice guaranteed to be length > N. |
2230 | let ret = unsafe { &*self.slice_head.cast::<[T; N]>() }; |
2231 | // SAFETY: Guaranteed that there are at least 1 item remaining otherwise |
2232 | // earlier branch would've been hit |
2233 | self.slice_head = unsafe { self.slice_head.add(1) }; |
2234 | |
2235 | self.num -= 1; |
2236 | Some(ret) |
2237 | } |
2238 | |
2239 | #[inline ] |
2240 | fn size_hint(&self) -> (usize, Option<usize>) { |
2241 | (self.num, Some(self.num)) |
2242 | } |
2243 | |
2244 | #[inline ] |
2245 | fn count(self) -> usize { |
2246 | self.num |
2247 | } |
2248 | |
2249 | #[inline ] |
2250 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
2251 | if self.num <= n { |
2252 | self.num = 0; |
2253 | return None; |
2254 | } |
2255 | // SAFETY: |
2256 | // This is safe because it's indexing into a slice guaranteed to be length > N. |
2257 | let ret = unsafe { &*self.slice_head.add(n).cast::<[T; N]>() }; |
2258 | // SAFETY: Guaranteed that there are at least n items remaining |
2259 | self.slice_head = unsafe { self.slice_head.add(n + 1) }; |
2260 | |
2261 | self.num -= n + 1; |
2262 | Some(ret) |
2263 | } |
2264 | |
2265 | #[inline ] |
2266 | fn last(mut self) -> Option<Self::Item> { |
2267 | self.nth(self.num.checked_sub(1)?) |
2268 | } |
2269 | } |
2270 | |
2271 | #[unstable (feature = "array_windows" , issue = "75027" )] |
2272 | impl<'a, T, const N: usize> DoubleEndedIterator for ArrayWindows<'a, T, N> { |
2273 | #[inline ] |
2274 | fn next_back(&mut self) -> Option<&'a [T; N]> { |
2275 | if self.num == 0 { |
2276 | return None; |
2277 | } |
2278 | // SAFETY: Guaranteed that there are n items remaining, n-1 for 0-indexing. |
2279 | let ret: &[T; N] = unsafe { &*self.slice_head.add(self.num - 1).cast::<[T; N]>() }; |
2280 | self.num -= 1; |
2281 | Some(ret) |
2282 | } |
2283 | |
2284 | #[inline ] |
2285 | fn nth_back(&mut self, n: usize) -> Option<&'a [T; N]> { |
2286 | if self.num <= n { |
2287 | self.num = 0; |
2288 | return None; |
2289 | } |
2290 | // SAFETY: Guaranteed that there are n items remaining, n-1 for 0-indexing. |
2291 | let ret: &[T; N] = unsafe { &*self.slice_head.add(self.num - (n + 1)).cast::<[T; N]>() }; |
2292 | self.num -= n + 1; |
2293 | Some(ret) |
2294 | } |
2295 | } |
2296 | |
2297 | #[unstable (feature = "array_windows" , issue = "75027" )] |
2298 | impl<T, const N: usize> ExactSizeIterator for ArrayWindows<'_, T, N> { |
2299 | fn is_empty(&self) -> bool { |
2300 | self.num == 0 |
2301 | } |
2302 | } |
2303 | |
2304 | /// An iterator over a slice in (non-overlapping) chunks (`N` elements at a |
2305 | /// time), starting at the beginning of the slice. |
2306 | /// |
2307 | /// When the slice len is not evenly divided by the chunk size, the last |
2308 | /// up to `N-1` elements will be omitted but can be retrieved from |
2309 | /// the [`remainder`] function from the iterator. |
2310 | /// |
2311 | /// This struct is created by the [`array_chunks`] method on [slices]. |
2312 | /// |
2313 | /// # Example |
2314 | /// |
2315 | /// ``` |
2316 | /// #![feature(array_chunks)] |
2317 | /// |
2318 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
2319 | /// let mut iter = slice.array_chunks::<2>(); |
2320 | /// assert_eq!(iter.next(), Some(&['l' , 'o' ])); |
2321 | /// assert_eq!(iter.next(), Some(&['r' , 'e' ])); |
2322 | /// assert_eq!(iter.next(), None); |
2323 | /// ``` |
2324 | /// |
2325 | /// [`array_chunks`]: slice::array_chunks |
2326 | /// [`remainder`]: ArrayChunks::remainder |
2327 | /// [slices]: slice |
2328 | #[derive (Debug)] |
2329 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2330 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
2331 | pub struct ArrayChunks<'a, T: 'a, const N: usize> { |
2332 | iter: Iter<'a, [T; N]>, |
2333 | rem: &'a [T], |
2334 | } |
2335 | |
2336 | impl<'a, T, const N: usize> ArrayChunks<'a, T, N> { |
2337 | #[rustc_const_unstable (feature = "const_slice_make_iter" , issue = "137737" )] |
2338 | #[inline ] |
2339 | pub(super) const fn new(slice: &'a [T]) -> Self { |
2340 | let (array_slice: &[[T; N]], rem: &[T]) = slice.as_chunks(); |
2341 | Self { iter: array_slice.iter(), rem } |
2342 | } |
2343 | |
2344 | /// Returns the remainder of the original slice that is not going to be |
2345 | /// returned by the iterator. The returned slice has at most `N-1` |
2346 | /// elements. |
2347 | #[must_use ] |
2348 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2349 | pub fn remainder(&self) -> &'a [T] { |
2350 | self.rem |
2351 | } |
2352 | } |
2353 | |
2354 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
2355 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2356 | impl<T, const N: usize> Clone for ArrayChunks<'_, T, N> { |
2357 | fn clone(&self) -> Self { |
2358 | ArrayChunks { iter: self.iter.clone(), rem: self.rem } |
2359 | } |
2360 | } |
2361 | |
2362 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2363 | impl<'a, T, const N: usize> Iterator for ArrayChunks<'a, T, N> { |
2364 | type Item = &'a [T; N]; |
2365 | |
2366 | #[inline ] |
2367 | fn next(&mut self) -> Option<&'a [T; N]> { |
2368 | self.iter.next() |
2369 | } |
2370 | |
2371 | #[inline ] |
2372 | fn size_hint(&self) -> (usize, Option<usize>) { |
2373 | self.iter.size_hint() |
2374 | } |
2375 | |
2376 | #[inline ] |
2377 | fn count(self) -> usize { |
2378 | self.iter.count() |
2379 | } |
2380 | |
2381 | #[inline ] |
2382 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
2383 | self.iter.nth(n) |
2384 | } |
2385 | |
2386 | #[inline ] |
2387 | fn last(self) -> Option<Self::Item> { |
2388 | self.iter.last() |
2389 | } |
2390 | |
2391 | unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> &'a [T; N] { |
2392 | // SAFETY: The safety guarantees of `__iterator_get_unchecked` are |
2393 | // transferred to the caller. |
2394 | unsafe { self.iter.__iterator_get_unchecked(i) } |
2395 | } |
2396 | } |
2397 | |
2398 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2399 | impl<'a, T, const N: usize> DoubleEndedIterator for ArrayChunks<'a, T, N> { |
2400 | #[inline ] |
2401 | fn next_back(&mut self) -> Option<&'a [T; N]> { |
2402 | self.iter.next_back() |
2403 | } |
2404 | |
2405 | #[inline ] |
2406 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
2407 | self.iter.nth_back(n) |
2408 | } |
2409 | } |
2410 | |
2411 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2412 | impl<T, const N: usize> ExactSizeIterator for ArrayChunks<'_, T, N> { |
2413 | fn is_empty(&self) -> bool { |
2414 | self.iter.is_empty() |
2415 | } |
2416 | } |
2417 | |
2418 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
2419 | unsafe impl<T, const N: usize> TrustedLen for ArrayChunks<'_, T, N> {} |
2420 | |
2421 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2422 | impl<T, const N: usize> FusedIterator for ArrayChunks<'_, T, N> {} |
2423 | |
2424 | #[doc (hidden)] |
2425 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2426 | unsafe impl<'a, T, const N: usize> TrustedRandomAccess for ArrayChunks<'a, T, N> {} |
2427 | |
2428 | #[doc (hidden)] |
2429 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2430 | unsafe impl<'a, T, const N: usize> TrustedRandomAccessNoCoerce for ArrayChunks<'a, T, N> { |
2431 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
2432 | } |
2433 | |
2434 | /// An iterator over a slice in (non-overlapping) mutable chunks (`N` elements |
2435 | /// at a time), starting at the beginning of the slice. |
2436 | /// |
2437 | /// When the slice len is not evenly divided by the chunk size, the last |
2438 | /// up to `N-1` elements will be omitted but can be retrieved from |
2439 | /// the [`into_remainder`] function from the iterator. |
2440 | /// |
2441 | /// This struct is created by the [`array_chunks_mut`] method on [slices]. |
2442 | /// |
2443 | /// # Example |
2444 | /// |
2445 | /// ``` |
2446 | /// #![feature(array_chunks)] |
2447 | /// |
2448 | /// let mut slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
2449 | /// let iter = slice.array_chunks_mut::<2>(); |
2450 | /// ``` |
2451 | /// |
2452 | /// [`array_chunks_mut`]: slice::array_chunks_mut |
2453 | /// [`into_remainder`]: ../../std/slice/struct.ArrayChunksMut.html#method.into_remainder |
2454 | /// [slices]: slice |
2455 | #[derive (Debug)] |
2456 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2457 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
2458 | pub struct ArrayChunksMut<'a, T: 'a, const N: usize> { |
2459 | iter: IterMut<'a, [T; N]>, |
2460 | rem: &'a mut [T], |
2461 | } |
2462 | |
2463 | impl<'a, T, const N: usize> ArrayChunksMut<'a, T, N> { |
2464 | #[rustc_const_unstable (feature = "const_slice_make_iter" , issue = "137737" )] |
2465 | #[inline ] |
2466 | pub(super) const fn new(slice: &'a mut [T]) -> Self { |
2467 | let (array_slice: &mut [[T; N]], rem: &mut [T]) = slice.as_chunks_mut(); |
2468 | Self { iter: array_slice.iter_mut(), rem } |
2469 | } |
2470 | |
2471 | /// Returns the remainder of the original slice that is not going to be |
2472 | /// returned by the iterator. The returned slice has at most `N-1` |
2473 | /// elements. |
2474 | #[must_use = "`self` will be dropped if the result is not used" ] |
2475 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2476 | pub fn into_remainder(self) -> &'a mut [T] { |
2477 | self.rem |
2478 | } |
2479 | } |
2480 | |
2481 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2482 | impl<'a, T, const N: usize> Iterator for ArrayChunksMut<'a, T, N> { |
2483 | type Item = &'a mut [T; N]; |
2484 | |
2485 | #[inline ] |
2486 | fn next(&mut self) -> Option<&'a mut [T; N]> { |
2487 | self.iter.next() |
2488 | } |
2489 | |
2490 | #[inline ] |
2491 | fn size_hint(&self) -> (usize, Option<usize>) { |
2492 | self.iter.size_hint() |
2493 | } |
2494 | |
2495 | #[inline ] |
2496 | fn count(self) -> usize { |
2497 | self.iter.count() |
2498 | } |
2499 | |
2500 | #[inline ] |
2501 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
2502 | self.iter.nth(n) |
2503 | } |
2504 | |
2505 | #[inline ] |
2506 | fn last(self) -> Option<Self::Item> { |
2507 | self.iter.last() |
2508 | } |
2509 | |
2510 | unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> &'a mut [T; N] { |
2511 | // SAFETY: The safety guarantees of `__iterator_get_unchecked` are transferred to |
2512 | // the caller. |
2513 | unsafe { self.iter.__iterator_get_unchecked(i) } |
2514 | } |
2515 | } |
2516 | |
2517 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2518 | impl<'a, T, const N: usize> DoubleEndedIterator for ArrayChunksMut<'a, T, N> { |
2519 | #[inline ] |
2520 | fn next_back(&mut self) -> Option<&'a mut [T; N]> { |
2521 | self.iter.next_back() |
2522 | } |
2523 | |
2524 | #[inline ] |
2525 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
2526 | self.iter.nth_back(n) |
2527 | } |
2528 | } |
2529 | |
2530 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2531 | impl<T, const N: usize> ExactSizeIterator for ArrayChunksMut<'_, T, N> { |
2532 | fn is_empty(&self) -> bool { |
2533 | self.iter.is_empty() |
2534 | } |
2535 | } |
2536 | |
2537 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
2538 | unsafe impl<T, const N: usize> TrustedLen for ArrayChunksMut<'_, T, N> {} |
2539 | |
2540 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2541 | impl<T, const N: usize> FusedIterator for ArrayChunksMut<'_, T, N> {} |
2542 | |
2543 | #[doc (hidden)] |
2544 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2545 | unsafe impl<'a, T, const N: usize> TrustedRandomAccess for ArrayChunksMut<'a, T, N> {} |
2546 | |
2547 | #[doc (hidden)] |
2548 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
2549 | unsafe impl<'a, T, const N: usize> TrustedRandomAccessNoCoerce for ArrayChunksMut<'a, T, N> { |
2550 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
2551 | } |
2552 | |
2553 | /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a |
2554 | /// time), starting at the end of the slice. |
2555 | /// |
2556 | /// When the slice len is not evenly divided by the chunk size, the last slice |
2557 | /// of the iteration will be the remainder. |
2558 | /// |
2559 | /// This struct is created by the [`rchunks`] method on [slices]. |
2560 | /// |
2561 | /// # Example |
2562 | /// |
2563 | /// ``` |
2564 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
2565 | /// let mut iter = slice.rchunks(2); |
2566 | /// assert_eq!(iter.next(), Some(&['e' , 'm' ][..])); |
2567 | /// assert_eq!(iter.next(), Some(&['o' , 'r' ][..])); |
2568 | /// assert_eq!(iter.next(), Some(&['l' ][..])); |
2569 | /// assert_eq!(iter.next(), None); |
2570 | /// ``` |
2571 | /// |
2572 | /// [`rchunks`]: slice::rchunks |
2573 | /// [slices]: slice |
2574 | #[derive (Debug)] |
2575 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2576 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
2577 | pub struct RChunks<'a, T: 'a> { |
2578 | v: &'a [T], |
2579 | chunk_size: usize, |
2580 | } |
2581 | |
2582 | impl<'a, T: 'a> RChunks<'a, T> { |
2583 | #[inline ] |
2584 | pub(super) const fn new(slice: &'a [T], size: usize) -> Self { |
2585 | Self { v: slice, chunk_size: size } |
2586 | } |
2587 | } |
2588 | |
2589 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
2590 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2591 | impl<T> Clone for RChunks<'_, T> { |
2592 | fn clone(&self) -> Self { |
2593 | RChunks { v: self.v, chunk_size: self.chunk_size } |
2594 | } |
2595 | } |
2596 | |
2597 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2598 | impl<'a, T> Iterator for RChunks<'a, T> { |
2599 | type Item = &'a [T]; |
2600 | |
2601 | #[inline ] |
2602 | fn next(&mut self) -> Option<&'a [T]> { |
2603 | if self.v.is_empty() { |
2604 | None |
2605 | } else { |
2606 | let len = self.v.len(); |
2607 | let chunksz = cmp::min(len, self.chunk_size); |
2608 | // SAFETY: split_at_unchecked just requires the argument be less |
2609 | // than the length. This could only happen if the expression `len - |
2610 | // chunksz` overflows. This could only happen if `chunksz > len`, |
2611 | // which is impossible as we initialize it as the `min` of `len` and |
2612 | // `self.chunk_size`. |
2613 | let (fst, snd) = unsafe { self.v.split_at_unchecked(len - chunksz) }; |
2614 | self.v = fst; |
2615 | Some(snd) |
2616 | } |
2617 | } |
2618 | |
2619 | #[inline ] |
2620 | fn size_hint(&self) -> (usize, Option<usize>) { |
2621 | if self.v.is_empty() { |
2622 | (0, Some(0)) |
2623 | } else { |
2624 | let n = self.v.len() / self.chunk_size; |
2625 | let rem = self.v.len() % self.chunk_size; |
2626 | let n = if rem > 0 { n + 1 } else { n }; |
2627 | (n, Some(n)) |
2628 | } |
2629 | } |
2630 | |
2631 | #[inline ] |
2632 | fn count(self) -> usize { |
2633 | self.len() |
2634 | } |
2635 | |
2636 | #[inline ] |
2637 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
2638 | let (end, overflow) = n.overflowing_mul(self.chunk_size); |
2639 | if end >= self.v.len() || overflow { |
2640 | self.v = &self.v[..0]; // cheaper than &[] |
2641 | None |
2642 | } else { |
2643 | // Can't underflow because of the check above |
2644 | let end = self.v.len() - end; |
2645 | let start = match end.checked_sub(self.chunk_size) { |
2646 | Some(sum) => sum, |
2647 | None => 0, |
2648 | }; |
2649 | let nth = &self.v[start..end]; |
2650 | self.v = &self.v[0..start]; |
2651 | Some(nth) |
2652 | } |
2653 | } |
2654 | |
2655 | #[inline ] |
2656 | fn last(self) -> Option<Self::Item> { |
2657 | if self.v.is_empty() { |
2658 | None |
2659 | } else { |
2660 | let rem = self.v.len() % self.chunk_size; |
2661 | let end = if rem == 0 { self.chunk_size } else { rem }; |
2662 | Some(&self.v[0..end]) |
2663 | } |
2664 | } |
2665 | |
2666 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
2667 | let end = self.v.len() - idx * self.chunk_size; |
2668 | let start = match end.checked_sub(self.chunk_size) { |
2669 | None => 0, |
2670 | Some(start) => start, |
2671 | }; |
2672 | // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`. |
2673 | unsafe { from_raw_parts(self.v.as_ptr().add(start), end - start) } |
2674 | } |
2675 | } |
2676 | |
2677 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2678 | impl<'a, T> DoubleEndedIterator for RChunks<'a, T> { |
2679 | #[inline ] |
2680 | fn next_back(&mut self) -> Option<&'a [T]> { |
2681 | if self.v.is_empty() { |
2682 | None |
2683 | } else { |
2684 | let remainder = self.v.len() % self.chunk_size; |
2685 | let chunksz = if remainder != 0 { remainder } else { self.chunk_size }; |
2686 | // SAFETY: similar to Chunks::next_back |
2687 | let (fst, snd) = unsafe { self.v.split_at_unchecked(chunksz) }; |
2688 | self.v = snd; |
2689 | Some(fst) |
2690 | } |
2691 | } |
2692 | |
2693 | #[inline ] |
2694 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
2695 | let len = self.len(); |
2696 | if n >= len { |
2697 | self.v = &self.v[..0]; // cheaper than &[] |
2698 | None |
2699 | } else { |
2700 | // can't underflow because `n < len` |
2701 | let offset_from_end = (len - 1 - n) * self.chunk_size; |
2702 | let end = self.v.len() - offset_from_end; |
2703 | let start = end.saturating_sub(self.chunk_size); |
2704 | let nth_back = &self.v[start..end]; |
2705 | self.v = &self.v[end..]; |
2706 | Some(nth_back) |
2707 | } |
2708 | } |
2709 | } |
2710 | |
2711 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2712 | impl<T> ExactSizeIterator for RChunks<'_, T> {} |
2713 | |
2714 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
2715 | unsafe impl<T> TrustedLen for RChunks<'_, T> {} |
2716 | |
2717 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2718 | impl<T> FusedIterator for RChunks<'_, T> {} |
2719 | |
2720 | #[doc (hidden)] |
2721 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
2722 | unsafe impl<'a, T> TrustedRandomAccess for RChunks<'a, T> {} |
2723 | |
2724 | #[doc (hidden)] |
2725 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
2726 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunks<'a, T> { |
2727 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
2728 | } |
2729 | |
2730 | /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size` |
2731 | /// elements at a time), starting at the end of the slice. |
2732 | /// |
2733 | /// When the slice len is not evenly divided by the chunk size, the last slice |
2734 | /// of the iteration will be the remainder. |
2735 | /// |
2736 | /// This struct is created by the [`rchunks_mut`] method on [slices]. |
2737 | /// |
2738 | /// # Example |
2739 | /// |
2740 | /// ``` |
2741 | /// let mut slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
2742 | /// let iter = slice.rchunks_mut(2); |
2743 | /// ``` |
2744 | /// |
2745 | /// [`rchunks_mut`]: slice::rchunks_mut |
2746 | /// [slices]: slice |
2747 | #[derive (Debug)] |
2748 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2749 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
2750 | pub struct RChunksMut<'a, T: 'a> { |
2751 | /// # Safety |
2752 | /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally, |
2753 | /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot |
2754 | /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing |
2755 | /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw |
2756 | /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap. |
2757 | v: *mut [T], |
2758 | chunk_size: usize, |
2759 | _marker: PhantomData<&'a mut T>, |
2760 | } |
2761 | |
2762 | impl<'a, T: 'a> RChunksMut<'a, T> { |
2763 | #[inline ] |
2764 | pub(super) const fn new(slice: &'a mut [T], size: usize) -> Self { |
2765 | Self { v: slice, chunk_size: size, _marker: PhantomData } |
2766 | } |
2767 | } |
2768 | |
2769 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2770 | impl<'a, T> Iterator for RChunksMut<'a, T> { |
2771 | type Item = &'a mut [T]; |
2772 | |
2773 | #[inline ] |
2774 | fn next(&mut self) -> Option<&'a mut [T]> { |
2775 | if self.v.is_empty() { |
2776 | None |
2777 | } else { |
2778 | let sz = cmp::min(self.v.len(), self.chunk_size); |
2779 | let len = self.v.len(); |
2780 | // SAFETY: split_at_mut_unchecked just requires the argument be less |
2781 | // than the length. This could only happen if the expression |
2782 | // `len - sz` overflows. This could only happen if `sz > |
2783 | // len`, which is impossible as we initialize it as the `min` of |
2784 | // `self.v.len()` (e.g. `len`) and `self.chunk_size`. |
2785 | let (head, tail) = unsafe { self.v.split_at_mut_unchecked(len - sz) }; |
2786 | self.v = head; |
2787 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
2788 | Some(unsafe { &mut *tail }) |
2789 | } |
2790 | } |
2791 | |
2792 | #[inline ] |
2793 | fn size_hint(&self) -> (usize, Option<usize>) { |
2794 | if self.v.is_empty() { |
2795 | (0, Some(0)) |
2796 | } else { |
2797 | let n = self.v.len() / self.chunk_size; |
2798 | let rem = self.v.len() % self.chunk_size; |
2799 | let n = if rem > 0 { n + 1 } else { n }; |
2800 | (n, Some(n)) |
2801 | } |
2802 | } |
2803 | |
2804 | #[inline ] |
2805 | fn count(self) -> usize { |
2806 | self.len() |
2807 | } |
2808 | |
2809 | #[inline ] |
2810 | fn nth(&mut self, n: usize) -> Option<&'a mut [T]> { |
2811 | let (end, overflow) = n.overflowing_mul(self.chunk_size); |
2812 | if end >= self.v.len() || overflow { |
2813 | self.v = &mut []; |
2814 | None |
2815 | } else { |
2816 | // Can't underflow because of the check above |
2817 | let end = self.v.len() - end; |
2818 | let start = match end.checked_sub(self.chunk_size) { |
2819 | Some(sum) => sum, |
2820 | None => 0, |
2821 | }; |
2822 | // SAFETY: This type ensures that self.v is a valid pointer with a correct len. |
2823 | // Therefore the bounds check in split_at_mut guarantees the split point is inbounds. |
2824 | let (head, tail) = unsafe { self.v.split_at_mut(start) }; |
2825 | // SAFETY: This type ensures that self.v is a valid pointer with a correct len. |
2826 | // Therefore the bounds check in split_at_mut guarantees the split point is inbounds. |
2827 | let (nth, _) = unsafe { tail.split_at_mut(end - start) }; |
2828 | self.v = head; |
2829 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
2830 | Some(unsafe { &mut *nth }) |
2831 | } |
2832 | } |
2833 | |
2834 | #[inline ] |
2835 | fn last(self) -> Option<Self::Item> { |
2836 | if self.v.is_empty() { |
2837 | None |
2838 | } else { |
2839 | let rem = self.v.len() % self.chunk_size; |
2840 | let end = if rem == 0 { self.chunk_size } else { rem }; |
2841 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
2842 | Some(unsafe { &mut *self.v.get_unchecked_mut(0..end) }) |
2843 | } |
2844 | } |
2845 | |
2846 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
2847 | let end = self.v.len() - idx * self.chunk_size; |
2848 | let start = match end.checked_sub(self.chunk_size) { |
2849 | None => 0, |
2850 | Some(start) => start, |
2851 | }; |
2852 | // SAFETY: see comments for `RChunks::__iterator_get_unchecked` and |
2853 | // `ChunksMut::__iterator_get_unchecked`, `self.v`. |
2854 | unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start) } |
2855 | } |
2856 | } |
2857 | |
2858 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2859 | impl<'a, T> DoubleEndedIterator for RChunksMut<'a, T> { |
2860 | #[inline ] |
2861 | fn next_back(&mut self) -> Option<&'a mut [T]> { |
2862 | if self.v.is_empty() { |
2863 | None |
2864 | } else { |
2865 | let remainder = self.v.len() % self.chunk_size; |
2866 | let sz = if remainder != 0 { remainder } else { self.chunk_size }; |
2867 | // SAFETY: Similar to `Chunks::next_back` |
2868 | let (head, tail) = unsafe { self.v.split_at_mut_unchecked(sz) }; |
2869 | self.v = tail; |
2870 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
2871 | Some(unsafe { &mut *head }) |
2872 | } |
2873 | } |
2874 | |
2875 | #[inline ] |
2876 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
2877 | let len = self.len(); |
2878 | if n >= len { |
2879 | self.v = &mut []; |
2880 | None |
2881 | } else { |
2882 | // can't underflow because `n < len` |
2883 | let offset_from_end = (len - 1 - n) * self.chunk_size; |
2884 | let end = self.v.len() - offset_from_end; |
2885 | let start = end.saturating_sub(self.chunk_size); |
2886 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
2887 | let (tmp, tail) = unsafe { self.v.split_at_mut(end) }; |
2888 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
2889 | let (_, nth_back) = unsafe { tmp.split_at_mut(start) }; |
2890 | self.v = tail; |
2891 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
2892 | Some(unsafe { &mut *nth_back }) |
2893 | } |
2894 | } |
2895 | } |
2896 | |
2897 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2898 | impl<T> ExactSizeIterator for RChunksMut<'_, T> {} |
2899 | |
2900 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
2901 | unsafe impl<T> TrustedLen for RChunksMut<'_, T> {} |
2902 | |
2903 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2904 | impl<T> FusedIterator for RChunksMut<'_, T> {} |
2905 | |
2906 | #[doc (hidden)] |
2907 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
2908 | unsafe impl<'a, T> TrustedRandomAccess for RChunksMut<'a, T> {} |
2909 | |
2910 | #[doc (hidden)] |
2911 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
2912 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksMut<'a, T> { |
2913 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
2914 | } |
2915 | |
2916 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2917 | unsafe impl<T> Send for RChunksMut<'_, T> where T: Send {} |
2918 | |
2919 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2920 | unsafe impl<T> Sync for RChunksMut<'_, T> where T: Sync {} |
2921 | |
2922 | /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a |
2923 | /// time), starting at the end of the slice. |
2924 | /// |
2925 | /// When the slice len is not evenly divided by the chunk size, the last |
2926 | /// up to `chunk_size-1` elements will be omitted but can be retrieved from |
2927 | /// the [`remainder`] function from the iterator. |
2928 | /// |
2929 | /// This struct is created by the [`rchunks_exact`] method on [slices]. |
2930 | /// |
2931 | /// # Example |
2932 | /// |
2933 | /// ``` |
2934 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
2935 | /// let mut iter = slice.rchunks_exact(2); |
2936 | /// assert_eq!(iter.next(), Some(&['e' , 'm' ][..])); |
2937 | /// assert_eq!(iter.next(), Some(&['o' , 'r' ][..])); |
2938 | /// assert_eq!(iter.next(), None); |
2939 | /// ``` |
2940 | /// |
2941 | /// [`rchunks_exact`]: slice::rchunks_exact |
2942 | /// [`remainder`]: RChunksExact::remainder |
2943 | /// [slices]: slice |
2944 | #[derive (Debug)] |
2945 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2946 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
2947 | pub struct RChunksExact<'a, T: 'a> { |
2948 | v: &'a [T], |
2949 | rem: &'a [T], |
2950 | chunk_size: usize, |
2951 | } |
2952 | |
2953 | impl<'a, T> RChunksExact<'a, T> { |
2954 | #[inline ] |
2955 | pub(super) const fn new(slice: &'a [T], chunk_size: usize) -> Self { |
2956 | let rem = slice.len() % chunk_size; |
2957 | // SAFETY: 0 <= rem <= slice.len() by construction above |
2958 | let (fst, snd) = unsafe { slice.split_at_unchecked(rem) }; |
2959 | Self { v: snd, rem: fst, chunk_size } |
2960 | } |
2961 | |
2962 | /// Returns the remainder of the original slice that is not going to be |
2963 | /// returned by the iterator. The returned slice has at most `chunk_size-1` |
2964 | /// elements. |
2965 | /// |
2966 | /// # Example |
2967 | /// |
2968 | /// ``` |
2969 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
2970 | /// let mut iter = slice.rchunks_exact(2); |
2971 | /// assert_eq!(iter.remainder(), &['l' ][..]); |
2972 | /// assert_eq!(iter.next(), Some(&['e' , 'm' ][..])); |
2973 | /// assert_eq!(iter.remainder(), &['l' ][..]); |
2974 | /// assert_eq!(iter.next(), Some(&['o' , 'r' ][..])); |
2975 | /// assert_eq!(iter.remainder(), &['l' ][..]); |
2976 | /// assert_eq!(iter.next(), None); |
2977 | /// assert_eq!(iter.remainder(), &['l' ][..]); |
2978 | /// ``` |
2979 | #[must_use ] |
2980 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2981 | #[rustc_const_unstable (feature = "const_slice_make_iter" , issue = "137737" )] |
2982 | pub const fn remainder(&self) -> &'a [T] { |
2983 | self.rem |
2984 | } |
2985 | } |
2986 | |
2987 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
2988 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2989 | impl<'a, T> Clone for RChunksExact<'a, T> { |
2990 | fn clone(&self) -> RChunksExact<'a, T> { |
2991 | RChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size } |
2992 | } |
2993 | } |
2994 | |
2995 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
2996 | impl<'a, T> Iterator for RChunksExact<'a, T> { |
2997 | type Item = &'a [T]; |
2998 | |
2999 | #[inline ] |
3000 | fn next(&mut self) -> Option<&'a [T]> { |
3001 | if self.v.len() < self.chunk_size { |
3002 | None |
3003 | } else { |
3004 | let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size); |
3005 | self.v = fst; |
3006 | Some(snd) |
3007 | } |
3008 | } |
3009 | |
3010 | #[inline ] |
3011 | fn size_hint(&self) -> (usize, Option<usize>) { |
3012 | let n = self.v.len() / self.chunk_size; |
3013 | (n, Some(n)) |
3014 | } |
3015 | |
3016 | #[inline ] |
3017 | fn count(self) -> usize { |
3018 | self.len() |
3019 | } |
3020 | |
3021 | #[inline ] |
3022 | fn nth(&mut self, n: usize) -> Option<Self::Item> { |
3023 | let (end, overflow) = n.overflowing_mul(self.chunk_size); |
3024 | if end >= self.v.len() || overflow { |
3025 | self.v = &self.v[..0]; // cheaper than &[] |
3026 | None |
3027 | } else { |
3028 | let (fst, _) = self.v.split_at(self.v.len() - end); |
3029 | self.v = fst; |
3030 | self.next() |
3031 | } |
3032 | } |
3033 | |
3034 | #[inline ] |
3035 | fn last(mut self) -> Option<Self::Item> { |
3036 | self.next_back() |
3037 | } |
3038 | |
3039 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
3040 | let end = self.v.len() - idx * self.chunk_size; |
3041 | let start = end - self.chunk_size; |
3042 | // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`. |
3043 | unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) } |
3044 | } |
3045 | } |
3046 | |
3047 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3048 | impl<'a, T> DoubleEndedIterator for RChunksExact<'a, T> { |
3049 | #[inline ] |
3050 | fn next_back(&mut self) -> Option<&'a [T]> { |
3051 | if self.v.len() < self.chunk_size { |
3052 | None |
3053 | } else { |
3054 | let (fst, snd) = self.v.split_at(self.chunk_size); |
3055 | self.v = snd; |
3056 | Some(fst) |
3057 | } |
3058 | } |
3059 | |
3060 | #[inline ] |
3061 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
3062 | let len = self.len(); |
3063 | if n >= len { |
3064 | self.v = &self.v[..0]; // cheaper than &[] |
3065 | None |
3066 | } else { |
3067 | // now that we know that `n` corresponds to a chunk, |
3068 | // none of these operations can underflow/overflow |
3069 | let offset = (len - n) * self.chunk_size; |
3070 | let start = self.v.len() - offset; |
3071 | let end = start + self.chunk_size; |
3072 | let nth_back = &self.v[start..end]; |
3073 | self.v = &self.v[end..]; |
3074 | Some(nth_back) |
3075 | } |
3076 | } |
3077 | } |
3078 | |
3079 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3080 | impl<'a, T> ExactSizeIterator for RChunksExact<'a, T> { |
3081 | fn is_empty(&self) -> bool { |
3082 | self.v.is_empty() |
3083 | } |
3084 | } |
3085 | |
3086 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
3087 | unsafe impl<T> TrustedLen for RChunksExact<'_, T> {} |
3088 | |
3089 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3090 | impl<T> FusedIterator for RChunksExact<'_, T> {} |
3091 | |
3092 | #[doc (hidden)] |
3093 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
3094 | unsafe impl<'a, T> TrustedRandomAccess for RChunksExact<'a, T> {} |
3095 | |
3096 | #[doc (hidden)] |
3097 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
3098 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExact<'a, T> { |
3099 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
3100 | } |
3101 | |
3102 | /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size` |
3103 | /// elements at a time), starting at the end of the slice. |
3104 | /// |
3105 | /// When the slice len is not evenly divided by the chunk size, the last up to |
3106 | /// `chunk_size-1` elements will be omitted but can be retrieved from the |
3107 | /// [`into_remainder`] function from the iterator. |
3108 | /// |
3109 | /// This struct is created by the [`rchunks_exact_mut`] method on [slices]. |
3110 | /// |
3111 | /// # Example |
3112 | /// |
3113 | /// ``` |
3114 | /// let mut slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
3115 | /// let iter = slice.rchunks_exact_mut(2); |
3116 | /// ``` |
3117 | /// |
3118 | /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut |
3119 | /// [`into_remainder`]: RChunksExactMut::into_remainder |
3120 | /// [slices]: slice |
3121 | #[derive (Debug)] |
3122 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3123 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
3124 | pub struct RChunksExactMut<'a, T: 'a> { |
3125 | /// # Safety |
3126 | /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally, |
3127 | /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot |
3128 | /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing |
3129 | /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw |
3130 | /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap. |
3131 | v: *mut [T], |
3132 | rem: &'a mut [T], |
3133 | chunk_size: usize, |
3134 | } |
3135 | |
3136 | impl<'a, T> RChunksExactMut<'a, T> { |
3137 | #[inline ] |
3138 | pub(super) const fn new(slice: &'a mut [T], chunk_size: usize) -> Self { |
3139 | let rem: usize = slice.len() % chunk_size; |
3140 | // SAFETY: 0 <= rem <= slice.len() by construction above |
3141 | let (fst: &mut [T], snd: &mut [T]) = unsafe { slice.split_at_mut_unchecked(mid:rem) }; |
3142 | Self { v: snd, rem: fst, chunk_size } |
3143 | } |
3144 | |
3145 | /// Returns the remainder of the original slice that is not going to be |
3146 | /// returned by the iterator. The returned slice has at most `chunk_size-1` |
3147 | /// elements. |
3148 | #[must_use = "`self` will be dropped if the result is not used" ] |
3149 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3150 | #[rustc_const_unstable (feature = "const_slice_make_iter" , issue = "137737" )] |
3151 | pub const fn into_remainder(self) -> &'a mut [T] { |
3152 | self.rem |
3153 | } |
3154 | } |
3155 | |
3156 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3157 | impl<'a, T> Iterator for RChunksExactMut<'a, T> { |
3158 | type Item = &'a mut [T]; |
3159 | |
3160 | #[inline ] |
3161 | fn next(&mut self) -> Option<&'a mut [T]> { |
3162 | if self.v.len() < self.chunk_size { |
3163 | None |
3164 | } else { |
3165 | let len = self.v.len(); |
3166 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
3167 | let (head, tail) = unsafe { self.v.split_at_mut(len - self.chunk_size) }; |
3168 | self.v = head; |
3169 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
3170 | Some(unsafe { &mut *tail }) |
3171 | } |
3172 | } |
3173 | |
3174 | #[inline ] |
3175 | fn size_hint(&self) -> (usize, Option<usize>) { |
3176 | let n = self.v.len() / self.chunk_size; |
3177 | (n, Some(n)) |
3178 | } |
3179 | |
3180 | #[inline ] |
3181 | fn count(self) -> usize { |
3182 | self.len() |
3183 | } |
3184 | |
3185 | #[inline ] |
3186 | fn nth(&mut self, n: usize) -> Option<&'a mut [T]> { |
3187 | let (end, overflow) = n.overflowing_mul(self.chunk_size); |
3188 | if end >= self.v.len() || overflow { |
3189 | self.v = &mut []; |
3190 | None |
3191 | } else { |
3192 | let len = self.v.len(); |
3193 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
3194 | let (fst, _) = unsafe { self.v.split_at_mut(len - end) }; |
3195 | self.v = fst; |
3196 | self.next() |
3197 | } |
3198 | } |
3199 | |
3200 | #[inline ] |
3201 | fn last(mut self) -> Option<Self::Item> { |
3202 | self.next_back() |
3203 | } |
3204 | |
3205 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
3206 | let end = self.v.len() - idx * self.chunk_size; |
3207 | let start = end - self.chunk_size; |
3208 | // SAFETY: see comments for `RChunksMut::__iterator_get_unchecked` and `self.v`. |
3209 | unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) } |
3210 | } |
3211 | } |
3212 | |
3213 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3214 | impl<'a, T> DoubleEndedIterator for RChunksExactMut<'a, T> { |
3215 | #[inline ] |
3216 | fn next_back(&mut self) -> Option<&'a mut [T]> { |
3217 | if self.v.len() < self.chunk_size { |
3218 | None |
3219 | } else { |
3220 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
3221 | let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) }; |
3222 | self.v = tail; |
3223 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
3224 | Some(unsafe { &mut *head }) |
3225 | } |
3226 | } |
3227 | |
3228 | #[inline ] |
3229 | fn nth_back(&mut self, n: usize) -> Option<Self::Item> { |
3230 | let len = self.len(); |
3231 | if n >= len { |
3232 | self.v = &mut []; |
3233 | None |
3234 | } else { |
3235 | // now that we know that `n` corresponds to a chunk, |
3236 | // none of these operations can underflow/overflow |
3237 | let offset = (len - n) * self.chunk_size; |
3238 | let start = self.v.len() - offset; |
3239 | let end = start + self.chunk_size; |
3240 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
3241 | let (tmp, tail) = unsafe { self.v.split_at_mut(end) }; |
3242 | // SAFETY: The self.v contract ensures that any split_at_mut is valid. |
3243 | let (_, nth_back) = unsafe { tmp.split_at_mut(start) }; |
3244 | self.v = tail; |
3245 | // SAFETY: Nothing else points to or will point to the contents of this slice. |
3246 | Some(unsafe { &mut *nth_back }) |
3247 | } |
3248 | } |
3249 | } |
3250 | |
3251 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3252 | impl<T> ExactSizeIterator for RChunksExactMut<'_, T> { |
3253 | fn is_empty(&self) -> bool { |
3254 | self.v.is_empty() |
3255 | } |
3256 | } |
3257 | |
3258 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
3259 | unsafe impl<T> TrustedLen for RChunksExactMut<'_, T> {} |
3260 | |
3261 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3262 | impl<T> FusedIterator for RChunksExactMut<'_, T> {} |
3263 | |
3264 | #[doc (hidden)] |
3265 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
3266 | unsafe impl<'a, T> TrustedRandomAccess for RChunksExactMut<'a, T> {} |
3267 | |
3268 | #[doc (hidden)] |
3269 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
3270 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExactMut<'a, T> { |
3271 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
3272 | } |
3273 | |
3274 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3275 | unsafe impl<T> Send for RChunksExactMut<'_, T> where T: Send {} |
3276 | |
3277 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
3278 | unsafe impl<T> Sync for RChunksExactMut<'_, T> where T: Sync {} |
3279 | |
3280 | #[doc (hidden)] |
3281 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
3282 | unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {} |
3283 | |
3284 | #[doc (hidden)] |
3285 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
3286 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Iter<'a, T> { |
3287 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
3288 | } |
3289 | |
3290 | #[doc (hidden)] |
3291 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
3292 | unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {} |
3293 | |
3294 | #[doc (hidden)] |
3295 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
3296 | unsafe impl<'a, T> TrustedRandomAccessNoCoerce for IterMut<'a, T> { |
3297 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
3298 | } |
3299 | |
3300 | /// An iterator over slice in (non-overlapping) chunks separated by a predicate. |
3301 | /// |
3302 | /// This struct is created by the [`chunk_by`] method on [slices]. |
3303 | /// |
3304 | /// [`chunk_by`]: slice::chunk_by |
3305 | /// [slices]: slice |
3306 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3307 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
3308 | pub struct ChunkBy<'a, T: 'a, P> { |
3309 | slice: &'a [T], |
3310 | predicate: P, |
3311 | } |
3312 | |
3313 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3314 | impl<'a, T: 'a, P> ChunkBy<'a, T, P> { |
3315 | pub(super) const fn new(slice: &'a [T], predicate: P) -> Self { |
3316 | ChunkBy { slice, predicate } |
3317 | } |
3318 | } |
3319 | |
3320 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3321 | impl<'a, T: 'a, P> Iterator for ChunkBy<'a, T, P> |
3322 | where |
3323 | P: FnMut(&T, &T) -> bool, |
3324 | { |
3325 | type Item = &'a [T]; |
3326 | |
3327 | #[inline ] |
3328 | fn next(&mut self) -> Option<Self::Item> { |
3329 | if self.slice.is_empty() { |
3330 | None |
3331 | } else { |
3332 | let mut len = 1; |
3333 | let mut iter = self.slice.windows(2); |
3334 | while let Some([l, r]) = iter.next() { |
3335 | if (self.predicate)(l, r) { len += 1 } else { break } |
3336 | } |
3337 | let (head, tail) = self.slice.split_at(len); |
3338 | self.slice = tail; |
3339 | Some(head) |
3340 | } |
3341 | } |
3342 | |
3343 | #[inline ] |
3344 | fn size_hint(&self) -> (usize, Option<usize>) { |
3345 | if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) } |
3346 | } |
3347 | |
3348 | #[inline ] |
3349 | fn last(mut self) -> Option<Self::Item> { |
3350 | self.next_back() |
3351 | } |
3352 | } |
3353 | |
3354 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3355 | impl<'a, T: 'a, P> DoubleEndedIterator for ChunkBy<'a, T, P> |
3356 | where |
3357 | P: FnMut(&T, &T) -> bool, |
3358 | { |
3359 | #[inline ] |
3360 | fn next_back(&mut self) -> Option<Self::Item> { |
3361 | if self.slice.is_empty() { |
3362 | None |
3363 | } else { |
3364 | let mut len: usize = 1; |
3365 | let mut iter: Windows<'_, T> = self.slice.windows(size:2); |
3366 | while let Some([l: &T, r: &T]) = iter.next_back() { |
3367 | if (self.predicate)(l, r) { len += 1 } else { break } |
3368 | } |
3369 | let (head: &[T], tail: &[T]) = self.slice.split_at(self.slice.len() - len); |
3370 | self.slice = head; |
3371 | Some(tail) |
3372 | } |
3373 | } |
3374 | } |
3375 | |
3376 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3377 | impl<'a, T: 'a, P> FusedIterator for ChunkBy<'a, T, P> where P: FnMut(&T, &T) -> bool {} |
3378 | |
3379 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3380 | impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for ChunkBy<'a, T, P> { |
3381 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
3382 | f.debug_struct("ChunkBy" ).field(name:"slice" , &self.slice).finish() |
3383 | } |
3384 | } |
3385 | |
3386 | /// An iterator over slice in (non-overlapping) mutable chunks separated |
3387 | /// by a predicate. |
3388 | /// |
3389 | /// This struct is created by the [`chunk_by_mut`] method on [slices]. |
3390 | /// |
3391 | /// [`chunk_by_mut`]: slice::chunk_by_mut |
3392 | /// [slices]: slice |
3393 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3394 | #[must_use = "iterators are lazy and do nothing unless consumed" ] |
3395 | pub struct ChunkByMut<'a, T: 'a, P> { |
3396 | slice: &'a mut [T], |
3397 | predicate: P, |
3398 | } |
3399 | |
3400 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3401 | impl<'a, T: 'a, P> ChunkByMut<'a, T, P> { |
3402 | pub(super) const fn new(slice: &'a mut [T], predicate: P) -> Self { |
3403 | ChunkByMut { slice, predicate } |
3404 | } |
3405 | } |
3406 | |
3407 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3408 | impl<'a, T: 'a, P> Iterator for ChunkByMut<'a, T, P> |
3409 | where |
3410 | P: FnMut(&T, &T) -> bool, |
3411 | { |
3412 | type Item = &'a mut [T]; |
3413 | |
3414 | #[inline ] |
3415 | fn next(&mut self) -> Option<Self::Item> { |
3416 | if self.slice.is_empty() { |
3417 | None |
3418 | } else { |
3419 | let mut len = 1; |
3420 | let mut iter = self.slice.windows(2); |
3421 | while let Some([l, r]) = iter.next() { |
3422 | if (self.predicate)(l, r) { len += 1 } else { break } |
3423 | } |
3424 | let slice = mem::take(&mut self.slice); |
3425 | let (head, tail) = slice.split_at_mut(len); |
3426 | self.slice = tail; |
3427 | Some(head) |
3428 | } |
3429 | } |
3430 | |
3431 | #[inline ] |
3432 | fn size_hint(&self) -> (usize, Option<usize>) { |
3433 | if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) } |
3434 | } |
3435 | |
3436 | #[inline ] |
3437 | fn last(mut self) -> Option<Self::Item> { |
3438 | self.next_back() |
3439 | } |
3440 | } |
3441 | |
3442 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3443 | impl<'a, T: 'a, P> DoubleEndedIterator for ChunkByMut<'a, T, P> |
3444 | where |
3445 | P: FnMut(&T, &T) -> bool, |
3446 | { |
3447 | #[inline ] |
3448 | fn next_back(&mut self) -> Option<Self::Item> { |
3449 | if self.slice.is_empty() { |
3450 | None |
3451 | } else { |
3452 | let mut len: usize = 1; |
3453 | let mut iter: Windows<'_, T> = self.slice.windows(size:2); |
3454 | while let Some([l: &T, r: &T]) = iter.next_back() { |
3455 | if (self.predicate)(l, r) { len += 1 } else { break } |
3456 | } |
3457 | let slice: &'a mut [T] = mem::take(&mut self.slice); |
3458 | let (head: &mut [T], tail: &mut [T]) = slice.split_at_mut(mid:slice.len() - len); |
3459 | self.slice = head; |
3460 | Some(tail) |
3461 | } |
3462 | } |
3463 | } |
3464 | |
3465 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3466 | impl<'a, T: 'a, P> FusedIterator for ChunkByMut<'a, T, P> where P: FnMut(&T, &T) -> bool {} |
3467 | |
3468 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
3469 | impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for ChunkByMut<'a, T, P> { |
3470 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
3471 | f.debug_struct("ChunkByMut" ).field(name:"slice" , &self.slice).finish() |
3472 | } |
3473 | } |
3474 | |