src/libcollections/slice.rs

   1 // Copyright 2012-2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! A dynamically-sized view into a contiguous sequence, `[T]`.
  12 //!
  13 //! Slices are a view into a block of memory represented as a pointer and a
  14 //! length.
  15 //!
  16 //! ```
  17 //! // slicing a Vec
  18 //! let vec = vec![1, 2, 3];
  19 //! let int_slice = &vec[..];
  20 //! // coercing an array to a slice
  21 //! let str_slice: &[&str] = &["one", "two", "three"];
  22 //! ```
  23 //!
  24 //! Slices are either mutable or shared. The shared slice type is `&[T]`,
  25 //! while the mutable slice type is `&mut [T]`, where `T` represents the element
  26 //! type. For example, you can mutate the block of memory that a mutable slice
  27 //! points to:
  28 //!
  29 //! ```
  30 //! let x = &mut [1, 2, 3];
  31 //! x[1] = 7;
  32 //! assert_eq!(x, &[1, 7, 3]);
  33 //! ```
  34 //!
  35 //! Here are some of the things this module contains:
  36 //!
  37 //! ## Structs
  38 //!
  39 //! There are several structs that are useful for slices, such as [`Iter`], which
  40 //! represents iteration over a slice.
  41 //!
  42 //! ## Trait Implementations
  43 //!
  44 //! There are several implementations of common traits for slices. Some examples
  45 //! include:
  46 //!
  47 //! * [`Clone`]
  48 //! * [`Eq`], [`Ord`] - for slices whose element type are [`Eq`] or [`Ord`].
  49 //! * [`Hash`] - for slices whose element type is [`Hash`].
  50 //!
  51 //! ## Iteration
  52 //!
  53 //! The slices implement `IntoIterator`. The iterator yields references to the
  54 //! slice elements.
  55 //!
  56 //! ```
  57 //! let numbers = &[0, 1, 2];
  58 //! for n in numbers {
  59 //!     println!("{} is a number!", n);
  60 //! }
  61 //! ```
  62 //!
  63 //! The mutable slice yields mutable references to the elements:
  64 //!
  65 //! ```
  66 //! let mut scores = [7, 8, 9];
  67 //! for score in &mut scores[..] {
  68 //!     *score += 1;
  69 //! }
  70 //! ```
  71 //!
  72 //! This iterator yields mutable references to the slice's elements, so while
  73 //! the element type of the slice is `i32`, the element type of the iterator is
  74 //! `&mut i32`.
  75 //!
  76 //! * [`.iter`] and [`.iter_mut`] are the explicit methods to return the default
  77 //!   iterators.
  78 //! * Further methods that return iterators are [`.split`], [`.splitn`],
  79 //!   [`.chunks`], [`.windows`] and more.
  80 //!
  81 //! *[See also the slice primitive type](../../std/primitive.slice.html).*
  82 //!
  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 alloc::boxed::Box;
 101 use core::cmp::Ordering::{self, Less};
 102 use core::mem::size_of;
 103 use core::mem;
 104 use core::ptr;
 105 use core::slice as core_slice;
 106
 107 use borrow::{Borrow, BorrowMut, ToOwned};
 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 = "slice_get_slice", issue = "35729")]
 123 pub use core::slice::SliceIndex;
 124
 125 ////////////////////////////////////////////////////////////////////////////////
 126 // Basic slice extension methods
 127 ////////////////////////////////////////////////////////////////////////////////
 128
 129 // HACK(japaric) needed for the implementation of `vec!` macro during testing
 130 // NB see the hack module in this file for more details
 131 #[cfg(test)]
 132 pub use self::hack::into_vec;
 133
 134 // HACK(japaric) needed for the implementation of `Vec::clone` during testing
 135 // NB see the hack module in this file for more details
 136 #[cfg(test)]
 137 pub use self::hack::to_vec;
 138
 139 // HACK(japaric): With cfg(test) `impl [T]` is not available, these three
 140 // functions are actually methods that are in `impl [T]` but not in
 141 // `core::slice::SliceExt` - we need to supply these functions for the
 142 // `test_permutations` test
 143 mod hack {
 144     use alloc::boxed::Box;
 145     use core::mem;
 146
 147     #[cfg(test)]
 148     use string::ToString;
 149     use vec::Vec;
 150
 151     pub fn into_vec<T>(mut b: Box<[T]>) -> Vec<T> {
 152         unsafe {
 153             let xs = Vec::from_raw_parts(b.as_mut_ptr(), b.len(), b.len());
 154             mem::forget(b);
 155             xs
 156         }
 157     }
 158
 159     #[inline]
 160     pub fn to_vec<T>(s: &[T]) -> Vec<T>
 161         where T: Clone
 162     {
 163         let mut vector = Vec::with_capacity(s.len());
 164         vector.extend_from_slice(s);
 165         vector
 166     }
 167 }
 168
 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 the 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 the slice, or `None` if it is empty.
 218     ///
 219     /// # Examples
 220     ///
 221     /// ```
 222     /// let x = &mut [0, 1, 2];
 223     ///
 224     /// if let Some(first) = x.first_mut() {
 225     ///     *first = 5;
 226     /// }
 227     /// assert_eq!(x, &[5, 1, 2]);
 228     /// ```
 229     #[stable(feature = "rust1", since = "1.0.0")]
 230     #[inline]
 231     pub fn first_mut(&mut self) -> Option<&mut T> {
 232         core_slice::SliceExt::first_mut(self)
 233     }
 234
 235     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
 236     ///
 237     /// # Examples
 238     ///
 239     /// ```
 240     /// let x = &[0, 1, 2];
 241     ///
 242     /// if let Some((first, elements)) = x.split_first() {
 243     ///     assert_eq!(first, &0);
 244     ///     assert_eq!(elements, &[1, 2]);
 245     /// }
 246     /// ```
 247     #[stable(feature = "slice_splits", since = "1.5.0")]
 248     #[inline]
 249     pub fn split_first(&self) -> Option<(&T, &[T])> {
 250         core_slice::SliceExt::split_first(self)
 251     }
 252
 253     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
 254     ///
 255     /// # Examples
 256     ///
 257     /// ```
 258     /// let x = &mut [0, 1, 2];
 259     ///
 260     /// if let Some((first, elements)) = x.split_first_mut() {
 261     ///     *first = 3;
 262     ///     elements[0] = 4;
 263     ///     elements[1] = 5;
 264     /// }
 265     /// assert_eq!(x, &[3, 4, 5]);
 266     /// ```
 267     #[stable(feature = "slice_splits", since = "1.5.0")]
 268     #[inline]
 269     pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 270         core_slice::SliceExt::split_first_mut(self)
 271     }
 272
 273     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
 274     ///
 275     /// # Examples
 276     ///
 277     /// ```
 278     /// let x = &[0, 1, 2];
 279     ///
 280     /// if let Some((last, elements)) = x.split_last() {
 281     ///     assert_eq!(last, &2);
 282     ///     assert_eq!(elements, &[0, 1]);
 283     /// }
 284     /// ```
 285     #[stable(feature = "slice_splits", since = "1.5.0")]
 286     #[inline]
 287     pub fn split_last(&self) -> Option<(&T, &[T])> {
 288         core_slice::SliceExt::split_last(self)
 289
 290     }
 291
 292     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
 293     ///
 294     /// # Examples
 295     ///
 296     /// ```
 297     /// let x = &mut [0, 1, 2];
 298     ///
 299     /// if let Some((last, elements)) = x.split_last_mut() {
 300     ///     *last = 3;
 301     ///     elements[0] = 4;
 302     ///     elements[1] = 5;
 303     /// }
 304     /// assert_eq!(x, &[4, 5, 3]);
 305     /// ```
 306     #[stable(feature = "slice_splits", since = "1.5.0")]
 307     #[inline]
 308     pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 309         core_slice::SliceExt::split_last_mut(self)
 310     }
 311
 312     /// Returns the last element of the slice, or `None` if it is empty.
 313     ///
 314     /// # Examples
 315     ///
 316     /// ```
 317     /// let v = [10, 40, 30];
 318     /// assert_eq!(Some(&30), v.last());
 319     ///
 320     /// let w: &[i32] = &[];
 321     /// assert_eq!(None, w.last());
 322     /// ```
 323     #[stable(feature = "rust1", since = "1.0.0")]
 324     #[inline]
 325     pub fn last(&self) -> Option<&T> {
 326         core_slice::SliceExt::last(self)
 327     }
 328
 329     /// Returns a mutable pointer to the last item in the slice.
 330     ///
 331     /// # Examples
 332     ///
 333     /// ```
 334     /// let x = &mut [0, 1, 2];
 335     ///
 336     /// if let Some(last) = x.last_mut() {
 337     ///     *last = 10;
 338     /// }
 339     /// assert_eq!(x, &[0, 1, 10]);
 340     /// ```
 341     #[stable(feature = "rust1", since = "1.0.0")]
 342     #[inline]
 343     pub fn last_mut(&mut self) -> Option<&mut T> {
 344         core_slice::SliceExt::last_mut(self)
 345     }
 346
 347     /// Returns a reference to an element or subslice depending on the type of
 348     /// index.
 349     ///
 350     /// - If given a position, returns a reference to the element at that
 351     ///   position or `None` if out of bounds.
 352     /// - If given a range, returns the subslice corresponding to that range,
 353     ///   or `None` if out of bounds.
 354     ///
 355     /// # Examples
 356     ///
 357     /// ```
 358     /// let v = [10, 40, 30];
 359     /// assert_eq!(Some(&40), v.get(1));
 360     /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
 361     /// assert_eq!(None, v.get(3));
 362     /// assert_eq!(None, v.get(0..4));
 363     /// ```
 364     #[stable(feature = "rust1", since = "1.0.0")]
 365     #[inline]
 366     pub fn get<I>(&self, index: I) -> Option<&I::Output>
 367         where I: SliceIndex<Self>
 368     {
 369         core_slice::SliceExt::get(self, index)
 370     }
 371
 372     /// Returns a mutable reference to an element or subslice depending on the
 373     /// type of index (see [`get`]) or `None` if the index is out of bounds.
 374     ///
 375     /// [`get`]: #method.get
 376     ///
 377     /// # Examples
 378     ///
 379     /// ```
 380     /// let x = &mut [0, 1, 2];
 381     ///
 382     /// if let Some(elem) = x.get_mut(1) {
 383     ///     *elem = 42;
 384     /// }
 385     /// assert_eq!(x, &[0, 42, 2]);
 386     /// ```
 387     #[stable(feature = "rust1", since = "1.0.0")]
 388     #[inline]
 389     pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
 390         where I: SliceIndex<Self>
 391     {
 392         core_slice::SliceExt::get_mut(self, index)
 393     }
 394
 395     /// Returns a reference to an element or subslice, without doing bounds
 396     /// checking.
 397     ///
 398     /// This is generally not recommended, use with caution! For a safe
 399     /// alternative see [`get`].
 400     ///
 401     /// [`get`]: #method.get
 402     ///
 403     /// # Examples
 404     ///
 405     /// ```
 406     /// let x = &[1, 2, 4];
 407     ///
 408     /// unsafe {
 409     ///     assert_eq!(x.get_unchecked(1), &2);
 410     /// }
 411     /// ```
 412     #[stable(feature = "rust1", since = "1.0.0")]
 413     #[inline]
 414     pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
 415         where I: SliceIndex<Self>
 416     {
 417         core_slice::SliceExt::get_unchecked(self, index)
 418     }
 419
 420     /// Returns a mutable reference to an element or subslice, without doing
 421     /// bounds checking.
 422     ///
 423     /// This is generally not recommended, use with caution! For a safe
 424     /// alternative see [`get_mut`].
 425     ///
 426     /// [`get_mut`]: #method.get_mut
 427     ///
 428     /// # Examples
 429     ///
 430     /// ```
 431     /// let x = &mut [1, 2, 4];
 432     ///
 433     /// unsafe {
 434     ///     let elem = x.get_unchecked_mut(1);
 435     ///     *elem = 13;
 436     /// }
 437     /// assert_eq!(x, &[1, 13, 4]);
 438     /// ```
 439     #[stable(feature = "rust1", since = "1.0.0")]
 440     #[inline]
 441     pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
 442         where I: SliceIndex<Self>
 443     {
 444         core_slice::SliceExt::get_unchecked_mut(self, index)
 445     }
 446
 447     /// Returns a raw pointer to the slice's buffer.
 448     ///
 449     /// The caller must ensure that the slice outlives the pointer this
 450     /// function returns, or else it will end up pointing to garbage.
 451     ///
 452     /// Modifying the container referenced by this slice may cause its buffer
 453     /// to be reallocated, which would also make any pointers to it invalid.
 454     ///
 455     /// # Examples
 456     ///
 457     /// ```
 458     /// let x = &[1, 2, 4];
 459     /// let x_ptr = x.as_ptr();
 460     ///
 461     /// unsafe {
 462     ///     for i in 0..x.len() {
 463     ///         assert_eq!(x.get_unchecked(i), &*x_ptr.offset(i as isize));
 464     ///     }
 465     /// }
 466     /// ```
 467     #[stable(feature = "rust1", since = "1.0.0")]
 468     #[inline]
 469     pub fn as_ptr(&self) -> *const T {
 470         core_slice::SliceExt::as_ptr(self)
 471     }
 472
 473     /// Returns an unsafe mutable pointer to the slice's buffer.
 474     ///
 475     /// The caller must ensure that the slice outlives the pointer this
 476     /// function returns, or else it will end up pointing to garbage.
 477     ///
 478     /// Modifying the container referenced by this slice may cause its buffer
 479     /// to be reallocated, which would also make any pointers to it invalid.
 480     ///
 481     /// # Examples
 482     ///
 483     /// ```
 484     /// let x = &mut [1, 2, 4];
 485     /// let x_ptr = x.as_mut_ptr();
 486     ///
 487     /// unsafe {
 488     ///     for i in 0..x.len() {
 489     ///         *x_ptr.offset(i as isize) += 2;
 490     ///     }
 491     /// }
 492     /// assert_eq!(x, &[3, 4, 6]);
 493     /// ```
 494     #[stable(feature = "rust1", since = "1.0.0")]
 495     #[inline]
 496     pub fn as_mut_ptr(&mut self) -> *mut T {
 497         core_slice::SliceExt::as_mut_ptr(self)
 498     }
 499
 500     /// Swaps two elements in the slice.
 501     ///
 502     /// # Arguments
 503     ///
 504     /// * a - The index of the first element
 505     /// * b - The index of the second element
 506     ///
 507     /// # Panics
 508     ///
 509     /// Panics if `a` or `b` are out of bounds.
 510     ///
 511     /// # Examples
 512     ///
 513     /// ```
 514     /// let mut v = ["a", "b", "c", "d"];
 515     /// v.swap(1, 3);
 516     /// assert!(v == ["a", "d", "c", "b"]);
 517     /// ```
 518     #[stable(feature = "rust1", since = "1.0.0")]
 519     #[inline]
 520     pub fn swap(&mut self, a: usize, b: usize) {
 521         core_slice::SliceExt::swap(self, a, b)
 522     }
 523
 524     /// Reverses the order of elements in the slice, in place.
 525     ///
 526     /// # Example
 527     ///
 528     /// ```
 529     /// let mut v = [1, 2, 3];
 530     /// v.reverse();
 531     /// assert!(v == [3, 2, 1]);
 532     /// ```
 533     #[stable(feature = "rust1", since = "1.0.0")]
 534     #[inline]
 535     pub fn reverse(&mut self) {
 536         core_slice::SliceExt::reverse(self)
 537     }
 538
 539     /// Returns an iterator over the slice.
 540     ///
 541     /// # Examples
 542     ///
 543     /// ```
 544     /// let x = &[1, 2, 4];
 545     /// let mut iterator = x.iter();
 546     ///
 547     /// assert_eq!(iterator.next(), Some(&1));
 548     /// assert_eq!(iterator.next(), Some(&2));
 549     /// assert_eq!(iterator.next(), Some(&4));
 550     /// assert_eq!(iterator.next(), None);
 551     /// ```
 552     #[stable(feature = "rust1", since = "1.0.0")]
 553     #[inline]
 554     pub fn iter(&self) -> Iter<T> {
 555         core_slice::SliceExt::iter(self)
 556     }
 557
 558     /// Returns an iterator that allows modifying each value.
 559     ///
 560     /// # Examples
 561     ///
 562     /// ```
 563     /// let x = &mut [1, 2, 4];
 564     /// for elem in x.iter_mut() {
 565     ///     *elem += 2;
 566     /// }
 567     /// assert_eq!(x, &[3, 4, 6]);
 568     /// ```
 569     #[stable(feature = "rust1", since = "1.0.0")]
 570     #[inline]
 571     pub fn iter_mut(&mut self) -> IterMut<T> {
 572         core_slice::SliceExt::iter_mut(self)
 573     }
 574
 575     /// Returns an iterator over all contiguous windows of length
 576     /// `size`. The windows overlap. If the slice is shorter than
 577     /// `size`, the iterator returns no values.
 578     ///
 579     /// # Panics
 580     ///
 581     /// Panics if `size` is 0.
 582     ///
 583     /// # Example
 584     ///
 585     /// ```
 586     /// let slice = ['r', 'u', 's', 't'];
 587     /// let mut iter = slice.windows(2);
 588     /// assert_eq!(iter.next().unwrap(), &['r', 'u']);
 589     /// assert_eq!(iter.next().unwrap(), &['u', 's']);
 590     /// assert_eq!(iter.next().unwrap(), &['s', 't']);
 591     /// assert!(iter.next().is_none());
 592     /// ```
 593     ///
 594     /// If the slice is shorter than `size`:
 595     ///
 596     /// ```
 597     /// let slice = ['f', 'o', 'o'];
 598     /// let mut iter = slice.windows(4);
 599     /// assert!(iter.next().is_none());
 600     /// ```
 601     #[stable(feature = "rust1", since = "1.0.0")]
 602     #[inline]
 603     pub fn windows(&self, size: usize) -> Windows<T> {
 604         core_slice::SliceExt::windows(self, size)
 605     }
 606
 607     /// Returns an iterator over `size` elements of the slice at a
 608     /// time. The chunks are slices and do not overlap. If `size` does
 609     /// not divide the length of the slice, then the last chunk will
 610     /// not have length `size`.
 611     ///
 612     /// # Panics
 613     ///
 614     /// Panics if `size` is 0.
 615     ///
 616     /// # Example
 617     ///
 618     /// ```
 619     /// let slice = ['l', 'o', 'r', 'e', 'm'];
 620     /// let mut iter = slice.chunks(2);
 621     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
 622     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
 623     /// assert_eq!(iter.next().unwrap(), &['m']);
 624     /// assert!(iter.next().is_none());
 625     /// ```
 626     #[stable(feature = "rust1", since = "1.0.0")]
 627     #[inline]
 628     pub fn chunks(&self, size: usize) -> Chunks<T> {
 629         core_slice::SliceExt::chunks(self, size)
 630     }
 631
 632     /// Returns an iterator over `chunk_size` elements of the slice at a time.
 633     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
 634     /// not divide the length of the slice, then the last chunk will not
 635     /// have length `chunk_size`.
 636     ///
 637     /// # Panics
 638     ///
 639     /// Panics if `chunk_size` is 0.
 640     ///
 641     /// # Examples
 642     ///
 643     /// ```
 644     /// let v = &mut [0, 0, 0, 0, 0];
 645     /// let mut count = 1;
 646     ///
 647     /// for chunk in v.chunks_mut(2) {
 648     ///     for elem in chunk.iter_mut() {
 649     ///         *elem += count;
 650     ///     }
 651     ///     count += 1;
 652     /// }
 653     /// assert_eq!(v, &[1, 1, 2, 2, 3]);
 654     /// ```
 655     #[stable(feature = "rust1", since = "1.0.0")]
 656     #[inline]
 657     pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
 658         core_slice::SliceExt::chunks_mut(self, chunk_size)
 659     }
 660
 661     /// Divides one slice into two at an index.
 662     ///
 663     /// The first will contain all indices from `[0, mid)` (excluding
 664     /// the index `mid` itself) and the second will contain all
 665     /// indices from `[mid, len)` (excluding the index `len` itself).
 666     ///
 667     /// # Panics
 668     ///
 669     /// Panics if `mid > len`.
 670     ///
 671     /// # Examples
 672     ///
 673     /// ```
 674     /// let v = [10, 40, 30, 20, 50];
 675     /// let (v1, v2) = v.split_at(2);
 676     /// assert_eq!([10, 40], v1);
 677     /// assert_eq!([30, 20, 50], v2);
 678     /// ```
 679     #[stable(feature = "rust1", since = "1.0.0")]
 680     #[inline]
 681     pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
 682         core_slice::SliceExt::split_at(self, mid)
 683     }
 684
 685     /// Divides one `&mut` into two at an index.
 686     ///
 687     /// The first will contain all indices from `[0, mid)` (excluding
 688     /// the index `mid` itself) and the second will contain all
 689     /// indices from `[mid, len)` (excluding the index `len` itself).
 690     ///
 691     /// # Panics
 692     ///
 693     /// Panics if `mid > len`.
 694     ///
 695     /// # Examples
 696     ///
 697     /// ```
 698     /// let mut v = [1, 2, 3, 4, 5, 6];
 699     ///
 700     /// // scoped to restrict the lifetime of the borrows
 701     /// {
 702     ///    let (left, right) = v.split_at_mut(0);
 703     ///    assert!(left == []);
 704     ///    assert!(right == [1, 2, 3, 4, 5, 6]);
 705     /// }
 706     ///
 707     /// {
 708     ///     let (left, right) = v.split_at_mut(2);
 709     ///     assert!(left == [1, 2]);
 710     ///     assert!(right == [3, 4, 5, 6]);
 711     /// }
 712     ///
 713     /// {
 714     ///     let (left, right) = v.split_at_mut(6);
 715     ///     assert!(left == [1, 2, 3, 4, 5, 6]);
 716     ///     assert!(right == []);
 717     /// }
 718     /// ```
 719     #[stable(feature = "rust1", since = "1.0.0")]
 720     #[inline]
 721     pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
 722         core_slice::SliceExt::split_at_mut(self, mid)
 723     }
 724
 725     /// Returns an iterator over subslices separated by elements that match
 726     /// `pred`. The matched element is not contained in the subslices.
 727     ///
 728     /// # Examples
 729     ///
 730     /// ```
 731     /// let slice = [10, 40, 33, 20];
 732     /// let mut iter = slice.split(|num| num % 3 == 0);
 733     ///
 734     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
 735     /// assert_eq!(iter.next().unwrap(), &[20]);
 736     /// assert!(iter.next().is_none());
 737     /// ```
 738     ///
 739     /// If the first element is matched, an empty slice will be the first item
 740     /// returned by the iterator. Similarly, if the last element in the slice
 741     /// is matched, an empty slice will be the last item returned by the
 742     /// iterator:
 743     ///
 744     /// ```
 745     /// let slice = [10, 40, 33];
 746     /// let mut iter = slice.split(|num| num % 3 == 0);
 747     ///
 748     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
 749     /// assert_eq!(iter.next().unwrap(), &[]);
 750     /// assert!(iter.next().is_none());
 751     /// ```
 752     ///
 753     /// If two matched elements are directly adjacent, an empty slice will be
 754     /// present between them:
 755     ///
 756     /// ```
 757     /// let slice = [10, 6, 33, 20];
 758     /// let mut iter = slice.split(|num| num % 3 == 0);
 759     ///
 760     /// assert_eq!(iter.next().unwrap(), &[10]);
 761     /// assert_eq!(iter.next().unwrap(), &[]);
 762     /// assert_eq!(iter.next().unwrap(), &[20]);
 763     /// assert!(iter.next().is_none());
 764     /// ```
 765     #[stable(feature = "rust1", since = "1.0.0")]
 766     #[inline]
 767     pub fn split<F>(&self, pred: F) -> Split<T, F>
 768         where F: FnMut(&T) -> bool
 769     {
 770         core_slice::SliceExt::split(self, pred)
 771     }
 772
 773     /// Returns an iterator over mutable subslices separated by elements that
 774     /// match `pred`. The matched element is not contained in the subslices.
 775     ///
 776     /// # Examples
 777     ///
 778     /// ```
 779     /// let mut v = [10, 40, 30, 20, 60, 50];
 780     ///
 781     /// for group in v.split_mut(|num| *num % 3 == 0) {
 782     ///     group[0] = 1;
 783     /// }
 784     /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
 785     /// ```
 786     #[stable(feature = "rust1", since = "1.0.0")]
 787     #[inline]
 788     pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F>
 789         where F: FnMut(&T) -> bool
 790     {
 791         core_slice::SliceExt::split_mut(self, pred)
 792     }
 793
 794     /// Returns an iterator over subslices separated by elements that match
 795     /// `pred`, starting at the end of the slice and working backwards.
 796     /// The matched element is not contained in the subslices.
 797     ///
 798     /// # Examples
 799     ///
 800     /// ```
 801     /// #![feature(slice_rsplit)]
 802     ///
 803     /// let slice = [11, 22, 33, 0, 44, 55];
 804     /// let mut iter = slice.rsplit(|num| *num == 0);
 805     ///
 806     /// assert_eq!(iter.next().unwrap(), &[44, 55]);
 807     /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
 808     /// assert_eq!(iter.next(), None);
 809     /// ```
 810     ///
 811     /// As with `split()`, if the first or last element is matched, an empty
 812     /// slice will be the first (or last) item returned by the iterator.
 813     ///
 814     /// ```
 815     /// #![feature(slice_rsplit)]
 816     ///
 817     /// let v = &[0, 1, 1, 2, 3, 5, 8];
 818     /// let mut it = v.rsplit(|n| *n % 2 == 0);
 819     /// assert_eq!(it.next().unwrap(), &[]);
 820     /// assert_eq!(it.next().unwrap(), &[3, 5]);
 821     /// assert_eq!(it.next().unwrap(), &[1, 1]);
 822     /// assert_eq!(it.next().unwrap(), &[]);
 823     /// assert_eq!(it.next(), None);
 824     /// ```
 825     #[unstable(feature = "slice_rsplit", issue = "41020")]
 826     #[inline]
 827     pub fn rsplit<F>(&self, pred: F) -> RSplit<T, F>
 828         where F: FnMut(&T) -> bool
 829     {
 830         core_slice::SliceExt::rsplit(self, pred)
 831     }
 832
 833     /// Returns an iterator over mutable subslices separated by elements that
 834     /// match `pred`, starting at the end of the slice and working
 835     /// backwards. The matched element is not contained in the subslices.
 836     ///
 837     /// # Examples
 838     ///
 839     /// ```
 840     /// #![feature(slice_rsplit)]
 841     ///
 842     /// let mut v = [100, 400, 300, 200, 600, 500];
 843     ///
 844     /// let mut count = 0;
 845     /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
 846     ///     count += 1;
 847     ///     group[0] = count;
 848     /// }
 849     /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
 850     /// ```
 851     ///
 852     #[unstable(feature = "slice_rsplit", issue = "41020")]
 853     #[inline]
 854     pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<T, F>
 855         where F: FnMut(&T) -> bool
 856     {
 857         core_slice::SliceExt::rsplit_mut(self, pred)
 858     }
 859
 860     /// Returns an iterator over subslices separated by elements that match
 861     /// `pred`, limited to returning at most `n` items. The matched element is
 862     /// not contained in the subslices.
 863     ///
 864     /// The last element returned, if any, will contain the remainder of the
 865     /// slice.
 866     ///
 867     /// # Examples
 868     ///
 869     /// Print the slice split once by numbers divisible by 3 (i.e. `[10, 40]`,
 870     /// `[20, 60, 50]`):
 871     ///
 872     /// ```
 873     /// let v = [10, 40, 30, 20, 60, 50];
 874     ///
 875     /// for group in v.splitn(2, |num| *num % 3 == 0) {
 876     ///     println!("{:?}", group);
 877     /// }
 878     /// ```
 879     #[stable(feature = "rust1", since = "1.0.0")]
 880     #[inline]
 881     pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<T, F>
 882         where F: FnMut(&T) -> bool
 883     {
 884         core_slice::SliceExt::splitn(self, n, pred)
 885     }
 886
 887     /// Returns an iterator over subslices separated by elements that match
 888     /// `pred`, limited to returning at most `n` items. The matched element is
 889     /// not contained in the subslices.
 890     ///
 891     /// The last element returned, if any, will contain the remainder of the
 892     /// slice.
 893     ///
 894     /// # Examples
 895     ///
 896     /// ```
 897     /// let mut v = [10, 40, 30, 20, 60, 50];
 898     ///
 899     /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
 900     ///     group[0] = 1;
 901     /// }
 902     /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
 903     /// ```
 904     #[stable(feature = "rust1", since = "1.0.0")]
 905     #[inline]
 906     pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<T, F>
 907         where F: FnMut(&T) -> bool
 908     {
 909         core_slice::SliceExt::splitn_mut(self, n, pred)
 910     }
 911
 912     /// Returns an iterator over subslices separated by elements that match
 913     /// `pred` limited to returning at most `n` items. This starts at the end of
 914     /// the slice and works backwards.  The matched element is not contained in
 915     /// the subslices.
 916     ///
 917     /// The last element returned, if any, will contain the remainder of the
 918     /// slice.
 919     ///
 920     /// # Examples
 921     ///
 922     /// Print the slice split once, starting from the end, by numbers divisible
 923     /// by 3 (i.e. `[50]`, `[10, 40, 30, 20]`):
 924     ///
 925     /// ```
 926     /// let v = [10, 40, 30, 20, 60, 50];
 927     ///
 928     /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
 929     ///     println!("{:?}", group);
 930     /// }
 931     /// ```
 932     #[stable(feature = "rust1", since = "1.0.0")]
 933     #[inline]
 934     pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<T, F>
 935         where F: FnMut(&T) -> bool
 936     {
 937         core_slice::SliceExt::rsplitn(self, n, pred)
 938     }
 939
 940     /// Returns an iterator over subslices separated by elements that match
 941     /// `pred` limited to returning at most `n` items. This starts at the end of
 942     /// the slice and works backwards. The matched element is not contained in
 943     /// the subslices.
 944     ///
 945     /// The last element returned, if any, will contain the remainder of the
 946     /// slice.
 947     ///
 948     /// # Examples
 949     ///
 950     /// ```
 951     /// let mut s = [10, 40, 30, 20, 60, 50];
 952     ///
 953     /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
 954     ///     group[0] = 1;
 955     /// }
 956     /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
 957     /// ```
 958     #[stable(feature = "rust1", since = "1.0.0")]
 959     #[inline]
 960     pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<T, F>
 961         where F: FnMut(&T) -> bool
 962     {
 963         core_slice::SliceExt::rsplitn_mut(self, n, pred)
 964     }
 965
 966     /// Returns `true` if the slice contains an element with the given value.
 967     ///
 968     /// # Examples
 969     ///
 970     /// ```
 971     /// let v = [10, 40, 30];
 972     /// assert!(v.contains(&30));
 973     /// assert!(!v.contains(&50));
 974     /// ```
 975     #[stable(feature = "rust1", since = "1.0.0")]
 976     pub fn contains(&self, x: &T) -> bool
 977         where T: PartialEq
 978     {
 979         core_slice::SliceExt::contains(self, x)
 980     }
 981
 982     /// Returns `true` if `needle` is a prefix of the slice.
 983     ///
 984     /// # Examples
 985     ///
 986     /// ```
 987     /// let v = [10, 40, 30];
 988     /// assert!(v.starts_with(&[10]));
 989     /// assert!(v.starts_with(&[10, 40]));
 990     /// assert!(!v.starts_with(&[50]));
 991     /// assert!(!v.starts_with(&[10, 50]));
 992     /// ```
 993     ///
 994     /// Always returns `true` if `needle` is an empty slice:
 995     ///
 996     /// ```
 997     /// let v = &[10, 40, 30];
 998     /// assert!(v.starts_with(&[]));
 999     /// let v: &[u8] = &[];
