src/liballoc/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 //!
  83 //! [`Clone`]: ../../std/clone/trait.Clone.html
  84 //! [`Eq`]: ../../std/cmp/trait.Eq.html
  85 //! [`Ord`]: ../../std/cmp/trait.Ord.html
  86 //! [`Iter`]: struct.Iter.html
  87 //! [`Hash`]: ../../std/hash/trait.Hash.html
  88 //! [`.iter`]: ../../std/primitive.slice.html#method.iter
  89 //! [`.iter_mut`]: ../../std/primitive.slice.html#method.iter_mut
  90 //! [`.split`]: ../../std/primitive.slice.html#method.split
  91 //! [`.splitn`]: ../../std/primitive.slice.html#method.splitn
  92 //! [`.chunks`]: ../../std/primitive.slice.html#method.chunks
  93 //! [`.windows`]: ../../std/primitive.slice.html#method.windows
  94 #![stable(feature = "rust1", since = "1.0.0")]
  95
  96 // Many of the usings in this module are only used in the test configuration.
  97 // It's cleaner to just turn off the unused_imports warning than to fix them.
  98 #![cfg_attr(test, allow(unused_imports, dead_code))]
  99
 100 use core::cmp::Ordering::{self, Less};
 101 use core::mem::size_of;
 102 use core::mem;
 103 use core::ptr;
 104 use core::slice as core_slice;
 105
 106 use borrow::{Borrow, BorrowMut, ToOwned};
 107 use boxed::Box;
 108 use vec::Vec;
 109
 110 #[stable(feature = "rust1", since = "1.0.0")]
 111 pub use core::slice::{Chunks, Windows};
 112 #[stable(feature = "rust1", since = "1.0.0")]
 113 pub use core::slice::{Iter, IterMut};
 114 #[stable(feature = "rust1", since = "1.0.0")]
 115 pub use core::slice::{SplitMut, ChunksMut, Split};
 116 #[stable(feature = "rust1", since = "1.0.0")]
 117 pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut};
 118 #[unstable(feature = "slice_rsplit", issue = "41020")]
 119 pub use core::slice::{RSplit, RSplitMut};
 120 #[stable(feature = "rust1", since = "1.0.0")]
 121 pub use core::slice::{from_raw_parts, from_raw_parts_mut};
 122 #[unstable(feature = "from_ref", issue = "45703")]
 123 pub use core::slice::{from_ref, from_ref_mut};
 124 #[unstable(feature = "slice_get_slice", issue = "35729")]
 125 pub use core::slice::SliceIndex;
 126 #[unstable(feature = "exact_chunks", issue = "47115")]
 127 pub use core::slice::{ExactChunks, ExactChunksMut};
 128
 129 ////////////////////////////////////////////////////////////////////////////////
 130 // Basic slice extension methods
 131 ////////////////////////////////////////////////////////////////////////////////
 132
 133 // HACK(japaric) needed for the implementation of `vec!` macro during testing
 134 // NB see the hack module in this file for more details
 135 #[cfg(test)]
 136 pub use self::hack::into_vec;
 137
 138 // HACK(japaric) needed for the implementation of `Vec::clone` during testing
 139 // NB see the hack module in this file for more details
 140 #[cfg(test)]
 141 pub use self::hack::to_vec;
 142
 143 // HACK(japaric): With cfg(test) `impl [T]` is not available, these three
 144 // functions are actually methods that are in `impl [T]` but not in
 145 // `core::slice::SliceExt` - we need to supply these functions for the
 146 // `test_permutations` test
 147 mod hack {
 148     use boxed::Box;
 149     use core::mem;
 150
 151     #[cfg(test)]
 152     use string::ToString;
 153     use vec::Vec;
 154
 155     pub fn into_vec<T>(mut b: Box<[T]>) -> Vec<T> {
 156         unsafe {
 157             let xs = Vec::from_raw_parts(b.as_mut_ptr(), b.len(), b.len());
 158             mem::forget(b);
 159             xs
 160         }
 161     }
 162
 163     #[inline]
 164     pub fn to_vec<T>(s: &[T]) -> Vec<T>
 165         where T: Clone
 166     {
 167         let mut vector = Vec::with_capacity(s.len());
 168         vector.extend_from_slice(s);
 169         vector
 170     }
 171 }
 172
 173 #[lang = "slice"]
 174 #[cfg(not(test))]
 175 impl<T> [T] {
 176     /// Returns the number of elements in the slice.
 177     ///
 178     /// # Examples
 179     ///
 180     /// ```
 181     /// let a = [1, 2, 3];
 182     /// assert_eq!(a.len(), 3);
 183     /// ```
 184     #[stable(feature = "rust1", since = "1.0.0")]
 185     #[inline]
 186     pub fn len(&self) -> usize {
 187         core_slice::SliceExt::len(self)
 188     }
 189
 190     /// Returns `true` if the slice has a length of 0.
 191     ///
 192     /// # Examples
 193     ///
 194     /// ```
 195     /// let a = [1, 2, 3];
 196     /// assert!(!a.is_empty());
 197     /// ```
 198     #[stable(feature = "rust1", since = "1.0.0")]
 199     #[inline]
 200     pub fn is_empty(&self) -> bool {
 201         core_slice::SliceExt::is_empty(self)
 202     }
 203
 204     /// Returns the first element of the slice, or `None` if it is empty.
 205     ///
 206     /// # Examples
 207     ///
 208     /// ```
 209     /// let v = [10, 40, 30];
 210     /// assert_eq!(Some(&10), v.first());
 211     ///
 212     /// let w: &[i32] = &[];
 213     /// assert_eq!(None, w.first());
 214     /// ```
 215     #[stable(feature = "rust1", since = "1.0.0")]
 216     #[inline]
 217     pub fn first(&self) -> Option<&T> {
 218         core_slice::SliceExt::first(self)
 219     }
 220
 221     /// Returns a mutable pointer to the first element of the slice, or `None` if it is empty.
 222     ///
 223     /// # Examples
 224     ///
 225     /// ```
 226     /// let x = &mut [0, 1, 2];
 227     ///
 228     /// if let Some(first) = x.first_mut() {
 229     ///     *first = 5;
 230     /// }
 231     /// assert_eq!(x, &[5, 1, 2]);
 232     /// ```
 233     #[stable(feature = "rust1", since = "1.0.0")]
 234     #[inline]
 235     pub fn first_mut(&mut self) -> Option<&mut T> {
 236         core_slice::SliceExt::first_mut(self)
 237     }
 238
 239     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
 240     ///
 241     /// # Examples
 242     ///
 243     /// ```
 244     /// let x = &[0, 1, 2];
 245     ///
 246     /// if let Some((first, elements)) = x.split_first() {
 247     ///     assert_eq!(first, &0);
 248     ///     assert_eq!(elements, &[1, 2]);
 249     /// }
 250     /// ```
 251     #[stable(feature = "slice_splits", since = "1.5.0")]
 252     #[inline]
 253     pub fn split_first(&self) -> Option<(&T, &[T])> {
 254         core_slice::SliceExt::split_first(self)
 255     }
 256
 257     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
 258     ///
 259     /// # Examples
 260     ///
 261     /// ```
 262     /// let x = &mut [0, 1, 2];
 263     ///
 264     /// if let Some((first, elements)) = x.split_first_mut() {
 265     ///     *first = 3;
 266     ///     elements[0] = 4;
 267     ///     elements[1] = 5;
 268     /// }
 269     /// assert_eq!(x, &[3, 4, 5]);
 270     /// ```
 271     #[stable(feature = "slice_splits", since = "1.5.0")]
 272     #[inline]
 273     pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 274         core_slice::SliceExt::split_first_mut(self)
 275     }
 276
 277     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
 278     ///
 279     /// # Examples
 280     ///
 281     /// ```
 282     /// let x = &[0, 1, 2];
 283     ///
 284     /// if let Some((last, elements)) = x.split_last() {
 285     ///     assert_eq!(last, &2);
 286     ///     assert_eq!(elements, &[0, 1]);
 287     /// }
 288     /// ```
 289     #[stable(feature = "slice_splits", since = "1.5.0")]
 290     #[inline]
 291     pub fn split_last(&self) -> Option<(&T, &[T])> {
 292         core_slice::SliceExt::split_last(self)
 293
 294     }
 295
 296     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
 297     ///
 298     /// # Examples
 299     ///
 300     /// ```
 301     /// let x = &mut [0, 1, 2];
 302     ///
 303     /// if let Some((last, elements)) = x.split_last_mut() {
 304     ///     *last = 3;
 305     ///     elements[0] = 4;
 306     ///     elements[1] = 5;
 307     /// }
 308     /// assert_eq!(x, &[4, 5, 3]);
 309     /// ```
 310     #[stable(feature = "slice_splits", since = "1.5.0")]
 311     #[inline]
 312     pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 313         core_slice::SliceExt::split_last_mut(self)
 314     }
 315
 316     /// Returns the last element of the slice, or `None` if it is empty.
 317     ///
 318     /// # Examples
 319     ///
 320     /// ```
 321     /// let v = [10, 40, 30];
 322     /// assert_eq!(Some(&30), v.last());
 323     ///
 324     /// let w: &[i32] = &[];
 325     /// assert_eq!(None, w.last());
 326     /// ```
 327     #[stable(feature = "rust1", since = "1.0.0")]
 328     #[inline]
 329     pub fn last(&self) -> Option<&T> {
 330         core_slice::SliceExt::last(self)
 331     }
 332
 333     /// Returns a mutable pointer to the last item in the slice.
 334     ///
 335     /// # Examples
 336     ///
 337     /// ```
 338     /// let x = &mut [0, 1, 2];
 339     ///
 340     /// if let Some(last) = x.last_mut() {
 341     ///     *last = 10;
 342     /// }
 343     /// assert_eq!(x, &[0, 1, 10]);
 344     /// ```
 345     #[stable(feature = "rust1", since = "1.0.0")]
 346     #[inline]
 347     pub fn last_mut(&mut self) -> Option<&mut T> {
 348         core_slice::SliceExt::last_mut(self)
 349     }
 350
 351     /// Returns a reference to an element or subslice depending on the type of
 352     /// index.
 353     ///
 354     /// - If given a position, returns a reference to the element at that
 355     ///   position or `None` if out of bounds.
 356     /// - If given a range, returns the subslice corresponding to that range,
 357     ///   or `None` if out of bounds.
 358     ///
 359     /// # Examples
 360     ///
 361     /// ```
 362     /// let v = [10, 40, 30];
 363     /// assert_eq!(Some(&40), v.get(1));
 364     /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
 365     /// assert_eq!(None, v.get(3));
 366     /// assert_eq!(None, v.get(0..4));
 367     /// ```
 368     #[stable(feature = "rust1", since = "1.0.0")]
 369     #[inline]
 370     pub fn get<I>(&self, index: I) -> Option<&I::Output>
 371         where I: SliceIndex<Self>
 372     {
 373         core_slice::SliceExt::get(self, index)
 374     }
 375
 376     /// Returns a mutable reference to an element or subslice depending on the
 377     /// type of index (see [`get`]) or `None` if the index is out of bounds.
 378     ///
 379     /// [`get`]: #method.get
 380     ///
 381     /// # Examples
 382     ///
 383     /// ```
 384     /// let x = &mut [0, 1, 2];
 385     ///
 386     /// if let Some(elem) = x.get_mut(1) {
 387     ///     *elem = 42;
 388     /// }
 389     /// assert_eq!(x, &[0, 42, 2]);
 390     /// ```
 391     #[stable(feature = "rust1", since = "1.0.0")]
 392     #[inline]
 393     pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
 394         where I: SliceIndex<Self>
 395     {
 396         core_slice::SliceExt::get_mut(self, index)
 397     }
 398
 399     /// Returns a reference to an element or subslice, without doing bounds
 400     /// checking.
 401     ///
 402     /// This is generally not recommended, use with caution! For a safe
 403     /// alternative see [`get`].
 404     ///
 405     /// [`get`]: #method.get
 406     ///
 407     /// # Examples
 408     ///
 409     /// ```
 410     /// let x = &[1, 2, 4];
 411     ///
 412     /// unsafe {
 413     ///     assert_eq!(x.get_unchecked(1), &2);
 414     /// }
 415     /// ```
 416     #[stable(feature = "rust1", since = "1.0.0")]
 417     #[inline]
 418     pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
 419         where I: SliceIndex<Self>
 420     {
 421         core_slice::SliceExt::get_unchecked(self, index)
 422     }
 423
 424     /// Returns a mutable reference to an element or subslice, without doing
 425     /// bounds checking.
 426     ///
 427     /// This is generally not recommended, use with caution! For a safe
 428     /// alternative see [`get_mut`].
 429     ///
 430     /// [`get_mut`]: #method.get_mut
 431     ///
 432     /// # Examples
 433     ///
 434     /// ```
 435     /// let x = &mut [1, 2, 4];
 436     ///
 437     /// unsafe {
 438     ///     let elem = x.get_unchecked_mut(1);
 439     ///     *elem = 13;
 440     /// }
 441     /// assert_eq!(x, &[1, 13, 4]);
 442     /// ```
 443     #[stable(feature = "rust1", since = "1.0.0")]
 444     #[inline]
 445     pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
 446         where I: SliceIndex<Self>
 447     {
 448         core_slice::SliceExt::get_unchecked_mut(self, index)
 449     }
 450
 451     /// Returns a raw pointer to the slice's buffer.
 452     ///
 453     /// The caller must ensure that the slice outlives the pointer this
 454     /// function returns, or else it will end up pointing to garbage.
 455     ///
 456     /// Modifying the container referenced by this slice may cause its buffer
 457     /// to be reallocated, which would also make any pointers to it invalid.
 458     ///
 459     /// # Examples
 460     ///
 461     /// ```
 462     /// let x = &[1, 2, 4];
 463     /// let x_ptr = x.as_ptr();
 464     ///
 465     /// unsafe {
 466     ///     for i in 0..x.len() {
 467     ///         assert_eq!(x.get_unchecked(i), &*x_ptr.offset(i as isize));
 468     ///     }
 469     /// }
 470     /// ```
 471     #[stable(feature = "rust1", since = "1.0.0")]
 472     #[inline]
 473     pub fn as_ptr(&self) -> *const T {
 474         core_slice::SliceExt::as_ptr(self)
 475     }
 476
 477     /// Returns an unsafe mutable pointer to the slice's buffer.
 478     ///
 479     /// The caller must ensure that the slice outlives the pointer this
 480     /// function returns, or else it will end up pointing to garbage.
 481     ///
 482     /// Modifying the container referenced by this slice may cause its buffer
 483     /// to be reallocated, which would also make any pointers to it invalid.
 484     ///
 485     /// # Examples
 486     ///
 487     /// ```
 488     /// let x = &mut [1, 2, 4];
 489     /// let x_ptr = x.as_mut_ptr();
 490     ///
 491     /// unsafe {
 492     ///     for i in 0..x.len() {
 493     ///         *x_ptr.offset(i as isize) += 2;
 494     ///     }
 495     /// }
 496     /// assert_eq!(x, &[3, 4, 6]);
 497     /// ```
 498     #[stable(feature = "rust1", since = "1.0.0")]
 499     #[inline]
 500     pub fn as_mut_ptr(&mut self) -> *mut T {
 501         core_slice::SliceExt::as_mut_ptr(self)
 502     }
 503
 504     /// Swaps two elements in the slice.
 505     ///
 506     /// # Arguments
 507     ///
 508     /// * a - The index of the first element
 509     /// * b - The index of the second element
 510     ///
 511     /// # Panics
 512     ///
 513     /// Panics if `a` or `b` are out of bounds.
 514     ///
 515     /// # Examples
 516     ///
 517     /// ```
 518     /// let mut v = ["a", "b", "c", "d"];
 519     /// v.swap(1, 3);
 520     /// assert!(v == ["a", "d", "c", "b"]);
 521     /// ```
 522     #[stable(feature = "rust1", since = "1.0.0")]
 523     #[inline]
 524     pub fn swap(&mut self, a: usize, b: usize) {
 525         core_slice::SliceExt::swap(self, a, b)
 526     }
 527
 528     /// Reverses the order of elements in the slice, in place.
 529     ///
 530     /// # Examples
 531     ///
 532     /// ```
 533     /// let mut v = [1, 2, 3];
 534     /// v.reverse();
 535     /// assert!(v == [3, 2, 1]);
 536     /// ```
 537     #[stable(feature = "rust1", since = "1.0.0")]
 538     #[inline]
 539     pub fn reverse(&mut self) {
 540         core_slice::SliceExt::reverse(self)
 541     }
 542
 543     /// Returns an iterator over the slice.
 544     ///
 545     /// # Examples
 546     ///
 547     /// ```
 548     /// let x = &[1, 2, 4];
 549     /// let mut iterator = x.iter();
 550     ///
 551     /// assert_eq!(iterator.next(), Some(&1));
 552     /// assert_eq!(iterator.next(), Some(&2));
 553     /// assert_eq!(iterator.next(), Some(&4));
 554     /// assert_eq!(iterator.next(), None);
 555     /// ```
 556     #[stable(feature = "rust1", since = "1.0.0")]
 557     #[inline]
 558     pub fn iter(&self) -> Iter<T> {
 559         core_slice::SliceExt::iter(self)
 560     }
 561
 562     /// Returns an iterator that allows modifying each value.
 563     ///
 564     /// # Examples
 565     ///
 566     /// ```
 567     /// let x = &mut [1, 2, 4];
 568     /// for elem in x.iter_mut() {
 569     ///     *elem += 2;
 570     /// }
 571     /// assert_eq!(x, &[3, 4, 6]);
 572     /// ```
 573     #[stable(feature = "rust1", since = "1.0.0")]
 574     #[inline]
 575     pub fn iter_mut(&mut self) -> IterMut<T> {
 576         core_slice::SliceExt::iter_mut(self)
 577     }
 578
 579     /// Returns an iterator over all contiguous windows of length
 580     /// `size`. The windows overlap. If the slice is shorter than
 581     /// `size`, the iterator returns no values.
 582     ///
 583     /// # Panics
 584     ///
 585     /// Panics if `size` is 0.
 586     ///
 587     /// # Examples
 588     ///
 589     /// ```
 590     /// let slice = ['r', 'u', 's', 't'];
 591     /// let mut iter = slice.windows(2);
 592     /// assert_eq!(iter.next().unwrap(), &['r', 'u']);
 593     /// assert_eq!(iter.next().unwrap(), &['u', 's']);
 594     /// assert_eq!(iter.next().unwrap(), &['s', 't']);
 595     /// assert!(iter.next().is_none());
 596     /// ```
 597     ///
 598     /// If the slice is shorter than `size`:
 599     ///
 600     /// ```
 601     /// let slice = ['f', 'o', 'o'];
 602     /// let mut iter = slice.windows(4);
 603     /// assert!(iter.next().is_none());
 604     /// ```
 605     #[stable(feature = "rust1", since = "1.0.0")]
 606     #[inline]
 607     pub fn windows(&self, size: usize) -> Windows<T> {
 608         core_slice::SliceExt::windows(self, size)
 609     }
 610
 611     /// Returns an iterator over `chunk_size` elements of the slice at a
 612     /// time. The chunks are slices and do not overlap. If `chunk_size` does
 613     /// not divide the length of the slice, then the last chunk will
 614     /// not have length `chunk_size`.
 615     ///
 616     /// See [`exact_chunks`] for a variant of this iterator that returns chunks
 617     /// of always exactly `chunk_size` elements.
 618     ///
 619     /// # Panics
 620     ///
 621     /// Panics if `chunk_size` is 0.
 622     ///
 623     /// # Examples
 624     ///
 625     /// ```
 626     /// let slice = ['l', 'o', 'r', 'e', 'm'];
 627     /// let mut iter = slice.chunks(2);
 628     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
 629     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
 630     /// assert_eq!(iter.next().unwrap(), &['m']);
 631     /// assert!(iter.next().is_none());
 632     /// ```
 633     #[stable(feature = "rust1", since = "1.0.0")]
 634     #[inline]
 635     pub fn chunks(&self, chunk_size: usize) -> Chunks<T> {
 636         core_slice::SliceExt::chunks(self, chunk_size)
 637     }
 638
 639     /// Returns an iterator over `chunk_size` elements of the slice at a
 640     /// time. The chunks are slices and do not overlap. If `chunk_size` does
 641     /// not divide the length of the slice, then the last up to `chunk_size-1`
 642     /// elements will be omitted.
 643     ///
 644     /// Due to each chunk having exactly `chunk_size` elements, the compiler
 645     /// can often optimize the resulting code better than in the case of
 646     /// [`chunks`].
 647     ///
 648     /// # Panics
 649     ///
 650     /// Panics if `chunk_size` is 0.
 651     ///
 652     /// # Examples
 653     ///
 654     /// ```
 655     /// #![feature(exact_chunks)]
 656     ///
 657     /// let slice = ['l', 'o', 'r', 'e', 'm'];
 658     /// let mut iter = slice.exact_chunks(2);
 659     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
 660     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
 661     /// assert!(iter.next().is_none());
 662     /// ```
 663     #[unstable(feature = "exact_chunks", issue = "47115")]
 664     #[inline]
 665     pub fn exact_chunks(&self, chunk_size: usize) -> ExactChunks<T> {
 666         core_slice::SliceExt::exact_chunks(self, chunk_size)
 667     }
 668
 669     /// Returns an iterator over `chunk_size` elements of the slice at a time.
 670     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
 671     /// not divide the length of the slice, then the last chunk will not
 672     /// have length `chunk_size`.
 673     ///
 674     /// See [`exact_chunks_mut`] for a variant of this iterator that returns chunks
 675     /// of always exactly `chunk_size` elements.
 676     ///
 677     /// # Panics
 678     ///
 679     /// Panics if `chunk_size` is 0.
 680     ///
 681     /// # Examples
 682     ///
 683     /// ```
 684     /// let v = &mut [0, 0, 0, 0, 0];
 685     /// let mut count = 1;
 686     ///
 687     /// for chunk in v.chunks_mut(2) {
 688     ///     for elem in chunk.iter_mut() {
 689     ///         *elem += count;
 690     ///     }
 691     ///     count += 1;
 692     /// }
 693     /// assert_eq!(v, &[1, 1, 2, 2, 3]);
 694     /// ```
 695     #[stable(feature = "rust1", since = "1.0.0")]
 696     #[inline]
 697     pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
 698         core_slice::SliceExt::chunks_mut(self, chunk_size)
 699     }
 700
 701     /// Returns an iterator over `chunk_size` elements of the slice at a time.
 702     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
 703     /// not divide the length of the slice, then the last up to `chunk_size-1`
 704     /// elements will be omitted.
 705     ///
 706     ///
 707     /// Due to each chunk having exactly `chunk_size` elements, the compiler
 708     /// can often optimize the resulting code better than in the case of
 709     /// [`chunks_mut`].
 710     ///
 711     /// # Panics
 712     ///
 713     /// Panics if `chunk_size` is 0.
 714     ///
 715     /// # Examples
 716     ///
 717     /// ```
 718     /// #![feature(exact_chunks)]
 719     ///
 720     /// let v = &mut [0, 0, 0, 0, 0];
 721     /// let mut count = 1;
 722     ///
 723     /// for chunk in v.exact_chunks_mut(2) {
 724     ///     for elem in chunk.iter_mut() {
 725     ///         *elem += count;
 726     ///     }
 727     ///     count += 1;
 728     /// }
 729     /// assert_eq!(v, &[1, 1, 2, 2, 0]);
 730     /// ```
 731     #[unstable(feature = "exact_chunks", issue = "47115")]
 732     #[inline]
 733     pub fn exact_chunks_mut(&mut self, chunk_size: usize) -> ExactChunksMut<T> {
 734         core_slice::SliceExt::exact_chunks_mut(self, chunk_size)
 735     }
 736
 737     /// Divides one slice into two at an index.
 738     ///
 739     /// The first will contain all indices from `[0, mid)` (excluding
 740     /// the index `mid` itself) and the second will contain all
 741     /// indices from `[mid, len)` (excluding the index `len` itself).
 742     ///
 743     /// # Panics
 744     ///
 745     /// Panics if `mid > len`.
 746     ///
 747     /// # Examples
 748     ///
 749     /// ```
 750     /// let v = [1, 2, 3, 4, 5, 6];
 751     ///
 752     /// {
 753     ///    let (left, right) = v.split_at(0);
 754     ///    assert!(left == []);
 755     ///    assert!(right == [1, 2, 3, 4, 5, 6]);
 756     /// }
 757     ///
 758     /// {
 759     ///     let (left, right) = v.split_at(2);
 760     ///     assert!(left == [1, 2]);
 761     ///     assert!(right == [3, 4, 5, 6]);
 762     /// }
 763     ///
 764     /// {
 765     ///     let (left, right) = v.split_at(6);
 766     ///     assert!(left == [1, 2, 3, 4, 5, 6]);
 767     ///     assert!(right == []);
 768     /// }
 769     /// ```
 770     #[stable(feature = "rust1", since = "1.0.0")]
 771     #[inline]
 772     pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
 773         core_slice::SliceExt::split_at(self, mid)
 774     }
 775
 776     /// Divides one mutable slice into two at an index.
 777     ///
 778     /// The first will contain all indices from `[0, mid)` (excluding
 779     /// the index `mid` itself) and the second will contain all
 780     /// indices from `[mid, len)` (excluding the index `len` itself).
 781     ///
 782     /// # Panics
 783     ///
 784     /// Panics if `mid > len`.
 785     ///
 786     /// # Examples
 787     ///
 788     /// ```
 789     /// let mut v = [1, 0, 3, 0, 5, 6];
 790     /// // scoped to restrict the lifetime of the borrows
 791     /// {
 792     ///     let (left, right) = v.split_at_mut(2);
 793     ///     assert!(left == [1, 0]);
 794     ///     assert!(right == [3, 0, 5, 6]);
 795     ///     left[1] = 2;
 796     ///     right[1] = 4;
 797     /// }
 798     /// assert!(v == [1, 2, 3, 4, 5, 6]);
 799     /// ```
 800     #[stable(feature = "rust1", since = "1.0.0")]
 801     #[inline]
 802     pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
 803         core_slice::SliceExt::split_at_mut(self, mid)
 804     }
 805
 806     /// Returns an iterator over subslices separated by elements that match
 807     /// `pred`. The matched element is not contained in the subslices.
 808     ///
 809     /// # Examples
 810     ///
 811     /// ```
 812     /// let slice = [10, 40, 33, 20];
 813     /// let mut iter = slice.split(|num| num % 3 == 0);
 814     ///
 815     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
 816     /// assert_eq!(iter.next().unwrap(), &[20]);
 817     /// assert!(iter.next().is_none());
 818     /// ```
 819     ///
 820     /// If the first element is matched, an empty slice will be the first item
 821     /// returned by the iterator. Similarly, if the last element in the slice
 822     /// is matched, an empty slice will be the last item returned by the
 823     /// iterator:
 824     ///
 825     /// ```
 826     /// let slice = [10, 40, 33];
 827     /// let mut iter = slice.split(|num| num % 3 == 0);
 828     ///
 829     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
 830     /// assert_eq!(iter.next().unwrap(), &[]);
 831     /// assert!(iter.next().is_none());
 832     /// ```
 833     ///
 834     /// If two matched elements are directly adjacent, an empty slice will be
 835     /// present between them:
 836     ///
 837     /// ```
 838     /// let slice = [10, 6, 33, 20];
 839     /// let mut iter = slice.split(|num| num % 3 == 0);
 840     ///
 841     /// assert_eq!(iter.next().unwrap(), &[10]);
 842     /// assert_eq!(iter.next().unwrap(), &[]);
 843     /// assert_eq!(iter.next().unwrap(), &[20]);
 844     /// assert!(iter.next().is_none());
 845     /// ```
 846     #[stable(feature = "rust1", since = "1.0.0")]
 847     #[inline]
 848     pub fn split<F>(&self, pred: F) -> Split<T, F>
 849         where F: FnMut(&T) -> bool
 850     {
 851         core_slice::SliceExt::split(self, pred)
 852     }
 853
 854     /// Returns an iterator over mutable subslices separated by elements that
 855     /// match `pred`. The matched element is not contained in the subslices.
 856     ///
 857     /// # Examples
 858     ///
 859     /// ```
 860     /// let mut v = [10, 40, 30, 20, 60, 50];
 861     ///
 862     /// for group in v.split_mut(|num| *num % 3 == 0) {
 863     ///     group[0] = 1;
 864     /// }
 865     /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
 866     /// ```
 867     #[stable(feature = "rust1", since = "1.0.0")]
 868     #[inline]
 869     pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F>
 870         where F: FnMut(&T) -> bool
 871     {
 872         core_slice::SliceExt::split_mut(self, pred)
 873     }
 874
 875     /// Returns an iterator over subslices separated by elements that match
 876     /// `pred`, starting at the end of the slice and working backwards.
 877     /// The matched element is not contained in the subslices.
 878     ///
 879     /// # Examples
 880     ///
 881     /// ```
 882     /// #![feature(slice_rsplit)]
 883     ///
 884     /// let slice = [11, 22, 33, 0, 44, 55];
 885     /// let mut iter = slice.rsplit(|num| *num == 0);
 886     ///
 887     /// assert_eq!(iter.next().unwrap(), &[44, 55]);
 888     /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
 889     /// assert_eq!(iter.next(), None);
 890     /// ```
 891     ///
 892     /// As with `split()`, if the first or last element is matched, an empty
 893     /// slice will be the first (or last) item returned by the iterator.
 894     ///
 895     /// ```
 896     /// #![feature(slice_rsplit)]
 897     ///
 898     /// let v = &[0, 1, 1, 2, 3, 5, 8];
 899     /// let mut it = v.rsplit(|n| *n % 2 == 0);
 900     /// assert_eq!(it.next().unwrap(), &[]);
 901     /// assert_eq!(it.next().unwrap(), &[3, 5]);
 902     /// assert_eq!(it.next().unwrap(), &[1, 1]);
 903     /// assert_eq!(it.next().unwrap(), &[]);
 904     /// assert_eq!(it.next(), None);
 905     /// ```
 906     #[unstable(feature = "slice_rsplit", issue = "41020")]
 907     #[inline]
 908     pub fn rsplit<F>(&self, pred: F) -> RSplit<T, F>
 909         where F: FnMut(&T) -> bool
 910     {
 911         core_slice::SliceExt::rsplit(self, pred)
 912     }
 913
 914     /// Returns an iterator over mutable subslices separated by elements that
 915     /// match `pred`, starting at the end of the slice and working
 916     /// backwards. The matched element is not contained in the subslices.
 917     ///
 918     /// # Examples
 919     ///
 920     /// ```
 921     /// #![feature(slice_rsplit)]
 922     ///
 923     /// let mut v = [100, 400, 300, 200, 600, 500];
 924     ///
 925     /// let mut count = 0;
 926     /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
 927     ///     count += 1;
 928     ///     group[0] = count;
 929     /// }
 930     /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
 931     /// ```
 932     ///
 933     #[unstable(feature = "slice_rsplit", issue = "41020")]
 934     #[inline]
 935     pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<T, F>
 936         where F: FnMut(&T) -> bool
 937     {
 938         core_slice::SliceExt::rsplit_mut(self, pred)
 939     }
 940
 941     /// Returns an iterator over subslices separated by elements that match
 942     /// `pred`, limited to returning at most `n` items. The matched element is
 943     /// not contained in the subslices.
 944     ///
 945     /// The last element returned, if any, will contain the remainder of the
 946     /// slice.
 947     ///
 948     /// # Examples
 949     ///
 950     /// Print the slice split once by numbers divisible by 3 (i.e. `[10, 40]`,
 951     /// `[20, 60, 50]`):
 952     ///
 953     /// ```
 954     /// let v = [10, 40, 30, 20, 60, 50];
 955     ///
 956     /// for group in v.splitn(2, |num| *num % 3 == 0) {
 957     ///     println!("{:?}", group);
 958     /// }
 959     /// ```
 960     #[stable(feature = "rust1", since = "1.0.0")]
 961     #[inline]
 962     pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<T, F>
 963         where F: FnMut(&T) -> bool
 964     {
 965         core_slice::SliceExt::splitn(self, n, pred)
 966     }
 967
 968     /// Returns an iterator over subslices separated by elements that match
 969     /// `pred`, limited to returning at most `n` items. The matched element is
 970     /// not contained in the subslices.
 971     ///
 972     /// The last element returned, if any, will contain the remainder of the
 973     /// slice.
 974     ///
 975     /// # Examples
 976     ///
 977     /// ```
 978     /// let mut v = [10, 40, 30, 20, 60, 50];
 979     ///
 980     /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
 981     ///     group[0] = 1;
 982     /// }
 983     /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
 984     /// ```
 985     #[stable(feature = "rust1", since = "1.0.0")]
 986     #[inline]
 987     pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<T, F>
 988         where F: FnMut(&T) -> bool
 989     {
 990         core_slice::SliceExt::splitn_mut(self, n, pred)
 991     }
 992
 993     /// Returns an iterator over subslices separated by elements that match
 994     /// `pred` limited to returning at most `n` items. This starts at the end of
 995     /// the slice and works backwards.  The matched element is not contained in
 996     /// the subslices.
 997     ///
 998     /// The last element returned, if any, will contain the remainder of the
 999     /// slice.
