]>
Commit | Line | Data |
---|---|---|
85aaf69f | 1 | // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT |
1a4d82fc JJ |
2 | // file at the top-level directory of this distribution and at |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
c1a9b12d | 11 | //! A dynamically-sized view into a contiguous sequence, `[T]`. |
1a4d82fc | 12 | //! |
62682a34 SL |
13 | //! Slices are a view into a block of memory represented as a pointer and a |
14 | //! length. | |
1a4d82fc | 15 | //! |
c34b1796 | 16 | //! ``` |
1a4d82fc | 17 | //! // slicing a Vec |
c34b1796 AL |
18 | //! let vec = vec![1, 2, 3]; |
19 | //! let int_slice = &vec[..]; | |
1a4d82fc JJ |
20 | //! // coercing an array to a slice |
21 | //! let str_slice: &[&str] = &["one", "two", "three"]; | |
22 | //! ``` | |
23 | //! | |
24 | //! Slices are either mutable or shared. The shared slice type is `&[T]`, | |
c34b1796 AL |
25 | //! while the mutable slice type is `&mut [T]`, where `T` represents the element |
26 | //! type. For example, you can mutate the block of memory that a mutable slice | |
27 | //! points to: | |
1a4d82fc | 28 | //! |
c34b1796 AL |
29 | //! ``` |
30 | //! let x = &mut [1, 2, 3]; | |
1a4d82fc | 31 | //! x[1] = 7; |
c34b1796 | 32 | //! assert_eq!(x, &[1, 7, 3]); |
1a4d82fc JJ |
33 | //! ``` |
34 | //! | |
35 | //! Here are some of the things this module contains: | |
36 | //! | |
37 | //! ## Structs | |
38 | //! | |
39 | //! There are several structs that are useful for slices, such as `Iter`, which | |
40 | //! represents iteration over a slice. | |
41 | //! | |
c34b1796 | 42 | //! ## Trait Implementations |
1a4d82fc JJ |
43 | //! |
44 | //! There are several implementations of common traits for slices. Some examples | |
45 | //! include: | |
46 | //! | |
47 | //! * `Clone` | |
c34b1796 | 48 | //! * `Eq`, `Ord` - for slices whose element type are `Eq` or `Ord`. |
1a4d82fc JJ |
49 | //! * `Hash` - for slices whose element type is `Hash` |
50 | //! | |
51 | //! ## Iteration | |
52 | //! | |
c34b1796 AL |
53 | //! The slices implement `IntoIterator`. The iterator yields references to the |
54 | //! slice elements. | |
1a4d82fc | 55 | //! |
c34b1796 AL |
56 | //! ``` |
57 | //! let numbers = &[0, 1, 2]; | |
58 | //! for n in numbers { | |
59 | //! println!("{} is a number!", n); | |
1a4d82fc JJ |
60 | //! } |
61 | //! ``` | |
62 | //! | |
c34b1796 AL |
63 | //! The mutable slice yields mutable references to the elements: |
64 | //! | |
65 | //! ``` | |
66 | //! let mut scores = [7, 8, 9]; | |
67 | //! for score in &mut scores[..] { | |
68 | //! *score += 1; | |
69 | //! } | |
70 | //! ``` | |
71 | //! | |
62682a34 SL |
72 | //! This iterator yields mutable references to the slice's elements, so while |
73 | //! the element type of the slice is `i32`, the element type of the iterator is | |
74 | //! `&mut i32`. | |
c34b1796 AL |
75 | //! |
76 | //! * `.iter()` and `.iter_mut()` are the explicit methods to return the default | |
77 | //! iterators. | |
78 | //! * Further methods that return iterators are `.split()`, `.splitn()`, | |
79 | //! `.chunks()`, `.windows()` and more. | |
c1a9b12d | 80 | //! |
54a0048b | 81 | //! *[See also the slice primitive type](../../std/primitive.slice.html).* |
85aaf69f | 82 | #![stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 83 | |
62682a34 SL |
84 | // Many of the usings in this module are only used in the test configuration. |
85 | // It's cleaner to just turn off the unused_imports warning than to fix them. | |
7453a54e | 86 | #![cfg_attr(test, allow(unused_imports, dead_code))] |
62682a34 | 87 | |
1a4d82fc | 88 | use alloc::boxed::Box; |
1a4d82fc | 89 | use core::cmp::Ordering::{self, Greater, Less}; |
7453a54e | 90 | use core::cmp; |
1a4d82fc JJ |
91 | use core::mem::size_of; |
92 | use core::mem; | |
1a4d82fc | 93 | use core::ptr; |
1a4d82fc | 94 | use core::slice as core_slice; |
1a4d82fc | 95 | |
85aaf69f | 96 | use borrow::{Borrow, BorrowMut, ToOwned}; |
1a4d82fc JJ |
97 | use vec::Vec; |
98 | ||
92a42be0 | 99 | #[stable(feature = "rust1", since = "1.0.0")] |
9346a6ac | 100 | pub use core::slice::{Chunks, Windows}; |
92a42be0 | 101 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 102 | pub use core::slice::{Iter, IterMut}; |
92a42be0 | 103 | #[stable(feature = "rust1", since = "1.0.0")] |
e9174d1e | 104 | pub use core::slice::{SplitMut, ChunksMut, Split}; |
92a42be0 | 105 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 106 | pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut}; |
92a42be0 | 107 | #[stable(feature = "rust1", since = "1.0.0")] |
85aaf69f | 108 | pub use core::slice::{from_raw_parts, from_raw_parts_mut}; |
1a4d82fc JJ |
109 | |
110 | //////////////////////////////////////////////////////////////////////////////// | |
111 | // Basic slice extension methods | |
112 | //////////////////////////////////////////////////////////////////////////////// | |
113 | ||
c34b1796 AL |
114 | // HACK(japaric) needed for the implementation of `vec!` macro during testing |
115 | // NB see the hack module in this file for more details | |
116 | #[cfg(test)] | |
117 | pub use self::hack::into_vec; | |
118 | ||
119 | // HACK(japaric) needed for the implementation of `Vec::clone` during testing | |
120 | // NB see the hack module in this file for more details | |
121 | #[cfg(test)] | |
122 | pub use self::hack::to_vec; | |
123 | ||
124 | // HACK(japaric): With cfg(test) `impl [T]` is not available, these three | |
125 | // functions are actually methods that are in `impl [T]` but not in | |
126 | // `core::slice::SliceExt` - we need to supply these functions for the | |
127 | // `test_permutations` test | |
128 | mod hack { | |
129 | use alloc::boxed::Box; | |
c34b1796 | 130 | use core::mem; |
c34b1796 AL |
131 | |
132 | #[cfg(test)] | |
133 | use string::ToString; | |
134 | use vec::Vec; | |
135 | ||
c34b1796 AL |
136 | pub fn into_vec<T>(mut b: Box<[T]>) -> Vec<T> { |
137 | unsafe { | |
138 | let xs = Vec::from_raw_parts(b.as_mut_ptr(), b.len(), b.len()); | |
139 | mem::forget(b); | |
140 | xs | |
141 | } | |
142 | } | |
143 | ||
c34b1796 | 144 | #[inline] |
92a42be0 SL |
145 | pub fn to_vec<T>(s: &[T]) -> Vec<T> |
146 | where T: Clone | |
147 | { | |
c34b1796 | 148 | let mut vector = Vec::with_capacity(s.len()); |
92a42be0 | 149 | vector.extend_from_slice(s); |
c34b1796 AL |
150 | vector |
151 | } | |
c34b1796 AL |
152 | } |
153 | ||
1a4d82fc | 154 | /// Allocating extension methods for slices. |
c34b1796 AL |
155 | #[lang = "slice"] |
156 | #[cfg(not(test))] | |
c34b1796 | 157 | impl<T> [T] { |
62682a34 | 158 | /// Returns the number of elements in the slice. |
1a4d82fc | 159 | /// |
62682a34 | 160 | /// # Example |
1a4d82fc | 161 | /// |
62682a34 SL |
162 | /// ``` |
163 | /// let a = [1, 2, 3]; | |
164 | /// assert_eq!(a.len(), 3); | |
1a4d82fc | 165 | /// ``` |
85aaf69f | 166 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 167 | #[inline] |
62682a34 SL |
168 | pub fn len(&self) -> usize { |
169 | core_slice::SliceExt::len(self) | |
c34b1796 | 170 | } |
1a4d82fc | 171 | |
62682a34 | 172 | /// Returns true if the slice has a length of 0 |
1a4d82fc | 173 | /// |
62682a34 | 174 | /// # Example |
1a4d82fc | 175 | /// |
1a4d82fc | 176 | /// ``` |
62682a34 SL |
177 | /// let a = [1, 2, 3]; |
178 | /// assert!(!a.is_empty()); | |
179 | /// ``` | |
180 | #[stable(feature = "rust1", since = "1.0.0")] | |
c34b1796 | 181 | #[inline] |
62682a34 SL |
182 | pub fn is_empty(&self) -> bool { |
183 | core_slice::SliceExt::is_empty(self) | |
c34b1796 | 184 | } |
1a4d82fc | 185 | |
62682a34 | 186 | /// Returns the first element of a slice, or `None` if it is empty. |
85aaf69f SL |
187 | /// |
188 | /// # Examples | |
189 | /// | |
190 | /// ``` | |
62682a34 SL |
191 | /// let v = [10, 40, 30]; |
192 | /// assert_eq!(Some(&10), v.first()); | |
193 | /// | |
194 | /// let w: &[i32] = &[]; | |
195 | /// assert_eq!(None, w.first()); | |
85aaf69f SL |
196 | /// ``` |
197 | #[stable(feature = "rust1", since = "1.0.0")] | |
c34b1796 | 198 | #[inline] |
62682a34 SL |
199 | pub fn first(&self) -> Option<&T> { |
200 | core_slice::SliceExt::first(self) | |
c34b1796 | 201 | } |
1a4d82fc | 202 | |
62682a34 | 203 | /// Returns a mutable pointer to the first element of a slice, or `None` if it is empty |
85aaf69f | 204 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 205 | #[inline] |
62682a34 SL |
206 | pub fn first_mut(&mut self) -> Option<&mut T> { |
207 | core_slice::SliceExt::first_mut(self) | |
c34b1796 | 208 | } |
1a4d82fc | 209 | |
c1a9b12d | 210 | /// Returns the first and all the rest of the elements of a slice. |
b039eaaf | 211 | #[stable(feature = "slice_splits", since = "1.5.0")] |
c1a9b12d SL |
212 | #[inline] |
213 | pub fn split_first(&self) -> Option<(&T, &[T])> { | |
214 | core_slice::SliceExt::split_first(self) | |
215 | } | |
216 | ||
c1a9b12d | 217 | /// Returns the first and all the rest of the elements of a slice. |
b039eaaf | 218 | #[stable(feature = "slice_splits", since = "1.5.0")] |
c1a9b12d SL |
219 | #[inline] |
220 | pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> { | |
221 | core_slice::SliceExt::split_first_mut(self) | |
222 | } | |
223 | ||
c1a9b12d | 224 | /// Returns the last and all the rest of the elements of a slice. |
b039eaaf | 225 | #[stable(feature = "slice_splits", since = "1.5.0")] |
c1a9b12d SL |
226 | #[inline] |
227 | pub fn split_last(&self) -> Option<(&T, &[T])> { | |
228 | core_slice::SliceExt::split_last(self) | |
229 | ||
230 | } | |
231 | ||
c1a9b12d | 232 | /// Returns the last and all the rest of the elements of a slice. |
b039eaaf | 233 | #[stable(feature = "slice_splits", since = "1.5.0")] |
c1a9b12d SL |
234 | #[inline] |
235 | pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> { | |
236 | core_slice::SliceExt::split_last_mut(self) | |
237 | } | |
238 | ||
62682a34 | 239 | /// Returns the last element of a slice, or `None` if it is empty. |
1a4d82fc | 240 | /// |
62682a34 | 241 | /// # Examples |
1a4d82fc | 242 | /// |
62682a34 SL |
243 | /// ``` |
244 | /// let v = [10, 40, 30]; | |
245 | /// assert_eq!(Some(&30), v.last()); | |
1a4d82fc | 246 | /// |
62682a34 SL |
247 | /// let w: &[i32] = &[]; |
248 | /// assert_eq!(None, w.last()); | |
1a4d82fc | 249 | /// ``` |
85aaf69f | 250 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 251 | #[inline] |
62682a34 SL |
252 | pub fn last(&self) -> Option<&T> { |
253 | core_slice::SliceExt::last(self) | |
c34b1796 | 254 | } |
1a4d82fc | 255 | |
62682a34 | 256 | /// Returns a mutable pointer to the last item in the slice. |
85aaf69f | 257 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 258 | #[inline] |
62682a34 SL |
259 | pub fn last_mut(&mut self) -> Option<&mut T> { |
260 | core_slice::SliceExt::last_mut(self) | |
c34b1796 | 261 | } |
1a4d82fc JJ |
262 | |
263 | /// Returns the element of a slice at the given index, or `None` if the | |
264 | /// index is out of bounds. | |
85aaf69f SL |
265 | /// |
266 | /// # Examples | |
267 | /// | |
268 | /// ``` | |
269 | /// let v = [10, 40, 30]; | |
270 | /// assert_eq!(Some(&40), v.get(1)); | |
271 | /// assert_eq!(None, v.get(3)); | |
272 | /// ``` | |
273 | #[stable(feature = "rust1", since = "1.0.0")] | |
c34b1796 AL |
274 | #[inline] |
275 | pub fn get(&self, index: usize) -> Option<&T> { | |
276 | core_slice::SliceExt::get(self, index) | |
277 | } | |
1a4d82fc | 278 | |
62682a34 SL |
279 | /// Returns a mutable reference to the element at the given index, |
280 | /// or `None` if the index is out of bounds | |
85aaf69f | 281 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 282 | #[inline] |
62682a34 SL |
283 | pub fn get_mut(&mut self, index: usize) -> Option<&mut T> { |
284 | core_slice::SliceExt::get_mut(self, index) | |
c34b1796 | 285 | } |
1a4d82fc | 286 | |
62682a34 SL |
287 | /// Returns a pointer to the element at the given index, without doing |
288 | /// bounds checking. | |
289 | #[stable(feature = "rust1", since = "1.0.0")] | |
c34b1796 | 290 | #[inline] |
62682a34 SL |
291 | pub unsafe fn get_unchecked(&self, index: usize) -> &T { |
292 | core_slice::SliceExt::get_unchecked(self, index) | |
c34b1796 | 293 | } |
1a4d82fc | 294 | |
62682a34 SL |
295 | /// Returns an unsafe mutable pointer to the element in index |
296 | #[stable(feature = "rust1", since = "1.0.0")] | |
c34b1796 | 297 | #[inline] |
62682a34 SL |
298 | pub unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T { |
299 | core_slice::SliceExt::get_unchecked_mut(self, index) | |
c34b1796 | 300 | } |
1a4d82fc | 301 | |
62682a34 | 302 | /// Returns an raw pointer to the slice's buffer |
85aaf69f | 303 | /// |
62682a34 SL |
304 | /// The caller must ensure that the slice outlives the pointer this |
305 | /// function returns, or else it will end up pointing to garbage. | |
85aaf69f | 306 | /// |
62682a34 SL |
307 | /// Modifying the slice may cause its buffer to be reallocated, which |
308 | /// would also make any pointers to it invalid. | |
85aaf69f | 309 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 310 | #[inline] |
62682a34 SL |
311 | pub fn as_ptr(&self) -> *const T { |
312 | core_slice::SliceExt::as_ptr(self) | |
c34b1796 | 313 | } |
1a4d82fc | 314 | |
62682a34 | 315 | /// Returns an unsafe mutable pointer to the slice's buffer. |
1a4d82fc JJ |
316 | /// |
317 | /// The caller must ensure that the slice outlives the pointer this | |
318 | /// function returns, or else it will end up pointing to garbage. | |
319 | /// | |
320 | /// Modifying the slice may cause its buffer to be reallocated, which | |
321 | /// would also make any pointers to it invalid. | |
85aaf69f | 322 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 323 | #[inline] |
62682a34 SL |
324 | pub fn as_mut_ptr(&mut self) -> *mut T { |
325 | core_slice::SliceExt::as_mut_ptr(self) | |
c34b1796 | 326 | } |
1a4d82fc | 327 | |
62682a34 | 328 | /// Swaps two elements in a slice. |
1a4d82fc | 329 | /// |
62682a34 | 330 | /// # Arguments |
1a4d82fc | 331 | /// |
62682a34 SL |
332 | /// * a - The index of the first element |
333 | /// * b - The index of the second element | |
1a4d82fc | 334 | /// |
62682a34 | 335 | /// # Panics |
1a4d82fc | 336 | /// |
62682a34 | 337 | /// Panics if `a` or `b` are out of bounds. |
1a4d82fc JJ |
338 | /// |
339 | /// # Example | |
340 | /// | |
62682a34 SL |
341 | /// ```rust |
342 | /// let mut v = ["a", "b", "c", "d"]; | |
343 | /// v.swap(1, 3); | |
344 | /// assert!(v == ["a", "d", "c", "b"]); | |
1a4d82fc | 345 | /// ``` |
85aaf69f | 346 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 347 | #[inline] |
62682a34 SL |
348 | pub fn swap(&mut self, a: usize, b: usize) { |
349 | core_slice::SliceExt::swap(self, a, b) | |
c34b1796 | 350 | } |
1a4d82fc | 351 | |
62682a34 | 352 | /// Reverse the order of elements in a slice, in place. |
1a4d82fc JJ |
353 | /// |
354 | /// # Example | |
355 | /// | |
62682a34 SL |
356 | /// ```rust |
357 | /// let mut v = [1, 2, 3]; | |
358 | /// v.reverse(); | |
359 | /// assert!(v == [3, 2, 1]); | |
1a4d82fc | 360 | /// ``` |
85aaf69f | 361 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 362 | #[inline] |
62682a34 SL |
363 | pub fn reverse(&mut self) { |
364 | core_slice::SliceExt::reverse(self) | |
c34b1796 AL |
365 | } |
366 | ||
62682a34 | 367 | /// Returns an iterator over the slice. |
85aaf69f | 368 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 369 | #[inline] |
62682a34 SL |
370 | pub fn iter(&self) -> Iter<T> { |
371 | core_slice::SliceExt::iter(self) | |
c34b1796 | 372 | } |
1a4d82fc JJ |
373 | |
374 | /// Returns an iterator that allows modifying each value | |
85aaf69f | 375 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
376 | #[inline] |
377 | pub fn iter_mut(&mut self) -> IterMut<T> { | |
378 | core_slice::SliceExt::iter_mut(self) | |
379 | } | |
1a4d82fc | 380 | |
62682a34 SL |
381 | /// Returns an iterator over all contiguous windows of length |
382 | /// `size`. The windows overlap. If the slice is shorter than | |
383 | /// `size`, the iterator returns no values. | |
c34b1796 | 384 | /// |
62682a34 SL |
385 | /// # Panics |
386 | /// | |
387 | /// Panics if `size` is 0. | |
388 | /// | |
389 | /// # Example | |
390 | /// | |
391 | /// Print the adjacent pairs of a slice (i.e. `[1,2]`, `[2,3]`, | |
392 | /// `[3,4]`): | |
393 | /// | |
394 | /// ```rust | |
395 | /// let v = &[1, 2, 3, 4]; | |
396 | /// for win in v.windows(2) { | |
397 | /// println!("{:?}", win); | |
398 | /// } | |
399 | /// ``` | |
85aaf69f | 400 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 401 | #[inline] |
62682a34 SL |
402 | pub fn windows(&self, size: usize) -> Windows<T> { |
403 | core_slice::SliceExt::windows(self, size) | |
c34b1796 | 404 | } |
1a4d82fc | 405 | |
62682a34 | 406 | /// Returns an iterator over `size` elements of the slice at a |
7453a54e | 407 | /// time. The chunks are slices and do not overlap. If `size` does not divide the |
62682a34 SL |
408 | /// length of the slice, then the last chunk will not have length |
409 | /// `size`. | |
c34b1796 | 410 | /// |
62682a34 SL |
411 | /// # Panics |
412 | /// | |
413 | /// Panics if `size` is 0. | |
414 | /// | |
415 | /// # Example | |
416 | /// | |
417 | /// Print the slice two elements at a time (i.e. `[1,2]`, | |
418 | /// `[3,4]`, `[5]`): | |
419 | /// | |
420 | /// ```rust | |
421 | /// let v = &[1, 2, 3, 4, 5]; | |
422 | /// for win in v.chunks(2) { | |
423 | /// println!("{:?}", win); | |
424 | /// } | |
425 | /// ``` | |
85aaf69f | 426 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 427 | #[inline] |
62682a34 SL |
428 | pub fn chunks(&self, size: usize) -> Chunks<T> { |
429 | core_slice::SliceExt::chunks(self, size) | |
c34b1796 | 430 | } |
1a4d82fc JJ |
431 | |
432 | /// Returns an iterator over `chunk_size` elements of the slice at a time. | |
7453a54e | 433 | /// The chunks are mutable slices, and do not overlap. If `chunk_size` does |
1a4d82fc JJ |
434 | /// not divide the length of the slice, then the last chunk will not |
435 | /// have length `chunk_size`. | |
436 | /// | |
437 | /// # Panics | |
438 | /// | |
439 | /// Panics if `chunk_size` is 0. | |
85aaf69f | 440 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
441 | #[inline] |
442 | pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> { | |
443 | core_slice::SliceExt::chunks_mut(self, chunk_size) | |
444 | } | |
1a4d82fc | 445 | |
62682a34 | 446 | /// Divides one slice into two at an index. |
1a4d82fc | 447 | /// |
62682a34 SL |
448 | /// The first will contain all indices from `[0, mid)` (excluding |
449 | /// the index `mid` itself) and the second will contain all | |
450 | /// indices from `[mid, len)` (excluding the index `len` itself). | |
1a4d82fc | 451 | /// |
b039eaaf SL |
452 | /// # Panics |
453 | /// | |
62682a34 | 454 | /// Panics if `mid > len`. |
1a4d82fc | 455 | /// |
62682a34 | 456 | /// # Examples |
1a4d82fc | 457 | /// |
62682a34 SL |
458 | /// ``` |
459 | /// let v = [10, 40, 30, 20, 50]; | |
460 | /// let (v1, v2) = v.split_at(2); | |
461 | /// assert_eq!([10, 40], v1); | |
462 | /// assert_eq!([30, 20, 50], v2); | |
1a4d82fc | 463 | /// ``` |
85aaf69f | 464 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 465 | #[inline] |
62682a34 SL |
466 | pub fn split_at(&self, mid: usize) -> (&[T], &[T]) { |
467 | core_slice::SliceExt::split_at(self, mid) | |
c34b1796 | 468 | } |
1a4d82fc JJ |
469 | |
470 | /// Divides one `&mut` into two at an index. | |
471 | /// | |
472 | /// The first will contain all indices from `[0, mid)` (excluding | |
473 | /// the index `mid` itself) and the second will contain all | |
474 | /// indices from `[mid, len)` (excluding the index `len` itself). | |
475 | /// | |
476 | /// # Panics | |
477 | /// | |
478 | /// Panics if `mid > len`. | |
479 | /// | |
480 | /// # Example | |
481 | /// | |
482 | /// ```rust | |
85aaf69f | 483 | /// let mut v = [1, 2, 3, 4, 5, 6]; |
1a4d82fc JJ |
484 | /// |
485 | /// // scoped to restrict the lifetime of the borrows | |
486 | /// { | |
487 | /// let (left, right) = v.split_at_mut(0); | |
488 | /// assert!(left == []); | |
85aaf69f | 489 | /// assert!(right == [1, 2, 3, 4, 5, 6]); |
1a4d82fc JJ |
490 | /// } |
491 | /// | |
492 | /// { | |
493 | /// let (left, right) = v.split_at_mut(2); | |
85aaf69f SL |
494 | /// assert!(left == [1, 2]); |
495 | /// assert!(right == [3, 4, 5, 6]); | |
1a4d82fc JJ |
496 | /// } |
497 | /// | |
498 | /// { | |
499 | /// let (left, right) = v.split_at_mut(6); | |
85aaf69f | 500 | /// assert!(left == [1, 2, 3, 4, 5, 6]); |
1a4d82fc JJ |
501 | /// assert!(right == []); |
502 | /// } | |
503 | /// ``` | |
85aaf69f | 504 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 AL |
505 | #[inline] |
506 | pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) { | |
507 | core_slice::SliceExt::split_at_mut(self, mid) | |
508 | } | |
1a4d82fc | 509 | |
62682a34 SL |
510 | /// Returns an iterator over subslices separated by elements that match |
511 | /// `pred`. The matched element is not contained in the subslices. | |
1a4d82fc | 512 | /// |
62682a34 | 513 | /// # Examples |
1a4d82fc | 514 | /// |
62682a34 SL |
515 | /// Print the slice split by numbers divisible by 3 (i.e. `[10, 40]`, |
516 | /// `[20]`, `[50]`): | |
517 | /// | |
518 | /// ``` | |
519 | /// let v = [10, 40, 30, 20, 60, 50]; | |
520 | /// for group in v.split(|num| *num % 3 == 0) { | |
521 | /// println!("{:?}", group); | |
522 | /// } | |
1a4d82fc | 523 | /// ``` |
85aaf69f | 524 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 525 | #[inline] |
92a42be0 SL |
526 | pub fn split<F>(&self, pred: F) -> Split<T, F> |
527 | where F: FnMut(&T) -> bool | |
528 | { | |
62682a34 | 529 | core_slice::SliceExt::split(self, pred) |
c34b1796 | 530 | } |
1a4d82fc | 531 | |
62682a34 SL |
532 | /// Returns an iterator over mutable subslices separated by elements that |
533 | /// match `pred`. The matched element is not contained in the subslices. | |
85aaf69f | 534 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 535 | #[inline] |
92a42be0 SL |
536 | pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F> |
537 | where F: FnMut(&T) -> bool | |
538 | { | |
62682a34 | 539 | core_slice::SliceExt::split_mut(self, pred) |
c34b1796 | 540 | } |
1a4d82fc | 541 | |
62682a34 SL |
542 | /// Returns an iterator over subslices separated by elements that match |
543 | /// `pred`, limited to returning at most `n` items. The matched element is | |
544 | /// not contained in the subslices. | |
1a4d82fc | 545 | /// |
62682a34 SL |
546 | /// The last element returned, if any, will contain the remainder of the |
547 | /// slice. | |
1a4d82fc JJ |
548 | /// |
549 | /// # Examples | |
550 | /// | |
62682a34 SL |
551 | /// Print the slice split once by numbers divisible by 3 (i.e. `[10, 40]`, |
552 | /// `[20, 60, 50]`): | |
1a4d82fc | 553 | /// |
62682a34 SL |
554 | /// ``` |
555 | /// let v = [10, 40, 30, 20, 60, 50]; | |
556 | /// for group in v.splitn(2, |num| *num % 3 == 0) { | |
557 | /// println!("{:?}", group); | |
1a4d82fc JJ |
558 | /// } |
559 | /// ``` | |
62682a34 SL |
560 | #[stable(feature = "rust1", since = "1.0.0")] |
561 | #[inline] | |
92a42be0 SL |
562 | pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<T, F> |
563 | where F: FnMut(&T) -> bool | |
564 | { | |
62682a34 SL |
565 | core_slice::SliceExt::splitn(self, n, pred) |
566 | } | |
567 | ||
568 | /// Returns an iterator over subslices separated by elements that match | |
569 | /// `pred`, limited to returning at most `n` items. The matched element is | |
570 | /// not contained in the subslices. | |
1a4d82fc | 571 | /// |
62682a34 SL |
572 | /// The last element returned, if any, will contain the remainder of the |
573 | /// slice. | |
574 | #[stable(feature = "rust1", since = "1.0.0")] | |
575 | #[inline] | |
576 | pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<T, F> | |
92a42be0 SL |
577 | where F: FnMut(&T) -> bool |
578 | { | |
62682a34 SL |
579 | core_slice::SliceExt::splitn_mut(self, n, pred) |
580 | } | |
581 | ||
582 | /// Returns an iterator over subslices separated by elements that match | |
583 | /// `pred` limited to returning at most `n` items. This starts at the end of | |
584 | /// the slice and works backwards. The matched element is not contained in | |
585 | /// the subslices. | |
1a4d82fc | 586 | /// |
62682a34 SL |
587 | /// The last element returned, if any, will contain the remainder of the |
588 | /// slice. | |
1a4d82fc | 589 | /// |
62682a34 SL |
590 | /// # Examples |
591 | /// | |
592 | /// Print the slice split once, starting from the end, by numbers divisible | |
593 | /// by 3 (i.e. `[50]`, `[10, 40, 30, 20]`): | |
594 | /// | |
595 | /// ``` | |
596 | /// let v = [10, 40, 30, 20, 60, 50]; | |
597 | /// for group in v.rsplitn(2, |num| *num % 3 == 0) { | |
598 | /// println!("{:?}", group); | |
599 | /// } | |
1a4d82fc | 600 | /// ``` |
62682a34 | 601 | #[stable(feature = "rust1", since = "1.0.0")] |
c34b1796 | 602 | #[inline] |
92a42be0 SL |
603 | pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<T, F> |
604 | where F: FnMut(&T) -> bool | |
605 | { | |
62682a34 | 606 | core_slice::SliceExt::rsplitn(self, n, pred) |
c34b1796 | 607 | } |
1a4d82fc | 608 | |
62682a34 SL |
609 | /// Returns an iterator over subslices separated by elements that match |
610 | /// `pred` limited to returning at most `n` items. This starts at the end of | |
611 | /// the slice and works backwards. The matched element is not contained in | |
612 | /// the subslices. | |
1a4d82fc | 613 | /// |
62682a34 SL |
614 | /// The last element returned, if any, will contain the remainder of the |
615 | /// slice. | |
616 | #[stable(feature = "rust1", since = "1.0.0")] | |
617 | #[inline] | |
92a42be0 SL |
618 | pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<T, F> |
619 | where F: FnMut(&T) -> bool | |
620 | { | |
62682a34 SL |
621 | core_slice::SliceExt::rsplitn_mut(self, n, pred) |
622 | } | |
623 | ||
624 | /// Returns true if the slice contains an element with the given value. | |
1a4d82fc | 625 | /// |
62682a34 | 626 | /// # Examples |
1a4d82fc | 627 | /// |
1a4d82fc | 628 | /// ``` |
62682a34 SL |
629 | /// let v = [10, 40, 30]; |
630 | /// assert!(v.contains(&30)); | |
631 | /// assert!(!v.contains(&50)); | |
632 | /// ``` | |
633 | #[stable(feature = "rust1", since = "1.0.0")] | |
92a42be0 SL |
634 | pub fn contains(&self, x: &T) -> bool |
635 | where T: PartialEq | |
636 | { | |
62682a34 | 637 | core_slice::SliceExt::contains(self, x) |
c34b1796 | 638 | } |
1a4d82fc | 639 | |
62682a34 | 640 | /// Returns true if `needle` is a prefix of the slice. |
1a4d82fc JJ |
641 | /// |
642 | /// # Examples | |
643 | /// | |
62682a34 SL |
644 | /// ``` |
645 | /// let v = [10, 40, 30]; | |
646 | /// assert!(v.starts_with(&[10])); | |
647 | /// assert!(v.starts_with(&[10, 40])); | |
648 | /// assert!(!v.starts_with(&[50])); | |
649 | /// assert!(!v.starts_with(&[10, 50])); | |
650 | /// ``` | |
651 | #[stable(feature = "rust1", since = "1.0.0")] | |
92a42be0 SL |
652 | pub fn starts_with(&self, needle: &[T]) -> bool |
653 | where T: PartialEq | |
654 | { | |
62682a34 SL |
655 | core_slice::SliceExt::starts_with(self, needle) |
656 | } | |
657 | ||
658 | /// Returns true if `needle` is a suffix of the slice. | |
659 | /// | |
660 | /// # Examples | |
1a4d82fc | 661 | /// |
62682a34 SL |
662 | /// ``` |
663 | /// let v = [10, 40, 30]; | |
664 | /// assert!(v.ends_with(&[30])); | |
665 | /// assert!(v.ends_with(&[40, 30])); | |
666 | /// assert!(!v.ends_with(&[50])); | |
667 | /// assert!(!v.ends_with(&[50, 30])); | |
1a4d82fc | 668 | /// ``` |
85aaf69f | 669 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
670 | pub fn ends_with(&self, needle: &[T]) -> bool |
671 | where T: PartialEq | |
672 | { | |
62682a34 SL |
673 | core_slice::SliceExt::ends_with(self, needle) |
674 | } | |
675 | ||
1a4d82fc JJ |
676 | /// Binary search a sorted slice for a given element. |
677 | /// | |
678 | /// If the value is found then `Ok` is returned, containing the | |
679 | /// index of the matching element; if the value is not found then | |
680 | /// `Err` is returned, containing the index where a matching | |
681 | /// element could be inserted while maintaining sorted order. | |
682 | /// | |
683 | /// # Example | |
684 | /// | |
685 | /// Looks up a series of four elements. The first is found, with a | |
686 | /// uniquely determined position; the second and third are not | |
687 | /// found; the fourth could match any position in `[1,4]`. | |
688 | /// | |
689 | /// ```rust | |
85aaf69f | 690 | /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; |
1a4d82fc JJ |
691 | /// |
692 | /// assert_eq!(s.binary_search(&13), Ok(9)); | |
693 | /// assert_eq!(s.binary_search(&4), Err(7)); | |
694 | /// assert_eq!(s.binary_search(&100), Err(13)); | |
695 | /// let r = s.binary_search(&1); | |
696 | /// assert!(match r { Ok(1...4) => true, _ => false, }); | |
697 | /// ``` | |
85aaf69f | 698 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 SL |
699 | pub fn binary_search(&self, x: &T) -> Result<usize, usize> |
700 | where T: Ord | |
701 | { | |
c34b1796 | 702 | core_slice::SliceExt::binary_search(self, x) |
1a4d82fc JJ |
703 | } |
704 | ||
62682a34 SL |
705 | /// Binary search a sorted slice with a comparator function. |
706 | /// | |
707 | /// The comparator function should implement an order consistent | |
708 | /// with the sort order of the underlying slice, returning an | |
709 | /// order code that indicates whether its argument is `Less`, | |
710 | /// `Equal` or `Greater` the desired target. | |
711 | /// | |
712 | /// If a matching value is found then returns `Ok`, containing | |
713 | /// the index for the matched element; if no match is found then | |
714 | /// `Err` is returned, containing the index where a matching | |
715 | /// element could be inserted while maintaining sorted order. | |
716 | /// | |
717 | /// # Example | |
718 | /// | |
719 | /// Looks up a series of four elements. The first is found, with a | |
720 | /// uniquely determined position; the second and third are not | |
721 | /// found; the fourth could match any position in `[1,4]`. | |
722 | /// | |
723 | /// ```rust | |
724 | /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; | |
725 | /// | |
726 | /// let seek = 13; | |
727 | /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9)); | |
728 | /// let seek = 4; | |
729 | /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7)); | |
730 | /// let seek = 100; | |
731 | /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13)); | |
732 | /// let seek = 1; | |
733 | /// let r = s.binary_search_by(|probe| probe.cmp(&seek)); | |
734 | /// assert!(match r { Ok(1...4) => true, _ => false, }); | |
735 | /// ``` | |
736 | #[stable(feature = "rust1", since = "1.0.0")] | |
737 | #[inline] | |
92a42be0 SL |
738 | pub fn binary_search_by<F>(&self, f: F) -> Result<usize, usize> |
739 | where F: FnMut(&T) -> Ordering | |
740 | { | |
62682a34 SL |
741 | core_slice::SliceExt::binary_search_by(self, f) |
742 | } | |
743 | ||
744 | /// Sorts the slice, in place. | |
745 | /// | |
746 | /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`. | |
747 | /// | |
92a42be0 SL |
748 | /// This is a stable sort. |
749 | /// | |
62682a34 SL |
750 | /// # Examples |
751 | /// | |
752 | /// ```rust | |
753 | /// let mut v = [-5, 4, 1, -3, 2]; | |
754 | /// | |
755 | /// v.sort(); | |
756 | /// assert!(v == [-5, -3, 1, 2, 4]); | |
757 | /// ``` | |
758 | #[stable(feature = "rust1", since = "1.0.0")] | |
759 | #[inline] | |
92a42be0 SL |
760 | pub fn sort(&mut self) |
761 | where T: Ord | |
762 | { | |
62682a34 SL |
763 | self.sort_by(|a, b| a.cmp(b)) |
764 | } | |
765 | ||
92a42be0 SL |
766 | /// Sorts the slice, in place, using `key` to extract a key by which to |
767 | /// order the sort by. | |
768 | /// | |
769 | /// This sort is `O(n log n)` worst-case and stable, but allocates | |
770 | /// approximately `2 * n`, where `n` is the length of `self`. | |
771 | /// | |
772 | /// This is a stable sort. | |
773 | /// | |
774 | /// # Examples | |
775 | /// | |
776 | /// ```rust | |
92a42be0 SL |
777 | /// let mut v = [-5i32, 4, 1, -3, 2]; |
778 | /// | |
779 | /// v.sort_by_key(|k| k.abs()); | |
780 | /// assert!(v == [1, 2, -3, 4, -5]); | |
781 | /// ``` | |
9cc50fc6 | 782 | #[stable(feature = "slice_sort_by_key", since = "1.7.0")] |
92a42be0 SL |
783 | #[inline] |
784 | pub fn sort_by_key<B, F>(&mut self, mut f: F) | |
785 | where F: FnMut(&T) -> B, B: Ord | |
786 | { | |
787 | self.sort_by(|a, b| f(a).cmp(&f(b))) | |
788 | } | |
789 | ||
62682a34 SL |
790 | /// Sorts the slice, in place, using `compare` to compare |
791 | /// elements. | |
792 | /// | |
793 | /// This sort is `O(n log n)` worst-case and stable, but allocates | |
794 | /// approximately `2 * n`, where `n` is the length of `self`. | |
795 | /// | |
796 | /// # Examples | |
797 | /// | |
798 | /// ```rust | |
799 | /// let mut v = [5, 4, 1, 3, 2]; | |
800 | /// v.sort_by(|a, b| a.cmp(b)); | |
801 | /// assert!(v == [1, 2, 3, 4, 5]); | |
802 | /// | |
803 | /// // reverse sorting | |
804 | /// v.sort_by(|a, b| b.cmp(a)); | |
805 | /// assert!(v == [5, 4, 3, 2, 1]); | |
806 | /// ``` | |
807 | #[stable(feature = "rust1", since = "1.0.0")] | |
808 | #[inline] | |
92a42be0 SL |
809 | pub fn sort_by<F>(&mut self, compare: F) |
810 | where F: FnMut(&T, &T) -> Ordering | |
811 | { | |
62682a34 SL |
812 | merge_sort(self, compare) |
813 | } | |
814 | ||
9cc50fc6 SL |
815 | /// Copies the elements from `src` into `self`. |
816 | /// | |
817 | /// The length of this slice must be the same as the slice passed in. | |
818 | /// | |
819 | /// # Panics | |
820 | /// | |
821 | /// This function will panic if the two slices have different lengths. | |
85aaf69f | 822 | /// |
62682a34 | 823 | /// # Example |
85aaf69f | 824 | /// |
62682a34 | 825 | /// ```rust |
62682a34 | 826 | /// let mut dst = [0, 0, 0]; |
9cc50fc6 | 827 | /// let src = [1, 2, 3]; |
85aaf69f | 828 | /// |
9cc50fc6 SL |
829 | /// dst.clone_from_slice(&src); |
830 | /// assert!(dst == [1, 2, 3]); | |
85aaf69f | 831 | /// ``` |
9cc50fc6 SL |
832 | #[stable(feature = "clone_from_slice", since = "1.7.0")] |
833 | pub fn clone_from_slice(&mut self, src: &[T]) where T: Clone { | |
62682a34 | 834 | core_slice::SliceExt::clone_from_slice(self, src) |
c34b1796 | 835 | } |
1a4d82fc | 836 | |
7453a54e SL |
837 | /// Copies all elements from `src` into `self`, using a memcpy. |
838 | /// | |
839 | /// The length of `src` must be the same as `self`. | |
840 | /// | |
841 | /// # Panics | |
842 | /// | |
843 | /// This function will panic if the two slices have different lengths. | |
844 | /// | |
845 | /// # Example | |
846 | /// | |
847 | /// ```rust | |
7453a54e SL |
848 | /// let mut dst = [0, 0, 0]; |
849 | /// let src = [1, 2, 3]; | |
850 | /// | |
851 | /// dst.copy_from_slice(&src); | |
852 | /// assert_eq!(src, dst); | |
853 | /// ``` | |
54a0048b | 854 | #[stable(feature = "copy_from_slice", since = "1.9.0")] |
7453a54e SL |
855 | pub fn copy_from_slice(&mut self, src: &[T]) where T: Copy { |
856 | core_slice::SliceExt::copy_from_slice(self, src) | |
857 | } | |
858 | ||
859 | ||
62682a34 | 860 | /// Copies `self` into a new `Vec`. |
85aaf69f | 861 | #[stable(feature = "rust1", since = "1.0.0")] |
62682a34 | 862 | #[inline] |
92a42be0 SL |
863 | pub fn to_vec(&self) -> Vec<T> |
864 | where T: Clone | |
865 | { | |
62682a34 SL |
866 | // NB see hack module in this file |
867 | hack::to_vec(self) | |
1a4d82fc JJ |
868 | } |
869 | ||
9346a6ac | 870 | /// Converts `self` into a vector without clones or allocation. |
c34b1796 | 871 | #[stable(feature = "rust1", since = "1.0.0")] |
1a4d82fc | 872 | #[inline] |
c34b1796 AL |
873 | pub fn into_vec(self: Box<Self>) -> Vec<T> { |
874 | // NB see hack module in this file | |
875 | hack::into_vec(self) | |
1a4d82fc | 876 | } |
c34b1796 | 877 | } |
1a4d82fc JJ |
878 | |
879 | //////////////////////////////////////////////////////////////////////////////// | |
880 | // Extension traits for slices over specific kinds of data | |
881 | //////////////////////////////////////////////////////////////////////////////// | |
62682a34 | 882 | #[unstable(feature = "slice_concat_ext", |
e9174d1e SL |
883 | reason = "trait should not have to exist", |
884 | issue = "27747")] | |
1a4d82fc | 885 | /// An extension trait for concatenating slices |
d9579d0f | 886 | pub trait SliceConcatExt<T: ?Sized> { |
62682a34 | 887 | #[unstable(feature = "slice_concat_ext", |
e9174d1e SL |
888 | reason = "trait should not have to exist", |
889 | issue = "27747")] | |
d9579d0f AL |
890 | /// The resulting type after concatenation |
891 | type Output; | |
892 | ||
893 | /// Flattens a slice of `T` into a single value `Self::Output`. | |
85aaf69f SL |
894 | /// |
895 | /// # Examples | |
896 | /// | |
897 | /// ``` | |
d9579d0f | 898 | /// assert_eq!(["hello", "world"].concat(), "helloworld"); |
85aaf69f SL |
899 | /// ``` |
900 | #[stable(feature = "rust1", since = "1.0.0")] | |
d9579d0f | 901 | fn concat(&self) -> Self::Output; |
1a4d82fc | 902 | |
c1a9b12d SL |
903 | /// Flattens a slice of `T` into a single value `Self::Output`, placing a |
904 | /// given separator between each. | |
905 | /// | |
906 | /// # Examples | |
907 | /// | |
908 | /// ``` | |
909 | /// assert_eq!(["hello", "world"].join(" "), "hello world"); | |
910 | /// ``` | |
911 | #[stable(feature = "rename_connect_to_join", since = "1.3.0")] | |
912 | fn join(&self, sep: &T) -> Self::Output; | |
913 | ||
85aaf69f | 914 | #[stable(feature = "rust1", since = "1.0.0")] |
92a42be0 | 915 | #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")] |
d9579d0f | 916 | fn connect(&self, sep: &T) -> Self::Output; |
1a4d82fc JJ |
917 | } |
918 | ||
92a42be0 SL |
919 | #[unstable(feature = "slice_concat_ext", |
920 | reason = "trait should not have to exist", | |
921 | issue = "27747")] | |
d9579d0f AL |
922 | impl<T: Clone, V: Borrow<[T]>> SliceConcatExt<T> for [V] { |
923 | type Output = Vec<T>; | |
924 | ||
1a4d82fc | 925 | fn concat(&self) -> Vec<T> { |
bd371182 | 926 | let size = self.iter().fold(0, |acc, v| acc + v.borrow().len()); |
1a4d82fc | 927 | let mut result = Vec::with_capacity(size); |
85aaf69f | 928 | for v in self { |
92a42be0 | 929 | result.extend_from_slice(v.borrow()) |
1a4d82fc JJ |
930 | } |
931 | result | |
932 | } | |
933 | ||
c1a9b12d | 934 | fn join(&self, sep: &T) -> Vec<T> { |
bd371182 | 935 | let size = self.iter().fold(0, |acc, v| acc + v.borrow().len()); |
1a4d82fc JJ |
936 | let mut result = Vec::with_capacity(size + self.len()); |
937 | let mut first = true; | |
85aaf69f | 938 | for v in self { |
92a42be0 SL |
939 | if first { |
940 | first = false | |
941 | } else { | |
942 | result.push(sep.clone()) | |
943 | } | |
944 | result.extend_from_slice(v.borrow()) | |
1a4d82fc JJ |
945 | } |
946 | result | |
947 | } | |
c1a9b12d SL |
948 | |
949 | fn connect(&self, sep: &T) -> Vec<T> { | |
950 | self.join(sep) | |
951 | } | |
1a4d82fc JJ |
952 | } |
953 | ||
1a4d82fc JJ |
954 | //////////////////////////////////////////////////////////////////////////////// |
955 | // Standard trait implementations for slices | |
956 | //////////////////////////////////////////////////////////////////////////////// | |
957 | ||
85aaf69f SL |
958 | #[stable(feature = "rust1", since = "1.0.0")] |
959 | impl<T> Borrow<[T]> for Vec<T> { | |
92a42be0 SL |
960 | fn borrow(&self) -> &[T] { |
961 | &self[..] | |
962 | } | |
1a4d82fc JJ |
963 | } |
964 | ||
85aaf69f SL |
965 | #[stable(feature = "rust1", since = "1.0.0")] |
966 | impl<T> BorrowMut<[T]> for Vec<T> { | |
92a42be0 SL |
967 | fn borrow_mut(&mut self) -> &mut [T] { |
968 | &mut self[..] | |
969 | } | |
1a4d82fc JJ |
970 | } |
971 | ||
85aaf69f SL |
972 | #[stable(feature = "rust1", since = "1.0.0")] |
973 | impl<T: Clone> ToOwned for [T] { | |
974 | type Owned = Vec<T>; | |
c34b1796 | 975 | #[cfg(not(test))] |
92a42be0 SL |
976 | fn to_owned(&self) -> Vec<T> { |
977 | self.to_vec() | |
978 | } | |
c34b1796 AL |
979 | |
980 | // HACK(japaric): with cfg(test) the inherent `[T]::to_vec`, which is required for this method | |
981 | // definition, is not available. Since we don't require this method for testing purposes, I'll | |
982 | // just stub it | |
983 | // NB see the slice::hack module in slice.rs for more information | |
984 | #[cfg(test)] | |
92a42be0 SL |
985 | fn to_owned(&self) -> Vec<T> { |
986 | panic!("not available with cfg(test)") | |
987 | } | |
1a4d82fc JJ |
988 | } |
989 | ||
1a4d82fc JJ |
990 | //////////////////////////////////////////////////////////////////////////////// |
991 | // Sorting | |
992 | //////////////////////////////////////////////////////////////////////////////// | |
993 | ||
92a42be0 SL |
994 | fn insertion_sort<T, F>(v: &mut [T], mut compare: F) |
995 | where F: FnMut(&T, &T) -> Ordering | |
996 | { | |
85aaf69f | 997 | let len = v.len() as isize; |
1a4d82fc JJ |
998 | let buf_v = v.as_mut_ptr(); |
999 | ||
1000 | // 1 <= i < len; | |
85aaf69f | 1001 | for i in 1..len { |
1a4d82fc JJ |
1002 | // j satisfies: 0 <= j <= i; |
1003 | let mut j = i; | |
1004 | unsafe { | |
1005 | // `i` is in bounds. | |
1006 | let read_ptr = buf_v.offset(i) as *const T; | |
1007 | ||
1008 | // find where to insert, we need to do strict <, | |
1009 | // rather than <=, to maintain stability. | |
1010 | ||
1011 | // 0 <= j - 1 < len, so .offset(j - 1) is in bounds. | |
92a42be0 | 1012 | while j > 0 && compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less { |
1a4d82fc JJ |
1013 | j -= 1; |
1014 | } | |
1015 | ||
1016 | // shift everything to the right, to make space to | |
1017 | // insert this value. | |
1018 | ||
1019 | // j + 1 could be `len` (for the last `i`), but in | |
1020 | // that case, `i == j` so we don't copy. The | |
1021 | // `.offset(j)` is always in bounds. | |
1022 | ||
1023 | if i != j { | |
1024 | let tmp = ptr::read(read_ptr); | |
92a42be0 | 1025 | ptr::copy(&*buf_v.offset(j), buf_v.offset(j + 1), (i - j) as usize); |
c34b1796 | 1026 | ptr::copy_nonoverlapping(&tmp, buf_v.offset(j), 1); |
1a4d82fc JJ |
1027 | mem::forget(tmp); |
1028 | } | |
1029 | } | |
1030 | } | |
1031 | } | |
1032 | ||
92a42be0 SL |
1033 | fn merge_sort<T, F>(v: &mut [T], mut compare: F) |
1034 | where F: FnMut(&T, &T) -> Ordering | |
1035 | { | |
1a4d82fc | 1036 | // warning: this wildly uses unsafe. |
c34b1796 AL |
1037 | const BASE_INSERTION: usize = 32; |
1038 | const LARGE_INSERTION: usize = 16; | |
1a4d82fc JJ |
1039 | |
1040 | // FIXME #12092: smaller insertion runs seems to make sorting | |
1041 | // vectors of large elements a little faster on some platforms, | |
1042 | // but hasn't been tested/tuned extensively | |
1043 | let insertion = if size_of::<T>() <= 16 { | |
1044 | BASE_INSERTION | |
1045 | } else { | |
1046 | LARGE_INSERTION | |
1047 | }; | |
1048 | ||
1049 | let len = v.len(); | |
1050 | ||
1051 | // short vectors get sorted in-place via insertion sort to avoid allocations | |
1052 | if len <= insertion { | |
1053 | insertion_sort(v, compare); | |
1054 | return; | |
1055 | } | |
1056 | ||
1057 | // allocate some memory to use as scratch memory, we keep the | |
1058 | // length 0 so we can keep shallow copies of the contents of `v` | |
1059 | // without risking the dtors running on an object twice if | |
1060 | // `compare` panics. | |
1061 | let mut working_space = Vec::with_capacity(2 * len); | |
1062 | // these both are buffers of length `len`. | |
1063 | let mut buf_dat = working_space.as_mut_ptr(); | |
92a42be0 | 1064 | let mut buf_tmp = unsafe { buf_dat.offset(len as isize) }; |
1a4d82fc JJ |
1065 | |
1066 | // length `len`. | |
1067 | let buf_v = v.as_ptr(); | |
1068 | ||
1069 | // step 1. sort short runs with insertion sort. This takes the | |
1070 | // values from `v` and sorts them into `buf_dat`, leaving that | |
1071 | // with sorted runs of length INSERTION. | |
1072 | ||
1073 | // We could hardcode the sorting comparisons here, and we could | |
1074 | // manipulate/step the pointers themselves, rather than repeatedly | |
1075 | // .offset-ing. | |
92a42be0 | 1076 | for start in (0..len).step_by(insertion) { |
1a4d82fc | 1077 | // start <= i < len; |
85aaf69f | 1078 | for i in start..cmp::min(start + insertion, len) { |
1a4d82fc | 1079 | // j satisfies: start <= j <= i; |
85aaf69f | 1080 | let mut j = i as isize; |
1a4d82fc JJ |
1081 | unsafe { |
1082 | // `i` is in bounds. | |
85aaf69f | 1083 | let read_ptr = buf_v.offset(i as isize); |
1a4d82fc JJ |
1084 | |
1085 | // find where to insert, we need to do strict <, | |
1086 | // rather than <=, to maintain stability. | |
1087 | ||
1088 | // start <= j - 1 < len, so .offset(j - 1) is in | |
1089 | // bounds. | |
92a42be0 | 1090 | while j > start as isize && compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less { |
1a4d82fc JJ |
1091 | j -= 1; |
1092 | } | |
1093 | ||
1094 | // shift everything to the right, to make space to | |
1095 | // insert this value. | |
1096 | ||
1097 | // j + 1 could be `len` (for the last `i`), but in | |
1098 | // that case, `i == j` so we don't copy. The | |
1099 | // `.offset(j)` is always in bounds. | |
92a42be0 | 1100 | ptr::copy(&*buf_dat.offset(j), buf_dat.offset(j + 1), i - j as usize); |
c34b1796 | 1101 | ptr::copy_nonoverlapping(read_ptr, buf_dat.offset(j), 1); |
1a4d82fc JJ |
1102 | } |
1103 | } | |
1104 | } | |
1105 | ||
1106 | // step 2. merge the sorted runs. | |
1107 | let mut width = insertion; | |
1108 | while width < len { | |
1109 | // merge the sorted runs of length `width` in `buf_dat` two at | |
1110 | // a time, placing the result in `buf_tmp`. | |
1111 | ||
1112 | // 0 <= start <= len. | |
c34b1796 | 1113 | for start in (0..len).step_by(2 * width) { |
1a4d82fc JJ |
1114 | // manipulate pointers directly for speed (rather than |
1115 | // using a `for` loop with `range` and `.offset` inside | |
1116 | // that loop). | |
1117 | unsafe { | |
1118 | // the end of the first run & start of the | |
1119 | // second. Offset of `len` is defined, since this is | |
1120 | // precisely one byte past the end of the object. | |
85aaf69f | 1121 | let right_start = buf_dat.offset(cmp::min(start + width, len) as isize); |
1a4d82fc JJ |
1122 | // end of the second. Similar reasoning to the above re safety. |
1123 | let right_end_idx = cmp::min(start + 2 * width, len); | |
85aaf69f | 1124 | let right_end = buf_dat.offset(right_end_idx as isize); |
1a4d82fc JJ |
1125 | |
1126 | // the pointers to the elements under consideration | |
1127 | // from the two runs. | |
1128 | ||
1129 | // both of these are in bounds. | |
85aaf69f | 1130 | let mut left = buf_dat.offset(start as isize); |
1a4d82fc JJ |
1131 | let mut right = right_start; |
1132 | ||
1133 | // where we're putting the results, it is a run of | |
1134 | // length `2*width`, so we step it once for each step | |
1135 | // of either `left` or `right`. `buf_tmp` has length | |
1136 | // `len`, so these are in bounds. | |
85aaf69f SL |
1137 | let mut out = buf_tmp.offset(start as isize); |
1138 | let out_end = buf_tmp.offset(right_end_idx as isize); | |
1a4d82fc | 1139 | |
92a42be0 SL |
1140 | // If left[last] <= right[0], they are already in order: |
1141 | // fast-forward the left side (the right side is handled | |
1142 | // in the loop). | |
1143 | // If `right` is not empty then left is not empty, and | |
1144 | // the offsets are in bounds. | |
1145 | if right != right_end && compare(&*right.offset(-1), &*right) != Greater { | |
1146 | let elems = (right_start as usize - left as usize) / mem::size_of::<T>(); | |
1147 | ptr::copy_nonoverlapping(&*left, out, elems); | |
1148 | out = out.offset(elems as isize); | |
1149 | left = right_start; | |
1150 | } | |
1151 | ||
1a4d82fc JJ |
1152 | while out < out_end { |
1153 | // Either the left or the right run are exhausted, | |
1154 | // so just copy the remainder from the other run | |
1155 | // and move on; this gives a huge speed-up (order | |
1156 | // of 25%) for mostly sorted vectors (the best | |
1157 | // case). | |
1158 | if left == right_start { | |
1159 | // the number remaining in this run. | |
85aaf69f | 1160 | let elems = (right_end as usize - right as usize) / mem::size_of::<T>(); |
c34b1796 | 1161 | ptr::copy_nonoverlapping(&*right, out, elems); |
1a4d82fc JJ |
1162 | break; |
1163 | } else if right == right_end { | |
85aaf69f | 1164 | let elems = (right_start as usize - left as usize) / mem::size_of::<T>(); |
c34b1796 | 1165 | ptr::copy_nonoverlapping(&*left, out, elems); |
1a4d82fc JJ |
1166 | break; |
1167 | } | |
1168 | ||
1169 | // check which side is smaller, and that's the | |
1170 | // next element for the new run. | |
1171 | ||
1172 | // `left < right_start` and `right < right_end`, | |
1173 | // so these are valid. | |
1174 | let to_copy = if compare(&*left, &*right) == Greater { | |
1175 | step(&mut right) | |
1176 | } else { | |
1177 | step(&mut left) | |
1178 | }; | |
c34b1796 | 1179 | ptr::copy_nonoverlapping(&*to_copy, out, 1); |
1a4d82fc JJ |
1180 | step(&mut out); |
1181 | } | |
1182 | } | |
1183 | } | |
1184 | ||
1185 | mem::swap(&mut buf_dat, &mut buf_tmp); | |
1186 | ||
1187 | width *= 2; | |
1188 | } | |
1189 | ||
1190 | // write the result to `v` in one go, so that there are never two copies | |
1191 | // of the same object in `v`. | |
1192 | unsafe { | |
c34b1796 | 1193 | ptr::copy_nonoverlapping(&*buf_dat, v.as_mut_ptr(), len); |
1a4d82fc JJ |
1194 | } |
1195 | ||
1196 | // increment the pointer, returning the old pointer. | |
1197 | #[inline(always)] | |
1198 | unsafe fn step<T>(ptr: &mut *mut T) -> *mut T { | |
1199 | let old = *ptr; | |
1200 | *ptr = ptr.offset(1); | |
1201 | old | |
1202 | } | |
1203 | } |