src/libcollections/slice.rs

   1 // Copyright 2012-2014 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 //! Utilities for slice manipulation
  12 //!
  13 //! The `slice` module contains useful code to help work with slice values.
  14 //! Slices are a view into a block of memory represented as a pointer and a length.
  15 //!
  16 //! ```rust
  17 //! // slicing a Vec
  18 //! let vec = vec!(1i, 2, 3);
  19 //! let int_slice = vec.as_slice();
  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]`. For example, you can mutate the
  26 //! block of memory that a mutable slice points to:
  27 //!
  28 //! ```rust
  29 //! let x: &mut[int] = &mut [1i, 2, 3];
  30 //! x[1] = 7;
  31 //! assert_eq!(x[0], 1);
  32 //! assert_eq!(x[1], 7);
  33 //! assert_eq!(x[2], 3);
  34 //! ```
  35 //!
  36 //! Here are some of the things this module contains:
  37 //!
  38 //! ## Structs
  39 //!
  40 //! There are several structs that are useful for slices, such as `Iter`, which
  41 //! represents iteration over a slice.
  42 //!
  43 //! ## Traits
  44 //!
  45 //! A number of traits add methods that allow you to accomplish tasks
  46 //! with slices, the most important being `SliceExt`. Other traits
  47 //! apply only to slices of elements satisfying certain bounds (like
  48 //! `Ord`).
  49 //!
  50 //! An example is the `slice` method which enables slicing syntax `[a..b]` that
  51 //! returns an immutable "view" into a `Vec` or another slice from the index
  52 //! interval `[a, b)`:
  53 //!
  54 //! ```rust
  55 //! #![feature(slicing_syntax)]
  56 //! fn main() {
  57 //!     let numbers = [0i, 1i, 2i];
  58 //!     let last_numbers = &numbers[1..3];
  59 //!     // last_numbers is now &[1i, 2i]
  60 //! }
  61 //! ```
  62 //!
  63 //! ## Implementations of other traits
  64 //!
  65 //! There are several implementations of common traits for slices. Some examples
  66 //! include:
  67 //!
  68 //! * `Clone`
  69 //! * `Eq`, `Ord` - for immutable slices whose element type are `Eq` or `Ord`.
  70 //! * `Hash` - for slices whose element type is `Hash`
  71 //!
  72 //! ## Iteration
  73 //!
  74 //! The method `iter()` returns an iteration value for a slice. The iterator
  75 //! yields references to the slice's elements, so if the element
  76 //! type of the slice is `int`, the element type of the iterator is `&int`.
  77 //!
  78 //! ```rust
  79 //! let numbers = [0i, 1i, 2i];
  80 //! for &x in numbers.iter() {
  81 //!     println!("{} is a number!", x);
  82 //! }
  83 //! ```
  84 //!
  85 //! * `.iter_mut()` returns an iterator that allows modifying each value.
  86 //! * Further iterators exist that split, chunk or permute the slice.
  87
  88 #![doc(primitive = "slice")]
  89 #![stable]
  90
  91 use alloc::boxed::Box;
  92 use core::borrow::{BorrowFrom, BorrowFromMut, ToOwned};
  93 use core::clone::Clone;
  94 use core::cmp::Ordering::{self, Greater, Less};
  95 use core::cmp::{self, Ord, PartialEq};
  96 use core::iter::{Iterator, IteratorExt};
  97 use core::iter::{range, range_step, MultiplicativeIterator};
  98 use core::marker::Sized;
  99 use core::mem::size_of;
 100 use core::mem;
 101 use core::ops::{FnMut, FullRange};
 102 use core::option::Option::{self, Some, None};
 103 use core::ptr::PtrExt;
 104 use core::ptr;
 105 use core::result::Result;
 106 use core::slice as core_slice;
 107 use self::Direction::*;
 108
 109 use vec::Vec;
 110
 111 pub use core::slice::{Chunks, AsSlice, Windows};
 112 pub use core::slice::{Iter, IterMut};
 113 pub use core::slice::{IntSliceExt, SplitMut, ChunksMut, Split};
 114 pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut};
 115 pub use core::slice::{bytes, mut_ref_slice, ref_slice};
 116 pub use core::slice::{from_raw_buf, from_raw_mut_buf};
 117
 118 ////////////////////////////////////////////////////////////////////////////////
 119 // Basic slice extension methods
 120 ////////////////////////////////////////////////////////////////////////////////
 121
 122 /// Allocating extension methods for slices.
 123 #[stable]
 124 pub trait SliceExt {
 125     #[stable]
 126     type Item;
 127
 128     /// Sorts the slice, in place, using `compare` to compare
 129     /// elements.
 130     ///
 131     /// This sort is `O(n log n)` worst-case and stable, but allocates
 132     /// approximately `2 * n`, where `n` is the length of `self`.
 133     ///
 134     /// # Examples
 135     ///
 136     /// ```rust
 137     /// let mut v = [5i, 4, 1, 3, 2];
 138     /// v.sort_by(|a, b| a.cmp(b));
 139     /// assert!(v == [1, 2, 3, 4, 5]);
 140     ///
 141     /// // reverse sorting
 142     /// v.sort_by(|a, b| b.cmp(a));
 143     /// assert!(v == [5, 4, 3, 2, 1]);
 144     /// ```
 145     #[stable]
 146     fn sort_by<F>(&mut self, compare: F) where F: FnMut(&Self::Item, &Self::Item) -> Ordering;
 147
 148     /// Consumes `src` and moves as many elements as it can into `self`
 149     /// from the range [start,end).
 150     ///
 151     /// Returns the number of elements copied (the shorter of `self.len()`
 152     /// and `end - start`).
 153     ///
 154     /// # Arguments
 155     ///
 156     /// * src - A mutable vector of `T`
 157     /// * start - The index into `src` to start copying from
 158     /// * end - The index into `src` to stop copying from
 159     ///
 160     /// # Examples
 161     ///
 162     /// ```rust
 163     /// let mut a = [1i, 2, 3, 4, 5];
 164     /// let b = vec![6i, 7, 8];
 165     /// let num_moved = a.move_from(b, 0, 3);
 166     /// assert_eq!(num_moved, 3);
 167     /// assert!(a == [6i, 7, 8, 4, 5]);
 168     /// ```
 169     #[unstable = "uncertain about this API approach"]
 170     fn move_from(&mut self, src: Vec<Self::Item>, start: uint, end: uint) -> uint;
 171
 172     /// Deprecated: use `&s[start .. end]` notation instead.
 173     #[deprecated = "use &s[start .. end] instead"]
 174     fn slice(&self, start: uint, end: uint) -> &[Self::Item];
 175
 176     /// Deprecated: use `&s[start..]` notation instead.
 177     #[deprecated = "use &s[start..] isntead"]
 178     fn slice_from(&self, start: uint) -> &[Self::Item];
 179
 180     /// Deprecated: use `&s[..end]` notation instead.
 181     #[deprecated = "use &s[..end] instead"]
 182     fn slice_to(&self, end: uint) -> &[Self::Item];
 183
 184     /// Divides one slice into two at an index.
 185     ///
 186     /// The first will contain all indices from `[0, mid)` (excluding
 187     /// the index `mid` itself) and the second will contain all
 188     /// indices from `[mid, len)` (excluding the index `len` itself).
 189     ///
 190     /// Panics if `mid > len`.
 191     #[stable]
 192     fn split_at(&self, mid: uint) -> (&[Self::Item], &[Self::Item]);
 193
 194     /// Returns an iterator over the slice
 195     #[stable]
 196     fn iter(&self) -> Iter<Self::Item>;
 197
 198     /// Returns an iterator over subslices separated by elements that match
 199     /// `pred`.  The matched element is not contained in the subslices.
 200     #[stable]
 201     fn split<F>(&self, pred: F) -> Split<Self::Item, F>
 202                 where F: FnMut(&Self::Item) -> bool;
 203
 204     /// Returns an iterator over subslices separated by elements that match
 205     /// `pred`, limited to splitting at most `n` times.  The matched element is
 206     /// not contained in the subslices.
 207     #[stable]
 208     fn splitn<F>(&self, n: uint, pred: F) -> SplitN<Self::Item, F>
 209                  where F: FnMut(&Self::Item) -> bool;
 210
 211     /// Returns an iterator over subslices separated by elements that match
 212     /// `pred` limited to splitting at most `n` times. This starts at the end of
 213     /// the slice and works backwards.  The matched element is not contained in
 214     /// the subslices.
 215     #[stable]
 216     fn rsplitn<F>(&self, n: uint, pred: F) -> RSplitN<Self::Item, F>
 217                   where F: FnMut(&Self::Item) -> bool;
 218
 219     /// Returns an iterator over all contiguous windows of length
 220     /// `size`. The windows overlap. If the slice is shorter than
 221     /// `size`, the iterator returns no values.
 222     ///
 223     /// # Panics
 224     ///
 225     /// Panics if `size` is 0.
 226     ///
 227     /// # Example
 228     ///
 229     /// Print the adjacent pairs of a slice (i.e. `[1,2]`, `[2,3]`,
 230     /// `[3,4]`):
 231     ///
 232     /// ```rust
 233     /// let v = &[1i, 2, 3, 4];
 234     /// for win in v.windows(2) {
 235     ///     println!("{:?}", win);
 236     /// }
 237     /// ```
 238     #[stable]
 239     fn windows(&self, size: uint) -> Windows<Self::Item>;
 240
 241     /// Returns an iterator over `size` elements of the slice at a
 242     /// time. The chunks do not overlap. If `size` does not divide the
 243     /// length of the slice, then the last chunk will not have length
 244     /// `size`.
 245     ///
 246     /// # Panics
 247     ///
 248     /// Panics if `size` is 0.
 249     ///
 250     /// # Example
 251     ///
 252     /// Print the slice two elements at a time (i.e. `[1,2]`,
 253     /// `[3,4]`, `[5]`):
 254     ///
 255     /// ```rust
 256     /// let v = &[1i, 2, 3, 4, 5];
 257     /// for win in v.chunks(2) {
 258     ///     println!("{:?}", win);
 259     /// }
 260     /// ```
 261     #[stable]
 262     fn chunks(&self, size: uint) -> Chunks<Self::Item>;
 263
 264     /// Returns the element of a slice at the given index, or `None` if the
 265     /// index is out of bounds.
 266     #[stable]
 267     fn get(&self, index: uint) -> Option<&Self::Item>;
 268
 269     /// Returns the first element of a slice, or `None` if it is empty.
 270     #[stable]
 271     fn first(&self) -> Option<&Self::Item>;
 272
 273     /// Returns all but the first element of a slice.
 274     #[unstable = "likely to be renamed"]
 275     fn tail(&self) -> &[Self::Item];
 276
 277     /// Returns all but the last element of a slice.
 278     #[unstable = "likely to be renamed"]
 279     fn init(&self) -> &[Self::Item];
 280
 281     /// Returns the last element of a slice, or `None` if it is empty.
 282     #[stable]
 283     fn last(&self) -> Option<&Self::Item>;
 284
 285     /// Returns a pointer to the element at the given index, without doing
 286     /// bounds checking.
 287     #[stable]
 288     unsafe fn get_unchecked(&self, index: uint) -> &Self::Item;
 289
 290     /// Returns an unsafe pointer to the slice's buffer
 291     ///
 292     /// The caller must ensure that the slice outlives the pointer this
 293     /// function returns, or else it will end up pointing to garbage.
 294     ///
 295     /// Modifying the slice may cause its buffer to be reallocated, which
 296     /// would also make any pointers to it invalid.
 297     #[stable]
 298     fn as_ptr(&self) -> *const Self::Item;
 299
 300     /// Binary search a sorted slice with a comparator function.
 301     ///
 302     /// The comparator function should implement an order consistent
 303     /// with the sort order of the underlying slice, returning an
 304     /// order code that indicates whether its argument is `Less`,
 305     /// `Equal` or `Greater` the desired target.
 306     ///
 307     /// If a matching value is found then returns `Ok`, containing
 308     /// the index for the matched element; if no match is found then
 309     /// `Err` is returned, containing the index where a matching
 310     /// element could be inserted while maintaining sorted order.
 311     ///
 312     /// # Example
 313     ///
 314     /// Looks up a series of four elements. The first is found, with a
 315     /// uniquely determined position; the second and third are not
 316     /// found; the fourth could match any position in `[1,4]`.
 317     ///
 318     /// ```rust
 319     /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
 320     /// let s = s.as_slice();
 321     ///
 322     /// let seek = 13;
 323     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
 324     /// let seek = 4;
 325     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
 326     /// let seek = 100;
 327     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
 328     /// let seek = 1;
 329     /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
 330     /// assert!(match r { Ok(1...4) => true, _ => false, });
 331     /// ```
 332     #[stable]
 333     fn binary_search_by<F>(&self, f: F) -> Result<uint, uint> where
 334         F: FnMut(&Self::Item) -> Ordering;
 335
 336     /// Return the number of elements in the slice
 337     ///
 338     /// # Example
 339     ///
 340     /// ```
 341     /// let a = [1i, 2, 3];
 342     /// assert_eq!(a.len(), 3);
 343     /// ```
 344     #[stable]
 345     fn len(&self) -> uint;
 346
 347     /// Returns true if the slice has a length of 0
 348     ///
 349     /// # Example
 350     ///
 351     /// ```
 352     /// let a = [1i, 2, 3];
 353     /// assert!(!a.is_empty());
 354     /// ```
 355     #[inline]
 356     #[stable]
 357     fn is_empty(&self) -> bool { self.len() == 0 }
 358     /// Returns a mutable reference to the element at the given index,
 359     /// or `None` if the index is out of bounds
 360     #[stable]
 361     fn get_mut(&mut self, index: uint) -> Option<&mut Self::Item>;
 362
 363     /// Work with `self` as a mut slice.
 364     /// Primarily intended for getting a &mut [T] from a [T; N].
 365     #[stable]
 366     fn as_mut_slice(&mut self) -> &mut [Self::Item];
 367
 368     /// Deprecated: use `&mut s[start .. end]` instead.
 369     #[deprecated = "use &mut s[start .. end] instead"]
 370     fn slice_mut(&mut self, start: uint, end: uint) -> &mut [Self::Item];
 371
 372     /// Deprecated: use `&mut s[start ..]` instead.
 373     #[deprecated = "use &mut s[start ..] instead"]
 374     fn slice_from_mut(&mut self, start: uint) -> &mut [Self::Item];
 375
 376     /// Deprecated: use `&mut s[.. end]` instead.
 377     #[deprecated = "use &mut s[.. end] instead"]
 378     fn slice_to_mut(&mut self, end: uint) -> &mut [Self::Item];
 379
 380     /// Returns an iterator that allows modifying each value
 381     #[stable]
 382     fn iter_mut(&mut self) -> IterMut<Self::Item>;
 383
 384     /// Returns a mutable pointer to the first element of a slice, or `None` if it is empty
 385     #[stable]
 386     fn first_mut(&mut self) -> Option<&mut Self::Item>;
 387
 388     /// Returns all but the first element of a mutable slice
 389     #[unstable = "likely to be renamed or removed"]
 390     fn tail_mut(&mut self) -> &mut [Self::Item];
 391
 392     /// Returns all but the last element of a mutable slice
 393     #[unstable = "likely to be renamed or removed"]
 394     fn init_mut(&mut self) -> &mut [Self::Item];
 395
 396     /// Returns a mutable pointer to the last item in the slice.
 397     #[stable]
 398     fn last_mut(&mut self) -> Option<&mut Self::Item>;
 399
 400     /// Returns an iterator over mutable subslices separated by elements that
 401     /// match `pred`.  The matched element is not contained in the subslices.
 402     #[stable]
 403     fn split_mut<F>(&mut self, pred: F) -> SplitMut<Self::Item, F>
 404                     where F: FnMut(&Self::Item) -> bool;
 405
 406     /// Returns an iterator over subslices separated by elements that match
 407     /// `pred`, limited to splitting at most `n` times.  The matched element is
 408     /// not contained in the subslices.
 409     #[stable]
 410     fn splitn_mut<F>(&mut self, n: uint, pred: F) -> SplitNMut<Self::Item, F>
 411                      where F: FnMut(&Self::Item) -> bool;
 412
 413     /// Returns an iterator over subslices separated by elements that match
 414     /// `pred` limited to splitting at most `n` times. This starts at the end of
 415     /// the slice and works backwards.  The matched element is not contained in
 416     /// the subslices.
 417     #[stable]
 418     fn rsplitn_mut<F>(&mut self,  n: uint, pred: F) -> RSplitNMut<Self::Item, F>
 419                       where F: FnMut(&Self::Item) -> bool;
 420
 421     /// Returns an iterator over `chunk_size` elements of the slice at a time.
 422     /// The chunks are mutable and do not overlap. If `chunk_size` does
 423     /// not divide the length of the slice, then the last chunk will not
 424     /// have length `chunk_size`.
 425     ///
 426     /// # Panics
 427     ///
 428     /// Panics if `chunk_size` is 0.
 429     #[stable]
 430     fn chunks_mut(&mut self, chunk_size: uint) -> ChunksMut<Self::Item>;
 431
 432     /// Swaps two elements in a slice.
 433     ///
 434     /// # Arguments
 435     ///
 436     /// * a - The index of the first element
 437     /// * b - The index of the second element
 438     ///
 439     /// # Panics
 440     ///
 441     /// Panics if `a` or `b` are out of bounds.
 442     ///
 443     /// # Example
 444     ///
 445     /// ```rust
 446     /// let mut v = ["a", "b", "c", "d"];
 447     /// v.swap(1, 3);
 448     /// assert!(v == ["a", "d", "c", "b"]);
 449     /// ```
 450     #[stable]
 451     fn swap(&mut self, a: uint, b: uint);
 452
 453     /// Divides one `&mut` into two at an index.
 454     ///
 455     /// The first will contain all indices from `[0, mid)` (excluding
 456     /// the index `mid` itself) and the second will contain all
 457     /// indices from `[mid, len)` (excluding the index `len` itself).
 458     ///
 459     /// # Panics
 460     ///
 461     /// Panics if `mid > len`.
 462     ///
 463     /// # Example
 464     ///
 465     /// ```rust
 466     /// let mut v = [1i, 2, 3, 4, 5, 6];
 467     ///
 468     /// // scoped to restrict the lifetime of the borrows
 469     /// {
 470     ///    let (left, right) = v.split_at_mut(0);
 471     ///    assert!(left == []);
 472     ///    assert!(right == [1i, 2, 3, 4, 5, 6]);
 473     /// }
 474     ///
 475     /// {
 476     ///     let (left, right) = v.split_at_mut(2);
 477     ///     assert!(left == [1i, 2]);
 478     ///     assert!(right == [3i, 4, 5, 6]);
 479     /// }
 480     ///
 481     /// {
 482     ///     let (left, right) = v.split_at_mut(6);
 483     ///     assert!(left == [1i, 2, 3, 4, 5, 6]);
 484     ///     assert!(right == []);
 485     /// }
 486     /// ```
 487     #[stable]
 488     fn split_at_mut(&mut self, mid: uint) -> (&mut [Self::Item], &mut [Self::Item]);
 489
 490     /// Reverse the order of elements in a slice, in place.
 491     ///
 492     /// # Example
 493     ///
 494     /// ```rust
 495     /// let mut v = [1i, 2, 3];
 496     /// v.reverse();
 497     /// assert!(v == [3i, 2, 1]);
 498     /// ```
 499     #[stable]
 500     fn reverse(&mut self);
 501
 502     /// Returns an unsafe mutable pointer to the element in index
 503     #[stable]
 504     unsafe fn get_unchecked_mut(&mut self, index: uint) -> &mut Self::Item;
 505
 506     /// Return an unsafe mutable pointer to the slice's buffer.
 507     ///
 508     /// The caller must ensure that the slice outlives the pointer this
 509     /// function returns, or else it will end up pointing to garbage.
 510     ///
 511     /// Modifying the slice may cause its buffer to be reallocated, which
 512     /// would also make any pointers to it invalid.
 513     #[inline]
 514     #[stable]
 515     fn as_mut_ptr(&mut self) -> *mut Self::Item;
 516
 517     /// Copies `self` into a new `Vec`.
 518     #[stable]
 519     fn to_vec(&self) -> Vec<Self::Item> where Self::Item: Clone;
 520
 521     /// Creates an iterator that yields every possible permutation of the
 522     /// vector in succession.
 523     ///
 524     /// # Examples
 525     ///
 526     /// ```rust
 527     /// let v = [1i, 2, 3];
 528     /// let mut perms = v.permutations();
 529     ///
 530     /// for p in perms {
 531     ///   println!("{:?}", p);
 532     /// }
 533     /// ```
 534     ///
 535     /// Iterating through permutations one by one.
 536     ///
 537     /// ```rust
 538     /// let v = [1i, 2, 3];
 539     /// let mut perms = v.permutations();
 540     ///
 541     /// assert_eq!(Some(vec![1i, 2, 3]), perms.next());
 542     /// assert_eq!(Some(vec![1i, 3, 2]), perms.next());
 543     /// assert_eq!(Some(vec![3i, 1, 2]), perms.next());
 544     /// ```
 545     #[unstable]
 546     fn permutations(&self) -> Permutations<Self::Item> where Self::Item: Clone;
 547
 548     /// Copies as many elements from `src` as it can into `self` (the
 549     /// shorter of `self.len()` and `src.len()`). Returns the number
 550     /// of elements copied.
 551     ///
 552     /// # Example
 553     ///
 554     /// ```rust
 555     /// let mut dst = [0i, 0, 0];
 556     /// let src = [1i, 2];
 557     ///
 558     /// assert!(dst.clone_from_slice(&src) == 2);
 559     /// assert!(dst == [1, 2, 0]);
 560     ///
 561     /// let src2 = [3i, 4, 5, 6];
 562     /// assert!(dst.clone_from_slice(&src2) == 3);
 563     /// assert!(dst == [3i, 4, 5]);
 564     /// ```
 565     #[unstable]
 566     fn clone_from_slice(&mut self, &[Self::Item]) -> uint where Self::Item: Clone;
 567
 568     /// Sorts the slice, in place.
 569     ///
 570     /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`.
 571     ///
 572     /// # Examples
 573     ///
 574     /// ```rust
 575     /// let mut v = [-5i, 4, 1, -3, 2];
 576     ///
 577     /// v.sort();
 578     /// assert!(v == [-5i, -3, 1, 2, 4]);
 579     /// ```
 580     #[stable]
 581     fn sort(&mut self) where Self::Item: Ord;
 582
 583     /// Binary search a sorted slice for a given element.
 584     ///
 585     /// If the value is found then `Ok` is returned, containing the
 586     /// index of the matching element; if the value is not found then
 587     /// `Err` is returned, containing the index where a matching
 588     /// element could be inserted while maintaining sorted order.
 589     ///
 590     /// # Example
 591     ///
 592     /// Looks up a series of four elements. The first is found, with a
 593     /// uniquely determined position; the second and third are not
 594     /// found; the fourth could match any position in `[1,4]`.
 595     ///
 596     /// ```rust
 597     /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
 598     /// let s = s.as_slice();
 599     ///
 600     /// assert_eq!(s.binary_search(&13),  Ok(9));
 601     /// assert_eq!(s.binary_search(&4),   Err(7));
 602     /// assert_eq!(s.binary_search(&100), Err(13));
 603     /// let r = s.binary_search(&1);
 604     /// assert!(match r { Ok(1...4) => true, _ => false, });
 605     /// ```
 606     #[stable]
 607     fn binary_search(&self, x: &Self::Item) -> Result<uint, uint> where Self::Item: Ord;
 608
 609     /// Deprecated: use `binary_search` instead.
 610     #[deprecated = "use binary_search instead"]
 611     fn binary_search_elem(&self, x: &Self::Item) -> Result<uint, uint> where Self::Item: Ord {
 612         self.binary_search(x)
 613     }
 614
 615     /// Mutates the slice to the next lexicographic permutation.
 616     ///
 617     /// Returns `true` if successful and `false` if the slice is at the
 618     /// last-ordered permutation.
 619     ///
 620     /// # Example
 621     ///
 622     /// ```rust
 623     /// let v: &mut [_] = &mut [0i, 1, 2];
 624     /// v.next_permutation();
 625     /// let b: &mut [_] = &mut [0i, 2, 1];
 626     /// assert!(v == b);
 627     /// v.next_permutation();
 628     /// let b: &mut [_] = &mut [1i, 0, 2];
 629     /// assert!(v == b);
 630     /// ```
 631     #[unstable = "uncertain if this merits inclusion in std"]
 632     fn next_permutation(&mut self) -> bool where Self::Item: Ord;
 633
 634     /// Mutates the slice to the previous lexicographic permutation.
 635     ///
 636     /// Returns `true` if successful and `false` if the slice is at the
 637     /// first-ordered permutation.
 638     ///
 639     /// # Example
 640     ///
 641     /// ```rust
 642     /// let v: &mut [_] = &mut [1i, 0, 2];
 643     /// v.prev_permutation();
 644     /// let b: &mut [_] = &mut [0i, 2, 1];
 645     /// assert!(v == b);
 646     /// v.prev_permutation();
 647     /// let b: &mut [_] = &mut [0i, 1, 2];
 648     /// assert!(v == b);
 649     /// ```
 650     #[unstable = "uncertain if this merits inclusion in std"]
 651     fn prev_permutation(&mut self) -> bool where Self::Item: Ord;
 652
 653     /// Find the first index containing a matching value.
 654     #[unstable]
 655     fn position_elem(&self, t: &Self::Item) -> Option<uint> where Self::Item: PartialEq;
 656
 657     /// Find the last index containing a matching value.
 658     #[unstable]
 659     fn rposition_elem(&self, t: &Self::Item) -> Option<uint> where Self::Item: PartialEq;
 660
 661     /// Return true if the slice contains an element with the given value.
 662     #[stable]
 663     fn contains(&self, x: &Self::Item) -> bool where Self::Item: PartialEq;
 664
 665     /// Returns true if `needle` is a prefix of the slice.
 666     #[stable]
 667     fn starts_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
 668
 669     /// Returns true if `needle` is a suffix of the slice.
 670     #[stable]
 671     fn ends_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
 672
 673     /// Convert `self` into a vector without clones or allocation.
 674     #[unstable]
 675     fn into_vec(self: Box<Self>) -> Vec<Self::Item>;
 676 }
 677
 678 #[stable]
 679 impl<T> SliceExt for [T] {
 680     type Item = T;
 681
 682     #[inline]
 683     fn sort_by<F>(&mut self, compare: F) where F: FnMut(&T, &T) -> Ordering {
 684         merge_sort(self, compare)
 685     }
 686
 687     #[inline]
 688     fn move_from(&mut self, mut src: Vec<T>, start: uint, end: uint) -> uint {
 689         for (a, b) in self.iter_mut().zip(src[start .. end].iter_mut()) {
 690             mem::swap(a, b);
 691         }
 692         cmp::min(self.len(), end-start)
 693     }
 694
 695     #[inline]
 696     fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] {
 697         &self[start .. end]
 698     }
 699
 700     #[inline]
 701     fn slice_from<'a>(&'a self, start: uint) -> &'a [T] {
 702         &self[start ..]
 703     }
 704
 705     #[inline]
 706     fn slice_to<'a>(&'a self, end: uint) -> &'a [T] {
 707         &self[.. end]
 708     }
 709
 710     #[inline]
 711     fn split_at<'a>(&'a self, mid: uint) -> (&'a [T], &'a [T]) {
 712         core_slice::SliceExt::split_at(self, mid)
 713     }
 714
 715     #[inline]
 716     fn iter<'a>(&'a self) -> Iter<'a, T> {
 717         core_slice::SliceExt::iter(self)
 718     }
 719
 720     #[inline]
 721     fn split<F>(&self, pred: F) -> Split<T, F>
 722                 where F: FnMut(&T) -> bool {
 723         core_slice::SliceExt::split(self, pred)
 724     }
 725
 726     #[inline]
 727     fn splitn<F>(&self, n: uint, pred: F) -> SplitN<T, F>
 728                  where F: FnMut(&T) -> bool {
 729         core_slice::SliceExt::splitn(self, n, pred)
 730     }
 731
 732     #[inline]
 733     fn rsplitn<F>(&self, n: uint, pred: F) -> RSplitN<T, F>
 734                   where F: FnMut(&T) -> bool {
 735         core_slice::SliceExt::rsplitn(self, n, pred)
 736     }
 737
 738     #[inline]
 739     fn windows<'a>(&'a self, size: uint) -> Windows<'a, T> {
 740         core_slice::SliceExt::windows(self, size)
 741     }
 742
 743     #[inline]
 744     fn chunks<'a>(&'a self, size: uint) -> Chunks<'a, T> {
 745         core_slice::SliceExt::chunks(self, size)
 746     }
 747
 748     #[inline]
 749     fn get<'a>(&'a self, index: uint) -> Option<&'a T> {
 750         core_slice::SliceExt::get(self, index)
 751     }
 752
 753     #[inline]
 754     fn first<'a>(&'a self) -> Option<&'a T> {
 755         core_slice::SliceExt::first(self)
 756     }
 757
 758     #[inline]
 759     fn tail<'a>(&'a self) -> &'a [T] {
 760         core_slice::SliceExt::tail(self)
 761     }
 762
 763     #[inline]
 764     fn init<'a>(&'a self) -> &'a [T] {
 765         core_slice::SliceExt::init(self)
 766     }
 767
 768     #[inline]
 769     fn last<'a>(&'a self) -> Option<&'a T> {
 770         core_slice::SliceExt::last(self)
 771     }
 772
 773     #[inline]
 774     unsafe fn get_unchecked<'a>(&'a self, index: uint) -> &'a T {
 775         core_slice::SliceExt::get_unchecked(self, index)
 776     }
 777
 778     #[inline]
 779     fn as_ptr(&self) -> *const T {
 780         core_slice::SliceExt::as_ptr(self)
 781     }
 782
 783     #[inline]
 784     fn binary_search_by<F>(&self, f: F) -> Result<uint, uint>
 785                         where F: FnMut(&T) -> Ordering {
 786         core_slice::SliceExt::binary_search_by(self, f)
 787     }
 788
 789     #[inline]
 790     fn len(&self) -> uint {
 791         core_slice::SliceExt::len(self)
 792     }
 793
 794     #[inline]
 795     fn is_empty(&self) -> bool {
 796         core_slice::SliceExt::is_empty(self)
 797     }
 798
 799     #[inline]
 800     fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T> {
 801         core_slice::SliceExt::get_mut(self, index)
 802     }
 803
 804     #[inline]
 805     fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
 806         core_slice::SliceExt::as_mut_slice(self)
 807     }
 808
 809     #[inline]
 810     fn slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T] {
 811         &mut self[start .. end]
 812     }
 813
 814     #[inline]
 815     fn slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [T] {
 816         &mut self[start ..]
 817     }
 818
 819     #[inline]
 820     fn slice_to_mut<'a>(&'a mut self, end: uint) -> &'a mut [T] {
 821         &mut self[.. end]
 822     }
 823
 824     #[inline]
 825     fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
 826         core_slice::SliceExt::iter_mut(self)
 827     }
 828
 829     #[inline]
 830     fn first_mut<'a>(&'a mut self) -> Option<&'a mut T> {
 831         core_slice::SliceExt::first_mut(self)
 832     }
 833
 834     #[inline]
 835     fn tail_mut<'a>(&'a mut self) -> &'a mut [T] {
 836         core_slice::SliceExt::tail_mut(self)
 837     }
 838
 839     #[inline]
 840     fn init_mut<'a>(&'a mut self) -> &'a mut [T] {
 841         core_slice::SliceExt::init_mut(self)
 842     }
 843
 844     #[inline]
 845     fn last_mut<'a>(&'a mut self) -> Option<&'a mut T> {
 846         core_slice::SliceExt::last_mut(self)
 847     }
 848
 849     #[inline]
 850     fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F>
 851                     where F: FnMut(&T) -> bool {
 852         core_slice::SliceExt::split_mut(self, pred)
 853     }
 854
 855     #[inline]
 856     fn splitn_mut<F>(&mut self, n: uint, pred: F) -> SplitNMut<T, F>
 857                      where F: FnMut(&T) -> bool {
 858         core_slice::SliceExt::splitn_mut(self, n, pred)
 859     }
 860
 861     #[inline]
 862     fn rsplitn_mut<F>(&mut self,  n: uint, pred: F) -> RSplitNMut<T, F>
 863                       where F: FnMut(&T) -> bool {
 864         core_slice::SliceExt::rsplitn_mut(self, n, pred)
 865     }
 866
 867     #[inline]
 868     fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> ChunksMut<'a, T> {
 869         core_slice::SliceExt::chunks_mut(self, chunk_size)
 870     }
 871
 872     #[inline]
 873     fn swap(&mut self, a: uint, b: uint) {
 874         core_slice::SliceExt::swap(self, a, b)
 875     }
 876
 877     #[inline]
 878     fn split_at_mut<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
 879         core_slice::SliceExt::split_at_mut(self, mid)
 880     }
 881
 882     #[inline]
 883     fn reverse(&mut self) {
 884         core_slice::SliceExt::reverse(self)
 885     }
 886
 887     #[inline]
 888     unsafe fn get_unchecked_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
 889         core_slice::SliceExt::get_unchecked_mut(self, index)
 890     }
 891
 892     #[inline]
 893     fn as_mut_ptr(&mut self) -> *mut T {
 894         core_slice::SliceExt::as_mut_ptr(self)
 895     }
 896
 897     /// Returns a copy of `v`.
 898     #[inline]
 899     fn to_vec(&self) -> Vec<T> where T: Clone {
 900         let mut vector = Vec::with_capacity(self.len());
 901         vector.push_all(self);
 902         vector
 903     }
 904
 905     /// Returns an iterator over all permutations of a vector.
 906     fn permutations(&self) -> Permutations<T> where T: Clone {
 907         Permutations{
 908             swaps: ElementSwaps::new(self.len()),
 909             v: self.to_vec(),
 910         }
 911     }
 912
 913     fn clone_from_slice(&mut self, src: &[T]) -> uint where T: Clone {
 914         core_slice::SliceExt::clone_from_slice(self, src)
 915     }
 916
 917     #[inline]
 918     fn sort(&mut self) where T: Ord {
 919         self.sort_by(|a, b| a.cmp(b))
 920     }
 921
 922     fn binary_search(&self, x: &T) -> Result<uint, uint> where T: Ord {
 923         core_slice::SliceExt::binary_search(self, x)
 924     }
 925
 926     fn next_permutation(&mut self) -> bool where T: Ord {
 927         core_slice::SliceExt::next_permutation(self)
 928     }
 929
 930     fn prev_permutation(&mut self) -> bool where T: Ord {
 931         core_slice::SliceExt::prev_permutation(self)
 932     }
 933
 934     fn position_elem(&self, t: &T) -> Option<uint> where T: PartialEq {
 935         core_slice::SliceExt::position_elem(self, t)
 936     }
 937
 938     fn rposition_elem(&self, t: &T) -> Option<uint> where T: PartialEq {
 939         core_slice::SliceExt::rposition_elem(self, t)
 940     }
 941
 942     fn contains(&self, x: &T) -> bool where T: PartialEq {
 943         core_slice::SliceExt::contains(self, x)
 944     }
 945
 946     fn starts_with(&self, needle: &[T]) -> bool where T: PartialEq {
 947         core_slice::SliceExt::starts_with(self, needle)
 948     }
 949
 950     fn ends_with(&self, needle: &[T]) -> bool where T: PartialEq {
 951         core_slice::SliceExt::ends_with(self, needle)
 952     }
 953
 954     fn into_vec(mut self: Box<Self>) -> Vec<T> {
 955         unsafe {
 956             let xs = Vec::from_raw_parts(self.as_mut_ptr(), self.len(), self.len());
 957             mem::forget(self);
 958             xs
 959         }
 960     }
 961 }
 962
 963 ////////////////////////////////////////////////////////////////////////////////
 964 // Extension traits for slices over specific kinds of data
 965 ////////////////////////////////////////////////////////////////////////////////
 966 #[unstable = "U should be an associated type"]
 967 /// An extension trait for concatenating slices
 968 pub trait SliceConcatExt<T: ?Sized, U> {
 969     /// Flattens a slice of `T` into a single value `U`.
 970     #[stable]
 971     fn concat(&self) -> U;
 972
 973     /// Flattens a slice of `T` into a single value `U`, placing a
 974     /// given separator between each.
 975     #[stable]
 976     fn connect(&self, sep: &T) -> U;
 977 }
 978
 979 impl<T: Clone, V: AsSlice<T>> SliceConcatExt<T, Vec<T>> for [V] {
 980     fn concat(&self) -> Vec<T> {
 981         let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
 982         let mut result = Vec::with_capacity(size);
 983         for v in self.iter() {
 984             result.push_all(v.as_slice())
 985         }
 986         result
 987     }
 988
 989     fn connect(&self, sep: &T) -> Vec<T> {
 990         let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
 991         let mut result = Vec::with_capacity(size + self.len());
 992         let mut first = true;
 993         for v in self.iter() {
 994             if first { first = false } else { result.push(sep.clone()) }
 995             result.push_all(v.as_slice())
 996         }
 997         result
 998     }
 999 }