1000     ///
1001     /// # Examples
1002     ///
1003     /// Print the slice split once, starting from the end, by numbers divisible
1004     /// by 3 (i.e. `[50]`, `[10, 40, 30, 20]`):
1005     ///
1006     /// ```
1007     /// let v = [10, 40, 30, 20, 60, 50];
1008     ///
1009     /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
1010     ///     println!("{:?}", group);
1011     /// }
1012     /// ```
1013     #[stable(feature = "rust1", since = "1.0.0")]
1014     #[inline]
1015     pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<T, F>
1016         where F: FnMut(&T) -> bool
1017     {
1018         core_slice::SliceExt::rsplitn(self, n, pred)
1019     }
1020
1021     /// Returns an iterator over subslices separated by elements that match
1022     /// `pred` limited to returning at most `n` items. This starts at the end of
1023     /// the slice and works backwards. The matched element is not contained in
1024     /// the subslices.
1025     ///
1026     /// The last element returned, if any, will contain the remainder of the
1027     /// slice.
1028     ///
1029     /// # Examples
1030     ///
1031     /// ```
1032     /// let mut s = [10, 40, 30, 20, 60, 50];
1033     ///
1034     /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
1035     ///     group[0] = 1;
1036     /// }
1037     /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
1038     /// ```
1039     #[stable(feature = "rust1", since = "1.0.0")]
1040     #[inline]
1041     pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<T, F>
1042         where F: FnMut(&T) -> bool
1043     {
1044         core_slice::SliceExt::rsplitn_mut(self, n, pred)
1045     }
1046
1047     /// Returns `true` if the slice contains an element with the given value.
1048     ///
1049     /// # Examples
1050     ///
1051     /// ```
1052     /// let v = [10, 40, 30];
1053     /// assert!(v.contains(&30));
1054     /// assert!(!v.contains(&50));
1055     /// ```
1056     #[stable(feature = "rust1", since = "1.0.0")]
1057     pub fn contains(&self, x: &T) -> bool
1058         where T: PartialEq
1059     {
1060         core_slice::SliceExt::contains(self, x)
1061     }
1062
1063     /// Returns `true` if `needle` is a prefix of the slice.
1064     ///
1065     /// # Examples
1066     ///
1067     /// ```
1068     /// let v = [10, 40, 30];
1069     /// assert!(v.starts_with(&[10]));
1070     /// assert!(v.starts_with(&[10, 40]));
1071     /// assert!(!v.starts_with(&[50]));
1072     /// assert!(!v.starts_with(&[10, 50]));
1073     /// ```
1074     ///
1075     /// Always returns `true` if `needle` is an empty slice:
1076     ///
1077     /// ```
1078     /// let v = &[10, 40, 30];
1079     /// assert!(v.starts_with(&[]));
1080     /// let v: &[u8] = &[];
1081     /// assert!(v.starts_with(&[]));
1082     /// ```
1083     #[stable(feature = "rust1", since = "1.0.0")]
1084     pub fn starts_with(&self, needle: &[T]) -> bool
1085         where T: PartialEq
1086     {
1087         core_slice::SliceExt::starts_with(self, needle)
1088     }
1089
1090     /// Returns `true` if `needle` is a suffix of the slice.
1091     ///
1092     /// # Examples
1093     ///
1094     /// ```
1095     /// let v = [10, 40, 30];
1096     /// assert!(v.ends_with(&[30]));
1097     /// assert!(v.ends_with(&[40, 30]));
1098     /// assert!(!v.ends_with(&[50]));
1099     /// assert!(!v.ends_with(&[50, 30]));
1100     /// ```
1101     ///
1102     /// Always returns `true` if `needle` is an empty slice:
1103     ///
1104     /// ```
1105     /// let v = &[10, 40, 30];
1106     /// assert!(v.ends_with(&[]));
1107     /// let v: &[u8] = &[];
1108     /// assert!(v.ends_with(&[]));
1109     /// ```
1110     #[stable(feature = "rust1", since = "1.0.0")]
1111     pub fn ends_with(&self, needle: &[T]) -> bool
1112         where T: PartialEq
1113     {
1114         core_slice::SliceExt::ends_with(self, needle)
1115     }
1116
1117     /// Binary searches this sorted slice for a given element.
1118     ///
1119     /// If the value is found then `Ok` is returned, containing the
1120     /// index of the matching element; if the value is not found then
1121     /// `Err` is returned, containing the index where a matching
1122     /// element could be inserted while maintaining sorted order.
1123     ///
1124     /// # Examples
1125     ///
1126     /// Looks up a series of four elements. The first is found, with a
1127     /// uniquely determined position; the second and third are not
1128     /// found; the fourth could match any position in `[1, 4]`.
1129     ///
1130     /// ```
1131     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1132     ///
1133     /// assert_eq!(s.binary_search(&13),  Ok(9));
1134     /// assert_eq!(s.binary_search(&4),   Err(7));
1135     /// assert_eq!(s.binary_search(&100), Err(13));
1136     /// let r = s.binary_search(&1);
1137     /// assert!(match r { Ok(1...4) => true, _ => false, });
1138     /// ```
1139     #[stable(feature = "rust1", since = "1.0.0")]
1140     pub fn binary_search(&self, x: &T) -> Result<usize, usize>
1141         where T: Ord
1142     {
1143         core_slice::SliceExt::binary_search(self, x)
1144     }
1145
1146     /// Binary searches this sorted slice with a comparator function.
1147     ///
1148     /// The comparator function should implement an order consistent
1149     /// with the sort order of the underlying slice, returning an
1150     /// order code that indicates whether its argument is `Less`,
1151     /// `Equal` or `Greater` the desired target.
1152     ///
1153     /// If a matching value is found then returns `Ok`, containing
1154     /// the index for the matched element; if no match is found then
1155     /// `Err` is returned, containing the index where a matching
1156     /// element could be inserted while maintaining sorted order.
1157     ///
1158     /// # Examples
1159     ///
1160     /// Looks up a series of four elements. The first is found, with a
1161     /// uniquely determined position; the second and third are not
1162     /// found; the fourth could match any position in `[1, 4]`.
1163     ///
1164     /// ```
1165     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1166     ///
1167     /// let seek = 13;
1168     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
1169     /// let seek = 4;
1170     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
1171     /// let seek = 100;
1172     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
1173     /// let seek = 1;
1174     /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
1175     /// assert!(match r { Ok(1...4) => true, _ => false, });
1176     /// ```
1177     #[stable(feature = "rust1", since = "1.0.0")]
1178     #[inline]
1179     pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>
1180         where F: FnMut(&'a T) -> Ordering
1181     {
1182         core_slice::SliceExt::binary_search_by(self, f)
1183     }
1184
1185     /// Binary searches this sorted slice with a key extraction function.
1186     ///
1187     /// Assumes that the slice is sorted by the key, for instance with
1188     /// [`sort_by_key`] using the same key extraction function.
1189     ///
1190     /// If a matching value is found then returns `Ok`, containing the
1191     /// index for the matched element; if no match is found then `Err`
1192     /// is returned, containing the index where a matching element could
1193     /// be inserted while maintaining sorted order.
1194     ///
1195     /// [`sort_by_key`]: #method.sort_by_key
1196     ///
1197     /// # Examples
1198     ///
1199     /// Looks up a series of four elements in a slice of pairs sorted by
1200     /// their second elements. The first is found, with a uniquely
1201     /// determined position; the second and third are not found; the
1202     /// fourth could match any position in `[1, 4]`.
1203     ///
1204     /// ```
1205     /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
1206     ///          (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
1207     ///          (1, 21), (2, 34), (4, 55)];
1208     ///
1209     /// assert_eq!(s.binary_search_by_key(&13, |&(a,b)| b),  Ok(9));
1210     /// assert_eq!(s.binary_search_by_key(&4, |&(a,b)| b),   Err(7));
1211     /// assert_eq!(s.binary_search_by_key(&100, |&(a,b)| b), Err(13));
1212     /// let r = s.binary_search_by_key(&1, |&(a,b)| b);
1213     /// assert!(match r { Ok(1...4) => true, _ => false, });
1214     /// ```
1215     #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
1216     #[inline]
1217     pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, f: F) -> Result<usize, usize>
1218         where F: FnMut(&'a T) -> B,
1219               B: Ord
1220     {
1221         core_slice::SliceExt::binary_search_by_key(self, b, f)
1222     }
1223
1224     /// Sorts the slice.
1225     ///
1226     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1227     ///
1228     /// When applicable, unstable sorting is preferred because it is generally faster than stable
1229     /// sorting and it doesn't allocate auxiliary memory.
1230     /// See [`sort_unstable`](#method.sort_unstable).
1231     ///
1232     /// # Current implementation
1233     ///
1234     /// The current algorithm is an adaptive, iterative merge sort inspired by
1235     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1236     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1237     /// two or more sorted sequences concatenated one after another.
1238     ///
1239     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1240     /// non-allocating insertion sort is used instead.
1241     ///
1242     /// # Examples
1243     ///
1244     /// ```
1245     /// let mut v = [-5, 4, 1, -3, 2];
1246     ///
1247     /// v.sort();
1248     /// assert!(v == [-5, -3, 1, 2, 4]);
1249     /// ```
1250     #[stable(feature = "rust1", since = "1.0.0")]
1251     #[inline]
1252     pub fn sort(&mut self)
1253         where T: Ord
1254     {
1255         merge_sort(self, |a, b| a.lt(b));
1256     }
1257
1258     /// Sorts the slice with a comparator function.
1259     ///
1260     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1261     ///
1262     /// When applicable, unstable sorting is preferred because it is generally faster than stable
1263     /// sorting and it doesn't allocate auxiliary memory.
1264     /// See [`sort_unstable_by`](#method.sort_unstable_by).
1265     ///
1266     /// # Current implementation
1267     ///
1268     /// The current algorithm is an adaptive, iterative merge sort inspired by
1269     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1270     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1271     /// two or more sorted sequences concatenated one after another.
1272     ///
1273     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1274     /// non-allocating insertion sort is used instead.
1275     ///
1276     /// # Examples
1277     ///
1278     /// ```
1279     /// let mut v = [5, 4, 1, 3, 2];
1280     /// v.sort_by(|a, b| a.cmp(b));
1281     /// assert!(v == [1, 2, 3, 4, 5]);
1282     ///
1283     /// // reverse sorting
1284     /// v.sort_by(|a, b| b.cmp(a));
1285     /// assert!(v == [5, 4, 3, 2, 1]);
1286     /// ```
1287     #[stable(feature = "rust1", since = "1.0.0")]
1288     #[inline]
1289     pub fn sort_by<F>(&mut self, mut compare: F)
1290         where F: FnMut(&T, &T) -> Ordering
1291     {
1292         merge_sort(self, |a, b| compare(a, b) == Less);
1293     }
1294
1295     /// Sorts the slice with a key extraction function.
1296     ///
1297     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1298     ///
1299     /// When applicable, unstable sorting is preferred because it is generally faster than stable
1300     /// sorting and it doesn't allocate auxiliary memory.
1301     /// See [`sort_unstable_by_key`](#method.sort_unstable_by_key).
1302     ///
1303     /// # Current implementation
1304     ///
1305     /// The current algorithm is an adaptive, iterative merge sort inspired by
1306     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1307     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1308     /// two or more sorted sequences concatenated one after another.
1309     ///
1310     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1311     /// non-allocating insertion sort is used instead.
1312     ///
1313     /// # Examples
1314     ///
1315     /// ```
1316     /// let mut v = [-5i32, 4, 1, -3, 2];
1317     ///
1318     /// v.sort_by_key(|k| k.abs());
1319     /// assert!(v == [1, 2, -3, 4, -5]);
1320     /// ```
1321     #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
1322     #[inline]
1323     pub fn sort_by_key<B, F>(&mut self, mut f: F)
1324         where F: FnMut(&T) -> B, B: Ord
1325     {
1326         merge_sort(self, |a, b| f(a).lt(&f(b)));
1327     }
1328
1329     /// Sorts the slice, but may not preserve the order of equal elements.
1330     ///
1331     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1332     /// and `O(n log n)` worst-case.
1333     ///
1334     /// # Current implementation
1335     ///
1336     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1337     /// which combines the fast average case of randomized quicksort with the fast worst case of
1338     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1339     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1340     /// deterministic behavior.
1341     ///
1342     /// It is typically faster than stable sorting, except in a few special cases, e.g. when the
1343     /// slice consists of several concatenated sorted sequences.
1344     ///
1345     /// # Examples
1346     ///
1347     /// ```
1348     /// let mut v = [-5, 4, 1, -3, 2];
1349     ///
1350     /// v.sort_unstable();
1351     /// assert!(v == [-5, -3, 1, 2, 4]);
1352     /// ```
1353     ///
1354     /// [pdqsort]: https://github.com/orlp/pdqsort
1355     #[stable(feature = "sort_unstable", since = "1.20.0")]
1356     #[inline]
1357     pub fn sort_unstable(&mut self)
1358         where T: Ord
1359     {
1360         core_slice::SliceExt::sort_unstable(self);
1361     }
1362
1363     /// Sorts the slice with a comparator function, but may not preserve the order of equal
1364     /// elements.
1365     ///
1366     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1367     /// and `O(n log n)` worst-case.
1368     ///
1369     /// # Current implementation
1370     ///
1371     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1372     /// which combines the fast average case of randomized quicksort with the fast worst case of
1373     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1374     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1375     /// deterministic behavior.
1376     ///
1377     /// It is typically faster than stable sorting, except in a few special cases, e.g. when the
1378     /// slice consists of several concatenated sorted sequences.
1379     ///
1380     /// # Examples
1381     ///
1382     /// ```
1383     /// let mut v = [5, 4, 1, 3, 2];
1384     /// v.sort_unstable_by(|a, b| a.cmp(b));
1385     /// assert!(v == [1, 2, 3, 4, 5]);
1386     ///
1387     /// // reverse sorting
1388     /// v.sort_unstable_by(|a, b| b.cmp(a));
1389     /// assert!(v == [5, 4, 3, 2, 1]);
1390     /// ```
1391     ///
1392     /// [pdqsort]: https://github.com/orlp/pdqsort
1393     #[stable(feature = "sort_unstable", since = "1.20.0")]
1394     #[inline]
1395     pub fn sort_unstable_by<F>(&mut self, compare: F)
1396         where F: FnMut(&T, &T) -> Ordering
1397     {
1398         core_slice::SliceExt::sort_unstable_by(self, compare);
1399     }
1400
1401     /// Sorts the slice with a key extraction function, but may not preserve the order of equal
1402     /// elements.
1403     ///
1404     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1405     /// and `O(n log n)` worst-case.
1406     ///
1407     /// # Current implementation
1408     ///
1409     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1410     /// which combines the fast average case of randomized quicksort with the fast worst case of
1411     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1412     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1413     /// deterministic behavior.
1414     ///
1415     /// It is typically faster than stable sorting, except in a few special cases, e.g. when the
1416     /// slice consists of several concatenated sorted sequences.
1417     ///
1418     /// # Examples
1419     ///
1420     /// ```
1421     /// let mut v = [-5i32, 4, 1, -3, 2];
1422     ///
1423     /// v.sort_unstable_by_key(|k| k.abs());
1424     /// assert!(v == [1, 2, -3, 4, -5]);
1425     /// ```
1426     ///
1427     /// [pdqsort]: https://github.com/orlp/pdqsort
1428     #[stable(feature = "sort_unstable", since = "1.20.0")]
1429     #[inline]
1430     pub fn sort_unstable_by_key<B, F>(&mut self, f: F)
1431         where F: FnMut(&T) -> B,
1432               B: Ord
1433     {
1434         core_slice::SliceExt::sort_unstable_by_key(self, f);
1435     }
1436
1437     /// Rotates the slice in-place such that the first `mid` elements of the
1438     /// slice move to the end while the last `self.len() - mid` elements move to
1439     /// the front. After calling `rotate_left`, the element previously at index
1440     /// `mid` will become the first element in the slice.
1441     ///
1442     /// # Panics
1443     ///
1444     /// This function will panic if `mid` is greater than the length of the
1445     /// slice. Note that `mid == self.len()` does _not_ panic and is a no-op
1446     /// rotation.
1447     ///
1448     /// # Complexity
1449     ///
1450     /// Takes linear (in `self.len()`) time.
1451     ///
1452     /// # Examples
1453     ///
1454     /// ```
1455     /// #![feature(slice_rotate)]
1456     ///
1457     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1458     /// a.rotate_left(2);
1459     /// assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
1460     /// ```
1461     ///
1462     /// Rotating a subslice:
1463     ///
1464     /// ```
1465     /// #![feature(slice_rotate)]
1466     ///
1467     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1468     /// a[1..5].rotate_left(1);
1469     /// assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);
1470     /// ```
1471     #[unstable(feature = "slice_rotate", issue = "41891")]
1472     pub fn rotate_left(&mut self, mid: usize) {
1473         core_slice::SliceExt::rotate_left(self, mid);
1474     }
1475
1476     #[unstable(feature = "slice_rotate", issue = "41891")]
1477     #[rustc_deprecated(since = "", reason = "renamed to `rotate_left`")]
1478     pub fn rotate(&mut self, mid: usize) {
1479         core_slice::SliceExt::rotate_left(self, mid);
1480     }
1481
1482     /// Rotates the slice in-place such that the first `self.len() - k`
1483     /// elements of the slice move to the end while the last `k` elements move
1484     /// to the front. After calling `rotate_right`, the element previously at
1485     /// index `self.len() - k` will become the first element in the slice.
1486     ///
1487     /// # Panics
1488     ///
1489     /// This function will panic if `k` is greater than the length of the
1490     /// slice. Note that `k == self.len()` does _not_ panic and is a no-op
1491     /// rotation.
1492     ///
1493     /// # Complexity
1494     ///
1495     /// Takes linear (in `self.len()`) time.
1496     ///
1497     /// # Examples
1498     ///
1499     /// ```
1500     /// #![feature(slice_rotate)]
1501     ///
1502     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1503     /// a.rotate_right(2);
1504     /// assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
1505     /// ```
1506     ///
1507     /// Rotate a subslice:
1508     ///
1509     /// ```
1510     /// #![feature(slice_rotate)]
1511     ///
1512     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1513     /// a[1..5].rotate_right(1);
1514     /// assert_eq!(a, ['a', 'e', 'b', 'c', 'd', 'f']);
1515     /// ```
1516     #[unstable(feature = "slice_rotate", issue = "41891")]
1517     pub fn rotate_right(&mut self, k: usize) {
1518         core_slice::SliceExt::rotate_right(self, k);
1519     }
1520
1521     /// Copies the elements from `src` into `self`.
1522     ///
1523     /// The length of `src` must be the same as `self`.
1524     ///
1525     /// If `src` implements `Copy`, it can be more performant to use
1526     /// [`copy_from_slice`].
1527     ///
1528     /// # Panics
1529     ///
1530     /// This function will panic if the two slices have different lengths.
1531     ///
1532     /// # Examples
1533     ///
1534     /// Cloning two elements from a slice into another:
1535     ///
1536     /// ```
1537     /// let src = [1, 2, 3, 4];
1538     /// let mut dst = [0, 0];
1539     ///
1540     /// dst.clone_from_slice(&src[2..]);
1541     ///
1542     /// assert_eq!(src, [1, 2, 3, 4]);
1543     /// assert_eq!(dst, [3, 4]);
1544     /// ```
1545     ///
1546     /// Rust enforces that there can only be one mutable reference with no
1547     /// immutable references to a particular piece of data in a particular
1548     /// scope. Because of this, attempting to use `clone_from_slice` on a
1549     /// single slice will result in a compile failure:
1550     ///
1551     /// ```compile_fail
1552     /// let mut slice = [1, 2, 3, 4, 5];
1553     ///
1554     /// slice[..2].clone_from_slice(&slice[3..]); // compile fail!
1555     /// ```
1556     ///
1557     /// To work around this, we can use [`split_at_mut`] to create two distinct
1558     /// sub-slices from a slice:
1559     ///
1560     /// ```
1561     /// let mut slice = [1, 2, 3, 4, 5];
1562     ///
1563     /// {
1564     ///     let (left, right) = slice.split_at_mut(2);
1565     ///     left.clone_from_slice(&right[1..]);
1566     /// }
1567     ///
1568     /// assert_eq!(slice, [4, 5, 3, 4, 5]);
1569     /// ```
1570     ///
1571     /// [`copy_from_slice`]: #method.copy_from_slice
1572     /// [`split_at_mut`]: #method.split_at_mut
1573     #[stable(feature = "clone_from_slice", since = "1.7.0")]
1574     pub fn clone_from_slice(&mut self, src: &[T]) where T: Clone {
1575         core_slice::SliceExt::clone_from_slice(self, src)
1576     }
1577
1578     /// Copies all elements from `src` into `self`, using a memcpy.
1579     ///
1580     /// The length of `src` must be the same as `self`.
1581     ///
1582     /// If `src` does not implement `Copy`, use [`clone_from_slice`].
1583     ///
1584     /// # Panics
1585     ///
1586     /// This function will panic if the two slices have different lengths.
1587     ///
1588     /// # Examples
1589     ///
1590     /// Copying two elements from a slice into another:
1591     ///
1592     /// ```
1593     /// let src = [1, 2, 3, 4];
1594     /// let mut dst = [0, 0];
1595     ///
1596     /// dst.copy_from_slice(&src[2..]);
1597     ///
1598     /// assert_eq!(src, [1, 2, 3, 4]);
1599     /// assert_eq!(dst, [3, 4]);
1600     /// ```
1601     ///
1602     /// Rust enforces that there can only be one mutable reference with no
1603     /// immutable references to a particular piece of data in a particular
1604     /// scope. Because of this, attempting to use `copy_from_slice` on a
1605     /// single slice will result in a compile failure:
1606     ///
1607     /// ```compile_fail
1608     /// let mut slice = [1, 2, 3, 4, 5];
1609     ///
1610     /// slice[..2].copy_from_slice(&slice[3..]); // compile fail!
1611     /// ```
1612     ///
1613     /// To work around this, we can use [`split_at_mut`] to create two distinct
1614     /// sub-slices from a slice:
1615     ///
1616     /// ```
1617     /// let mut slice = [1, 2, 3, 4, 5];
1618     ///
1619     /// {
1620     ///     let (left, right) = slice.split_at_mut(2);
1621     ///     left.copy_from_slice(&right[1..]);
1622     /// }
1623     ///
1624     /// assert_eq!(slice, [4, 5, 3, 4, 5]);
1625     /// ```
1626     ///
1627     /// [`clone_from_slice`]: #method.clone_from_slice
1628     /// [`split_at_mut`]: #method.split_at_mut
1629     #[stable(feature = "copy_from_slice", since = "1.9.0")]
1630     pub fn copy_from_slice(&mut self, src: &[T]) where T: Copy {
1631         core_slice::SliceExt::copy_from_slice(self, src)
1632     }
1633
1634     /// Swaps all elements in `self` with those in `other`.
1635     ///
1636     /// The length of `other` must be the same as `self`.
1637     ///
1638     /// # Panics
1639     ///
1640     /// This function will panic if the two slices have different lengths.
1641     ///
1642     /// # Example
1643     ///
1644     /// Swapping two elements across slices:
1645     ///
1646     /// ```
1647     /// #![feature(swap_with_slice)]
1648     ///
1649     /// let mut slice1 = [0, 0];
1650     /// let mut slice2 = [1, 2, 3, 4];
1651     ///
1652     /// slice1.swap_with_slice(&mut slice2[2..]);
1653     ///
1654     /// assert_eq!(slice1, [3, 4]);
1655     /// assert_eq!(slice2, [1, 2, 0, 0]);
1656     /// ```
1657     ///
1658     /// Rust enforces that there can only be one mutable reference to a
1659     /// particular piece of data in a particular scope. Because of this,
1660     /// attempting to use `swap_with_slice` on a single slice will result in
1661     /// a compile failure:
1662     ///
1663     /// ```compile_fail
1664     /// #![feature(swap_with_slice)]
1665     ///
1666     /// let mut slice = [1, 2, 3, 4, 5];
1667     /// slice[..2].swap_with_slice(&mut slice[3..]); // compile fail!
1668     /// ```
1669     ///
1670     /// To work around this, we can use [`split_at_mut`] to create two distinct
1671     /// mutable sub-slices from a slice:
1672     ///
1673     /// ```
1674     /// #![feature(swap_with_slice)]
1675     ///
1676     /// let mut slice = [1, 2, 3, 4, 5];
1677     ///
1678     /// {
1679     ///     let (left, right) = slice.split_at_mut(2);
1680     ///     left.swap_with_slice(&mut right[1..]);
1681     /// }
1682     ///
1683     /// assert_eq!(slice, [4, 5, 3, 1, 2]);
1684     /// ```
1685     ///
1686     /// [`split_at_mut`]: #method.split_at_mut
1687     #[unstable(feature = "swap_with_slice", issue = "44030")]
1688     pub fn swap_with_slice(&mut self, other: &mut [T]) {
1689         core_slice::SliceExt::swap_with_slice(self, other)
1690     }
1691
1692     /// Copies `self` into a new `Vec`.
1693     ///
1694     /// # Examples
1695     ///
1696     /// ```
1697     /// let s = [10, 40, 30];
1698     /// let x = s.to_vec();
1699     /// // Here, `s` and `x` can be modified independently.
1700     /// ```
1701     #[rustc_conversion_suggestion]
1702     #[stable(feature = "rust1", since = "1.0.0")]
1703     #[inline]
1704     pub fn to_vec(&self) -> Vec<T>
1705         where T: Clone
1706     {
1707         // NB see hack module in this file
1708         hack::to_vec(self)
1709     }
1710
1711     /// Converts `self` into a vector without clones or allocation.
1712     ///
1713     /// The resulting vector can be converted back into a box via
1714     /// `Vec<T>`'s `into_boxed_slice` method.
1715     ///
1716     /// # Examples
1717     ///
1718     /// ```
1719     /// let s: Box<[i32]> = Box::new([10, 40, 30]);
1720     /// let x = s.into_vec();
1721     /// // `s` cannot be used anymore because it has been converted into `x`.
1722     ///
1723     /// assert_eq!(x, vec![10, 40, 30]);
1724     /// ```
1725     #[stable(feature = "rust1", since = "1.0.0")]
1726     #[inline]
1727     pub fn into_vec(self: Box<Self>) -> Vec<T> {
1728         // NB see hack module in this file
1729         hack::into_vec(self)
1730     }
1731 }
1732
1733 #[lang = "slice_u8"]
1734 #[cfg(not(test))]
1735 impl [u8] {
1736     /// Checks if all bytes in this slice are within the ASCII range.
1737     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1738     #[inline]
1739     pub fn is_ascii(&self) -> bool {
1740         self.iter().all(|b| b.is_ascii())
1741     }
1742
1743     /// Returns a vector containing a copy of this slice where each byte
1744     /// is mapped to its ASCII upper case equivalent.
1745     ///
1746     /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
1747     /// but non-ASCII letters are unchanged.
1748     ///
1749     /// To uppercase the value in-place, use [`make_ascii_uppercase`].
1750     ///
1751     /// [`make_ascii_uppercase`]: #method.make_ascii_uppercase
1752     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1753     #[inline]
1754     pub fn to_ascii_uppercase(&self) -> Vec<u8> {
1755         let mut me = self.to_vec();
1756         me.make_ascii_uppercase();
1757         me
1758     }
1759
1760     /// Returns a vector containing a copy of this slice where each byte
1761     /// is mapped to its ASCII lower case equivalent.
1762     ///
1763     /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
1764     /// but non-ASCII letters are unchanged.
1765     ///
1766     /// To lowercase the value in-place, use [`make_ascii_lowercase`].
1767     ///
1768     /// [`make_ascii_lowercase`]: #method.make_ascii_lowercase
1769     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1770     #[inline]
1771     pub fn to_ascii_lowercase(&self) -> Vec<u8> {
1772         let mut me = self.to_vec();
1773         me.make_ascii_lowercase();
1774         me
1775     }
1776
1777     /// Checks that two slices are an ASCII case-insensitive match.
1778     ///
1779     /// Same as `to_ascii_lowercase(a) == to_ascii_lowercase(b)`,
1780     /// but without allocating and copying temporaries.
1781     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1782     #[inline]
1783     pub fn eq_ignore_ascii_case(&self, other: &[u8]) -> bool {
1784         self.len() == other.len() &&
1785             self.iter().zip(other).all(|(a, b)| {
1786                 a.eq_ignore_ascii_case(b)
1787             })
1788     }
1789
1790     /// Converts this slice to its ASCII upper case equivalent in-place.
1791     ///
1792     /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
1793     /// but non-ASCII letters are unchanged.
1794     ///
1795     /// To return a new uppercased value without modifying the existing one, use
1796     /// [`to_ascii_uppercase`].
1797     ///
1798     /// [`to_ascii_uppercase`]: #method.to_ascii_uppercase
1799     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1800     #[inline]
1801     pub fn make_ascii_uppercase(&mut self) {
1802         for byte in self {
1803             byte.make_ascii_uppercase();
1804         }
1805     }
1806
1807     /// Converts this slice to its ASCII lower case equivalent in-place.
1808     ///
1809     /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
1810     /// but non-ASCII letters are unchanged.
1811     ///
1812     /// To return a new lowercased value without modifying the existing one, use
1813     /// [`to_ascii_lowercase`].
1814     ///
1815     /// [`to_ascii_lowercase`]: #method.to_ascii_lowercase
1816     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1817     #[inline]
1818     pub fn make_ascii_lowercase(&mut self) {
1819         for byte in self {
1820             byte.make_ascii_lowercase();
1821         }
1822     }
1823 }
1824
1825 ////////////////////////////////////////////////////////////////////////////////
1826 // Extension traits for slices over specific kinds of data
1827 ////////////////////////////////////////////////////////////////////////////////
1828 #[unstable(feature = "slice_concat_ext",
1829            reason = "trait should not have to exist",
1830            issue = "27747")]
1831 /// An extension trait for concatenating slices
1832 ///
1833 /// While this trait is unstable, the methods are stable. `SliceConcatExt` is
1834 /// included in the [standard library prelude], so you can use [`join()`] and
1835 /// [`concat()`] as if they existed on `[T]` itself.
1836 ///
1837 /// [standard library prelude]: ../../std/prelude/index.html
1838 /// [`join()`]: #tymethod.join
1839 /// [`concat()`]: #tymethod.concat
1840 pub trait SliceConcatExt<T: ?Sized> {
1841     #[unstable(feature = "slice_concat_ext",
1842                reason = "trait should not have to exist",
1843                issue = "27747")]
1844     /// The resulting type after concatenation
1845     type Output;
1846
1847     /// Flattens a slice of `T` into a single value `Self::Output`.
1848     ///
1849     /// # Examples
1850     ///
1851     /// ```
1852     /// assert_eq!(["hello", "world"].concat(), "helloworld");
1853     /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
1854     /// ```
1855     #[stable(feature = "rust1", since = "1.0.0")]
1856     fn concat(&self) -> Self::Output;
1857
1858     /// Flattens a slice of `T` into a single value `Self::Output`, placing a
1859     /// given separator between each.
1860     ///
1861     /// # Examples
1862     ///
1863     /// ```
1864     /// assert_eq!(["hello", "world"].join(" "), "hello world");
1865     /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
1866     /// ```
1867     #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
1868     fn join(&self, sep: &T) -> Self::Output;
1869
1870     #[stable(feature = "rust1", since = "1.0.0")]
1871     #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
1872     fn connect(&self, sep: &T) -> Self::Output;
1873 }
1874
1875 #[unstable(feature = "slice_concat_ext",
1876            reason = "trait should not have to exist",
1877            issue = "27747")]
1878 impl<T: Clone, V: Borrow<[T]>> SliceConcatExt<T> for [V] {
1879     type Output = Vec<T>;
1880
1881     fn concat(&self) -> Vec<T> {
1882         let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
1883         let mut result = Vec::with_capacity(size);
1884         for v in self {
1885             result.extend_from_slice(v.borrow())
1886         }
1887         result
1888     }
1889
1890     fn join(&self, sep: &T) -> Vec<T> {
1891         let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
1892         let mut result = Vec::with_capacity(size + self.len());
1893         let mut first = true;
1894         for v in self {
1895             if first {
1896                 first = false
1897             } else {
1898                 result.push(sep.clone())
1899             }
1900             result.extend_from_slice(v.borrow())
1901         }
1902         result
1903     }
1904
1905     fn connect(&self, sep: &T) -> Vec<T> {
1906         self.join(sep)
1907     }
1908 }
1909
1910 ////////////////////////////////////////////////////////////////////////////////
1911 // Standard trait implementations for slices
1912 ////////////////////////////////////////////////////////////////////////////////
1913
1914 #[stable(feature = "rust1", since = "1.0.0")]
1915 impl<T> Borrow<[T]> for Vec<T> {
1916     fn borrow(&self) -> &[T] {
1917         &self[..]
1918     }
1919 }
1920
1921 #[stable(feature = "rust1", since = "1.0.0")]
1922 impl<T> BorrowMut<[T]> for Vec<T> {
1923     fn borrow_mut(&mut self) -> &mut [T] {
1924         &mut self[..]
1925     }
1926 }
1927
1928 #[stable(feature = "rust1", since = "1.0.0")]
1929 impl<T: Clone> ToOwned for [T] {
1930     type Owned = Vec<T>;
1931     #[cfg(not(test))]
1932     fn to_owned(&self) -> Vec<T> {
1933         self.to_vec()
1934     }
1935
1936     #[cfg(test)]
1937     fn to_owned(&self) -> Vec<T> {
1938         hack::to_vec(self)
1939     }
1940
1941     fn clone_into(&self, target: &mut Vec<T>) {
1942         // drop anything in target that will not be overwritten
1943         target.truncate(self.len());
1944         let len = target.len();
1945
1946         // reuse the contained values' allocations/resources.
1947         target.clone_from_slice(&self[..len]);
1948
1949         // target.len <= self.len due to the truncate above, so the
1950         // slice here is always in-bounds.
1951         target.extend_from_slice(&self[len..]);
1952     }
1953 }
1954
1955 ////////////////////////////////////////////////////////////////////////////////
1956 // Sorting
1957 ////////////////////////////////////////////////////////////////////////////////
1958
1959 /// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted.
1960 ///
1961 /// This is the integral subroutine of insertion sort.
1962 fn insert_head<T, F>(v: &mut [T], is_less: &mut F)
1963     where F: FnMut(&T, &T) -> bool
1964 {
1965     if v.len() >= 2 && is_less(&v[1], &v[0]) {
1966         unsafe {
1967             // There are three ways to implement insertion here:
1968             //
1969             // 1. Swap adjacent elements until the first one gets to its final destination.
1970             //    However, this way we copy data around more than is necessary. If elements are big
1971             //    structures (costly to copy), this method will be slow.
1972             //
1973             // 2. Iterate until the right place for the first element is found. Then shift the
1974             //    elements succeeding it to make room for it and finally place it into the
1975             //    remaining hole. This is a good method.
1976             //
1977             // 3. Copy the first element into a temporary variable. Iterate until the right place
1978             //    for it is found. As we go along, copy every traversed element into the slot
1979             //    preceding it. Finally, copy data from the temporary variable into the remaining
1980             //    hole. This method is very good. Benchmarks demonstrated slightly better
1981             //    performance than with the 2nd method.
1982             //
1983             // All methods were benchmarked, and the 3rd showed best results. So we chose that one.
1984             let mut tmp = mem::ManuallyDrop::new(ptr::read(&v[0]));
1985
1986             // Intermediate state of the insertion process is always tracked by `hole`, which
1987             // serves two purposes:
1988             // 1. Protects integrity of `v` from panics in `is_less`.
1989             // 2. Fills the remaining hole in `v` in the end.
1990             //
1991             // Panic safety:
1992             //
1993             // If `is_less` panics at any point during the process, `hole` will get dropped and
1994             // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it
1995             // initially held exactly once.
1996             let mut hole = InsertionHole {
1997                 src: &mut *tmp,
1998                 dest: &mut v[1],
1999             };
2000             ptr::copy_nonoverlapping(&v[1], &mut v[0], 1);
2001
2002             for i in 2..v.len() {
2003                 if !is_less(&v[i], &*tmp) {
2004                     break;
2005                 }
2006                 ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1);
2007                 hole.dest = &mut v[i];
2008             }
2009             // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`.
2010         }
2011     }
2012
2013     // When dropped, copies from `src` into `dest`.
2014     struct InsertionHole<T> {
2015         src: *mut T,
2016         dest: *mut T,
2017     }
2018
2019     impl<T> Drop for InsertionHole<T> {
2020         fn drop(&mut self) {
2021             unsafe { ptr::copy_nonoverlapping(self.src, self.dest, 1); }
2022         }
2023     }
2024 }
2025
2026 /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and
2027 /// stores the result into `v[..]`.
2028 ///
2029 /// # Safety
2030 ///
2031 /// The two slices must be non-empty and `mid` must be in bounds. Buffer `buf` must be long enough
2032 /// to hold a copy of the shorter slice. Also, `T` must not be a zero-sized type.
2033 unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
2034     where F: FnMut(&T, &T) -> bool
2035 {
2036     let len = v.len();
2037     let v = v.as_mut_ptr();
2038     let v_mid = v.offset(mid as isize);
2039     let v_end = v.offset(len as isize);
2040
2041     // The merge process first copies the shorter run into `buf`. Then it traces the newly copied
2042     // run and the longer run forwards (or backwards), comparing their next unconsumed elements and
2043     // copying the lesser (or greater) one into `v`.
2044     //
2045     // As soon as the shorter run is fully consumed, the process is done. If the longer run gets
2046     // consumed first, then we must copy whatever is left of the shorter run into the remaining
2047     // hole in `v`.
2048     //
2049     // Intermediate state of the process is always tracked by `hole`, which serves two purposes:
2050     // 1. Protects integrity of `v` from panics in `is_less`.
2051     // 2. Fills the remaining hole in `v` if the longer run gets consumed first.
2052     //
2053     // Panic safety:
2054     //
2055     // If `is_less` panics at any point during the process, `hole` will get dropped and fill the
2056     // hole in `v` with the unconsumed range in `buf`, thus ensuring that `v` still holds every
2057     // object it initially held exactly once.
2058     let mut hole;
2059
2060     if mid <= len - mid {
2061         // The left run is shorter.
2062         ptr::copy_nonoverlapping(v, buf, mid);
2063         hole = MergeHole {
2064             start: buf,
2065             end: buf.offset(mid as isize),
2066             dest: v,
2067         };
2068
2069         // Initially, these pointers point to the beginnings of their arrays.
2070         let left = &mut hole.start;
2071         let mut right = v_mid;
2072         let out = &mut hole.dest;
2073
2074         while *left < hole.end && right < v_end {
2075             // Consume the lesser side.
2076             // If equal, prefer the left run to maintain stability.
2077             let to_copy = if is_less(&*right, &**left) {
2078                 get_and_increment(&mut right)
2079             } else {
2080                 get_and_increment(left)
2081             };
2082             ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1);
2083         }
2084     } else {
2085         // The right run is shorter.
2086         ptr::copy_nonoverlapping(v_mid, buf, len - mid);
2087         hole = MergeHole {
2088             start: buf,
2089             end: buf.offset((len - mid) as isize),
2090             dest: v_mid,
2091         };
2092
2093         // Initially, these pointers point past the ends of their arrays.
2094         let left = &mut hole.dest;
2095         let right = &mut hole.end;
2096         let mut out = v_end;
2097
2098         while v < *left && buf < *right {
2099             // Consume the greater side.
2100             // If equal, prefer the right run to maintain stability.
2101             let to_copy = if is_less(&*right.offset(-1), &*left.offset(-1)) {
2102                 decrement_and_get(left)
2103             } else {
2104                 decrement_and_get(right)
2105             };
2106             ptr::copy_nonoverlapping(to_copy, decrement_and_get(&mut out), 1);
2107         }
2108     }
2109     // Finally, `hole` gets dropped. If the shorter run was not fully consumed, whatever remains of
2110     // it will now be copied into the hole in `v`.
2111
2112     unsafe fn get_and_increment<T>(ptr: &mut *mut T) -> *mut T {
2113         let old = *ptr;
2114         *ptr = ptr.offset(1);
2115         old
2116     }
2117
2118     unsafe fn decrement_and_get<T>(ptr: &mut *mut T) -> *mut T {
2119         *ptr = ptr.offset(-1);
2120         *ptr
2121     }
2122
2123     // When dropped, copies the range `start..end` into `dest..`.
2124     struct MergeHole<T> {
2125         start: *mut T,
2126         end: *mut T,
2127         dest: *mut T,
2128     }
2129
2130     impl<T> Drop for MergeHole<T> {
2131         fn drop(&mut self) {
2132             // `T` is not a zero-sized type, so it's okay to divide by its size.
2133             let len = (self.end as usize - self.start as usize) / mem::size_of::<T>();
2134             unsafe { ptr::copy_nonoverlapping(self.start, self.dest, len); }
2135         }
2136     }
2137 }
2138
2139 /// This merge sort borrows some (but not all) ideas from TimSort, which is described in detail
2140 /// [here](http://svn.python.org/projects/python/trunk/Objects/listsort.txt).
2141 ///
2142 /// The algorithm identifies strictly descending and non-descending subsequences, which are called
2143 /// natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed
2144 /// onto the stack, and then some pairs of adjacent runs are merged until these two invariants are
2145 /// satisfied:
2146 ///
2147 /// 1. for every `i` in `1..runs.len()`: `runs[i - 1].len > runs[i].len`
2148 /// 2. for every `i` in `2..runs.len()`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
2149 ///
2150 /// The invariants ensure that the total running time is `O(n log n)` worst-case.
2151 fn merge_sort<T, F>(v: &mut [T], mut is_less: F)
2152     where F: FnMut(&T, &T) -> bool
2153 {
2154     // Slices of up to this length get sorted using insertion sort.
2155     const MAX_INSERTION: usize = 20;
2156     // Very short runs are extended using insertion sort to span at least this many elements.
2157     const MIN_RUN: usize = 10;
2158
2159     // Sorting has no meaningful behavior on zero-sized types.
2160     if size_of::<T>() == 0 {
2161         return;
2162     }
2163
2164     let len = v.len();
2165
2166     // Short arrays get sorted in-place via insertion sort to avoid allocations.
2167     if len <= MAX_INSERTION {
2168         if len >= 2 {
2169             for i in (0..len-1).rev() {
2170                 insert_head(&mut v[i..], &mut is_less);
2171             }
2172         }
2173         return;
2174     }
2175
2176     // Allocate a buffer to use as scratch memory. We keep the length 0 so we can keep in it
2177     // shallow copies of the contents of `v` without risking the dtors running on copies if
2178     // `is_less` panics. When merging two sorted runs, this buffer holds a copy of the shorter run,
2179     // which will always have length at most `len / 2`.
2180     let mut buf = Vec::with_capacity(len / 2);
2181
2182     // In order to identify natural runs in `v`, we traverse it backwards. That might seem like a
2183     // strange decision, but consider the fact that merges more often go in the opposite direction
2184     // (forwards). According to benchmarks, merging forwards is slightly faster than merging
2185     // backwards. To conclude, identifying runs by traversing backwards improves performance.
2186     let mut runs = vec![];
2187     let mut end = len;
2188     while end > 0 {
2189         // Find the next natural run, and reverse it if it's strictly descending.
2190         let mut start = end - 1;
2191         if start > 0 {
2192             start -= 1;
2193             unsafe {
2194                 if is_less(v.get_unchecked(start + 1), v.get_unchecked(start)) {
2195                     while start > 0 && is_less(v.get_unchecked(start),
2196                                                v.get_unchecked(start - 1)) {
2197                         start -= 1;
2198                     }
2199                     v[start..end].reverse();
2200                 } else {
2201                     while start > 0 && !is_less(v.get_unchecked(start),
2202                                                 v.get_unchecked(start - 1)) {
2203                         start -= 1;
2204                     }
2205                 }
2206             }
2207         }
2208
2209         // Insert some more elements into the run if it's too short. Insertion sort is faster than
2210         // merge sort on short sequences, so this significantly improves performance.
2211         while start > 0 && end - start < MIN_RUN {
2212             start -= 1;
2213             insert_head(&mut v[start..end], &mut is_less);
2214         }
2215
2216         // Push this run onto the stack.
2217         runs.push(Run {
2218             start,
2219             len: end - start,
2220         });
2221         end = start;
2222
2223         // Merge some pairs of adjacent runs to satisfy the invariants.
2224         while let Some(r) = collapse(&runs) {
2225             let left = runs[r + 1];
2226             let right = runs[r];
2227             unsafe {
2228                 merge(&mut v[left.start .. right.start + right.len], left.len, buf.as_mut_ptr(),
2229                       &mut is_less);
2230             }
2231             runs[r] = Run {
2232                 start: left.start,
2233                 len: left.len + right.len,
2234             };
2235             runs.remove(r + 1);
2236         }
2237     }
2238
2239     // Finally, exactly one run must remain in the stack.
2240     debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);
2241
2242     // Examines the stack of runs and identifies the next pair of runs to merge. More specifically,
2243     // if `Some(r)` is returned, that means `runs[r]` and `runs[r + 1]` must be merged next. If the
2244     // algorithm should continue building a new run instead, `None` is returned.
2245     //
2246     // TimSort is infamous for its buggy implementations, as described here:
2247     // http://envisage-project.eu/timsort-specification-and-verification/
2248     //
2249     // The gist of the story is: we must enforce the invariants on the top four runs on the stack.
2250     // Enforcing them on just top three is not sufficient to ensure that the invariants will still
2251     // hold for *all* runs in the stack.
2252     //
2253     // This function correctly checks invariants for the top four runs. Additionally, if the top
2254     // run starts at index 0, it will always demand a merge operation until the stack is fully
2255     // collapsed, in order to complete the sort.
2256     #[inline]
2257     fn collapse(runs: &[Run]) -> Option<usize> {
2258         let n = runs.len();
2259         if n >= 2 && (runs[n - 1].start == 0 ||
2260                       runs[n - 2].len <= runs[n - 1].len ||
2261                       (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len) ||
2262                       (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len)) {
2263             if n >= 3 && runs[n - 3].len < runs[n - 1].len {
2264                 Some(n - 3)
2265             } else {
2266                 Some(n - 2)
2267             }
2268         } else {
2269             None
2270         }
2271     }
2272
2273     #[derive(Clone, Copy)]
2274     struct Run {
2275         start: usize,
2276         len: usize,
2277     }
2278 }