src/libcollections/slice.rs

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