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