1000     /// assert!(v.starts_with(&[]));
1001     /// ```
1002     #[stable(feature = "rust1", since = "1.0.0")]
1003     pub fn starts_with(&self, needle: &[T]) -> bool
1004         where T: PartialEq
1005     {
1006         core_slice::SliceExt::starts_with(self, needle)
1007     }
1008
1009     /// Returns `true` if `needle` is a suffix of the slice.
1010     ///
1011     /// # Examples
1012     ///
1013     /// ```
1014     /// let v = [10, 40, 30];
1015     /// assert!(v.ends_with(&[30]));
1016     /// assert!(v.ends_with(&[40, 30]));
1017     /// assert!(!v.ends_with(&[50]));
1018     /// assert!(!v.ends_with(&[50, 30]));
1019     /// ```
1020     ///
1021     /// Always returns `true` if `needle` is an empty slice:
1022     ///
1023     /// ```
1024     /// let v = &[10, 40, 30];
1025     /// assert!(v.ends_with(&[]));
1026     /// let v: &[u8] = &[];
1027     /// assert!(v.ends_with(&[]));
1028     /// ```
1029     #[stable(feature = "rust1", since = "1.0.0")]
1030     pub fn ends_with(&self, needle: &[T]) -> bool
1031         where T: PartialEq
1032     {
1033         core_slice::SliceExt::ends_with(self, needle)
1034     }
1035
1036     /// Binary searches this sorted slice for a given element.
1037     ///
1038     /// If the value is found then `Ok` is returned, containing the
1039     /// index of the matching element; if the value is not found then
1040     /// `Err` is returned, containing the index where a matching
1041     /// element could be inserted while maintaining sorted order.
1042     ///
1043     /// # Example
1044     ///
1045     /// Looks up a series of four elements. The first is found, with a
1046     /// uniquely determined position; the second and third are not
1047     /// found; the fourth could match any position in `[1, 4]`.
1048     ///
1049     /// ```
1050     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1051     ///
1052     /// assert_eq!(s.binary_search(&13),  Ok(9));
1053     /// assert_eq!(s.binary_search(&4),   Err(7));
1054     /// assert_eq!(s.binary_search(&100), Err(13));
1055     /// let r = s.binary_search(&1);
1056     /// assert!(match r { Ok(1...4) => true, _ => false, });
1057     /// ```
1058     #[stable(feature = "rust1", since = "1.0.0")]
1059     pub fn binary_search(&self, x: &T) -> Result<usize, usize>
1060         where T: Ord
1061     {
1062         core_slice::SliceExt::binary_search(self, x)
1063     }
1064
1065     /// Binary searches this sorted slice with a comparator function.
1066     ///
1067     /// The comparator function should implement an order consistent
1068     /// with the sort order of the underlying slice, returning an
1069     /// order code that indicates whether its argument is `Less`,
1070     /// `Equal` or `Greater` the desired target.
1071     ///
1072     /// If a matching value is found then returns `Ok`, containing
1073     /// the index for the matched element; if no match is found then
1074     /// `Err` is returned, containing the index where a matching
1075     /// element could be inserted while maintaining sorted order.
1076     ///
1077     /// # Example
1078     ///
1079     /// Looks up a series of four elements. The first is found, with a
1080     /// uniquely determined position; the second and third are not
1081     /// found; the fourth could match any position in `[1, 4]`.
1082     ///
1083     /// ```
1084     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1085     ///
1086     /// let seek = 13;
1087     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
1088     /// let seek = 4;
1089     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
1090     /// let seek = 100;
1091     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
1092     /// let seek = 1;
1093     /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
1094     /// assert!(match r { Ok(1...4) => true, _ => false, });
1095     /// ```
1096     #[stable(feature = "rust1", since = "1.0.0")]
1097     #[inline]
1098     pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>
1099         where F: FnMut(&'a T) -> Ordering
1100     {
1101         core_slice::SliceExt::binary_search_by(self, f)
1102     }
1103
1104     /// Binary searches this sorted slice with a key extraction function.
1105     ///
1106     /// Assumes that the slice is sorted by the key, for instance with
1107     /// [`sort_by_key`] using the same key extraction function.
1108     ///
1109     /// If a matching value is found then returns `Ok`, containing the
1110     /// index for the matched element; if no match is found then `Err`
1111     /// is returned, containing the index where a matching element could
1112     /// be inserted while maintaining sorted order.
1113     ///
1114     /// [`sort_by_key`]: #method.sort_by_key
1115     ///
1116     /// # Examples
1117     ///
1118     /// Looks up a series of four elements in a slice of pairs sorted by
1119     /// their second elements. The first is found, with a uniquely
1120     /// determined position; the second and third are not found; the
1121     /// fourth could match any position in `[1, 4]`.
1122     ///
1123     /// ```
1124     /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
1125     ///          (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
1126     ///          (1, 21), (2, 34), (4, 55)];
1127     ///
1128     /// assert_eq!(s.binary_search_by_key(&13, |&(a,b)| b),  Ok(9));
1129     /// assert_eq!(s.binary_search_by_key(&4, |&(a,b)| b),   Err(7));
1130     /// assert_eq!(s.binary_search_by_key(&100, |&(a,b)| b), Err(13));
1131     /// let r = s.binary_search_by_key(&1, |&(a,b)| b);
1132     /// assert!(match r { Ok(1...4) => true, _ => false, });
1133     /// ```
1134     #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
1135     #[inline]
1136     pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, f: F) -> Result<usize, usize>
1137         where F: FnMut(&'a T) -> B,
1138               B: Ord
1139     {
1140         core_slice::SliceExt::binary_search_by_key(self, b, f)
1141     }
1142
1143     /// Sorts the slice.
1144     ///
1145     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1146     ///
1147     /// # Current implementation
1148     ///
1149     /// The current algorithm is an adaptive, iterative merge sort inspired by
1150     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1151     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1152     /// two or more sorted sequences concatenated one after another.
1153     ///
1154     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1155     /// non-allocating insertion sort is used instead.
1156     ///
1157     /// # Examples
1158     ///
1159     /// ```
1160     /// let mut v = [-5, 4, 1, -3, 2];
1161     ///
1162     /// v.sort();
1163     /// assert!(v == [-5, -3, 1, 2, 4]);
1164     /// ```
1165     #[stable(feature = "rust1", since = "1.0.0")]
1166     #[inline]
1167     pub fn sort(&mut self)
1168         where T: Ord
1169     {
1170         merge_sort(self, |a, b| a.lt(b));
1171     }
1172
1173     /// Sorts the slice with a comparator function.
1174     ///
1175     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1176     ///
1177     /// # Current implementation
1178     ///
1179     /// The current algorithm is an adaptive, iterative merge sort inspired by
1180     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1181     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1182     /// two or more sorted sequences concatenated one after another.
1183     ///
1184     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1185     /// non-allocating insertion sort is used instead.
1186     ///
1187     /// # Examples
1188     ///
1189     /// ```
1190     /// let mut v = [5, 4, 1, 3, 2];
1191     /// v.sort_by(|a, b| a.cmp(b));
1192     /// assert!(v == [1, 2, 3, 4, 5]);
1193     ///
1194     /// // reverse sorting
1195     /// v.sort_by(|a, b| b.cmp(a));
1196     /// assert!(v == [5, 4, 3, 2, 1]);
1197     /// ```
1198     #[stable(feature = "rust1", since = "1.0.0")]
1199     #[inline]
1200     pub fn sort_by<F>(&mut self, mut compare: F)
1201         where F: FnMut(&T, &T) -> Ordering
1202     {
1203         merge_sort(self, |a, b| compare(a, b) == Less);
1204     }
1205
1206     /// Sorts the slice with a key extraction function.
1207     ///
1208     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1209     ///
1210     /// # Current implementation
1211     ///
1212     /// The current algorithm is an adaptive, iterative merge sort inspired by
1213     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1214     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1215     /// two or more sorted sequences concatenated one after another.
1216     ///
1217     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1218     /// non-allocating insertion sort is used instead.
1219     ///
1220     /// # Examples
1221     ///
1222     /// ```
1223     /// let mut v = [-5i32, 4, 1, -3, 2];
1224     ///
1225     /// v.sort_by_key(|k| k.abs());
1226     /// assert!(v == [1, 2, -3, 4, -5]);
1227     /// ```
1228     #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
1229     #[inline]
1230     pub fn sort_by_key<B, F>(&mut self, mut f: F)
1231         where F: FnMut(&T) -> B, B: Ord
1232     {
1233         merge_sort(self, |a, b| f(a).lt(&f(b)));
1234     }
1235
1236     /// Sorts the slice, but may not preserve the order of equal elements.
1237     ///
1238     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1239     /// and `O(n log n)` worst-case.
1240     ///
1241     /// # Current implementation
1242     ///
1243     /// The current algorithm is based on Orson Peters' [pattern-defeating quicksort][pdqsort],
1244     /// which is a quicksort variant designed to be very fast on certain kinds of patterns,
1245     /// sometimes achieving linear time. It is randomized but deterministic, and falls back to
1246     /// heapsort on degenerate inputs.
1247     ///
1248     /// It is generally faster than stable sorting, except in a few special cases, e.g. when the
1249     /// slice consists of several concatenated sorted sequences.
1250     ///
1251     /// # Examples
1252     ///
1253     /// ```
1254     /// #![feature(sort_unstable)]
1255     ///
1256     /// let mut v = [-5, 4, 1, -3, 2];
1257     ///
1258     /// v.sort_unstable();
1259     /// assert!(v == [-5, -3, 1, 2, 4]);
1260     /// ```
1261     ///
1262     /// [pdqsort]: https://github.com/orlp/pdqsort
1263     // FIXME #40585: Mention `sort_unstable` in the documentation for `sort`.
1264     #[unstable(feature = "sort_unstable", issue = "40585")]
1265     #[inline]
1266     pub fn sort_unstable(&mut self)
1267         where T: Ord
1268     {
1269         core_slice::SliceExt::sort_unstable(self);
1270     }
1271
1272     /// Sorts the slice with a comparator function, but may not preserve the order of equal
1273     /// elements.
1274     ///
1275     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1276     /// and `O(n log n)` worst-case.
1277     ///
1278     /// # Current implementation
1279     ///
1280     /// The current algorithm is based on Orson Peters' [pattern-defeating quicksort][pdqsort],
1281     /// which is a quicksort variant designed to be very fast on certain kinds of patterns,
1282     /// sometimes achieving linear time. It is randomized but deterministic, and falls back to
1283     /// heapsort on degenerate inputs.
1284     ///
1285     /// It is generally faster than stable sorting, except in a few special cases, e.g. when the
1286     /// slice consists of several concatenated sorted sequences.
1287     ///
1288     /// # Examples
1289     ///
1290     /// ```
1291     /// #![feature(sort_unstable)]
1292     ///
1293     /// let mut v = [5, 4, 1, 3, 2];
1294     /// v.sort_unstable_by(|a, b| a.cmp(b));
1295     /// assert!(v == [1, 2, 3, 4, 5]);
1296     ///
1297     /// // reverse sorting
1298     /// v.sort_unstable_by(|a, b| b.cmp(a));
1299     /// assert!(v == [5, 4, 3, 2, 1]);
1300     /// ```
1301     ///
1302     /// [pdqsort]: https://github.com/orlp/pdqsort
1303     // FIXME #40585: Mention `sort_unstable_by` in the documentation for `sort_by`.
1304     #[unstable(feature = "sort_unstable", issue = "40585")]
1305     #[inline]
1306     pub fn sort_unstable_by<F>(&mut self, compare: F)
1307         where F: FnMut(&T, &T) -> Ordering
1308     {
1309         core_slice::SliceExt::sort_unstable_by(self, compare);
1310     }
1311
1312     /// Sorts the slice with a key extraction function, but may not preserve the order of equal
1313     /// elements.
1314     ///
1315     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1316     /// and `O(n log n)` worst-case.
1317     ///
1318     /// # Current implementation
1319     ///
1320     /// The current algorithm is based on Orson Peters' [pattern-defeating quicksort][pdqsort],
1321     /// which is a quicksort variant designed to be very fast on certain kinds of patterns,
1322     /// sometimes achieving linear time. It is randomized but deterministic, and falls back to
1323     /// heapsort on degenerate inputs.
1324     ///
1325     /// It is generally faster than stable sorting, except in a few special cases, e.g. when the
1326     /// slice consists of several concatenated sorted sequences.
1327     ///
1328     /// # Examples
1329     ///
1330     /// ```
1331     /// #![feature(sort_unstable)]
1332     ///
1333     /// let mut v = [-5i32, 4, 1, -3, 2];
1334     ///
1335     /// v.sort_unstable_by_key(|k| k.abs());
1336     /// assert!(v == [1, 2, -3, 4, -5]);
1337     /// ```
1338     ///
1339     /// [pdqsort]: https://github.com/orlp/pdqsort
1340     // FIXME #40585: Mention `sort_unstable_by_key` in the documentation for `sort_by_key`.
1341     #[unstable(feature = "sort_unstable", issue = "40585")]
1342     #[inline]
1343     pub fn sort_unstable_by_key<B, F>(&mut self, f: F)
1344         where F: FnMut(&T) -> B,
1345               B: Ord
1346     {
1347         core_slice::SliceExt::sort_unstable_by_key(self, f);
1348     }
1349
1350     /// Copies the elements from `src` into `self`.
1351     ///
1352     /// The length of `src` must be the same as `self`.
1353     ///
1354     /// If `src` implements `Copy`, it can be more performant to use
1355     /// [`copy_from_slice`].
1356     ///
1357     /// # Panics
1358     ///
1359     /// This function will panic if the two slices have different lengths.
1360     ///
1361     /// # Example
1362     ///
1363     /// ```
1364     /// let mut dst = [0, 0, 0];
1365     /// let src = [1, 2, 3];
1366     ///
1367     /// dst.clone_from_slice(&src);
1368     /// assert!(dst == [1, 2, 3]);
1369     /// ```
1370     ///
1371     /// [`copy_from_slice`]: #method.copy_from_slice
1372     #[stable(feature = "clone_from_slice", since = "1.7.0")]
1373     pub fn clone_from_slice(&mut self, src: &[T]) where T: Clone {
1374         core_slice::SliceExt::clone_from_slice(self, src)
1375     }
1376
1377     /// Copies all elements from `src` into `self`, using a memcpy.
1378     ///
1379     /// The length of `src` must be the same as `self`.
1380     ///
1381     /// If `src` does not implement `Copy`, use [`clone_from_slice`].
1382     ///
1383     /// # Panics
1384     ///
1385     /// This function will panic if the two slices have different lengths.
1386     ///
1387     /// # Example
1388     ///
1389     /// ```
1390     /// let mut dst = [0, 0, 0];
1391     /// let src = [1, 2, 3];
1392     ///
1393     /// dst.copy_from_slice(&src);
1394     /// assert_eq!(src, dst);
1395     /// ```
1396     ///
1397     /// [`clone_from_slice`]: #method.clone_from_slice
1398     #[stable(feature = "copy_from_slice", since = "1.9.0")]
1399     pub fn copy_from_slice(&mut self, src: &[T]) where T: Copy {
1400         core_slice::SliceExt::copy_from_slice(self, src)
1401     }
1402
1403     /// Copies `self` into a new `Vec`.
1404     ///
1405     /// # Examples
1406     ///
1407     /// ```
1408     /// let s = [10, 40, 30];
1409     /// let x = s.to_vec();
1410     /// // Here, `s` and `x` can be modified independently.
1411     /// ```
1412     #[stable(feature = "rust1", since = "1.0.0")]
1413     #[inline]
1414     pub fn to_vec(&self) -> Vec<T>
1415         where T: Clone
1416     {
1417         // NB see hack module in this file
1418         hack::to_vec(self)
1419     }
1420
1421     /// Converts `self` into a vector without clones or allocation.
1422     ///
1423     /// The resulting vector can be converted back into a box via
1424     /// `Vec<T>`'s `into_boxed_slice` method.
1425     ///
1426     /// # Examples
1427     ///
1428     /// ```
1429     /// let s: Box<[i32]> = Box::new([10, 40, 30]);
1430     /// let x = s.into_vec();
1431     /// // `s` cannot be used anymore because it has been converted into `x`.
1432     ///
1433     /// assert_eq!(x, vec![10, 40, 30]);
1434     /// ```
1435     #[stable(feature = "rust1", since = "1.0.0")]
1436     #[inline]
1437     pub fn into_vec(self: Box<Self>) -> Vec<T> {
1438         // NB see hack module in this file
1439         hack::into_vec(self)
1440     }
1441 }
1442
1443 ////////////////////////////////////////////////////////////////////////////////
1444 // Extension traits for slices over specific kinds of data
1445 ////////////////////////////////////////////////////////////////////////////////
1446 #[unstable(feature = "slice_concat_ext",
1447            reason = "trait should not have to exist",
1448            issue = "27747")]
1449 /// An extension trait for concatenating slices
1450 pub trait SliceConcatExt<T: ?Sized> {
1451     #[unstable(feature = "slice_concat_ext",
1452                reason = "trait should not have to exist",
1453                issue = "27747")]
1454     /// The resulting type after concatenation
1455     type Output;
1456
1457     /// Flattens a slice of `T` into a single value `Self::Output`.
1458     ///
1459     /// # Examples
1460     ///
1461     /// ```
1462     /// assert_eq!(["hello", "world"].concat(), "helloworld");
1463     /// ```
1464     #[stable(feature = "rust1", since = "1.0.0")]
1465     fn concat(&self) -> Self::Output;
1466
1467     /// Flattens a slice of `T` into a single value `Self::Output`, placing a
1468     /// given separator between each.
1469     ///
1470     /// # Examples
1471     ///
1472     /// ```
1473     /// assert_eq!(["hello", "world"].join(" "), "hello world");
1474     /// ```
1475     #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
1476     fn join(&self, sep: &T) -> Self::Output;
1477
1478     #[stable(feature = "rust1", since = "1.0.0")]
1479     #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
1480     fn connect(&self, sep: &T) -> Self::Output;
1481 }
1482
1483 #[unstable(feature = "slice_concat_ext",
1484            reason = "trait should not have to exist",
1485            issue = "27747")]
1486 impl<T: Clone, V: Borrow<[T]>> SliceConcatExt<T> for [V] {
1487     type Output = Vec<T>;
1488
1489     fn concat(&self) -> Vec<T> {
1490         let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
1491         let mut result = Vec::with_capacity(size);
1492         for v in self {
1493             result.extend_from_slice(v.borrow())
1494         }
1495         result
1496     }
1497
1498     fn join(&self, sep: &T) -> Vec<T> {
1499         let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
1500         let mut result = Vec::with_capacity(size + self.len());
1501         let mut first = true;
1502         for v in self {
1503             if first {
1504                 first = false
1505             } else {
1506                 result.push(sep.clone())
1507             }
1508             result.extend_from_slice(v.borrow())
1509         }
1510         result
1511     }
1512
1513     fn connect(&self, sep: &T) -> Vec<T> {
1514         self.join(sep)
1515     }
1516 }
1517
1518 ////////////////////////////////////////////////////////////////////////////////
1519 // Standard trait implementations for slices
1520 ////////////////////////////////////////////////////////////////////////////////
1521
1522 #[stable(feature = "rust1", since = "1.0.0")]
1523 impl<T> Borrow<[T]> for Vec<T> {
1524     fn borrow(&self) -> &[T] {
1525         &self[..]
1526     }
1527 }
1528
1529 #[stable(feature = "rust1", since = "1.0.0")]
1530 impl<T> BorrowMut<[T]> for Vec<T> {
1531     fn borrow_mut(&mut self) -> &mut [T] {
1532         &mut self[..]
1533     }
1534 }
1535
1536 #[stable(feature = "rust1", since = "1.0.0")]
1537 impl<T: Clone> ToOwned for [T] {
1538     type Owned = Vec<T>;
1539     #[cfg(not(test))]
1540     fn to_owned(&self) -> Vec<T> {
1541         self.to_vec()
1542     }
1543
1544     #[cfg(test)]
1545     fn to_owned(&self) -> Vec<T> {
1546         hack::to_vec(self)
1547     }
1548
1549     fn clone_into(&self, target: &mut Vec<T>) {
1550         // drop anything in target that will not be overwritten
1551         target.truncate(self.len());
1552         let len = target.len();
1553
1554         // reuse the contained values' allocations/resources.
1555         target.clone_from_slice(&self[..len]);
1556
1557         // target.len <= self.len due to the truncate above, so the
1558         // slice here is always in-bounds.
1559         target.extend_from_slice(&self[len..]);
1560     }
1561 }
1562
1563 ////////////////////////////////////////////////////////////////////////////////
1564 // Sorting
1565 ////////////////////////////////////////////////////////////////////////////////
1566
1567 /// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted.
1568 ///
1569 /// This is the integral subroutine of insertion sort.
1570 fn insert_head<T, F>(v: &mut [T], is_less: &mut F)
1571     where F: FnMut(&T, &T) -> bool
1572 {
1573     if v.len() >= 2 && is_less(&v[1], &v[0]) {
1574         unsafe {
1575             // There are three ways to implement insertion here:
1576             //
1577             // 1. Swap adjacent elements until the first one gets to its final destination.
1578             //    However, this way we copy data around more than is necessary. If elements are big
1579             //    structures (costly to copy), this method will be slow.
1580             //
1581             // 2. Iterate until the right place for the first element is found. Then shift the
1582             //    elements succeeding it to make room for it and finally place it into the
1583             //    remaining hole. This is a good method.
1584             //
1585             // 3. Copy the first element into a temporary variable. Iterate until the right place
1586             //    for it is found. As we go along, copy every traversed element into the slot
1587             //    preceding it. Finally, copy data from the temporary variable into the remaining
1588             //    hole. This method is very good. Benchmarks demonstrated slightly better
1589             //    performance than with the 2nd method.
1590             //
1591             // All methods were benchmarked, and the 3rd showed best results. So we chose that one.
1592             let mut tmp = mem::ManuallyDrop::new(ptr::read(&v[0]));
1593
1594             // Intermediate state of the insertion process is always tracked by `hole`, which
1595             // serves two purposes:
1596             // 1. Protects integrity of `v` from panics in `is_less`.
1597             // 2. Fills the remaining hole in `v` in the end.
1598             //
1599             // Panic safety:
1600             //
1601             // If `is_less` panics at any point during the process, `hole` will get dropped and
1602             // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it
1603             // initially held exactly once.
1604             let mut hole = InsertionHole {
1605                 src: &mut *tmp,
1606                 dest: &mut v[1],
1607             };
1608             ptr::copy_nonoverlapping(&v[1], &mut v[0], 1);
1609
1610             for i in 2..v.len() {
1611                 if !is_less(&v[i], &*tmp) {
1612                     break;
1613                 }
1614                 ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1);
1615                 hole.dest = &mut v[i];
1616             }
1617             // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`.
1618         }
1619     }
1620
1621     // When dropped, copies from `src` into `dest`.
1622     struct InsertionHole<T> {
1623         src: *mut T,
1624         dest: *mut T,
1625     }
1626
1627     impl<T> Drop for InsertionHole<T> {
1628         fn drop(&mut self) {
1629             unsafe { ptr::copy_nonoverlapping(self.src, self.dest, 1); }
1630         }
1631     }
1632 }
1633
1634 /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and
1635 /// stores the result into `v[..]`.
1636 ///
1637 /// # Safety
1638 ///
1639 /// The two slices must be non-empty and `mid` must be in bounds. Buffer `buf` must be long enough
1640 /// to hold a copy of the shorter slice. Also, `T` must not be a zero-sized type.
1641 unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
1642     where F: FnMut(&T, &T) -> bool
1643 {
1644     let len = v.len();
1645     let v = v.as_mut_ptr();
1646     let v_mid = v.offset(mid as isize);
1647     let v_end = v.offset(len as isize);
1648
1649     // The merge process first copies the shorter run into `buf`. Then it traces the newly copied
1650     // run and the longer run forwards (or backwards), comparing their next unconsumed elements and
1651     // copying the lesser (or greater) one into `v`.
1652     //
1653     // As soon as the shorter run is fully consumed, the process is done. If the longer run gets
1654     // consumed first, then we must copy whatever is left of the shorter run into the remaining
1655     // hole in `v`.
1656     //
1657     // Intermediate state of the process is always tracked by `hole`, which serves two purposes:
1658     // 1. Protects integrity of `v` from panics in `is_less`.
1659     // 2. Fills the remaining hole in `v` if the longer run gets consumed first.
1660     //
1661     // Panic safety:
1662     //
1663     // If `is_less` panics at any point during the process, `hole` will get dropped and fill the
1664     // hole in `v` with the unconsumed range in `buf`, thus ensuring that `v` still holds every
1665     // object it initially held exactly once.
1666     let mut hole;
1667
1668     if mid <= len - mid {
1669         // The left run is shorter.
1670         ptr::copy_nonoverlapping(v, buf, mid);
1671         hole = MergeHole {
1672             start: buf,
1673             end: buf.offset(mid as isize),
1674             dest: v,
1675         };
1676
1677         // Initially, these pointers point to the beginnings of their arrays.
1678         let left = &mut hole.start;
1679         let mut right = v_mid;
1680         let out = &mut hole.dest;
1681
1682         while *left < hole.end && right < v_end {
1683             // Consume the lesser side.
1684             // If equal, prefer the left run to maintain stability.
1685             let to_copy = if is_less(&*right, &**left) {
1686                 get_and_increment(&mut right)
1687             } else {
1688                 get_and_increment(left)
1689             };
1690             ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1);
1691         }
1692     } else {
1693         // The right run is shorter.
1694         ptr::copy_nonoverlapping(v_mid, buf, len - mid);
1695         hole = MergeHole {
1696             start: buf,
1697             end: buf.offset((len - mid) as isize),
1698             dest: v_mid,
1699         };
1700
1701         // Initially, these pointers point past the ends of their arrays.
1702         let left = &mut hole.dest;
1703         let right = &mut hole.end;
1704         let mut out = v_end;
1705
1706         while v < *left && buf < *right {
1707             // Consume the greater side.
1708             // If equal, prefer the right run to maintain stability.
1709             let to_copy = if is_less(&*right.offset(-1), &*left.offset(-1)) {
1710                 decrement_and_get(left)
1711             } else {
1712                 decrement_and_get(right)
1713             };
1714             ptr::copy_nonoverlapping(to_copy, decrement_and_get(&mut out), 1);
1715         }
1716     }
1717     // Finally, `hole` gets dropped. If the shorter run was not fully consumed, whatever remains of
1718     // it will now be copied into the hole in `v`.
1719
1720     unsafe fn get_and_increment<T>(ptr: &mut *mut T) -> *mut T {
1721         let old = *ptr;
1722         *ptr = ptr.offset(1);
1723         old
1724     }
1725
1726     unsafe fn decrement_and_get<T>(ptr: &mut *mut T) -> *mut T {
1727         *ptr = ptr.offset(-1);
1728         *ptr
1729     }
1730
1731     // When dropped, copies the range `start..end` into `dest..`.
1732     struct MergeHole<T> {
1733         start: *mut T,
1734         end: *mut T,
1735         dest: *mut T,
1736     }
1737
1738     impl<T> Drop for MergeHole<T> {
1739         fn drop(&mut self) {
1740             // `T` is not a zero-sized type, so it's okay to divide by it's size.
1741             let len = (self.end as usize - self.start as usize) / mem::size_of::<T>();
1742             unsafe { ptr::copy_nonoverlapping(self.start, self.dest, len); }
1743         }
1744     }
1745 }
1746
1747 /// This merge sort borrows some (but not all) ideas from TimSort, which is described in detail
1748 /// [here](http://svn.python.org/projects/python/trunk/Objects/listsort.txt).
1749 ///
1750 /// The algorithm identifies strictly descending and non-descending subsequences, which are called
1751 /// natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed
1752 /// onto the stack, and then some pairs of adjacent runs are merged until these two invariants are
1753 /// satisfied:
1754 ///
1755 /// 1. for every `i` in `1..runs.len()`: `runs[i - 1].len > runs[i].len`
1756 /// 2. for every `i` in `2..runs.len()`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
1757 ///
1758 /// The invariants ensure that the total running time is `O(n log n)` worst-case.
1759 fn merge_sort<T, F>(v: &mut [T], mut is_less: F)
1760     where F: FnMut(&T, &T) -> bool
1761 {
1762     // Slices of up to this length get sorted using insertion sort.
1763     const MAX_INSERTION: usize = 20;
1764     // Very short runs are extended using insertion sort to span at least this many elements.
1765     const MIN_RUN: usize = 10;
1766
1767     // Sorting has no meaningful behavior on zero-sized types.
1768     if size_of::<T>() == 0 {
1769         return;
1770     }
1771
1772     let len = v.len();
1773
1774     // Short arrays get sorted in-place via insertion sort to avoid allocations.
1775     if len <= MAX_INSERTION {
1776         if len >= 2 {
1777             for i in (0..len-1).rev() {
1778                 insert_head(&mut v[i..], &mut is_less);
1779             }
1780         }
1781         return;
1782     }
1783
1784     // Allocate a buffer to use as scratch memory. We keep the length 0 so we can keep in it
1785     // shallow copies of the contents of `v` without risking the dtors running on copies if
1786     // `is_less` panics. When merging two sorted runs, this buffer holds a copy of the shorter run,
1787     // which will always have length at most `len / 2`.
1788     let mut buf = Vec::with_capacity(len / 2);
1789
1790     // In order to identify natural runs in `v`, we traverse it backwards. That might seem like a
1791     // strange decision, but consider the fact that merges more often go in the opposite direction
1792     // (forwards). According to benchmarks, merging forwards is slightly faster than merging
1793     // backwards. To conclude, identifying runs by traversing backwards improves performance.
1794     let mut runs = vec![];
1795     let mut end = len;
1796     while end > 0 {
1797         // Find the next natural run, and reverse it if it's strictly descending.
1798         let mut start = end - 1;
1799         if start > 0 {
1800             start -= 1;
1801             unsafe {
1802                 if is_less(v.get_unchecked(start + 1), v.get_unchecked(start)) {
1803                     while start > 0 && is_less(v.get_unchecked(start),
1804                                                v.get_unchecked(start - 1)) {
1805                         start -= 1;
1806                     }
1807                     v[start..end].reverse();
1808                 } else {
1809                     while start > 0 && !is_less(v.get_unchecked(start),
1810                                                 v.get_unchecked(start - 1)) {
1811                         start -= 1;
1812                     }
1813                 }
1814             }
1815         }
1816
1817         // Insert some more elements into the run if it's too short. Insertion sort is faster than
1818         // merge sort on short sequences, so this significantly improves performance.
1819         while start > 0 && end - start < MIN_RUN {
1820             start -= 1;
1821             insert_head(&mut v[start..end], &mut is_less);
1822         }
1823
1824         // Push this run onto the stack.
1825         runs.push(Run {
1826             start: start,
1827             len: end - start,
1828         });
1829         end = start;
1830
1831         // Merge some pairs of adjacent runs to satisfy the invariants.
1832         while let Some(r) = collapse(&runs) {
1833             let left = runs[r + 1];
1834             let right = runs[r];
1835             unsafe {
1836                 merge(&mut v[left.start .. right.start + right.len], left.len, buf.as_mut_ptr(),
1837                       &mut is_less);
1838             }
1839             runs[r] = Run {
1840                 start: left.start,
1841                 len: left.len + right.len,
1842             };
1843             runs.remove(r + 1);
1844         }
1845     }
1846
1847     // Finally, exactly one run must remain in the stack.
1848     debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);
1849
1850     // Examines the stack of runs and identifies the next pair of runs to merge. More specifically,
1851     // if `Some(r)` is returned, that means `runs[r]` and `runs[r + 1]` must be merged next. If the
1852     // algorithm should continue building a new run instead, `None` is returned.
1853     //
1854     // TimSort is infamous for it's buggy implementations, as described here:
1855     // http://envisage-project.eu/timsort-specification-and-verification/
1856     //
1857     // The gist of the story is: we must enforce the invariants on the top four runs on the stack.
1858     // Enforcing them on just top three is not sufficient to ensure that the invariants will still
1859     // hold for *all* runs in the stack.
1860     //
1861     // This function correctly checks invariants for the top four runs. Additionally, if the top
1862     // run starts at index 0, it will always demand a merge operation until the stack is fully
1863     // collapsed, in order to complete the sort.
1864     #[inline]
1865     fn collapse(runs: &[Run]) -> Option<usize> {
1866         let n = runs.len();
1867         if n >= 2 && (runs[n - 1].start == 0 ||
1868                       runs[n - 2].len <= runs[n - 1].len ||
1869                       (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len) ||
1870                       (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len)) {
1871             if n >= 3 && runs[n - 3].len < runs[n - 1].len {
1872                 Some(n - 3)
1873             } else {
1874                 Some(n - 2)
1875             }
1876         } else {
1877             None
1878         }
1879     }
1880
1881     #[derive(Clone, Copy)]
1882     struct Run {
1883         start: usize,
1884         len: usize,
1885     }
1886 }