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