]> git.proxmox.com Git - rustc.git/blame - src/libcollections/slice.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / libcollections / slice.rs
CommitLineData
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 88use alloc::boxed::Box;
1a4d82fc 89use core::cmp::Ordering::{self, Greater, Less};
7453a54e 90use core::cmp;
1a4d82fc
JJ
91use core::mem::size_of;
92use core::mem;
1a4d82fc 93use core::ptr;
1a4d82fc 94use core::slice as core_slice;
1a4d82fc 95
85aaf69f 96use borrow::{Borrow, BorrowMut, ToOwned};
1a4d82fc
JJ
97use vec::Vec;
98
92a42be0 99#[stable(feature = "rust1", since = "1.0.0")]
9346a6ac 100pub use core::slice::{Chunks, Windows};
92a42be0 101#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 102pub use core::slice::{Iter, IterMut};
92a42be0 103#[stable(feature = "rust1", since = "1.0.0")]
e9174d1e 104pub use core::slice::{SplitMut, ChunksMut, Split};
92a42be0 105#[stable(feature = "rust1", since = "1.0.0")]
1a4d82fc 106pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut};
92a42be0 107#[stable(feature = "rust1", since = "1.0.0")]
85aaf69f 108pub 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)]
117pub 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)]
122pub 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
128mod 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 157impl<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 886pub 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
922impl<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")]
959impl<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")]
966impl<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")]
973impl<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
994fn 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
1033fn 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}