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`.
1000 /// let v = vec!["hello", "world"];
1002 /// let s: String = v.concat();
1004 /// println!("{}", s); // prints "helloworld"
1007 fn concat(&self) -> U;
1009 /// Flattens a slice of `T` into a single value `U`, placing a given separator between each.
1014 /// let v = vec!["hello", "world"];
1016 /// let s: String = v.connect(" ");
1018 /// println!("{}", s); // prints "hello world"
1021 fn connect(&self, sep: &T) -> U;
1024 impl<T: Clone, V: AsSlice<T>> SliceConcatExt<T, Vec<T>> for [V] {
1025 fn concat(&self) -> Vec<T> {
1026 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
1027 let mut result = Vec::with_capacity(size);
1028 for v in self.iter() {
1029 result.push_all(v.as_slice())
1034 fn connect(&self, sep: &T) -> Vec<T> {
1035 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
1036 let mut result = Vec::with_capacity(size + self.len());
1037 let mut first = true;
1038 for v in self.iter() {
1039 if first { first = false } else { result.push(sep.clone()) }
1040 result.push_all(v.as_slice())
1046 /// An iterator that yields the element swaps needed to produce
1047 /// a sequence of all possible permutations for an indexed sequence of
1048 /// elements. Each permutation is only a single swap apart.
1050 /// The Steinhaus-Johnson-Trotter algorithm is used.
1052 /// Generates even and odd permutations alternately.
1054 /// The last generated swap is always (0, 1), and it returns the
1055 /// sequence to its initial order.
1058 pub struct ElementSwaps {
1059 sdir: Vec<SizeDirection>,
1060 /// If `true`, emit the last swap that returns the sequence to initial
1067 /// Creates an `ElementSwaps` iterator for a sequence of `length` elements.
1069 pub fn new(length: uint) -> ElementSwaps {
1070 // Initialize `sdir` with a direction that position should move in
1071 // (all negative at the beginning) and the `size` of the
1072 // element (equal to the original index).
1075 sdir: range(0, length).map(|i| SizeDirection{ size: i, dir: Neg }).collect(),
1081 ////////////////////////////////////////////////////////////////////////////////
1082 // Standard trait implementations for slices
1083 ////////////////////////////////////////////////////////////////////////////////
1085 #[unstable = "trait is unstable"]
1086 impl<T> BorrowFrom<Vec<T>> for [T] {
1087 fn borrow_from(owned: &Vec<T>) -> &[T] { &owned[] }
1090 #[unstable = "trait is unstable"]
1091 impl<T> BorrowFromMut<Vec<T>> for [T] {
1092 fn borrow_from_mut(owned: &mut Vec<T>) -> &mut [T] { &mut owned[] }
1095 #[unstable = "trait is unstable"]
1096 impl<T: Clone> ToOwned<Vec<T>> for [T] {
1097 fn to_owned(&self) -> Vec<T> { self.to_vec() }
1100 ////////////////////////////////////////////////////////////////////////////////
1102 ////////////////////////////////////////////////////////////////////////////////
1104 #[derive(Copy, Clone)]
1105 enum Direction { Pos, Neg }
1107 /// An `Index` and `Direction` together.
1108 #[derive(Copy, Clone)]
1109 struct SizeDirection {
1115 impl Iterator for ElementSwaps {
1116 type Item = (uint, uint);
1119 fn next(&mut self) -> Option<(uint, uint)> {
1120 fn new_pos(i: uint, s: Direction) -> uint {
1121 i + match s { Pos => 1, Neg => -1 }
1124 // Find the index of the largest mobile element:
1125 // The direction should point into the vector, and the
1126 // swap should be with a smaller `size` element.
1127 let max = self.sdir.iter().map(|&x| x).enumerate()
1129 new_pos(i, sd.dir) < self.sdir.len() &&
1130 self.sdir[new_pos(i, sd.dir)].size < sd.size)
1131 .max_by(|&(_, sd)| sd.size);
1134 let j = new_pos(i, sd.dir);
1135 self.sdir.swap(i, j);
1137 // Swap the direction of each larger SizeDirection
1138 for x in self.sdir.iter_mut() {
1139 if x.size > sd.size {
1140 x.dir = match x.dir { Pos => Neg, Neg => Pos };
1143 self.swaps_made += 1;
1146 None => if self.emit_reset {
1147 self.emit_reset = false;
1148 if self.sdir.len() > 1 {
1150 self.swaps_made += 1;
1153 // Vector is of the form [] or [x], and the only permutation is itself
1154 self.swaps_made += 1;
1162 fn size_hint(&self) -> (uint, Option<uint>) {
1163 // For a vector of size n, there are exactly n! permutations.
1164 let n = range(2, self.sdir.len() + 1).product();
1165 (n - self.swaps_made, Some(n - self.swaps_made))
1169 /// An iterator that uses `ElementSwaps` to iterate through
1170 /// all possible permutations of a vector.
1172 /// The first iteration yields a clone of the vector as it is,
1173 /// then each successive element is the vector with one
1176 /// Generates even and odd permutations alternately.
1178 pub struct Permutations<T> {
1179 swaps: ElementSwaps,
1183 #[unstable = "trait is unstable"]
1184 impl<T: Clone> Iterator for Permutations<T> {
1188 fn next(&mut self) -> Option<Vec<T>> {
1189 match self.swaps.next() {
1191 Some((0,0)) => Some(self.v.clone()),
1193 let elt = self.v.clone();
1201 fn size_hint(&self) -> (uint, Option<uint>) {
1202 self.swaps.size_hint()
1206 ////////////////////////////////////////////////////////////////////////////////
1208 ////////////////////////////////////////////////////////////////////////////////
1210 fn insertion_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering {
1211 let len = v.len() as int;
1212 let buf_v = v.as_mut_ptr();
1215 for i in range(1, len) {
1216 // j satisfies: 0 <= j <= i;
1219 // `i` is in bounds.
1220 let read_ptr = buf_v.offset(i) as *const T;
1222 // find where to insert, we need to do strict <,
1223 // rather than <=, to maintain stability.
1225 // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
1227 compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less {
1231 // shift everything to the right, to make space to
1232 // insert this value.
1234 // j + 1 could be `len` (for the last `i`), but in
1235 // that case, `i == j` so we don't copy. The
1236 // `.offset(j)` is always in bounds.
1239 let tmp = ptr::read(read_ptr);
1240 ptr::copy_memory(buf_v.offset(j + 1),
1243 ptr::copy_nonoverlapping_memory(buf_v.offset(j),
1252 fn merge_sort<T, F>(v: &mut [T], mut compare: F) where F: FnMut(&T, &T) -> Ordering {
1253 // warning: this wildly uses unsafe.
1254 static BASE_INSERTION: uint = 32;
1255 static LARGE_INSERTION: uint = 16;
1257 // FIXME #12092: smaller insertion runs seems to make sorting
1258 // vectors of large elements a little faster on some platforms,
1259 // but hasn't been tested/tuned extensively
1260 let insertion = if size_of::<T>() <= 16 {
1268 // short vectors get sorted in-place via insertion sort to avoid allocations
1269 if len <= insertion {
1270 insertion_sort(v, compare);
1274 // allocate some memory to use as scratch memory, we keep the
1275 // length 0 so we can keep shallow copies of the contents of `v`
1276 // without risking the dtors running on an object twice if
1277 // `compare` panics.
1278 let mut working_space = Vec::with_capacity(2 * len);
1279 // these both are buffers of length `len`.
1280 let mut buf_dat = working_space.as_mut_ptr();
1281 let mut buf_tmp = unsafe {buf_dat.offset(len as int)};
1284 let buf_v = v.as_ptr();
1286 // step 1. sort short runs with insertion sort. This takes the
1287 // values from `v` and sorts them into `buf_dat`, leaving that
1288 // with sorted runs of length INSERTION.
1290 // We could hardcode the sorting comparisons here, and we could
1291 // manipulate/step the pointers themselves, rather than repeatedly
1293 for start in range_step(0, len, insertion) {
1294 // start <= i < len;
1295 for i in range(start, cmp::min(start + insertion, len)) {
1296 // j satisfies: start <= j <= i;
1297 let mut j = i as int;
1299 // `i` is in bounds.
1300 let read_ptr = buf_v.offset(i as int);
1302 // find where to insert, we need to do strict <,
1303 // rather than <=, to maintain stability.
1305 // start <= j - 1 < len, so .offset(j - 1) is in
1307 while j > start as int &&
1308 compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less {
1312 // shift everything to the right, to make space to
1313 // insert this value.
1315 // j + 1 could be `len` (for the last `i`), but in
1316 // that case, `i == j` so we don't copy. The
1317 // `.offset(j)` is always in bounds.
1318 ptr::copy_memory(buf_dat.offset(j + 1),
1319 &*buf_dat.offset(j),
1321 ptr::copy_nonoverlapping_memory(buf_dat.offset(j), read_ptr, 1);
1326 // step 2. merge the sorted runs.
1327 let mut width = insertion;
1329 // merge the sorted runs of length `width` in `buf_dat` two at
1330 // a time, placing the result in `buf_tmp`.
1332 // 0 <= start <= len.
1333 for start in range_step(0, len, 2 * width) {
1334 // manipulate pointers directly for speed (rather than
1335 // using a `for` loop with `range` and `.offset` inside
1338 // the end of the first run & start of the
1339 // second. Offset of `len` is defined, since this is
1340 // precisely one byte past the end of the object.
1341 let right_start = buf_dat.offset(cmp::min(start + width, len) as int);
1342 // end of the second. Similar reasoning to the above re safety.
1343 let right_end_idx = cmp::min(start + 2 * width, len);
1344 let right_end = buf_dat.offset(right_end_idx as int);
1346 // the pointers to the elements under consideration
1347 // from the two runs.
1349 // both of these are in bounds.
1350 let mut left = buf_dat.offset(start as int);
1351 let mut right = right_start;
1353 // where we're putting the results, it is a run of
1354 // length `2*width`, so we step it once for each step
1355 // of either `left` or `right`. `buf_tmp` has length
1356 // `len`, so these are in bounds.
1357 let mut out = buf_tmp.offset(start as int);
1358 let out_end = buf_tmp.offset(right_end_idx as int);
1360 while out < out_end {
1361 // Either the left or the right run are exhausted,
1362 // so just copy the remainder from the other run
1363 // and move on; this gives a huge speed-up (order
1364 // of 25%) for mostly sorted vectors (the best
1366 if left == right_start {
1367 // the number remaining in this run.
1368 let elems = (right_end as uint - right as uint) / mem::size_of::<T>();
1369 ptr::copy_nonoverlapping_memory(out, &*right, elems);
1371 } else if right == right_end {
1372 let elems = (right_start as uint - left as uint) / mem::size_of::<T>();
1373 ptr::copy_nonoverlapping_memory(out, &*left, elems);
1377 // check which side is smaller, and that's the
1378 // next element for the new run.
1380 // `left < right_start` and `right < right_end`,
1381 // so these are valid.
1382 let to_copy = if compare(&*left, &*right) == Greater {
1387 ptr::copy_nonoverlapping_memory(out, &*to_copy, 1);
1393 mem::swap(&mut buf_dat, &mut buf_tmp);
1398 // write the result to `v` in one go, so that there are never two copies
1399 // of the same object in `v`.
1401 ptr::copy_nonoverlapping_memory(v.as_mut_ptr(), &*buf_dat, len);
1404 // increment the pointer, returning the old pointer.
1406 unsafe fn step<T>(ptr: &mut *mut T) -> *mut T {
1408 *ptr = ptr.offset(1);
1415 use core::cmp::Ordering::{Greater, Less, Equal};
1416 use core::prelude::{Some, None, range, Clone};
1417 use core::prelude::{Iterator, IteratorExt};
1418 use core::prelude::{AsSlice};
1419 use core::prelude::{Ord, FullRange};
1420 use core::default::Default;
1422 use std::iter::RandomAccessIterator;
1423 use std::rand::{Rng, thread_rng};
1425 use string::ToString;
1427 use super::{ElementSwaps, SliceConcatExt, SliceExt};
1429 fn square(n: uint) -> uint { n * n }
1431 fn is_odd(n: &uint) -> bool { *n % 2u == 1u }
1435 // Test on-stack from_fn.
1436 let mut v = range(0, 3).map(square).collect::<Vec<_>>();
1438 let v = v.as_slice();
1439 assert_eq!(v.len(), 3u);
1440 assert_eq!(v[0], 0u);
1441 assert_eq!(v[1], 1u);
1442 assert_eq!(v[2], 4u);
1445 // Test on-heap from_fn.
1446 v = range(0, 5).map(square).collect::<Vec<_>>();
1448 let v = v.as_slice();
1449 assert_eq!(v.len(), 5u);
1450 assert_eq!(v[0], 0u);
1451 assert_eq!(v[1], 1u);
1452 assert_eq!(v[2], 4u);
1453 assert_eq!(v[3], 9u);
1454 assert_eq!(v[4], 16u);
1459 fn test_from_elem() {
1460 // Test on-stack from_elem.
1461 let mut v = vec![10u, 10u];
1463 let v = v.as_slice();
1464 assert_eq!(v.len(), 2u);
1465 assert_eq!(v[0], 10u);
1466 assert_eq!(v[1], 10u);
1469 // Test on-heap from_elem.
1470 v = vec![20u, 20u, 20u, 20u, 20u, 20u];
1472 let v = v.as_slice();
1473 assert_eq!(v[0], 20u);
1474 assert_eq!(v[1], 20u);
1475 assert_eq!(v[2], 20u);
1476 assert_eq!(v[3], 20u);
1477 assert_eq!(v[4], 20u);
1478 assert_eq!(v[5], 20u);
1483 fn test_is_empty() {
1484 let xs: [int; 0] = [];
1485 assert!(xs.is_empty());
1486 assert!(![0i].is_empty());
1490 fn test_len_divzero() {
1492 let v0 : &[Z] = &[];
1493 let v1 : &[Z] = &[[]];
1494 let v2 : &[Z] = &[[], []];
1495 assert_eq!(mem::size_of::<Z>(), 0);
1496 assert_eq!(v0.len(), 0);
1497 assert_eq!(v1.len(), 1);
1498 assert_eq!(v2.len(), 2);
1503 let mut a = vec![11i];
1504 assert_eq!(a.as_slice().get(1), None);
1506 assert_eq!(a.as_slice().get(1).unwrap(), &12);
1507 a = vec![11i, 12, 13];
1508 assert_eq!(a.as_slice().get(1).unwrap(), &12);
1514 assert_eq!(a.as_slice().first(), None);
1516 assert_eq!(a.as_slice().first().unwrap(), &11);
1518 assert_eq!(a.as_slice().first().unwrap(), &11);
1522 fn test_first_mut() {
1524 assert_eq!(a.first_mut(), None);
1526 assert_eq!(*a.first_mut().unwrap(), 11);
1528 assert_eq!(*a.first_mut().unwrap(), 11);
1533 let mut a = vec![11i];
1534 let b: &[int] = &[];
1535 assert_eq!(a.tail(), b);
1537 let b: &[int] = &[12];
1538 assert_eq!(a.tail(), b);
1542 fn test_tail_mut() {
1543 let mut a = vec![11i];
1544 let b: &mut [int] = &mut [];
1545 assert!(a.tail_mut() == b);
1547 let b: &mut [int] = &mut [12];
1548 assert!(a.tail_mut() == b);
1553 fn test_tail_empty() {
1554 let a: Vec<int> = vec![];
1560 fn test_tail_mut_empty() {
1561 let mut a: Vec<int> = vec![];
1567 let mut a = vec![11i];
1568 let b: &[int] = &[];
1569 assert_eq!(a.init(), b);
1571 let b: &[int] = &[11];
1572 assert_eq!(a.init(), b);
1576 fn test_init_mut() {
1577 let mut a = vec![11i];
1578 let b: &mut [int] = &mut [];
1579 assert!(a.init_mut() == b);
1581 let b: &mut [int] = &mut [11];
1582 assert!(a.init_mut() == b);
1587 fn test_init_empty() {
1588 let a: Vec<int> = vec![];
1594 fn test_init_mut_empty() {
1595 let mut a: Vec<int> = vec![];
1602 assert_eq!(a.as_slice().last(), None);
1604 assert_eq!(a.as_slice().last().unwrap(), &11);
1606 assert_eq!(a.as_slice().last().unwrap(), &12);
1610 fn test_last_mut() {
1612 assert_eq!(a.last_mut(), None);
1614 assert_eq!(*a.last_mut().unwrap(), 11);
1616 assert_eq!(*a.last_mut().unwrap(), 12);
1621 // Test fixed length vector.
1622 let vec_fixed = [1i, 2, 3, 4];
1623 let v_a = vec_fixed[1u..vec_fixed.len()].to_vec();
1624 assert_eq!(v_a.len(), 3u);
1625 let v_a = v_a.as_slice();
1626 assert_eq!(v_a[0], 2);
1627 assert_eq!(v_a[1], 3);
1628 assert_eq!(v_a[2], 4);
1631 let vec_stack: &[_] = &[1i, 2, 3];
1632 let v_b = vec_stack[1u..3u].to_vec();
1633 assert_eq!(v_b.len(), 2u);
1634 let v_b = v_b.as_slice();
1635 assert_eq!(v_b[0], 2);
1636 assert_eq!(v_b[1], 3);
1639 let vec_unique = vec![1i, 2, 3, 4, 5, 6];
1640 let v_d = vec_unique[1u..6u].to_vec();
1641 assert_eq!(v_d.len(), 5u);
1642 let v_d = v_d.as_slice();
1643 assert_eq!(v_d[0], 2);
1644 assert_eq!(v_d[1], 3);
1645 assert_eq!(v_d[2], 4);
1646 assert_eq!(v_d[3], 5);
1647 assert_eq!(v_d[4], 6);
1651 fn test_slice_from() {
1652 let vec: &[int] = &[1, 2, 3, 4];
1653 assert_eq!(&vec[], vec);
1654 let b: &[int] = &[3, 4];
1655 assert_eq!(&vec[2..], b);
1656 let b: &[int] = &[];
1657 assert_eq!(&vec[4..], b);
1661 fn test_slice_to() {
1662 let vec: &[int] = &[1, 2, 3, 4];
1663 assert_eq!(&vec[..4], vec);
1664 let b: &[int] = &[1, 2];
1665 assert_eq!(&vec[..2], b);
1666 let b: &[int] = &[];
1667 assert_eq!(&vec[..0], b);
1673 let mut v = vec![5i];
1675 assert_eq!(v.len(), 0);
1676 assert_eq!(e, Some(5));
1678 assert_eq!(f, None);
1680 assert_eq!(g, None);
1684 fn test_swap_remove() {
1685 let mut v = vec![1i, 2, 3, 4, 5];
1686 let mut e = v.swap_remove(0);
1688 assert_eq!(v, vec![5i, 2, 3, 4]);
1689 e = v.swap_remove(3);
1691 assert_eq!(v, vec![5i, 2, 3]);
1696 fn test_swap_remove_fail() {
1697 let mut v = vec![1i];
1698 let _ = v.swap_remove(0);
1699 let _ = v.swap_remove(0);
1703 fn test_swap_remove_noncopyable() {
1704 // Tests that we don't accidentally run destructors twice.
1705 let mut v = Vec::new();
1709 let mut _e = v.swap_remove(0);
1710 assert_eq!(v.len(), 2);
1711 _e = v.swap_remove(1);
1712 assert_eq!(v.len(), 1);
1713 _e = v.swap_remove(0);
1714 assert_eq!(v.len(), 0);
1719 // Test on-stack push().
1722 assert_eq!(v.len(), 1u);
1723 assert_eq!(v.as_slice()[0], 1);
1725 // Test on-heap push().
1727 assert_eq!(v.len(), 2u);
1728 assert_eq!(v.as_slice()[0], 1);
1729 assert_eq!(v.as_slice()[1], 2);
1733 fn test_truncate() {
1734 let mut v = vec![box 6i,box 5,box 4];
1736 let v = v.as_slice();
1737 assert_eq!(v.len(), 1);
1738 assert_eq!(*(v[0]), 6);
1739 // If the unsafe block didn't drop things properly, we blow up here.
1744 let mut v = vec![box 6i,box 5,box 4];
1746 assert_eq!(v.len(), 0);
1747 // If the unsafe block didn't drop things properly, we blow up here.
1752 fn case(a: Vec<uint>, b: Vec<uint>) {
1757 case(vec![], vec![]);
1758 case(vec![1u], vec![1]);
1759 case(vec![1u,1], vec![1]);
1760 case(vec![1u,2,3], vec![1,2,3]);
1761 case(vec![1u,1,2,3], vec![1,2,3]);
1762 case(vec![1u,2,2,3], vec![1,2,3]);
1763 case(vec![1u,2,3,3], vec![1,2,3]);
1764 case(vec![1u,1,2,2,2,3,3], vec![1,2,3]);
1768 fn test_dedup_unique() {
1769 let mut v0 = vec![box 1i, box 1, box 2, box 3];
1771 let mut v1 = vec![box 1i, box 2, box 2, box 3];
1773 let mut v2 = vec![box 1i, box 2, box 3, box 3];
1776 * If the boxed pointers were leaked or otherwise misused, valgrind
1777 * and/or rt should raise errors.
1782 fn test_dedup_shared() {
1783 let mut v0 = vec![box 1i, box 1, box 2, box 3];
1785 let mut v1 = vec![box 1i, box 2, box 2, box 3];
1787 let mut v2 = vec![box 1i, box 2, box 3, box 3];
1790 * If the pointers were leaked or otherwise misused, valgrind and/or
1791 * rt should raise errors.
1797 let mut v = vec![1u, 2, 3, 4, 5];
1799 assert_eq!(v, vec![1u, 3, 5]);
1803 fn test_element_swaps() {
1804 let mut v = [1i, 2, 3];
1805 for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
1808 0 => assert!(v == [1, 3, 2]),
1809 1 => assert!(v == [3, 1, 2]),
1810 2 => assert!(v == [3, 2, 1]),
1811 3 => assert!(v == [2, 3, 1]),
1812 4 => assert!(v == [2, 1, 3]),
1813 5 => assert!(v == [1, 2, 3]),
1820 fn test_permutations() {
1822 let v: [int; 0] = [];
1823 let mut it = v.permutations();
1824 let (min_size, max_opt) = it.size_hint();
1825 assert_eq!(min_size, 1);
1826 assert_eq!(max_opt.unwrap(), 1);
1827 assert_eq!(it.next(), Some(v.as_slice().to_vec()));
1828 assert_eq!(it.next(), None);
1831 let v = ["Hello".to_string()];
1832 let mut it = v.permutations();
1833 let (min_size, max_opt) = it.size_hint();
1834 assert_eq!(min_size, 1);
1835 assert_eq!(max_opt.unwrap(), 1);
1836 assert_eq!(it.next(), Some(v.as_slice().to_vec()));
1837 assert_eq!(it.next(), None);
1841 let mut it = v.permutations();
1842 let (min_size, max_opt) = it.size_hint();
1843 assert_eq!(min_size, 3*2);
1844 assert_eq!(max_opt.unwrap(), 3*2);
1845 assert_eq!(it.next(), Some(vec![1,2,3]));
1846 assert_eq!(it.next(), Some(vec![1,3,2]));
1847 assert_eq!(it.next(), Some(vec![3,1,2]));
1848 let (min_size, max_opt) = it.size_hint();
1849 assert_eq!(min_size, 3);
1850 assert_eq!(max_opt.unwrap(), 3);
1851 assert_eq!(it.next(), Some(vec![3,2,1]));
1852 assert_eq!(it.next(), Some(vec![2,3,1]));
1853 assert_eq!(it.next(), Some(vec![2,1,3]));
1854 assert_eq!(it.next(), None);
1857 // check that we have N! permutations
1858 let v = ['A', 'B', 'C', 'D', 'E', 'F'];
1860 let mut it = v.permutations();
1861 let (min_size, max_opt) = it.size_hint();
1865 assert_eq!(amt, it.swaps.swaps_made);
1866 assert_eq!(amt, min_size);
1867 assert_eq!(amt, 2 * 3 * 4 * 5 * 6);
1868 assert_eq!(amt, max_opt.unwrap());
1873 fn test_lexicographic_permutations() {
1874 let v : &mut[int] = &mut[1i, 2, 3, 4, 5];
1875 assert!(v.prev_permutation() == false);
1876 assert!(v.next_permutation());
1877 let b: &mut[int] = &mut[1, 2, 3, 5, 4];
1879 assert!(v.prev_permutation());
1880 let b: &mut[int] = &mut[1, 2, 3, 4, 5];
1882 assert!(v.next_permutation());
1883 assert!(v.next_permutation());
1884 let b: &mut[int] = &mut[1, 2, 4, 3, 5];
1886 assert!(v.next_permutation());
1887 let b: &mut[int] = &mut[1, 2, 4, 5, 3];
1890 let v : &mut[int] = &mut[1i, 0, 0, 0];
1891 assert!(v.next_permutation() == false);
1892 assert!(v.prev_permutation());
1893 let b: &mut[int] = &mut[0, 1, 0, 0];
1895 assert!(v.prev_permutation());
1896 let b: &mut[int] = &mut[0, 0, 1, 0];
1898 assert!(v.prev_permutation());
1899 let b: &mut[int] = &mut[0, 0, 0, 1];
1901 assert!(v.prev_permutation() == false);
1905 fn test_lexicographic_permutations_empty_and_short() {
1906 let empty : &mut[int] = &mut[];
1907 assert!(empty.next_permutation() == false);
1908 let b: &mut[int] = &mut[];
1909 assert!(empty == b);
1910 assert!(empty.prev_permutation() == false);
1911 assert!(empty == b);
1913 let one_elem : &mut[int] = &mut[4i];
1914 assert!(one_elem.prev_permutation() == false);
1915 let b: &mut[int] = &mut[4];
1916 assert!(one_elem == b);
1917 assert!(one_elem.next_permutation() == false);
1918 assert!(one_elem == b);
1920 let two_elem : &mut[int] = &mut[1i, 2];
1921 assert!(two_elem.prev_permutation() == false);
1922 let b : &mut[int] = &mut[1, 2];
1923 let c : &mut[int] = &mut[2, 1];
1924 assert!(two_elem == b);
1925 assert!(two_elem.next_permutation());
1926 assert!(two_elem == c);
1927 assert!(two_elem.next_permutation() == false);
1928 assert!(two_elem == c);
1929 assert!(two_elem.prev_permutation());
1930 assert!(two_elem == b);
1931 assert!(two_elem.prev_permutation() == false);
1932 assert!(two_elem == b);
1936 fn test_position_elem() {
1937 assert!([].position_elem(&1i).is_none());
1939 let v1 = vec![1i, 2, 3, 3, 2, 5];
1940 assert_eq!(v1.as_slice().position_elem(&1), Some(0u));
1941 assert_eq!(v1.as_slice().position_elem(&2), Some(1u));
1942 assert_eq!(v1.as_slice().position_elem(&5), Some(5u));
1943 assert!(v1.as_slice().position_elem(&4).is_none());
1947 fn test_binary_search() {
1948 assert_eq!([1i,2,3,4,5].binary_search(&5).ok(), Some(4));
1949 assert_eq!([1i,2,3,4,5].binary_search(&4).ok(), Some(3));
1950 assert_eq!([1i,2,3,4,5].binary_search(&3).ok(), Some(2));
1951 assert_eq!([1i,2,3,4,5].binary_search(&2).ok(), Some(1));
1952 assert_eq!([1i,2,3,4,5].binary_search(&1).ok(), Some(0));
1954 assert_eq!([2i,4,6,8,10].binary_search(&1).ok(), None);
1955 assert_eq!([2i,4,6,8,10].binary_search(&5).ok(), None);
1956 assert_eq!([2i,4,6,8,10].binary_search(&4).ok(), Some(1));
1957 assert_eq!([2i,4,6,8,10].binary_search(&10).ok(), Some(4));
1959 assert_eq!([2i,4,6,8].binary_search(&1).ok(), None);
1960 assert_eq!([2i,4,6,8].binary_search(&5).ok(), None);
1961 assert_eq!([2i,4,6,8].binary_search(&4).ok(), Some(1));
1962 assert_eq!([2i,4,6,8].binary_search(&8).ok(), Some(3));
1964 assert_eq!([2i,4,6].binary_search(&1).ok(), None);
1965 assert_eq!([2i,4,6].binary_search(&5).ok(), None);
1966 assert_eq!([2i,4,6].binary_search(&4).ok(), Some(1));
1967 assert_eq!([2i,4,6].binary_search(&6).ok(), Some(2));
1969 assert_eq!([2i,4].binary_search(&1).ok(), None);
1970 assert_eq!([2i,4].binary_search(&5).ok(), None);
1971 assert_eq!([2i,4].binary_search(&2).ok(), Some(0));
1972 assert_eq!([2i,4].binary_search(&4).ok(), Some(1));
1974 assert_eq!([2i].binary_search(&1).ok(), None);
1975 assert_eq!([2i].binary_search(&5).ok(), None);
1976 assert_eq!([2i].binary_search(&2).ok(), Some(0));
1978 assert_eq!([].binary_search(&1i).ok(), None);
1979 assert_eq!([].binary_search(&5i).ok(), None);
1981 assert!([1i,1,1,1,1].binary_search(&1).ok() != None);
1982 assert!([1i,1,1,1,2].binary_search(&1).ok() != None);
1983 assert!([1i,1,1,2,2].binary_search(&1).ok() != None);
1984 assert!([1i,1,2,2,2].binary_search(&1).ok() != None);
1985 assert_eq!([1i,2,2,2,2].binary_search(&1).ok(), Some(0));
1987 assert_eq!([1i,2,3,4,5].binary_search(&6).ok(), None);
1988 assert_eq!([1i,2,3,4,5].binary_search(&0).ok(), None);
1993 let mut v: Vec<int> = vec![10i, 20];
1994 assert_eq!(v[0], 10);
1995 assert_eq!(v[1], 20);
1997 assert_eq!(v[0], 20);
1998 assert_eq!(v[1], 10);
2000 let mut v3: Vec<int> = vec![];
2002 assert!(v3.is_empty());
2007 for len in range(4u, 25) {
2008 for _ in range(0i, 100) {
2009 let mut v = thread_rng().gen_iter::<uint>().take(len)
2010 .collect::<Vec<uint>>();
2011 let mut v1 = v.clone();
2014 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
2016 v1.sort_by(|a, b| a.cmp(b));
2017 assert!(v1.as_slice().windows(2).all(|w| w[0] <= w[1]));
2019 v1.sort_by(|a, b| b.cmp(a));
2020 assert!(v1.as_slice().windows(2).all(|w| w[0] >= w[1]));
2025 let mut v: [uint; 0] = [];
2028 let mut v = [0xDEADBEEFu];
2030 assert!(v == [0xDEADBEEF]);
2034 fn test_sort_stability() {
2035 for len in range(4i, 25) {
2036 for _ in range(0u, 10) {
2037 let mut counts = [0i; 10];
2039 // create a vector like [(6, 1), (5, 1), (6, 2), ...],
2040 // where the first item of each tuple is random, but
2041 // the second item represents which occurrence of that
2042 // number this element is, i.e. the second elements
2043 // will occur in sorted order.
2044 let mut v = range(0, len).map(|_| {
2045 let n = thread_rng().gen::<uint>() % 10;
2048 }).collect::<Vec<(uint, int)>>();
2050 // only sort on the first element, so an unstable sort
2051 // may mix up the counts.
2052 v.sort_by(|&(a,_), &(b,_)| a.cmp(&b));
2054 // this comparison includes the count (the second item
2055 // of the tuple), so elements with equal first items
2056 // will need to be ordered with increasing
2057 // counts... i.e. exactly asserting that this sort is
2059 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
2066 let v: [Vec<int>; 0] = [];
2067 let c: Vec<int> = v.concat();
2069 let d: Vec<int> = [vec![1i], vec![2i,3i]].concat();
2070 assert_eq!(d, vec![1i, 2, 3]);
2072 let v: [&[int]; 2] = [&[1], &[2, 3]];
2073 assert_eq!(v.connect(&0), vec![1i, 0, 2, 3]);
2074 let v: [&[int]; 3] = [&[1i], &[2], &[3]];
2075 assert_eq!(v.connect(&0), vec![1i, 0, 2, 0, 3]);
2080 let v: [Vec<int>; 0] = [];
2081 assert_eq!(v.connect(&0), vec![]);
2082 assert_eq!([vec![1i], vec![2i, 3]].connect(&0), vec![1, 0, 2, 3]);
2083 assert_eq!([vec![1i], vec![2i], vec![3i]].connect(&0), vec![1, 0, 2, 0, 3]);
2085 let v: [&[int]; 2] = [&[1], &[2, 3]];
2086 assert_eq!(v.connect(&0), vec![1, 0, 2, 3]);
2087 let v: [&[int]; 3] = [&[1], &[2], &[3]];
2088 assert_eq!(v.connect(&0), vec![1, 0, 2, 0, 3]);
2093 let mut a = vec![1i, 2, 4];
2095 assert_eq!(a, vec![1, 2, 3, 4]);
2097 let mut a = vec![1i, 2, 3];
2099 assert_eq!(a, vec![0, 1, 2, 3]);
2101 let mut a = vec![1i, 2, 3];
2103 assert_eq!(a, vec![1, 2, 3, 4]);
2107 assert_eq!(a, vec![1]);
2112 fn test_insert_oob() {
2113 let mut a = vec![1i, 2, 3];
2119 let mut a = vec![1i,2,3,4];
2121 assert_eq!(a.remove(2), 3);
2122 assert_eq!(a, vec![1i,2,4]);
2124 assert_eq!(a.remove(2), 4);
2125 assert_eq!(a, vec![1i,2]);
2127 assert_eq!(a.remove(0), 1);
2128 assert_eq!(a, vec![2i]);
2130 assert_eq!(a.remove(0), 2);
2131 assert_eq!(a, vec![]);
2136 fn test_remove_fail() {
2137 let mut a = vec![1i];
2138 let _ = a.remove(0);
2139 let _ = a.remove(0);
2143 fn test_capacity() {
2144 let mut v = vec![0u64];
2145 v.reserve_exact(10u);
2146 assert!(v.capacity() >= 11u);
2147 let mut v = vec![0u32];
2148 v.reserve_exact(10u);
2149 assert!(v.capacity() >= 11u);
2154 let v = vec![1i, 2, 3, 4, 5];
2155 let v = v.slice(1u, 3u);
2156 assert_eq!(v.len(), 2u);
2157 assert_eq!(v[0], 2);
2158 assert_eq!(v[1], 3);
2163 fn test_permute_fail() {
2164 let v = [(box 0i, Rc::new(0i)), (box 0i, Rc::new(0i)),
2165 (box 0i, Rc::new(0i)), (box 0i, Rc::new(0i))];
2167 for _ in v.permutations() {
2176 fn test_total_ord() {
2177 let c: &[int] = &[1, 2, 3];
2178 [1, 2, 3, 4][].cmp(c) == Greater;
2179 let c: &[int] = &[1, 2, 3, 4];
2180 [1, 2, 3][].cmp(c) == Less;
2181 let c: &[int] = &[1, 2, 3, 6];
2182 [1, 2, 3, 4][].cmp(c) == Equal;
2183 let c: &[int] = &[1, 2, 3, 4, 5, 6];
2184 [1, 2, 3, 4, 5, 5, 5, 5][].cmp(c) == Less;
2185 let c: &[int] = &[1, 2, 3, 4];
2186 [2, 2][].cmp(c) == Greater;
2190 fn test_iterator() {
2191 let xs = [1i, 2, 5, 10, 11];
2192 let mut it = xs.iter();
2193 assert_eq!(it.size_hint(), (5, Some(5)));
2194 assert_eq!(it.next().unwrap(), &1);
2195 assert_eq!(it.size_hint(), (4, Some(4)));
2196 assert_eq!(it.next().unwrap(), &2);
2197 assert_eq!(it.size_hint(), (3, Some(3)));
2198 assert_eq!(it.next().unwrap(), &5);
2199 assert_eq!(it.size_hint(), (2, Some(2)));
2200 assert_eq!(it.next().unwrap(), &10);
2201 assert_eq!(it.size_hint(), (1, Some(1)));
2202 assert_eq!(it.next().unwrap(), &11);
2203 assert_eq!(it.size_hint(), (0, Some(0)));
2204 assert!(it.next().is_none());
2208 fn test_random_access_iterator() {
2209 let xs = [1i, 2, 5, 10, 11];
2210 let mut it = xs.iter();
2212 assert_eq!(it.indexable(), 5);
2213 assert_eq!(it.idx(0).unwrap(), &1);
2214 assert_eq!(it.idx(2).unwrap(), &5);
2215 assert_eq!(it.idx(4).unwrap(), &11);
2216 assert!(it.idx(5).is_none());
2218 assert_eq!(it.next().unwrap(), &1);
2219 assert_eq!(it.indexable(), 4);
2220 assert_eq!(it.idx(0).unwrap(), &2);
2221 assert_eq!(it.idx(3).unwrap(), &11);
2222 assert!(it.idx(4).is_none());
2224 assert_eq!(it.next().unwrap(), &2);
2225 assert_eq!(it.indexable(), 3);
2226 assert_eq!(it.idx(1).unwrap(), &10);
2227 assert!(it.idx(3).is_none());
2229 assert_eq!(it.next().unwrap(), &5);
2230 assert_eq!(it.indexable(), 2);
2231 assert_eq!(it.idx(1).unwrap(), &11);
2233 assert_eq!(it.next().unwrap(), &10);
2234 assert_eq!(it.indexable(), 1);
2235 assert_eq!(it.idx(0).unwrap(), &11);
2236 assert!(it.idx(1).is_none());
2238 assert_eq!(it.next().unwrap(), &11);
2239 assert_eq!(it.indexable(), 0);
2240 assert!(it.idx(0).is_none());
2242 assert!(it.next().is_none());
2246 fn test_iter_size_hints() {
2247 let mut xs = [1i, 2, 5, 10, 11];
2248 assert_eq!(xs.iter().size_hint(), (5, Some(5)));
2249 assert_eq!(xs.iter_mut().size_hint(), (5, Some(5)));
2253 fn test_iter_clone() {
2254 let xs = [1i, 2, 5];
2255 let mut it = xs.iter();
2257 let mut jt = it.clone();
2258 assert_eq!(it.next(), jt.next());
2259 assert_eq!(it.next(), jt.next());
2260 assert_eq!(it.next(), jt.next());
2264 fn test_mut_iterator() {
2265 let mut xs = [1i, 2, 3, 4, 5];
2266 for x in xs.iter_mut() {
2269 assert!(xs == [2, 3, 4, 5, 6])
2273 fn test_rev_iterator() {
2275 let xs = [1i, 2, 5, 10, 11];
2276 let ys = [11, 10, 5, 2, 1];
2278 for &x in xs.iter().rev() {
2279 assert_eq!(x, ys[i]);
2286 fn test_mut_rev_iterator() {
2287 let mut xs = [1u, 2, 3, 4, 5];
2288 for (i,x) in xs.iter_mut().rev().enumerate() {
2291 assert!(xs == [5, 5, 5, 5, 5])
2295 fn test_move_iterator() {
2296 let xs = vec![1u,2,3,4,5];
2297 assert_eq!(xs.into_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
2301 fn test_move_rev_iterator() {
2302 let xs = vec![1u,2,3,4,5];
2303 assert_eq!(xs.into_iter().rev().fold(0, |a: uint, b: uint| 10*a + b), 54321);
2307 fn test_splitator() {
2308 let xs = &[1i,2,3,4,5];
2310 let splits: &[&[int]] = &[&[1], &[3], &[5]];
2311 assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2313 let splits: &[&[int]] = &[&[], &[2,3,4,5]];
2314 assert_eq!(xs.split(|x| *x == 1).collect::<Vec<&[int]>>(),
2316 let splits: &[&[int]] = &[&[1,2,3,4], &[]];
2317 assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[int]>>(),
2319 let splits: &[&[int]] = &[&[1,2,3,4,5]];
2320 assert_eq!(xs.split(|x| *x == 10).collect::<Vec<&[int]>>(),
2322 let splits: &[&[int]] = &[&[], &[], &[], &[], &[], &[]];
2323 assert_eq!(xs.split(|_| true).collect::<Vec<&[int]>>(),
2326 let xs: &[int] = &[];
2327 let splits: &[&[int]] = &[&[]];
2328 assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[int]>>(), splits);
2332 fn test_splitnator() {
2333 let xs = &[1i,2,3,4,5];
2335 let splits: &[&[int]] = &[&[1,2,3,4,5]];
2336 assert_eq!(xs.splitn(0, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2338 let splits: &[&[int]] = &[&[1], &[3,4,5]];
2339 assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2341 let splits: &[&[int]] = &[&[], &[], &[], &[4,5]];
2342 assert_eq!(xs.splitn(3, |_| true).collect::<Vec<&[int]>>(),
2345 let xs: &[int] = &[];
2346 let splits: &[&[int]] = &[&[]];
2347 assert_eq!(xs.splitn(1, |x| *x == 5).collect::<Vec<&[int]>>(), splits);
2351 fn test_splitnator_mut() {
2352 let xs = &mut [1i,2,3,4,5];
2354 let splits: &[&mut [int]] = &[&mut [1,2,3,4,5]];
2355 assert_eq!(xs.splitn_mut(0, |x| *x % 2 == 0).collect::<Vec<&mut [int]>>(),
2357 let splits: &[&mut [int]] = &[&mut [1], &mut [3,4,5]];
2358 assert_eq!(xs.splitn_mut(1, |x| *x % 2 == 0).collect::<Vec<&mut [int]>>(),
2360 let splits: &[&mut [int]] = &[&mut [], &mut [], &mut [], &mut [4,5]];
2361 assert_eq!(xs.splitn_mut(3, |_| true).collect::<Vec<&mut [int]>>(),
2364 let xs: &mut [int] = &mut [];
2365 let splits: &[&mut [int]] = &[&mut []];
2366 assert_eq!(xs.splitn_mut(1, |x| *x == 5).collect::<Vec<&mut [int]>>(),
2371 fn test_rsplitator() {
2372 let xs = &[1i,2,3,4,5];
2374 let splits: &[&[int]] = &[&[5], &[3], &[1]];
2375 assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<&[int]>>(),
2377 let splits: &[&[int]] = &[&[2,3,4,5], &[]];
2378 assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<&[int]>>(),
2380 let splits: &[&[int]] = &[&[], &[1,2,3,4]];
2381 assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[int]>>(),
2383 let splits: &[&[int]] = &[&[1,2,3,4,5]];
2384 assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<&[int]>>(),
2387 let xs: &[int] = &[];
2388 let splits: &[&[int]] = &[&[]];
2389 assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[int]>>(), splits);
2393 fn test_rsplitnator() {
2394 let xs = &[1,2,3,4,5];
2396 let splits: &[&[int]] = &[&[1,2,3,4,5]];
2397 assert_eq!(xs.rsplitn(0, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2399 let splits: &[&[int]] = &[&[5], &[1,2,3]];
2400 assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<&[int]>>(),
2402 let splits: &[&[int]] = &[&[], &[], &[], &[1,2]];
2403 assert_eq!(xs.rsplitn(3, |_| true).collect::<Vec<&[int]>>(),
2406 let xs: &[int] = &[];
2407 let splits: &[&[int]] = &[&[]];
2408 assert_eq!(xs.rsplitn(1, |x| *x == 5).collect::<Vec<&[int]>>(), splits);
2412 fn test_windowsator() {
2413 let v = &[1i,2,3,4];
2415 let wins: &[&[int]] = &[&[1,2], &[2,3], &[3,4]];
2416 assert_eq!(v.windows(2).collect::<Vec<&[int]>>(), wins);
2417 let wins: &[&[int]] = &[&[1i,2,3], &[2,3,4]];
2418 assert_eq!(v.windows(3).collect::<Vec<&[int]>>(), wins);
2419 assert!(v.windows(6).next().is_none());
2424 fn test_windowsator_0() {
2425 let v = &[1i,2,3,4];
2426 let _it = v.windows(0);
2430 fn test_chunksator() {
2431 let v = &[1i,2,3,4,5];
2433 let chunks: &[&[int]] = &[&[1i,2], &[3,4], &[5]];
2434 assert_eq!(v.chunks(2).collect::<Vec<&[int]>>(), chunks);
2435 let chunks: &[&[int]] = &[&[1i,2,3], &[4,5]];
2436 assert_eq!(v.chunks(3).collect::<Vec<&[int]>>(), chunks);
2437 let chunks: &[&[int]] = &[&[1i,2,3,4,5]];
2438 assert_eq!(v.chunks(6).collect::<Vec<&[int]>>(), chunks);
2440 let chunks: &[&[int]] = &[&[5i], &[3,4], &[1,2]];
2441 assert_eq!(v.chunks(2).rev().collect::<Vec<&[int]>>(), chunks);
2442 let mut it = v.chunks(2);
2443 assert_eq!(it.indexable(), 3);
2444 let chunk: &[int] = &[1,2];
2445 assert_eq!(it.idx(0).unwrap(), chunk);
2446 let chunk: &[int] = &[3,4];
2447 assert_eq!(it.idx(1).unwrap(), chunk);
2448 let chunk: &[int] = &[5];
2449 assert_eq!(it.idx(2).unwrap(), chunk);
2450 assert_eq!(it.idx(3), None);
2455 fn test_chunksator_0() {
2456 let v = &[1i,2,3,4];
2457 let _it = v.chunks(0);
2461 fn test_move_from() {
2462 let mut a = [1i,2,3,4,5];
2463 let b = vec![6i,7,8];
2464 assert_eq!(a.move_from(b, 0, 3), 3);
2465 assert!(a == [6i,7,8,4,5]);
2466 let mut a = [7i,2,8,1];
2467 let b = vec![3i,1,4,1,5,9];
2468 assert_eq!(a.move_from(b, 0, 6), 4);
2469 assert!(a == [3i,1,4,1]);
2470 let mut a = [1i,2,3,4];
2471 let b = vec![5i,6,7,8,9,0];
2472 assert_eq!(a.move_from(b, 2, 3), 1);
2473 assert!(a == [7i,2,3,4]);
2474 let mut a = [1i,2,3,4,5];
2475 let b = vec![5i,6,7,8,9,0];
2476 assert_eq!(a.slice_mut(2, 4).move_from(b,1,6), 2);
2477 assert!(a == [1i,2,6,7,5]);
2481 fn test_reverse_part() {
2482 let mut values = [1i,2,3,4,5];
2483 values.slice_mut(1, 4).reverse();
2484 assert!(values == [1,4,3,2,5]);
2489 macro_rules! test_show_vec {
2490 ($x:expr, $x_str:expr) => ({
2491 let (x, x_str) = ($x, $x_str);
2492 assert_eq!(format!("{:?}", x), x_str);
2493 assert_eq!(format!("{:?}", x.as_slice()), x_str);
2496 let empty: Vec<int> = vec![];
2497 test_show_vec!(empty, "[]");
2498 test_show_vec!(vec![1i], "[1i]");
2499 test_show_vec!(vec![1i, 2, 3], "[1i, 2i, 3i]");
2500 test_show_vec!(vec![vec![], vec![1u], vec![1u, 1u]],
2501 "[[], [1u], [1u, 1u]]");
2503 let empty_mut: &mut [int] = &mut[];
2504 test_show_vec!(empty_mut, "[]");
2505 let v: &mut[int] = &mut[1];
2506 test_show_vec!(v, "[1i]");
2507 let v: &mut[int] = &mut[1, 2, 3];
2508 test_show_vec!(v, "[1i, 2i, 3i]");
2509 let v: &mut [&mut[uint]] = &mut[&mut[], &mut[1u], &mut[1u, 1u]];
2510 test_show_vec!(v, "[[], [1u], [1u, 1u]]");
2514 fn test_vec_default() {
2517 let v: $ty = Default::default();
2518 assert!(v.is_empty());
2527 fn test_bytes_set_memory() {
2528 use slice::bytes::MutableByteVector;
2529 let mut values = [1u8,2,3,4,5];
2530 values.slice_mut(0, 5).set_memory(0xAB);
2531 assert!(values == [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
2532 values.slice_mut(2, 4).set_memory(0xFF);
2533 assert!(values == [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
2538 fn test_overflow_does_not_cause_segfault() {
2540 v.reserve_exact(-1);
2547 fn test_overflow_does_not_cause_segfault_managed() {
2548 let mut v = vec![Rc::new(1i)];
2549 v.reserve_exact(-1);
2550 v.push(Rc::new(2i));
2554 fn test_mut_split_at() {
2555 let mut values = [1u8,2,3,4,5];
2557 let (left, right) = values.split_at_mut(2);
2559 let left: &[_] = left;
2560 assert!(left[..left.len()] == [1, 2][]);
2562 for p in left.iter_mut() {
2567 let right: &[_] = right;
2568 assert!(right[..right.len()] == [3, 4, 5][]);
2570 for p in right.iter_mut() {
2575 assert!(values == [2, 3, 5, 6, 7]);
2578 #[derive(Clone, PartialEq)]
2582 fn test_iter_zero_sized() {
2583 let mut v = vec![Foo, Foo, Foo];
2584 assert_eq!(v.len(), 3);
2593 for f in v[1..3].iter() {
2599 for f in v.iter_mut() {
2605 for f in v.into_iter() {
2609 assert_eq!(cnt, 11);
2611 let xs: [Foo; 3] = [Foo, Foo, Foo];
2613 for f in xs.iter() {
2621 fn test_shrink_to_fit() {
2622 let mut xs = vec![0, 1, 2, 3];
2623 for i in range(4i, 100) {
2626 assert_eq!(xs.capacity(), 128);
2628 assert_eq!(xs.capacity(), 100);
2629 assert_eq!(xs, range(0i, 100i).collect::<Vec<_>>());
2633 fn test_starts_with() {
2634 assert!(b"foobar".starts_with(b"foo"));
2635 assert!(!b"foobar".starts_with(b"oob"));
2636 assert!(!b"foobar".starts_with(b"bar"));
2637 assert!(!b"foo".starts_with(b"foobar"));
2638 assert!(!b"bar".starts_with(b"foobar"));
2639 assert!(b"foobar".starts_with(b"foobar"));
2640 let empty: &[u8] = &[];
2641 assert!(empty.starts_with(empty));
2642 assert!(!empty.starts_with(b"foo"));
2643 assert!(b"foobar".starts_with(empty));
2647 fn test_ends_with() {
2648 assert!(b"foobar".ends_with(b"bar"));
2649 assert!(!b"foobar".ends_with(b"oba"));
2650 assert!(!b"foobar".ends_with(b"foo"));
2651 assert!(!b"foo".ends_with(b"foobar"));
2652 assert!(!b"bar".ends_with(b"foobar"));
2653 assert!(b"foobar".ends_with(b"foobar"));
2654 let empty: &[u8] = &[];
2655 assert!(empty.ends_with(empty));
2656 assert!(!empty.ends_with(b"foo"));
2657 assert!(b"foobar".ends_with(empty));
2661 fn test_mut_splitator() {
2662 let mut xs = [0i,1,0,2,3,0,0,4,5,0];
2663 assert_eq!(xs.split_mut(|x| *x == 0).count(), 6);
2664 for slice in xs.split_mut(|x| *x == 0) {
2667 assert!(xs == [0,1,0,3,2,0,0,5,4,0]);
2669 let mut xs = [0i,1,0,2,3,0,0,4,5,0,6,7];
2670 for slice in xs.split_mut(|x| *x == 0).take(5) {
2673 assert!(xs == [0,1,0,3,2,0,0,5,4,0,6,7]);
2677 fn test_mut_splitator_rev() {
2678 let mut xs = [1i,2,0,3,4,0,0,5,6,0];
2679 for slice in xs.split_mut(|x| *x == 0).rev().take(4) {
2682 assert!(xs == [1,2,0,4,3,0,0,6,5,0]);
2687 let mut v = [0i,1,2];
2688 assert_eq!(v.get_mut(3), None);
2689 v.get_mut(1).map(|e| *e = 7);
2690 assert_eq!(v[1], 7);
2692 assert_eq!(v.get_mut(2), Some(&mut x));
2696 fn test_mut_chunks() {
2697 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
2698 for (i, chunk) in v.chunks_mut(3).enumerate() {
2699 for x in chunk.iter_mut() {
2703 let result = [0u8, 0, 0, 1, 1, 1, 2];
2704 assert!(v == result);
2708 fn test_mut_chunks_rev() {
2709 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
2710 for (i, chunk) in v.chunks_mut(3).rev().enumerate() {
2711 for x in chunk.iter_mut() {
2715 let result = [2u8, 2, 2, 1, 1, 1, 0];
2716 assert!(v == result);
2721 fn test_mut_chunks_0() {
2722 let mut v = [1i, 2, 3, 4];
2723 let _it = v.chunks_mut(0);
2727 fn test_mut_last() {
2728 let mut x = [1i, 2, 3, 4, 5];
2729 let h = x.last_mut();
2730 assert_eq!(*h.unwrap(), 5);
2732 let y: &mut [int] = &mut [];
2733 assert!(y.last_mut().is_none());
2738 let xs = box [1u, 2, 3];
2739 let ys = xs.to_vec();
2740 assert_eq!(ys, [1u, 2, 3]);
2749 use core::iter::repeat;
2750 use std::rand::{weak_rng, Rng};
2751 use test::{Bencher, black_box};
2754 fn iterator(b: &mut Bencher) {
2755 // peculiar numbers to stop LLVM from optimising the summation
2757 let v = range(0u, 100).map(|i| i ^ (i << 1) ^ (i >> 1)).collect::<Vec<_>>();
2764 // sum == 11806, to stop dead code elimination.
2765 if sum == 0 {panic!()}
2770 fn mut_iterator(b: &mut Bencher) {
2771 let mut v = repeat(0i).take(100).collect::<Vec<_>>();
2775 for x in v.iter_mut() {
2783 fn concat(b: &mut Bencher) {
2784 let xss: Vec<Vec<uint>> =
2785 range(0, 100u).map(|i| range(0, i).collect()).collect();
2787 xss.as_slice().concat();
2792 fn connect(b: &mut Bencher) {
2793 let xss: Vec<Vec<uint>> =
2794 range(0, 100u).map(|i| range(0, i).collect()).collect();
2796 xss.as_slice().connect(&0)
2801 fn push(b: &mut Bencher) {
2802 let mut vec: Vec<uint> = vec![];
2810 fn starts_with_same_vector(b: &mut Bencher) {
2811 let vec: Vec<uint> = range(0, 100).collect();
2813 vec.as_slice().starts_with(vec.as_slice())
2818 fn starts_with_single_element(b: &mut Bencher) {
2819 let vec: Vec<uint> = vec![0];
2821 vec.as_slice().starts_with(vec.as_slice())
2826 fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
2827 let vec: Vec<uint> = range(0, 100).collect();
2828 let mut match_vec: Vec<uint> = range(0, 99).collect();
2831 vec.as_slice().starts_with(match_vec.as_slice())
2836 fn ends_with_same_vector(b: &mut Bencher) {
2837 let vec: Vec<uint> = range(0, 100).collect();
2839 vec.as_slice().ends_with(vec.as_slice())
2844 fn ends_with_single_element(b: &mut Bencher) {
2845 let vec: Vec<uint> = vec![0];
2847 vec.as_slice().ends_with(vec.as_slice())
2852 fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
2853 let vec: Vec<uint> = range(0, 100).collect();
2854 let mut match_vec: Vec<uint> = range(0, 100).collect();
2855 match_vec.as_mut_slice()[0] = 200;
2857 vec.as_slice().starts_with(match_vec.as_slice())
2862 fn contains_last_element(b: &mut Bencher) {
2863 let vec: Vec<uint> = range(0, 100).collect();
2870 fn zero_1kb_from_elem(b: &mut Bencher) {
2872 repeat(0u8).take(1024).collect::<Vec<_>>()
2877 fn zero_1kb_set_memory(b: &mut Bencher) {
2879 let mut v: Vec<uint> = Vec::with_capacity(1024);
2881 let vp = v.as_mut_ptr();
2882 ptr::set_memory(vp, 0, 1024);
2890 fn zero_1kb_loop_set(b: &mut Bencher) {
2892 let mut v: Vec<uint> = Vec::with_capacity(1024);
2896 for i in range(0u, 1024) {
2903 fn zero_1kb_mut_iter(b: &mut Bencher) {
2905 let mut v = Vec::with_capacity(1024);
2909 for x in v.iter_mut() {
2917 fn random_inserts(b: &mut Bencher) {
2918 let mut rng = weak_rng();
2920 let mut v = repeat((0u, 0u)).take(30).collect::<Vec<_>>();
2921 for _ in range(0u, 100) {
2923 v.insert(rng.gen::<uint>() % (l + 1),
2929 fn random_removes(b: &mut Bencher) {
2930 let mut rng = weak_rng();
2932 let mut v = repeat((0u, 0u)).take(130).collect::<Vec<_>>();
2933 for _ in range(0u, 100) {
2935 v.remove(rng.gen::<uint>() % l);
2941 fn sort_random_small(b: &mut Bencher) {
2942 let mut rng = weak_rng();
2944 let mut v = rng.gen_iter::<u64>().take(5).collect::<Vec<u64>>();
2945 v.as_mut_slice().sort();
2947 b.bytes = 5 * mem::size_of::<u64>() as u64;
2951 fn sort_random_medium(b: &mut Bencher) {
2952 let mut rng = weak_rng();
2954 let mut v = rng.gen_iter::<u64>().take(100).collect::<Vec<u64>>();
2955 v.as_mut_slice().sort();
2957 b.bytes = 100 * mem::size_of::<u64>() as u64;
2961 fn sort_random_large(b: &mut Bencher) {
2962 let mut rng = weak_rng();
2964 let mut v = rng.gen_iter::<u64>().take(10000).collect::<Vec<u64>>();
2965 v.as_mut_slice().sort();
2967 b.bytes = 10000 * mem::size_of::<u64>() as u64;
2971 fn sort_sorted(b: &mut Bencher) {
2972 let mut v = range(0u, 10000).collect::<Vec<_>>();
2976 b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;
2979 type BigSortable = (u64,u64,u64,u64);
2982 fn sort_big_random_small(b: &mut Bencher) {
2983 let mut rng = weak_rng();
2985 let mut v = rng.gen_iter::<BigSortable>().take(5)
2986 .collect::<Vec<BigSortable>>();
2989 b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
2993 fn sort_big_random_medium(b: &mut Bencher) {
2994 let mut rng = weak_rng();
2996 let mut v = rng.gen_iter::<BigSortable>().take(100)
2997 .collect::<Vec<BigSortable>>();
3000 b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
3004 fn sort_big_random_large(b: &mut Bencher) {
3005 let mut rng = weak_rng();
3007 let mut v = rng.gen_iter::<BigSortable>().take(10000)
3008 .collect::<Vec<BigSortable>>();
3011 b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
3015 fn sort_big_sorted(b: &mut Bencher) {
3016 let mut v = range(0, 10000u).map(|i| (i, i, i, i)).collect::<Vec<_>>();
3020 b.bytes = (v.len() * mem::size_of_val(&v[0])) as u64;