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