1000
1001 /// An iterator that yields the element swaps needed to produce
1002 /// a sequence of all possible permutations for an indexed sequence of
1003 /// elements. Each permutation is only a single swap apart.
1004 ///
1005 /// The Steinhaus-Johnson-Trotter algorithm is used.
1006 ///
1007 /// Generates even and odd permutations alternately.
1008 ///
1009 /// The last generated swap is always (0, 1), and it returns the
1010 /// sequence to its initial order.
1011 #[unstable]
1012 #[derive(Clone)]
1013 pub struct ElementSwaps {
1014     sdir: Vec<SizeDirection>,
1015     /// If `true`, emit the last swap that returns the sequence to initial
1016     /// state.
1017     emit_reset: bool,
1018     swaps_made : uint,
1019 }
1020
1021 impl ElementSwaps {
1022     /// Creates an `ElementSwaps` iterator for a sequence of `length` elements.
1023     #[unstable]
1024     pub fn new(length: uint) -> ElementSwaps {
1025         // Initialize `sdir` with a direction that position should move in
1026         // (all negative at the beginning) and the `size` of the
1027         // element (equal to the original index).
1028         ElementSwaps{
1029             emit_reset: true,
1030             sdir: range(0, length).map(|i| SizeDirection{ size: i, dir: Neg }).collect(),
1031             swaps_made: 0
1032         }
1033     }
1034 }
1035
1036 ////////////////////////////////////////////////////////////////////////////////
1037 // Standard trait implementations for slices
1038 ////////////////////////////////////////////////////////////////////////////////
1039
1040 #[unstable = "trait is unstable"]
1041 impl<T> BorrowFrom<Vec<T>> for [T] {
1042     fn borrow_from(owned: &Vec<T>) -> &[T] { &owned[] }
1043 }
1044
1045 #[unstable = "trait is unstable"]
1046 impl<T> BorrowFromMut<Vec<T>> for [T] {
1047     fn borrow_from_mut(owned: &mut Vec<T>) -> &mut [T] { &mut owned[] }
1048 }
1049
1050 #[unstable = "trait is unstable"]
1051 impl<T: Clone> ToOwned<Vec<T>> for [T] {
1052     fn to_owned(&self) -> Vec<T> { self.to_vec() }
1053 }
1054
1055 ////////////////////////////////////////////////////////////////////////////////
1056 // Iterators
1057 ////////////////////////////////////////////////////////////////////////////////
1058
1059 #[derive(Copy, Clone)]
1060 enum Direction { Pos, Neg }
1061
1062 /// An `Index` and `Direction` together.
1063 #[derive(Copy, Clone)]
1064 struct SizeDirection {
1065     size: uint,
1066     dir: Direction,
1067 }
1068
1069 #[stable]
1070 impl Iterator for ElementSwaps {
1071     type Item = (uint, uint);
1072
1073     #[inline]
1074     fn next(&mut self) -> Option<(uint, uint)> {
1075         fn new_pos(i: uint, s: Direction) -> uint {
1076             i + match s { Pos => 1, Neg => -1 }
1077         }
1078
1079         // Find the index of the largest mobile element:
1080         // The direction should point into the vector, and the
1081         // swap should be with a smaller `size` element.
1082         let max = self.sdir.iter().map(|&x| x).enumerate()
1083                            .filter(|&(i, sd)|
1084                                 new_pos(i, sd.dir) < self.sdir.len() &&
1085                                 self.sdir[new_pos(i, sd.dir)].size < sd.size)
1086                            .max_by(|&(_, sd)| sd.size);
1087         match max {
1088             Some((i, sd)) => {
1089                 let j = new_pos(i, sd.dir);
1090                 self.sdir.swap(i, j);
1091
1092                 // Swap the direction of each larger SizeDirection
1093                 for x in self.sdir.iter_mut() {
1094                     if x.size > sd.size {
1095                         x.dir = match x.dir { Pos => Neg, Neg => Pos };
1096                     }
1097                 }
1098                 self.swaps_made += 1;
1099                 Some((i, j))
1100             },
1101             None => if self.emit_reset {
1102                 self.emit_reset = false;
1103                 if self.sdir.len() > 1 {
1104                     // The last swap
1105                     self.swaps_made += 1;
1106                     Some((0, 1))
1107                 } else {
1108                     // Vector is of the form [] or [x], and the only permutation is itself
1109                     self.swaps_made += 1;
1110                     Some((0,0))
1111                 }
1112             } else { None }
1113         }
1114     }
1115
1116     #[inline]
1117     fn size_hint(&self) -> (uint, Option<uint>) {
1118         // For a vector of size n, there are exactly n! permutations.
1119         let n = range(2, self.sdir.len() + 1).product();
1120         (n - self.swaps_made, Some(n - self.swaps_made))
1121     }
1122 }
1123
1124 /// An iterator that uses `ElementSwaps` to iterate through
1125 /// all possible permutations of a vector.
1126 ///
1127 /// The first iteration yields a clone of the vector as it is,
1128 /// then each successive element is the vector with one
1129 /// swap applied.
1130 ///
1131 /// Generates even and odd permutations alternately.
1132 #[unstable]
1133 pub struct Permutations<T> {
1134     swaps: ElementSwaps,
1135     v: Vec<T>,
1136 }
1137
1138 #[unstable = "trait is unstable"]
1139 impl<T: Clone> Iterator for Permutations<T> {
1140     type Item = Vec<T>;
1141
1142     #[inline]
1143     fn next(&mut self) -> Option<Vec<T>> {
1144         match self.swaps.next() {
1145             None => None,
1146             Some((0,0)) => Some(self.v.clone()),
1147             Some((a, b)) => {
1148                 let elt = self.v.clone();
1149                 self.v.swap(a, b);
1150                 Some(elt)
1151             }
1152         }
1153     }
1154
1155     #[inline]
1156     fn size_hint(&self) -> (uint, Option<uint>) {
1157         self.swaps.size_hint()
1158     }
1159 }
1160
1161 ////////////////////////////////////////////////////////////////////////////////
1162 // Sorting
1163 ////////////////////////////////////////////////////////////////////////////////
1164
1165 fn insertion_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering {
1166     let len = v.len() as int;
1167     let buf_v = v.as_mut_ptr();
1168
1169     // 1 <= i < len;
1170     for i in range(1, len) {
1171         // j satisfies: 0 <= j <= i;
1172         let mut j = i;
1173         unsafe {
1174             // `i` is in bounds.
1175             let read_ptr = buf_v.offset(i) as *const T;
1176
1177             // find where to insert, we need to do strict <,
1178             // rather than <=, to maintain stability.
1179
1180             // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
1181             while j > 0 &&
1182                     compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less {
1183                 j -= 1;
1184             }
1185
1186             // shift everything to the right, to make space to
1187             // insert this value.
1188
1189             // j + 1 could be `len` (for the last `i`), but in
1190             // that case, `i == j` so we don't copy. The
1191             // `.offset(j)` is always in bounds.
1192
1193             if i != j {
1194                 let tmp = ptr::read(read_ptr);
1195                 ptr::copy_memory(buf_v.offset(j + 1),
1196                                  &*buf_v.offset(j),
1197                                  (i - j) as uint);
1198                 ptr::copy_nonoverlapping_memory(buf_v.offset(j),
1199                                                 &tmp,
1200                                                 1);
1201                 mem::forget(tmp);
1202             }
1203         }
1204     }
1205 }
1206
1207 fn merge_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering {
1208     // warning: this wildly uses unsafe.
1209     static BASE_INSERTION: uint = 32;
1210     static LARGE_INSERTION: uint = 16;
1211
1212     // FIXME #12092: smaller insertion runs seems to make sorting
1213     // vectors of large elements a little faster on some platforms,
1214     // but hasn't been tested/tuned extensively
1215     let insertion = if size_of::<T>() <= 16 {
1216         BASE_INSERTION
1217     } else {
1218         LARGE_INSERTION
1219     };
1220
1221     let len = v.len();
1222
1223     // short vectors get sorted in-place via insertion sort to avoid allocations
1224     if len <= insertion {
1225         insertion_sort(v, compare);
1226         return;
1227     }
1228
1229     // allocate some memory to use as scratch memory, we keep the
1230     // length 0 so we can keep shallow copies of the contents of `v`
1231     // without risking the dtors running on an object twice if
1232     // `compare` panics.
1233     let mut working_space = Vec::with_capacity(2 * len);
1234     // these both are buffers of length `len`.
1235     let mut buf_dat = working_space.as_mut_ptr();
1236     let mut buf_tmp = unsafe {buf_dat.offset(len as int)};
1237
1238     // length `len`.
1239     let buf_v = v.as_ptr();
1240
1241     // step 1. sort short runs with insertion sort. This takes the
1242     // values from `v` and sorts them into `buf_dat`, leaving that
1243     // with sorted runs of length INSERTION.
1244
1245     // We could hardcode the sorting comparisons here, and we could
1246     // manipulate/step the pointers themselves, rather than repeatedly
1247     // .offset-ing.
1248     for start in range_step(0, len, insertion) {
1249         // start <= i < len;
1250         for i in range(start, cmp::min(start + insertion, len)) {
1251             // j satisfies: start <= j <= i;
1252             let mut j = i as int;
1253             unsafe {
1254                 // `i` is in bounds.
1255                 let read_ptr = buf_v.offset(i as int);
1256
1257                 // find where to insert, we need to do strict <,
1258                 // rather than <=, to maintain stability.
1259
1260                 // start <= j - 1 < len, so .offset(j - 1) is in
1261                 // bounds.
1262                 while j > start as int &&
1263                         compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less {
1264                     j -= 1;
1265                 }
1266
1267                 // shift everything to the right, to make space to
1268                 // insert this value.
1269
1270                 // j + 1 could be `len` (for the last `i`), but in
1271                 // that case, `i == j` so we don't copy. The
1272                 // `.offset(j)` is always in bounds.
1273                 ptr::copy_memory(buf_dat.offset(j + 1),
1274                                  &*buf_dat.offset(j),
1275                                  i - j as uint);
1276                 ptr::copy_nonoverlapping_memory(buf_dat.offset(j), read_ptr, 1);
1277             }
1278         }
1279     }
1280
1281     // step 2. merge the sorted runs.
1282     let mut width = insertion;
1283     while width < len {
1284         // merge the sorted runs of length `width` in `buf_dat` two at
1285         // a time, placing the result in `buf_tmp`.
1286
1287         // 0 <= start <= len.
1288         for start in range_step(0, len, 2 * width) {
1289             // manipulate pointers directly for speed (rather than
1290             // using a `for` loop with `range` and `.offset` inside
1291             // that loop).
1292             unsafe {
1293                 // the end of the first run & start of the
1294                 // second. Offset of `len` is defined, since this is
1295                 // precisely one byte past the end of the object.
1296                 let right_start = buf_dat.offset(cmp::min(start + width, len) as int);
1297                 // end of the second. Similar reasoning to the above re safety.
1298                 let right_end_idx = cmp::min(start + 2 * width, len);
1299                 let right_end = buf_dat.offset(right_end_idx as int);
1300
1301                 // the pointers to the elements under consideration
1302                 // from the two runs.
1303
1304                 // both of these are in bounds.
1305                 let mut left = buf_dat.offset(start as int);
1306                 let mut right = right_start;
1307
1308                 // where we're putting the results, it is a run of
1309                 // length `2*width`, so we step it once for each step
1310                 // of either `left` or `right`.  `buf_tmp` has length
1311                 // `len`, so these are in bounds.
1312                 let mut out = buf_tmp.offset(start as int);
1313                 let out_end = buf_tmp.offset(right_end_idx as int);
1314
1315                 while out < out_end {
1316                     // Either the left or the right run are exhausted,
1317                     // so just copy the remainder from the other run
1318                     // and move on; this gives a huge speed-up (order
1319                     // of 25%) for mostly sorted vectors (the best
1320                     // case).
1321                     if left == right_start {
1322                         // the number remaining in this run.
1323                         let elems = (right_end as uint - right as uint) / mem::size_of::<T>();
1324                         ptr::copy_nonoverlapping_memory(out, &*right, elems);
1325                         break;
1326                     } else if right == right_end {
1327                         let elems = (right_start as uint - left as uint) / mem::size_of::<T>();
1328                         ptr::copy_nonoverlapping_memory(out, &*left, elems);
1329                         break;
1330                     }
1331
1332                     // check which side is smaller, and that's the
1333                     // next element for the new run.
1334
1335                     // `left < right_start` and `right < right_end`,
1336                     // so these are valid.
1337                     let to_copy = if compare(&*left, &*right) == Greater {
1338                         step(&mut right)
1339                     } else {
1340                         step(&mut left)
1341                     };
1342                     ptr::copy_nonoverlapping_memory(out, &*to_copy, 1);
1343                     step(&mut out);
1344                 }
1345             }
1346         }
1347
1348         mem::swap(&mut buf_dat, &mut buf_tmp);
1349
1350         width *= 2;
1351     }
1352
1353     // write the result to `v` in one go, so that there are never two copies
1354     // of the same object in `v`.
1355     unsafe {
1356         ptr::copy_nonoverlapping_memory(v.as_mut_ptr(), &*buf_dat, len);
1357     }
1358
1359     // increment the pointer, returning the old pointer.
1360     #[inline(always)]
1361     unsafe fn step<T>(ptr: &mut *mut T) -> *mut T {
1362         let old = *ptr;
1363         *ptr = ptr.offset(1);
1364         old
1365     }
1366 }
1367
1368 #[cfg(test)]
1369 mod tests {
1370     use core::cmp::Ordering::{Greater, Less, Equal};
1371     use core::prelude::{Some, None, range, Clone};
1372     use core::prelude::{Iterator, IteratorExt};
1373     use core::prelude::{AsSlice};
1374     use core::prelude::{Ord, FullRange};
1375     use core::default::Default;
1376     use core::mem;
1377     use std::iter::RandomAccessIterator;
1378     use std::rand::{Rng, thread_rng};
1379     use std::rc::Rc;
1380     use string::ToString;
1381     use vec::Vec;
1382     use super::{ElementSwaps, SliceConcatExt, SliceExt};
1383
1384     fn square(n: uint) -> uint { n * n }
1385
1386     fn is_odd(n: &uint) -> bool { *n % 2u == 1u }
1387
1388     #[test]
1389     fn test_from_fn() {
1390         // Test on-stack from_fn.
1391         let mut v = range(0, 3).map(square).collect::<Vec<_>>();
1392         {
1393             let v = v.as_slice();
1394             assert_eq!(v.len(), 3u);
1395             assert_eq!(v[0], 0u);
1396             assert_eq!(v[1], 1u);
1397             assert_eq!(v[2], 4u);
1398         }
1399
1400         // Test on-heap from_fn.
1401         v = range(0, 5).map(square).collect::<Vec<_>>();
1402         {
1403             let v = v.as_slice();
1404             assert_eq!(v.len(), 5u);
1405             assert_eq!(v[0], 0u);
1406             assert_eq!(v[1], 1u);
1407             assert_eq!(v[2], 4u);
1408             assert_eq!(v[3], 9u);
1409             assert_eq!(v[4], 16u);
1410         }
1411     }
1412
1413     #[test]
1414     fn test_from_elem() {
1415         // Test on-stack from_elem.
1416         let mut v = vec![10u, 10u];
1417         {
1418             let v = v.as_slice();
1419             assert_eq!(v.len(), 2u);
1420             assert_eq!(v[0], 10u);
1421             assert_eq!(v[1], 10u);
1422         }
1423
1424         // Test on-heap from_elem.
1425         v = vec![20u, 20u, 20u, 20u, 20u, 20u];
1426         {
1427             let v = v.as_slice();
1428             assert_eq!(v[0], 20u);
1429             assert_eq!(v[1], 20u);
1430             assert_eq!(v[2], 20u);
1431             assert_eq!(v[3], 20u);
1432             assert_eq!(v[4], 20u);
1433             assert_eq!(v[5], 20u);
1434         }
1435     }
1436
1437     #[test]
1438     fn test_is_empty() {
1439         let xs: [int; 0] = [];
1440         assert!(xs.is_empty());
1441         assert!(![0i].is_empty());
1442     }
1443
1444     #[test]
1445     fn test_len_divzero() {
1446         type Z = [i8; 0];
1447         let v0 : &[Z] = &[];
1448         let v1 : &[Z] = &[[]];
1449         let v2 : &[Z] = &[[], []];
1450         assert_eq!(mem::size_of::<Z>(), 0);
1451         assert_eq!(v0.len(), 0);
1452         assert_eq!(v1.len(), 1);
1453         assert_eq!(v2.len(), 2);
1454     }
1455
1456     #[test]
1457     fn test_get() {
1458         let mut a = vec![11i];
1459         assert_eq!(a.as_slice().get(1), None);
1460         a = vec![11i, 12];
1461         assert_eq!(a.as_slice().get(1).unwrap(), &12);
1462         a = vec![11i, 12, 13];
1463         assert_eq!(a.as_slice().get(1).unwrap(), &12);
1464     }
1465
1466     #[test]
1467     fn test_first() {
1468         let mut a = vec![];
1469         assert_eq!(a.as_slice().first(), None);
1470         a = vec![11i];
1471         assert_eq!(a.as_slice().first().unwrap(), &11);
1472         a = vec![11i, 12];
1473         assert_eq!(a.as_slice().first().unwrap(), &11);
1474     }
1475
1476     #[test]
1477     fn test_first_mut() {
1478         let mut a = vec![];
1479         assert_eq!(a.first_mut(), None);
1480         a = vec![11i];
1481         assert_eq!(*a.first_mut().unwrap(), 11);
1482         a = vec![11i, 12];
1483         assert_eq!(*a.first_mut().unwrap(), 11);
1484     }
1485
1486     #[test]
1487     fn test_tail() {
1488         let mut a = vec![11i];
1489         let b: &[int] = &[];
1490         assert_eq!(a.tail(), b);
1491         a = vec![11i, 12];
1492         let b: &[int] = &[12];
1493         assert_eq!(a.tail(), b);
1494     }
1495
1496     #[test]
1497     fn test_tail_mut() {
1498         let mut a = vec![11i];
1499         let b: &mut [int] = &mut [];
1500         assert!(a.tail_mut() == b);
1501         a = vec![11i, 12];
1502         let b: &mut [int] = &mut [12];
1503         assert!(a.tail_mut() == b);
1504     }
1505
1506     #[test]
1507     #[should_fail]
1508     fn test_tail_empty() {
1509         let a: Vec<int> = vec![];
1510         a.tail();
1511     }
1512
1513     #[test]
1514     #[should_fail]
1515     fn test_tail_mut_empty() {
1516         let mut a: Vec<int> = vec![];
1517         a.tail_mut();
1518     }
1519
1520     #[test]
1521     fn test_init() {
1522         let mut a = vec![11i];
1523         let b: &[int] = &[];
1524         assert_eq!(a.init(), b);
1525         a = vec![11i, 12];
1526         let b: &[int] = &[11];
1527         assert_eq!(a.init(), b);
1528     }
1529
1530     #[test]
1531     fn test_init_mut() {
1532         let mut a = vec![11i];
1533         let b: &mut [int] = &mut [];
1534         assert!(a.init_mut() == b);
1535         a = vec![11i, 12];
1536         let b: &mut [int] = &mut [11];
1537         assert!(a.init_mut() == b);
1538     }
1539
1540     #[test]
1541     #[should_fail]
1542     fn test_init_empty() {
1543         let a: Vec<int> = vec![];
1544         a.init();
1545     }
1546
1547     #[test]
1548     #[should_fail]
1549     fn test_init_mut_empty() {
1550         let mut a: Vec<int> = vec![];
1551         a.init_mut();
1552     }
1553
1554     #[test]
1555     fn test_last() {
1556         let mut a = vec![];
1557         assert_eq!(a.as_slice().last(), None);
1558         a = vec![11i];
1559         assert_eq!(a.as_slice().last().unwrap(), &11);
1560         a = vec![11i, 12];
1561         assert_eq!(a.as_slice().last().unwrap(), &12);
1562     }
1563
1564     #[test]
1565     fn test_last_mut() {
1566         let mut a = vec![];
1567         assert_eq!(a.last_mut(), None);
1568         a = vec![11i];
1569         assert_eq!(*a.last_mut().unwrap(), 11);
1570         a = vec![11i, 12];
1571         assert_eq!(*a.last_mut().unwrap(), 12);
1572     }
1573
1574     #[test]
1575     fn test_slice() {
1576         // Test fixed length vector.
1577         let vec_fixed = [1i, 2, 3, 4];
1578         let v_a = vec_fixed[1u..vec_fixed.len()].to_vec();
1579         assert_eq!(v_a.len(), 3u);
1580         let v_a = v_a.as_slice();
1581         assert_eq!(v_a[0], 2);
1582         assert_eq!(v_a[1], 3);
1583         assert_eq!(v_a[2], 4);
1584
1585         // Test on stack.
1586         let vec_stack: &[_] = &[1i, 2, 3];
1587         let v_b = vec_stack[1u..3u].to_vec();
1588         assert_eq!(v_b.len(), 2u);
1589         let v_b = v_b.as_slice();
1590         assert_eq!(v_b[0], 2);
1591         assert_eq!(v_b[1], 3);
1592
1593         // Test `Box<[T]>`
1594         let vec_unique = vec![1i, 2, 3, 4, 5, 6];
1595         let v_d = vec_unique[1u..6u].to_vec();
1596         assert_eq!(v_d.len(), 5u);
1597         let v_d = v_d.as_slice();
1598         assert_eq!(v_d[0], 2);
1599         assert_eq!(v_d[1], 3);
1600         assert_eq!(v_d[2], 4);
1601         assert_eq!(v_d[3], 5);
1602         assert_eq!(v_d[4], 6);
1603     }
1604
1605     #[test]
1606     fn test_slice_from() {
1607         let vec: &[int] = &[1, 2, 3, 4];
1608         assert_eq!(&vec[], vec);
1609         let b: &[int] = &[3, 4];
1610         assert_eq!(&vec[2..], b);
1611         let b: &[int] = &[];
1612         assert_eq!(&vec[4..], b);
1613     }
1614
1615     #[test]
1616     fn test_slice_to() {
1617         let vec: &[int] = &[1, 2, 3, 4];
1618         assert_eq!(&vec[..4], vec);
1619         let b: &[int] = &[1, 2];
1620         assert_eq!(&vec[..2], b);
1621         let b: &[int] = &[];
1622         assert_eq!(&vec[..0], b);
1623     }
1624
1625
1626     #[test]
1627     fn test_pop() {
1628         let mut v = vec![5i];
1629         let e = v.pop();
1630         assert_eq!(v.len(), 0);
1631         assert_eq!(e, Some(5));
1632         let f = v.pop();
1633         assert_eq!(f, None);
1634         let g = v.pop();
1635         assert_eq!(g, None);
1636     }
1637
1638     #[test]
1639     fn test_swap_remove() {
1640         let mut v = vec![1i, 2, 3, 4, 5];
1641         let mut e = v.swap_remove(0);
1642         assert_eq!(e, 1);
1643         assert_eq!(v, vec![5i, 2, 3, 4]);
1644         e = v.swap_remove(3);
1645         assert_eq!(e, 4);
1646         assert_eq!(v, vec![5i, 2, 3]);
1647     }
1648
1649     #[test]
1650     #[should_fail]
1651     fn test_swap_remove_fail() {
1652         let mut v = vec![1i];
1653         let _ = v.swap_remove(0);
1654         let _ = v.swap_remove(0);
1655     }
1656
1657     #[test]
1658     fn test_swap_remove_noncopyable() {
1659         // Tests that we don't accidentally run destructors twice.
1660         let mut v = Vec::new();
1661         v.push(box 0u8);
1662         v.push(box 0u8);
1663         v.push(box 0u8);
1664         let mut _e = v.swap_remove(0);
1665         assert_eq!(v.len(), 2);
1666         _e = v.swap_remove(1);
1667         assert_eq!(v.len(), 1);
1668         _e = v.swap_remove(0);
1669         assert_eq!(v.len(), 0);
1670     }
1671
1672     #[test]
1673     fn test_push() {
1674         // Test on-stack push().
1675         let mut v = vec![];
1676         v.push(1i);
1677         assert_eq!(v.len(), 1u);
1678         assert_eq!(v.as_slice()[0], 1);
1679
1680         // Test on-heap push().
1681         v.push(2i);
1682         assert_eq!(v.len(), 2u);
1683         assert_eq!(v.as_slice()[0], 1);
1684         assert_eq!(v.as_slice()[1], 2);
1685     }
1686
1687     #[test]
1688     fn test_truncate() {
1689         let mut v = vec![box 6i,box 5,box 4];
1690         v.truncate(1);
1691         let v = v.as_slice();
1692         assert_eq!(v.len(), 1);
1693         assert_eq!(*(v[0]), 6);
1694         // If the unsafe block didn't drop things properly, we blow up here.
1695     }
1696
1697     #[test]
1698     fn test_clear() {
1699         let mut v = vec![box 6i,box 5,box 4];
1700         v.clear();
1701         assert_eq!(v.len(), 0);
1702         // If the unsafe block didn't drop things properly, we blow up here.
1703     }
1704
1705     #[test]
1706     fn test_dedup() {
1707         fn case(a: Vec<uint>, b: Vec<uint>) {
1708             let mut v = a;
1709             v.dedup();
1710             assert_eq!(v, b);
1711         }
1712         case(vec![], vec![]);
1713         case(vec![1u], vec![1]);
1714         case(vec![1u,1], vec![1]);
1715         case(vec![1u,2,3], vec![1,2,3]);
1716         case(vec![1u,1,2,3], vec![1,2,3]);
1717         case(vec![1u,2,2,3], vec![1,2,3]);
1718         case(vec![1u,2,3,3], vec![1,2,3]);
1719         case(vec![1u,1,2,2,2,3,3], vec![1,2,3]);
1720     }
1721
1722     #[test]
1723     fn test_dedup_unique() {
1724         let mut v0 = vec![box 1i, box 1, box 2, box 3];
1725         v0.dedup();
1726         let mut v1 = vec![box 1i, box 2, box 2, box 3];
1727         v1.dedup();
1728         let mut v2 = vec![box 1i, box 2, box 3, box 3];
1729         v2.dedup();
1730         /*
1731          * If the boxed pointers were leaked or otherwise misused, valgrind
1732          * and/or rt should raise errors.
1733          */
1734     }
1735
1736     #[test]
1737     fn test_dedup_shared() {
1738         let mut v0 = vec![box 1i, box 1, box 2, box 3];
1739         v0.dedup();
1740         let mut v1 = vec![box 1i, box 2, box 2, box 3];
1741         v1.dedup();
1742         let mut v2 = vec![box 1i, box 2, box 3, box 3];
1743         v2.dedup();
1744         /*
1745          * If the pointers were leaked or otherwise misused, valgrind and/or
1746          * rt should raise errors.
1747          */
1748     }
1749
1750     #[test]
1751     fn test_retain() {
1752         let mut v = vec![1u, 2, 3, 4, 5];
1753         v.retain(is_odd);
1754         assert_eq!(v, vec![1u, 3, 5]);
1755     }
1756
1757     #[test]
1758     fn test_element_swaps() {
1759         let mut v = [1i, 2, 3];
1760         for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
1761             v.swap(a, b);
1762             match i {
1763                 0 => assert!(v == [1, 3, 2]),
1764                 1 => assert!(v == [3, 1, 2]),
1765                 2 => assert!(v == [3, 2, 1]),
1766                 3 => assert!(v == [2, 3, 1]),
1767                 4 => assert!(v == [2, 1, 3]),
1768                 5 => assert!(v == [1, 2, 3]),
1769                 _ => panic!(),
1770             }
1771         }
1772     }
1773
1774     #[test]
1775     fn test_permutations() {
1776         {
1777             let v: [int; 0] = [];
1778             let mut it = v.permutations();
1779             let (min_size, max_opt) = it.size_hint();
1780             assert_eq!(min_size, 1);
1781             assert_eq!(max_opt.unwrap(), 1);
1782             assert_eq!(it.next(), Some(v.as_slice().to_vec()));
1783             assert_eq!(it.next(), None);
1784         }
1785         {
1786             let v = ["Hello".to_string()];
1787             let mut it = v.permutations();
1788             let (min_size, max_opt) = it.size_hint();
1789             assert_eq!(min_size, 1);
1790             assert_eq!(max_opt.unwrap(), 1);
1791             assert_eq!(it.next(), Some(v.as_slice().to_vec()));
1792             assert_eq!(it.next(), None);
1793         }
1794         {
1795             let v = [1i, 2, 3];
1796             let mut it = v.permutations();
1797             let (min_size, max_opt) = it.size_hint();
1798             assert_eq!(min_size, 3*2);
1799             assert_eq!(max_opt.unwrap(), 3*2);
1800             assert_eq!(it.next(), Some(vec![1,2,3]));
1801             assert_eq!(it.next(), Some(vec![1,3,2]));
1802             assert_eq!(it.next(), Some(vec![3,1,2]));
1803             let (min_size, max_opt) = it.size_hint();
1804             assert_eq!(min_size, 3);
1805             assert_eq!(max_opt.unwrap(), 3);
1806             assert_eq!(it.next(), Some(vec![3,2,1]));
1807             assert_eq!(it.next(), Some(vec![2,3,1]));
1808             assert_eq!(it.next(), Some(vec![2,1,3]));
1809             assert_eq!(it.next(), None);
1810         }
1811         {
1812             // check that we have N! permutations
1813             let v = ['A', 'B', 'C', 'D', 'E', 'F'];
1814             let mut amt = 0;
1815             let mut it = v.permutations();
1816             let (min_size, max_opt) = it.size_hint();
1817             for _perm in it {
1818                 amt += 1;
1819             }
1820             assert_eq!(amt, it.swaps.swaps_made);
1821             assert_eq!(amt, min_size);
1822             assert_eq!(amt, 2 * 3 * 4 * 5 * 6);
1823             assert_eq!(amt, max_opt.unwrap());
1824         }
1825     }
1826
1827     #[test]
1828     fn test_lexicographic_permutations() {
1829         let v : &mut[int] = &mut[1i, 2, 3, 4, 5];
1830         assert!(v.prev_permutation() == false);
1831         assert!(v.next_permutation());
1832         let b: &mut[int] = &mut[1, 2, 3, 5, 4];
1833         assert!(v == b);
1834         assert!(v.prev_permutation());
1835         let b: &mut[int] = &mut[1, 2, 3, 4, 5];
1836         assert!(v == b);
1837         assert!(v.next_permutation());
1838         assert!(v.next_permutation());
1839         let b: &mut[int] = &mut[1, 2, 4, 3, 5];
1840         assert!(v == b);
1841         assert!(v.next_permutation());
1842         let b: &mut[int] = &mut[1, 2, 4, 5, 3];
1843         assert!(v == b);
1844
1845         let v : &mut[int] = &mut[1i, 0, 0, 0];
1846         assert!(v.next_permutation() == false);
1847         assert!(v.prev_permutation());
1848         let b: &mut[int] = &mut[0, 1, 0, 0];
1849         assert!(v == b);
1850         assert!(v.prev_permutation());
1851         let b: &mut[int] = &mut[0, 0, 1, 0];
1852         assert!(v == b);
1853         assert!(v.prev_permutation());
1854         let b: &mut[int] = &mut[0, 0, 0, 1];
1855         assert!(v == b);
1856         assert!(v.prev_permutation() == false);
1857     }
1858
1859     #[test]
1860     fn test_lexicographic_permutations_empty_and_short() {
1861         let empty : &mut[int] = &mut[];
1862         assert!(empty.next_permutation() == false);
1863         let b: &mut[int] = &mut[];
1864         assert!(empty == b);
1865         assert!(empty.prev_permutation() == false);
1866         assert!(empty == b);
1867
1868         let one_elem : &mut[int] = &mut[4i];
1869         assert!(one_elem.prev_permutation() == false);
1870         let b: &mut[int] = &mut[4];
1871         assert!(one_elem == b);
1872         assert!(one_elem.next_permutation() == false);
1873         assert!(one_elem == b);
1874
1875         let two_elem : &mut[int] = &mut[1i, 2];
1876         assert!(two_elem.prev_permutation() == false);
1877         let b : &mut[int] = &mut[1, 2];
1878         let c : &mut[int] = &mut[2, 1];
1879         assert!(two_elem == b);
1880         assert!(two_elem.next_permutation());
1881         assert!(two_elem == c);
1882         assert!(two_elem.next_permutation() == false);
1883         assert!(two_elem == c);
1884         assert!(two_elem.prev_permutation());
1885         assert!(two_elem == b);
1886         assert!(two_elem.prev_permutation() == false);
1887         assert!(two_elem == b);
1888     }
1889
1890     #[test]
1891     fn test_position_elem() {
1892         assert!([].position_elem(&1i).is_none());
1893
1894         let v1 = vec![1i, 2, 3, 3, 2, 5];
1895         assert_eq!(v1.as_slice().position_elem(&1), Some(0u));
1896         assert_eq!(v1.as_slice().position_elem(&2), Some(1u));
1897         assert_eq!(v1.as_slice().position_elem(&5), Some(5u));
1898         assert!(v1.as_slice().position_elem(&4).is_none());
1899     }
1900
1901     #[test]
1902     fn test_binary_search() {
1903         assert_eq!([1i,2,3,4,5].binary_search(&5).ok(), Some(4));
1904         assert_eq!([1i,2,3,4,5].binary_search(&4).ok(), Some(3));
1905         assert_eq!([1i,2,3,4,5].binary_search(&3).ok(), Some(2));
1906         assert_eq!([1i,2,3,4,5].binary_search(&2).ok(), Some(1));
1907         assert_eq!([1i,2,3,4,5].binary_search(&1).ok(), Some(0));
1908
1909         assert_eq!([2i,4,6,8,10].binary_search(&1).ok(), None);
1910         assert_eq!([2i,4,6,8,10].binary_search(&5).ok(), None);
1911         assert_eq!([2i,4,6,8,10].binary_search(&4).ok(), Some(1));
1912         assert_eq!([2i,4,6,8,10].binary_search(&10).ok(), Some(4));
1913
1914         assert_eq!([2i,4,6,8].binary_search(&1).ok(), None);
1915         assert_eq!([2i,4,6,8].binary_search(&5).ok(), None);
1916         assert_eq!([2i,4,6,8].binary_search(&4).ok(), Some(1));
1917         assert_eq!([2i,4,6,8].binary_search(&8).ok(), Some(3));
1918
1919         assert_eq!([2i,4,6].binary_search(&1).ok(), None);
1920         assert_eq!([2i,4,6].binary_search(&5).ok(), None);
1921         assert_eq!([2i,4,6].binary_search(&4).ok(), Some(1));
1922         assert_eq!([2i,4,6].binary_search(&6).ok(), Some(2));
1923
1924         assert_eq!([2i,4].binary_search(&1).ok(), None);
1925         assert_eq!([2i,4].binary_search(&5).ok(), None);
1926         assert_eq!([2i,4].binary_search(&2).ok(), Some(0));
1927         assert_eq!([2i,4].binary_search(&4).ok(), Some(1));
1928
1929         assert_eq!([2i].binary_search(&1).ok(), None);
1930         assert_eq!([2i].binary_search(&5).ok(), None);
1931         assert_eq!([2i].binary_search(&2).ok(), Some(0));
1932
1933         assert_eq!([].binary_search(&1i).ok(), None);
1934         assert_eq!([].binary_search(&5i).ok(), None);
1935
1936         assert!([1i,1,1,1,1].binary_search(&1).ok() != None);
1937         assert!([1i,1,1,1,2].binary_search(&1).ok() != None);
1938         assert!([1i,1,1,2,2].binary_search(&1).ok() != None);
1939         assert!([1i,1,2,2,2].binary_search(&1).ok() != None);
1940         assert_eq!([1i,2,2,2,2].binary_search(&1).ok(), Some(0));
1941
1942         assert_eq!([1i,2,3,4,5].binary_search(&6).ok(), None);
1943         assert_eq!([1i,2,3,4,5].binary_search(&0).ok(), None);
1944     }
1945
1946     #[test]
1947     fn test_reverse() {
1948         let mut v: Vec<int> = vec![10i, 20];
1949         assert_eq!(v[0], 10);
1950         assert_eq!(v[1], 20);
1951         v.reverse();
1952         assert_eq!(v[0], 20);
1953         assert_eq!(v[1], 10);
1954
1955         let mut v3: Vec<int> = vec![];
1956         v3.reverse();
1957         assert!(v3.is_empty());
1958     }
1959
1960     #[test]
1961     fn test_sort() {
1962         for len in range(4u, 25) {
1963             for _ in range(0i, 100) {
1964                 let mut v = thread_rng().gen_iter::<uint>().take(len)
1965                                       .collect::<Vec<uint>>();
1966                 let mut v1 = v.clone();
1967
1968                 v.sort();
1969                 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
1970
1971                 v1.sort_by(|a, b| a.cmp(b));
1972                 assert!(v1.as_slice().windows(2).all(|w| w[0] <= w[1]));
1973
1974                 v1.sort_by(|a, b| b.cmp(a));
1975                 assert!(v1.as_slice().windows(2).all(|w| w[0] >= w[1]));
1976             }
1977         }
1978
1979         // shouldn't panic
1980         let mut v: [uint; 0] = [];
1981         v.sort();
1982
1983         let mut v = [0xDEADBEEFu];
1984         v.sort();
1985         assert!(v == [0xDEADBEEF]);
1986     }
1987
1988     #[test]
1989     fn test_sort_stability() {
1990         for len in range(4i, 25) {
1991             for _ in range(0u, 10) {
1992                 let mut counts = [0i; 10];
1993
1994                 // create a vector like [(6, 1), (5, 1), (6, 2), ...],
1995                 // where the first item of each tuple is random, but
1996                 // the second item represents which occurrence of that
1997                 // number this element is, i.e. the second elements
1998                 // will occur in sorted order.
1999                 let mut v = range(0, len).map(|_| {
2000                         let n = thread_rng().gen::<uint>() % 10;
2001                         counts[n] += 1;
2002                         (n, counts[n])
2003                     }).collect::<Vec<(uint, int)>>();
2004
2005                 // only sort on the first element, so an unstable sort
2006                 // may mix up the counts.
2007                 v.sort_by(|&(a,_), &(b,_)| a.cmp(&b));
2008
2009                 // this comparison includes the count (the second item
2010                 // of the tuple), so elements with equal first items
2011                 // will need to be ordered with increasing
2012                 // counts... i.e. exactly asserting that this sort is
2013                 // stable.
2014                 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
2015             }
2016         }
2017     }
2018
2019     #[test]
2020     fn test_concat() {
2021         let v: [Vec<int>; 0] = [];
2022         let c: Vec<int> = v.concat();
2023         assert_eq!(c, []);
2024         let d: Vec<int> = [vec![1i], vec![2i,3i]].concat();
2025         assert_eq!(d, vec![1i, 2, 3]);
2026
2027         let v: [&[int]; 2] = [&[1], &[2, 3]];
2028         assert_eq!(v.connect(&0), vec![1i, 0, 2, 3]);
2029         let v: [&[int]; 3] = [&[1i], &[2], &[3]];
2030         assert_eq!(v.connect(&0), vec![1i, 0, 2, 0, 3]);
2031     }
2032
2033     #[test]
2034     fn test_connect() {
2035         let v: [Vec<int>; 0] = [];
2036         assert_eq!(v.connect(&0), vec![]);
2037         assert_eq!([vec![1i], vec![2i, 3]].connect(&0), vec![1, 0, 2, 3]);
2038         assert_eq!([vec![1i], vec![2i], vec![3i]].connect(&0), vec![1, 0, 2, 0, 3]);
2039
2040         let v: [&[int]; 2] = [&[1], &[2, 3]];
2041         assert_eq!(v.connect(&0), vec![1, 0, 2, 3]);
2042         let v: [&[int]; 3] = [&[1], &[2], &[3]];
2043         assert_eq!(v.connect(&0), vec![1, 0, 2, 0, 3]);
2044     }
2045
2046     #[test]
2047     fn test_insert() {
2048         let mut a = vec![1i, 2, 4];
2049         a.insert(2, 3);
2050         assert_eq!(a, vec![1, 2, 3, 4]);
2051
2052         let mut a = vec![1i, 2, 3];
2053         a.insert(0, 0);
2054         assert_eq!(a, vec![0, 1, 2, 3]);
2055
2056         let mut a = vec![1i, 2, 3];
2057         a.insert(3, 4);
2058         assert_eq!(a, vec![1, 2, 3, 4]);
2059
2060         let mut a = vec![];
2061         a.insert(0, 1i);
2062         assert_eq!(a, vec![1]);
2063     }
2064
2065     #[test]
2066     #[should_fail]
2067     fn test_insert_oob() {
2068         let mut a = vec![1i, 2, 3];
2069         a.insert(4, 5);
2070     }
2071
2072     #[test]
2073     fn test_remove() {
2074         let mut a = vec![1i,2,3,4];
2075
2076         assert_eq!(a.remove(2), 3);
2077         assert_eq!(a, vec![1i,2,4]);
2078
2079         assert_eq!(a.remove(2), 4);
2080         assert_eq!(a, vec![1i,2]);
2081
2082         assert_eq!(a.remove(0), 1);
2083         assert_eq!(a, vec![2i]);
2084
2085         assert_eq!(a.remove(0), 2);
2086         assert_eq!(a, vec![]);
2087     }
2088
2089     #[test]
2090     #[should_fail]
2091     fn test_remove_fail() {
2092         let mut a = vec![1i];
2093         let _ = a.remove(0);
2094         let _ = a.remove(0);
2095     }
2096
2097     #[test]
2098     fn test_capacity() {
2099         let mut v = vec![0u64];
2100         v.reserve_exact(10u);
2101         assert!(v.capacity() >= 11u);
2102         let mut v = vec![0u32];
2103         v.reserve_exact(10u);
2104         assert!(v.capacity() >= 11u);
2105     }
2106
2107     #[test]
2108     fn test_slice_2() {
2109         let v = vec![1i, 2, 3, 4, 5];
2110         let v = v.slice(1u, 3u);
2111         assert_eq!(v.len(), 2u);
2112         assert_eq!(v[0], 2);
2113         assert_eq!(v[1], 3);
2114     }
2115
2116     #[test]
2117     #[should_fail]
2118     fn test_permute_fail() {
2119         let v = [(box 0i, Rc::new(0i)), (box 0i, Rc::new(0i)),
2120                  (box 0i, Rc::new(0i)), (box 0i, Rc::new(0i))];
2121         let mut i = 0u;
2122         for _ in v.permutations() {
2123             if i == 2 {
2124                 panic!()
2125             }
2126             i += 1;
2127         }
2128     }
2129
2130     #[test]
2131     fn test_total_ord() {
2132         let c: &[int] = &[1, 2, 3];
2133         [1, 2, 3, 4][].cmp(c) == Greater;
2134         let c: &[int] = &[1, 2, 3, 4];
2135         [1, 2, 3][].cmp(c) == Less;
2136         let c: &[int] = &[1, 2, 3, 6];
2137         [1, 2, 3, 4][].cmp(c) == Equal;
2138         let c: &[int] = &[1, 2, 3, 4, 5, 6];
2139         [1, 2, 3, 4, 5, 5, 5, 5][].cmp(c) == Less;
2140         let c: &[int] = &[1, 2, 3, 4];
2141         [2, 2][].cmp(c) == Greater;
2142     }
2143
2144     #[test]
2145     fn test_iterator() {
2146         let xs = [1i, 2, 5, 10, 11];
2147         let mut it = xs.iter();
2148         assert_eq!(it.size_hint(), (5, Some(5)));
2149         assert_eq!(it.next().unwrap(), &1);
2150         assert_eq!(it.size_hint(), (4, Some(4)));
2151         assert_eq!(it.next().unwrap(), &2);
2152         assert_eq!(it.size_hint(), (3, Some(3)));
2153         assert_eq!(it.next().unwrap(), &5);
2154         assert_eq!(it.size_hint(), (2, Some(2)));
2155         assert_eq!(it.next().unwrap(), &10);
2156         assert_eq!(it.size_hint(), (1, Some(1)));
2157         assert_eq!(it.next().unwrap(), &11);
2158         assert_eq!(it.size_hint(), (0, Some(0)));
2159         assert!(it.next().is_none());
2160     }
2161
2162     #[test]
2163     fn test_random_access_iterator() {
2164         let xs = [1i, 2, 5, 10, 11];
2165         let mut it = xs.iter();
2166
2167         assert_eq!(it.indexable(), 5);
2168         assert_eq!(it.idx(0).unwrap(), &1);
2169         assert_eq!(it.idx(2).unwrap(), &5);
2170         assert_eq!(it.idx(4).unwrap(), &11);
2171         assert!(it.idx(5).is_none());
2172
2173         assert_eq!(it.next().unwrap(), &1);
2174         assert_eq!(it.indexable(), 4);
2175         assert_eq!(it.idx(0).unwrap(), &2);
2176         assert_eq!(it.idx(3).unwrap(), &11);
2177         assert!(it.idx(4).is_none());
2178
2179         assert_eq!(it.next().unwrap(), &2);
2180         assert_eq!(it.indexable(), 3);
2181         assert_eq!(it.idx(1).unwrap(), &10);
2182         assert!(it.idx(3).is_none());
2183
2184         assert_eq!(it.next().unwrap(), &5);
2185         assert_eq!(it.indexable(), 2);
2186         assert_eq!(it.idx(1).unwrap(), &11);
2187
2188         assert_eq!(it.next().unwrap(), &10);
2189         assert_eq!(it.indexable(), 1);
2190         assert_eq!(it.idx(0).unwrap(), &11);
2191         assert!(it.idx(1).is_none());
2192
2193         assert_eq!(it.next().unwrap(), &11);
2194         assert_eq!(it.indexable(), 0);
2195         assert!(it.idx(0).is_none());
2196
2197         assert!(it.next().is_none());
2198     }
2199
2200     #[test]
2201     fn test_iter_size_hints() {
2202         let mut xs = [1i, 2, 5, 10, 11];
2203         assert_eq!(xs.iter().size_hint(), (5, Some(5)));
2204         assert_eq!(xs.iter_mut().size_hint(), (5, Some(5)));
2205     }
2206
2207     #[test]
2208     fn test_iter_clone() {
2209         let xs = [1i, 2, 5];
2210         let mut it = xs.iter();
2211         it.next();
2212         let mut jt = it.clone();
2213         assert_eq!(it.next(), jt.next());
2214         assert_eq!(it.next(), jt.next());
2215         assert_eq!(it.next(), jt.next());
2216     }
2217
2218     #[test]
2219     fn test_mut_iterator() {
2220         let mut xs = [1i, 2, 3, 4, 5];
2221         for x in xs.iter_mut() {
2222             *x += 1;
2223         }
2224         assert!(xs == [2, 3, 4, 5, 6])
2225     }
2226
2227     #[test]
2228     fn test_rev_iterator() {
2229
2230         let xs = [1i, 2, 5, 10, 11];
2231         let ys = [11, 10, 5, 2, 1];
2232         let mut i = 0;
2233         for &x in xs.iter().rev() {
2234             assert_eq!(x, ys[i]);
2235             i += 1;
2236         }
2237         assert_eq!(i, 5);
2238     }
2239
2240     #[test]
2241     fn test_mut_rev_iterator() {
2242         let mut xs = [1u, 2, 3, 4, 5];
2243         for (i,x) in xs.iter_mut().rev().enumerate() {
2244             *x += i;
2245         }
2246         assert!(xs == [5, 5, 5, 5, 5])
2247     }
2248
2249     #[test]
2250     fn test_move_iterator() {
2251         let xs = vec![1u,2,3,4,5];
2252         assert_eq!(xs.into_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
2253     }
2254
2255     #[test]
2256     fn test_move_rev_iterator() {
2257         let xs = vec![1u,2,3,4,5];
2258         assert_eq!(xs.into_iter().rev().fold(0, |a: uint, b: uint| 10*a + b), 54321);
2259     }
2260
2261     #[test]
2262     fn test_splitator() {
2263         let xs = &[1i,2,3,4,5];
2264
2265         let splits: &[&[int]] = &[&[1], &[3], &[5]];
2266         assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2267                    splits);
2268         let splits: &[&[int]] = &[&[], &[2,3,4,5]];
2269         assert_eq!(xs.split(|x| *x == 1).collect::<Vec<&[int]>>(),
2270                    splits);
2271         let splits: &[&[int]] = &[&[1,2,3,4], &[]];
2272         assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[int]>>(),
2273                    splits);
2274         let splits: &[&[int]] = &[&[1,2,3,4,5]];
2275         assert_eq!(xs.split(|x| *x == 10).collect::<Vec<&[int]>>(),
2276                    splits);
2277         let splits: &[&[int]] = &[&[], &[], &[], &[], &[], &[]];
2278         assert_eq!(xs.split(|_| true).collect::<Vec<&[int]>>(),
2279                    splits);
2280
2281         let xs: &[int] = &[];
2282         let splits: &[&[int]] = &[&[]];
2283         assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[int]>>(), splits);
2284     }
2285
2286     #[test]
2287     fn test_splitnator() {
2288         let xs = &[1i,2,3,4,5];
2289
2290         let splits: &[&[int]] = &[&[1,2,3,4,5]];
2291         assert_eq!(xs.splitn(0, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2292                    splits);
2293         let splits: &[&[int]] = &[&[1], &[3,4,5]];
2294         assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2295                    splits);
2296         let splits: &[&[int]] = &[&[], &[], &[], &[4,5]];
2297         assert_eq!(xs.splitn(3, |_| true).collect::<Vec<&[int]>>(),
2298                    splits);
2299
2300         let xs: &[int] = &[];
2301         let splits: &[&[int]] = &[&[]];
2302         assert_eq!(xs.splitn(1, |x| *x == 5).collect::<Vec<&[int]>>(), splits);
2303     }
2304
2305     #[test]
2306     fn test_splitnator_mut() {
2307         let xs = &mut [1i,2,3,4,5];
2308
2309         let splits: &[&mut [int]] = &[&mut [1,2,3,4,5]];
2310         assert_eq!(xs.splitn_mut(0, |x| *x % 2 == 0).collect::<Vec<&mut [int]>>(),
2311                    splits);
2312         let splits: &[&mut [int]] = &[&mut [1], &mut [3,4,5]];
2313         assert_eq!(xs.splitn_mut(1, |x| *x % 2 == 0).collect::<Vec<&mut [int]>>(),
2314                    splits);
2315         let splits: &[&mut [int]] = &[&mut [], &mut [], &mut [], &mut [4,5]];
2316         assert_eq!(xs.splitn_mut(3, |_| true).collect::<Vec<&mut [int]>>(),
2317                    splits);
2318
2319         let xs: &mut [int] = &mut [];
2320         let splits: &[&mut [int]] = &[&mut []];
2321         assert_eq!(xs.splitn_mut(1, |x| *x == 5).collect::<Vec<&mut [int]>>(),
2322                    splits);
2323     }
2324
2325     #[test]
2326     fn test_rsplitator() {
2327         let xs = &[1i,2,3,4,5];
2328
2329         let splits: &[&[int]] = &[&[5], &[3], &[1]];
2330         assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<&[int]>>(),
2331                    splits);
2332         let splits: &[&[int]] = &[&[2,3,4,5], &[]];
2333         assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<&[int]>>(),
2334                    splits);
2335         let splits: &[&[int]] = &[&[], &[1,2,3,4]];
2336         assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[int]>>(),
2337                    splits);
2338         let splits: &[&[int]] = &[&[1,2,3,4,5]];
2339         assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<&[int]>>(),
2340                    splits);
2341
2342         let xs: &[int] = &[];
2343         let splits: &[&[int]] = &[&[]];
2344         assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[int]>>(), splits);
2345     }
2346
2347     #[test]
2348     fn test_rsplitnator() {
2349         let xs = &[1,2,3,4,5];
2350
2351         let splits: &[&[int]] = &[&[1,2,3,4,5]];
2352         assert_eq!(xs.rsplitn(0, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2353                    splits);
2354         let splits: &[&[int]] = &[&[5], &[1,2,3]];
2355         assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2356                    splits);
2357         let splits: &[&[int]] = &[&[], &[], &[], &[1,2]];
2358         assert_eq!(xs.rsplitn(3, |_| true).collect::<Vec<&[int]>>(),
2359                    splits);
2360
2361         let xs: &[int] = &[];
2362         let splits: &[&[int]] = &[&[]];
2363         assert_eq!(xs.rsplitn(1, |x| *x == 5).collect::<Vec<&[int]>>(), splits);
2364     }
2365
2366     #[test]
2367     fn test_windowsator() {
2368         let v = &[1i,2,3,4];
2369
2370         let wins: &[&[int]] = &[&[1,2], &[2,3], &[3,4]];
2371         assert_eq!(v.windows(2).collect::<Vec<&[int]>>(), wins);
2372         let wins: &[&[int]] = &[&[1i,2,3], &[2,3,4]];
2373         assert_eq!(v.windows(3).collect::<Vec<&[int]>>(), wins);
2374         assert!(v.windows(6).next().is_none());
2375     }
2376
2377     #[test]
2378     #[should_fail]
2379     fn test_windowsator_0() {
2380         let v = &[1i,2,3,4];
2381         let _it = v.windows(0);
2382     }
2383
2384     #[test]
2385     fn test_chunksator() {
2386         let v = &[1i,2,3,4,5];
2387
2388         let chunks: &[&[int]] = &[&[1i,2], &[3,4], &[5]];
2389         assert_eq!(v.chunks(2).collect::<Vec<&[int]>>(), chunks);
2390         let chunks: &[&[int]] = &[&[1i,2,3], &[4,5]];
2391         assert_eq!(v.chunks(3).collect::<Vec<&[int]>>(), chunks);
2392         let chunks: &[&[int]] = &[&[1i,2,3,4,5]];
2393         assert_eq!(v.chunks(6).collect::<Vec<&[int]>>(), chunks);
2394
2395         let chunks: &[&[int]] = &[&[5i], &[3,4], &[1,2]];
2396         assert_eq!(v.chunks(2).rev().collect::<Vec<&[int]>>(), chunks);
2397         let mut it = v.chunks(2);
2398         assert_eq!(it.indexable(), 3);
2399         let chunk: &[int] = &[1,2];
2400         assert_eq!(it.idx(0).unwrap(), chunk);
2401         let chunk: &[int] = &[3,4];
2402         assert_eq!(it.idx(1).unwrap(), chunk);
2403         let chunk: &[int] = &[5];
2404         assert_eq!(it.idx(2).unwrap(), chunk);
2405         assert_eq!(it.idx(3), None);
2406     }
2407
2408     #[test]
2409     #[should_fail]
2410     fn test_chunksator_0() {
2411         let v = &[1i,2,3,4];
2412         let _it = v.chunks(0);
2413     }
2414
2415     #[test]
2416     fn test_move_from() {
2417         let mut a = [1i,2,3,4,5];
2418         let b = vec![6i,7,8];
2419         assert_eq!(a.move_from(b, 0, 3), 3);
2420         assert!(a == [6i,7,8,4,5]);
2421         let mut a = [7i,2,8,1];
2422         let b = vec![3i,1,4,1,5,9];
2423         assert_eq!(a.move_from(b, 0, 6), 4);
2424         assert!(a == [3i,1,4,1]);
2425         let mut a = [1i,2,3,4];
2426         let b = vec![5i,6,7,8,9,0];
2427         assert_eq!(a.move_from(b, 2, 3), 1);
2428         assert!(a == [7i,2,3,4]);
2429         let mut a = [1i,2,3,4,5];
2430         let b = vec![5i,6,7,8,9,0];
2431         assert_eq!(a.slice_mut(2, 4).move_from(b,1,6), 2);
2432         assert!(a == [1i,2,6,7,5]);
2433     }
2434
2435     #[test]
2436     fn test_reverse_part() {
2437         let mut values = [1i,2,3,4,5];
2438         values.slice_mut(1, 4).reverse();
2439         assert!(values == [1,4,3,2,5]);
2440     }
2441
2442     #[test]
2443     fn test_show() {
2444         macro_rules! test_show_vec {
2445             ($x:expr, $x_str:expr) => ({
2446                 let (x, x_str) = ($x, $x_str);
2447                 assert_eq!(format!("{:?}", x), x_str);
2448                 assert_eq!(format!("{:?}", x.as_slice()), x_str);
2449             })
2450         }
2451         let empty: Vec<int> = vec![];
2452         test_show_vec!(empty, "[]");
2453         test_show_vec!(vec![1i], "[1i]");
2454         test_show_vec!(vec![1i, 2, 3], "[1i, 2i, 3i]");
2455         test_show_vec!(vec![vec![], vec![1u], vec![1u, 1u]],
2456                        "[[], [1u], [1u, 1u]]");
2457
2458         let empty_mut: &mut [int] = &mut[];
2459         test_show_vec!(empty_mut, "[]");
2460         let v: &mut[int] = &mut[1];
2461         test_show_vec!(v, "[1i]");
2462         let v: &mut[int] = &mut[1, 2, 3];
2463         test_show_vec!(v, "[1i, 2i, 3i]");
2464         let v: &mut [&mut[uint]] = &mut[&mut[], &mut[1u], &mut[1u, 1u]];
2465         test_show_vec!(v, "[[], [1u], [1u, 1u]]");
2466     }
2467
2468     #[test]
2469     fn test_vec_default() {
2470         macro_rules! t {
2471             ($ty:ty) => {{
2472                 let v: $ty = Default::default();
2473                 assert!(v.is_empty());
2474             }}
2475         }
2476
2477         t!(&[int]);
2478         t!(Vec<int>);
2479     }
2480
2481     #[test]
2482     fn test_bytes_set_memory() {
2483         use slice::bytes::MutableByteVector;
2484         let mut values = [1u8,2,3,4,5];
2485         values.slice_mut(0, 5).set_memory(0xAB);
2486         assert!(values == [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
2487         values.slice_mut(2, 4).set_memory(0xFF);
2488         assert!(values == [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
2489     }
2490
2491     #[test]
2492     #[should_fail]
2493     fn test_overflow_does_not_cause_segfault() {
2494         let mut v = vec![];
2495         v.reserve_exact(-1);
2496         v.push(1i);
2497         v.push(2);
2498     }
2499
2500     #[test]
2501     #[should_fail]
2502     fn test_overflow_does_not_cause_segfault_managed() {
2503         let mut v = vec![Rc::new(1i)];
2504         v.reserve_exact(-1);
2505         v.push(Rc::new(2i));
2506     }
2507
2508     #[test]
2509     fn test_mut_split_at() {
2510         let mut values = [1u8,2,3,4,5];
2511         {
2512             let (left, right) = values.split_at_mut(2);
2513             {
2514                 let left: &[_] = left;
2515                 assert!(left[..left.len()] == [1, 2][]);
2516             }
2517             for p in left.iter_mut() {
2518                 *p += 1;
2519             }
2520
2521             {
2522                 let right: &[_] = right;
2523                 assert!(right[..right.len()] == [3, 4, 5][]);
2524             }
2525             for p in right.iter_mut() {
2526                 *p += 2;
2527             }
2528         }
2529
2530         assert!(values == [2, 3, 5, 6, 7]);
2531     }
2532
2533     #[derive(Clone, PartialEq)]
2534     struct Foo;
2535
2536     #[test]
2537     fn test_iter_zero_sized() {
2538         let mut v = vec![Foo, Foo, Foo];
2539         assert_eq!(v.len(), 3);
2540         let mut cnt = 0u;
2541
2542         for f in v.iter() {
2543             assert!(*f == Foo);
2544             cnt += 1;
2545         }
2546         assert_eq!(cnt, 3);
2547
2548         for f in v[1..3].iter() {
2549             assert!(*f == Foo);
2550             cnt += 1;
2551         }
2552         assert_eq!(cnt, 5);
2553
2554         for f in v.iter_mut() {
2555             assert!(*f == Foo);
2556             cnt += 1;
2557         }
2558         assert_eq!(cnt, 8);
2559
2560         for f in v.into_iter() {
2561             assert!(f == Foo);
2562             cnt += 1;
2563         }
2564         assert_eq!(cnt, 11);
2565
2566         let xs: [Foo; 3] = [Foo, Foo, Foo];
2567         cnt = 0;
2568         for f in xs.iter() {
2569             assert!(*f == Foo);
2570             cnt += 1;
2571         }
2572         assert!(cnt == 3);
2573     }
2574
2575     #[test]
2576     fn test_shrink_to_fit() {
2577         let mut xs = vec![0, 1, 2, 3];
2578         for i in range(4i, 100) {
2579             xs.push(i)
2580         }
2581         assert_eq!(xs.capacity(), 128);
2582         xs.shrink_to_fit();
2583         assert_eq!(xs.capacity(), 100);
2584         assert_eq!(xs, range(0i, 100i).collect::<Vec<_>>());
2585     }
2586
2587     #[test]
2588     fn test_starts_with() {
2589         assert!(b"foobar".starts_with(b"foo"));
2590         assert!(!b"foobar".starts_with(b"oob"));
2591         assert!(!b"foobar".starts_with(b"bar"));
2592         assert!(!b"foo".starts_with(b"foobar"));
2593         assert!(!b"bar".starts_with(b"foobar"));
2594         assert!(b"foobar".starts_with(b"foobar"));
2595         let empty: &[u8] = &[];
2596         assert!(empty.starts_with(empty));
2597         assert!(!empty.starts_with(b"foo"));
2598         assert!(b"foobar".starts_with(empty));
2599     }
2600
2601     #[test]
2602     fn test_ends_with() {
2603         assert!(b"foobar".ends_with(b"bar"));
2604         assert!(!b"foobar".ends_with(b"oba"));
2605         assert!(!b"foobar".ends_with(b"foo"));
2606         assert!(!b"foo".ends_with(b"foobar"));
2607         assert!(!b"bar".ends_with(b"foobar"));
2608         assert!(b"foobar".ends_with(b"foobar"));
2609         let empty: &[u8] = &[];
2610         assert!(empty.ends_with(empty));
2611         assert!(!empty.ends_with(b"foo"));
2612         assert!(b"foobar".ends_with(empty));
2613     }
2614
2615     #[test]
2616     fn test_mut_splitator() {
2617         let mut xs = [0i,1,0,2,3,0,0,4,5,0];
2618         assert_eq!(xs.split_mut(|x| *x == 0).count(), 6);
2619         for slice in xs.split_mut(|x| *x == 0) {
2620             slice.reverse();
2621         }
2622         assert!(xs == [0,1,0,3,2,0,0,5,4,0]);
2623
2624         let mut xs = [0i,1,0,2,3,0,0,4,5,0,6,7];
2625         for slice in xs.split_mut(|x| *x == 0).take(5) {
2626             slice.reverse();
2627         }
2628         assert!(xs == [0,1,0,3,2,0,0,5,4,0,6,7]);
2629     }
2630
2631     #[test]
2632     fn test_mut_splitator_rev() {
2633         let mut xs = [1i,2,0,3,4,0,0,5,6,0];
2634         for slice in xs.split_mut(|x| *x == 0).rev().take(4) {
2635             slice.reverse();
2636         }
2637         assert!(xs == [1,2,0,4,3,0,0,6,5,0]);
2638     }
2639
2640     #[test]
2641     fn test_get_mut() {
2642         let mut v = [0i,1,2];
2643         assert_eq!(v.get_mut(3), None);
2644         v.get_mut(1).map(|e| *e = 7);
2645         assert_eq!(v[1], 7);
2646         let mut x = 2;
2647         assert_eq!(v.get_mut(2), Some(&mut x));
2648     }
2649
2650     #[test]
2651     fn test_mut_chunks() {
2652         let mut v = [0u8, 1, 2, 3, 4, 5, 6];
2653         for (i, chunk) in v.chunks_mut(3).enumerate() {
2654             for x in chunk.iter_mut() {
2655                 *x = i as u8;
2656             }
2657         }
2658         let result = [0u8, 0, 0, 1, 1, 1, 2];
2659         assert!(v == result);
2660     }
2661
2662     #[test]
2663     fn test_mut_chunks_rev() {
2664         let mut v = [0u8, 1, 2, 3, 4, 5, 6];
2665         for (i, chunk) in v.chunks_mut(3).rev().enumerate() {
2666             for x in chunk.iter_mut() {
2667                 *x = i as u8;
2668             }
2669         }
2670         let result = [2u8, 2, 2, 1, 1, 1, 0];
2671         assert!(v == result);
2672     }
2673
2674     #[test]
2675     #[should_fail]
2676     fn test_mut_chunks_0() {
2677         let mut v = [1i, 2, 3, 4];
2678         let _it = v.chunks_mut(0);
2679     }
2680
2681     #[test]
2682     fn test_mut_last() {
2683         let mut x = [1i, 2, 3, 4, 5];
2684         let h = x.last_mut();
2685         assert_eq!(*h.unwrap(), 5);
2686
2687         let y: &mut [int] = &mut [];
2688         assert!(y.last_mut().is_none());
2689     }
2690
2691     #[test]
2692     fn test_to_vec() {
2693         let xs = box [1u, 2, 3];
2694         let ys = xs.to_vec();
2695         assert_eq!(ys, [1u, 2, 3]);
2696     }
2697 }
2698
2699 #[cfg(test)]
2700 mod bench {
2701     use prelude::*;
2702     use core::mem;
2703     use core::ptr;
2704     use core::iter::repeat;
2705     use std::rand::{weak_rng, Rng};
2706     use test::{Bencher, black_box};
2707
2708     #[bench]
2709     fn iterator(b: &mut Bencher) {
2710         // peculiar numbers to stop LLVM from optimising the summation
2711         // out.
2712         let v = range(0u, 100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect::<Vec<_>>();
2713
2714         b.iter(|| {
2715             let mut sum = 0;
2716             for x in v.iter() {
2717                 sum += *x;
2718             }
2719             // sum == 11806, to stop dead code elimination.
2720             if sum == 0 {panic!()}
2721         })
2722     }
2723
2724     #[bench]
2725     fn mut_iterator(b: &mut Bencher) {
2726         let mut v = repeat(0i).take(100).collect::<Vec<_>>();
2727
2728         b.iter(|| {
2729             let mut i = 0i;
2730             for x in v.iter_mut() {
2731                 *x = i;
2732                 i += 1;
2733             }
2734         })
2735     }
2736
2737     #[bench]
2738     fn concat(b: &mut Bencher) {
2739         let xss: Vec<Vec<uint>> =
2740             range(0, 100u).map(|i| range(0, i).collect()).collect();
2741         b.iter(|| {
2742             xss.as_slice().concat();
2743         });
2744     }
2745
2746     #[bench]
2747     fn connect(b: &mut Bencher) {
2748         let xss: Vec<Vec<uint>> =
2749             range(0, 100u).map(|i| range(0, i).collect()).collect();
2750         b.iter(|| {
2751             xss.as_slice().connect(&0)
2752         });
2753     }
2754
2755     #[bench]
2756     fn push(b: &mut Bencher) {
2757         let mut vec: Vec<uint> = vec![];
2758         b.iter(|| {
2759             vec.push(0);
2760             black_box(&vec);
2761         });
2762     }
2763
2764     #[bench]
2765     fn starts_with_same_vector(b: &mut Bencher) {
2766         let vec: Vec<uint> = range(0, 100).collect();
2767         b.iter(|| {
2768             vec.as_slice().starts_with(vec.as_slice())
2769         })
2770     }
2771
2772     #[bench]
2773     fn starts_with_single_element(b: &mut Bencher) {
2774         let vec: Vec<uint> = vec![0];
2775         b.iter(|| {
2776             vec.as_slice().starts_with(vec.as_slice())
2777         })
2778     }
2779
2780     #[bench]
2781     fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
2782         let vec: Vec<uint> = range(0, 100).collect();
2783         let mut match_vec: Vec<uint> = range(0, 99).collect();
2784         match_vec.push(0);
2785         b.iter(|| {
2786             vec.as_slice().starts_with(match_vec.as_slice())
2787         })
2788     }
2789
2790     #[bench]
2791     fn ends_with_same_vector(b: &mut Bencher) {
2792         let vec: Vec<uint> = range(0, 100).collect();
2793         b.iter(|| {
2794             vec.as_slice().ends_with(vec.as_slice())
2795         })
2796     }
2797
2798     #[bench]
2799     fn ends_with_single_element(b: &mut Bencher) {
2800         let vec: Vec<uint> = vec![0];
2801         b.iter(|| {
2802             vec.as_slice().ends_with(vec.as_slice())
2803         })
2804     }
2805
2806     #[bench]
2807     fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
2808         let vec: Vec<uint> = range(0, 100).collect();
2809         let mut match_vec: Vec<uint> = range(0, 100).collect();
2810         match_vec.as_mut_slice()[0] = 200;
2811         b.iter(|| {
2812             vec.as_slice().starts_with(match_vec.as_slice())
2813         })
2814     }
2815
2816     #[bench]
2817     fn contains_last_element(b: &mut Bencher) {
2818         let vec: Vec<uint> = range(0, 100).collect();
2819         b.iter(|| {
2820             vec.contains(&99u)
2821         })
2822     }
2823
2824     #[bench]
2825     fn zero_1kb_from_elem(b: &mut Bencher) {
2826         b.iter(|| {
2827             repeat(0u8).take(1024).collect::<Vec<_>>()
2828         });
2829     }
2830
2831     #[bench]
2832     fn zero_1kb_set_memory(b: &mut Bencher) {
2833         b.iter(|| {
2834             let mut v: Vec<uint> = Vec::with_capacity(1024);
2835             unsafe {
2836                 let vp = v.as_mut_ptr();
2837                 ptr::set_memory(vp, 0, 1024);
2838                 v.set_len(1024);
2839             }
2840             v
2841         });
2842     }
2843
2844     #[bench]
2845     fn zero_1kb_loop_set(b: &mut Bencher) {
2846         b.iter(|| {
2847             let mut v: Vec<uint> = Vec::with_capacity(1024);
2848             unsafe {
2849                 v.set_len(1024);
2850             }
2851             for i in range(0u, 1024) {
2852                 v[i] = 0;
2853             }
2854         });
2855     }
2856
2857     #[bench]
2858     fn zero_1kb_mut_iter(b: &mut Bencher) {
2859         b.iter(|| {
2860             let mut v = Vec::with_capacity(1024);
2861             unsafe {
2862                 v.set_len(1024);
2863             }
2864             for x in v.iter_mut() {
2865                 *x = 0i;
2866             }
2867             v
2868         });
2869     }
2870
2871     #[bench]
2872     fn random_inserts(b: &mut Bencher) {
2873         let mut rng = weak_rng();
2874         b.iter(|| {
2875             let mut v = repeat((0u, 0u)).take(30).collect::<Vec<_>>();
2876             for _ in range(0u, 100) {
2877                 let l = v.len();
2878                 v.insert(rng.gen::<uint>() % (l + 1),
2879                          (1, 1));
2880             }
2881         })
2882     }
2883     #[bench]
2884     fn random_removes(b: &mut Bencher) {
2885         let mut rng = weak_rng();
2886         b.iter(|| {
2887             let mut v = repeat((0u, 0u)).take(130).collect::<Vec<_>>();
2888             for _ in range(0u, 100) {
2889                 let l = v.len();
2890                 v.remove(rng.gen::<uint>() % l);
2891             }
2892         })
2893     }
2894
2895     #[bench]
2896     fn sort_random_small(b: &mut Bencher) {
2897         let mut rng = weak_rng();
2898         b.iter(|| {
2899             let mut v = rng.gen_iter::<u64>().take(5).collect::<Vec<u64>>();
2900             v.as_mut_slice().sort();
2901         });
2902         b.bytes = 5 * mem::size_of::<u64>() as u64;
2903     }
2904
2905     #[bench]
2906     fn sort_random_medium(b: &mut Bencher) {
2907         let mut rng = weak_rng();
2908         b.iter(|| {
2909             let mut v = rng.gen_iter::<u64>().take(100).collect::<Vec<u64>>();
2910             v.as_mut_slice().sort();
2911         });
2912         b.bytes = 100 * mem::size_of::<u64>() as u64;
2913     }
2914
2915     #[bench]
2916     fn sort_random_large(b: &mut Bencher) {
2917         let mut rng = weak_rng();
2918         b.iter(|| {
2919             let mut v = rng.gen_iter::<u64>().take(10000).collect::<Vec<u64>>();
2920             v.as_mut_slice().sort();
2921         });
2922         b.bytes = 10000 * mem::size_of::<u64>() as u64;
2923     }
2924
2925     #[bench]
2926     fn sort_sorted(b: &mut Bencher) {
2927         let mut v = range(0u, 10000).collect::<Vec<_>>();
2928         b.iter(|| {
2929             v.sort();
2930         });
2931         b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
2932     }
2933
2934     type BigSortable = (u64,u64,u64,u64);
2935
2936     #[bench]
2937     fn sort_big_random_small(b: &mut Bencher) {
2938         let mut rng = weak_rng();
2939         b.iter(|| {
2940             let mut v = rng.gen_iter::<BigSortable>().take(5)
2941                            .collect::<Vec<BigSortable>>();
2942             v.sort();
2943         });
2944         b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
2945     }
2946
2947     #[bench]
2948     fn sort_big_random_medium(b: &mut Bencher) {
2949         let mut rng = weak_rng();
2950         b.iter(|| {
2951             let mut v = rng.gen_iter::<BigSortable>().take(100)
2952                            .collect::<Vec<BigSortable>>();
2953             v.sort();
2954         });
2955         b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
2956     }
2957
2958     #[bench]
2959     fn sort_big_random_large(b: &mut Bencher) {
2960         let mut rng = weak_rng();
2961         b.iter(|| {
2962             let mut v = rng.gen_iter::<BigSortable>().take(10000)
2963                            .collect::<Vec<BigSortable>>();
2964             v.sort();
2965         });
2966         b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
2967     }
2968
2969     #[bench]
2970     fn sort_big_sorted(b: &mut Bencher) {
2971         let mut v = range(0, 10000u).map(|i| (i, i, i, i)).collect::<Vec<_>>();
2972         b.iter(|| {
2973             v.sort();
2974         });
2975         b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
2976     }
2977 }