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.
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.
11 //! Utilities for slice manipulation
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.
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"];
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:
29 //! let x: &mut[int] = &mut [1i, 2, 3];
31 //! assert_eq!(x[0], 1);
32 //! assert_eq!(x[1], 7);
33 //! assert_eq!(x[2], 3);
36 //! Here are some of the things this module contains:
40 //! There are several structs that are useful for slices, such as `Iter`, which
41 //! represents iteration over a slice.
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
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)`:
55 //! #![feature(slicing_syntax)]
57 //! let numbers = [0i, 1i, 2i];
58 //! let last_numbers = &numbers[1..3];
59 //! // last_numbers is now &[1i, 2i]
63 //! ## Implementations of other traits
65 //! There are several implementations of common traits for slices. Some examples
69 //! * `Eq`, `Ord` - for immutable slices whose element type are `Eq` or `Ord`.
70 //! * `Hash` - for slices whose element type is `Hash`
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`.
79 //! let numbers = [0i, 1i, 2i];
80 //! for &x in numbers.iter() {
81 //! println!("{} is a number!", x);
85 //! * `.iter_mut()` returns an iterator that allows modifying each value.
86 //! * Further iterators exist that split, chunk or permute the slice.
88 #![doc(primitive = "slice")]
91 use alloc::boxed::Box;
92 use core::borrow::{BorrowFrom, BorrowFromMut, ToOwned};
93 use core::clone::Clone;
94 use core::cmp::Ordering::{self, Greater, Less};
95 use core::cmp::{self, Ord, PartialEq};
96 use core::iter::{Iterator, IteratorExt};
97 use core::iter::{range, range_step, MultiplicativeIterator};
98 use core::marker::Sized;
99 use core::mem::size_of;
101 use core::ops::{FnMut, FullRange};
102 use core::option::Option::{self, Some, None};
103 use core::ptr::PtrExt;
105 use core::result::Result;
106 use core::slice as core_slice;
107 use self::Direction::*;
111 pub use core::slice::{Chunks, AsSlice, Windows};
112 pub use core::slice::{Iter, IterMut};
113 pub use core::slice::{IntSliceExt, SplitMut, ChunksMut, Split};
114 pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut};
115 pub use core::slice::{bytes, mut_ref_slice, ref_slice};
116 pub use core::slice::{from_raw_buf, from_raw_mut_buf};
118 ////////////////////////////////////////////////////////////////////////////////
119 // Basic slice extension methods
120 ////////////////////////////////////////////////////////////////////////////////
122 /// Allocating extension methods for slices.
128 /// Sorts the slice, in place, using `compare` to compare
131 /// This sort is `O(n log n)` worst-case and stable, but allocates
132 /// approximately `2 * n`, where `n` is the length of `self`.
137 /// let mut v = [5i, 4, 1, 3, 2];
138 /// v.sort_by(|a, b| a.cmp(b));
139 /// assert!(v == [1, 2, 3, 4, 5]);
141 /// // reverse sorting
142 /// v.sort_by(|a, b| b.cmp(a));
143 /// assert!(v == [5, 4, 3, 2, 1]);
146 fn sort_by<F>(&mut self, compare: F) where F: FnMut(&Self::Item, &Self::Item) -> Ordering;
148 /// Consumes `src` and moves as many elements as it can into `self`
149 /// from the range [start,end).
151 /// Returns the number of elements copied (the shorter of `self.len()`
152 /// and `end - start`).
156 /// * src - A mutable vector of `T`
157 /// * start - The index into `src` to start copying from
158 /// * end - The index into `src` to stop copying from
163 /// let mut a = [1i, 2, 3, 4, 5];
164 /// let b = vec![6i, 7, 8];
165 /// let num_moved = a.move_from(b, 0, 3);
166 /// assert_eq!(num_moved, 3);
167 /// assert!(a == [6i, 7, 8, 4, 5]);
169 #[unstable = "uncertain about this API approach"]
170 fn move_from(&mut self, src: Vec<Self::Item>, start: uint, end: uint) -> uint;
172 /// Returns a subslice spanning the interval [`start`, `end`).
174 /// Panics when the end of the new slice lies beyond the end of the
175 /// original slice (i.e. when `end > self.len()`) or when `start > end`.
177 /// Slicing with `start` equal to `end` yields an empty slice.
178 #[unstable = "will be replaced by slice syntax"]
179 fn slice(&self, start: uint, end: uint) -> &[Self::Item];
181 /// Returns a subslice from `start` to the end of the slice.
183 /// Panics when `start` is strictly greater than the length of the original slice.
185 /// Slicing from `self.len()` yields an empty slice.
186 #[unstable = "will be replaced by slice syntax"]
187 fn slice_from(&self, start: uint) -> &[Self::Item];
189 /// Returns a subslice from the start of the slice to `end`.
191 /// Panics when `end` is strictly greater than the length of the original slice.
193 /// Slicing to `0` yields an empty slice.
194 #[unstable = "will be replaced by slice syntax"]
195 fn slice_to(&self, end: uint) -> &[Self::Item];
197 /// Divides one slice into two at an index.
199 /// The first will contain all indices from `[0, mid)` (excluding
200 /// the index `mid` itself) and the second will contain all
201 /// indices from `[mid, len)` (excluding the index `len` itself).
203 /// Panics if `mid > len`.
205 fn split_at(&self, mid: uint) -> (&[Self::Item], &[Self::Item]);
207 /// Returns an iterator over the slice
209 fn iter(&self) -> Iter<Self::Item>;
211 /// Returns an iterator over subslices separated by elements that match
212 /// `pred`. The matched element is not contained in the subslices.
214 fn split<F>(&self, pred: F) -> Split<Self::Item, F>
215 where F: FnMut(&Self::Item) -> bool;
217 /// Returns an iterator over subslices separated by elements that match
218 /// `pred`, limited to splitting at most `n` times. The matched element is
219 /// not contained in the subslices.
221 fn splitn<F>(&self, n: uint, pred: F) -> SplitN<Self::Item, F>
222 where F: FnMut(&Self::Item) -> bool;
224 /// Returns an iterator over subslices separated by elements that match
225 /// `pred` limited to splitting at most `n` times. This starts at the end of
226 /// the slice and works backwards. The matched element is not contained in
229 fn rsplitn<F>(&self, n: uint, pred: F) -> RSplitN<Self::Item, F>
230 where F: FnMut(&Self::Item) -> bool;
232 /// Returns an iterator over all contiguous windows of length
233 /// `size`. The windows overlap. If the slice is shorter than
234 /// `size`, the iterator returns no values.
238 /// Panics if `size` is 0.
242 /// Print the adjacent pairs of a slice (i.e. `[1,2]`, `[2,3]`,
246 /// let v = &[1i, 2, 3, 4];
247 /// for win in v.windows(2) {
248 /// println!("{:?}", win);
252 fn windows(&self, size: uint) -> Windows<Self::Item>;
254 /// Returns an iterator over `size` elements of the slice at a
255 /// time. The chunks do not overlap. If `size` does not divide the
256 /// length of the slice, then the last chunk will not have length
261 /// Panics if `size` is 0.
265 /// Print the slice two elements at a time (i.e. `[1,2]`,
269 /// let v = &[1i, 2, 3, 4, 5];
270 /// for win in v.chunks(2) {
271 /// println!("{:?}", win);
275 fn chunks(&self, size: uint) -> Chunks<Self::Item>;
277 /// Returns the element of a slice at the given index, or `None` if the
278 /// index is out of bounds.
280 fn get(&self, index: uint) -> Option<&Self::Item>;
282 /// Returns the first element of a slice, or `None` if it is empty.
284 fn first(&self) -> Option<&Self::Item>;
286 /// Returns all but the first element of a slice.
287 #[unstable = "likely to be renamed"]
288 fn tail(&self) -> &[Self::Item];
290 /// Returns all but the last element of a slice.
291 #[unstable = "likely to be renamed"]
292 fn init(&self) -> &[Self::Item];
294 /// Returns the last element of a slice, or `None` if it is empty.
296 fn last(&self) -> Option<&Self::Item>;
298 /// Returns a pointer to the element at the given index, without doing
301 unsafe fn get_unchecked(&self, index: uint) -> &Self::Item;
303 /// Returns an unsafe pointer to the slice's buffer
305 /// The caller must ensure that the slice outlives the pointer this
306 /// function returns, or else it will end up pointing to garbage.
308 /// Modifying the slice may cause its buffer to be reallocated, which
309 /// would also make any pointers to it invalid.
311 fn as_ptr(&self) -> *const Self::Item;
313 /// Binary search a sorted slice with a comparator function.
315 /// The comparator function should implement an order consistent
316 /// with the sort order of the underlying slice, returning an
317 /// order code that indicates whether its argument is `Less`,
318 /// `Equal` or `Greater` the desired target.
320 /// If a matching value is found then returns `Ok`, containing
321 /// the index for the matched element; if no match is found then
322 /// `Err` is returned, containing the index where a matching
323 /// element could be inserted while maintaining sorted order.
327 /// Looks up a series of four elements. The first is found, with a
328 /// uniquely determined position; the second and third are not
329 /// found; the fourth could match any position in `[1,4]`.
332 /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
333 /// let s = s.as_slice();
336 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
338 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
340 /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
342 /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
343 /// assert!(match r { Ok(1...4) => true, _ => false, });
346 fn binary_search_by<F>(&self, f: F) -> Result<uint, uint> where
347 F: FnMut(&Self::Item) -> Ordering;
349 /// Return the number of elements in the slice
354 /// let a = [1i, 2, 3];
355 /// assert_eq!(a.len(), 3);
358 fn len(&self) -> uint;
360 /// Returns true if the slice has a length of 0
365 /// let a = [1i, 2, 3];
366 /// assert!(!a.is_empty());
370 fn is_empty(&self) -> bool { self.len() == 0 }
371 /// Returns a mutable reference to the element at the given index,
372 /// or `None` if the index is out of bounds
374 fn get_mut(&mut self, index: uint) -> Option<&mut Self::Item>;
376 /// Work with `self` as a mut slice.
377 /// Primarily intended for getting a &mut [T] from a [T; N].
379 fn as_mut_slice(&mut self) -> &mut [Self::Item];
381 /// Returns a mutable subslice spanning the interval [`start`, `end`).
383 /// Panics when the end of the new slice lies beyond the end of the
384 /// original slice (i.e. when `end > self.len()`) or when `start > end`.
386 /// Slicing with `start` equal to `end` yields an empty slice.
387 #[unstable = "will be replaced by slice syntax"]
388 fn slice_mut(&mut self, start: uint, end: uint) -> &mut [Self::Item];
390 /// Returns a mutable subslice from `start` to the end of the slice.
392 /// Panics when `start` is strictly greater than the length of the original slice.
394 /// Slicing from `self.len()` yields an empty slice.
395 #[unstable = "will be replaced by slice syntax"]
396 fn slice_from_mut(&mut self, start: uint) -> &mut [Self::Item];
398 /// Returns a mutable subslice from the start of the slice to `end`.
400 /// Panics when `end` is strictly greater than the length of the original slice.
402 /// Slicing to `0` yields an empty slice.
403 #[unstable = "will be replaced by slice syntax"]
404 fn slice_to_mut(&mut self, end: uint) -> &mut [Self::Item];
406 /// Returns an iterator that allows modifying each value
408 fn iter_mut(&mut self) -> IterMut<Self::Item>;
410 /// Returns a mutable pointer to the first element of a slice, or `None` if it is empty
412 fn first_mut(&mut self) -> Option<&mut Self::Item>;
414 /// Returns all but the first element of a mutable slice
415 #[unstable = "likely to be renamed or removed"]
416 fn tail_mut(&mut self) -> &mut [Self::Item];
418 /// Returns all but the last element of a mutable slice
419 #[unstable = "likely to be renamed or removed"]
420 fn init_mut(&mut self) -> &mut [Self::Item];
422 /// Returns a mutable pointer to the last item in the slice.
424 fn last_mut(&mut self) -> Option<&mut Self::Item>;
426 /// Returns an iterator over mutable subslices separated by elements that
427 /// match `pred`. The matched element is not contained in the subslices.
429 fn split_mut<F>(&mut self, pred: F) -> SplitMut<Self::Item, F>
430 where F: FnMut(&Self::Item) -> bool;
432 /// Returns an iterator over subslices separated by elements that match
433 /// `pred`, limited to splitting at most `n` times. The matched element is
434 /// not contained in the subslices.
436 fn splitn_mut<F>(&mut self, n: uint, pred: F) -> SplitNMut<Self::Item, F>
437 where F: FnMut(&Self::Item) -> bool;
439 /// Returns an iterator over subslices separated by elements that match
440 /// `pred` limited to splitting at most `n` times. This starts at the end of
441 /// the slice and works backwards. The matched element is not contained in
444 fn rsplitn_mut<F>(&mut self, n: uint, pred: F) -> RSplitNMut<Self::Item, F>
445 where F: FnMut(&Self::Item) -> bool;
447 /// Returns an iterator over `chunk_size` elements of the slice at a time.
448 /// The chunks are mutable and do not overlap. If `chunk_size` does
449 /// not divide the length of the slice, then the last chunk will not
450 /// have length `chunk_size`.
454 /// Panics if `chunk_size` is 0.
456 fn chunks_mut(&mut self, chunk_size: uint) -> ChunksMut<Self::Item>;
458 /// Swaps two elements in a slice.
462 /// * a - The index of the first element
463 /// * b - The index of the second element
467 /// Panics if `a` or `b` are out of bounds.
472 /// let mut v = ["a", "b", "c", "d"];
474 /// assert!(v == ["a", "d", "c", "b"]);
477 fn swap(&mut self, a: uint, b: uint);
479 /// Divides one `&mut` into two at an index.
481 /// The first will contain all indices from `[0, mid)` (excluding
482 /// the index `mid` itself) and the second will contain all
483 /// indices from `[mid, len)` (excluding the index `len` itself).
487 /// Panics if `mid > len`.
492 /// let mut v = [1i, 2, 3, 4, 5, 6];
494 /// // scoped to restrict the lifetime of the borrows
496 /// let (left, right) = v.split_at_mut(0);
497 /// assert!(left == []);
498 /// assert!(right == [1i, 2, 3, 4, 5, 6]);
502 /// let (left, right) = v.split_at_mut(2);
503 /// assert!(left == [1i, 2]);
504 /// assert!(right == [3i, 4, 5, 6]);
508 /// let (left, right) = v.split_at_mut(6);
509 /// assert!(left == [1i, 2, 3, 4, 5, 6]);
510 /// assert!(right == []);
514 fn split_at_mut(&mut self, mid: uint) -> (&mut [Self::Item], &mut [Self::Item]);
516 /// Reverse the order of elements in a slice, in place.
521 /// let mut v = [1i, 2, 3];
523 /// assert!(v == [3i, 2, 1]);
526 fn reverse(&mut self);
528 /// Returns an unsafe mutable pointer to the element in index
530 unsafe fn get_unchecked_mut(&mut self, index: uint) -> &mut Self::Item;
532 /// Return an unsafe mutable pointer to the slice's buffer.
534 /// The caller must ensure that the slice outlives the pointer this
535 /// function returns, or else it will end up pointing to garbage.
537 /// Modifying the slice may cause its buffer to be reallocated, which
538 /// would also make any pointers to it invalid.
541 fn as_mut_ptr(&mut self) -> *mut Self::Item;
543 /// Copies `self` into a new `Vec`.
545 fn to_vec(&self) -> Vec<Self::Item> where Self::Item: Clone;
547 /// Creates an iterator that yields every possible permutation of the
548 /// vector in succession.
553 /// let v = [1i, 2, 3];
554 /// let mut perms = v.permutations();
557 /// println!("{:?}", p);
561 /// Iterating through permutations one by one.
564 /// let v = [1i, 2, 3];
565 /// let mut perms = v.permutations();
567 /// assert_eq!(Some(vec![1i, 2, 3]), perms.next());
568 /// assert_eq!(Some(vec![1i, 3, 2]), perms.next());
569 /// assert_eq!(Some(vec![3i, 1, 2]), perms.next());
572 fn permutations(&self) -> Permutations<Self::Item> where Self::Item: Clone;
574 /// Copies as many elements from `src` as it can into `self` (the
575 /// shorter of `self.len()` and `src.len()`). Returns the number
576 /// of elements copied.
581 /// let mut dst = [0i, 0, 0];
582 /// let src = [1i, 2];
584 /// assert!(dst.clone_from_slice(&src) == 2);
585 /// assert!(dst == [1, 2, 0]);
587 /// let src2 = [3i, 4, 5, 6];
588 /// assert!(dst.clone_from_slice(&src2) == 3);
589 /// assert!(dst == [3i, 4, 5]);
592 fn clone_from_slice(&mut self, &[Self::Item]) -> uint where Self::Item: Clone;
594 /// Sorts the slice, in place.
596 /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`.
601 /// let mut v = [-5i, 4, 1, -3, 2];
604 /// assert!(v == [-5i, -3, 1, 2, 4]);
607 fn sort(&mut self) where Self::Item: Ord;
609 /// Binary search a sorted slice for a given element.
611 /// If the value is found then `Ok` is returned, containing the
612 /// index of the matching element; if the value is not found then
613 /// `Err` is returned, containing the index where a matching
614 /// element could be inserted while maintaining sorted order.
618 /// Looks up a series of four elements. The first is found, with a
619 /// uniquely determined position; the second and third are not
620 /// found; the fourth could match any position in `[1,4]`.
623 /// let s = [0i, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
624 /// let s = s.as_slice();
626 /// assert_eq!(s.binary_search(&13), Ok(9));
627 /// assert_eq!(s.binary_search(&4), Err(7));
628 /// assert_eq!(s.binary_search(&100), Err(13));
629 /// let r = s.binary_search(&1);
630 /// assert!(match r { Ok(1...4) => true, _ => false, });
633 fn binary_search(&self, x: &Self::Item) -> Result<uint, uint> where Self::Item: Ord;
635 /// Deprecated: use `binary_search` instead.
636 #[deprecated = "use binary_search instead"]
637 fn binary_search_elem(&self, x: &Self::Item) -> Result<uint, uint> where Self::Item: Ord {
638 self.binary_search(x)
641 /// Mutates the slice to the next lexicographic permutation.
643 /// Returns `true` if successful and `false` if the slice is at the
644 /// last-ordered permutation.
649 /// let v: &mut [_] = &mut [0i, 1, 2];
650 /// v.next_permutation();
651 /// let b: &mut [_] = &mut [0i, 2, 1];
653 /// v.next_permutation();
654 /// let b: &mut [_] = &mut [1i, 0, 2];
657 #[unstable = "uncertain if this merits inclusion in std"]
658 fn next_permutation(&mut self) -> bool where Self::Item: Ord;
660 /// Mutates the slice to the previous lexicographic permutation.
662 /// Returns `true` if successful and `false` if the slice is at the
663 /// first-ordered permutation.
668 /// let v: &mut [_] = &mut [1i, 0, 2];
669 /// v.prev_permutation();
670 /// let b: &mut [_] = &mut [0i, 2, 1];
672 /// v.prev_permutation();
673 /// let b: &mut [_] = &mut [0i, 1, 2];
676 #[unstable = "uncertain if this merits inclusion in std"]
677 fn prev_permutation(&mut self) -> bool where Self::Item: Ord;
679 /// Find the first index containing a matching value.
681 fn position_elem(&self, t: &Self::Item) -> Option<uint> where Self::Item: PartialEq;
683 /// Find the last index containing a matching value.
685 fn rposition_elem(&self, t: &Self::Item) -> Option<uint> where Self::Item: PartialEq;
687 /// Return true if the slice contains an element with the given value.
689 fn contains(&self, x: &Self::Item) -> bool where Self::Item: PartialEq;
691 /// Returns true if `needle` is a prefix of the slice.
693 fn starts_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
695 /// Returns true if `needle` is a suffix of the slice.
697 fn ends_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
699 /// Convert `self` into a vector without clones or allocation.
701 fn into_vec(self: Box<Self>) -> Vec<Self::Item>;
705 impl<T> SliceExt for [T] {
709 fn sort_by<F>(&mut self, compare: F) where F: FnMut(&T, &T) -> Ordering {
710 merge_sort(self, compare)
714 fn move_from(&mut self, mut src: Vec<T>, start: uint, end: uint) -> uint {
715 for (a, b) in self.iter_mut().zip(src.slice_mut(start, end).iter_mut()) {
718 cmp::min(self.len(), end-start)
722 fn slice<'a>(&'a self, start: uint, end: uint) -> &'a [T] {
723 core_slice::SliceExt::slice(self, start, end)
727 fn slice_from<'a>(&'a self, start: uint) -> &'a [T] {
728 core_slice::SliceExt::slice_from(self, start)
732 fn slice_to<'a>(&'a self, end: uint) -> &'a [T] {
733 core_slice::SliceExt::slice_to(self, end)
737 fn split_at<'a>(&'a self, mid: uint) -> (&'a [T], &'a [T]) {
738 core_slice::SliceExt::split_at(self, mid)
742 fn iter<'a>(&'a self) -> Iter<'a, T> {
743 core_slice::SliceExt::iter(self)
747 fn split<F>(&self, pred: F) -> Split<T, F>
748 where F: FnMut(&T) -> bool {
749 core_slice::SliceExt::split(self, pred)
753 fn splitn<F>(&self, n: uint, pred: F) -> SplitN<T, F>
754 where F: FnMut(&T) -> bool {
755 core_slice::SliceExt::splitn(self, n, pred)
759 fn rsplitn<F>(&self, n: uint, pred: F) -> RSplitN<T, F>
760 where F: FnMut(&T) -> bool {
761 core_slice::SliceExt::rsplitn(self, n, pred)
765 fn windows<'a>(&'a self, size: uint) -> Windows<'a, T> {
766 core_slice::SliceExt::windows(self, size)
770 fn chunks<'a>(&'a self, size: uint) -> Chunks<'a, T> {
771 core_slice::SliceExt::chunks(self, size)
775 fn get<'a>(&'a self, index: uint) -> Option<&'a T> {
776 core_slice::SliceExt::get(self, index)
780 fn first<'a>(&'a self) -> Option<&'a T> {
781 core_slice::SliceExt::first(self)
785 fn tail<'a>(&'a self) -> &'a [T] {
786 core_slice::SliceExt::tail(self)
790 fn init<'a>(&'a self) -> &'a [T] {
791 core_slice::SliceExt::init(self)
795 fn last<'a>(&'a self) -> Option<&'a T> {
796 core_slice::SliceExt::last(self)
800 unsafe fn get_unchecked<'a>(&'a self, index: uint) -> &'a T {
801 core_slice::SliceExt::get_unchecked(self, index)
805 fn as_ptr(&self) -> *const T {
806 core_slice::SliceExt::as_ptr(self)
810 fn binary_search_by<F>(&self, f: F) -> Result<uint, uint>
811 where F: FnMut(&T) -> Ordering {
812 core_slice::SliceExt::binary_search_by(self, f)
816 fn len(&self) -> uint {
817 core_slice::SliceExt::len(self)
821 fn is_empty(&self) -> bool {
822 core_slice::SliceExt::is_empty(self)
826 fn get_mut<'a>(&'a mut self, index: uint) -> Option<&'a mut T> {
827 core_slice::SliceExt::get_mut(self, index)
831 fn as_mut_slice<'a>(&'a mut self) -> &'a mut [T] {
832 core_slice::SliceExt::as_mut_slice(self)
836 fn slice_mut<'a>(&'a mut self, start: uint, end: uint) -> &'a mut [T] {
837 core_slice::SliceExt::slice_mut(self, start, end)
841 fn slice_from_mut<'a>(&'a mut self, start: uint) -> &'a mut [T] {
842 core_slice::SliceExt::slice_from_mut(self, start)
846 fn slice_to_mut<'a>(&'a mut self, end: uint) -> &'a mut [T] {
847 core_slice::SliceExt::slice_to_mut(self, end)
851 fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
852 core_slice::SliceExt::iter_mut(self)
856 fn first_mut<'a>(&'a mut self) -> Option<&'a mut T> {
857 core_slice::SliceExt::first_mut(self)
861 fn tail_mut<'a>(&'a mut self) -> &'a mut [T] {
862 core_slice::SliceExt::tail_mut(self)
866 fn init_mut<'a>(&'a mut self) -> &'a mut [T] {
867 core_slice::SliceExt::init_mut(self)
871 fn last_mut<'a>(&'a mut self) -> Option<&'a mut T> {
872 core_slice::SliceExt::last_mut(self)
876 fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F>
877 where F: FnMut(&T) -> bool {
878 core_slice::SliceExt::split_mut(self, pred)
882 fn splitn_mut<F>(&mut self, n: uint, pred: F) -> SplitNMut<T, F>
883 where F: FnMut(&T) -> bool {
884 core_slice::SliceExt::splitn_mut(self, n, pred)
888 fn rsplitn_mut<F>(&mut self, n: uint, pred: F) -> RSplitNMut<T, F>
889 where F: FnMut(&T) -> bool {
890 core_slice::SliceExt::rsplitn_mut(self, n, pred)
894 fn chunks_mut<'a>(&'a mut self, chunk_size: uint) -> ChunksMut<'a, T> {
895 core_slice::SliceExt::chunks_mut(self, chunk_size)
899 fn swap(&mut self, a: uint, b: uint) {
900 core_slice::SliceExt::swap(self, a, b)
904 fn split_at_mut<'a>(&'a mut self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
905 core_slice::SliceExt::split_at_mut(self, mid)
909 fn reverse(&mut self) {
910 core_slice::SliceExt::reverse(self)
914 unsafe fn get_unchecked_mut<'a>(&'a mut self, index: uint) -> &'a mut T {
915 core_slice::SliceExt::get_unchecked_mut(self, index)
919 fn as_mut_ptr(&mut self) -> *mut T {
920 core_slice::SliceExt::as_mut_ptr(self)
923 /// Returns a copy of `v`.
925 fn to_vec(&self) -> Vec<T> where T: Clone {
926 let mut vector = Vec::with_capacity(self.len());
927 vector.push_all(self);
931 /// Returns an iterator over all permutations of a vector.
932 fn permutations(&self) -> Permutations<T> where T: Clone {
934 swaps: ElementSwaps::new(self.len()),
939 fn clone_from_slice(&mut self, src: &[T]) -> uint where T: Clone {
940 core_slice::SliceExt::clone_from_slice(self, src)
944 fn sort(&mut self) where T: Ord {
945 self.sort_by(|a, b| a.cmp(b))
948 fn binary_search(&self, x: &T) -> Result<uint, uint> where T: Ord {
949 core_slice::SliceExt::binary_search(self, x)
952 fn next_permutation(&mut self) -> bool where T: Ord {
953 core_slice::SliceExt::next_permutation(self)
956 fn prev_permutation(&mut self) -> bool where T: Ord {
957 core_slice::SliceExt::prev_permutation(self)
960 fn position_elem(&self, t: &T) -> Option<uint> where T: PartialEq {
961 core_slice::SliceExt::position_elem(self, t)
964 fn rposition_elem(&self, t: &T) -> Option<uint> where T: PartialEq {
965 core_slice::SliceExt::rposition_elem(self, t)
968 fn contains(&self, x: &T) -> bool where T: PartialEq {
969 core_slice::SliceExt::contains(self, x)
972 fn starts_with(&self, needle: &[T]) -> bool where T: PartialEq {
973 core_slice::SliceExt::starts_with(self, needle)
976 fn ends_with(&self, needle: &[T]) -> bool where T: PartialEq {
977 core_slice::SliceExt::ends_with(self, needle)
980 fn into_vec(mut self: Box<Self>) -> Vec<T> {
982 let xs = Vec::from_raw_parts(self.as_mut_ptr(), self.len(), self.len());
989 ////////////////////////////////////////////////////////////////////////////////
990 // Extension traits for slices over specific kinds of data
991 ////////////////////////////////////////////////////////////////////////////////
992 #[unstable = "U should be an associated type"]
993 /// An extension trait for concatenating slices
994 pub trait SliceConcatExt<T: ?Sized, U> {
995 /// Flattens a slice of `T` into a single value `U`.
997 fn concat(&self) -> U;
999 /// Flattens a slice of `T` into a single value `U`, placing a
1000 /// given separator between each.
1002 fn connect(&self, sep: &T) -> U;
1005 impl<T: Clone, V: AsSlice<T>> SliceConcatExt<T, Vec<T>> for [V] {
1006 fn concat(&self) -> Vec<T> {
1007 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
1008 let mut result = Vec::with_capacity(size);
1009 for v in self.iter() {
1010 result.push_all(v.as_slice())
1015 fn connect(&self, sep: &T) -> Vec<T> {
1016 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
1017 let mut result = Vec::with_capacity(size + self.len());
1018 let mut first = true;
1019 for v in self.iter() {
1020 if first { first = false } else { result.push(sep.clone()) }
1021 result.push_all(v.as_slice())
1027 /// An iterator that yields the element swaps needed to produce
1028 /// a sequence of all possible permutations for an indexed sequence of
1029 /// elements. Each permutation is only a single swap apart.
1031 /// The Steinhaus-Johnson-Trotter algorithm is used.
1033 /// Generates even and odd permutations alternately.
1035 /// The last generated swap is always (0, 1), and it returns the
1036 /// sequence to its initial order.
1039 pub struct ElementSwaps {
1040 sdir: Vec<SizeDirection>,
1041 /// If `true`, emit the last swap that returns the sequence to initial
1048 /// Creates an `ElementSwaps` iterator for a sequence of `length` elements.
1050 pub fn new(length: uint) -> ElementSwaps {
1051 // Initialize `sdir` with a direction that position should move in
1052 // (all negative at the beginning) and the `size` of the
1053 // element (equal to the original index).
1056 sdir: range(0, length).map(|i| SizeDirection{ size: i, dir: Neg }).collect(),
1062 ////////////////////////////////////////////////////////////////////////////////
1063 // Standard trait implementations for slices
1064 ////////////////////////////////////////////////////////////////////////////////
1066 #[unstable = "trait is unstable"]
1067 impl<T> BorrowFrom<Vec<T>> for [T] {
1068 fn borrow_from(owned: &Vec<T>) -> &[T] { &owned[] }
1071 #[unstable = "trait is unstable"]
1072 impl<T> BorrowFromMut<Vec<T>> for [T] {
1073 fn borrow_from_mut(owned: &mut Vec<T>) -> &mut [T] { &mut owned[] }
1076 #[unstable = "trait is unstable"]
1077 impl<T: Clone> ToOwned<Vec<T>> for [T] {
1078 fn to_owned(&self) -> Vec<T> { self.to_vec() }
1081 ////////////////////////////////////////////////////////////////////////////////
1083 ////////////////////////////////////////////////////////////////////////////////
1085 #[derive(Copy, Clone)]
1086 enum Direction { Pos, Neg }
1088 /// An `Index` and `Direction` together.
1089 #[derive(Copy, Clone)]
1090 struct SizeDirection {
1096 impl Iterator for ElementSwaps {
1097 type Item = (uint, uint);
1100 fn next(&mut self) -> Option<(uint, uint)> {
1101 fn new_pos(i: uint, s: Direction) -> uint {
1102 i + match s { Pos => 1, Neg => -1 }
1105 // Find the index of the largest mobile element:
1106 // The direction should point into the vector, and the
1107 // swap should be with a smaller `size` element.
1108 let max = self.sdir.iter().map(|&x| x).enumerate()
1110 new_pos(i, sd.dir) < self.sdir.len() &&
1111 self.sdir[new_pos(i, sd.dir)].size < sd.size)
1112 .max_by(|&(_, sd)| sd.size);
1115 let j = new_pos(i, sd.dir);
1116 self.sdir.swap(i, j);
1118 // Swap the direction of each larger SizeDirection
1119 for x in self.sdir.iter_mut() {
1120 if x.size > sd.size {
1121 x.dir = match x.dir { Pos => Neg, Neg => Pos };
1124 self.swaps_made += 1;
1127 None => if self.emit_reset {
1128 self.emit_reset = false;
1129 if self.sdir.len() > 1 {
1131 self.swaps_made += 1;
1134 // Vector is of the form [] or [x], and the only permutation is itself
1135 self.swaps_made += 1;
1143 fn size_hint(&self) -> (uint, Option<uint>) {
1144 // For a vector of size n, there are exactly n! permutations.
1145 let n = range(2, self.sdir.len() + 1).product();
1146 (n - self.swaps_made, Some(n - self.swaps_made))
1150 /// An iterator that uses `ElementSwaps` to iterate through
1151 /// all possible permutations of a vector.
1153 /// The first iteration yields a clone of the vector as it is,
1154 /// then each successive element is the vector with one
1157 /// Generates even and odd permutations alternately.
1159 pub struct Permutations<T> {
1160 swaps: ElementSwaps,
1164 #[unstable = "trait is unstable"]
1165 impl<T: Clone> Iterator for Permutations<T> {
1169 fn next(&mut self) -> Option<Vec<T>> {
1170 match self.swaps.next() {
1172 Some((0,0)) => Some(self.v.clone()),
1174 let elt = self.v.clone();
1182 fn size_hint(&self) -> (uint, Option<uint>) {
1183 self.swaps.size_hint()
1187 ////////////////////////////////////////////////////////////////////////////////
1189 ////////////////////////////////////////////////////////////////////////////////
1191 fn insertion_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering {
1192 let len = v.len() as int;
1193 let buf_v = v.as_mut_ptr();
1196 for i in range(1, len) {
1197 // j satisfies: 0 <= j <= i;
1200 // `i` is in bounds.
1201 let read_ptr = buf_v.offset(i) as *const T;
1203 // find where to insert, we need to do strict <,
1204 // rather than <=, to maintain stability.
1206 // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
1208 compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less {
1212 // shift everything to the right, to make space to
1213 // insert this value.
1215 // j + 1 could be `len` (for the last `i`), but in
1216 // that case, `i == j` so we don't copy. The
1217 // `.offset(j)` is always in bounds.
1220 let tmp = ptr::read(read_ptr);
1221 ptr::copy_memory(buf_v.offset(j + 1),
1224 ptr::copy_nonoverlapping_memory(buf_v.offset(j),
1233 fn merge_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering {
1234 // warning: this wildly uses unsafe.
1235 static BASE_INSERTION: uint = 32;
1236 static LARGE_INSERTION: uint = 16;
1238 // FIXME #12092: smaller insertion runs seems to make sorting
1239 // vectors of large elements a little faster on some platforms,
1240 // but hasn't been tested/tuned extensively
1241 let insertion = if size_of::<T>() <= 16 {
1249 // short vectors get sorted in-place via insertion sort to avoid allocations
1250 if len <= insertion {
1251 insertion_sort(v, compare);
1255 // allocate some memory to use as scratch memory, we keep the
1256 // length 0 so we can keep shallow copies of the contents of `v`
1257 // without risking the dtors running on an object twice if
1258 // `compare` panics.
1259 let mut working_space = Vec::with_capacity(2 * len);
1260 // these both are buffers of length `len`.
1261 let mut buf_dat = working_space.as_mut_ptr();
1262 let mut buf_tmp = unsafe {buf_dat.offset(len as int)};
1265 let buf_v = v.as_ptr();
1267 // step 1. sort short runs with insertion sort. This takes the
1268 // values from `v` and sorts them into `buf_dat`, leaving that
1269 // with sorted runs of length INSERTION.
1271 // We could hardcode the sorting comparisons here, and we could
1272 // manipulate/step the pointers themselves, rather than repeatedly
1274 for start in range_step(0, len, insertion) {
1275 // start <= i < len;
1276 for i in range(start, cmp::min(start + insertion, len)) {
1277 // j satisfies: start <= j <= i;
1278 let mut j = i as int;
1280 // `i` is in bounds.
1281 let read_ptr = buf_v.offset(i as int);
1283 // find where to insert, we need to do strict <,
1284 // rather than <=, to maintain stability.
1286 // start <= j - 1 < len, so .offset(j - 1) is in
1288 while j > start as int &&
1289 compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less {
1293 // shift everything to the right, to make space to
1294 // insert this value.
1296 // j + 1 could be `len` (for the last `i`), but in
1297 // that case, `i == j` so we don't copy. The
1298 // `.offset(j)` is always in bounds.
1299 ptr::copy_memory(buf_dat.offset(j + 1),
1300 &*buf_dat.offset(j),
1302 ptr::copy_nonoverlapping_memory(buf_dat.offset(j), read_ptr, 1);
1307 // step 2. merge the sorted runs.
1308 let mut width = insertion;
1310 // merge the sorted runs of length `width` in `buf_dat` two at
1311 // a time, placing the result in `buf_tmp`.
1313 // 0 <= start <= len.
1314 for start in range_step(0, len, 2 * width) {
1315 // manipulate pointers directly for speed (rather than
1316 // using a `for` loop with `range` and `.offset` inside
1319 // the end of the first run & start of the
1320 // second. Offset of `len` is defined, since this is
1321 // precisely one byte past the end of the object.
1322 let right_start = buf_dat.offset(cmp::min(start + width, len) as int);
1323 // end of the second. Similar reasoning to the above re safety.
1324 let right_end_idx = cmp::min(start + 2 * width, len);
1325 let right_end = buf_dat.offset(right_end_idx as int);
1327 // the pointers to the elements under consideration
1328 // from the two runs.
1330 // both of these are in bounds.
1331 let mut left = buf_dat.offset(start as int);
1332 let mut right = right_start;
1334 // where we're putting the results, it is a run of
1335 // length `2*width`, so we step it once for each step
1336 // of either `left` or `right`. `buf_tmp` has length
1337 // `len`, so these are in bounds.
1338 let mut out = buf_tmp.offset(start as int);
1339 let out_end = buf_tmp.offset(right_end_idx as int);
1341 while out < out_end {
1342 // Either the left or the right run are exhausted,
1343 // so just copy the remainder from the other run
1344 // and move on; this gives a huge speed-up (order
1345 // of 25%) for mostly sorted vectors (the best
1347 if left == right_start {
1348 // the number remaining in this run.
1349 let elems = (right_end as uint - right as uint) / mem::size_of::<T>();
1350 ptr::copy_nonoverlapping_memory(out, &*right, elems);
1352 } else if right == right_end {
1353 let elems = (right_start as uint - left as uint) / mem::size_of::<T>();
1354 ptr::copy_nonoverlapping_memory(out, &*left, elems);
1358 // check which side is smaller, and that's the
1359 // next element for the new run.
1361 // `left < right_start` and `right < right_end`,
1362 // so these are valid.
1363 let to_copy = if compare(&*left, &*right) == Greater {
1368 ptr::copy_nonoverlapping_memory(out, &*to_copy, 1);
1374 mem::swap(&mut buf_dat, &mut buf_tmp);
1379 // write the result to `v` in one go, so that there are never two copies
1380 // of the same object in `v`.
1382 ptr::copy_nonoverlapping_memory(v.as_mut_ptr(), &*buf_dat, len);
1385 // increment the pointer, returning the old pointer.
1387 unsafe fn step<T>(ptr: &mut *mut T) -> *mut T {
1389 *ptr = ptr.offset(1);
1396 use core::cmp::Ordering::{Greater, Less, Equal};
1397 use core::prelude::{Some, None, range, Clone};
1398 use core::prelude::{Iterator, IteratorExt};
1399 use core::prelude::{AsSlice};
1400 use core::prelude::{Ord, FullRange};
1401 use core::default::Default;
1403 use std::iter::RandomAccessIterator;
1404 use std::rand::{Rng, thread_rng};
1406 use string::ToString;
1408 use super::{ElementSwaps, SliceConcatExt, SliceExt};
1410 fn square(n: uint) -> uint { n * n }
1412 fn is_odd(n: &uint) -> bool { *n % 2u == 1u }
1416 // Test on-stack from_fn.
1417 let mut v = range(0, 3).map(square).collect::<Vec<_>>();
1419 let v = v.as_slice();
1420 assert_eq!(v.len(), 3u);
1421 assert_eq!(v[0], 0u);
1422 assert_eq!(v[1], 1u);
1423 assert_eq!(v[2], 4u);
1426 // Test on-heap from_fn.
1427 v = range(0, 5).map(square).collect::<Vec<_>>();
1429 let v = v.as_slice();
1430 assert_eq!(v.len(), 5u);
1431 assert_eq!(v[0], 0u);
1432 assert_eq!(v[1], 1u);
1433 assert_eq!(v[2], 4u);
1434 assert_eq!(v[3], 9u);
1435 assert_eq!(v[4], 16u);
1440 fn test_from_elem() {
1441 // Test on-stack from_elem.
1442 let mut v = vec![10u, 10u];
1444 let v = v.as_slice();
1445 assert_eq!(v.len(), 2u);
1446 assert_eq!(v[0], 10u);
1447 assert_eq!(v[1], 10u);
1450 // Test on-heap from_elem.
1451 v = vec![20u, 20u, 20u, 20u, 20u, 20u];
1453 let v = v.as_slice();
1454 assert_eq!(v[0], 20u);
1455 assert_eq!(v[1], 20u);
1456 assert_eq!(v[2], 20u);
1457 assert_eq!(v[3], 20u);
1458 assert_eq!(v[4], 20u);
1459 assert_eq!(v[5], 20u);
1464 fn test_is_empty() {
1465 let xs: [int; 0] = [];
1466 assert!(xs.is_empty());
1467 assert!(![0i].is_empty());
1471 fn test_len_divzero() {
1473 let v0 : &[Z] = &[];
1474 let v1 : &[Z] = &[[]];
1475 let v2 : &[Z] = &[[], []];
1476 assert_eq!(mem::size_of::<Z>(), 0);
1477 assert_eq!(v0.len(), 0);
1478 assert_eq!(v1.len(), 1);
1479 assert_eq!(v2.len(), 2);
1484 let mut a = vec![11i];
1485 assert_eq!(a.as_slice().get(1), None);
1487 assert_eq!(a.as_slice().get(1).unwrap(), &12);
1488 a = vec![11i, 12, 13];
1489 assert_eq!(a.as_slice().get(1).unwrap(), &12);
1495 assert_eq!(a.as_slice().first(), None);
1497 assert_eq!(a.as_slice().first().unwrap(), &11);
1499 assert_eq!(a.as_slice().first().unwrap(), &11);
1503 fn test_first_mut() {
1505 assert_eq!(a.first_mut(), None);
1507 assert_eq!(*a.first_mut().unwrap(), 11);
1509 assert_eq!(*a.first_mut().unwrap(), 11);
1514 let mut a = vec![11i];
1515 let b: &[int] = &[];
1516 assert_eq!(a.tail(), b);
1518 let b: &[int] = &[12];
1519 assert_eq!(a.tail(), b);
1523 fn test_tail_mut() {
1524 let mut a = vec![11i];
1525 let b: &mut [int] = &mut [];
1526 assert!(a.tail_mut() == b);
1528 let b: &mut [int] = &mut [12];
1529 assert!(a.tail_mut() == b);
1534 fn test_tail_empty() {
1535 let a: Vec<int> = vec![];
1541 fn test_tail_mut_empty() {
1542 let mut a: Vec<int> = vec![];
1548 let mut a = vec![11i];
1549 let b: &[int] = &[];
1550 assert_eq!(a.init(), b);
1552 let b: &[int] = &[11];
1553 assert_eq!(a.init(), b);
1557 fn test_init_mut() {
1558 let mut a = vec![11i];
1559 let b: &mut [int] = &mut [];
1560 assert!(a.init_mut() == b);
1562 let b: &mut [int] = &mut [11];
1563 assert!(a.init_mut() == b);
1568 fn test_init_empty() {
1569 let a: Vec<int> = vec![];
1575 fn test_init_mut_empty() {
1576 let mut a: Vec<int> = vec![];
1583 assert_eq!(a.as_slice().last(), None);
1585 assert_eq!(a.as_slice().last().unwrap(), &11);
1587 assert_eq!(a.as_slice().last().unwrap(), &12);
1591 fn test_last_mut() {
1593 assert_eq!(a.last_mut(), None);
1595 assert_eq!(*a.last_mut().unwrap(), 11);
1597 assert_eq!(*a.last_mut().unwrap(), 12);
1602 // Test fixed length vector.
1603 let vec_fixed = [1i, 2, 3, 4];
1604 let v_a = vec_fixed[1u..vec_fixed.len()].to_vec();
1605 assert_eq!(v_a.len(), 3u);
1606 let v_a = v_a.as_slice();
1607 assert_eq!(v_a[0], 2);
1608 assert_eq!(v_a[1], 3);
1609 assert_eq!(v_a[2], 4);
1612 let vec_stack: &[_] = &[1i, 2, 3];
1613 let v_b = vec_stack[1u..3u].to_vec();
1614 assert_eq!(v_b.len(), 2u);
1615 let v_b = v_b.as_slice();
1616 assert_eq!(v_b[0], 2);
1617 assert_eq!(v_b[1], 3);
1620 let vec_unique = vec![1i, 2, 3, 4, 5, 6];
1621 let v_d = vec_unique[1u..6u].to_vec();
1622 assert_eq!(v_d.len(), 5u);
1623 let v_d = v_d.as_slice();
1624 assert_eq!(v_d[0], 2);
1625 assert_eq!(v_d[1], 3);
1626 assert_eq!(v_d[2], 4);
1627 assert_eq!(v_d[3], 5);
1628 assert_eq!(v_d[4], 6);
1632 fn test_slice_from() {
1633 let vec: &[int] = &[1, 2, 3, 4];
1634 assert_eq!(&vec[], vec);
1635 let b: &[int] = &[3, 4];
1636 assert_eq!(&vec[2..], b);
1637 let b: &[int] = &[];
1638 assert_eq!(&vec[4..], b);
1642 fn test_slice_to() {
1643 let vec: &[int] = &[1, 2, 3, 4];
1644 assert_eq!(&vec[..4], vec);
1645 let b: &[int] = &[1, 2];
1646 assert_eq!(&vec[..2], b);
1647 let b: &[int] = &[];
1648 assert_eq!(&vec[..0], b);
1654 let mut v = vec![5i];
1656 assert_eq!(v.len(), 0);
1657 assert_eq!(e, Some(5));
1659 assert_eq!(f, None);
1661 assert_eq!(g, None);
1665 fn test_swap_remove() {
1666 let mut v = vec![1i, 2, 3, 4, 5];
1667 let mut e = v.swap_remove(0);
1669 assert_eq!(v, vec![5i, 2, 3, 4]);
1670 e = v.swap_remove(3);
1672 assert_eq!(v, vec![5i, 2, 3]);
1677 fn test_swap_remove_fail() {
1678 let mut v = vec![1i];
1679 let _ = v.swap_remove(0);
1680 let _ = v.swap_remove(0);
1684 fn test_swap_remove_noncopyable() {
1685 // Tests that we don't accidentally run destructors twice.
1686 let mut v = Vec::new();
1690 let mut _e = v.swap_remove(0);
1691 assert_eq!(v.len(), 2);
1692 _e = v.swap_remove(1);
1693 assert_eq!(v.len(), 1);
1694 _e = v.swap_remove(0);
1695 assert_eq!(v.len(), 0);
1700 // Test on-stack push().
1703 assert_eq!(v.len(), 1u);
1704 assert_eq!(v.as_slice()[0], 1);
1706 // Test on-heap push().
1708 assert_eq!(v.len(), 2u);
1709 assert_eq!(v.as_slice()[0], 1);
1710 assert_eq!(v.as_slice()[1], 2);
1714 fn test_truncate() {
1715 let mut v = vec![box 6i,box 5,box 4];
1717 let v = v.as_slice();
1718 assert_eq!(v.len(), 1);
1719 assert_eq!(*(v[0]), 6);
1720 // If the unsafe block didn't drop things properly, we blow up here.
1725 let mut v = vec![box 6i,box 5,box 4];
1727 assert_eq!(v.len(), 0);
1728 // If the unsafe block didn't drop things properly, we blow up here.
1733 fn case(a: Vec<uint>, b: Vec<uint>) {
1738 case(vec![], vec![]);
1739 case(vec![1u], vec![1]);
1740 case(vec![1u,1], vec![1]);
1741 case(vec![1u,2,3], vec![1,2,3]);
1742 case(vec![1u,1,2,3], vec![1,2,3]);
1743 case(vec![1u,2,2,3], vec![1,2,3]);
1744 case(vec![1u,2,3,3], vec![1,2,3]);
1745 case(vec![1u,1,2,2,2,3,3], vec![1,2,3]);
1749 fn test_dedup_unique() {
1750 let mut v0 = vec![box 1i, box 1, box 2, box 3];
1752 let mut v1 = vec![box 1i, box 2, box 2, box 3];
1754 let mut v2 = vec![box 1i, box 2, box 3, box 3];
1757 * If the boxed pointers were leaked or otherwise misused, valgrind
1758 * and/or rt should raise errors.
1763 fn test_dedup_shared() {
1764 let mut v0 = vec![box 1i, box 1, box 2, box 3];
1766 let mut v1 = vec![box 1i, box 2, box 2, box 3];
1768 let mut v2 = vec![box 1i, box 2, box 3, box 3];
1771 * If the pointers were leaked or otherwise misused, valgrind and/or
1772 * rt should raise errors.
1778 let mut v = vec![1u, 2, 3, 4, 5];
1780 assert_eq!(v, vec![1u, 3, 5]);
1784 fn test_element_swaps() {
1785 let mut v = [1i, 2, 3];
1786 for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
1789 0 => assert!(v == [1, 3, 2]),
1790 1 => assert!(v == [3, 1, 2]),
1791 2 => assert!(v == [3, 2, 1]),
1792 3 => assert!(v == [2, 3, 1]),
1793 4 => assert!(v == [2, 1, 3]),
1794 5 => assert!(v == [1, 2, 3]),
1801 fn test_permutations() {
1803 let v: [int; 0] = [];
1804 let mut it = v.permutations();
1805 let (min_size, max_opt) = it.size_hint();
1806 assert_eq!(min_size, 1);
1807 assert_eq!(max_opt.unwrap(), 1);
1808 assert_eq!(it.next(), Some(v.as_slice().to_vec()));
1809 assert_eq!(it.next(), None);
1812 let v = ["Hello".to_string()];
1813 let mut it = v.permutations();
1814 let (min_size, max_opt) = it.size_hint();
1815 assert_eq!(min_size, 1);
1816 assert_eq!(max_opt.unwrap(), 1);
1817 assert_eq!(it.next(), Some(v.as_slice().to_vec()));
1818 assert_eq!(it.next(), None);
1822 let mut it = v.permutations();
1823 let (min_size, max_opt) = it.size_hint();
1824 assert_eq!(min_size, 3*2);
1825 assert_eq!(max_opt.unwrap(), 3*2);
1826 assert_eq!(it.next(), Some(vec![1,2,3]));
1827 assert_eq!(it.next(), Some(vec![1,3,2]));
1828 assert_eq!(it.next(), Some(vec![3,1,2]));
1829 let (min_size, max_opt) = it.size_hint();
1830 assert_eq!(min_size, 3);
1831 assert_eq!(max_opt.unwrap(), 3);
1832 assert_eq!(it.next(), Some(vec![3,2,1]));
1833 assert_eq!(it.next(), Some(vec![2,3,1]));
1834 assert_eq!(it.next(), Some(vec![2,1,3]));
1835 assert_eq!(it.next(), None);
1838 // check that we have N! permutations
1839 let v = ['A', 'B', 'C', 'D', 'E', 'F'];
1841 let mut it = v.permutations();
1842 let (min_size, max_opt) = it.size_hint();
1846 assert_eq!(amt, it.swaps.swaps_made);
1847 assert_eq!(amt, min_size);
1848 assert_eq!(amt, 2 * 3 * 4 * 5 * 6);
1849 assert_eq!(amt, max_opt.unwrap());
1854 fn test_lexicographic_permutations() {
1855 let v : &mut[int] = &mut[1i, 2, 3, 4, 5];
1856 assert!(v.prev_permutation() == false);
1857 assert!(v.next_permutation());
1858 let b: &mut[int] = &mut[1, 2, 3, 5, 4];
1860 assert!(v.prev_permutation());
1861 let b: &mut[int] = &mut[1, 2, 3, 4, 5];
1863 assert!(v.next_permutation());
1864 assert!(v.next_permutation());
1865 let b: &mut[int] = &mut[1, 2, 4, 3, 5];
1867 assert!(v.next_permutation());
1868 let b: &mut[int] = &mut[1, 2, 4, 5, 3];
1871 let v : &mut[int] = &mut[1i, 0, 0, 0];
1872 assert!(v.next_permutation() == false);
1873 assert!(v.prev_permutation());
1874 let b: &mut[int] = &mut[0, 1, 0, 0];
1876 assert!(v.prev_permutation());
1877 let b: &mut[int] = &mut[0, 0, 1, 0];
1879 assert!(v.prev_permutation());
1880 let b: &mut[int] = &mut[0, 0, 0, 1];
1882 assert!(v.prev_permutation() == false);
1886 fn test_lexicographic_permutations_empty_and_short() {
1887 let empty : &mut[int] = &mut[];
1888 assert!(empty.next_permutation() == false);
1889 let b: &mut[int] = &mut[];
1890 assert!(empty == b);
1891 assert!(empty.prev_permutation() == false);
1892 assert!(empty == b);
1894 let one_elem : &mut[int] = &mut[4i];
1895 assert!(one_elem.prev_permutation() == false);
1896 let b: &mut[int] = &mut[4];
1897 assert!(one_elem == b);
1898 assert!(one_elem.next_permutation() == false);
1899 assert!(one_elem == b);
1901 let two_elem : &mut[int] = &mut[1i, 2];
1902 assert!(two_elem.prev_permutation() == false);
1903 let b : &mut[int] = &mut[1, 2];
1904 let c : &mut[int] = &mut[2, 1];
1905 assert!(two_elem == b);
1906 assert!(two_elem.next_permutation());
1907 assert!(two_elem == c);
1908 assert!(two_elem.next_permutation() == false);
1909 assert!(two_elem == c);
1910 assert!(two_elem.prev_permutation());
1911 assert!(two_elem == b);
1912 assert!(two_elem.prev_permutation() == false);
1913 assert!(two_elem == b);
1917 fn test_position_elem() {
1918 assert!([].position_elem(&1i).is_none());
1920 let v1 = vec![1i, 2, 3, 3, 2, 5];
1921 assert_eq!(v1.as_slice().position_elem(&1), Some(0u));
1922 assert_eq!(v1.as_slice().position_elem(&2), Some(1u));
1923 assert_eq!(v1.as_slice().position_elem(&5), Some(5u));
1924 assert!(v1.as_slice().position_elem(&4).is_none());
1928 fn test_binary_search() {
1929 assert_eq!([1i,2,3,4,5].binary_search(&5).ok(), Some(4));
1930 assert_eq!([1i,2,3,4,5].binary_search(&4).ok(), Some(3));
1931 assert_eq!([1i,2,3,4,5].binary_search(&3).ok(), Some(2));
1932 assert_eq!([1i,2,3,4,5].binary_search(&2).ok(), Some(1));
1933 assert_eq!([1i,2,3,4,5].binary_search(&1).ok(), Some(0));
1935 assert_eq!([2i,4,6,8,10].binary_search(&1).ok(), None);
1936 assert_eq!([2i,4,6,8,10].binary_search(&5).ok(), None);
1937 assert_eq!([2i,4,6,8,10].binary_search(&4).ok(), Some(1));
1938 assert_eq!([2i,4,6,8,10].binary_search(&10).ok(), Some(4));
1940 assert_eq!([2i,4,6,8].binary_search(&1).ok(), None);
1941 assert_eq!([2i,4,6,8].binary_search(&5).ok(), None);
1942 assert_eq!([2i,4,6,8].binary_search(&4).ok(), Some(1));
1943 assert_eq!([2i,4,6,8].binary_search(&8).ok(), Some(3));
1945 assert_eq!([2i,4,6].binary_search(&1).ok(), None);
1946 assert_eq!([2i,4,6].binary_search(&5).ok(), None);
1947 assert_eq!([2i,4,6].binary_search(&4).ok(), Some(1));
1948 assert_eq!([2i,4,6].binary_search(&6).ok(), Some(2));
1950 assert_eq!([2i,4].binary_search(&1).ok(), None);
1951 assert_eq!([2i,4].binary_search(&5).ok(), None);
1952 assert_eq!([2i,4].binary_search(&2).ok(), Some(0));
1953 assert_eq!([2i,4].binary_search(&4).ok(), Some(1));
1955 assert_eq!([2i].binary_search(&1).ok(), None);
1956 assert_eq!([2i].binary_search(&5).ok(), None);
1957 assert_eq!([2i].binary_search(&2).ok(), Some(0));
1959 assert_eq!([].binary_search(&1i).ok(), None);
1960 assert_eq!([].binary_search(&5i).ok(), None);
1962 assert!([1i,1,1,1,1].binary_search(&1).ok() != None);
1963 assert!([1i,1,1,1,2].binary_search(&1).ok() != None);
1964 assert!([1i,1,1,2,2].binary_search(&1).ok() != None);
1965 assert!([1i,1,2,2,2].binary_search(&1).ok() != None);
1966 assert_eq!([1i,2,2,2,2].binary_search(&1).ok(), Some(0));
1968 assert_eq!([1i,2,3,4,5].binary_search(&6).ok(), None);
1969 assert_eq!([1i,2,3,4,5].binary_search(&0).ok(), None);
1974 let mut v: Vec<int> = vec![10i, 20];
1975 assert_eq!(v[0], 10);
1976 assert_eq!(v[1], 20);
1978 assert_eq!(v[0], 20);
1979 assert_eq!(v[1], 10);
1981 let mut v3: Vec<int> = vec![];
1983 assert!(v3.is_empty());
1988 for len in range(4u, 25) {
1989 for _ in range(0i, 100) {
1990 let mut v = thread_rng().gen_iter::<uint>().take(len)
1991 .collect::<Vec<uint>>();
1992 let mut v1 = v.clone();
1995 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
1997 v1.sort_by(|a, b| a.cmp(b));
1998 assert!(v1.as_slice().windows(2).all(|w| w[0] <= w[1]));
2000 v1.sort_by(|a, b| b.cmp(a));
2001 assert!(v1.as_slice().windows(2).all(|w| w[0] >= w[1]));
2006 let mut v: [uint; 0] = [];
2009 let mut v = [0xDEADBEEFu];
2011 assert!(v == [0xDEADBEEF]);
2015 fn test_sort_stability() {
2016 for len in range(4i, 25) {
2017 for _ in range(0u, 10) {
2018 let mut counts = [0i; 10];
2020 // create a vector like [(6, 1), (5, 1), (6, 2), ...],
2021 // where the first item of each tuple is random, but
2022 // the second item represents which occurrence of that
2023 // number this element is, i.e. the second elements
2024 // will occur in sorted order.
2025 let mut v = range(0, len).map(|_| {
2026 let n = thread_rng().gen::<uint>() % 10;
2029 }).collect::<Vec<(uint, int)>>();
2031 // only sort on the first element, so an unstable sort
2032 // may mix up the counts.
2033 v.sort_by(|&(a,_), &(b,_)| a.cmp(&b));
2035 // this comparison includes the count (the second item
2036 // of the tuple), so elements with equal first items
2037 // will need to be ordered with increasing
2038 // counts... i.e. exactly asserting that this sort is
2040 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
2047 let v: [Vec<int>; 0] = [];
2048 let c: Vec<int> = v.concat();
2050 let d: Vec<int> = [vec![1i], vec![2i,3i]].concat();
2051 assert_eq!(d, vec![1i, 2, 3]);
2053 let v: [&[int]; 2] = [&[1], &[2, 3]];
2054 assert_eq!(v.connect(&0), vec![1i, 0, 2, 3]);
2055 let v: [&[int]; 3] = [&[1i], &[2], &[3]];
2056 assert_eq!(v.connect(&0), vec![1i, 0, 2, 0, 3]);
2061 let v: [Vec<int>; 0] = [];
2062 assert_eq!(v.connect(&0), vec![]);
2063 assert_eq!([vec![1i], vec![2i, 3]].connect(&0), vec![1, 0, 2, 3]);
2064 assert_eq!([vec![1i], vec![2i], vec![3i]].connect(&0), vec![1, 0, 2, 0, 3]);
2066 let v: [&[int]; 2] = [&[1], &[2, 3]];
2067 assert_eq!(v.connect(&0), vec![1, 0, 2, 3]);
2068 let v: [&[int]; 3] = [&[1], &[2], &[3]];
2069 assert_eq!(v.connect(&0), vec![1, 0, 2, 0, 3]);
2074 let mut a = vec![1i, 2, 4];
2076 assert_eq!(a, vec![1, 2, 3, 4]);
2078 let mut a = vec![1i, 2, 3];
2080 assert_eq!(a, vec![0, 1, 2, 3]);
2082 let mut a = vec![1i, 2, 3];
2084 assert_eq!(a, vec![1, 2, 3, 4]);
2088 assert_eq!(a, vec![1]);
2093 fn test_insert_oob() {
2094 let mut a = vec![1i, 2, 3];
2100 let mut a = vec![1i,2,3,4];
2102 assert_eq!(a.remove(2), 3);
2103 assert_eq!(a, vec![1i,2,4]);
2105 assert_eq!(a.remove(2), 4);
2106 assert_eq!(a, vec![1i,2]);
2108 assert_eq!(a.remove(0), 1);
2109 assert_eq!(a, vec![2i]);
2111 assert_eq!(a.remove(0), 2);
2112 assert_eq!(a, vec![]);
2117 fn test_remove_fail() {
2118 let mut a = vec![1i];
2119 let _ = a.remove(0);
2120 let _ = a.remove(0);
2124 fn test_capacity() {
2125 let mut v = vec![0u64];
2126 v.reserve_exact(10u);
2127 assert!(v.capacity() >= 11u);
2128 let mut v = vec![0u32];
2129 v.reserve_exact(10u);
2130 assert!(v.capacity() >= 11u);
2135 let v = vec![1i, 2, 3, 4, 5];
2136 let v = v.slice(1u, 3u);
2137 assert_eq!(v.len(), 2u);
2138 assert_eq!(v[0], 2);
2139 assert_eq!(v[1], 3);
2144 fn test_permute_fail() {
2145 let v = [(box 0i, Rc::new(0i)), (box 0i, Rc::new(0i)),
2146 (box 0i, Rc::new(0i)), (box 0i, Rc::new(0i))];
2148 for _ in v.permutations() {
2157 fn test_total_ord() {
2158 let c: &[int] = &[1, 2, 3];
2159 [1, 2, 3, 4][].cmp(c) == Greater;
2160 let c: &[int] = &[1, 2, 3, 4];
2161 [1, 2, 3][].cmp(c) == Less;
2162 let c: &[int] = &[1, 2, 3, 6];
2163 [1, 2, 3, 4][].cmp(c) == Equal;
2164 let c: &[int] = &[1, 2, 3, 4, 5, 6];
2165 [1, 2, 3, 4, 5, 5, 5, 5][].cmp(c) == Less;
2166 let c: &[int] = &[1, 2, 3, 4];
2167 [2, 2][].cmp(c) == Greater;
2171 fn test_iterator() {
2172 let xs = [1i, 2, 5, 10, 11];
2173 let mut it = xs.iter();
2174 assert_eq!(it.size_hint(), (5, Some(5)));
2175 assert_eq!(it.next().unwrap(), &1);
2176 assert_eq!(it.size_hint(), (4, Some(4)));
2177 assert_eq!(it.next().unwrap(), &2);
2178 assert_eq!(it.size_hint(), (3, Some(3)));
2179 assert_eq!(it.next().unwrap(), &5);
2180 assert_eq!(it.size_hint(), (2, Some(2)));
2181 assert_eq!(it.next().unwrap(), &10);
2182 assert_eq!(it.size_hint(), (1, Some(1)));
2183 assert_eq!(it.next().unwrap(), &11);
2184 assert_eq!(it.size_hint(), (0, Some(0)));
2185 assert!(it.next().is_none());
2189 fn test_random_access_iterator() {
2190 let xs = [1i, 2, 5, 10, 11];
2191 let mut it = xs.iter();
2193 assert_eq!(it.indexable(), 5);
2194 assert_eq!(it.idx(0).unwrap(), &1);
2195 assert_eq!(it.idx(2).unwrap(), &5);
2196 assert_eq!(it.idx(4).unwrap(), &11);
2197 assert!(it.idx(5).is_none());
2199 assert_eq!(it.next().unwrap(), &1);
2200 assert_eq!(it.indexable(), 4);
2201 assert_eq!(it.idx(0).unwrap(), &2);
2202 assert_eq!(it.idx(3).unwrap(), &11);
2203 assert!(it.idx(4).is_none());
2205 assert_eq!(it.next().unwrap(), &2);
2206 assert_eq!(it.indexable(), 3);
2207 assert_eq!(it.idx(1).unwrap(), &10);
2208 assert!(it.idx(3).is_none());
2210 assert_eq!(it.next().unwrap(), &5);
2211 assert_eq!(it.indexable(), 2);
2212 assert_eq!(it.idx(1).unwrap(), &11);
2214 assert_eq!(it.next().unwrap(), &10);
2215 assert_eq!(it.indexable(), 1);
2216 assert_eq!(it.idx(0).unwrap(), &11);
2217 assert!(it.idx(1).is_none());
2219 assert_eq!(it.next().unwrap(), &11);
2220 assert_eq!(it.indexable(), 0);
2221 assert!(it.idx(0).is_none());
2223 assert!(it.next().is_none());
2227 fn test_iter_size_hints() {
2228 let mut xs = [1i, 2, 5, 10, 11];
2229 assert_eq!(xs.iter().size_hint(), (5, Some(5)));
2230 assert_eq!(xs.iter_mut().size_hint(), (5, Some(5)));
2234 fn test_iter_clone() {
2235 let xs = [1i, 2, 5];
2236 let mut it = xs.iter();
2238 let mut jt = it.clone();
2239 assert_eq!(it.next(), jt.next());
2240 assert_eq!(it.next(), jt.next());
2241 assert_eq!(it.next(), jt.next());
2245 fn test_mut_iterator() {
2246 let mut xs = [1i, 2, 3, 4, 5];
2247 for x in xs.iter_mut() {
2250 assert!(xs == [2, 3, 4, 5, 6])
2254 fn test_rev_iterator() {
2256 let xs = [1i, 2, 5, 10, 11];
2257 let ys = [11, 10, 5, 2, 1];
2259 for &x in xs.iter().rev() {
2260 assert_eq!(x, ys[i]);
2267 fn test_mut_rev_iterator() {
2268 let mut xs = [1u, 2, 3, 4, 5];
2269 for (i,x) in xs.iter_mut().rev().enumerate() {
2272 assert!(xs == [5, 5, 5, 5, 5])
2276 fn test_move_iterator() {
2277 let xs = vec![1u,2,3,4,5];
2278 assert_eq!(xs.into_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
2282 fn test_move_rev_iterator() {
2283 let xs = vec![1u,2,3,4,5];
2284 assert_eq!(xs.into_iter().rev().fold(0, |a: uint, b: uint| 10*a + b), 54321);
2288 fn test_splitator() {
2289 let xs = &[1i,2,3,4,5];
2291 let splits: &[&[int]] = &[&[1], &[3], &[5]];
2292 assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2294 let splits: &[&[int]] = &[&[], &[2,3,4,5]];
2295 assert_eq!(xs.split(|x| *x == 1).collect::<Vec<&[int]>>(),
2297 let splits: &[&[int]] = &[&[1,2,3,4], &[]];
2298 assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[int]>>(),
2300 let splits: &[&[int]] = &[&[1,2,3,4,5]];
2301 assert_eq!(xs.split(|x| *x == 10).collect::<Vec<&[int]>>(),
2303 let splits: &[&[int]] = &[&[], &[], &[], &[], &[], &[]];
2304 assert_eq!(xs.split(|_| true).collect::<Vec<&[int]>>(),
2307 let xs: &[int] = &[];
2308 let splits: &[&[int]] = &[&[]];
2309 assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[int]>>(), splits);
2313 fn test_splitnator() {
2314 let xs = &[1i,2,3,4,5];
2316 let splits: &[&[int]] = &[&[1,2,3,4,5]];
2317 assert_eq!(xs.splitn(0, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2319 let splits: &[&[int]] = &[&[1], &[3,4,5]];
2320 assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2322 let splits: &[&[int]] = &[&[], &[], &[], &[4,5]];
2323 assert_eq!(xs.splitn(3, |_| true).collect::<Vec<&[int]>>(),
2326 let xs: &[int] = &[];
2327 let splits: &[&[int]] = &[&[]];
2328 assert_eq!(xs.splitn(1, |x| *x == 5).collect::<Vec<&[int]>>(), splits);
2332 fn test_splitnator_mut() {
2333 let xs = &mut [1i,2,3,4,5];
2335 let splits: &[&mut [int]] = &[&mut [1,2,3,4,5]];
2336 assert_eq!(xs.splitn_mut(0, |x| *x % 2 == 0).collect::<Vec<&mut [int]>>(),
2338 let splits: &[&mut [int]] = &[&mut [1], &mut [3,4,5]];
2339 assert_eq!(xs.splitn_mut(1, |x| *x % 2 == 0).collect::<Vec<&mut [int]>>(),
2341 let splits: &[&mut [int]] = &[&mut [], &mut [], &mut [], &mut [4,5]];
2342 assert_eq!(xs.splitn_mut(3, |_| true).collect::<Vec<&mut [int]>>(),
2345 let xs: &mut [int] = &mut [];
2346 let splits: &[&mut [int]] = &[&mut []];
2347 assert_eq!(xs.splitn_mut(1, |x| *x == 5).collect::<Vec<&mut [int]>>(),
2352 fn test_rsplitator() {
2353 let xs = &[1i,2,3,4,5];
2355 let splits: &[&[int]] = &[&[5], &[3], &[1]];
2356 assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<&[int]>>(),
2358 let splits: &[&[int]] = &[&[2,3,4,5], &[]];
2359 assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<&[int]>>(),
2361 let splits: &[&[int]] = &[&[], &[1,2,3,4]];
2362 assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[int]>>(),
2364 let splits: &[&[int]] = &[&[1,2,3,4,5]];
2365 assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<&[int]>>(),
2368 let xs: &[int] = &[];
2369 let splits: &[&[int]] = &[&[]];
2370 assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[int]>>(), splits);
2374 fn test_rsplitnator() {
2375 let xs = &[1,2,3,4,5];
2377 let splits: &[&[int]] = &[&[1,2,3,4,5]];
2378 assert_eq!(xs.rsplitn(0, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2380 let splits: &[&[int]] = &[&[5], &[1,2,3]];
2381 assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2383 let splits: &[&[int]] = &[&[], &[], &[], &[1,2]];
2384 assert_eq!(xs.rsplitn(3, |_| true).collect::<Vec<&[int]>>(),
2387 let xs: &[int] = &[];
2388 let splits: &[&[int]] = &[&[]];
2389 assert_eq!(xs.rsplitn(1, |x| *x == 5).collect::<Vec<&[int]>>(), splits);
2393 fn test_windowsator() {
2394 let v = &[1i,2,3,4];
2396 let wins: &[&[int]] = &[&[1,2], &[2,3], &[3,4]];
2397 assert_eq!(v.windows(2).collect::<Vec<&[int]>>(), wins);
2398 let wins: &[&[int]] = &[&[1i,2,3], &[2,3,4]];
2399 assert_eq!(v.windows(3).collect::<Vec<&[int]>>(), wins);
2400 assert!(v.windows(6).next().is_none());
2405 fn test_windowsator_0() {
2406 let v = &[1i,2,3,4];
2407 let _it = v.windows(0);
2411 fn test_chunksator() {
2412 use core::iter::ExactSizeIterator;
2414 let v = &[1i,2,3,4,5];
2416 assert_eq!(v.chunks(2).len(), 3);
2418 let chunks: &[&[int]] = &[&[1i,2], &[3,4], &[5]];
2419 assert_eq!(v.chunks(2).collect::<Vec<&[int]>>(), chunks);
2420 let chunks: &[&[int]] = &[&[1i,2,3], &[4,5]];
2421 assert_eq!(v.chunks(3).collect::<Vec<&[int]>>(), chunks);
2422 let chunks: &[&[int]] = &[&[1i,2,3,4,5]];
2423 assert_eq!(v.chunks(6).collect::<Vec<&[int]>>(), chunks);
2425 let chunks: &[&[int]] = &[&[5i], &[3,4], &[1,2]];
2426 assert_eq!(v.chunks(2).rev().collect::<Vec<&[int]>>(), chunks);
2427 let mut it = v.chunks(2);
2428 assert_eq!(it.indexable(), 3);
2429 let chunk: &[int] = &[1,2];
2430 assert_eq!(it.idx(0).unwrap(), chunk);
2431 let chunk: &[int] = &[3,4];
2432 assert_eq!(it.idx(1).unwrap(), chunk);
2433 let chunk: &[int] = &[5];
2434 assert_eq!(it.idx(2).unwrap(), chunk);
2435 assert_eq!(it.idx(3), None);
2440 fn test_chunksator_0() {
2441 let v = &[1i,2,3,4];
2442 let _it = v.chunks(0);
2446 fn test_move_from() {
2447 let mut a = [1i,2,3,4,5];
2448 let b = vec![6i,7,8];
2449 assert_eq!(a.move_from(b, 0, 3), 3);
2450 assert!(a == [6i,7,8,4,5]);
2451 let mut a = [7i,2,8,1];
2452 let b = vec![3i,1,4,1,5,9];
2453 assert_eq!(a.move_from(b, 0, 6), 4);
2454 assert!(a == [3i,1,4,1]);
2455 let mut a = [1i,2,3,4];
2456 let b = vec![5i,6,7,8,9,0];
2457 assert_eq!(a.move_from(b, 2, 3), 1);
2458 assert!(a == [7i,2,3,4]);
2459 let mut a = [1i,2,3,4,5];
2460 let b = vec![5i,6,7,8,9,0];
2461 assert_eq!(a.slice_mut(2, 4).move_from(b,1,6), 2);
2462 assert!(a == [1i,2,6,7,5]);
2466 fn test_reverse_part() {
2467 let mut values = [1i,2,3,4,5];
2468 values.slice_mut(1, 4).reverse();
2469 assert!(values == [1,4,3,2,5]);
2474 macro_rules! test_show_vec {
2475 ($x:expr, $x_str:expr) => ({
2476 let (x, x_str) = ($x, $x_str);
2477 assert_eq!(format!("{:?}", x), x_str);
2478 assert_eq!(format!("{:?}", x.as_slice()), x_str);
2481 let empty: Vec<int> = vec![];
2482 test_show_vec!(empty, "[]");
2483 test_show_vec!(vec![1i], "[1]");
2484 test_show_vec!(vec![1i, 2, 3], "[1, 2, 3]");
2485 test_show_vec!(vec![vec![], vec![1u], vec![1u, 1u]],
2486 "[[], [1], [1, 1]]");
2488 let empty_mut: &mut [int] = &mut[];
2489 test_show_vec!(empty_mut, "[]");
2490 let v: &mut[int] = &mut[1];
2491 test_show_vec!(v, "[1]");
2492 let v: &mut[int] = &mut[1, 2, 3];
2493 test_show_vec!(v, "[1, 2, 3]");
2494 let v: &mut [&mut[uint]] = &mut[&mut[], &mut[1u], &mut[1u, 1u]];
2495 test_show_vec!(v, "[[], [1], [1, 1]]");
2499 fn test_vec_default() {
2502 let v: $ty = Default::default();
2503 assert!(v.is_empty());
2512 fn test_bytes_set_memory() {
2513 use slice::bytes::MutableByteVector;
2514 let mut values = [1u8,2,3,4,5];
2515 values.slice_mut(0, 5).set_memory(0xAB);
2516 assert!(values == [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
2517 values.slice_mut(2, 4).set_memory(0xFF);
2518 assert!(values == [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
2523 fn test_overflow_does_not_cause_segfault() {
2525 v.reserve_exact(-1);
2532 fn test_overflow_does_not_cause_segfault_managed() {
2533 let mut v = vec![Rc::new(1i)];
2534 v.reserve_exact(-1);
2535 v.push(Rc::new(2i));
2539 fn test_mut_split_at() {
2540 let mut values = [1u8,2,3,4,5];
2542 let (left, right) = values.split_at_mut(2);
2544 let left: &[_] = left;
2545 assert!(left[..left.len()] == [1, 2][]);
2547 for p in left.iter_mut() {
2552 let right: &[_] = right;
2553 assert!(right[..right.len()] == [3, 4, 5][]);
2555 for p in right.iter_mut() {
2560 assert!(values == [2, 3, 5, 6, 7]);
2563 #[derive(Clone, PartialEq)]
2567 fn test_iter_zero_sized() {
2568 let mut v = vec![Foo, Foo, Foo];
2569 assert_eq!(v.len(), 3);
2578 for f in v[1..3].iter() {
2584 for f in v.iter_mut() {
2590 for f in v.into_iter() {
2594 assert_eq!(cnt, 11);
2596 let xs: [Foo; 3] = [Foo, Foo, Foo];
2598 for f in xs.iter() {
2606 fn test_shrink_to_fit() {
2607 let mut xs = vec![0, 1, 2, 3];
2608 for i in range(4i, 100) {
2611 assert_eq!(xs.capacity(), 128);
2613 assert_eq!(xs.capacity(), 100);
2614 assert_eq!(xs, range(0i, 100i).collect::<Vec<_>>());
2618 fn test_starts_with() {
2619 assert!(b"foobar".starts_with(b"foo"));
2620 assert!(!b"foobar".starts_with(b"oob"));
2621 assert!(!b"foobar".starts_with(b"bar"));
2622 assert!(!b"foo".starts_with(b"foobar"));
2623 assert!(!b"bar".starts_with(b"foobar"));
2624 assert!(b"foobar".starts_with(b"foobar"));
2625 let empty: &[u8] = &[];
2626 assert!(empty.starts_with(empty));
2627 assert!(!empty.starts_with(b"foo"));
2628 assert!(b"foobar".starts_with(empty));
2632 fn test_ends_with() {
2633 assert!(b"foobar".ends_with(b"bar"));
2634 assert!(!b"foobar".ends_with(b"oba"));
2635 assert!(!b"foobar".ends_with(b"foo"));
2636 assert!(!b"foo".ends_with(b"foobar"));
2637 assert!(!b"bar".ends_with(b"foobar"));
2638 assert!(b"foobar".ends_with(b"foobar"));
2639 let empty: &[u8] = &[];
2640 assert!(empty.ends_with(empty));
2641 assert!(!empty.ends_with(b"foo"));
2642 assert!(b"foobar".ends_with(empty));
2646 fn test_mut_splitator() {
2647 let mut xs = [0i,1,0,2,3,0,0,4,5,0];
2648 assert_eq!(xs.split_mut(|x| *x == 0).count(), 6);
2649 for slice in xs.split_mut(|x| *x == 0) {
2652 assert!(xs == [0,1,0,3,2,0,0,5,4,0]);
2654 let mut xs = [0i,1,0,2,3,0,0,4,5,0,6,7];
2655 for slice in xs.split_mut(|x| *x == 0).take(5) {
2658 assert!(xs == [0,1,0,3,2,0,0,5,4,0,6,7]);
2662 fn test_mut_splitator_rev() {
2663 let mut xs = [1i,2,0,3,4,0,0,5,6,0];
2664 for slice in xs.split_mut(|x| *x == 0).rev().take(4) {
2667 assert!(xs == [1,2,0,4,3,0,0,6,5,0]);
2672 let mut v = [0i,1,2];
2673 assert_eq!(v.get_mut(3), None);
2674 v.get_mut(1).map(|e| *e = 7);
2675 assert_eq!(v[1], 7);
2677 assert_eq!(v.get_mut(2), Some(&mut x));
2681 fn test_mut_chunks() {
2682 use core::iter::ExactSizeIterator;
2684 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
2685 assert_eq!(v.chunks_mut(2).len(), 4);
2686 for (i, chunk) in v.chunks_mut(3).enumerate() {
2687 for x in chunk.iter_mut() {
2691 let result = [0u8, 0, 0, 1, 1, 1, 2];
2692 assert!(v == result);
2696 fn test_mut_chunks_rev() {
2697 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
2698 for (i, chunk) in v.chunks_mut(3).rev().enumerate() {
2699 for x in chunk.iter_mut() {
2703 let result = [2u8, 2, 2, 1, 1, 1, 0];
2704 assert!(v == result);
2709 fn test_mut_chunks_0() {
2710 let mut v = [1i, 2, 3, 4];
2711 let _it = v.chunks_mut(0);
2715 fn test_mut_last() {
2716 let mut x = [1i, 2, 3, 4, 5];
2717 let h = x.last_mut();
2718 assert_eq!(*h.unwrap(), 5);
2720 let y: &mut [int] = &mut [];
2721 assert!(y.last_mut().is_none());
2726 let xs = box [1u, 2, 3];
2727 let ys = xs.to_vec();
2728 assert_eq!(ys, [1u, 2, 3]);
2737 use core::iter::repeat;
2738 use std::rand::{weak_rng, Rng};
2739 use test::{Bencher, black_box};
2742 fn iterator(b: &mut Bencher) {
2743 // peculiar numbers to stop LLVM from optimising the summation
2745 let v = range(0u, 100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect::<Vec<_>>();
2752 // sum == 11806, to stop dead code elimination.
2753 if sum == 0 {panic!()}
2758 fn mut_iterator(b: &mut Bencher) {
2759 let mut v = repeat(0i).take(100).collect::<Vec<_>>();
2763 for x in v.iter_mut() {
2771 fn concat(b: &mut Bencher) {
2772 let xss: Vec<Vec<uint>> =
2773 range(0, 100u).map(|i| range(0, i).collect()).collect();
2775 xss.as_slice().concat();
2780 fn connect(b: &mut Bencher) {
2781 let xss: Vec<Vec<uint>> =
2782 range(0, 100u).map(|i| range(0, i).collect()).collect();
2784 xss.as_slice().connect(&0)
2789 fn push(b: &mut Bencher) {
2790 let mut vec: Vec<uint> = vec![];
2798 fn starts_with_same_vector(b: &mut Bencher) {
2799 let vec: Vec<uint> = range(0, 100).collect();
2801 vec.as_slice().starts_with(vec.as_slice())
2806 fn starts_with_single_element(b: &mut Bencher) {
2807 let vec: Vec<uint> = vec![0];
2809 vec.as_slice().starts_with(vec.as_slice())
2814 fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
2815 let vec: Vec<uint> = range(0, 100).collect();
2816 let mut match_vec: Vec<uint> = range(0, 99).collect();
2819 vec.as_slice().starts_with(match_vec.as_slice())
2824 fn ends_with_same_vector(b: &mut Bencher) {
2825 let vec: Vec<uint> = range(0, 100).collect();
2827 vec.as_slice().ends_with(vec.as_slice())
2832 fn ends_with_single_element(b: &mut Bencher) {
2833 let vec: Vec<uint> = vec![0];
2835 vec.as_slice().ends_with(vec.as_slice())
2840 fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
2841 let vec: Vec<uint> = range(0, 100).collect();
2842 let mut match_vec: Vec<uint> = range(0, 100).collect();
2843 match_vec.as_mut_slice()[0] = 200;
2845 vec.as_slice().starts_with(match_vec.as_slice())
2850 fn contains_last_element(b: &mut Bencher) {
2851 let vec: Vec<uint> = range(0, 100).collect();
2858 fn zero_1kb_from_elem(b: &mut Bencher) {
2860 repeat(0u8).take(1024).collect::<Vec<_>>()
2865 fn zero_1kb_set_memory(b: &mut Bencher) {
2867 let mut v: Vec<uint> = Vec::with_capacity(1024);
2869 let vp = v.as_mut_ptr();
2870 ptr::set_memory(vp, 0, 1024);
2878 fn zero_1kb_loop_set(b: &mut Bencher) {
2880 let mut v: Vec<uint> = Vec::with_capacity(1024);
2884 for i in range(0u, 1024) {
2891 fn zero_1kb_mut_iter(b: &mut Bencher) {
2893 let mut v = Vec::with_capacity(1024);
2897 for x in v.iter_mut() {
2905 fn random_inserts(b: &mut Bencher) {
2906 let mut rng = weak_rng();
2908 let mut v = repeat((0u, 0u)).take(30).collect::<Vec<_>>();
2909 for _ in range(0u, 100) {
2911 v.insert(rng.gen::<uint>() % (l + 1),
2917 fn random_removes(b: &mut Bencher) {
2918 let mut rng = weak_rng();
2920 let mut v = repeat((0u, 0u)).take(130).collect::<Vec<_>>();
2921 for _ in range(0u, 100) {
2923 v.remove(rng.gen::<uint>() % l);
2929 fn sort_random_small(b: &mut Bencher) {
2930 let mut rng = weak_rng();
2932 let mut v = rng.gen_iter::<u64>().take(5).collect::<Vec<u64>>();
2933 v.as_mut_slice().sort();
2935 b.bytes = 5 * mem::size_of::<u64>() as u64;
2939 fn sort_random_medium(b: &mut Bencher) {
2940 let mut rng = weak_rng();
2942 let mut v = rng.gen_iter::<u64>().take(100).collect::<Vec<u64>>();
2943 v.as_mut_slice().sort();
2945 b.bytes = 100 * mem::size_of::<u64>() as u64;
2949 fn sort_random_large(b: &mut Bencher) {
2950 let mut rng = weak_rng();
2952 let mut v = rng.gen_iter::<u64>().take(10000).collect::<Vec<u64>>();
2953 v.as_mut_slice().sort();
2955 b.bytes = 10000 * mem::size_of::<u64>() as u64;
2959 fn sort_sorted(b: &mut Bencher) {
2960 let mut v = range(0u, 10000).collect::<Vec<_>>();
2964 b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
2967 type BigSortable = (u64,u64,u64,u64);
2970 fn sort_big_random_small(b: &mut Bencher) {
2971 let mut rng = weak_rng();
2973 let mut v = rng.gen_iter::<BigSortable>().take(5)
2974 .collect::<Vec<BigSortable>>();
2977 b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
2981 fn sort_big_random_medium(b: &mut Bencher) {
2982 let mut rng = weak_rng();
2984 let mut v = rng.gen_iter::<BigSortable>().take(100)
2985 .collect::<Vec<BigSortable>>();
2988 b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
2992 fn sort_big_random_large(b: &mut Bencher) {
2993 let mut rng = weak_rng();
2995 let mut v = rng.gen_iter::<BigSortable>().take(10000)
2996 .collect::<Vec<BigSortable>>();
2999 b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
3003 fn sort_big_sorted(b: &mut Bencher) {
3004 let mut v = range(0, 10000u).map(|i| (i, i, i, i)).collect::<Vec<_>>();
3008 b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;