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