1 | //! Slice management and manipulation. |
2 | //! |
3 | //! For more details see [`std::slice`]. |
4 | //! |
5 | //! [`std::slice`]: ../../std/slice/index.html |
6 | |
7 | #![stable (feature = "rust1" , since = "1.0.0" )] |
8 | |
9 | use crate::cmp::Ordering::{self, Equal, Greater, Less}; |
10 | use crate::fmt; |
11 | use crate::hint; |
12 | use crate::intrinsics::exact_div; |
13 | use crate::mem::{self, SizedTypeProperties}; |
14 | use crate::num::NonZeroUsize; |
15 | use crate::ops::{Bound, OneSidedRange, Range, RangeBounds}; |
16 | use crate::panic::debug_assert_nounwind; |
17 | use crate::ptr; |
18 | use crate::simd::{self, Simd}; |
19 | use crate::slice; |
20 | |
21 | #[unstable ( |
22 | feature = "slice_internals" , |
23 | issue = "none" , |
24 | reason = "exposed from core to be reused in std; use the memchr crate" |
25 | )] |
26 | /// Pure rust memchr implementation, taken from rust-memchr |
27 | pub mod memchr; |
28 | |
29 | #[unstable ( |
30 | feature = "slice_internals" , |
31 | issue = "none" , |
32 | reason = "exposed from core to be reused in std;" |
33 | )] |
34 | pub mod sort; |
35 | |
36 | mod ascii; |
37 | mod cmp; |
38 | pub(crate) mod index; |
39 | mod iter; |
40 | mod raw; |
41 | mod rotate; |
42 | mod select; |
43 | mod specialize; |
44 | |
45 | #[unstable (feature = "str_internals" , issue = "none" )] |
46 | #[doc (hidden)] |
47 | pub use ascii::is_ascii_simple; |
48 | |
49 | #[stable (feature = "rust1" , since = "1.0.0" )] |
50 | pub use iter::{Chunks, ChunksMut, Windows}; |
51 | #[stable (feature = "rust1" , since = "1.0.0" )] |
52 | pub use iter::{Iter, IterMut}; |
53 | #[stable (feature = "rust1" , since = "1.0.0" )] |
54 | pub use iter::{RSplitN, RSplitNMut, Split, SplitMut, SplitN, SplitNMut}; |
55 | |
56 | #[stable (feature = "slice_rsplit" , since = "1.27.0" )] |
57 | pub use iter::{RSplit, RSplitMut}; |
58 | |
59 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
60 | pub use iter::{ChunksExact, ChunksExactMut}; |
61 | |
62 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
63 | pub use iter::{RChunks, RChunksExact, RChunksExactMut, RChunksMut}; |
64 | |
65 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
66 | pub use iter::{ArrayChunks, ArrayChunksMut}; |
67 | |
68 | #[unstable (feature = "array_windows" , issue = "75027" )] |
69 | pub use iter::ArrayWindows; |
70 | |
71 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
72 | pub use iter::{ChunkBy, ChunkByMut}; |
73 | |
74 | #[stable (feature = "split_inclusive" , since = "1.51.0" )] |
75 | pub use iter::{SplitInclusive, SplitInclusiveMut}; |
76 | |
77 | #[stable (feature = "rust1" , since = "1.0.0" )] |
78 | pub use raw::{from_raw_parts, from_raw_parts_mut}; |
79 | |
80 | #[stable (feature = "from_ref" , since = "1.28.0" )] |
81 | pub use raw::{from_mut, from_ref}; |
82 | |
83 | #[unstable (feature = "slice_from_ptr_range" , issue = "89792" )] |
84 | pub use raw::{from_mut_ptr_range, from_ptr_range}; |
85 | |
86 | // This function is public only because there is no other way to unit test heapsort. |
87 | #[unstable (feature = "sort_internals" , reason = "internal to sort module" , issue = "none" )] |
88 | pub use sort::heapsort; |
89 | |
90 | #[stable (feature = "slice_get_slice" , since = "1.28.0" )] |
91 | pub use index::SliceIndex; |
92 | |
93 | #[unstable (feature = "slice_range" , issue = "76393" )] |
94 | pub use index::range; |
95 | |
96 | #[stable (feature = "inherent_ascii_escape" , since = "1.60.0" )] |
97 | pub use ascii::EscapeAscii; |
98 | |
99 | /// Calculates the direction and split point of a one-sided range. |
100 | /// |
101 | /// This is a helper function for `take` and `take_mut` that returns |
102 | /// the direction of the split (front or back) as well as the index at |
103 | /// which to split. Returns `None` if the split index would overflow. |
104 | #[inline ] |
105 | fn split_point_of(range: impl OneSidedRange<usize>) -> Option<(Direction, usize)> { |
106 | use Bound::*; |
107 | |
108 | Some(match (range.start_bound(), range.end_bound()) { |
109 | (Unbounded, Excluded(i: &usize)) => (Direction::Front, *i), |
110 | (Unbounded, Included(i: &usize)) => (Direction::Front, i.checked_add(1)?), |
111 | (Excluded(i: &usize), Unbounded) => (Direction::Back, i.checked_add(1)?), |
112 | (Included(i: &usize), Unbounded) => (Direction::Back, *i), |
113 | _ => unreachable!(), |
114 | }) |
115 | } |
116 | |
117 | enum Direction { |
118 | Front, |
119 | Back, |
120 | } |
121 | |
122 | #[cfg (not(test))] |
123 | impl<T> [T] { |
124 | /// Returns the number of elements in the slice. |
125 | /// |
126 | /// # Examples |
127 | /// |
128 | /// ``` |
129 | /// let a = [1, 2, 3]; |
130 | /// assert_eq!(a.len(), 3); |
131 | /// ``` |
132 | #[lang = "slice_len_fn" ] |
133 | #[stable (feature = "rust1" , since = "1.0.0" )] |
134 | #[rustc_const_stable (feature = "const_slice_len" , since = "1.39.0" )] |
135 | #[rustc_allow_const_fn_unstable (ptr_metadata)] |
136 | #[inline ] |
137 | #[must_use ] |
138 | pub const fn len(&self) -> usize { |
139 | ptr::metadata(self) |
140 | } |
141 | |
142 | /// Returns `true` if the slice has a length of 0. |
143 | /// |
144 | /// # Examples |
145 | /// |
146 | /// ``` |
147 | /// let a = [1, 2, 3]; |
148 | /// assert!(!a.is_empty()); |
149 | /// ``` |
150 | #[stable (feature = "rust1" , since = "1.0.0" )] |
151 | #[rustc_const_stable (feature = "const_slice_is_empty" , since = "1.39.0" )] |
152 | #[inline ] |
153 | #[must_use ] |
154 | pub const fn is_empty(&self) -> bool { |
155 | self.len() == 0 |
156 | } |
157 | |
158 | /// Returns the first element of the slice, or `None` if it is empty. |
159 | /// |
160 | /// # Examples |
161 | /// |
162 | /// ``` |
163 | /// let v = [10, 40, 30]; |
164 | /// assert_eq!(Some(&10), v.first()); |
165 | /// |
166 | /// let w: &[i32] = &[]; |
167 | /// assert_eq!(None, w.first()); |
168 | /// ``` |
169 | #[stable (feature = "rust1" , since = "1.0.0" )] |
170 | #[rustc_const_stable (feature = "const_slice_first_last_not_mut" , since = "1.56.0" )] |
171 | #[inline ] |
172 | #[must_use ] |
173 | pub const fn first(&self) -> Option<&T> { |
174 | if let [first, ..] = self { Some(first) } else { None } |
175 | } |
176 | |
177 | /// Returns a mutable pointer to the first element of the slice, or `None` if it is empty. |
178 | /// |
179 | /// # Examples |
180 | /// |
181 | /// ``` |
182 | /// let x = &mut [0, 1, 2]; |
183 | /// |
184 | /// if let Some(first) = x.first_mut() { |
185 | /// *first = 5; |
186 | /// } |
187 | /// assert_eq!(x, &[5, 1, 2]); |
188 | /// ``` |
189 | #[stable (feature = "rust1" , since = "1.0.0" )] |
190 | #[rustc_const_unstable (feature = "const_slice_first_last" , issue = "83570" )] |
191 | #[inline ] |
192 | #[must_use ] |
193 | pub const fn first_mut(&mut self) -> Option<&mut T> { |
194 | if let [first, ..] = self { Some(first) } else { None } |
195 | } |
196 | |
197 | /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty. |
198 | /// |
199 | /// # Examples |
200 | /// |
201 | /// ``` |
202 | /// let x = &[0, 1, 2]; |
203 | /// |
204 | /// if let Some((first, elements)) = x.split_first() { |
205 | /// assert_eq!(first, &0); |
206 | /// assert_eq!(elements, &[1, 2]); |
207 | /// } |
208 | /// ``` |
209 | #[stable (feature = "slice_splits" , since = "1.5.0" )] |
210 | #[rustc_const_stable (feature = "const_slice_first_last_not_mut" , since = "1.56.0" )] |
211 | #[inline ] |
212 | #[must_use ] |
213 | pub const fn split_first(&self) -> Option<(&T, &[T])> { |
214 | if let [first, tail @ ..] = self { Some((first, tail)) } else { None } |
215 | } |
216 | |
217 | /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty. |
218 | /// |
219 | /// # Examples |
220 | /// |
221 | /// ``` |
222 | /// let x = &mut [0, 1, 2]; |
223 | /// |
224 | /// if let Some((first, elements)) = x.split_first_mut() { |
225 | /// *first = 3; |
226 | /// elements[0] = 4; |
227 | /// elements[1] = 5; |
228 | /// } |
229 | /// assert_eq!(x, &[3, 4, 5]); |
230 | /// ``` |
231 | #[stable (feature = "slice_splits" , since = "1.5.0" )] |
232 | #[rustc_const_unstable (feature = "const_slice_first_last" , issue = "83570" )] |
233 | #[inline ] |
234 | #[must_use ] |
235 | pub const fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> { |
236 | if let [first, tail @ ..] = self { Some((first, tail)) } else { None } |
237 | } |
238 | |
239 | /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty. |
240 | /// |
241 | /// # Examples |
242 | /// |
243 | /// ``` |
244 | /// let x = &[0, 1, 2]; |
245 | /// |
246 | /// if let Some((last, elements)) = x.split_last() { |
247 | /// assert_eq!(last, &2); |
248 | /// assert_eq!(elements, &[0, 1]); |
249 | /// } |
250 | /// ``` |
251 | #[stable (feature = "slice_splits" , since = "1.5.0" )] |
252 | #[rustc_const_stable (feature = "const_slice_first_last_not_mut" , since = "1.56.0" )] |
253 | #[inline ] |
254 | #[must_use ] |
255 | pub const fn split_last(&self) -> Option<(&T, &[T])> { |
256 | if let [init @ .., last] = self { Some((last, init)) } else { None } |
257 | } |
258 | |
259 | /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty. |
260 | /// |
261 | /// # Examples |
262 | /// |
263 | /// ``` |
264 | /// let x = &mut [0, 1, 2]; |
265 | /// |
266 | /// if let Some((last, elements)) = x.split_last_mut() { |
267 | /// *last = 3; |
268 | /// elements[0] = 4; |
269 | /// elements[1] = 5; |
270 | /// } |
271 | /// assert_eq!(x, &[4, 5, 3]); |
272 | /// ``` |
273 | #[stable (feature = "slice_splits" , since = "1.5.0" )] |
274 | #[rustc_const_unstable (feature = "const_slice_first_last" , issue = "83570" )] |
275 | #[inline ] |
276 | #[must_use ] |
277 | pub const fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> { |
278 | if let [init @ .., last] = self { Some((last, init)) } else { None } |
279 | } |
280 | |
281 | /// Returns the last element of the slice, or `None` if it is empty. |
282 | /// |
283 | /// # Examples |
284 | /// |
285 | /// ``` |
286 | /// let v = [10, 40, 30]; |
287 | /// assert_eq!(Some(&30), v.last()); |
288 | /// |
289 | /// let w: &[i32] = &[]; |
290 | /// assert_eq!(None, w.last()); |
291 | /// ``` |
292 | #[stable (feature = "rust1" , since = "1.0.0" )] |
293 | #[rustc_const_stable (feature = "const_slice_first_last_not_mut" , since = "1.56.0" )] |
294 | #[inline ] |
295 | #[must_use ] |
296 | pub const fn last(&self) -> Option<&T> { |
297 | if let [.., last] = self { Some(last) } else { None } |
298 | } |
299 | |
300 | /// Returns a mutable reference to the last item in the slice. |
301 | /// |
302 | /// # Examples |
303 | /// |
304 | /// ``` |
305 | /// let x = &mut [0, 1, 2]; |
306 | /// |
307 | /// if let Some(last) = x.last_mut() { |
308 | /// *last = 10; |
309 | /// } |
310 | /// assert_eq!(x, &[0, 1, 10]); |
311 | /// ``` |
312 | #[stable (feature = "rust1" , since = "1.0.0" )] |
313 | #[rustc_const_unstable (feature = "const_slice_first_last" , issue = "83570" )] |
314 | #[inline ] |
315 | #[must_use ] |
316 | pub const fn last_mut(&mut self) -> Option<&mut T> { |
317 | if let [.., last] = self { Some(last) } else { None } |
318 | } |
319 | |
320 | /// Return an array reference to the first `N` items in the slice. |
321 | /// |
322 | /// If the slice is not at least `N` in length, this will return `None`. |
323 | /// |
324 | /// # Examples |
325 | /// |
326 | /// ``` |
327 | /// let u = [10, 40, 30]; |
328 | /// assert_eq!(Some(&[10, 40]), u.first_chunk::<2>()); |
329 | /// |
330 | /// let v: &[i32] = &[10]; |
331 | /// assert_eq!(None, v.first_chunk::<2>()); |
332 | /// |
333 | /// let w: &[i32] = &[]; |
334 | /// assert_eq!(Some(&[]), w.first_chunk::<0>()); |
335 | /// ``` |
336 | #[inline ] |
337 | #[stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
338 | #[rustc_const_stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
339 | pub const fn first_chunk<const N: usize>(&self) -> Option<&[T; N]> { |
340 | if self.len() < N { |
341 | None |
342 | } else { |
343 | // SAFETY: We explicitly check for the correct number of elements, |
344 | // and do not let the reference outlive the slice. |
345 | Some(unsafe { &*(self.as_ptr().cast::<[T; N]>()) }) |
346 | } |
347 | } |
348 | |
349 | /// Return a mutable array reference to the first `N` items in the slice. |
350 | /// |
351 | /// If the slice is not at least `N` in length, this will return `None`. |
352 | /// |
353 | /// # Examples |
354 | /// |
355 | /// ``` |
356 | /// let x = &mut [0, 1, 2]; |
357 | /// |
358 | /// if let Some(first) = x.first_chunk_mut::<2>() { |
359 | /// first[0] = 5; |
360 | /// first[1] = 4; |
361 | /// } |
362 | /// assert_eq!(x, &[5, 4, 2]); |
363 | /// |
364 | /// assert_eq!(None, x.first_chunk_mut::<4>()); |
365 | /// ``` |
366 | #[inline ] |
367 | #[stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
368 | #[rustc_const_unstable (feature = "const_slice_first_last_chunk" , issue = "111774" )] |
369 | pub const fn first_chunk_mut<const N: usize>(&mut self) -> Option<&mut [T; N]> { |
370 | if self.len() < N { |
371 | None |
372 | } else { |
373 | // SAFETY: We explicitly check for the correct number of elements, |
374 | // do not let the reference outlive the slice, |
375 | // and require exclusive access to the entire slice to mutate the chunk. |
376 | Some(unsafe { &mut *(self.as_mut_ptr().cast::<[T; N]>()) }) |
377 | } |
378 | } |
379 | |
380 | /// Return an array reference to the first `N` items in the slice and the remaining slice. |
381 | /// |
382 | /// If the slice is not at least `N` in length, this will return `None`. |
383 | /// |
384 | /// # Examples |
385 | /// |
386 | /// ``` |
387 | /// let x = &[0, 1, 2]; |
388 | /// |
389 | /// if let Some((first, elements)) = x.split_first_chunk::<2>() { |
390 | /// assert_eq!(first, &[0, 1]); |
391 | /// assert_eq!(elements, &[2]); |
392 | /// } |
393 | /// |
394 | /// assert_eq!(None, x.split_first_chunk::<4>()); |
395 | /// ``` |
396 | #[inline ] |
397 | #[stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
398 | #[rustc_const_stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
399 | pub const fn split_first_chunk<const N: usize>(&self) -> Option<(&[T; N], &[T])> { |
400 | if self.len() < N { |
401 | None |
402 | } else { |
403 | // SAFETY: We manually verified the bounds of the split. |
404 | let (first, tail) = unsafe { self.split_at_unchecked(N) }; |
405 | |
406 | // SAFETY: We explicitly check for the correct number of elements, |
407 | // and do not let the references outlive the slice. |
408 | Some((unsafe { &*(first.as_ptr().cast::<[T; N]>()) }, tail)) |
409 | } |
410 | } |
411 | |
412 | /// Return a mutable array reference to the first `N` items in the slice and the remaining |
413 | /// slice. |
414 | /// |
415 | /// If the slice is not at least `N` in length, this will return `None`. |
416 | /// |
417 | /// # Examples |
418 | /// |
419 | /// ``` |
420 | /// let x = &mut [0, 1, 2]; |
421 | /// |
422 | /// if let Some((first, elements)) = x.split_first_chunk_mut::<2>() { |
423 | /// first[0] = 3; |
424 | /// first[1] = 4; |
425 | /// elements[0] = 5; |
426 | /// } |
427 | /// assert_eq!(x, &[3, 4, 5]); |
428 | /// |
429 | /// assert_eq!(None, x.split_first_chunk_mut::<4>()); |
430 | /// ``` |
431 | #[inline ] |
432 | #[stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
433 | #[rustc_const_unstable (feature = "const_slice_first_last_chunk" , issue = "111774" )] |
434 | pub const fn split_first_chunk_mut<const N: usize>( |
435 | &mut self, |
436 | ) -> Option<(&mut [T; N], &mut [T])> { |
437 | if self.len() < N { |
438 | None |
439 | } else { |
440 | // SAFETY: We manually verified the bounds of the split. |
441 | let (first, tail) = unsafe { self.split_at_mut_unchecked(N) }; |
442 | |
443 | // SAFETY: We explicitly check for the correct number of elements, |
444 | // do not let the reference outlive the slice, |
445 | // and enforce exclusive mutability of the chunk by the split. |
446 | Some((unsafe { &mut *(first.as_mut_ptr().cast::<[T; N]>()) }, tail)) |
447 | } |
448 | } |
449 | |
450 | /// Return an array reference to the last `N` items in the slice and the remaining slice. |
451 | /// |
452 | /// If the slice is not at least `N` in length, this will return `None`. |
453 | /// |
454 | /// # Examples |
455 | /// |
456 | /// ``` |
457 | /// let x = &[0, 1, 2]; |
458 | /// |
459 | /// if let Some((elements, last)) = x.split_last_chunk::<2>() { |
460 | /// assert_eq!(elements, &[0]); |
461 | /// assert_eq!(last, &[1, 2]); |
462 | /// } |
463 | /// |
464 | /// assert_eq!(None, x.split_last_chunk::<4>()); |
465 | /// ``` |
466 | #[inline ] |
467 | #[stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
468 | #[rustc_const_stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
469 | pub const fn split_last_chunk<const N: usize>(&self) -> Option<(&[T], &[T; N])> { |
470 | if self.len() < N { |
471 | None |
472 | } else { |
473 | // SAFETY: We manually verified the bounds of the split. |
474 | let (init, last) = unsafe { self.split_at_unchecked(self.len() - N) }; |
475 | |
476 | // SAFETY: We explicitly check for the correct number of elements, |
477 | // and do not let the references outlive the slice. |
478 | Some((init, unsafe { &*(last.as_ptr().cast::<[T; N]>()) })) |
479 | } |
480 | } |
481 | |
482 | /// Return a mutable array reference to the last `N` items in the slice and the remaining |
483 | /// slice. |
484 | /// |
485 | /// If the slice is not at least `N` in length, this will return `None`. |
486 | /// |
487 | /// # Examples |
488 | /// |
489 | /// ``` |
490 | /// let x = &mut [0, 1, 2]; |
491 | /// |
492 | /// if let Some((elements, last)) = x.split_last_chunk_mut::<2>() { |
493 | /// last[0] = 3; |
494 | /// last[1] = 4; |
495 | /// elements[0] = 5; |
496 | /// } |
497 | /// assert_eq!(x, &[5, 3, 4]); |
498 | /// |
499 | /// assert_eq!(None, x.split_last_chunk_mut::<4>()); |
500 | /// ``` |
501 | #[inline ] |
502 | #[stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
503 | #[rustc_const_unstable (feature = "const_slice_first_last_chunk" , issue = "111774" )] |
504 | pub const fn split_last_chunk_mut<const N: usize>( |
505 | &mut self, |
506 | ) -> Option<(&mut [T], &mut [T; N])> { |
507 | if self.len() < N { |
508 | None |
509 | } else { |
510 | // SAFETY: We manually verified the bounds of the split. |
511 | let (init, last) = unsafe { self.split_at_mut_unchecked(self.len() - N) }; |
512 | |
513 | // SAFETY: We explicitly check for the correct number of elements, |
514 | // do not let the reference outlive the slice, |
515 | // and enforce exclusive mutability of the chunk by the split. |
516 | Some((init, unsafe { &mut *(last.as_mut_ptr().cast::<[T; N]>()) })) |
517 | } |
518 | } |
519 | |
520 | /// Return an array reference to the last `N` items in the slice. |
521 | /// |
522 | /// If the slice is not at least `N` in length, this will return `None`. |
523 | /// |
524 | /// # Examples |
525 | /// |
526 | /// ``` |
527 | /// let u = [10, 40, 30]; |
528 | /// assert_eq!(Some(&[40, 30]), u.last_chunk::<2>()); |
529 | /// |
530 | /// let v: &[i32] = &[10]; |
531 | /// assert_eq!(None, v.last_chunk::<2>()); |
532 | /// |
533 | /// let w: &[i32] = &[]; |
534 | /// assert_eq!(Some(&[]), w.last_chunk::<0>()); |
535 | /// ``` |
536 | #[inline ] |
537 | #[stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
538 | #[rustc_const_unstable (feature = "const_slice_first_last_chunk" , issue = "111774" )] |
539 | pub const fn last_chunk<const N: usize>(&self) -> Option<&[T; N]> { |
540 | if self.len() < N { |
541 | None |
542 | } else { |
543 | // SAFETY: We manually verified the bounds of the slice. |
544 | // FIXME: Without const traits, we need this instead of `get_unchecked`. |
545 | let last = unsafe { self.split_at_unchecked(self.len() - N).1 }; |
546 | |
547 | // SAFETY: We explicitly check for the correct number of elements, |
548 | // and do not let the references outlive the slice. |
549 | Some(unsafe { &*(last.as_ptr().cast::<[T; N]>()) }) |
550 | } |
551 | } |
552 | |
553 | /// Return a mutable array reference to the last `N` items in the slice. |
554 | /// |
555 | /// If the slice is not at least `N` in length, this will return `None`. |
556 | /// |
557 | /// # Examples |
558 | /// |
559 | /// ``` |
560 | /// let x = &mut [0, 1, 2]; |
561 | /// |
562 | /// if let Some(last) = x.last_chunk_mut::<2>() { |
563 | /// last[0] = 10; |
564 | /// last[1] = 20; |
565 | /// } |
566 | /// assert_eq!(x, &[0, 10, 20]); |
567 | /// |
568 | /// assert_eq!(None, x.last_chunk_mut::<4>()); |
569 | /// ``` |
570 | #[inline ] |
571 | #[stable (feature = "slice_first_last_chunk" , since = "1.77.0" )] |
572 | #[rustc_const_unstable (feature = "const_slice_first_last_chunk" , issue = "111774" )] |
573 | pub const fn last_chunk_mut<const N: usize>(&mut self) -> Option<&mut [T; N]> { |
574 | if self.len() < N { |
575 | None |
576 | } else { |
577 | // SAFETY: We manually verified the bounds of the slice. |
578 | // FIXME: Without const traits, we need this instead of `get_unchecked`. |
579 | let last = unsafe { self.split_at_mut_unchecked(self.len() - N).1 }; |
580 | |
581 | // SAFETY: We explicitly check for the correct number of elements, |
582 | // do not let the reference outlive the slice, |
583 | // and require exclusive access to the entire slice to mutate the chunk. |
584 | Some(unsafe { &mut *(last.as_mut_ptr().cast::<[T; N]>()) }) |
585 | } |
586 | } |
587 | |
588 | /// Returns a reference to an element or subslice depending on the type of |
589 | /// index. |
590 | /// |
591 | /// - If given a position, returns a reference to the element at that |
592 | /// position or `None` if out of bounds. |
593 | /// - If given a range, returns the subslice corresponding to that range, |
594 | /// or `None` if out of bounds. |
595 | /// |
596 | /// # Examples |
597 | /// |
598 | /// ``` |
599 | /// let v = [10, 40, 30]; |
600 | /// assert_eq!(Some(&40), v.get(1)); |
601 | /// assert_eq!(Some(&[10, 40][..]), v.get(0..2)); |
602 | /// assert_eq!(None, v.get(3)); |
603 | /// assert_eq!(None, v.get(0..4)); |
604 | /// ``` |
605 | #[stable (feature = "rust1" , since = "1.0.0" )] |
606 | #[inline ] |
607 | #[must_use ] |
608 | pub fn get<I>(&self, index: I) -> Option<&I::Output> |
609 | where |
610 | I: SliceIndex<Self>, |
611 | { |
612 | index.get(self) |
613 | } |
614 | |
615 | /// Returns a mutable reference to an element or subslice depending on the |
616 | /// type of index (see [`get`]) or `None` if the index is out of bounds. |
617 | /// |
618 | /// [`get`]: slice::get |
619 | /// |
620 | /// # Examples |
621 | /// |
622 | /// ``` |
623 | /// let x = &mut [0, 1, 2]; |
624 | /// |
625 | /// if let Some(elem) = x.get_mut(1) { |
626 | /// *elem = 42; |
627 | /// } |
628 | /// assert_eq!(x, &[0, 42, 2]); |
629 | /// ``` |
630 | #[stable (feature = "rust1" , since = "1.0.0" )] |
631 | #[inline ] |
632 | #[must_use ] |
633 | pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output> |
634 | where |
635 | I: SliceIndex<Self>, |
636 | { |
637 | index.get_mut(self) |
638 | } |
639 | |
640 | /// Returns a reference to an element or subslice, without doing bounds |
641 | /// checking. |
642 | /// |
643 | /// For a safe alternative see [`get`]. |
644 | /// |
645 | /// # Safety |
646 | /// |
647 | /// Calling this method with an out-of-bounds index is *[undefined behavior]* |
648 | /// even if the resulting reference is not used. |
649 | /// |
650 | /// You can think of this like `.get(index).unwrap_unchecked()`. It's UB |
651 | /// to call `.get_unchecked(len)`, even if you immediately convert to a |
652 | /// pointer. And it's UB to call `.get_unchecked(..len + 1)`, |
653 | /// `.get_unchecked(..=len)`, or similar. |
654 | /// |
655 | /// [`get`]: slice::get |
656 | /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html |
657 | /// |
658 | /// # Examples |
659 | /// |
660 | /// ``` |
661 | /// let x = &[1, 2, 4]; |
662 | /// |
663 | /// unsafe { |
664 | /// assert_eq!(x.get_unchecked(1), &2); |
665 | /// } |
666 | /// ``` |
667 | #[stable (feature = "rust1" , since = "1.0.0" )] |
668 | #[inline ] |
669 | #[must_use ] |
670 | pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output |
671 | where |
672 | I: SliceIndex<Self>, |
673 | { |
674 | // SAFETY: the caller must uphold most of the safety requirements for `get_unchecked`; |
675 | // the slice is dereferenceable because `self` is a safe reference. |
676 | // The returned pointer is safe because impls of `SliceIndex` have to guarantee that it is. |
677 | unsafe { &*index.get_unchecked(self) } |
678 | } |
679 | |
680 | /// Returns a mutable reference to an element or subslice, without doing |
681 | /// bounds checking. |
682 | /// |
683 | /// For a safe alternative see [`get_mut`]. |
684 | /// |
685 | /// # Safety |
686 | /// |
687 | /// Calling this method with an out-of-bounds index is *[undefined behavior]* |
688 | /// even if the resulting reference is not used. |
689 | /// |
690 | /// You can think of this like `.get_mut(index).unwrap_unchecked()`. It's |
691 | /// UB to call `.get_unchecked_mut(len)`, even if you immediately convert |
692 | /// to a pointer. And it's UB to call `.get_unchecked_mut(..len + 1)`, |
693 | /// `.get_unchecked_mut(..=len)`, or similar. |
694 | /// |
695 | /// [`get_mut`]: slice::get_mut |
696 | /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html |
697 | /// |
698 | /// # Examples |
699 | /// |
700 | /// ``` |
701 | /// let x = &mut [1, 2, 4]; |
702 | /// |
703 | /// unsafe { |
704 | /// let elem = x.get_unchecked_mut(1); |
705 | /// *elem = 13; |
706 | /// } |
707 | /// assert_eq!(x, &[1, 13, 4]); |
708 | /// ``` |
709 | #[stable (feature = "rust1" , since = "1.0.0" )] |
710 | #[inline ] |
711 | #[must_use ] |
712 | pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output |
713 | where |
714 | I: SliceIndex<Self>, |
715 | { |
716 | // SAFETY: the caller must uphold the safety requirements for `get_unchecked_mut`; |
717 | // the slice is dereferenceable because `self` is a safe reference. |
718 | // The returned pointer is safe because impls of `SliceIndex` have to guarantee that it is. |
719 | unsafe { &mut *index.get_unchecked_mut(self) } |
720 | } |
721 | |
722 | /// Returns a raw pointer to the slice's buffer. |
723 | /// |
724 | /// The caller must ensure that the slice outlives the pointer this |
725 | /// function returns, or else it will end up pointing to garbage. |
726 | /// |
727 | /// The caller must also ensure that the memory the pointer (non-transitively) points to |
728 | /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer |
729 | /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`]. |
730 | /// |
731 | /// Modifying the container referenced by this slice may cause its buffer |
732 | /// to be reallocated, which would also make any pointers to it invalid. |
733 | /// |
734 | /// # Examples |
735 | /// |
736 | /// ``` |
737 | /// let x = &[1, 2, 4]; |
738 | /// let x_ptr = x.as_ptr(); |
739 | /// |
740 | /// unsafe { |
741 | /// for i in 0..x.len() { |
742 | /// assert_eq!(x.get_unchecked(i), &*x_ptr.add(i)); |
743 | /// } |
744 | /// } |
745 | /// ``` |
746 | /// |
747 | /// [`as_mut_ptr`]: slice::as_mut_ptr |
748 | #[stable (feature = "rust1" , since = "1.0.0" )] |
749 | #[rustc_const_stable (feature = "const_slice_as_ptr" , since = "1.32.0" )] |
750 | #[rustc_never_returns_null_ptr ] |
751 | #[inline (always)] |
752 | #[must_use ] |
753 | pub const fn as_ptr(&self) -> *const T { |
754 | self as *const [T] as *const T |
755 | } |
756 | |
757 | /// Returns an unsafe mutable pointer to the slice's buffer. |
758 | /// |
759 | /// The caller must ensure that the slice outlives the pointer this |
760 | /// function returns, or else it will end up pointing to garbage. |
761 | /// |
762 | /// Modifying the container referenced by this slice may cause its buffer |
763 | /// to be reallocated, which would also make any pointers to it invalid. |
764 | /// |
765 | /// # Examples |
766 | /// |
767 | /// ``` |
768 | /// let x = &mut [1, 2, 4]; |
769 | /// let x_ptr = x.as_mut_ptr(); |
770 | /// |
771 | /// unsafe { |
772 | /// for i in 0..x.len() { |
773 | /// *x_ptr.add(i) += 2; |
774 | /// } |
775 | /// } |
776 | /// assert_eq!(x, &[3, 4, 6]); |
777 | /// ``` |
778 | #[stable (feature = "rust1" , since = "1.0.0" )] |
779 | #[rustc_const_stable (feature = "const_ptr_offset" , since = "1.61.0" )] |
780 | #[rustc_allow_const_fn_unstable (const_mut_refs)] |
781 | #[rustc_never_returns_null_ptr ] |
782 | #[inline (always)] |
783 | #[must_use ] |
784 | pub const fn as_mut_ptr(&mut self) -> *mut T { |
785 | self as *mut [T] as *mut T |
786 | } |
787 | |
788 | /// Returns the two raw pointers spanning the slice. |
789 | /// |
790 | /// The returned range is half-open, which means that the end pointer |
791 | /// points *one past* the last element of the slice. This way, an empty |
792 | /// slice is represented by two equal pointers, and the difference between |
793 | /// the two pointers represents the size of the slice. |
794 | /// |
795 | /// See [`as_ptr`] for warnings on using these pointers. The end pointer |
796 | /// requires extra caution, as it does not point to a valid element in the |
797 | /// slice. |
798 | /// |
799 | /// This function is useful for interacting with foreign interfaces which |
800 | /// use two pointers to refer to a range of elements in memory, as is |
801 | /// common in C++. |
802 | /// |
803 | /// It can also be useful to check if a pointer to an element refers to an |
804 | /// element of this slice: |
805 | /// |
806 | /// ``` |
807 | /// let a = [1, 2, 3]; |
808 | /// let x = &a[1] as *const _; |
809 | /// let y = &5 as *const _; |
810 | /// |
811 | /// assert!(a.as_ptr_range().contains(&x)); |
812 | /// assert!(!a.as_ptr_range().contains(&y)); |
813 | /// ``` |
814 | /// |
815 | /// [`as_ptr`]: slice::as_ptr |
816 | #[stable (feature = "slice_ptr_range" , since = "1.48.0" )] |
817 | #[rustc_const_stable (feature = "const_ptr_offset" , since = "1.61.0" )] |
818 | #[inline ] |
819 | #[must_use ] |
820 | pub const fn as_ptr_range(&self) -> Range<*const T> { |
821 | let start = self.as_ptr(); |
822 | // SAFETY: The `add` here is safe, because: |
823 | // |
824 | // - Both pointers are part of the same object, as pointing directly |
825 | // past the object also counts. |
826 | // |
827 | // - The size of the slice is never larger than isize::MAX bytes, as |
828 | // noted here: |
829 | // - https://github.com/rust-lang/unsafe-code-guidelines/issues/102#issuecomment-473340447 |
830 | // - https://doc.rust-lang.org/reference/behavior-considered-undefined.html |
831 | // - https://doc.rust-lang.org/core/slice/fn.from_raw_parts.html#safety |
832 | // (This doesn't seem normative yet, but the very same assumption is |
833 | // made in many places, including the Index implementation of slices.) |
834 | // |
835 | // - There is no wrapping around involved, as slices do not wrap past |
836 | // the end of the address space. |
837 | // |
838 | // See the documentation of pointer::add. |
839 | let end = unsafe { start.add(self.len()) }; |
840 | start..end |
841 | } |
842 | |
843 | /// Returns the two unsafe mutable pointers spanning the slice. |
844 | /// |
845 | /// The returned range is half-open, which means that the end pointer |
846 | /// points *one past* the last element of the slice. This way, an empty |
847 | /// slice is represented by two equal pointers, and the difference between |
848 | /// the two pointers represents the size of the slice. |
849 | /// |
850 | /// See [`as_mut_ptr`] for warnings on using these pointers. The end |
851 | /// pointer requires extra caution, as it does not point to a valid element |
852 | /// in the slice. |
853 | /// |
854 | /// This function is useful for interacting with foreign interfaces which |
855 | /// use two pointers to refer to a range of elements in memory, as is |
856 | /// common in C++. |
857 | /// |
858 | /// [`as_mut_ptr`]: slice::as_mut_ptr |
859 | #[stable (feature = "slice_ptr_range" , since = "1.48.0" )] |
860 | #[rustc_const_stable (feature = "const_ptr_offset" , since = "1.61.0" )] |
861 | #[rustc_allow_const_fn_unstable (const_mut_refs)] |
862 | #[inline ] |
863 | #[must_use ] |
864 | pub const fn as_mut_ptr_range(&mut self) -> Range<*mut T> { |
865 | let start = self.as_mut_ptr(); |
866 | // SAFETY: See as_ptr_range() above for why `add` here is safe. |
867 | let end = unsafe { start.add(self.len()) }; |
868 | start..end |
869 | } |
870 | |
871 | /// Swaps two elements in the slice. |
872 | /// |
873 | /// If `a` equals to `b`, it's guaranteed that elements won't change value. |
874 | /// |
875 | /// # Arguments |
876 | /// |
877 | /// * a - The index of the first element |
878 | /// * b - The index of the second element |
879 | /// |
880 | /// # Panics |
881 | /// |
882 | /// Panics if `a` or `b` are out of bounds. |
883 | /// |
884 | /// # Examples |
885 | /// |
886 | /// ``` |
887 | /// let mut v = ["a" , "b" , "c" , "d" , "e" ]; |
888 | /// v.swap(2, 4); |
889 | /// assert!(v == ["a" , "b" , "e" , "d" , "c" ]); |
890 | /// ``` |
891 | #[stable (feature = "rust1" , since = "1.0.0" )] |
892 | #[rustc_const_unstable (feature = "const_swap" , issue = "83163" )] |
893 | #[inline ] |
894 | #[track_caller ] |
895 | pub const fn swap(&mut self, a: usize, b: usize) { |
896 | // FIXME: use swap_unchecked here (https://github.com/rust-lang/rust/pull/88540#issuecomment-944344343) |
897 | // Can't take two mutable loans from one vector, so instead use raw pointers. |
898 | let pa = ptr::addr_of_mut!(self[a]); |
899 | let pb = ptr::addr_of_mut!(self[b]); |
900 | // SAFETY: `pa` and `pb` have been created from safe mutable references and refer |
901 | // to elements in the slice and therefore are guaranteed to be valid and aligned. |
902 | // Note that accessing the elements behind `a` and `b` is checked and will |
903 | // panic when out of bounds. |
904 | unsafe { |
905 | ptr::swap(pa, pb); |
906 | } |
907 | } |
908 | |
909 | /// Swaps two elements in the slice, without doing bounds checking. |
910 | /// |
911 | /// For a safe alternative see [`swap`]. |
912 | /// |
913 | /// # Arguments |
914 | /// |
915 | /// * a - The index of the first element |
916 | /// * b - The index of the second element |
917 | /// |
918 | /// # Safety |
919 | /// |
920 | /// Calling this method with an out-of-bounds index is *[undefined behavior]*. |
921 | /// The caller has to ensure that `a < self.len()` and `b < self.len()`. |
922 | /// |
923 | /// # Examples |
924 | /// |
925 | /// ``` |
926 | /// #![feature(slice_swap_unchecked)] |
927 | /// |
928 | /// let mut v = ["a" , "b" , "c" , "d" ]; |
929 | /// // SAFETY: we know that 1 and 3 are both indices of the slice |
930 | /// unsafe { v.swap_unchecked(1, 3) }; |
931 | /// assert!(v == ["a" , "d" , "c" , "b" ]); |
932 | /// ``` |
933 | /// |
934 | /// [`swap`]: slice::swap |
935 | /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html |
936 | #[unstable (feature = "slice_swap_unchecked" , issue = "88539" )] |
937 | #[rustc_const_unstable (feature = "const_swap" , issue = "83163" )] |
938 | pub const unsafe fn swap_unchecked(&mut self, a: usize, b: usize) { |
939 | debug_assert_nounwind!( |
940 | a < self.len() && b < self.len(), |
941 | "slice::swap_unchecked requires that the indices are within the slice" , |
942 | ); |
943 | |
944 | let ptr = self.as_mut_ptr(); |
945 | // SAFETY: caller has to guarantee that `a < self.len()` and `b < self.len()` |
946 | unsafe { |
947 | ptr::swap(ptr.add(a), ptr.add(b)); |
948 | } |
949 | } |
950 | |
951 | /// Reverses the order of elements in the slice, in place. |
952 | /// |
953 | /// # Examples |
954 | /// |
955 | /// ``` |
956 | /// let mut v = [1, 2, 3]; |
957 | /// v.reverse(); |
958 | /// assert!(v == [3, 2, 1]); |
959 | /// ``` |
960 | #[stable (feature = "rust1" , since = "1.0.0" )] |
961 | #[inline ] |
962 | pub fn reverse(&mut self) { |
963 | let half_len = self.len() / 2; |
964 | let Range { start, end } = self.as_mut_ptr_range(); |
965 | |
966 | // These slices will skip the middle item for an odd length, |
967 | // since that one doesn't need to move. |
968 | let (front_half, back_half) = |
969 | // SAFETY: Both are subparts of the original slice, so the memory |
970 | // range is valid, and they don't overlap because they're each only |
971 | // half (or less) of the original slice. |
972 | unsafe { |
973 | ( |
974 | slice::from_raw_parts_mut(start, half_len), |
975 | slice::from_raw_parts_mut(end.sub(half_len), half_len), |
976 | ) |
977 | }; |
978 | |
979 | // Introducing a function boundary here means that the two halves |
980 | // get `noalias` markers, allowing better optimization as LLVM |
981 | // knows that they're disjoint, unlike in the original slice. |
982 | revswap(front_half, back_half, half_len); |
983 | |
984 | #[inline ] |
985 | fn revswap<T>(a: &mut [T], b: &mut [T], n: usize) { |
986 | debug_assert!(a.len() == n); |
987 | debug_assert!(b.len() == n); |
988 | |
989 | // Because this function is first compiled in isolation, |
990 | // this check tells LLVM that the indexing below is |
991 | // in-bounds. Then after inlining -- once the actual |
992 | // lengths of the slices are known -- it's removed. |
993 | let (a, b) = (&mut a[..n], &mut b[..n]); |
994 | |
995 | let mut i = 0; |
996 | while i < n { |
997 | mem::swap(&mut a[i], &mut b[n - 1 - i]); |
998 | i += 1; |
999 | } |
1000 | } |
1001 | } |
1002 | |
1003 | /// Returns an iterator over the slice. |
1004 | /// |
1005 | /// The iterator yields all items from start to end. |
1006 | /// |
1007 | /// # Examples |
1008 | /// |
1009 | /// ``` |
1010 | /// let x = &[1, 2, 4]; |
1011 | /// let mut iterator = x.iter(); |
1012 | /// |
1013 | /// assert_eq!(iterator.next(), Some(&1)); |
1014 | /// assert_eq!(iterator.next(), Some(&2)); |
1015 | /// assert_eq!(iterator.next(), Some(&4)); |
1016 | /// assert_eq!(iterator.next(), None); |
1017 | /// ``` |
1018 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1019 | #[inline ] |
1020 | pub fn iter(&self) -> Iter<'_, T> { |
1021 | Iter::new(self) |
1022 | } |
1023 | |
1024 | /// Returns an iterator that allows modifying each value. |
1025 | /// |
1026 | /// The iterator yields all items from start to end. |
1027 | /// |
1028 | /// # Examples |
1029 | /// |
1030 | /// ``` |
1031 | /// let x = &mut [1, 2, 4]; |
1032 | /// for elem in x.iter_mut() { |
1033 | /// *elem += 2; |
1034 | /// } |
1035 | /// assert_eq!(x, &[3, 4, 6]); |
1036 | /// ``` |
1037 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1038 | #[inline ] |
1039 | pub fn iter_mut(&mut self) -> IterMut<'_, T> { |
1040 | IterMut::new(self) |
1041 | } |
1042 | |
1043 | /// Returns an iterator over all contiguous windows of length |
1044 | /// `size`. The windows overlap. If the slice is shorter than |
1045 | /// `size`, the iterator returns no values. |
1046 | /// |
1047 | /// # Panics |
1048 | /// |
1049 | /// Panics if `size` is 0. |
1050 | /// |
1051 | /// # Examples |
1052 | /// |
1053 | /// ``` |
1054 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1055 | /// let mut iter = slice.windows(3); |
1056 | /// assert_eq!(iter.next().unwrap(), &['l' , 'o' , 'r' ]); |
1057 | /// assert_eq!(iter.next().unwrap(), &['o' , 'r' , 'e' ]); |
1058 | /// assert_eq!(iter.next().unwrap(), &['r' , 'e' , 'm' ]); |
1059 | /// assert!(iter.next().is_none()); |
1060 | /// ``` |
1061 | /// |
1062 | /// If the slice is shorter than `size`: |
1063 | /// |
1064 | /// ``` |
1065 | /// let slice = ['f' , 'o' , 'o' ]; |
1066 | /// let mut iter = slice.windows(4); |
1067 | /// assert!(iter.next().is_none()); |
1068 | /// ``` |
1069 | /// |
1070 | /// There's no `windows_mut`, as that existing would let safe code violate the |
1071 | /// "only one `&mut` at a time to the same thing" rule. However, you can sometimes |
1072 | /// use [`Cell::as_slice_of_cells`](crate::cell::Cell::as_slice_of_cells) in |
1073 | /// conjunction with `windows` to accomplish something similar: |
1074 | /// ``` |
1075 | /// use std::cell::Cell; |
1076 | /// |
1077 | /// let mut array = ['R' , 'u' , 's' , 't' , ' ' , '2' , '0' , '1' , '5' ]; |
1078 | /// let slice = &mut array[..]; |
1079 | /// let slice_of_cells: &[Cell<char>] = Cell::from_mut(slice).as_slice_of_cells(); |
1080 | /// for w in slice_of_cells.windows(3) { |
1081 | /// Cell::swap(&w[0], &w[2]); |
1082 | /// } |
1083 | /// assert_eq!(array, ['s' , 't' , ' ' , '2' , '0' , '1' , '5' , 'u' , 'R' ]); |
1084 | /// ``` |
1085 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1086 | #[inline ] |
1087 | #[track_caller ] |
1088 | pub fn windows(&self, size: usize) -> Windows<'_, T> { |
1089 | let size = NonZeroUsize::new(size).expect("window size must be non-zero" ); |
1090 | Windows::new(self, size) |
1091 | } |
1092 | |
1093 | /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the |
1094 | /// beginning of the slice. |
1095 | /// |
1096 | /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the |
1097 | /// slice, then the last chunk will not have length `chunk_size`. |
1098 | /// |
1099 | /// See [`chunks_exact`] for a variant of this iterator that returns chunks of always exactly |
1100 | /// `chunk_size` elements, and [`rchunks`] for the same iterator but starting at the end of the |
1101 | /// slice. |
1102 | /// |
1103 | /// # Panics |
1104 | /// |
1105 | /// Panics if `chunk_size` is 0. |
1106 | /// |
1107 | /// # Examples |
1108 | /// |
1109 | /// ``` |
1110 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1111 | /// let mut iter = slice.chunks(2); |
1112 | /// assert_eq!(iter.next().unwrap(), &['l' , 'o' ]); |
1113 | /// assert_eq!(iter.next().unwrap(), &['r' , 'e' ]); |
1114 | /// assert_eq!(iter.next().unwrap(), &['m' ]); |
1115 | /// assert!(iter.next().is_none()); |
1116 | /// ``` |
1117 | /// |
1118 | /// [`chunks_exact`]: slice::chunks_exact |
1119 | /// [`rchunks`]: slice::rchunks |
1120 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1121 | #[inline ] |
1122 | #[track_caller ] |
1123 | pub fn chunks(&self, chunk_size: usize) -> Chunks<'_, T> { |
1124 | assert!(chunk_size != 0, "chunk size must be non-zero" ); |
1125 | Chunks::new(self, chunk_size) |
1126 | } |
1127 | |
1128 | /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the |
1129 | /// beginning of the slice. |
1130 | /// |
1131 | /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the |
1132 | /// length of the slice, then the last chunk will not have length `chunk_size`. |
1133 | /// |
1134 | /// See [`chunks_exact_mut`] for a variant of this iterator that returns chunks of always |
1135 | /// exactly `chunk_size` elements, and [`rchunks_mut`] for the same iterator but starting at |
1136 | /// the end of the slice. |
1137 | /// |
1138 | /// # Panics |
1139 | /// |
1140 | /// Panics if `chunk_size` is 0. |
1141 | /// |
1142 | /// # Examples |
1143 | /// |
1144 | /// ``` |
1145 | /// let v = &mut [0, 0, 0, 0, 0]; |
1146 | /// let mut count = 1; |
1147 | /// |
1148 | /// for chunk in v.chunks_mut(2) { |
1149 | /// for elem in chunk.iter_mut() { |
1150 | /// *elem += count; |
1151 | /// } |
1152 | /// count += 1; |
1153 | /// } |
1154 | /// assert_eq!(v, &[1, 1, 2, 2, 3]); |
1155 | /// ``` |
1156 | /// |
1157 | /// [`chunks_exact_mut`]: slice::chunks_exact_mut |
1158 | /// [`rchunks_mut`]: slice::rchunks_mut |
1159 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1160 | #[inline ] |
1161 | #[track_caller ] |
1162 | pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T> { |
1163 | assert!(chunk_size != 0, "chunk size must be non-zero" ); |
1164 | ChunksMut::new(self, chunk_size) |
1165 | } |
1166 | |
1167 | /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the |
1168 | /// beginning of the slice. |
1169 | /// |
1170 | /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the |
1171 | /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved |
1172 | /// from the `remainder` function of the iterator. |
1173 | /// |
1174 | /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the |
1175 | /// resulting code better than in the case of [`chunks`]. |
1176 | /// |
1177 | /// See [`chunks`] for a variant of this iterator that also returns the remainder as a smaller |
1178 | /// chunk, and [`rchunks_exact`] for the same iterator but starting at the end of the slice. |
1179 | /// |
1180 | /// # Panics |
1181 | /// |
1182 | /// Panics if `chunk_size` is 0. |
1183 | /// |
1184 | /// # Examples |
1185 | /// |
1186 | /// ``` |
1187 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1188 | /// let mut iter = slice.chunks_exact(2); |
1189 | /// assert_eq!(iter.next().unwrap(), &['l' , 'o' ]); |
1190 | /// assert_eq!(iter.next().unwrap(), &['r' , 'e' ]); |
1191 | /// assert!(iter.next().is_none()); |
1192 | /// assert_eq!(iter.remainder(), &['m' ]); |
1193 | /// ``` |
1194 | /// |
1195 | /// [`chunks`]: slice::chunks |
1196 | /// [`rchunks_exact`]: slice::rchunks_exact |
1197 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1198 | #[inline ] |
1199 | #[track_caller ] |
1200 | pub fn chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T> { |
1201 | assert!(chunk_size != 0, "chunk size must be non-zero" ); |
1202 | ChunksExact::new(self, chunk_size) |
1203 | } |
1204 | |
1205 | /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the |
1206 | /// beginning of the slice. |
1207 | /// |
1208 | /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the |
1209 | /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be |
1210 | /// retrieved from the `into_remainder` function of the iterator. |
1211 | /// |
1212 | /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the |
1213 | /// resulting code better than in the case of [`chunks_mut`]. |
1214 | /// |
1215 | /// See [`chunks_mut`] for a variant of this iterator that also returns the remainder as a |
1216 | /// smaller chunk, and [`rchunks_exact_mut`] for the same iterator but starting at the end of |
1217 | /// the slice. |
1218 | /// |
1219 | /// # Panics |
1220 | /// |
1221 | /// Panics if `chunk_size` is 0. |
1222 | /// |
1223 | /// # Examples |
1224 | /// |
1225 | /// ``` |
1226 | /// let v = &mut [0, 0, 0, 0, 0]; |
1227 | /// let mut count = 1; |
1228 | /// |
1229 | /// for chunk in v.chunks_exact_mut(2) { |
1230 | /// for elem in chunk.iter_mut() { |
1231 | /// *elem += count; |
1232 | /// } |
1233 | /// count += 1; |
1234 | /// } |
1235 | /// assert_eq!(v, &[1, 1, 2, 2, 0]); |
1236 | /// ``` |
1237 | /// |
1238 | /// [`chunks_mut`]: slice::chunks_mut |
1239 | /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut |
1240 | #[stable (feature = "chunks_exact" , since = "1.31.0" )] |
1241 | #[inline ] |
1242 | #[track_caller ] |
1243 | pub fn chunks_exact_mut(&mut self, chunk_size: usize) -> ChunksExactMut<'_, T> { |
1244 | assert!(chunk_size != 0, "chunk size must be non-zero" ); |
1245 | ChunksExactMut::new(self, chunk_size) |
1246 | } |
1247 | |
1248 | /// Splits the slice into a slice of `N`-element arrays, |
1249 | /// assuming that there's no remainder. |
1250 | /// |
1251 | /// # Safety |
1252 | /// |
1253 | /// This may only be called when |
1254 | /// - The slice splits exactly into `N`-element chunks (aka `self.len() % N == 0`). |
1255 | /// - `N != 0`. |
1256 | /// |
1257 | /// # Examples |
1258 | /// |
1259 | /// ``` |
1260 | /// #![feature(slice_as_chunks)] |
1261 | /// let slice: &[char] = &['l' , 'o' , 'r' , 'e' , 'm' , '!' ]; |
1262 | /// let chunks: &[[char; 1]] = |
1263 | /// // SAFETY: 1-element chunks never have remainder |
1264 | /// unsafe { slice.as_chunks_unchecked() }; |
1265 | /// assert_eq!(chunks, &[['l' ], ['o' ], ['r' ], ['e' ], ['m' ], ['!' ]]); |
1266 | /// let chunks: &[[char; 3]] = |
1267 | /// // SAFETY: The slice length (6) is a multiple of 3 |
1268 | /// unsafe { slice.as_chunks_unchecked() }; |
1269 | /// assert_eq!(chunks, &[['l' , 'o' , 'r' ], ['e' , 'm' , '!' ]]); |
1270 | /// |
1271 | /// // These would be unsound: |
1272 | /// // let chunks: &[[_; 5]] = slice.as_chunks_unchecked() // The slice length is not a multiple of 5 |
1273 | /// // let chunks: &[[_; 0]] = slice.as_chunks_unchecked() // Zero-length chunks are never allowed |
1274 | /// ``` |
1275 | #[unstable (feature = "slice_as_chunks" , issue = "74985" )] |
1276 | #[inline ] |
1277 | #[must_use ] |
1278 | pub const unsafe fn as_chunks_unchecked<const N: usize>(&self) -> &[[T; N]] { |
1279 | debug_assert_nounwind!( |
1280 | N != 0 && self.len() % N == 0, |
1281 | "slice::as_chunks_unchecked requires `N != 0` and the slice to split exactly into `N`-element chunks" , |
1282 | ); |
1283 | // SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length |
1284 | let new_len = unsafe { exact_div(self.len(), N) }; |
1285 | // SAFETY: We cast a slice of `new_len * N` elements into |
1286 | // a slice of `new_len` many `N` elements chunks. |
1287 | unsafe { from_raw_parts(self.as_ptr().cast(), new_len) } |
1288 | } |
1289 | |
1290 | /// Splits the slice into a slice of `N`-element arrays, |
1291 | /// starting at the beginning of the slice, |
1292 | /// and a remainder slice with length strictly less than `N`. |
1293 | /// |
1294 | /// # Panics |
1295 | /// |
1296 | /// Panics if `N` is 0. This check will most probably get changed to a compile time |
1297 | /// error before this method gets stabilized. |
1298 | /// |
1299 | /// # Examples |
1300 | /// |
1301 | /// ``` |
1302 | /// #![feature(slice_as_chunks)] |
1303 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1304 | /// let (chunks, remainder) = slice.as_chunks(); |
1305 | /// assert_eq!(chunks, &[['l' , 'o' ], ['r' , 'e' ]]); |
1306 | /// assert_eq!(remainder, &['m' ]); |
1307 | /// ``` |
1308 | /// |
1309 | /// If you expect the slice to be an exact multiple, you can combine |
1310 | /// `let`-`else` with an empty slice pattern: |
1311 | /// ``` |
1312 | /// #![feature(slice_as_chunks)] |
1313 | /// let slice = ['R' , 'u' , 's' , 't' ]; |
1314 | /// let (chunks, []) = slice.as_chunks::<2>() else { |
1315 | /// panic!("slice didn't have even length" ) |
1316 | /// }; |
1317 | /// assert_eq!(chunks, &[['R' , 'u' ], ['s' , 't' ]]); |
1318 | /// ``` |
1319 | #[unstable (feature = "slice_as_chunks" , issue = "74985" )] |
1320 | #[inline ] |
1321 | #[track_caller ] |
1322 | #[must_use ] |
1323 | pub const fn as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]) { |
1324 | assert!(N != 0, "chunk size must be non-zero" ); |
1325 | let len = self.len() / N; |
1326 | let (multiple_of_n, remainder) = self.split_at(len * N); |
1327 | // SAFETY: We already panicked for zero, and ensured by construction |
1328 | // that the length of the subslice is a multiple of N. |
1329 | let array_slice = unsafe { multiple_of_n.as_chunks_unchecked() }; |
1330 | (array_slice, remainder) |
1331 | } |
1332 | |
1333 | /// Splits the slice into a slice of `N`-element arrays, |
1334 | /// starting at the end of the slice, |
1335 | /// and a remainder slice with length strictly less than `N`. |
1336 | /// |
1337 | /// # Panics |
1338 | /// |
1339 | /// Panics if `N` is 0. This check will most probably get changed to a compile time |
1340 | /// error before this method gets stabilized. |
1341 | /// |
1342 | /// # Examples |
1343 | /// |
1344 | /// ``` |
1345 | /// #![feature(slice_as_chunks)] |
1346 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1347 | /// let (remainder, chunks) = slice.as_rchunks(); |
1348 | /// assert_eq!(remainder, &['l' ]); |
1349 | /// assert_eq!(chunks, &[['o' , 'r' ], ['e' , 'm' ]]); |
1350 | /// ``` |
1351 | #[unstable (feature = "slice_as_chunks" , issue = "74985" )] |
1352 | #[inline ] |
1353 | #[track_caller ] |
1354 | #[must_use ] |
1355 | pub const fn as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]]) { |
1356 | assert!(N != 0, "chunk size must be non-zero" ); |
1357 | let len = self.len() / N; |
1358 | let (remainder, multiple_of_n) = self.split_at(self.len() - len * N); |
1359 | // SAFETY: We already panicked for zero, and ensured by construction |
1360 | // that the length of the subslice is a multiple of N. |
1361 | let array_slice = unsafe { multiple_of_n.as_chunks_unchecked() }; |
1362 | (remainder, array_slice) |
1363 | } |
1364 | |
1365 | /// Returns an iterator over `N` elements of the slice at a time, starting at the |
1366 | /// beginning of the slice. |
1367 | /// |
1368 | /// The chunks are array references and do not overlap. If `N` does not divide the |
1369 | /// length of the slice, then the last up to `N-1` elements will be omitted and can be |
1370 | /// retrieved from the `remainder` function of the iterator. |
1371 | /// |
1372 | /// This method is the const generic equivalent of [`chunks_exact`]. |
1373 | /// |
1374 | /// # Panics |
1375 | /// |
1376 | /// Panics if `N` is 0. This check will most probably get changed to a compile time |
1377 | /// error before this method gets stabilized. |
1378 | /// |
1379 | /// # Examples |
1380 | /// |
1381 | /// ``` |
1382 | /// #![feature(array_chunks)] |
1383 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1384 | /// let mut iter = slice.array_chunks(); |
1385 | /// assert_eq!(iter.next().unwrap(), &['l' , 'o' ]); |
1386 | /// assert_eq!(iter.next().unwrap(), &['r' , 'e' ]); |
1387 | /// assert!(iter.next().is_none()); |
1388 | /// assert_eq!(iter.remainder(), &['m' ]); |
1389 | /// ``` |
1390 | /// |
1391 | /// [`chunks_exact`]: slice::chunks_exact |
1392 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
1393 | #[inline ] |
1394 | #[track_caller ] |
1395 | pub fn array_chunks<const N: usize>(&self) -> ArrayChunks<'_, T, N> { |
1396 | assert!(N != 0, "chunk size must be non-zero" ); |
1397 | ArrayChunks::new(self) |
1398 | } |
1399 | |
1400 | /// Splits the slice into a slice of `N`-element arrays, |
1401 | /// assuming that there's no remainder. |
1402 | /// |
1403 | /// # Safety |
1404 | /// |
1405 | /// This may only be called when |
1406 | /// - The slice splits exactly into `N`-element chunks (aka `self.len() % N == 0`). |
1407 | /// - `N != 0`. |
1408 | /// |
1409 | /// # Examples |
1410 | /// |
1411 | /// ``` |
1412 | /// #![feature(slice_as_chunks)] |
1413 | /// let slice: &mut [char] = &mut ['l' , 'o' , 'r' , 'e' , 'm' , '!' ]; |
1414 | /// let chunks: &mut [[char; 1]] = |
1415 | /// // SAFETY: 1-element chunks never have remainder |
1416 | /// unsafe { slice.as_chunks_unchecked_mut() }; |
1417 | /// chunks[0] = ['L' ]; |
1418 | /// assert_eq!(chunks, &[['L' ], ['o' ], ['r' ], ['e' ], ['m' ], ['!' ]]); |
1419 | /// let chunks: &mut [[char; 3]] = |
1420 | /// // SAFETY: The slice length (6) is a multiple of 3 |
1421 | /// unsafe { slice.as_chunks_unchecked_mut() }; |
1422 | /// chunks[1] = ['a' , 'x' , '?' ]; |
1423 | /// assert_eq!(slice, &['L' , 'o' , 'r' , 'a' , 'x' , '?' ]); |
1424 | /// |
1425 | /// // These would be unsound: |
1426 | /// // let chunks: &[[_; 5]] = slice.as_chunks_unchecked_mut() // The slice length is not a multiple of 5 |
1427 | /// // let chunks: &[[_; 0]] = slice.as_chunks_unchecked_mut() // Zero-length chunks are never allowed |
1428 | /// ``` |
1429 | #[unstable (feature = "slice_as_chunks" , issue = "74985" )] |
1430 | #[inline ] |
1431 | #[must_use ] |
1432 | pub const unsafe fn as_chunks_unchecked_mut<const N: usize>(&mut self) -> &mut [[T; N]] { |
1433 | debug_assert_nounwind!( |
1434 | N != 0 && self.len() % N == 0, |
1435 | "slice::as_chunks_unchecked requires `N != 0` and the slice to split exactly into `N`-element chunks" , |
1436 | ); |
1437 | // SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length |
1438 | let new_len = unsafe { exact_div(self.len(), N) }; |
1439 | // SAFETY: We cast a slice of `new_len * N` elements into |
1440 | // a slice of `new_len` many `N` elements chunks. |
1441 | unsafe { from_raw_parts_mut(self.as_mut_ptr().cast(), new_len) } |
1442 | } |
1443 | |
1444 | /// Splits the slice into a slice of `N`-element arrays, |
1445 | /// starting at the beginning of the slice, |
1446 | /// and a remainder slice with length strictly less than `N`. |
1447 | /// |
1448 | /// # Panics |
1449 | /// |
1450 | /// Panics if `N` is 0. This check will most probably get changed to a compile time |
1451 | /// error before this method gets stabilized. |
1452 | /// |
1453 | /// # Examples |
1454 | /// |
1455 | /// ``` |
1456 | /// #![feature(slice_as_chunks)] |
1457 | /// let v = &mut [0, 0, 0, 0, 0]; |
1458 | /// let mut count = 1; |
1459 | /// |
1460 | /// let (chunks, remainder) = v.as_chunks_mut(); |
1461 | /// remainder[0] = 9; |
1462 | /// for chunk in chunks { |
1463 | /// *chunk = [count; 2]; |
1464 | /// count += 1; |
1465 | /// } |
1466 | /// assert_eq!(v, &[1, 1, 2, 2, 9]); |
1467 | /// ``` |
1468 | #[unstable (feature = "slice_as_chunks" , issue = "74985" )] |
1469 | #[inline ] |
1470 | #[track_caller ] |
1471 | #[must_use ] |
1472 | pub const fn as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]) { |
1473 | assert!(N != 0, "chunk size must be non-zero" ); |
1474 | let len = self.len() / N; |
1475 | let (multiple_of_n, remainder) = self.split_at_mut(len * N); |
1476 | // SAFETY: We already panicked for zero, and ensured by construction |
1477 | // that the length of the subslice is a multiple of N. |
1478 | let array_slice = unsafe { multiple_of_n.as_chunks_unchecked_mut() }; |
1479 | (array_slice, remainder) |
1480 | } |
1481 | |
1482 | /// Splits the slice into a slice of `N`-element arrays, |
1483 | /// starting at the end of the slice, |
1484 | /// and a remainder slice with length strictly less than `N`. |
1485 | /// |
1486 | /// # Panics |
1487 | /// |
1488 | /// Panics if `N` is 0. This check will most probably get changed to a compile time |
1489 | /// error before this method gets stabilized. |
1490 | /// |
1491 | /// # Examples |
1492 | /// |
1493 | /// ``` |
1494 | /// #![feature(slice_as_chunks)] |
1495 | /// let v = &mut [0, 0, 0, 0, 0]; |
1496 | /// let mut count = 1; |
1497 | /// |
1498 | /// let (remainder, chunks) = v.as_rchunks_mut(); |
1499 | /// remainder[0] = 9; |
1500 | /// for chunk in chunks { |
1501 | /// *chunk = [count; 2]; |
1502 | /// count += 1; |
1503 | /// } |
1504 | /// assert_eq!(v, &[9, 1, 1, 2, 2]); |
1505 | /// ``` |
1506 | #[unstable (feature = "slice_as_chunks" , issue = "74985" )] |
1507 | #[inline ] |
1508 | #[track_caller ] |
1509 | #[must_use ] |
1510 | pub const fn as_rchunks_mut<const N: usize>(&mut self) -> (&mut [T], &mut [[T; N]]) { |
1511 | assert!(N != 0, "chunk size must be non-zero" ); |
1512 | let len = self.len() / N; |
1513 | let (remainder, multiple_of_n) = self.split_at_mut(self.len() - len * N); |
1514 | // SAFETY: We already panicked for zero, and ensured by construction |
1515 | // that the length of the subslice is a multiple of N. |
1516 | let array_slice = unsafe { multiple_of_n.as_chunks_unchecked_mut() }; |
1517 | (remainder, array_slice) |
1518 | } |
1519 | |
1520 | /// Returns an iterator over `N` elements of the slice at a time, starting at the |
1521 | /// beginning of the slice. |
1522 | /// |
1523 | /// The chunks are mutable array references and do not overlap. If `N` does not divide |
1524 | /// the length of the slice, then the last up to `N-1` elements will be omitted and |
1525 | /// can be retrieved from the `into_remainder` function of the iterator. |
1526 | /// |
1527 | /// This method is the const generic equivalent of [`chunks_exact_mut`]. |
1528 | /// |
1529 | /// # Panics |
1530 | /// |
1531 | /// Panics if `N` is 0. This check will most probably get changed to a compile time |
1532 | /// error before this method gets stabilized. |
1533 | /// |
1534 | /// # Examples |
1535 | /// |
1536 | /// ``` |
1537 | /// #![feature(array_chunks)] |
1538 | /// let v = &mut [0, 0, 0, 0, 0]; |
1539 | /// let mut count = 1; |
1540 | /// |
1541 | /// for chunk in v.array_chunks_mut() { |
1542 | /// *chunk = [count; 2]; |
1543 | /// count += 1; |
1544 | /// } |
1545 | /// assert_eq!(v, &[1, 1, 2, 2, 0]); |
1546 | /// ``` |
1547 | /// |
1548 | /// [`chunks_exact_mut`]: slice::chunks_exact_mut |
1549 | #[unstable (feature = "array_chunks" , issue = "74985" )] |
1550 | #[inline ] |
1551 | #[track_caller ] |
1552 | pub fn array_chunks_mut<const N: usize>(&mut self) -> ArrayChunksMut<'_, T, N> { |
1553 | assert!(N != 0, "chunk size must be non-zero" ); |
1554 | ArrayChunksMut::new(self) |
1555 | } |
1556 | |
1557 | /// Returns an iterator over overlapping windows of `N` elements of a slice, |
1558 | /// starting at the beginning of the slice. |
1559 | /// |
1560 | /// This is the const generic equivalent of [`windows`]. |
1561 | /// |
1562 | /// If `N` is greater than the size of the slice, it will return no windows. |
1563 | /// |
1564 | /// # Panics |
1565 | /// |
1566 | /// Panics if `N` is 0. This check will most probably get changed to a compile time |
1567 | /// error before this method gets stabilized. |
1568 | /// |
1569 | /// # Examples |
1570 | /// |
1571 | /// ``` |
1572 | /// #![feature(array_windows)] |
1573 | /// let slice = [0, 1, 2, 3]; |
1574 | /// let mut iter = slice.array_windows(); |
1575 | /// assert_eq!(iter.next().unwrap(), &[0, 1]); |
1576 | /// assert_eq!(iter.next().unwrap(), &[1, 2]); |
1577 | /// assert_eq!(iter.next().unwrap(), &[2, 3]); |
1578 | /// assert!(iter.next().is_none()); |
1579 | /// ``` |
1580 | /// |
1581 | /// [`windows`]: slice::windows |
1582 | #[unstable (feature = "array_windows" , issue = "75027" )] |
1583 | #[inline ] |
1584 | #[track_caller ] |
1585 | pub fn array_windows<const N: usize>(&self) -> ArrayWindows<'_, T, N> { |
1586 | assert!(N != 0, "window size must be non-zero" ); |
1587 | ArrayWindows::new(self) |
1588 | } |
1589 | |
1590 | /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end |
1591 | /// of the slice. |
1592 | /// |
1593 | /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the |
1594 | /// slice, then the last chunk will not have length `chunk_size`. |
1595 | /// |
1596 | /// See [`rchunks_exact`] for a variant of this iterator that returns chunks of always exactly |
1597 | /// `chunk_size` elements, and [`chunks`] for the same iterator but starting at the beginning |
1598 | /// of the slice. |
1599 | /// |
1600 | /// # Panics |
1601 | /// |
1602 | /// Panics if `chunk_size` is 0. |
1603 | /// |
1604 | /// # Examples |
1605 | /// |
1606 | /// ``` |
1607 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1608 | /// let mut iter = slice.rchunks(2); |
1609 | /// assert_eq!(iter.next().unwrap(), &['e' , 'm' ]); |
1610 | /// assert_eq!(iter.next().unwrap(), &['o' , 'r' ]); |
1611 | /// assert_eq!(iter.next().unwrap(), &['l' ]); |
1612 | /// assert!(iter.next().is_none()); |
1613 | /// ``` |
1614 | /// |
1615 | /// [`rchunks_exact`]: slice::rchunks_exact |
1616 | /// [`chunks`]: slice::chunks |
1617 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
1618 | #[inline ] |
1619 | #[track_caller ] |
1620 | pub fn rchunks(&self, chunk_size: usize) -> RChunks<'_, T> { |
1621 | assert!(chunk_size != 0, "chunk size must be non-zero" ); |
1622 | RChunks::new(self, chunk_size) |
1623 | } |
1624 | |
1625 | /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end |
1626 | /// of the slice. |
1627 | /// |
1628 | /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the |
1629 | /// length of the slice, then the last chunk will not have length `chunk_size`. |
1630 | /// |
1631 | /// See [`rchunks_exact_mut`] for a variant of this iterator that returns chunks of always |
1632 | /// exactly `chunk_size` elements, and [`chunks_mut`] for the same iterator but starting at the |
1633 | /// beginning of the slice. |
1634 | /// |
1635 | /// # Panics |
1636 | /// |
1637 | /// Panics if `chunk_size` is 0. |
1638 | /// |
1639 | /// # Examples |
1640 | /// |
1641 | /// ``` |
1642 | /// let v = &mut [0, 0, 0, 0, 0]; |
1643 | /// let mut count = 1; |
1644 | /// |
1645 | /// for chunk in v.rchunks_mut(2) { |
1646 | /// for elem in chunk.iter_mut() { |
1647 | /// *elem += count; |
1648 | /// } |
1649 | /// count += 1; |
1650 | /// } |
1651 | /// assert_eq!(v, &[3, 2, 2, 1, 1]); |
1652 | /// ``` |
1653 | /// |
1654 | /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut |
1655 | /// [`chunks_mut`]: slice::chunks_mut |
1656 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
1657 | #[inline ] |
1658 | #[track_caller ] |
1659 | pub fn rchunks_mut(&mut self, chunk_size: usize) -> RChunksMut<'_, T> { |
1660 | assert!(chunk_size != 0, "chunk size must be non-zero" ); |
1661 | RChunksMut::new(self, chunk_size) |
1662 | } |
1663 | |
1664 | /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the |
1665 | /// end of the slice. |
1666 | /// |
1667 | /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the |
1668 | /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved |
1669 | /// from the `remainder` function of the iterator. |
1670 | /// |
1671 | /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the |
1672 | /// resulting code better than in the case of [`rchunks`]. |
1673 | /// |
1674 | /// See [`rchunks`] for a variant of this iterator that also returns the remainder as a smaller |
1675 | /// chunk, and [`chunks_exact`] for the same iterator but starting at the beginning of the |
1676 | /// slice. |
1677 | /// |
1678 | /// # Panics |
1679 | /// |
1680 | /// Panics if `chunk_size` is 0. |
1681 | /// |
1682 | /// # Examples |
1683 | /// |
1684 | /// ``` |
1685 | /// let slice = ['l' , 'o' , 'r' , 'e' , 'm' ]; |
1686 | /// let mut iter = slice.rchunks_exact(2); |
1687 | /// assert_eq!(iter.next().unwrap(), &['e' , 'm' ]); |
1688 | /// assert_eq!(iter.next().unwrap(), &['o' , 'r' ]); |
1689 | /// assert!(iter.next().is_none()); |
1690 | /// assert_eq!(iter.remainder(), &['l' ]); |
1691 | /// ``` |
1692 | /// |
1693 | /// [`chunks`]: slice::chunks |
1694 | /// [`rchunks`]: slice::rchunks |
1695 | /// [`chunks_exact`]: slice::chunks_exact |
1696 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
1697 | #[inline ] |
1698 | #[track_caller ] |
1699 | pub fn rchunks_exact(&self, chunk_size: usize) -> RChunksExact<'_, T> { |
1700 | assert!(chunk_size != 0, "chunk size must be non-zero" ); |
1701 | RChunksExact::new(self, chunk_size) |
1702 | } |
1703 | |
1704 | /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end |
1705 | /// of the slice. |
1706 | /// |
1707 | /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the |
1708 | /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be |
1709 | /// retrieved from the `into_remainder` function of the iterator. |
1710 | /// |
1711 | /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the |
1712 | /// resulting code better than in the case of [`chunks_mut`]. |
1713 | /// |
1714 | /// See [`rchunks_mut`] for a variant of this iterator that also returns the remainder as a |
1715 | /// smaller chunk, and [`chunks_exact_mut`] for the same iterator but starting at the beginning |
1716 | /// of the slice. |
1717 | /// |
1718 | /// # Panics |
1719 | /// |
1720 | /// Panics if `chunk_size` is 0. |
1721 | /// |
1722 | /// # Examples |
1723 | /// |
1724 | /// ``` |
1725 | /// let v = &mut [0, 0, 0, 0, 0]; |
1726 | /// let mut count = 1; |
1727 | /// |
1728 | /// for chunk in v.rchunks_exact_mut(2) { |
1729 | /// for elem in chunk.iter_mut() { |
1730 | /// *elem += count; |
1731 | /// } |
1732 | /// count += 1; |
1733 | /// } |
1734 | /// assert_eq!(v, &[0, 2, 2, 1, 1]); |
1735 | /// ``` |
1736 | /// |
1737 | /// [`chunks_mut`]: slice::chunks_mut |
1738 | /// [`rchunks_mut`]: slice::rchunks_mut |
1739 | /// [`chunks_exact_mut`]: slice::chunks_exact_mut |
1740 | #[stable (feature = "rchunks" , since = "1.31.0" )] |
1741 | #[inline ] |
1742 | #[track_caller ] |
1743 | pub fn rchunks_exact_mut(&mut self, chunk_size: usize) -> RChunksExactMut<'_, T> { |
1744 | assert!(chunk_size != 0, "chunk size must be non-zero" ); |
1745 | RChunksExactMut::new(self, chunk_size) |
1746 | } |
1747 | |
1748 | /// Returns an iterator over the slice producing non-overlapping runs |
1749 | /// of elements using the predicate to separate them. |
1750 | /// |
1751 | /// The predicate is called for every pair of consecutive elements, |
1752 | /// meaning that it is called on `slice[0]` and `slice[1]`, |
1753 | /// followed by `slice[1]` and `slice[2]`, and so on. |
1754 | /// |
1755 | /// # Examples |
1756 | /// |
1757 | /// ``` |
1758 | /// let slice = &[1, 1, 1, 3, 3, 2, 2, 2]; |
1759 | /// |
1760 | /// let mut iter = slice.chunk_by(|a, b| a == b); |
1761 | /// |
1762 | /// assert_eq!(iter.next(), Some(&[1, 1, 1][..])); |
1763 | /// assert_eq!(iter.next(), Some(&[3, 3][..])); |
1764 | /// assert_eq!(iter.next(), Some(&[2, 2, 2][..])); |
1765 | /// assert_eq!(iter.next(), None); |
1766 | /// ``` |
1767 | /// |
1768 | /// This method can be used to extract the sorted subslices: |
1769 | /// |
1770 | /// ``` |
1771 | /// let slice = &[1, 1, 2, 3, 2, 3, 2, 3, 4]; |
1772 | /// |
1773 | /// let mut iter = slice.chunk_by(|a, b| a <= b); |
1774 | /// |
1775 | /// assert_eq!(iter.next(), Some(&[1, 1, 2, 3][..])); |
1776 | /// assert_eq!(iter.next(), Some(&[2, 3][..])); |
1777 | /// assert_eq!(iter.next(), Some(&[2, 3, 4][..])); |
1778 | /// assert_eq!(iter.next(), None); |
1779 | /// ``` |
1780 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
1781 | #[inline ] |
1782 | pub fn chunk_by<F>(&self, pred: F) -> ChunkBy<'_, T, F> |
1783 | where |
1784 | F: FnMut(&T, &T) -> bool, |
1785 | { |
1786 | ChunkBy::new(self, pred) |
1787 | } |
1788 | |
1789 | /// Returns an iterator over the slice producing non-overlapping mutable |
1790 | /// runs of elements using the predicate to separate them. |
1791 | /// |
1792 | /// The predicate is called for every pair of consecutive elements, |
1793 | /// meaning that it is called on `slice[0]` and `slice[1]`, |
1794 | /// followed by `slice[1]` and `slice[2]`, and so on. |
1795 | /// |
1796 | /// # Examples |
1797 | /// |
1798 | /// ``` |
1799 | /// let slice = &mut [1, 1, 1, 3, 3, 2, 2, 2]; |
1800 | /// |
1801 | /// let mut iter = slice.chunk_by_mut(|a, b| a == b); |
1802 | /// |
1803 | /// assert_eq!(iter.next(), Some(&mut [1, 1, 1][..])); |
1804 | /// assert_eq!(iter.next(), Some(&mut [3, 3][..])); |
1805 | /// assert_eq!(iter.next(), Some(&mut [2, 2, 2][..])); |
1806 | /// assert_eq!(iter.next(), None); |
1807 | /// ``` |
1808 | /// |
1809 | /// This method can be used to extract the sorted subslices: |
1810 | /// |
1811 | /// ``` |
1812 | /// let slice = &mut [1, 1, 2, 3, 2, 3, 2, 3, 4]; |
1813 | /// |
1814 | /// let mut iter = slice.chunk_by_mut(|a, b| a <= b); |
1815 | /// |
1816 | /// assert_eq!(iter.next(), Some(&mut [1, 1, 2, 3][..])); |
1817 | /// assert_eq!(iter.next(), Some(&mut [2, 3][..])); |
1818 | /// assert_eq!(iter.next(), Some(&mut [2, 3, 4][..])); |
1819 | /// assert_eq!(iter.next(), None); |
1820 | /// ``` |
1821 | #[stable (feature = "slice_group_by" , since = "1.77.0" )] |
1822 | #[inline ] |
1823 | pub fn chunk_by_mut<F>(&mut self, pred: F) -> ChunkByMut<'_, T, F> |
1824 | where |
1825 | F: FnMut(&T, &T) -> bool, |
1826 | { |
1827 | ChunkByMut::new(self, pred) |
1828 | } |
1829 | |
1830 | /// Divides one slice into two at an index. |
1831 | /// |
1832 | /// The first will contain all indices from `[0, mid)` (excluding |
1833 | /// the index `mid` itself) and the second will contain all |
1834 | /// indices from `[mid, len)` (excluding the index `len` itself). |
1835 | /// |
1836 | /// # Panics |
1837 | /// |
1838 | /// Panics if `mid > len`. For a non-panicking alternative see |
1839 | /// [`split_at_checked`](slice::split_at_checked). |
1840 | /// |
1841 | /// # Examples |
1842 | /// |
1843 | /// ``` |
1844 | /// let v = [1, 2, 3, 4, 5, 6]; |
1845 | /// |
1846 | /// { |
1847 | /// let (left, right) = v.split_at(0); |
1848 | /// assert_eq!(left, []); |
1849 | /// assert_eq!(right, [1, 2, 3, 4, 5, 6]); |
1850 | /// } |
1851 | /// |
1852 | /// { |
1853 | /// let (left, right) = v.split_at(2); |
1854 | /// assert_eq!(left, [1, 2]); |
1855 | /// assert_eq!(right, [3, 4, 5, 6]); |
1856 | /// } |
1857 | /// |
1858 | /// { |
1859 | /// let (left, right) = v.split_at(6); |
1860 | /// assert_eq!(left, [1, 2, 3, 4, 5, 6]); |
1861 | /// assert_eq!(right, []); |
1862 | /// } |
1863 | /// ``` |
1864 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1865 | #[rustc_const_stable (feature = "const_slice_split_at_not_mut" , since = "1.71.0" )] |
1866 | #[rustc_allow_const_fn_unstable (split_at_checked)] |
1867 | #[inline ] |
1868 | #[track_caller ] |
1869 | #[must_use ] |
1870 | pub const fn split_at(&self, mid: usize) -> (&[T], &[T]) { |
1871 | match self.split_at_checked(mid) { |
1872 | Some(pair) => pair, |
1873 | None => panic!("mid > len" ), |
1874 | } |
1875 | } |
1876 | |
1877 | /// Divides one mutable slice into two at an index. |
1878 | /// |
1879 | /// The first will contain all indices from `[0, mid)` (excluding |
1880 | /// the index `mid` itself) and the second will contain all |
1881 | /// indices from `[mid, len)` (excluding the index `len` itself). |
1882 | /// |
1883 | /// # Panics |
1884 | /// |
1885 | /// Panics if `mid > len`. For a non-panicking alternative see |
1886 | /// [`split_at_mut_checked`](slice::split_at_mut_checked). |
1887 | /// |
1888 | /// # Examples |
1889 | /// |
1890 | /// ``` |
1891 | /// let mut v = [1, 0, 3, 0, 5, 6]; |
1892 | /// let (left, right) = v.split_at_mut(2); |
1893 | /// assert_eq!(left, [1, 0]); |
1894 | /// assert_eq!(right, [3, 0, 5, 6]); |
1895 | /// left[1] = 2; |
1896 | /// right[1] = 4; |
1897 | /// assert_eq!(v, [1, 2, 3, 4, 5, 6]); |
1898 | /// ``` |
1899 | #[stable (feature = "rust1" , since = "1.0.0" )] |
1900 | #[inline ] |
1901 | #[track_caller ] |
1902 | #[must_use ] |
1903 | #[rustc_const_unstable (feature = "const_slice_split_at_mut" , issue = "101804" )] |
1904 | pub const fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) { |
1905 | match self.split_at_mut_checked(mid) { |
1906 | Some(pair) => pair, |
1907 | None => panic!("mid > len" ), |
1908 | } |
1909 | } |
1910 | |
1911 | /// Divides one slice into two at an index, without doing bounds checking. |
1912 | /// |
1913 | /// The first will contain all indices from `[0, mid)` (excluding |
1914 | /// the index `mid` itself) and the second will contain all |
1915 | /// indices from `[mid, len)` (excluding the index `len` itself). |
1916 | /// |
1917 | /// For a safe alternative see [`split_at`]. |
1918 | /// |
1919 | /// # Safety |
1920 | /// |
1921 | /// Calling this method with an out-of-bounds index is *[undefined behavior]* |
1922 | /// even if the resulting reference is not used. The caller has to ensure that |
1923 | /// `0 <= mid <= self.len()`. |
1924 | /// |
1925 | /// [`split_at`]: slice::split_at |
1926 | /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html |
1927 | /// |
1928 | /// # Examples |
1929 | /// |
1930 | /// ``` |
1931 | /// #![feature(slice_split_at_unchecked)] |
1932 | /// |
1933 | /// let v = [1, 2, 3, 4, 5, 6]; |
1934 | /// |
1935 | /// unsafe { |
1936 | /// let (left, right) = v.split_at_unchecked(0); |
1937 | /// assert_eq!(left, []); |
1938 | /// assert_eq!(right, [1, 2, 3, 4, 5, 6]); |
1939 | /// } |
1940 | /// |
1941 | /// unsafe { |
1942 | /// let (left, right) = v.split_at_unchecked(2); |
1943 | /// assert_eq!(left, [1, 2]); |
1944 | /// assert_eq!(right, [3, 4, 5, 6]); |
1945 | /// } |
1946 | /// |
1947 | /// unsafe { |
1948 | /// let (left, right) = v.split_at_unchecked(6); |
1949 | /// assert_eq!(left, [1, 2, 3, 4, 5, 6]); |
1950 | /// assert_eq!(right, []); |
1951 | /// } |
1952 | /// ``` |
1953 | #[unstable (feature = "slice_split_at_unchecked" , reason = "new API" , issue = "76014" )] |
1954 | #[rustc_const_stable ( |
1955 | feature = "const_slice_split_at_unchecked" , |
1956 | since = "1.77.0" |
1957 | )] |
1958 | #[inline ] |
1959 | #[must_use ] |
1960 | pub const unsafe fn split_at_unchecked(&self, mid: usize) -> (&[T], &[T]) { |
1961 | // HACK: the const function `from_raw_parts` is used to make this |
1962 | // function const; previously the implementation used |
1963 | // `(self.get_unchecked(..mid), self.get_unchecked(mid..))` |
1964 | |
1965 | let len = self.len(); |
1966 | let ptr = self.as_ptr(); |
1967 | |
1968 | debug_assert_nounwind!( |
1969 | mid <= len, |
1970 | "slice::split_at_unchecked requires the index to be within the slice" , |
1971 | ); |
1972 | |
1973 | // SAFETY: Caller has to check that `0 <= mid <= self.len()` |
1974 | unsafe { (from_raw_parts(ptr, mid), from_raw_parts(ptr.add(mid), len - mid)) } |
1975 | } |
1976 | |
1977 | /// Divides one mutable slice into two at an index, without doing bounds checking. |
1978 | /// |
1979 | /// The first will contain all indices from `[0, mid)` (excluding |
1980 | /// the index `mid` itself) and the second will contain all |
1981 | /// indices from `[mid, len)` (excluding the index `len` itself). |
1982 | /// |
1983 | /// For a safe alternative see [`split_at_mut`]. |
1984 | /// |
1985 | /// # Safety |
1986 | /// |
1987 | /// Calling this method with an out-of-bounds index is *[undefined behavior]* |
1988 | /// even if the resulting reference is not used. The caller has to ensure that |
1989 | /// `0 <= mid <= self.len()`. |
1990 | /// |
1991 | /// [`split_at_mut`]: slice::split_at_mut |
1992 | /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html |
1993 | /// |
1994 | /// # Examples |
1995 | /// |
1996 | /// ``` |
1997 | /// #![feature(slice_split_at_unchecked)] |
1998 | /// |
1999 | /// let mut v = [1, 0, 3, 0, 5, 6]; |
2000 | /// // scoped to restrict the lifetime of the borrows |
2001 | /// unsafe { |
2002 | /// let (left, right) = v.split_at_mut_unchecked(2); |
2003 | /// assert_eq!(left, [1, 0]); |
2004 | /// assert_eq!(right, [3, 0, 5, 6]); |
2005 | /// left[1] = 2; |
2006 | /// right[1] = 4; |
2007 | /// } |
2008 | /// assert_eq!(v, [1, 2, 3, 4, 5, 6]); |
2009 | /// ``` |
2010 | #[unstable (feature = "slice_split_at_unchecked" , reason = "new API" , issue = "76014" )] |
2011 | #[rustc_const_unstable (feature = "const_slice_split_at_mut" , issue = "101804" )] |
2012 | #[inline ] |
2013 | #[must_use ] |
2014 | pub const unsafe fn split_at_mut_unchecked(&mut self, mid: usize) -> (&mut [T], &mut [T]) { |
2015 | let len = self.len(); |
2016 | let ptr = self.as_mut_ptr(); |
2017 | |
2018 | debug_assert_nounwind!( |
2019 | mid <= len, |
2020 | "slice::split_at_mut_unchecked requires the index to be within the slice" , |
2021 | ); |
2022 | |
2023 | // SAFETY: Caller has to check that `0 <= mid <= self.len()`. |
2024 | // |
2025 | // `[ptr; mid]` and `[mid; len]` are not overlapping, so returning a mutable reference |
2026 | // is fine. |
2027 | unsafe { (from_raw_parts_mut(ptr, mid), from_raw_parts_mut(ptr.add(mid), len - mid)) } |
2028 | } |
2029 | |
2030 | /// Divides one slice into two at an index, returning `None` if the slice is |
2031 | /// too short. |
2032 | /// |
2033 | /// If `mid ≤ len` returns a pair of slices where the first will contain all |
2034 | /// indices from `[0, mid)` (excluding the index `mid` itself) and the |
2035 | /// second will contain all indices from `[mid, len)` (excluding the index |
2036 | /// `len` itself). |
2037 | /// |
2038 | /// Otherwise, if `mid > len`, returns `None`. |
2039 | /// |
2040 | /// # Examples |
2041 | /// |
2042 | /// ``` |
2043 | /// #![feature(split_at_checked)] |
2044 | /// |
2045 | /// let v = [1, -2, 3, -4, 5, -6]; |
2046 | /// |
2047 | /// { |
2048 | /// let (left, right) = v.split_at_checked(0).unwrap(); |
2049 | /// assert_eq!(left, []); |
2050 | /// assert_eq!(right, [1, -2, 3, -4, 5, -6]); |
2051 | /// } |
2052 | /// |
2053 | /// { |
2054 | /// let (left, right) = v.split_at_checked(2).unwrap(); |
2055 | /// assert_eq!(left, [1, -2]); |
2056 | /// assert_eq!(right, [3, -4, 5, -6]); |
2057 | /// } |
2058 | /// |
2059 | /// { |
2060 | /// let (left, right) = v.split_at_checked(6).unwrap(); |
2061 | /// assert_eq!(left, [1, -2, 3, -4, 5, -6]); |
2062 | /// assert_eq!(right, []); |
2063 | /// } |
2064 | /// |
2065 | /// assert_eq!(None, v.split_at_checked(7)); |
2066 | /// ``` |
2067 | #[unstable (feature = "split_at_checked" , reason = "new API" , issue = "119128" )] |
2068 | #[rustc_const_unstable (feature = "split_at_checked" , issue = "119128" )] |
2069 | #[inline ] |
2070 | #[must_use ] |
2071 | pub const fn split_at_checked(&self, mid: usize) -> Option<(&[T], &[T])> { |
2072 | if mid <= self.len() { |
2073 | // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which |
2074 | // fulfills the requirements of `split_at_unchecked`. |
2075 | Some(unsafe { self.split_at_unchecked(mid) }) |
2076 | } else { |
2077 | None |
2078 | } |
2079 | } |
2080 | |
2081 | /// Divides one mutable slice into two at an index, returning `None` if the |
2082 | /// slice is too short. |
2083 | /// |
2084 | /// If `mid ≤ len` returns a pair of slices where the first will contain all |
2085 | /// indices from `[0, mid)` (excluding the index `mid` itself) and the |
2086 | /// second will contain all indices from `[mid, len)` (excluding the index |
2087 | /// `len` itself). |
2088 | /// |
2089 | /// Otherwise, if `mid > len`, returns `None`. |
2090 | /// |
2091 | /// # Examples |
2092 | /// |
2093 | /// ``` |
2094 | /// #![feature(split_at_checked)] |
2095 | /// |
2096 | /// let mut v = [1, 0, 3, 0, 5, 6]; |
2097 | /// |
2098 | /// if let Some((left, right)) = v.split_at_mut_checked(2) { |
2099 | /// assert_eq!(left, [1, 0]); |
2100 | /// assert_eq!(right, [3, 0, 5, 6]); |
2101 | /// left[1] = 2; |
2102 | /// right[1] = 4; |
2103 | /// } |
2104 | /// assert_eq!(v, [1, 2, 3, 4, 5, 6]); |
2105 | /// |
2106 | /// assert_eq!(None, v.split_at_mut_checked(7)); |
2107 | /// ``` |
2108 | #[unstable (feature = "split_at_checked" , reason = "new API" , issue = "119128" )] |
2109 | #[rustc_const_unstable (feature = "split_at_checked" , issue = "119128" )] |
2110 | #[inline ] |
2111 | #[must_use ] |
2112 | pub const fn split_at_mut_checked(&mut self, mid: usize) -> Option<(&mut [T], &mut [T])> { |
2113 | if mid <= self.len() { |
2114 | // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which |
2115 | // fulfills the requirements of `split_at_unchecked`. |
2116 | Some(unsafe { self.split_at_mut_unchecked(mid) }) |
2117 | } else { |
2118 | None |
2119 | } |
2120 | } |
2121 | |
2122 | /// Returns an iterator over subslices separated by elements that match |
2123 | /// `pred`. The matched element is not contained in the subslices. |
2124 | /// |
2125 | /// # Examples |
2126 | /// |
2127 | /// ``` |
2128 | /// let slice = [10, 40, 33, 20]; |
2129 | /// let mut iter = slice.split(|num| num % 3 == 0); |
2130 | /// |
2131 | /// assert_eq!(iter.next().unwrap(), &[10, 40]); |
2132 | /// assert_eq!(iter.next().unwrap(), &[20]); |
2133 | /// assert!(iter.next().is_none()); |
2134 | /// ``` |
2135 | /// |
2136 | /// If the first element is matched, an empty slice will be the first item |
2137 | /// returned by the iterator. Similarly, if the last element in the slice |
2138 | /// is matched, an empty slice will be the last item returned by the |
2139 | /// iterator: |
2140 | /// |
2141 | /// ``` |
2142 | /// let slice = [10, 40, 33]; |
2143 | /// let mut iter = slice.split(|num| num % 3 == 0); |
2144 | /// |
2145 | /// assert_eq!(iter.next().unwrap(), &[10, 40]); |
2146 | /// assert_eq!(iter.next().unwrap(), &[]); |
2147 | /// assert!(iter.next().is_none()); |
2148 | /// ``` |
2149 | /// |
2150 | /// If two matched elements are directly adjacent, an empty slice will be |
2151 | /// present between them: |
2152 | /// |
2153 | /// ``` |
2154 | /// let slice = [10, 6, 33, 20]; |
2155 | /// let mut iter = slice.split(|num| num % 3 == 0); |
2156 | /// |
2157 | /// assert_eq!(iter.next().unwrap(), &[10]); |
2158 | /// assert_eq!(iter.next().unwrap(), &[]); |
2159 | /// assert_eq!(iter.next().unwrap(), &[20]); |
2160 | /// assert!(iter.next().is_none()); |
2161 | /// ``` |
2162 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2163 | #[inline ] |
2164 | pub fn split<F>(&self, pred: F) -> Split<'_, T, F> |
2165 | where |
2166 | F: FnMut(&T) -> bool, |
2167 | { |
2168 | Split::new(self, pred) |
2169 | } |
2170 | |
2171 | /// Returns an iterator over mutable subslices separated by elements that |
2172 | /// match `pred`. The matched element is not contained in the subslices. |
2173 | /// |
2174 | /// # Examples |
2175 | /// |
2176 | /// ``` |
2177 | /// let mut v = [10, 40, 30, 20, 60, 50]; |
2178 | /// |
2179 | /// for group in v.split_mut(|num| *num % 3 == 0) { |
2180 | /// group[0] = 1; |
2181 | /// } |
2182 | /// assert_eq!(v, [1, 40, 30, 1, 60, 1]); |
2183 | /// ``` |
2184 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2185 | #[inline ] |
2186 | pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<'_, T, F> |
2187 | where |
2188 | F: FnMut(&T) -> bool, |
2189 | { |
2190 | SplitMut::new(self, pred) |
2191 | } |
2192 | |
2193 | /// Returns an iterator over subslices separated by elements that match |
2194 | /// `pred`. The matched element is contained in the end of the previous |
2195 | /// subslice as a terminator. |
2196 | /// |
2197 | /// # Examples |
2198 | /// |
2199 | /// ``` |
2200 | /// let slice = [10, 40, 33, 20]; |
2201 | /// let mut iter = slice.split_inclusive(|num| num % 3 == 0); |
2202 | /// |
2203 | /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]); |
2204 | /// assert_eq!(iter.next().unwrap(), &[20]); |
2205 | /// assert!(iter.next().is_none()); |
2206 | /// ``` |
2207 | /// |
2208 | /// If the last element of the slice is matched, |
2209 | /// that element will be considered the terminator of the preceding slice. |
2210 | /// That slice will be the last item returned by the iterator. |
2211 | /// |
2212 | /// ``` |
2213 | /// let slice = [3, 10, 40, 33]; |
2214 | /// let mut iter = slice.split_inclusive(|num| num % 3 == 0); |
2215 | /// |
2216 | /// assert_eq!(iter.next().unwrap(), &[3]); |
2217 | /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]); |
2218 | /// assert!(iter.next().is_none()); |
2219 | /// ``` |
2220 | #[stable (feature = "split_inclusive" , since = "1.51.0" )] |
2221 | #[inline ] |
2222 | pub fn split_inclusive<F>(&self, pred: F) -> SplitInclusive<'_, T, F> |
2223 | where |
2224 | F: FnMut(&T) -> bool, |
2225 | { |
2226 | SplitInclusive::new(self, pred) |
2227 | } |
2228 | |
2229 | /// Returns an iterator over mutable subslices separated by elements that |
2230 | /// match `pred`. The matched element is contained in the previous |
2231 | /// subslice as a terminator. |
2232 | /// |
2233 | /// # Examples |
2234 | /// |
2235 | /// ``` |
2236 | /// let mut v = [10, 40, 30, 20, 60, 50]; |
2237 | /// |
2238 | /// for group in v.split_inclusive_mut(|num| *num % 3 == 0) { |
2239 | /// let terminator_idx = group.len()-1; |
2240 | /// group[terminator_idx] = 1; |
2241 | /// } |
2242 | /// assert_eq!(v, [10, 40, 1, 20, 1, 1]); |
2243 | /// ``` |
2244 | #[stable (feature = "split_inclusive" , since = "1.51.0" )] |
2245 | #[inline ] |
2246 | pub fn split_inclusive_mut<F>(&mut self, pred: F) -> SplitInclusiveMut<'_, T, F> |
2247 | where |
2248 | F: FnMut(&T) -> bool, |
2249 | { |
2250 | SplitInclusiveMut::new(self, pred) |
2251 | } |
2252 | |
2253 | /// Returns an iterator over subslices separated by elements that match |
2254 | /// `pred`, starting at the end of the slice and working backwards. |
2255 | /// The matched element is not contained in the subslices. |
2256 | /// |
2257 | /// # Examples |
2258 | /// |
2259 | /// ``` |
2260 | /// let slice = [11, 22, 33, 0, 44, 55]; |
2261 | /// let mut iter = slice.rsplit(|num| *num == 0); |
2262 | /// |
2263 | /// assert_eq!(iter.next().unwrap(), &[44, 55]); |
2264 | /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]); |
2265 | /// assert_eq!(iter.next(), None); |
2266 | /// ``` |
2267 | /// |
2268 | /// As with `split()`, if the first or last element is matched, an empty |
2269 | /// slice will be the first (or last) item returned by the iterator. |
2270 | /// |
2271 | /// ``` |
2272 | /// let v = &[0, 1, 1, 2, 3, 5, 8]; |
2273 | /// let mut it = v.rsplit(|n| *n % 2 == 0); |
2274 | /// assert_eq!(it.next().unwrap(), &[]); |
2275 | /// assert_eq!(it.next().unwrap(), &[3, 5]); |
2276 | /// assert_eq!(it.next().unwrap(), &[1, 1]); |
2277 | /// assert_eq!(it.next().unwrap(), &[]); |
2278 | /// assert_eq!(it.next(), None); |
2279 | /// ``` |
2280 | #[stable (feature = "slice_rsplit" , since = "1.27.0" )] |
2281 | #[inline ] |
2282 | pub fn rsplit<F>(&self, pred: F) -> RSplit<'_, T, F> |
2283 | where |
2284 | F: FnMut(&T) -> bool, |
2285 | { |
2286 | RSplit::new(self, pred) |
2287 | } |
2288 | |
2289 | /// Returns an iterator over mutable subslices separated by elements that |
2290 | /// match `pred`, starting at the end of the slice and working |
2291 | /// backwards. The matched element is not contained in the subslices. |
2292 | /// |
2293 | /// # Examples |
2294 | /// |
2295 | /// ``` |
2296 | /// let mut v = [100, 400, 300, 200, 600, 500]; |
2297 | /// |
2298 | /// let mut count = 0; |
2299 | /// for group in v.rsplit_mut(|num| *num % 3 == 0) { |
2300 | /// count += 1; |
2301 | /// group[0] = count; |
2302 | /// } |
2303 | /// assert_eq!(v, [3, 400, 300, 2, 600, 1]); |
2304 | /// ``` |
2305 | /// |
2306 | #[stable (feature = "slice_rsplit" , since = "1.27.0" )] |
2307 | #[inline ] |
2308 | pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<'_, T, F> |
2309 | where |
2310 | F: FnMut(&T) -> bool, |
2311 | { |
2312 | RSplitMut::new(self, pred) |
2313 | } |
2314 | |
2315 | /// Returns an iterator over subslices separated by elements that match |
2316 | /// `pred`, limited to returning at most `n` items. The matched element is |
2317 | /// not contained in the subslices. |
2318 | /// |
2319 | /// The last element returned, if any, will contain the remainder of the |
2320 | /// slice. |
2321 | /// |
2322 | /// # Examples |
2323 | /// |
2324 | /// Print the slice split once by numbers divisible by 3 (i.e., `[10, 40]`, |
2325 | /// `[20, 60, 50]`): |
2326 | /// |
2327 | /// ``` |
2328 | /// let v = [10, 40, 30, 20, 60, 50]; |
2329 | /// |
2330 | /// for group in v.splitn(2, |num| *num % 3 == 0) { |
2331 | /// println!("{group:?}" ); |
2332 | /// } |
2333 | /// ``` |
2334 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2335 | #[inline ] |
2336 | pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<'_, T, F> |
2337 | where |
2338 | F: FnMut(&T) -> bool, |
2339 | { |
2340 | SplitN::new(self.split(pred), n) |
2341 | } |
2342 | |
2343 | /// Returns an iterator over mutable subslices separated by elements that match |
2344 | /// `pred`, limited to returning at most `n` items. The matched element is |
2345 | /// not contained in the subslices. |
2346 | /// |
2347 | /// The last element returned, if any, will contain the remainder of the |
2348 | /// slice. |
2349 | /// |
2350 | /// # Examples |
2351 | /// |
2352 | /// ``` |
2353 | /// let mut v = [10, 40, 30, 20, 60, 50]; |
2354 | /// |
2355 | /// for group in v.splitn_mut(2, |num| *num % 3 == 0) { |
2356 | /// group[0] = 1; |
2357 | /// } |
2358 | /// assert_eq!(v, [1, 40, 30, 1, 60, 50]); |
2359 | /// ``` |
2360 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2361 | #[inline ] |
2362 | pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<'_, T, F> |
2363 | where |
2364 | F: FnMut(&T) -> bool, |
2365 | { |
2366 | SplitNMut::new(self.split_mut(pred), n) |
2367 | } |
2368 | |
2369 | /// Returns an iterator over subslices separated by elements that match |
2370 | /// `pred` limited to returning at most `n` items. This starts at the end of |
2371 | /// the slice and works backwards. The matched element is not contained in |
2372 | /// the subslices. |
2373 | /// |
2374 | /// The last element returned, if any, will contain the remainder of the |
2375 | /// slice. |
2376 | /// |
2377 | /// # Examples |
2378 | /// |
2379 | /// Print the slice split once, starting from the end, by numbers divisible |
2380 | /// by 3 (i.e., `[50]`, `[10, 40, 30, 20]`): |
2381 | /// |
2382 | /// ``` |
2383 | /// let v = [10, 40, 30, 20, 60, 50]; |
2384 | /// |
2385 | /// for group in v.rsplitn(2, |num| *num % 3 == 0) { |
2386 | /// println!("{group:?}" ); |
2387 | /// } |
2388 | /// ``` |
2389 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2390 | #[inline ] |
2391 | pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<'_, T, F> |
2392 | where |
2393 | F: FnMut(&T) -> bool, |
2394 | { |
2395 | RSplitN::new(self.rsplit(pred), n) |
2396 | } |
2397 | |
2398 | /// Returns an iterator over subslices separated by elements that match |
2399 | /// `pred` limited to returning at most `n` items. This starts at the end of |
2400 | /// the slice and works backwards. The matched element is not contained in |
2401 | /// the subslices. |
2402 | /// |
2403 | /// The last element returned, if any, will contain the remainder of the |
2404 | /// slice. |
2405 | /// |
2406 | /// # Examples |
2407 | /// |
2408 | /// ``` |
2409 | /// let mut s = [10, 40, 30, 20, 60, 50]; |
2410 | /// |
2411 | /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) { |
2412 | /// group[0] = 1; |
2413 | /// } |
2414 | /// assert_eq!(s, [1, 40, 30, 20, 60, 1]); |
2415 | /// ``` |
2416 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2417 | #[inline ] |
2418 | pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<'_, T, F> |
2419 | where |
2420 | F: FnMut(&T) -> bool, |
2421 | { |
2422 | RSplitNMut::new(self.rsplit_mut(pred), n) |
2423 | } |
2424 | |
2425 | /// Splits the slice on the first element that matches the specified |
2426 | /// predicate. |
2427 | /// |
2428 | /// If any matching elements are present in the slice, returns the prefix |
2429 | /// before the match and suffix after. The matching element itself is not |
2430 | /// included. If no elements match, returns `None`. |
2431 | /// |
2432 | /// # Examples |
2433 | /// |
2434 | /// ``` |
2435 | /// #![feature(slice_split_once)] |
2436 | /// let s = [1, 2, 3, 2, 4]; |
2437 | /// assert_eq!(s.split_once(|&x| x == 2), Some(( |
2438 | /// &[1][..], |
2439 | /// &[3, 2, 4][..] |
2440 | /// ))); |
2441 | /// assert_eq!(s.split_once(|&x| x == 0), None); |
2442 | /// ``` |
2443 | #[unstable (feature = "slice_split_once" , reason = "newly added" , issue = "112811" )] |
2444 | #[inline ] |
2445 | pub fn split_once<F>(&self, pred: F) -> Option<(&[T], &[T])> |
2446 | where |
2447 | F: FnMut(&T) -> bool, |
2448 | { |
2449 | let index = self.iter().position(pred)?; |
2450 | Some((&self[..index], &self[index + 1..])) |
2451 | } |
2452 | |
2453 | /// Splits the slice on the last element that matches the specified |
2454 | /// predicate. |
2455 | /// |
2456 | /// If any matching elements are present in the slice, returns the prefix |
2457 | /// before the match and suffix after. The matching element itself is not |
2458 | /// included. If no elements match, returns `None`. |
2459 | /// |
2460 | /// # Examples |
2461 | /// |
2462 | /// ``` |
2463 | /// #![feature(slice_split_once)] |
2464 | /// let s = [1, 2, 3, 2, 4]; |
2465 | /// assert_eq!(s.rsplit_once(|&x| x == 2), Some(( |
2466 | /// &[1, 2, 3][..], |
2467 | /// &[4][..] |
2468 | /// ))); |
2469 | /// assert_eq!(s.rsplit_once(|&x| x == 0), None); |
2470 | /// ``` |
2471 | #[unstable (feature = "slice_split_once" , reason = "newly added" , issue = "112811" )] |
2472 | #[inline ] |
2473 | pub fn rsplit_once<F>(&self, pred: F) -> Option<(&[T], &[T])> |
2474 | where |
2475 | F: FnMut(&T) -> bool, |
2476 | { |
2477 | let index = self.iter().rposition(pred)?; |
2478 | Some((&self[..index], &self[index + 1..])) |
2479 | } |
2480 | |
2481 | /// Returns `true` if the slice contains an element with the given value. |
2482 | /// |
2483 | /// This operation is *O*(*n*). |
2484 | /// |
2485 | /// Note that if you have a sorted slice, [`binary_search`] may be faster. |
2486 | /// |
2487 | /// [`binary_search`]: slice::binary_search |
2488 | /// |
2489 | /// # Examples |
2490 | /// |
2491 | /// ``` |
2492 | /// let v = [10, 40, 30]; |
2493 | /// assert!(v.contains(&30)); |
2494 | /// assert!(!v.contains(&50)); |
2495 | /// ``` |
2496 | /// |
2497 | /// If you do not have a `&T`, but some other value that you can compare |
2498 | /// with one (for example, `String` implements `PartialEq<str>`), you can |
2499 | /// use `iter().any`: |
2500 | /// |
2501 | /// ``` |
2502 | /// let v = [String::from("hello" ), String::from("world" )]; // slice of `String` |
2503 | /// assert!(v.iter().any(|e| e == "hello" )); // search with `&str` |
2504 | /// assert!(!v.iter().any(|e| e == "hi" )); |
2505 | /// ``` |
2506 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2507 | #[inline ] |
2508 | #[must_use ] |
2509 | pub fn contains(&self, x: &T) -> bool |
2510 | where |
2511 | T: PartialEq, |
2512 | { |
2513 | cmp::SliceContains::slice_contains(x, self) |
2514 | } |
2515 | |
2516 | /// Returns `true` if `needle` is a prefix of the slice. |
2517 | /// |
2518 | /// # Examples |
2519 | /// |
2520 | /// ``` |
2521 | /// let v = [10, 40, 30]; |
2522 | /// assert!(v.starts_with(&[10])); |
2523 | /// assert!(v.starts_with(&[10, 40])); |
2524 | /// assert!(!v.starts_with(&[50])); |
2525 | /// assert!(!v.starts_with(&[10, 50])); |
2526 | /// ``` |
2527 | /// |
2528 | /// Always returns `true` if `needle` is an empty slice: |
2529 | /// |
2530 | /// ``` |
2531 | /// let v = &[10, 40, 30]; |
2532 | /// assert!(v.starts_with(&[])); |
2533 | /// let v: &[u8] = &[]; |
2534 | /// assert!(v.starts_with(&[])); |
2535 | /// ``` |
2536 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2537 | #[must_use ] |
2538 | pub fn starts_with(&self, needle: &[T]) -> bool |
2539 | where |
2540 | T: PartialEq, |
2541 | { |
2542 | let n = needle.len(); |
2543 | self.len() >= n && needle == &self[..n] |
2544 | } |
2545 | |
2546 | /// Returns `true` if `needle` is a suffix of the slice. |
2547 | /// |
2548 | /// # Examples |
2549 | /// |
2550 | /// ``` |
2551 | /// let v = [10, 40, 30]; |
2552 | /// assert!(v.ends_with(&[30])); |
2553 | /// assert!(v.ends_with(&[40, 30])); |
2554 | /// assert!(!v.ends_with(&[50])); |
2555 | /// assert!(!v.ends_with(&[50, 30])); |
2556 | /// ``` |
2557 | /// |
2558 | /// Always returns `true` if `needle` is an empty slice: |
2559 | /// |
2560 | /// ``` |
2561 | /// let v = &[10, 40, 30]; |
2562 | /// assert!(v.ends_with(&[])); |
2563 | /// let v: &[u8] = &[]; |
2564 | /// assert!(v.ends_with(&[])); |
2565 | /// ``` |
2566 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2567 | #[must_use ] |
2568 | pub fn ends_with(&self, needle: &[T]) -> bool |
2569 | where |
2570 | T: PartialEq, |
2571 | { |
2572 | let (m, n) = (self.len(), needle.len()); |
2573 | m >= n && needle == &self[m - n..] |
2574 | } |
2575 | |
2576 | /// Returns a subslice with the prefix removed. |
2577 | /// |
2578 | /// If the slice starts with `prefix`, returns the subslice after the prefix, wrapped in `Some`. |
2579 | /// If `prefix` is empty, simply returns the original slice. |
2580 | /// |
2581 | /// If the slice does not start with `prefix`, returns `None`. |
2582 | /// |
2583 | /// # Examples |
2584 | /// |
2585 | /// ``` |
2586 | /// let v = &[10, 40, 30]; |
2587 | /// assert_eq!(v.strip_prefix(&[10]), Some(&[40, 30][..])); |
2588 | /// assert_eq!(v.strip_prefix(&[10, 40]), Some(&[30][..])); |
2589 | /// assert_eq!(v.strip_prefix(&[50]), None); |
2590 | /// assert_eq!(v.strip_prefix(&[10, 50]), None); |
2591 | /// |
2592 | /// let prefix : &str = "he" ; |
2593 | /// assert_eq!(b"hello" .strip_prefix(prefix.as_bytes()), |
2594 | /// Some(b"llo" .as_ref())); |
2595 | /// ``` |
2596 | #[must_use = "returns the subslice without modifying the original" ] |
2597 | #[stable (feature = "slice_strip" , since = "1.51.0" )] |
2598 | pub fn strip_prefix<P: SlicePattern<Item = T> + ?Sized>(&self, prefix: &P) -> Option<&[T]> |
2599 | where |
2600 | T: PartialEq, |
2601 | { |
2602 | // This function will need rewriting if and when SlicePattern becomes more sophisticated. |
2603 | let prefix = prefix.as_slice(); |
2604 | let n = prefix.len(); |
2605 | if n <= self.len() { |
2606 | let (head, tail) = self.split_at(n); |
2607 | if head == prefix { |
2608 | return Some(tail); |
2609 | } |
2610 | } |
2611 | None |
2612 | } |
2613 | |
2614 | /// Returns a subslice with the suffix removed. |
2615 | /// |
2616 | /// If the slice ends with `suffix`, returns the subslice before the suffix, wrapped in `Some`. |
2617 | /// If `suffix` is empty, simply returns the original slice. |
2618 | /// |
2619 | /// If the slice does not end with `suffix`, returns `None`. |
2620 | /// |
2621 | /// # Examples |
2622 | /// |
2623 | /// ``` |
2624 | /// let v = &[10, 40, 30]; |
2625 | /// assert_eq!(v.strip_suffix(&[30]), Some(&[10, 40][..])); |
2626 | /// assert_eq!(v.strip_suffix(&[40, 30]), Some(&[10][..])); |
2627 | /// assert_eq!(v.strip_suffix(&[50]), None); |
2628 | /// assert_eq!(v.strip_suffix(&[50, 30]), None); |
2629 | /// ``` |
2630 | #[must_use = "returns the subslice without modifying the original" ] |
2631 | #[stable (feature = "slice_strip" , since = "1.51.0" )] |
2632 | pub fn strip_suffix<P: SlicePattern<Item = T> + ?Sized>(&self, suffix: &P) -> Option<&[T]> |
2633 | where |
2634 | T: PartialEq, |
2635 | { |
2636 | // This function will need rewriting if and when SlicePattern becomes more sophisticated. |
2637 | let suffix = suffix.as_slice(); |
2638 | let (len, n) = (self.len(), suffix.len()); |
2639 | if n <= len { |
2640 | let (head, tail) = self.split_at(len - n); |
2641 | if tail == suffix { |
2642 | return Some(head); |
2643 | } |
2644 | } |
2645 | None |
2646 | } |
2647 | |
2648 | /// Binary searches this slice for a given element. |
2649 | /// If the slice is not sorted, the returned result is unspecified and |
2650 | /// meaningless. |
2651 | /// |
2652 | /// If the value is found then [`Result::Ok`] is returned, containing the |
2653 | /// index of the matching element. If there are multiple matches, then any |
2654 | /// one of the matches could be returned. The index is chosen |
2655 | /// deterministically, but is subject to change in future versions of Rust. |
2656 | /// If the value is not found then [`Result::Err`] is returned, containing |
2657 | /// the index where a matching element could be inserted while maintaining |
2658 | /// sorted order. |
2659 | /// |
2660 | /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`]. |
2661 | /// |
2662 | /// [`binary_search_by`]: slice::binary_search_by |
2663 | /// [`binary_search_by_key`]: slice::binary_search_by_key |
2664 | /// [`partition_point`]: slice::partition_point |
2665 | /// |
2666 | /// # Examples |
2667 | /// |
2668 | /// Looks up a series of four elements. The first is found, with a |
2669 | /// uniquely determined position; the second and third are not |
2670 | /// found; the fourth could match any position in `[1, 4]`. |
2671 | /// |
2672 | /// ``` |
2673 | /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; |
2674 | /// |
2675 | /// assert_eq!(s.binary_search(&13), Ok(9)); |
2676 | /// assert_eq!(s.binary_search(&4), Err(7)); |
2677 | /// assert_eq!(s.binary_search(&100), Err(13)); |
2678 | /// let r = s.binary_search(&1); |
2679 | /// assert!(match r { Ok(1..=4) => true, _ => false, }); |
2680 | /// ``` |
2681 | /// |
2682 | /// If you want to find that whole *range* of matching items, rather than |
2683 | /// an arbitrary matching one, that can be done using [`partition_point`]: |
2684 | /// ``` |
2685 | /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; |
2686 | /// |
2687 | /// let low = s.partition_point(|x| x < &1); |
2688 | /// assert_eq!(low, 1); |
2689 | /// let high = s.partition_point(|x| x <= &1); |
2690 | /// assert_eq!(high, 5); |
2691 | /// let r = s.binary_search(&1); |
2692 | /// assert!((low..high).contains(&r.unwrap())); |
2693 | /// |
2694 | /// assert!(s[..low].iter().all(|&x| x < 1)); |
2695 | /// assert!(s[low..high].iter().all(|&x| x == 1)); |
2696 | /// assert!(s[high..].iter().all(|&x| x > 1)); |
2697 | /// |
2698 | /// // For something not found, the "range" of equal items is empty |
2699 | /// assert_eq!(s.partition_point(|x| x < &11), 9); |
2700 | /// assert_eq!(s.partition_point(|x| x <= &11), 9); |
2701 | /// assert_eq!(s.binary_search(&11), Err(9)); |
2702 | /// ``` |
2703 | /// |
2704 | /// If you want to insert an item to a sorted vector, while maintaining |
2705 | /// sort order, consider using [`partition_point`]: |
2706 | /// |
2707 | /// ``` |
2708 | /// let mut s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; |
2709 | /// let num = 42; |
2710 | /// let idx = s.partition_point(|&x| x < num); |
2711 | /// // The above is equivalent to `let idx = s.binary_search(&num).unwrap_or_else(|x| x);` |
2712 | /// s.insert(idx, num); |
2713 | /// assert_eq!(s, [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]); |
2714 | /// ``` |
2715 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2716 | pub fn binary_search(&self, x: &T) -> Result<usize, usize> |
2717 | where |
2718 | T: Ord, |
2719 | { |
2720 | self.binary_search_by(|p| p.cmp(x)) |
2721 | } |
2722 | |
2723 | /// Binary searches this slice with a comparator function. |
2724 | /// |
2725 | /// The comparator function should return an order code that indicates |
2726 | /// whether its argument is `Less`, `Equal` or `Greater` the desired |
2727 | /// target. |
2728 | /// If the slice is not sorted or if the comparator function does not |
2729 | /// implement an order consistent with the sort order of the underlying |
2730 | /// slice, the returned result is unspecified and meaningless. |
2731 | /// |
2732 | /// If the value is found then [`Result::Ok`] is returned, containing the |
2733 | /// index of the matching element. If there are multiple matches, then any |
2734 | /// one of the matches could be returned. The index is chosen |
2735 | /// deterministically, but is subject to change in future versions of Rust. |
2736 | /// If the value is not found then [`Result::Err`] is returned, containing |
2737 | /// the index where a matching element could be inserted while maintaining |
2738 | /// sorted order. |
2739 | /// |
2740 | /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`]. |
2741 | /// |
2742 | /// [`binary_search`]: slice::binary_search |
2743 | /// [`binary_search_by_key`]: slice::binary_search_by_key |
2744 | /// [`partition_point`]: slice::partition_point |
2745 | /// |
2746 | /// # Examples |
2747 | /// |
2748 | /// Looks up a series of four elements. The first is found, with a |
2749 | /// uniquely determined position; the second and third are not |
2750 | /// found; the fourth could match any position in `[1, 4]`. |
2751 | /// |
2752 | /// ``` |
2753 | /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; |
2754 | /// |
2755 | /// let seek = 13; |
2756 | /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9)); |
2757 | /// let seek = 4; |
2758 | /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7)); |
2759 | /// let seek = 100; |
2760 | /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13)); |
2761 | /// let seek = 1; |
2762 | /// let r = s.binary_search_by(|probe| probe.cmp(&seek)); |
2763 | /// assert!(match r { Ok(1..=4) => true, _ => false, }); |
2764 | /// ``` |
2765 | #[stable (feature = "rust1" , since = "1.0.0" )] |
2766 | #[inline ] |
2767 | pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize> |
2768 | where |
2769 | F: FnMut(&'a T) -> Ordering, |
2770 | { |
2771 | // INVARIANTS: |
2772 | // - 0 <= left <= left + size = right <= self.len() |
2773 | // - f returns Less for everything in self[..left] |
2774 | // - f returns Greater for everything in self[right..] |
2775 | let mut size = self.len(); |
2776 | let mut left = 0; |
2777 | let mut right = size; |
2778 | while left < right { |
2779 | let mid = left + size / 2; |
2780 | |
2781 | // SAFETY: the while condition means `size` is strictly positive, so |
2782 | // `size/2 < size`. Thus `left + size/2 < left + size`, which |
2783 | // coupled with the `left + size <= self.len()` invariant means |
2784 | // we have `left + size/2 < self.len()`, and this is in-bounds. |
2785 | let cmp = f(unsafe { self.get_unchecked(mid) }); |
2786 | |
2787 | // This control flow produces conditional moves, which results in |
2788 | // fewer branches and instructions than if/else or matching on |
2789 | // cmp::Ordering. |
2790 | // This is x86 asm for u8: https://rust.godbolt.org/z/698eYffTx. |
2791 | left = if cmp == Less { mid + 1 } else { left }; |
2792 | right = if cmp == Greater { mid } else { right }; |
2793 | if cmp == Equal { |
2794 | // SAFETY: same as the `get_unchecked` above |
2795 | unsafe { hint::assert_unchecked(mid < self.len()) }; |
2796 | return Ok(mid); |
2797 | } |
2798 | |
2799 | size = right - left; |
2800 | } |
2801 | |
2802 | // SAFETY: directly true from the overall invariant. |
2803 | // Note that this is `<=`, unlike the assume in the `Ok` path. |
2804 | unsafe { hint::assert_unchecked(left <= self.len()) }; |
2805 | Err(left) |
2806 | } |
2807 | |
2808 | /// Binary searches this slice with a key extraction function. |
2809 | /// |
2810 | /// Assumes that the slice is sorted by the key, for instance with |
2811 | /// [`sort_by_key`] using the same key extraction function. |
2812 | /// If the slice is not sorted by the key, the returned result is |
2813 | /// unspecified and meaningless. |
2814 | /// |
2815 | /// If the value is found then [`Result::Ok`] is returned, containing the |
2816 | /// index of the matching element. If there are multiple matches, then any |
2817 | /// one of the matches could be returned. The index is chosen |
2818 | /// deterministically, but is subject to change in future versions of Rust. |
2819 | /// If the value is not found then [`Result::Err`] is returned, containing |
2820 | /// the index where a matching element could be inserted while maintaining |
2821 | /// sorted order. |
2822 | /// |
2823 | /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`]. |
2824 | /// |
2825 | /// [`sort_by_key`]: slice::sort_by_key |
2826 | /// [`binary_search`]: slice::binary_search |
2827 | /// [`binary_search_by`]: slice::binary_search_by |
2828 | /// [`partition_point`]: slice::partition_point |
2829 | /// |
2830 | /// # Examples |
2831 | /// |
2832 | /// Looks up a series of four elements in a slice of pairs sorted by |
2833 | /// their second elements. The first is found, with a uniquely |
2834 | /// determined position; the second and third are not found; the |
2835 | /// fourth could match any position in `[1, 4]`. |
2836 | /// |
2837 | /// ``` |
2838 | /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1), |
2839 | /// (1, 2), (2, 3), (4, 5), (5, 8), (3, 13), |
2840 | /// (1, 21), (2, 34), (4, 55)]; |
2841 | /// |
2842 | /// assert_eq!(s.binary_search_by_key(&13, |&(a, b)| b), Ok(9)); |
2843 | /// assert_eq!(s.binary_search_by_key(&4, |&(a, b)| b), Err(7)); |
2844 | /// assert_eq!(s.binary_search_by_key(&100, |&(a, b)| b), Err(13)); |
2845 | /// let r = s.binary_search_by_key(&1, |&(a, b)| b); |
2846 | /// assert!(match r { Ok(1..=4) => true, _ => false, }); |
2847 | /// ``` |
2848 | // Lint rustdoc::broken_intra_doc_links is allowed as `slice::sort_by_key` is |
2849 | // in crate `alloc`, and as such doesn't exists yet when building `core`: #74481. |
2850 | // This breaks links when slice is displayed in core, but changing it to use relative links |
2851 | // would break when the item is re-exported. So allow the core links to be broken for now. |
2852 | #[allow (rustdoc::broken_intra_doc_links)] |
2853 | #[stable (feature = "slice_binary_search_by_key" , since = "1.10.0" )] |
2854 | #[inline ] |
2855 | pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize> |
2856 | where |
2857 | F: FnMut(&'a T) -> B, |
2858 | B: Ord, |
2859 | { |
2860 | self.binary_search_by(|k| f(k).cmp(b)) |
2861 | } |
2862 | |
2863 | /// Sorts the slice, but might not preserve the order of equal elements. |
2864 | /// |
2865 | /// This sort is unstable (i.e., may reorder equal elements), in-place |
2866 | /// (i.e., does not allocate), and *O*(*n* \* log(*n*)) worst-case. |
2867 | /// |
2868 | /// # Current implementation |
2869 | /// |
2870 | /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters, |
2871 | /// which combines the fast average case of randomized quicksort with the fast worst case of |
2872 | /// heapsort, while achieving linear time on slices with certain patterns. It uses some |
2873 | /// randomization to avoid degenerate cases, but with a fixed seed to always provide |
2874 | /// deterministic behavior. |
2875 | /// |
2876 | /// It is typically faster than stable sorting, except in a few special cases, e.g., when the |
2877 | /// slice consists of several concatenated sorted sequences. |
2878 | /// |
2879 | /// # Examples |
2880 | /// |
2881 | /// ``` |
2882 | /// let mut v = [-5, 4, 1, -3, 2]; |
2883 | /// |
2884 | /// v.sort_unstable(); |
2885 | /// assert!(v == [-5, -3, 1, 2, 4]); |
2886 | /// ``` |
2887 | /// |
2888 | /// [pdqsort]: https://github.com/orlp/pdqsort |
2889 | #[stable (feature = "sort_unstable" , since = "1.20.0" )] |
2890 | #[inline ] |
2891 | pub fn sort_unstable(&mut self) |
2892 | where |
2893 | T: Ord, |
2894 | { |
2895 | sort::quicksort(self, T::lt); |
2896 | } |
2897 | |
2898 | /// Sorts the slice with a comparator function, but might not preserve the order of equal |
2899 | /// elements. |
2900 | /// |
2901 | /// This sort is unstable (i.e., may reorder equal elements), in-place |
2902 | /// (i.e., does not allocate), and *O*(*n* \* log(*n*)) worst-case. |
2903 | /// |
2904 | /// The comparator function must define a total ordering for the elements in the slice. If |
2905 | /// the ordering is not total, the order of the elements is unspecified. An order is a |
2906 | /// total order if it is (for all `a`, `b` and `c`): |
2907 | /// |
2908 | /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and |
2909 | /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. |
2910 | /// |
2911 | /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use |
2912 | /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`. |
2913 | /// |
2914 | /// ``` |
2915 | /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0]; |
2916 | /// floats.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap()); |
2917 | /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]); |
2918 | /// ``` |
2919 | /// |
2920 | /// # Current implementation |
2921 | /// |
2922 | /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters, |
2923 | /// which combines the fast average case of randomized quicksort with the fast worst case of |
2924 | /// heapsort, while achieving linear time on slices with certain patterns. It uses some |
2925 | /// randomization to avoid degenerate cases, but with a fixed seed to always provide |
2926 | /// deterministic behavior. |
2927 | /// |
2928 | /// It is typically faster than stable sorting, except in a few special cases, e.g., when the |
2929 | /// slice consists of several concatenated sorted sequences. |
2930 | /// |
2931 | /// # Examples |
2932 | /// |
2933 | /// ``` |
2934 | /// let mut v = [5, 4, 1, 3, 2]; |
2935 | /// v.sort_unstable_by(|a, b| a.cmp(b)); |
2936 | /// assert!(v == [1, 2, 3, 4, 5]); |
2937 | /// |
2938 | /// // reverse sorting |
2939 | /// v.sort_unstable_by(|a, b| b.cmp(a)); |
2940 | /// assert!(v == [5, 4, 3, 2, 1]); |
2941 | /// ``` |
2942 | /// |
2943 | /// [pdqsort]: https://github.com/orlp/pdqsort |
2944 | #[stable (feature = "sort_unstable" , since = "1.20.0" )] |
2945 | #[inline ] |
2946 | pub fn sort_unstable_by<F>(&mut self, mut compare: F) |
2947 | where |
2948 | F: FnMut(&T, &T) -> Ordering, |
2949 | { |
2950 | sort::quicksort(self, |a, b| compare(a, b) == Ordering::Less); |
2951 | } |
2952 | |
2953 | /// Sorts the slice with a key extraction function, but might not preserve the order of equal |
2954 | /// elements. |
2955 | /// |
2956 | /// This sort is unstable (i.e., may reorder equal elements), in-place |
2957 | /// (i.e., does not allocate), and *O*(*m* \* *n* \* log(*n*)) worst-case, where the key function is |
2958 | /// *O*(*m*). |
2959 | /// |
2960 | /// # Current implementation |
2961 | /// |
2962 | /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters, |
2963 | /// which combines the fast average case of randomized quicksort with the fast worst case of |
2964 | /// heapsort, while achieving linear time on slices with certain patterns. It uses some |
2965 | /// randomization to avoid degenerate cases, but with a fixed seed to always provide |
2966 | /// deterministic behavior. |
2967 | /// |
2968 | /// Due to its key calling strategy, [`sort_unstable_by_key`](#method.sort_unstable_by_key) |
2969 | /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_cached_key) in |
2970 | /// cases where the key function is expensive. |
2971 | /// |
2972 | /// # Examples |
2973 | /// |
2974 | /// ``` |
2975 | /// let mut v = [-5i32, 4, 1, -3, 2]; |
2976 | /// |
2977 | /// v.sort_unstable_by_key(|k| k.abs()); |
2978 | /// assert!(v == [1, 2, -3, 4, -5]); |
2979 | /// ``` |
2980 | /// |
2981 | /// [pdqsort]: https://github.com/orlp/pdqsort |
2982 | #[stable (feature = "sort_unstable" , since = "1.20.0" )] |
2983 | #[inline ] |
2984 | pub fn sort_unstable_by_key<K, F>(&mut self, mut f: F) |
2985 | where |
2986 | F: FnMut(&T) -> K, |
2987 | K: Ord, |
2988 | { |
2989 | sort::quicksort(self, |a, b| f(a).lt(&f(b))); |
2990 | } |
2991 | |
2992 | /// Reorder the slice such that the element at `index` is at its final sorted position. |
2993 | /// |
2994 | /// This reordering has the additional property that any value at position `i < index` will be |
2995 | /// less than or equal to any value at a position `j > index`. Additionally, this reordering is |
2996 | /// unstable (i.e. any number of equal elements may end up at position `index`), in-place |
2997 | /// (i.e. does not allocate), and runs in *O*(*n*) time. |
2998 | /// This function is also known as "kth element" in other libraries. |
2999 | /// |
3000 | /// It returns a triplet of the following from the reordered slice: |
3001 | /// the subslice prior to `index`, the element at `index`, and the subslice after `index`; |
3002 | /// accordingly, the values in those two subslices will respectively all be less-than-or-equal-to |
3003 | /// and greater-than-or-equal-to the value of the element at `index`. |
3004 | /// |
3005 | /// # Current implementation |
3006 | /// |
3007 | /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also |
3008 | /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for |
3009 | /// pivot selection, which guarantees linear runtime for all inputs. |
3010 | /// |
3011 | /// [`sort_unstable`]: slice::sort_unstable |
3012 | /// |
3013 | /// # Panics |
3014 | /// |
3015 | /// Panics when `index >= len()`, meaning it always panics on empty slices. |
3016 | /// |
3017 | /// # Examples |
3018 | /// |
3019 | /// ``` |
3020 | /// let mut v = [-5i32, 4, 1, -3, 2]; |
3021 | /// |
3022 | /// // Find the median |
3023 | /// v.select_nth_unstable(2); |
3024 | /// |
3025 | /// // We are only guaranteed the slice will be one of the following, based on the way we sort |
3026 | /// // about the specified index. |
3027 | /// assert!(v == [-3, -5, 1, 2, 4] || |
3028 | /// v == [-5, -3, 1, 2, 4] || |
3029 | /// v == [-3, -5, 1, 4, 2] || |
3030 | /// v == [-5, -3, 1, 4, 2]); |
3031 | /// ``` |
3032 | #[stable (feature = "slice_select_nth_unstable" , since = "1.49.0" )] |
3033 | #[inline ] |
3034 | pub fn select_nth_unstable(&mut self, index: usize) -> (&mut [T], &mut T, &mut [T]) |
3035 | where |
3036 | T: Ord, |
3037 | { |
3038 | select::partition_at_index(self, index, T::lt) |
3039 | } |
3040 | |
3041 | /// Reorder the slice with a comparator function such that the element at `index` is at its |
3042 | /// final sorted position. |
3043 | /// |
3044 | /// This reordering has the additional property that any value at position `i < index` will be |
3045 | /// less than or equal to any value at a position `j > index` using the comparator function. |
3046 | /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at |
3047 | /// position `index`), in-place (i.e. does not allocate), and runs in *O*(*n*) time. |
3048 | /// This function is also known as "kth element" in other libraries. |
3049 | /// |
3050 | /// It returns a triplet of the following from |
3051 | /// the slice reordered according to the provided comparator function: the subslice prior to |
3052 | /// `index`, the element at `index`, and the subslice after `index`; accordingly, the values in |
3053 | /// those two subslices will respectively all be less-than-or-equal-to and greater-than-or-equal-to |
3054 | /// the value of the element at `index`. |
3055 | /// |
3056 | /// # Current implementation |
3057 | /// |
3058 | /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also |
3059 | /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for |
3060 | /// pivot selection, which guarantees linear runtime for all inputs. |
3061 | /// |
3062 | /// [`sort_unstable`]: slice::sort_unstable |
3063 | /// |
3064 | /// # Panics |
3065 | /// |
3066 | /// Panics when `index >= len()`, meaning it always panics on empty slices. |
3067 | /// |
3068 | /// # Examples |
3069 | /// |
3070 | /// ``` |
3071 | /// let mut v = [-5i32, 4, 1, -3, 2]; |
3072 | /// |
3073 | /// // Find the median as if the slice were sorted in descending order. |
3074 | /// v.select_nth_unstable_by(2, |a, b| b.cmp(a)); |
3075 | /// |
3076 | /// // We are only guaranteed the slice will be one of the following, based on the way we sort |
3077 | /// // about the specified index. |
3078 | /// assert!(v == [2, 4, 1, -5, -3] || |
3079 | /// v == [2, 4, 1, -3, -5] || |
3080 | /// v == [4, 2, 1, -5, -3] || |
3081 | /// v == [4, 2, 1, -3, -5]); |
3082 | /// ``` |
3083 | #[stable (feature = "slice_select_nth_unstable" , since = "1.49.0" )] |
3084 | #[inline ] |
3085 | pub fn select_nth_unstable_by<F>( |
3086 | &mut self, |
3087 | index: usize, |
3088 | mut compare: F, |
3089 | ) -> (&mut [T], &mut T, &mut [T]) |
3090 | where |
3091 | F: FnMut(&T, &T) -> Ordering, |
3092 | { |
3093 | select::partition_at_index(self, index, |a: &T, b: &T| compare(a, b) == Less) |
3094 | } |
3095 | |
3096 | /// Reorder the slice with a key extraction function such that the element at `index` is at its |
3097 | /// final sorted position. |
3098 | /// |
3099 | /// This reordering has the additional property that any value at position `i < index` will be |
3100 | /// less than or equal to any value at a position `j > index` using the key extraction function. |
3101 | /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at |
3102 | /// position `index`), in-place (i.e. does not allocate), and runs in *O*(*n*) time. |
3103 | /// This function is also known as "kth element" in other libraries. |
3104 | /// |
3105 | /// It returns a triplet of the following from |
3106 | /// the slice reordered according to the provided key extraction function: the subslice prior to |
3107 | /// `index`, the element at `index`, and the subslice after `index`; accordingly, the values in |
3108 | /// those two subslices will respectively all be less-than-or-equal-to and greater-than-or-equal-to |
3109 | /// the value of the element at `index`. |
3110 | /// |
3111 | /// # Current implementation |
3112 | /// |
3113 | /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also |
3114 | /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for |
3115 | /// pivot selection, which guarantees linear runtime for all inputs. |
3116 | /// |
3117 | /// [`sort_unstable`]: slice::sort_unstable |
3118 | /// |
3119 | /// # Panics |
3120 | /// |
3121 | /// Panics when `index >= len()`, meaning it always panics on empty slices. |
3122 | /// |
3123 | /// # Examples |
3124 | /// |
3125 | /// ``` |
3126 | /// let mut v = [-5i32, 4, 1, -3, 2]; |
3127 | /// |
3128 | /// // Return the median as if the array were sorted according to absolute value. |
3129 | /// v.select_nth_unstable_by_key(2, |a| a.abs()); |
3130 | /// |
3131 | /// // We are only guaranteed the slice will be one of the following, based on the way we sort |
3132 | /// // about the specified index. |
3133 | /// assert!(v == [1, 2, -3, 4, -5] || |
3134 | /// v == [1, 2, -3, -5, 4] || |
3135 | /// v == [2, 1, -3, 4, -5] || |
3136 | /// v == [2, 1, -3, -5, 4]); |
3137 | /// ``` |
3138 | #[stable (feature = "slice_select_nth_unstable" , since = "1.49.0" )] |
3139 | #[inline ] |
3140 | pub fn select_nth_unstable_by_key<K, F>( |
3141 | &mut self, |
3142 | index: usize, |
3143 | mut f: F, |
3144 | ) -> (&mut [T], &mut T, &mut [T]) |
3145 | where |
3146 | F: FnMut(&T) -> K, |
3147 | K: Ord, |
3148 | { |
3149 | select::partition_at_index(self, index, |a: &T, b: &T| f(a).lt(&f(b))) |
3150 | } |
3151 | |
3152 | /// Moves all consecutive repeated elements to the end of the slice according to the |
3153 | /// [`PartialEq`] trait implementation. |
3154 | /// |
3155 | /// Returns two slices. The first contains no consecutive repeated elements. |
3156 | /// The second contains all the duplicates in no specified order. |
3157 | /// |
3158 | /// If the slice is sorted, the first returned slice contains no duplicates. |
3159 | /// |
3160 | /// # Examples |
3161 | /// |
3162 | /// ``` |
3163 | /// #![feature(slice_partition_dedup)] |
3164 | /// |
3165 | /// let mut slice = [1, 2, 2, 3, 3, 2, 1, 1]; |
3166 | /// |
3167 | /// let (dedup, duplicates) = slice.partition_dedup(); |
3168 | /// |
3169 | /// assert_eq!(dedup, [1, 2, 3, 2, 1]); |
3170 | /// assert_eq!(duplicates, [2, 3, 1]); |
3171 | /// ``` |
3172 | #[unstable (feature = "slice_partition_dedup" , issue = "54279" )] |
3173 | #[inline ] |
3174 | pub fn partition_dedup(&mut self) -> (&mut [T], &mut [T]) |
3175 | where |
3176 | T: PartialEq, |
3177 | { |
3178 | self.partition_dedup_by(|a, b| a == b) |
3179 | } |
3180 | |
3181 | /// Moves all but the first of consecutive elements to the end of the slice satisfying |
3182 | /// a given equality relation. |
3183 | /// |
3184 | /// Returns two slices. The first contains no consecutive repeated elements. |
3185 | /// The second contains all the duplicates in no specified order. |
3186 | /// |
3187 | /// The `same_bucket` function is passed references to two elements from the slice and |
3188 | /// must determine if the elements compare equal. The elements are passed in opposite order |
3189 | /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is moved |
3190 | /// at the end of the slice. |
3191 | /// |
3192 | /// If the slice is sorted, the first returned slice contains no duplicates. |
3193 | /// |
3194 | /// # Examples |
3195 | /// |
3196 | /// ``` |
3197 | /// #![feature(slice_partition_dedup)] |
3198 | /// |
3199 | /// let mut slice = ["foo" , "Foo" , "BAZ" , "Bar" , "bar" , "baz" , "BAZ" ]; |
3200 | /// |
3201 | /// let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.eq_ignore_ascii_case(b)); |
3202 | /// |
3203 | /// assert_eq!(dedup, ["foo" , "BAZ" , "Bar" , "baz" ]); |
3204 | /// assert_eq!(duplicates, ["bar" , "Foo" , "BAZ" ]); |
3205 | /// ``` |
3206 | #[unstable (feature = "slice_partition_dedup" , issue = "54279" )] |
3207 | #[inline ] |
3208 | pub fn partition_dedup_by<F>(&mut self, mut same_bucket: F) -> (&mut [T], &mut [T]) |
3209 | where |
3210 | F: FnMut(&mut T, &mut T) -> bool, |
3211 | { |
3212 | // Although we have a mutable reference to `self`, we cannot make |
3213 | // *arbitrary* changes. The `same_bucket` calls could panic, so we |
3214 | // must ensure that the slice is in a valid state at all times. |
3215 | // |
3216 | // The way that we handle this is by using swaps; we iterate |
3217 | // over all the elements, swapping as we go so that at the end |
3218 | // the elements we wish to keep are in the front, and those we |
3219 | // wish to reject are at the back. We can then split the slice. |
3220 | // This operation is still `O(n)`. |
3221 | // |
3222 | // Example: We start in this state, where `r` represents "next |
3223 | // read" and `w` represents "next_write". |
3224 | // |
3225 | // r |
3226 | // +---+---+---+---+---+---+ |
3227 | // | 0 | 1 | 1 | 2 | 3 | 3 | |
3228 | // +---+---+---+---+---+---+ |
3229 | // w |
3230 | // |
3231 | // Comparing self[r] against self[w-1], this is not a duplicate, so |
3232 | // we swap self[r] and self[w] (no effect as r==w) and then increment both |
3233 | // r and w, leaving us with: |
3234 | // |
3235 | // r |
3236 | // +---+---+---+---+---+---+ |
3237 | // | 0 | 1 | 1 | 2 | 3 | 3 | |
3238 | // +---+---+---+---+---+---+ |
3239 | // w |
3240 | // |
3241 | // Comparing self[r] against self[w-1], this value is a duplicate, |
3242 | // so we increment `r` but leave everything else unchanged: |
3243 | // |
3244 | // r |
3245 | // +---+---+---+---+---+---+ |
3246 | // | 0 | 1 | 1 | 2 | 3 | 3 | |
3247 | // +---+---+---+---+---+---+ |
3248 | // w |
3249 | // |
3250 | // Comparing self[r] against self[w-1], this is not a duplicate, |
3251 | // so swap self[r] and self[w] and advance r and w: |
3252 | // |
3253 | // r |
3254 | // +---+---+---+---+---+---+ |
3255 | // | 0 | 1 | 2 | 1 | 3 | 3 | |
3256 | // +---+---+---+---+---+---+ |
3257 | // w |
3258 | // |
3259 | // Not a duplicate, repeat: |
3260 | // |
3261 | // r |
3262 | // +---+---+---+---+---+---+ |
3263 | // | 0 | 1 | 2 | 3 | 1 | 3 | |
3264 | // +---+---+---+---+---+---+ |
3265 | // w |
3266 | // |
3267 | // Duplicate, advance r. End of slice. Split at w. |
3268 | |
3269 | let len = self.len(); |
3270 | if len <= 1 { |
3271 | return (self, &mut []); |
3272 | } |
3273 | |
3274 | let ptr = self.as_mut_ptr(); |
3275 | let mut next_read: usize = 1; |
3276 | let mut next_write: usize = 1; |
3277 | |
3278 | // SAFETY: the `while` condition guarantees `next_read` and `next_write` |
3279 | // are less than `len`, thus are inside `self`. `prev_ptr_write` points to |
3280 | // one element before `ptr_write`, but `next_write` starts at 1, so |
3281 | // `prev_ptr_write` is never less than 0 and is inside the slice. |
3282 | // This fulfils the requirements for dereferencing `ptr_read`, `prev_ptr_write` |
3283 | // and `ptr_write`, and for using `ptr.add(next_read)`, `ptr.add(next_write - 1)` |
3284 | // and `prev_ptr_write.offset(1)`. |
3285 | // |
3286 | // `next_write` is also incremented at most once per loop at most meaning |
3287 | // no element is skipped when it may need to be swapped. |
3288 | // |
3289 | // `ptr_read` and `prev_ptr_write` never point to the same element. This |
3290 | // is required for `&mut *ptr_read`, `&mut *prev_ptr_write` to be safe. |
3291 | // The explanation is simply that `next_read >= next_write` is always true, |
3292 | // thus `next_read > next_write - 1` is too. |
3293 | unsafe { |
3294 | // Avoid bounds checks by using raw pointers. |
3295 | while next_read < len { |
3296 | let ptr_read = ptr.add(next_read); |
3297 | let prev_ptr_write = ptr.add(next_write - 1); |
3298 | if !same_bucket(&mut *ptr_read, &mut *prev_ptr_write) { |
3299 | if next_read != next_write { |
3300 | let ptr_write = prev_ptr_write.add(1); |
3301 | mem::swap(&mut *ptr_read, &mut *ptr_write); |
3302 | } |
3303 | next_write += 1; |
3304 | } |
3305 | next_read += 1; |
3306 | } |
3307 | } |
3308 | |
3309 | self.split_at_mut(next_write) |
3310 | } |
3311 | |
3312 | /// Moves all but the first of consecutive elements to the end of the slice that resolve |
3313 | /// to the same key. |
3314 | /// |
3315 | /// Returns two slices. The first contains no consecutive repeated elements. |
3316 | /// The second contains all the duplicates in no specified order. |
3317 | /// |
3318 | /// If the slice is sorted, the first returned slice contains no duplicates. |
3319 | /// |
3320 | /// # Examples |
3321 | /// |
3322 | /// ``` |
3323 | /// #![feature(slice_partition_dedup)] |
3324 | /// |
3325 | /// let mut slice = [10, 20, 21, 30, 30, 20, 11, 13]; |
3326 | /// |
3327 | /// let (dedup, duplicates) = slice.partition_dedup_by_key(|i| *i / 10); |
3328 | /// |
3329 | /// assert_eq!(dedup, [10, 20, 30, 20, 11]); |
3330 | /// assert_eq!(duplicates, [21, 30, 13]); |
3331 | /// ``` |
3332 | #[unstable (feature = "slice_partition_dedup" , issue = "54279" )] |
3333 | #[inline ] |
3334 | pub fn partition_dedup_by_key<K, F>(&mut self, mut key: F) -> (&mut [T], &mut [T]) |
3335 | where |
3336 | F: FnMut(&mut T) -> K, |
3337 | K: PartialEq, |
3338 | { |
3339 | self.partition_dedup_by(|a, b| key(a) == key(b)) |
3340 | } |
3341 | |
3342 | /// Rotates the slice in-place such that the first `mid` elements of the |
3343 | /// slice move to the end while the last `self.len() - mid` elements move to |
3344 | /// the front. After calling `rotate_left`, the element previously at index |
3345 | /// `mid` will become the first element in the slice. |
3346 | /// |
3347 | /// # Panics |
3348 | /// |
3349 | /// This function will panic if `mid` is greater than the length of the |
3350 | /// slice. Note that `mid == self.len()` does _not_ panic and is a no-op |
3351 | /// rotation. |
3352 | /// |
3353 | /// # Complexity |
3354 | /// |
3355 | /// Takes linear (in `self.len()`) time. |
3356 | /// |
3357 | /// # Examples |
3358 | /// |
3359 | /// ``` |
3360 | /// let mut a = ['a' , 'b' , 'c' , 'd' , 'e' , 'f' ]; |
3361 | /// a.rotate_left(2); |
3362 | /// assert_eq!(a, ['c' , 'd' , 'e' , 'f' , 'a' , 'b' ]); |
3363 | /// ``` |
3364 | /// |
3365 | /// Rotating a subslice: |
3366 | /// |
3367 | /// ``` |
3368 | /// let mut a = ['a' , 'b' , 'c' , 'd' , 'e' , 'f' ]; |
3369 | /// a[1..5].rotate_left(1); |
3370 | /// assert_eq!(a, ['a' , 'c' , 'd' , 'e' , 'b' , 'f' ]); |
3371 | /// ``` |
3372 | #[stable (feature = "slice_rotate" , since = "1.26.0" )] |
3373 | pub fn rotate_left(&mut self, mid: usize) { |
3374 | assert!(mid <= self.len()); |
3375 | let k = self.len() - mid; |
3376 | let p = self.as_mut_ptr(); |
3377 | |
3378 | // SAFETY: The range `[p.add(mid) - mid, p.add(mid) + k)` is trivially |
3379 | // valid for reading and writing, as required by `ptr_rotate`. |
3380 | unsafe { |
3381 | rotate::ptr_rotate(mid, p.add(mid), k); |
3382 | } |
3383 | } |
3384 | |
3385 | /// Rotates the slice in-place such that the first `self.len() - k` |
3386 | /// elements of the slice move to the end while the last `k` elements move |
3387 | /// to the front. After calling `rotate_right`, the element previously at |
3388 | /// index `self.len() - k` will become the first element in the slice. |
3389 | /// |
3390 | /// # Panics |
3391 | /// |
3392 | /// This function will panic if `k` is greater than the length of the |
3393 | /// slice. Note that `k == self.len()` does _not_ panic and is a no-op |
3394 | /// rotation. |
3395 | /// |
3396 | /// # Complexity |
3397 | /// |
3398 | /// Takes linear (in `self.len()`) time. |
3399 | /// |
3400 | /// # Examples |
3401 | /// |
3402 | /// ``` |
3403 | /// let mut a = ['a' , 'b' , 'c' , 'd' , 'e' , 'f' ]; |
3404 | /// a.rotate_right(2); |
3405 | /// assert_eq!(a, ['e' , 'f' , 'a' , 'b' , 'c' , 'd' ]); |
3406 | /// ``` |
3407 | /// |
3408 | /// Rotating a subslice: |
3409 | /// |
3410 | /// ``` |
3411 | /// let mut a = ['a' , 'b' , 'c' , 'd' , 'e' , 'f' ]; |
3412 | /// a[1..5].rotate_right(1); |
3413 | /// assert_eq!(a, ['a' , 'e' , 'b' , 'c' , 'd' , 'f' ]); |
3414 | /// ``` |
3415 | #[stable (feature = "slice_rotate" , since = "1.26.0" )] |
3416 | pub fn rotate_right(&mut self, k: usize) { |
3417 | assert!(k <= self.len()); |
3418 | let mid = self.len() - k; |
3419 | let p = self.as_mut_ptr(); |
3420 | |
3421 | // SAFETY: The range `[p.add(mid) - mid, p.add(mid) + k)` is trivially |
3422 | // valid for reading and writing, as required by `ptr_rotate`. |
3423 | unsafe { |
3424 | rotate::ptr_rotate(mid, p.add(mid), k); |
3425 | } |
3426 | } |
3427 | |
3428 | /// Fills `self` with elements by cloning `value`. |
3429 | /// |
3430 | /// # Examples |
3431 | /// |
3432 | /// ``` |
3433 | /// let mut buf = vec![0; 10]; |
3434 | /// buf.fill(1); |
3435 | /// assert_eq!(buf, vec![1; 10]); |
3436 | /// ``` |
3437 | #[doc (alias = "memset" )] |
3438 | #[stable (feature = "slice_fill" , since = "1.50.0" )] |
3439 | pub fn fill(&mut self, value: T) |
3440 | where |
3441 | T: Clone, |
3442 | { |
3443 | specialize::SpecFill::spec_fill(self, value); |
3444 | } |
3445 | |
3446 | /// Fills `self` with elements returned by calling a closure repeatedly. |
3447 | /// |
3448 | /// This method uses a closure to create new values. If you'd rather |
3449 | /// [`Clone`] a given value, use [`fill`]. If you want to use the [`Default`] |
3450 | /// trait to generate values, you can pass [`Default::default`] as the |
3451 | /// argument. |
3452 | /// |
3453 | /// [`fill`]: slice::fill |
3454 | /// |
3455 | /// # Examples |
3456 | /// |
3457 | /// ``` |
3458 | /// let mut buf = vec![1; 10]; |
3459 | /// buf.fill_with(Default::default); |
3460 | /// assert_eq!(buf, vec![0; 10]); |
3461 | /// ``` |
3462 | #[stable (feature = "slice_fill_with" , since = "1.51.0" )] |
3463 | pub fn fill_with<F>(&mut self, mut f: F) |
3464 | where |
3465 | F: FnMut() -> T, |
3466 | { |
3467 | for el in self { |
3468 | *el = f(); |
3469 | } |
3470 | } |
3471 | |
3472 | /// Copies the elements from `src` into `self`. |
3473 | /// |
3474 | /// The length of `src` must be the same as `self`. |
3475 | /// |
3476 | /// # Panics |
3477 | /// |
3478 | /// This function will panic if the two slices have different lengths. |
3479 | /// |
3480 | /// # Examples |
3481 | /// |
3482 | /// Cloning two elements from a slice into another: |
3483 | /// |
3484 | /// ``` |
3485 | /// let src = [1, 2, 3, 4]; |
3486 | /// let mut dst = [0, 0]; |
3487 | /// |
3488 | /// // Because the slices have to be the same length, |
3489 | /// // we slice the source slice from four elements |
3490 | /// // to two. It will panic if we don't do this. |
3491 | /// dst.clone_from_slice(&src[2..]); |
3492 | /// |
3493 | /// assert_eq!(src, [1, 2, 3, 4]); |
3494 | /// assert_eq!(dst, [3, 4]); |
3495 | /// ``` |
3496 | /// |
3497 | /// Rust enforces that there can only be one mutable reference with no |
3498 | /// immutable references to a particular piece of data in a particular |
3499 | /// scope. Because of this, attempting to use `clone_from_slice` on a |
3500 | /// single slice will result in a compile failure: |
3501 | /// |
3502 | /// ```compile_fail |
3503 | /// let mut slice = [1, 2, 3, 4, 5]; |
3504 | /// |
3505 | /// slice[..2].clone_from_slice(&slice[3..]); // compile fail! |
3506 | /// ``` |
3507 | /// |
3508 | /// To work around this, we can use [`split_at_mut`] to create two distinct |
3509 | /// sub-slices from a slice: |
3510 | /// |
3511 | /// ``` |
3512 | /// let mut slice = [1, 2, 3, 4, 5]; |
3513 | /// |
3514 | /// { |
3515 | /// let (left, right) = slice.split_at_mut(2); |
3516 | /// left.clone_from_slice(&right[1..]); |
3517 | /// } |
3518 | /// |
3519 | /// assert_eq!(slice, [4, 5, 3, 4, 5]); |
3520 | /// ``` |
3521 | /// |
3522 | /// [`copy_from_slice`]: slice::copy_from_slice |
3523 | /// [`split_at_mut`]: slice::split_at_mut |
3524 | #[stable (feature = "clone_from_slice" , since = "1.7.0" )] |
3525 | #[track_caller ] |
3526 | pub fn clone_from_slice(&mut self, src: &[T]) |
3527 | where |
3528 | T: Clone, |
3529 | { |
3530 | self.spec_clone_from(src); |
3531 | } |
3532 | |
3533 | /// Copies all elements from `src` into `self`, using a memcpy. |
3534 | /// |
3535 | /// The length of `src` must be the same as `self`. |
3536 | /// |
3537 | /// If `T` does not implement `Copy`, use [`clone_from_slice`]. |
3538 | /// |
3539 | /// # Panics |
3540 | /// |
3541 | /// This function will panic if the two slices have different lengths. |
3542 | /// |
3543 | /// # Examples |
3544 | /// |
3545 | /// Copying two elements from a slice into another: |
3546 | /// |
3547 | /// ``` |
3548 | /// let src = [1, 2, 3, 4]; |
3549 | /// let mut dst = [0, 0]; |
3550 | /// |
3551 | /// // Because the slices have to be the same length, |
3552 | /// // we slice the source slice from four elements |
3553 | /// // to two. It will panic if we don't do this. |
3554 | /// dst.copy_from_slice(&src[2..]); |
3555 | /// |
3556 | /// assert_eq!(src, [1, 2, 3, 4]); |
3557 | /// assert_eq!(dst, [3, 4]); |
3558 | /// ``` |
3559 | /// |
3560 | /// Rust enforces that there can only be one mutable reference with no |
3561 | /// immutable references to a particular piece of data in a particular |
3562 | /// scope. Because of this, attempting to use `copy_from_slice` on a |
3563 | /// single slice will result in a compile failure: |
3564 | /// |
3565 | /// ```compile_fail |
3566 | /// let mut slice = [1, 2, 3, 4, 5]; |
3567 | /// |
3568 | /// slice[..2].copy_from_slice(&slice[3..]); // compile fail! |
3569 | /// ``` |
3570 | /// |
3571 | /// To work around this, we can use [`split_at_mut`] to create two distinct |
3572 | /// sub-slices from a slice: |
3573 | /// |
3574 | /// ``` |
3575 | /// let mut slice = [1, 2, 3, 4, 5]; |
3576 | /// |
3577 | /// { |
3578 | /// let (left, right) = slice.split_at_mut(2); |
3579 | /// left.copy_from_slice(&right[1..]); |
3580 | /// } |
3581 | /// |
3582 | /// assert_eq!(slice, [4, 5, 3, 4, 5]); |
3583 | /// ``` |
3584 | /// |
3585 | /// [`clone_from_slice`]: slice::clone_from_slice |
3586 | /// [`split_at_mut`]: slice::split_at_mut |
3587 | #[doc (alias = "memcpy" )] |
3588 | #[stable (feature = "copy_from_slice" , since = "1.9.0" )] |
3589 | #[track_caller ] |
3590 | pub fn copy_from_slice(&mut self, src: &[T]) |
3591 | where |
3592 | T: Copy, |
3593 | { |
3594 | // The panic code path was put into a cold function to not bloat the |
3595 | // call site. |
3596 | #[inline (never)] |
3597 | #[cold ] |
3598 | #[track_caller ] |
3599 | fn len_mismatch_fail(dst_len: usize, src_len: usize) -> ! { |
3600 | panic!( |
3601 | "source slice length ( {}) does not match destination slice length ( {})" , |
3602 | src_len, dst_len, |
3603 | ); |
3604 | } |
3605 | |
3606 | if self.len() != src.len() { |
3607 | len_mismatch_fail(self.len(), src.len()); |
3608 | } |
3609 | |
3610 | // SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was |
3611 | // checked to have the same length. The slices cannot overlap because |
3612 | // mutable references are exclusive. |
3613 | unsafe { |
3614 | ptr::copy_nonoverlapping(src.as_ptr(), self.as_mut_ptr(), self.len()); |
3615 | } |
3616 | } |
3617 | |
3618 | /// Copies elements from one part of the slice to another part of itself, |
3619 | /// using a memmove. |
3620 | /// |
3621 | /// `src` is the range within `self` to copy from. `dest` is the starting |
3622 | /// index of the range within `self` to copy to, which will have the same |
3623 | /// length as `src`. The two ranges may overlap. The ends of the two ranges |
3624 | /// must be less than or equal to `self.len()`. |
3625 | /// |
3626 | /// # Panics |
3627 | /// |
3628 | /// This function will panic if either range exceeds the end of the slice, |
3629 | /// or if the end of `src` is before the start. |
3630 | /// |
3631 | /// # Examples |
3632 | /// |
3633 | /// Copying four bytes within a slice: |
3634 | /// |
3635 | /// ``` |
3636 | /// let mut bytes = *b"Hello, World!" ; |
3637 | /// |
3638 | /// bytes.copy_within(1..5, 8); |
3639 | /// |
3640 | /// assert_eq!(&bytes, b"Hello, Wello!" ); |
3641 | /// ``` |
3642 | #[stable (feature = "copy_within" , since = "1.37.0" )] |
3643 | #[track_caller ] |
3644 | pub fn copy_within<R: RangeBounds<usize>>(&mut self, src: R, dest: usize) |
3645 | where |
3646 | T: Copy, |
3647 | { |
3648 | let Range { start: src_start, end: src_end } = slice::range(src, ..self.len()); |
3649 | let count = src_end - src_start; |
3650 | assert!(dest <= self.len() - count, "dest is out of bounds" ); |
3651 | // SAFETY: the conditions for `ptr::copy` have all been checked above, |
3652 | // as have those for `ptr::add`. |
3653 | unsafe { |
3654 | // Derive both `src_ptr` and `dest_ptr` from the same loan |
3655 | let ptr = self.as_mut_ptr(); |
3656 | let src_ptr = ptr.add(src_start); |
3657 | let dest_ptr = ptr.add(dest); |
3658 | ptr::copy(src_ptr, dest_ptr, count); |
3659 | } |
3660 | } |
3661 | |
3662 | /// Swaps all elements in `self` with those in `other`. |
3663 | /// |
3664 | /// The length of `other` must be the same as `self`. |
3665 | /// |
3666 | /// # Panics |
3667 | /// |
3668 | /// This function will panic if the two slices have different lengths. |
3669 | /// |
3670 | /// # Example |
3671 | /// |
3672 | /// Swapping two elements across slices: |
3673 | /// |
3674 | /// ``` |
3675 | /// let mut slice1 = [0, 0]; |
3676 | /// let mut slice2 = [1, 2, 3, 4]; |
3677 | /// |
3678 | /// slice1.swap_with_slice(&mut slice2[2..]); |
3679 | /// |
3680 | /// assert_eq!(slice1, [3, 4]); |
3681 | /// assert_eq!(slice2, [1, 2, 0, 0]); |
3682 | /// ``` |
3683 | /// |
3684 | /// Rust enforces that there can only be one mutable reference to a |
3685 | /// particular piece of data in a particular scope. Because of this, |
3686 | /// attempting to use `swap_with_slice` on a single slice will result in |
3687 | /// a compile failure: |
3688 | /// |
3689 | /// ```compile_fail |
3690 | /// let mut slice = [1, 2, 3, 4, 5]; |
3691 | /// slice[..2].swap_with_slice(&mut slice[3..]); // compile fail! |
3692 | /// ``` |
3693 | /// |
3694 | /// To work around this, we can use [`split_at_mut`] to create two distinct |
3695 | /// mutable sub-slices from a slice: |
3696 | /// |
3697 | /// ``` |
3698 | /// let mut slice = [1, 2, 3, 4, 5]; |
3699 | /// |
3700 | /// { |
3701 | /// let (left, right) = slice.split_at_mut(2); |
3702 | /// left.swap_with_slice(&mut right[1..]); |
3703 | /// } |
3704 | /// |
3705 | /// assert_eq!(slice, [4, 5, 3, 1, 2]); |
3706 | /// ``` |
3707 | /// |
3708 | /// [`split_at_mut`]: slice::split_at_mut |
3709 | #[stable (feature = "swap_with_slice" , since = "1.27.0" )] |
3710 | #[track_caller ] |
3711 | pub fn swap_with_slice(&mut self, other: &mut [T]) { |
3712 | assert!(self.len() == other.len(), "destination and source slices have different lengths" ); |
3713 | // SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was |
3714 | // checked to have the same length. The slices cannot overlap because |
3715 | // mutable references are exclusive. |
3716 | unsafe { |
3717 | ptr::swap_nonoverlapping(self.as_mut_ptr(), other.as_mut_ptr(), self.len()); |
3718 | } |
3719 | } |
3720 | |
3721 | /// Function to calculate lengths of the middle and trailing slice for `align_to{,_mut}`. |
3722 | fn align_to_offsets<U>(&self) -> (usize, usize) { |
3723 | // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a |
3724 | // lowest number of `T`s. And how many `T`s we need for each such "multiple". |
3725 | // |
3726 | // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider |
3727 | // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in |
3728 | // place of every 3 Ts in the `rest` slice. A bit more complicated. |
3729 | // |
3730 | // Formula to calculate this is: |
3731 | // |
3732 | // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U> |
3733 | // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T> |
3734 | // |
3735 | // Expanded and simplified: |
3736 | // |
3737 | // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>) |
3738 | // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>) |
3739 | // |
3740 | // Luckily since all this is constant-evaluated... performance here matters not! |
3741 | const fn gcd(a: usize, b: usize) -> usize { |
3742 | if b == 0 { a } else { gcd(b, a % b) } |
3743 | } |
3744 | |
3745 | // Explicitly wrap the function call in a const block so it gets |
3746 | // constant-evaluated even in debug mode. |
3747 | let gcd: usize = const { gcd(mem::size_of::<T>(), mem::size_of::<U>()) }; |
3748 | let ts: usize = mem::size_of::<U>() / gcd; |
3749 | let us: usize = mem::size_of::<T>() / gcd; |
3750 | |
3751 | // Armed with this knowledge, we can find how many `U`s we can fit! |
3752 | let us_len = self.len() / ts * us; |
3753 | // And how many `T`s will be in the trailing slice! |
3754 | let ts_len = self.len() % ts; |
3755 | (us_len, ts_len) |
3756 | } |
3757 | |
3758 | /// Transmute the slice to a slice of another type, ensuring alignment of the types is |
3759 | /// maintained. |
3760 | /// |
3761 | /// This method splits the slice into three distinct slices: prefix, correctly aligned middle |
3762 | /// slice of a new type, and the suffix slice. How exactly the slice is split up is not |
3763 | /// specified; the middle part may be smaller than necessary. However, if this fails to return a |
3764 | /// maximal middle part, that is because code is running in a context where performance does not |
3765 | /// matter, such as a sanitizer attempting to find alignment bugs. Regular code running |
3766 | /// in a default (debug or release) execution *will* return a maximal middle part. |
3767 | /// |
3768 | /// This method has no purpose when either input element `T` or output element `U` are |
3769 | /// zero-sized and will return the original slice without splitting anything. |
3770 | /// |
3771 | /// # Safety |
3772 | /// |
3773 | /// This method is essentially a `transmute` with respect to the elements in the returned |
3774 | /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here. |
3775 | /// |
3776 | /// # Examples |
3777 | /// |
3778 | /// Basic usage: |
3779 | /// |
3780 | /// ``` |
3781 | /// unsafe { |
3782 | /// let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7]; |
3783 | /// let (prefix, shorts, suffix) = bytes.align_to::<u16>(); |
3784 | /// // less_efficient_algorithm_for_bytes(prefix); |
3785 | /// // more_efficient_algorithm_for_aligned_shorts(shorts); |
3786 | /// // less_efficient_algorithm_for_bytes(suffix); |
3787 | /// } |
3788 | /// ``` |
3789 | #[stable (feature = "slice_align_to" , since = "1.30.0" )] |
3790 | #[must_use ] |
3791 | pub unsafe fn align_to<U>(&self) -> (&[T], &[U], &[T]) { |
3792 | // Note that most of this function will be constant-evaluated, |
3793 | if U::IS_ZST || T::IS_ZST { |
3794 | // handle ZSTs specially, which is – don't handle them at all. |
3795 | return (self, &[], &[]); |
3796 | } |
3797 | |
3798 | // First, find at what point do we split between the first and 2nd slice. Easy with |
3799 | // ptr.align_offset. |
3800 | let ptr = self.as_ptr(); |
3801 | // SAFETY: See the `align_to_mut` method for the detailed safety comment. |
3802 | let offset = unsafe { crate::ptr::align_offset(ptr, mem::align_of::<U>()) }; |
3803 | if offset > self.len() { |
3804 | (self, &[], &[]) |
3805 | } else { |
3806 | let (left, rest) = self.split_at(offset); |
3807 | let (us_len, ts_len) = rest.align_to_offsets::<U>(); |
3808 | // Inform Miri that we want to consider the "middle" pointer to be suitably aligned. |
3809 | #[cfg (miri)] |
3810 | crate::intrinsics::miri_promise_symbolic_alignment( |
3811 | rest.as_ptr().cast(), |
3812 | mem::align_of::<U>(), |
3813 | ); |
3814 | // SAFETY: now `rest` is definitely aligned, so `from_raw_parts` below is okay, |
3815 | // since the caller guarantees that we can transmute `T` to `U` safely. |
3816 | unsafe { |
3817 | ( |
3818 | left, |
3819 | from_raw_parts(rest.as_ptr() as *const U, us_len), |
3820 | from_raw_parts(rest.as_ptr().add(rest.len() - ts_len), ts_len), |
3821 | ) |
3822 | } |
3823 | } |
3824 | } |
3825 | |
3826 | /// Transmute the mutable slice to a mutable slice of another type, ensuring alignment of the |
3827 | /// types is maintained. |
3828 | /// |
3829 | /// This method splits the slice into three distinct slices: prefix, correctly aligned middle |
3830 | /// slice of a new type, and the suffix slice. How exactly the slice is split up is not |
3831 | /// specified; the middle part may be smaller than necessary. However, if this fails to return a |
3832 | /// maximal middle part, that is because code is running in a context where performance does not |
3833 | /// matter, such as a sanitizer attempting to find alignment bugs. Regular code running |
3834 | /// in a default (debug or release) execution *will* return a maximal middle part. |
3835 | /// |
3836 | /// This method has no purpose when either input element `T` or output element `U` are |
3837 | /// zero-sized and will return the original slice without splitting anything. |
3838 | /// |
3839 | /// # Safety |
3840 | /// |
3841 | /// This method is essentially a `transmute` with respect to the elements in the returned |
3842 | /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here. |
3843 | /// |
3844 | /// # Examples |
3845 | /// |
3846 | /// Basic usage: |
3847 | /// |
3848 | /// ``` |
3849 | /// unsafe { |
3850 | /// let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7]; |
3851 | /// let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>(); |
3852 | /// // less_efficient_algorithm_for_bytes(prefix); |
3853 | /// // more_efficient_algorithm_for_aligned_shorts(shorts); |
3854 | /// // less_efficient_algorithm_for_bytes(suffix); |
3855 | /// } |
3856 | /// ``` |
3857 | #[stable (feature = "slice_align_to" , since = "1.30.0" )] |
3858 | #[must_use ] |
3859 | pub unsafe fn align_to_mut<U>(&mut self) -> (&mut [T], &mut [U], &mut [T]) { |
3860 | // Note that most of this function will be constant-evaluated, |
3861 | if U::IS_ZST || T::IS_ZST { |
3862 | // handle ZSTs specially, which is – don't handle them at all. |
3863 | return (self, &mut [], &mut []); |
3864 | } |
3865 | |
3866 | // First, find at what point do we split between the first and 2nd slice. Easy with |
3867 | // ptr.align_offset. |
3868 | let ptr = self.as_ptr(); |
3869 | // SAFETY: Here we are ensuring we will use aligned pointers for U for the |
3870 | // rest of the method. This is done by passing a pointer to &[T] with an |
3871 | // alignment targeted for U. |
3872 | // `crate::ptr::align_offset` is called with a correctly aligned and |
3873 | // valid pointer `ptr` (it comes from a reference to `self`) and with |
3874 | // a size that is a power of two (since it comes from the alignment for U), |
3875 | // satisfying its safety constraints. |
3876 | let offset = unsafe { crate::ptr::align_offset(ptr, mem::align_of::<U>()) }; |
3877 | if offset > self.len() { |
3878 | (self, &mut [], &mut []) |
3879 | } else { |
3880 | let (left, rest) = self.split_at_mut(offset); |
3881 | let (us_len, ts_len) = rest.align_to_offsets::<U>(); |
3882 | let rest_len = rest.len(); |
3883 | let mut_ptr = rest.as_mut_ptr(); |
3884 | // Inform Miri that we want to consider the "middle" pointer to be suitably aligned. |
3885 | #[cfg (miri)] |
3886 | crate::intrinsics::miri_promise_symbolic_alignment( |
3887 | mut_ptr.cast() as *const (), |
3888 | mem::align_of::<U>(), |
3889 | ); |
3890 | // We can't use `rest` again after this, that would invalidate its alias `mut_ptr`! |
3891 | // SAFETY: see comments for `align_to`. |
3892 | unsafe { |
3893 | ( |
3894 | left, |
3895 | from_raw_parts_mut(mut_ptr as *mut U, us_len), |
3896 | from_raw_parts_mut(mut_ptr.add(rest_len - ts_len), ts_len), |
3897 | ) |
3898 | } |
3899 | } |
3900 | } |
3901 | |
3902 | /// Split a slice into a prefix, a middle of aligned SIMD types, and a suffix. |
3903 | /// |
3904 | /// This is a safe wrapper around [`slice::align_to`], so has the same weak |
3905 | /// postconditions as that method. You're only assured that |
3906 | /// `self.len() == prefix.len() + middle.len() * LANES + suffix.len()`. |
3907 | /// |
3908 | /// Notably, all of the following are possible: |
3909 | /// - `prefix.len() >= LANES`. |
3910 | /// - `middle.is_empty()` despite `self.len() >= 3 * LANES`. |
3911 | /// - `suffix.len() >= LANES`. |
3912 | /// |
3913 | /// That said, this is a safe method, so if you're only writing safe code, |
3914 | /// then this can at most cause incorrect logic, not unsoundness. |
3915 | /// |
3916 | /// # Panics |
3917 | /// |
3918 | /// This will panic if the size of the SIMD type is different from |
3919 | /// `LANES` times that of the scalar. |
3920 | /// |
3921 | /// At the time of writing, the trait restrictions on `Simd<T, LANES>` keeps |
3922 | /// that from ever happening, as only power-of-two numbers of lanes are |
3923 | /// supported. It's possible that, in the future, those restrictions might |
3924 | /// be lifted in a way that would make it possible to see panics from this |
3925 | /// method for something like `LANES == 3`. |
3926 | /// |
3927 | /// # Examples |
3928 | /// |
3929 | /// ``` |
3930 | /// #![feature(portable_simd)] |
3931 | /// use core::simd::prelude::*; |
3932 | /// |
3933 | /// let short = &[1, 2, 3]; |
3934 | /// let (prefix, middle, suffix) = short.as_simd::<4>(); |
3935 | /// assert_eq!(middle, []); // Not enough elements for anything in the middle |
3936 | /// |
3937 | /// // They might be split in any possible way between prefix and suffix |
3938 | /// let it = prefix.iter().chain(suffix).copied(); |
3939 | /// assert_eq!(it.collect::<Vec<_>>(), vec![1, 2, 3]); |
3940 | /// |
3941 | /// fn basic_simd_sum(x: &[f32]) -> f32 { |
3942 | /// use std::ops::Add; |
3943 | /// let (prefix, middle, suffix) = x.as_simd(); |
3944 | /// let sums = f32x4::from_array([ |
3945 | /// prefix.iter().copied().sum(), |
3946 | /// 0.0, |
3947 | /// 0.0, |
3948 | /// suffix.iter().copied().sum(), |
3949 | /// ]); |
3950 | /// let sums = middle.iter().copied().fold(sums, f32x4::add); |
3951 | /// sums.reduce_sum() |
3952 | /// } |
3953 | /// |
3954 | /// let numbers: Vec<f32> = (1..101).map(|x| x as _).collect(); |
3955 | /// assert_eq!(basic_simd_sum(&numbers[1..99]), 4949.0); |
3956 | /// ``` |
3957 | #[unstable (feature = "portable_simd" , issue = "86656" )] |
3958 | #[must_use ] |
3959 | pub fn as_simd<const LANES: usize>(&self) -> (&[T], &[Simd<T, LANES>], &[T]) |
3960 | where |
3961 | Simd<T, LANES>: AsRef<[T; LANES]>, |
3962 | T: simd::SimdElement, |
3963 | simd::LaneCount<LANES>: simd::SupportedLaneCount, |
3964 | { |
3965 | // These are expected to always match, as vector types are laid out like |
3966 | // arrays per <https://llvm.org/docs/LangRef.html#vector-type>, but we |
3967 | // might as well double-check since it'll optimize away anyhow. |
3968 | assert_eq!(mem::size_of::<Simd<T, LANES>>(), mem::size_of::<[T; LANES]>()); |
3969 | |
3970 | // SAFETY: The simd types have the same layout as arrays, just with |
3971 | // potentially-higher alignment, so the de-facto transmutes are sound. |
3972 | unsafe { self.align_to() } |
3973 | } |
3974 | |
3975 | /// Split a mutable slice into a mutable prefix, a middle of aligned SIMD types, |
3976 | /// and a mutable suffix. |
3977 | /// |
3978 | /// This is a safe wrapper around [`slice::align_to_mut`], so has the same weak |
3979 | /// postconditions as that method. You're only assured that |
3980 | /// `self.len() == prefix.len() + middle.len() * LANES + suffix.len()`. |
3981 | /// |
3982 | /// Notably, all of the following are possible: |
3983 | /// - `prefix.len() >= LANES`. |
3984 | /// - `middle.is_empty()` despite `self.len() >= 3 * LANES`. |
3985 | /// - `suffix.len() >= LANES`. |
3986 | /// |
3987 | /// That said, this is a safe method, so if you're only writing safe code, |
3988 | /// then this can at most cause incorrect logic, not unsoundness. |
3989 | /// |
3990 | /// This is the mutable version of [`slice::as_simd`]; see that for examples. |
3991 | /// |
3992 | /// # Panics |
3993 | /// |
3994 | /// This will panic if the size of the SIMD type is different from |
3995 | /// `LANES` times that of the scalar. |
3996 | /// |
3997 | /// At the time of writing, the trait restrictions on `Simd<T, LANES>` keeps |
3998 | /// that from ever happening, as only power-of-two numbers of lanes are |
3999 | /// supported. It's possible that, in the future, those restrictions might |
4000 | /// be lifted in a way that would make it possible to see panics from this |
4001 | /// method for something like `LANES == 3`. |
4002 | #[unstable (feature = "portable_simd" , issue = "86656" )] |
4003 | #[must_use ] |
4004 | pub fn as_simd_mut<const LANES: usize>(&mut self) -> (&mut [T], &mut [Simd<T, LANES>], &mut [T]) |
4005 | where |
4006 | Simd<T, LANES>: AsMut<[T; LANES]>, |
4007 | T: simd::SimdElement, |
4008 | simd::LaneCount<LANES>: simd::SupportedLaneCount, |
4009 | { |
4010 | // These are expected to always match, as vector types are laid out like |
4011 | // arrays per <https://llvm.org/docs/LangRef.html#vector-type>, but we |
4012 | // might as well double-check since it'll optimize away anyhow. |
4013 | assert_eq!(mem::size_of::<Simd<T, LANES>>(), mem::size_of::<[T; LANES]>()); |
4014 | |
4015 | // SAFETY: The simd types have the same layout as arrays, just with |
4016 | // potentially-higher alignment, so the de-facto transmutes are sound. |
4017 | unsafe { self.align_to_mut() } |
4018 | } |
4019 | |
4020 | /// Checks if the elements of this slice are sorted. |
4021 | /// |
4022 | /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the |
4023 | /// slice yields exactly zero or one element, `true` is returned. |
4024 | /// |
4025 | /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition |
4026 | /// implies that this function returns `false` if any two consecutive items are not |
4027 | /// comparable. |
4028 | /// |
4029 | /// # Examples |
4030 | /// |
4031 | /// ``` |
4032 | /// #![feature(is_sorted)] |
4033 | /// let empty: [i32; 0] = []; |
4034 | /// |
4035 | /// assert!([1, 2, 2, 9].is_sorted()); |
4036 | /// assert!(![1, 3, 2, 4].is_sorted()); |
4037 | /// assert!([0].is_sorted()); |
4038 | /// assert!(empty.is_sorted()); |
4039 | /// assert!(![0.0, 1.0, f32::NAN].is_sorted()); |
4040 | /// ``` |
4041 | #[inline ] |
4042 | #[unstable (feature = "is_sorted" , reason = "new API" , issue = "53485" )] |
4043 | #[must_use ] |
4044 | pub fn is_sorted(&self) -> bool |
4045 | where |
4046 | T: PartialOrd, |
4047 | { |
4048 | self.is_sorted_by(|a, b| a <= b) |
4049 | } |
4050 | |
4051 | /// Checks if the elements of this slice are sorted using the given comparator function. |
4052 | /// |
4053 | /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare` |
4054 | /// function to determine whether two elements are to be considered in sorted order. |
4055 | /// |
4056 | /// # Examples |
4057 | /// |
4058 | /// ``` |
4059 | /// #![feature(is_sorted)] |
4060 | /// |
4061 | /// assert!([1, 2, 2, 9].is_sorted_by(|a, b| a <= b)); |
4062 | /// assert!(![1, 2, 2, 9].is_sorted_by(|a, b| a < b)); |
4063 | /// |
4064 | /// assert!([0].is_sorted_by(|a, b| true)); |
4065 | /// assert!([0].is_sorted_by(|a, b| false)); |
4066 | /// |
4067 | /// let empty: [i32; 0] = []; |
4068 | /// assert!(empty.is_sorted_by(|a, b| false)); |
4069 | /// assert!(empty.is_sorted_by(|a, b| true)); |
4070 | /// ``` |
4071 | #[unstable (feature = "is_sorted" , reason = "new API" , issue = "53485" )] |
4072 | #[must_use ] |
4073 | pub fn is_sorted_by<'a, F>(&'a self, mut compare: F) -> bool |
4074 | where |
4075 | F: FnMut(&'a T, &'a T) -> bool, |
4076 | { |
4077 | self.array_windows().all(|[a, b]| compare(a, b)) |
4078 | } |
4079 | |
4080 | /// Checks if the elements of this slice are sorted using the given key extraction function. |
4081 | /// |
4082 | /// Instead of comparing the slice's elements directly, this function compares the keys of the |
4083 | /// elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see its |
4084 | /// documentation for more information. |
4085 | /// |
4086 | /// [`is_sorted`]: slice::is_sorted |
4087 | /// |
4088 | /// # Examples |
4089 | /// |
4090 | /// ``` |
4091 | /// #![feature(is_sorted)] |
4092 | /// |
4093 | /// assert!(["c" , "bb" , "aaa" ].is_sorted_by_key(|s| s.len())); |
4094 | /// assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs())); |
4095 | /// ``` |
4096 | #[inline ] |
4097 | #[unstable (feature = "is_sorted" , reason = "new API" , issue = "53485" )] |
4098 | #[must_use ] |
4099 | pub fn is_sorted_by_key<'a, F, K>(&'a self, f: F) -> bool |
4100 | where |
4101 | F: FnMut(&'a T) -> K, |
4102 | K: PartialOrd, |
4103 | { |
4104 | self.iter().is_sorted_by_key(f) |
4105 | } |
4106 | |
4107 | /// Returns the index of the partition point according to the given predicate |
4108 | /// (the index of the first element of the second partition). |
4109 | /// |
4110 | /// The slice is assumed to be partitioned according to the given predicate. |
4111 | /// This means that all elements for which the predicate returns true are at the start of the slice |
4112 | /// and all elements for which the predicate returns false are at the end. |
4113 | /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0` |
4114 | /// (all odd numbers are at the start, all even at the end). |
4115 | /// |
4116 | /// If this slice is not partitioned, the returned result is unspecified and meaningless, |
4117 | /// as this method performs a kind of binary search. |
4118 | /// |
4119 | /// See also [`binary_search`], [`binary_search_by`], and [`binary_search_by_key`]. |
4120 | /// |
4121 | /// [`binary_search`]: slice::binary_search |
4122 | /// [`binary_search_by`]: slice::binary_search_by |
4123 | /// [`binary_search_by_key`]: slice::binary_search_by_key |
4124 | /// |
4125 | /// # Examples |
4126 | /// |
4127 | /// ``` |
4128 | /// let v = [1, 2, 3, 3, 5, 6, 7]; |
4129 | /// let i = v.partition_point(|&x| x < 5); |
4130 | /// |
4131 | /// assert_eq!(i, 4); |
4132 | /// assert!(v[..i].iter().all(|&x| x < 5)); |
4133 | /// assert!(v[i..].iter().all(|&x| !(x < 5))); |
4134 | /// ``` |
4135 | /// |
4136 | /// If all elements of the slice match the predicate, including if the slice |
4137 | /// is empty, then the length of the slice will be returned: |
4138 | /// |
4139 | /// ``` |
4140 | /// let a = [2, 4, 8]; |
4141 | /// assert_eq!(a.partition_point(|x| x < &100), a.len()); |
4142 | /// let a: [i32; 0] = []; |
4143 | /// assert_eq!(a.partition_point(|x| x < &100), 0); |
4144 | /// ``` |
4145 | /// |
4146 | /// If you want to insert an item to a sorted vector, while maintaining |
4147 | /// sort order: |
4148 | /// |
4149 | /// ``` |
4150 | /// let mut s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; |
4151 | /// let num = 42; |
4152 | /// let idx = s.partition_point(|&x| x < num); |
4153 | /// s.insert(idx, num); |
4154 | /// assert_eq!(s, [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]); |
4155 | /// ``` |
4156 | #[stable (feature = "partition_point" , since = "1.52.0" )] |
4157 | #[must_use ] |
4158 | pub fn partition_point<P>(&self, mut pred: P) -> usize |
4159 | where |
4160 | P: FnMut(&T) -> bool, |
4161 | { |
4162 | self.binary_search_by(|x| if pred(x) { Less } else { Greater }).unwrap_or_else(|i| i) |
4163 | } |
4164 | |
4165 | /// Removes the subslice corresponding to the given range |
4166 | /// and returns a reference to it. |
4167 | /// |
4168 | /// Returns `None` and does not modify the slice if the given |
4169 | /// range is out of bounds. |
4170 | /// |
4171 | /// Note that this method only accepts one-sided ranges such as |
4172 | /// `2..` or `..6`, but not `2..6`. |
4173 | /// |
4174 | /// # Examples |
4175 | /// |
4176 | /// Taking the first three elements of a slice: |
4177 | /// |
4178 | /// ``` |
4179 | /// #![feature(slice_take)] |
4180 | /// |
4181 | /// let mut slice: &[_] = &['a' , 'b' , 'c' , 'd' ]; |
4182 | /// let mut first_three = slice.take(..3).unwrap(); |
4183 | /// |
4184 | /// assert_eq!(slice, &['d' ]); |
4185 | /// assert_eq!(first_three, &['a' , 'b' , 'c' ]); |
4186 | /// ``` |
4187 | /// |
4188 | /// Taking the last two elements of a slice: |
4189 | /// |
4190 | /// ``` |
4191 | /// #![feature(slice_take)] |
4192 | /// |
4193 | /// let mut slice: &[_] = &['a' , 'b' , 'c' , 'd' ]; |
4194 | /// let mut tail = slice.take(2..).unwrap(); |
4195 | /// |
4196 | /// assert_eq!(slice, &['a' , 'b' ]); |
4197 | /// assert_eq!(tail, &['c' , 'd' ]); |
4198 | /// ``` |
4199 | /// |
4200 | /// Getting `None` when `range` is out of bounds: |
4201 | /// |
4202 | /// ``` |
4203 | /// #![feature(slice_take)] |
4204 | /// |
4205 | /// let mut slice: &[_] = &['a' , 'b' , 'c' , 'd' ]; |
4206 | /// |
4207 | /// assert_eq!(None, slice.take(5..)); |
4208 | /// assert_eq!(None, slice.take(..5)); |
4209 | /// assert_eq!(None, slice.take(..=4)); |
4210 | /// let expected: &[char] = &['a' , 'b' , 'c' , 'd' ]; |
4211 | /// assert_eq!(Some(expected), slice.take(..4)); |
4212 | /// ``` |
4213 | #[inline ] |
4214 | #[must_use = "method does not modify the slice if the range is out of bounds" ] |
4215 | #[unstable (feature = "slice_take" , issue = "62280" )] |
4216 | pub fn take<'a, R: OneSidedRange<usize>>(self: &mut &'a Self, range: R) -> Option<&'a Self> { |
4217 | let (direction, split_index) = split_point_of(range)?; |
4218 | if split_index > self.len() { |
4219 | return None; |
4220 | } |
4221 | let (front, back) = self.split_at(split_index); |
4222 | match direction { |
4223 | Direction::Front => { |
4224 | *self = back; |
4225 | Some(front) |
4226 | } |
4227 | Direction::Back => { |
4228 | *self = front; |
4229 | Some(back) |
4230 | } |
4231 | } |
4232 | } |
4233 | |
4234 | /// Removes the subslice corresponding to the given range |
4235 | /// and returns a mutable reference to it. |
4236 | /// |
4237 | /// Returns `None` and does not modify the slice if the given |
4238 | /// range is out of bounds. |
4239 | /// |
4240 | /// Note that this method only accepts one-sided ranges such as |
4241 | /// `2..` or `..6`, but not `2..6`. |
4242 | /// |
4243 | /// # Examples |
4244 | /// |
4245 | /// Taking the first three elements of a slice: |
4246 | /// |
4247 | /// ``` |
4248 | /// #![feature(slice_take)] |
4249 | /// |
4250 | /// let mut slice: &mut [_] = &mut ['a' , 'b' , 'c' , 'd' ]; |
4251 | /// let mut first_three = slice.take_mut(..3).unwrap(); |
4252 | /// |
4253 | /// assert_eq!(slice, &mut ['d' ]); |
4254 | /// assert_eq!(first_three, &mut ['a' , 'b' , 'c' ]); |
4255 | /// ``` |
4256 | /// |
4257 | /// Taking the last two elements of a slice: |
4258 | /// |
4259 | /// ``` |
4260 | /// #![feature(slice_take)] |
4261 | /// |
4262 | /// let mut slice: &mut [_] = &mut ['a' , 'b' , 'c' , 'd' ]; |
4263 | /// let mut tail = slice.take_mut(2..).unwrap(); |
4264 | /// |
4265 | /// assert_eq!(slice, &mut ['a' , 'b' ]); |
4266 | /// assert_eq!(tail, &mut ['c' , 'd' ]); |
4267 | /// ``` |
4268 | /// |
4269 | /// Getting `None` when `range` is out of bounds: |
4270 | /// |
4271 | /// ``` |
4272 | /// #![feature(slice_take)] |
4273 | /// |
4274 | /// let mut slice: &mut [_] = &mut ['a' , 'b' , 'c' , 'd' ]; |
4275 | /// |
4276 | /// assert_eq!(None, slice.take_mut(5..)); |
4277 | /// assert_eq!(None, slice.take_mut(..5)); |
4278 | /// assert_eq!(None, slice.take_mut(..=4)); |
4279 | /// let expected: &mut [_] = &mut ['a' , 'b' , 'c' , 'd' ]; |
4280 | /// assert_eq!(Some(expected), slice.take_mut(..4)); |
4281 | /// ``` |
4282 | #[inline ] |
4283 | #[must_use = "method does not modify the slice if the range is out of bounds" ] |
4284 | #[unstable (feature = "slice_take" , issue = "62280" )] |
4285 | pub fn take_mut<'a, R: OneSidedRange<usize>>( |
4286 | self: &mut &'a mut Self, |
4287 | range: R, |
4288 | ) -> Option<&'a mut Self> { |
4289 | let (direction, split_index) = split_point_of(range)?; |
4290 | if split_index > self.len() { |
4291 | return None; |
4292 | } |
4293 | let (front, back) = mem::take(self).split_at_mut(split_index); |
4294 | match direction { |
4295 | Direction::Front => { |
4296 | *self = back; |
4297 | Some(front) |
4298 | } |
4299 | Direction::Back => { |
4300 | *self = front; |
4301 | Some(back) |
4302 | } |
4303 | } |
4304 | } |
4305 | |
4306 | /// Removes the first element of the slice and returns a reference |
4307 | /// to it. |
4308 | /// |
4309 | /// Returns `None` if the slice is empty. |
4310 | /// |
4311 | /// # Examples |
4312 | /// |
4313 | /// ``` |
4314 | /// #![feature(slice_take)] |
4315 | /// |
4316 | /// let mut slice: &[_] = &['a' , 'b' , 'c' ]; |
4317 | /// let first = slice.take_first().unwrap(); |
4318 | /// |
4319 | /// assert_eq!(slice, &['b' , 'c' ]); |
4320 | /// assert_eq!(first, &'a' ); |
4321 | /// ``` |
4322 | #[inline ] |
4323 | #[unstable (feature = "slice_take" , issue = "62280" )] |
4324 | pub fn take_first<'a>(self: &mut &'a Self) -> Option<&'a T> { |
4325 | let (first, rem) = self.split_first()?; |
4326 | *self = rem; |
4327 | Some(first) |
4328 | } |
4329 | |
4330 | /// Removes the first element of the slice and returns a mutable |
4331 | /// reference to it. |
4332 | /// |
4333 | /// Returns `None` if the slice is empty. |
4334 | /// |
4335 | /// # Examples |
4336 | /// |
4337 | /// ``` |
4338 | /// #![feature(slice_take)] |
4339 | /// |
4340 | /// let mut slice: &mut [_] = &mut ['a' , 'b' , 'c' ]; |
4341 | /// let first = slice.take_first_mut().unwrap(); |
4342 | /// *first = 'd' ; |
4343 | /// |
4344 | /// assert_eq!(slice, &['b' , 'c' ]); |
4345 | /// assert_eq!(first, &'d' ); |
4346 | /// ``` |
4347 | #[inline ] |
4348 | #[unstable (feature = "slice_take" , issue = "62280" )] |
4349 | pub fn take_first_mut<'a>(self: &mut &'a mut Self) -> Option<&'a mut T> { |
4350 | let (first, rem) = mem::take(self).split_first_mut()?; |
4351 | *self = rem; |
4352 | Some(first) |
4353 | } |
4354 | |
4355 | /// Removes the last element of the slice and returns a reference |
4356 | /// to it. |
4357 | /// |
4358 | /// Returns `None` if the slice is empty. |
4359 | /// |
4360 | /// # Examples |
4361 | /// |
4362 | /// ``` |
4363 | /// #![feature(slice_take)] |
4364 | /// |
4365 | /// let mut slice: &[_] = &['a' , 'b' , 'c' ]; |
4366 | /// let last = slice.take_last().unwrap(); |
4367 | /// |
4368 | /// assert_eq!(slice, &['a' , 'b' ]); |
4369 | /// assert_eq!(last, &'c' ); |
4370 | /// ``` |
4371 | #[inline ] |
4372 | #[unstable (feature = "slice_take" , issue = "62280" )] |
4373 | pub fn take_last<'a>(self: &mut &'a Self) -> Option<&'a T> { |
4374 | let (last, rem) = self.split_last()?; |
4375 | *self = rem; |
4376 | Some(last) |
4377 | } |
4378 | |
4379 | /// Removes the last element of the slice and returns a mutable |
4380 | /// reference to it. |
4381 | /// |
4382 | /// Returns `None` if the slice is empty. |
4383 | /// |
4384 | /// # Examples |
4385 | /// |
4386 | /// ``` |
4387 | /// #![feature(slice_take)] |
4388 | /// |
4389 | /// let mut slice: &mut [_] = &mut ['a' , 'b' , 'c' ]; |
4390 | /// let last = slice.take_last_mut().unwrap(); |
4391 | /// *last = 'd' ; |
4392 | /// |
4393 | /// assert_eq!(slice, &['a' , 'b' ]); |
4394 | /// assert_eq!(last, &'d' ); |
4395 | /// ``` |
4396 | #[inline ] |
4397 | #[unstable (feature = "slice_take" , issue = "62280" )] |
4398 | pub fn take_last_mut<'a>(self: &mut &'a mut Self) -> Option<&'a mut T> { |
4399 | let (last, rem) = mem::take(self).split_last_mut()?; |
4400 | *self = rem; |
4401 | Some(last) |
4402 | } |
4403 | |
4404 | /// Returns mutable references to many indices at once, without doing any checks. |
4405 | /// |
4406 | /// For a safe alternative see [`get_many_mut`]. |
4407 | /// |
4408 | /// # Safety |
4409 | /// |
4410 | /// Calling this method with overlapping or out-of-bounds indices is *[undefined behavior]* |
4411 | /// even if the resulting references are not used. |
4412 | /// |
4413 | /// # Examples |
4414 | /// |
4415 | /// ``` |
4416 | /// #![feature(get_many_mut)] |
4417 | /// |
4418 | /// let x = &mut [1, 2, 4]; |
4419 | /// |
4420 | /// unsafe { |
4421 | /// let [a, b] = x.get_many_unchecked_mut([0, 2]); |
4422 | /// *a *= 10; |
4423 | /// *b *= 100; |
4424 | /// } |
4425 | /// assert_eq!(x, &[10, 2, 400]); |
4426 | /// ``` |
4427 | /// |
4428 | /// [`get_many_mut`]: slice::get_many_mut |
4429 | /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html |
4430 | #[unstable (feature = "get_many_mut" , issue = "104642" )] |
4431 | #[inline ] |
4432 | pub unsafe fn get_many_unchecked_mut<const N: usize>( |
4433 | &mut self, |
4434 | indices: [usize; N], |
4435 | ) -> [&mut T; N] { |
4436 | // NB: This implementation is written as it is because any variation of |
4437 | // `indices.map(|i| self.get_unchecked_mut(i))` would make miri unhappy, |
4438 | // or generate worse code otherwise. This is also why we need to go |
4439 | // through a raw pointer here. |
4440 | let slice: *mut [T] = self; |
4441 | let mut arr: mem::MaybeUninit<[&mut T; N]> = mem::MaybeUninit::uninit(); |
4442 | let arr_ptr = arr.as_mut_ptr(); |
4443 | |
4444 | // SAFETY: We expect `indices` to contain disjunct values that are |
4445 | // in bounds of `self`. |
4446 | unsafe { |
4447 | for i in 0..N { |
4448 | let idx = *indices.get_unchecked(i); |
4449 | *(*arr_ptr).get_unchecked_mut(i) = &mut *slice.get_unchecked_mut(idx); |
4450 | } |
4451 | arr.assume_init() |
4452 | } |
4453 | } |
4454 | |
4455 | /// Returns mutable references to many indices at once. |
4456 | /// |
4457 | /// Returns an error if any index is out-of-bounds, or if the same index was |
4458 | /// passed more than once. |
4459 | /// |
4460 | /// # Examples |
4461 | /// |
4462 | /// ``` |
4463 | /// #![feature(get_many_mut)] |
4464 | /// |
4465 | /// let v = &mut [1, 2, 3]; |
4466 | /// if let Ok([a, b]) = v.get_many_mut([0, 2]) { |
4467 | /// *a = 413; |
4468 | /// *b = 612; |
4469 | /// } |
4470 | /// assert_eq!(v, &[413, 2, 612]); |
4471 | /// ``` |
4472 | #[unstable (feature = "get_many_mut" , issue = "104642" )] |
4473 | #[inline ] |
4474 | pub fn get_many_mut<const N: usize>( |
4475 | &mut self, |
4476 | indices: [usize; N], |
4477 | ) -> Result<[&mut T; N], GetManyMutError<N>> { |
4478 | if !get_many_check_valid(&indices, self.len()) { |
4479 | return Err(GetManyMutError { _private: () }); |
4480 | } |
4481 | // SAFETY: The `get_many_check_valid()` call checked that all indices |
4482 | // are disjunct and in bounds. |
4483 | unsafe { Ok(self.get_many_unchecked_mut(indices)) } |
4484 | } |
4485 | } |
4486 | |
4487 | impl<T, const N: usize> [[T; N]] { |
4488 | /// Takes a `&[[T; N]]`, and flattens it to a `&[T]`. |
4489 | /// |
4490 | /// # Panics |
4491 | /// |
4492 | /// This panics if the length of the resulting slice would overflow a `usize`. |
4493 | /// |
4494 | /// This is only possible when flattening a slice of arrays of zero-sized |
4495 | /// types, and thus tends to be irrelevant in practice. If |
4496 | /// `size_of::<T>() > 0`, this will never panic. |
4497 | /// |
4498 | /// # Examples |
4499 | /// |
4500 | /// ``` |
4501 | /// #![feature(slice_flatten)] |
4502 | /// |
4503 | /// assert_eq!([[1, 2, 3], [4, 5, 6]].flatten(), &[1, 2, 3, 4, 5, 6]); |
4504 | /// |
4505 | /// assert_eq!( |
4506 | /// [[1, 2, 3], [4, 5, 6]].flatten(), |
4507 | /// [[1, 2], [3, 4], [5, 6]].flatten(), |
4508 | /// ); |
4509 | /// |
4510 | /// let slice_of_empty_arrays: &[[i32; 0]] = &[[], [], [], [], []]; |
4511 | /// assert!(slice_of_empty_arrays.flatten().is_empty()); |
4512 | /// |
4513 | /// let empty_slice_of_arrays: &[[u32; 10]] = &[]; |
4514 | /// assert!(empty_slice_of_arrays.flatten().is_empty()); |
4515 | /// ``` |
4516 | #[unstable (feature = "slice_flatten" , issue = "95629" )] |
4517 | pub const fn flatten(&self) -> &[T] { |
4518 | let len = if T::IS_ZST { |
4519 | self.len().checked_mul(N).expect("slice len overflow" ) |
4520 | } else { |
4521 | // SAFETY: `self.len() * N` cannot overflow because `self` is |
4522 | // already in the address space. |
4523 | unsafe { self.len().unchecked_mul(N) } |
4524 | }; |
4525 | // SAFETY: `[T]` is layout-identical to `[T; N]` |
4526 | unsafe { from_raw_parts(self.as_ptr().cast(), len) } |
4527 | } |
4528 | |
4529 | /// Takes a `&mut [[T; N]]`, and flattens it to a `&mut [T]`. |
4530 | /// |
4531 | /// # Panics |
4532 | /// |
4533 | /// This panics if the length of the resulting slice would overflow a `usize`. |
4534 | /// |
4535 | /// This is only possible when flattening a slice of arrays of zero-sized |
4536 | /// types, and thus tends to be irrelevant in practice. If |
4537 | /// `size_of::<T>() > 0`, this will never panic. |
4538 | /// |
4539 | /// # Examples |
4540 | /// |
4541 | /// ``` |
4542 | /// #![feature(slice_flatten)] |
4543 | /// |
4544 | /// fn add_5_to_all(slice: &mut [i32]) { |
4545 | /// for i in slice { |
4546 | /// *i += 5; |
4547 | /// } |
4548 | /// } |
4549 | /// |
4550 | /// let mut array = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]; |
4551 | /// add_5_to_all(array.flatten_mut()); |
4552 | /// assert_eq!(array, [[6, 7, 8], [9, 10, 11], [12, 13, 14]]); |
4553 | /// ``` |
4554 | #[unstable (feature = "slice_flatten" , issue = "95629" )] |
4555 | pub fn flatten_mut(&mut self) -> &mut [T] { |
4556 | let len = if T::IS_ZST { |
4557 | self.len().checked_mul(N).expect("slice len overflow" ) |
4558 | } else { |
4559 | // SAFETY: `self.len() * N` cannot overflow because `self` is |
4560 | // already in the address space. |
4561 | unsafe { self.len().unchecked_mul(N) } |
4562 | }; |
4563 | // SAFETY: `[T]` is layout-identical to `[T; N]` |
4564 | unsafe { from_raw_parts_mut(self.as_mut_ptr().cast(), len) } |
4565 | } |
4566 | } |
4567 | |
4568 | #[cfg (not(test))] |
4569 | impl [f32] { |
4570 | /// Sorts the slice of floats. |
4571 | /// |
4572 | /// This sort is in-place (i.e. does not allocate), *O*(*n* \* log(*n*)) worst-case, and uses |
4573 | /// the ordering defined by [`f32::total_cmp`]. |
4574 | /// |
4575 | /// # Current implementation |
4576 | /// |
4577 | /// This uses the same sorting algorithm as [`sort_unstable_by`](slice::sort_unstable_by). |
4578 | /// |
4579 | /// # Examples |
4580 | /// |
4581 | /// ``` |
4582 | /// #![feature(sort_floats)] |
4583 | /// let mut v = [2.6, -5e-8, f32::NAN, 8.29, f32::INFINITY, -1.0, 0.0, -f32::INFINITY, -0.0]; |
4584 | /// |
4585 | /// v.sort_floats(); |
4586 | /// let sorted = [-f32::INFINITY, -1.0, -5e-8, -0.0, 0.0, 2.6, 8.29, f32::INFINITY, f32::NAN]; |
4587 | /// assert_eq!(&v[..8], &sorted[..8]); |
4588 | /// assert!(v[8].is_nan()); |
4589 | /// ``` |
4590 | #[unstable (feature = "sort_floats" , issue = "93396" )] |
4591 | #[inline ] |
4592 | pub fn sort_floats(&mut self) { |
4593 | self.sort_unstable_by(f32::total_cmp); |
4594 | } |
4595 | } |
4596 | |
4597 | #[cfg (not(test))] |
4598 | impl [f64] { |
4599 | /// Sorts the slice of floats. |
4600 | /// |
4601 | /// This sort is in-place (i.e. does not allocate), *O*(*n* \* log(*n*)) worst-case, and uses |
4602 | /// the ordering defined by [`f64::total_cmp`]. |
4603 | /// |
4604 | /// # Current implementation |
4605 | /// |
4606 | /// This uses the same sorting algorithm as [`sort_unstable_by`](slice::sort_unstable_by). |
4607 | /// |
4608 | /// # Examples |
4609 | /// |
4610 | /// ``` |
4611 | /// #![feature(sort_floats)] |
4612 | /// let mut v = [2.6, -5e-8, f64::NAN, 8.29, f64::INFINITY, -1.0, 0.0, -f64::INFINITY, -0.0]; |
4613 | /// |
4614 | /// v.sort_floats(); |
4615 | /// let sorted = [-f64::INFINITY, -1.0, -5e-8, -0.0, 0.0, 2.6, 8.29, f64::INFINITY, f64::NAN]; |
4616 | /// assert_eq!(&v[..8], &sorted[..8]); |
4617 | /// assert!(v[8].is_nan()); |
4618 | /// ``` |
4619 | #[unstable (feature = "sort_floats" , issue = "93396" )] |
4620 | #[inline ] |
4621 | pub fn sort_floats(&mut self) { |
4622 | self.sort_unstable_by(f64::total_cmp); |
4623 | } |
4624 | } |
4625 | |
4626 | trait CloneFromSpec<T> { |
4627 | fn spec_clone_from(&mut self, src: &[T]); |
4628 | } |
4629 | |
4630 | impl<T> CloneFromSpec<T> for [T] |
4631 | where |
4632 | T: Clone, |
4633 | { |
4634 | #[track_caller ] |
4635 | default fn spec_clone_from(&mut self, src: &[T]) { |
4636 | assert!(self.len() == src.len(), "destination and source slices have different lengths" ); |
4637 | // NOTE: We need to explicitly slice them to the same length |
4638 | // to make it easier for the optimizer to elide bounds checking. |
4639 | // But since it can't be relied on we also have an explicit specialization for T: Copy. |
4640 | let len: usize = self.len(); |
4641 | let src: &[T] = &src[..len]; |
4642 | for i: usize in 0..len { |
4643 | self[i].clone_from(&src[i]); |
4644 | } |
4645 | } |
4646 | } |
4647 | |
4648 | impl<T> CloneFromSpec<T> for [T] |
4649 | where |
4650 | T: Copy, |
4651 | { |
4652 | #[track_caller ] |
4653 | fn spec_clone_from(&mut self, src: &[T]) { |
4654 | self.copy_from_slice(src); |
4655 | } |
4656 | } |
4657 | |
4658 | #[stable (feature = "rust1" , since = "1.0.0" )] |
4659 | impl<T> Default for &[T] { |
4660 | /// Creates an empty slice. |
4661 | fn default() -> Self { |
4662 | &[] |
4663 | } |
4664 | } |
4665 | |
4666 | #[stable (feature = "mut_slice_default" , since = "1.5.0" )] |
4667 | impl<T> Default for &mut [T] { |
4668 | /// Creates a mutable empty slice. |
4669 | fn default() -> Self { |
4670 | &mut [] |
4671 | } |
4672 | } |
4673 | |
4674 | #[unstable (feature = "slice_pattern" , reason = "stopgap trait for slice patterns" , issue = "56345" )] |
4675 | /// Patterns in slices - currently, only used by `strip_prefix` and `strip_suffix`. At a future |
4676 | /// point, we hope to generalise `core::str::Pattern` (which at the time of writing is limited to |
4677 | /// `str`) to slices, and then this trait will be replaced or abolished. |
4678 | pub trait SlicePattern { |
4679 | /// The element type of the slice being matched on. |
4680 | type Item; |
4681 | |
4682 | /// Currently, the consumers of `SlicePattern` need a slice. |
4683 | fn as_slice(&self) -> &[Self::Item]; |
4684 | } |
4685 | |
4686 | #[stable (feature = "slice_strip" , since = "1.51.0" )] |
4687 | impl<T> SlicePattern for [T] { |
4688 | type Item = T; |
4689 | |
4690 | #[inline ] |
4691 | fn as_slice(&self) -> &[Self::Item] { |
4692 | self |
4693 | } |
4694 | } |
4695 | |
4696 | #[stable (feature = "slice_strip" , since = "1.51.0" )] |
4697 | impl<T, const N: usize> SlicePattern for [T; N] { |
4698 | type Item = T; |
4699 | |
4700 | #[inline ] |
4701 | fn as_slice(&self) -> &[Self::Item] { |
4702 | self |
4703 | } |
4704 | } |
4705 | |
4706 | /// This checks every index against each other, and against `len`. |
4707 | /// |
4708 | /// This will do `binomial(N + 1, 2) = N * (N + 1) / 2 = 0, 1, 3, 6, 10, ..` |
4709 | /// comparison operations. |
4710 | fn get_many_check_valid<const N: usize>(indices: &[usize; N], len: usize) -> bool { |
4711 | // NB: The optimizer should inline the loops into a sequence |
4712 | // of instructions without additional branching. |
4713 | let mut valid: bool = true; |
4714 | for (i: usize, &idx: usize) in indices.iter().enumerate() { |
4715 | valid &= idx < len; |
4716 | for &idx2: usize in &indices[..i] { |
4717 | valid &= idx != idx2; |
4718 | } |
4719 | } |
4720 | valid |
4721 | } |
4722 | |
4723 | /// The error type returned by [`get_many_mut<N>`][`slice::get_many_mut`]. |
4724 | /// |
4725 | /// It indicates one of two possible errors: |
4726 | /// - An index is out-of-bounds. |
4727 | /// - The same index appeared multiple times in the array. |
4728 | /// |
4729 | /// # Examples |
4730 | /// |
4731 | /// ``` |
4732 | /// #![feature(get_many_mut)] |
4733 | /// |
4734 | /// let v = &mut [1, 2, 3]; |
4735 | /// assert!(v.get_many_mut([0, 999]).is_err()); |
4736 | /// assert!(v.get_many_mut([1, 1]).is_err()); |
4737 | /// ``` |
4738 | #[unstable (feature = "get_many_mut" , issue = "104642" )] |
4739 | // NB: The N here is there to be forward-compatible with adding more details |
4740 | // to the error type at a later point |
4741 | pub struct GetManyMutError<const N: usize> { |
4742 | _private: (), |
4743 | } |
4744 | |
4745 | #[unstable (feature = "get_many_mut" , issue = "104642" )] |
4746 | impl<const N: usize> fmt::Debug for GetManyMutError<N> { |
4747 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
4748 | f.debug_struct(name:"GetManyMutError" ).finish_non_exhaustive() |
4749 | } |
4750 | } |
4751 | |
4752 | #[unstable (feature = "get_many_mut" , issue = "104642" )] |
4753 | impl<const N: usize> fmt::Display for GetManyMutError<N> { |
4754 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
4755 | fmt::Display::fmt(self:"an index is out of bounds or appeared multiple times in the array" , f) |
4756 | } |
4757 | } |
4758 | |