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.
13 Utilities for vector manipulation
15 The `vec` module contains useful code to help work with vector values.
16 Vectors are Rust's list type. Vectors contain zero or more values of
20 let int_vector = [1,2,3];
21 let str_vector = ["one", "two", "three"];
24 This is a big module, but for a high-level overview:
28 Several structs that are useful for vectors, such as `Items`, which
29 represents iteration over a vector.
33 A number of traits add methods that allow you to accomplish tasks with vectors.
35 Traits defined for the `&[T]` type (a vector slice), have methods that can be
36 called on either owned vectors, denoted `~[T]`, or on vector slices themselves.
37 These traits include `ImmutableVector`, and `MutableVector` for the `&mut [T]`
40 An example is the method `.slice(a, b)` that returns an immutable "view" into
41 a vector or a vector slice from the index interval `[a, b)`:
44 let numbers = [0, 1, 2];
45 let last_numbers = numbers.slice(1, 3);
46 // last_numbers is now &[1, 2]
49 Traits defined for the `~[T]` type, like `OwnedVector`, can only be called
50 on such vectors. These methods deal with adding elements or otherwise changing
51 the allocation of the vector.
53 An example is the method `.push(element)` that will add an element at the end
57 let mut numbers = vec![0, 1, 2];
59 // numbers is now vec![0, 1, 2, 7];
62 ## Implementations of other traits
64 Vectors are a very useful type, and so there's several implementations of
65 traits from other modules. Some notable examples:
68 * `Eq`, `Ord`, `TotalEq`, `TotalOrd` -- vectors can be compared,
69 if the element type defines the corresponding trait.
73 The method `iter()` returns an iteration value for a vector or a vector slice.
74 The iterator yields references to the vector's elements, so if the element
75 type of the vector is `int`, the element type of the iterator is `&int`.
78 let numbers = [0, 1, 2];
79 for &x in numbers.iter() {
80 println!("{} is a number!", x);
84 * `.mut_iter()` returns an iterator that allows modifying each value.
85 * `.move_iter()` converts an owned vector into an iterator that
86 moves out a value from the vector each iteration.
87 * Further iterators exist that split, chunk or permute the vector.
89 ## Function definitions
91 There are a number of free functions that create or take vectors, for example:
93 * Creating a vector, like `from_elem` and `from_fn`
94 * Creating a vector with a given size: `with_capacity`
95 * Modifying a vector and returning it, like `append`
96 * Operations on paired elements, like `unzip`.
102 use cmp::{TotalOrd, Ordering, Less, Greater};
104 use container::Container;
109 use option::{None, Option, Some};
112 use rt::heap::{allocate, deallocate};
113 use unstable::finally::try_finally;
116 pub use core::slice::{ref_slice, mut_ref_slice, Splits, Windows};
117 pub use core::slice::{Chunks, Vector, ImmutableVector, ImmutableEqVector};
118 pub use core::slice::{ImmutableTotalOrdVector, MutableVector, Items, MutItems};
119 pub use core::slice::{MutSplits, MutChunks};
120 pub use core::slice::{bytes, MutableCloneableVector};
122 // Functional utilities
124 #[allow(missing_doc)]
125 pub trait VectorVector<T> {
126 // FIXME #5898: calling these .concat and .connect conflicts with
127 // StrVector::con{cat,nect}, since they have generic contents.
128 /// Flattens a vector of vectors of T into a single vector of T.
129 fn concat_vec(&self) -> Vec<T>;
131 /// Concatenate a vector of vectors, placing a given separator between each.
132 fn connect_vec(&self, sep: &T) -> Vec<T>;
135 impl<'a, T: Clone, V: Vector<T>> VectorVector<T> for &'a [V] {
136 fn concat_vec(&self) -> Vec<T> {
137 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
138 let mut result = Vec::with_capacity(size);
139 for v in self.iter() {
140 result.push_all(v.as_slice())
145 fn connect_vec(&self, sep: &T) -> Vec<T> {
146 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
147 let mut result = Vec::with_capacity(size + self.len());
148 let mut first = true;
149 for v in self.iter() {
150 if first { first = false } else { result.push(sep.clone()) }
151 result.push_all(v.as_slice())
157 /// An Iterator that yields the element swaps needed to produce
158 /// a sequence of all possible permutations for an indexed sequence of
159 /// elements. Each permutation is only a single swap apart.
161 /// The Steinhaus–Johnson–Trotter algorithm is used.
163 /// Generates even and odd permutations alternately.
165 /// The last generated swap is always (0, 1), and it returns the
166 /// sequence to its initial order.
167 pub struct ElementSwaps {
168 sdir: Vec<SizeDirection>,
169 /// If true, emit the last swap that returns the sequence to initial state
175 /// Create an `ElementSwaps` iterator for a sequence of `length` elements
176 pub fn new(length: uint) -> ElementSwaps {
177 // Initialize `sdir` with a direction that position should move in
178 // (all negative at the beginning) and the `size` of the
179 // element (equal to the original index).
182 sdir: range(0, length).map(|i| SizeDirection{ size: i, dir: Neg }).collect(),
188 enum Direction { Pos, Neg }
190 /// An Index and Direction together
191 struct SizeDirection {
196 impl Iterator<(uint, uint)> for ElementSwaps {
198 fn next(&mut self) -> Option<(uint, uint)> {
199 fn new_pos(i: uint, s: Direction) -> uint {
200 i + match s { Pos => 1, Neg => -1 }
203 // Find the index of the largest mobile element:
204 // The direction should point into the vector, and the
205 // swap should be with a smaller `size` element.
206 let max = self.sdir.iter().map(|&x| x).enumerate()
208 new_pos(i, sd.dir) < self.sdir.len() &&
209 self.sdir.get(new_pos(i, sd.dir)).size < sd.size)
210 .max_by(|&(_, sd)| sd.size);
213 let j = new_pos(i, sd.dir);
214 self.sdir.as_mut_slice().swap(i, j);
216 // Swap the direction of each larger SizeDirection
217 for x in self.sdir.mut_iter() {
218 if x.size > sd.size {
219 x.dir = match x.dir { Pos => Neg, Neg => Pos };
222 self.swaps_made += 1;
225 None => if self.emit_reset {
226 self.emit_reset = false;
227 if self.sdir.len() > 1 {
229 self.swaps_made += 1;
232 // Vector is of the form [] or [x], and the only permutation is itself
233 self.swaps_made += 1;
241 fn size_hint(&self) -> (uint, Option<uint>) {
242 // For a vector of size n, there are exactly n! permutations.
243 let n = range(2, self.sdir.len() + 1).product();
244 (n - self.swaps_made, Some(n - self.swaps_made))
248 /// An Iterator that uses `ElementSwaps` to iterate through
249 /// all possible permutations of a vector.
251 /// The first iteration yields a clone of the vector as it is,
252 /// then each successive element is the vector with one
255 /// Generates even and odd permutations alternately.
256 pub struct Permutations<T> {
261 impl<T: Clone> Iterator<~[T]> for Permutations<T> {
263 fn next(&mut self) -> Option<~[T]> {
264 match self.swaps.next() {
266 Some((0,0)) => Some(self.v.clone()),
268 let elt = self.v.clone();
276 fn size_hint(&self) -> (uint, Option<uint>) {
277 self.swaps.size_hint()
281 /// Extension methods for vector slices with cloneable elements
282 pub trait CloneableVector<T> {
283 /// Copy `self` into a new owned vector
284 fn to_owned(&self) -> ~[T];
286 /// Convert `self` into an owned vector, not making a copy if possible.
287 fn into_owned(self) -> ~[T];
290 /// Extension methods for vector slices
291 impl<'a, T: Clone> CloneableVector<T> for &'a [T] {
292 /// Returns a copy of `v`.
294 fn to_owned(&self) -> ~[T] {
295 use RawVec = core::raw::Vec;
296 use num::{CheckedAdd, CheckedMul};
299 let len = self.len();
300 let data_size = len.checked_mul(&mem::size_of::<T>());
301 let data_size = data_size.expect("overflow in to_owned()");
302 let size = mem::size_of::<RawVec<()>>().checked_add(&data_size);
303 let size = size.expect("overflow in to_owned()");
306 // this should pass the real required alignment
307 let ret = allocate(size, 8) as *mut RawVec<()>;
309 let a_size = mem::size_of::<T>();
310 let a_size = if a_size == 0 {1} else {a_size};
311 (*ret).fill = len * a_size;
312 (*ret).alloc = len * a_size;
314 // Be careful with the following loop. We want it to be optimized
315 // to a memcpy (or something similarly fast) when T is Copy. LLVM
316 // is easily confused, so any extra operations during the loop can
317 // prevent this optimization.
319 let p = &mut (*ret).data as *mut _ as *mut T;
322 |i, ()| while *i < len {
324 &mut(*p.offset(*i as int)),
325 self.unsafe_ref(*i).clone());
329 // we must be failing, clean up after ourselves
330 for j in range(0, *i as int) {
331 ptr::read(&*p.offset(j));
333 // FIXME: #13994 (should pass align and size here)
334 deallocate(ret as *mut u8, 0, 8);
341 fn into_owned(self) -> ~[T] { self.to_owned() }
344 /// Extension methods for owned vectors
345 impl<T: Clone> CloneableVector<T> for ~[T] {
347 fn to_owned(&self) -> ~[T] { self.clone() }
350 fn into_owned(self) -> ~[T] { self }
353 /// Extension methods for vectors containing `Clone` elements.
354 pub trait ImmutableCloneableVector<T> {
355 /// Partitions the vector into two vectors `(A,B)`, where all
356 /// elements of `A` satisfy `f` and all elements of `B` do not.
357 fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>);
359 /// Create an iterator that yields every possible permutation of the
360 /// vector in succession.
361 fn permutations(self) -> Permutations<T>;
364 impl<'a,T:Clone> ImmutableCloneableVector<T> for &'a [T] {
366 fn partitioned(&self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
367 let mut lefts = Vec::new();
368 let mut rights = Vec::new();
370 for elt in self.iter() {
372 lefts.push((*elt).clone());
374 rights.push((*elt).clone());
381 fn permutations(self) -> Permutations<T> {
383 swaps: ElementSwaps::new(self.len()),
390 /// Extension methods for owned vectors.
391 pub trait OwnedVector<T> {
392 /// Creates a consuming iterator, that is, one that moves each
393 /// value out of the vector (from start to end). The vector cannot
394 /// be used after calling this.
399 /// let v = ~["a".to_owned(), "b".to_owned()];
400 /// for s in v.move_iter() {
401 /// // s has type ~str, not &~str
402 /// println!("{}", s);
405 fn move_iter(self) -> MoveItems<T>;
408 * Partitions the vector into two vectors `(A,B)`, where all
409 * elements of `A` satisfy `f` and all elements of `B` do not.
411 fn partition(self, f: |&T| -> bool) -> (Vec<T>, Vec<T>);
414 impl<T> OwnedVector<T> for ~[T] {
416 fn move_iter(self) -> MoveItems<T> {
418 let iter = transmute(self.iter());
419 let ptr = transmute(self);
420 MoveItems { allocation: ptr, iter: iter }
425 fn partition(self, f: |&T| -> bool) -> (Vec<T>, Vec<T>) {
426 let mut lefts = Vec::new();
427 let mut rights = Vec::new();
429 for elt in self.move_iter() {
441 fn insertion_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
442 let len = v.len() as int;
443 let buf_v = v.as_mut_ptr();
446 for i in range(1, len) {
447 // j satisfies: 0 <= j <= i;
451 let read_ptr = buf_v.offset(i) as *T;
453 // find where to insert, we need to do strict <,
454 // rather than <=, to maintain stability.
456 // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
458 compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less {
462 // shift everything to the right, to make space to
463 // insert this value.
465 // j + 1 could be `len` (for the last `i`), but in
466 // that case, `i == j` so we don't copy. The
467 // `.offset(j)` is always in bounds.
470 let tmp = ptr::read(read_ptr);
471 ptr::copy_memory(buf_v.offset(j + 1),
474 ptr::copy_nonoverlapping_memory(buf_v.offset(j),
483 fn merge_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
484 // warning: this wildly uses unsafe.
485 static BASE_INSERTION: uint = 32;
486 static LARGE_INSERTION: uint = 16;
488 // FIXME #12092: smaller insertion runs seems to make sorting
489 // vectors of large elements a little faster on some platforms,
490 // but hasn't been tested/tuned extensively
491 let insertion = if size_of::<T>() <= 16 {
499 // short vectors get sorted in-place via insertion sort to avoid allocations
500 if len <= insertion {
501 insertion_sort(v, compare);
505 // allocate some memory to use as scratch memory, we keep the
506 // length 0 so we can keep shallow copies of the contents of `v`
507 // without risking the dtors running on an object twice if
509 let mut working_space = Vec::with_capacity(2 * len);
510 // these both are buffers of length `len`.
511 let mut buf_dat = working_space.as_mut_ptr();
512 let mut buf_tmp = unsafe {buf_dat.offset(len as int)};
515 let buf_v = v.as_ptr();
517 // step 1. sort short runs with insertion sort. This takes the
518 // values from `v` and sorts them into `buf_dat`, leaving that
519 // with sorted runs of length INSERTION.
521 // We could hardcode the sorting comparisons here, and we could
522 // manipulate/step the pointers themselves, rather than repeatedly
524 for start in range_step(0, len, insertion) {
526 for i in range(start, cmp::min(start + insertion, len)) {
527 // j satisfies: start <= j <= i;
528 let mut j = i as int;
531 let read_ptr = buf_v.offset(i as int);
533 // find where to insert, we need to do strict <,
534 // rather than <=, to maintain stability.
536 // start <= j - 1 < len, so .offset(j - 1) is in
538 while j > start as int &&
539 compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less {
543 // shift everything to the right, to make space to
544 // insert this value.
546 // j + 1 could be `len` (for the last `i`), but in
547 // that case, `i == j` so we don't copy. The
548 // `.offset(j)` is always in bounds.
549 ptr::copy_memory(buf_dat.offset(j + 1),
552 ptr::copy_nonoverlapping_memory(buf_dat.offset(j), read_ptr, 1);
557 // step 2. merge the sorted runs.
558 let mut width = insertion;
560 // merge the sorted runs of length `width` in `buf_dat` two at
561 // a time, placing the result in `buf_tmp`.
563 // 0 <= start <= len.
564 for start in range_step(0, len, 2 * width) {
565 // manipulate pointers directly for speed (rather than
566 // using a `for` loop with `range` and `.offset` inside
569 // the end of the first run & start of the
570 // second. Offset of `len` is defined, since this is
571 // precisely one byte past the end of the object.
572 let right_start = buf_dat.offset(cmp::min(start + width, len) as int);
573 // end of the second. Similar reasoning to the above re safety.
574 let right_end_idx = cmp::min(start + 2 * width, len);
575 let right_end = buf_dat.offset(right_end_idx as int);
577 // the pointers to the elements under consideration
578 // from the two runs.
580 // both of these are in bounds.
581 let mut left = buf_dat.offset(start as int);
582 let mut right = right_start;
584 // where we're putting the results, it is a run of
585 // length `2*width`, so we step it once for each step
586 // of either `left` or `right`. `buf_tmp` has length
587 // `len`, so these are in bounds.
588 let mut out = buf_tmp.offset(start as int);
589 let out_end = buf_tmp.offset(right_end_idx as int);
591 while out < out_end {
592 // Either the left or the right run are exhausted,
593 // so just copy the remainder from the other run
594 // and move on; this gives a huge speed-up (order
595 // of 25%) for mostly sorted vectors (the best
597 if left == right_start {
598 // the number remaining in this run.
599 let elems = (right_end as uint - right as uint) / mem::size_of::<T>();
600 ptr::copy_nonoverlapping_memory(out, &*right, elems);
602 } else if right == right_end {
603 let elems = (right_start as uint - left as uint) / mem::size_of::<T>();
604 ptr::copy_nonoverlapping_memory(out, &*left, elems);
608 // check which side is smaller, and that's the
609 // next element for the new run.
611 // `left < right_start` and `right < right_end`,
612 // so these are valid.
613 let to_copy = if compare(&*left, &*right) == Greater {
618 ptr::copy_nonoverlapping_memory(out, &*to_copy, 1);
624 mem::swap(&mut buf_dat, &mut buf_tmp);
629 // write the result to `v` in one go, so that there are never two copies
630 // of the same object in `v`.
632 ptr::copy_nonoverlapping_memory(v.as_mut_ptr(), &*buf_dat, len);
635 // increment the pointer, returning the old pointer.
637 unsafe fn step<T>(ptr: &mut *mut T) -> *mut T {
639 *ptr = ptr.offset(1);
644 /// Extension methods for vectors such that their elements are
646 pub trait MutableVectorAllocating<'a, T> {
647 /// Sort the vector, in place, using `compare` to compare
650 /// This sort is `O(n log n)` worst-case and stable, but allocates
651 /// approximately `2 * n`, where `n` is the length of `self`.
656 /// let mut v = [5i, 4, 1, 3, 2];
657 /// v.sort_by(|a, b| a.cmp(b));
658 /// assert!(v == [1, 2, 3, 4, 5]);
660 /// // reverse sorting
661 /// v.sort_by(|a, b| b.cmp(a));
662 /// assert!(v == [5, 4, 3, 2, 1]);
664 fn sort_by(self, compare: |&T, &T| -> Ordering);
667 * Consumes `src` and moves as many elements as it can into `self`
668 * from the range [start,end).
670 * Returns the number of elements copied (the shorter of self.len()
675 * * src - A mutable vector of `T`
676 * * start - The index into `src` to start copying from
677 * * end - The index into `str` to stop copying from
679 fn move_from(self, src: ~[T], start: uint, end: uint) -> uint;
682 impl<'a,T> MutableVectorAllocating<'a, T> for &'a mut [T] {
684 fn sort_by(self, compare: |&T, &T| -> Ordering) {
685 merge_sort(self, compare)
689 fn move_from(self, mut src: ~[T], start: uint, end: uint) -> uint {
690 for (a, b) in self.mut_iter().zip(src.mut_slice(start, end).mut_iter()) {
693 cmp::min(self.len(), end-start)
697 /// Methods for mutable vectors with orderable elements, such as
698 /// in-place sorting.
699 pub trait MutableTotalOrdVector<T> {
700 /// Sort the vector, in place.
702 /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`.
707 /// let mut v = [-5, 4, 1, -3, 2];
710 /// assert!(v == [-5, -3, 1, 2, 4]);
715 impl<'a, T: TotalOrd> MutableTotalOrdVector<T> for &'a mut [T] {
718 self.sort_by(|a,b| a.cmp(b))
722 /// Unsafe operations
724 pub use core::slice::raw::{buf_as_slice, mut_buf_as_slice};
725 pub use core::slice::raw::{shift_ptr, pop_ptr};
728 /// An iterator that moves out of a vector.
729 pub struct MoveItems<T> {
730 allocation: *mut u8, // the block of memory allocated for the vector
731 iter: Items<'static, T>
734 impl<T> Iterator<T> for MoveItems<T> {
736 fn next(&mut self) -> Option<T> {
738 self.iter.next().map(|x| ptr::read(x))
743 fn size_hint(&self) -> (uint, Option<uint>) {
744 self.iter.size_hint()
748 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
750 fn next_back(&mut self) -> Option<T> {
752 self.iter.next_back().map(|x| ptr::read(x))
758 impl<T> Drop for MoveItems<T> {
760 // destroy the remaining elements
763 // FIXME: #13994 (should pass align and size here)
764 deallocate(self.allocation, 0, 8)
775 use rand::{Rng, task_rng};
778 fn square(n: uint) -> uint { n * n }
780 fn is_odd(n: &uint) -> bool { *n % 2u == 1u }
784 // Test on-stack from_fn.
785 let mut v = Vec::from_fn(3u, square);
787 let v = v.as_slice();
788 assert_eq!(v.len(), 3u);
789 assert_eq!(v[0], 0u);
790 assert_eq!(v[1], 1u);
791 assert_eq!(v[2], 4u);
794 // Test on-heap from_fn.
795 v = Vec::from_fn(5u, square);
797 let v = v.as_slice();
798 assert_eq!(v.len(), 5u);
799 assert_eq!(v[0], 0u);
800 assert_eq!(v[1], 1u);
801 assert_eq!(v[2], 4u);
802 assert_eq!(v[3], 9u);
803 assert_eq!(v[4], 16u);
808 fn test_from_elem() {
809 // Test on-stack from_elem.
810 let mut v = Vec::from_elem(2u, 10u);
812 let v = v.as_slice();
813 assert_eq!(v.len(), 2u);
814 assert_eq!(v[0], 10u);
815 assert_eq!(v[1], 10u);
818 // Test on-heap from_elem.
819 v = Vec::from_elem(6u, 20u);
821 let v = v.as_slice();
822 assert_eq!(v[0], 20u);
823 assert_eq!(v[1], 20u);
824 assert_eq!(v[2], 20u);
825 assert_eq!(v[3], 20u);
826 assert_eq!(v[4], 20u);
827 assert_eq!(v[5], 20u);
833 let xs: [int, ..0] = [];
834 assert!(xs.is_empty());
835 assert!(![0].is_empty());
839 fn test_len_divzero() {
842 let v1 : &[Z] = &[[]];
843 let v2 : &[Z] = &[[], []];
844 assert_eq!(mem::size_of::<Z>(), 0);
845 assert_eq!(v0.len(), 0);
846 assert_eq!(v1.len(), 1);
847 assert_eq!(v2.len(), 2);
852 let mut a = box [11];
853 assert_eq!(a.get(1), None);
855 assert_eq!(a.get(1).unwrap(), &12);
856 a = box [11, 12, 13];
857 assert_eq!(a.get(1).unwrap(), &12);
863 assert_eq!(a.head(), None);
865 assert_eq!(a.head().unwrap(), &11);
867 assert_eq!(a.head().unwrap(), &11);
872 let mut a = box [11];
873 assert_eq!(a.tail(), &[]);
875 assert_eq!(a.tail(), &[12]);
880 fn test_tail_empty() {
881 let a: ~[int] = box [];
887 let mut a = box [11, 12, 13];
888 assert_eq!(a.tailn(0), &[11, 12, 13]);
889 a = box [11, 12, 13];
890 assert_eq!(a.tailn(2), &[13]);
895 fn test_tailn_empty() {
896 let a: ~[int] = box [];
902 let mut a = box [11];
903 assert_eq!(a.init(), &[]);
905 assert_eq!(a.init(), &[11]);
910 fn test_init_empty() {
911 let a: ~[int] = box [];
917 let mut a = box [11, 12, 13];
918 assert_eq!(a.initn(0), &[11, 12, 13]);
919 a = box [11, 12, 13];
920 assert_eq!(a.initn(2), &[11]);
925 fn test_initn_empty() {
926 let a: ~[int] = box [];
933 assert_eq!(a.last(), None);
935 assert_eq!(a.last().unwrap(), &11);
937 assert_eq!(a.last().unwrap(), &12);
942 // Test fixed length vector.
943 let vec_fixed = [1, 2, 3, 4];
944 let v_a = vec_fixed.slice(1u, vec_fixed.len()).to_owned();
945 assert_eq!(v_a.len(), 3u);
946 assert_eq!(v_a[0], 2);
947 assert_eq!(v_a[1], 3);
948 assert_eq!(v_a[2], 4);
951 let vec_stack = &[1, 2, 3];
952 let v_b = vec_stack.slice(1u, 3u).to_owned();
953 assert_eq!(v_b.len(), 2u);
954 assert_eq!(v_b[0], 2);
955 assert_eq!(v_b[1], 3);
958 let vec_unique = box [1, 2, 3, 4, 5, 6];
959 let v_d = vec_unique.slice(1u, 6u).to_owned();
960 assert_eq!(v_d.len(), 5u);
961 assert_eq!(v_d[0], 2);
962 assert_eq!(v_d[1], 3);
963 assert_eq!(v_d[2], 4);
964 assert_eq!(v_d[3], 5);
965 assert_eq!(v_d[4], 6);
969 fn test_slice_from() {
970 let vec = &[1, 2, 3, 4];
971 assert_eq!(vec.slice_from(0), vec);
972 assert_eq!(vec.slice_from(2), &[3, 4]);
973 assert_eq!(vec.slice_from(4), &[]);
978 let vec = &[1, 2, 3, 4];
979 assert_eq!(vec.slice_to(4), vec);
980 assert_eq!(vec.slice_to(2), &[1, 2]);
981 assert_eq!(vec.slice_to(0), &[]);
989 assert_eq!(v.len(), 0);
990 assert_eq!(e, Some(5));
998 fn test_swap_remove() {
999 let mut v = vec![1, 2, 3, 4, 5];
1000 let mut e = v.swap_remove(0);
1001 assert_eq!(e, Some(1));
1002 assert_eq!(v, vec![5, 2, 3, 4]);
1003 e = v.swap_remove(3);
1004 assert_eq!(e, Some(4));
1005 assert_eq!(v, vec![5, 2, 3]);
1007 e = v.swap_remove(3);
1008 assert_eq!(e, None);
1009 assert_eq!(v, vec![5, 2, 3]);
1013 fn test_swap_remove_noncopyable() {
1014 // Tests that we don't accidentally run destructors twice.
1015 let mut v = vec![::unstable::sync::Exclusive::new(()),
1016 ::unstable::sync::Exclusive::new(()),
1017 ::unstable::sync::Exclusive::new(())];
1018 let mut _e = v.swap_remove(0);
1019 assert_eq!(v.len(), 2);
1020 _e = v.swap_remove(1);
1021 assert_eq!(v.len(), 1);
1022 _e = v.swap_remove(0);
1023 assert_eq!(v.len(), 0);
1028 // Test on-stack push().
1031 assert_eq!(v.len(), 1u);
1032 assert_eq!(v.as_slice()[0], 1);
1034 // Test on-heap push().
1036 assert_eq!(v.len(), 2u);
1037 assert_eq!(v.as_slice()[0], 1);
1038 assert_eq!(v.as_slice()[1], 2);
1043 // Test on-stack grow().
1047 let v = v.as_slice();
1048 assert_eq!(v.len(), 2u);
1049 assert_eq!(v[0], 1);
1050 assert_eq!(v[1], 1);
1053 // Test on-heap grow().
1056 let v = v.as_slice();
1057 assert_eq!(v.len(), 5u);
1058 assert_eq!(v[0], 1);
1059 assert_eq!(v[1], 1);
1060 assert_eq!(v[2], 2);
1061 assert_eq!(v[3], 2);
1062 assert_eq!(v[4], 2);
1069 v.grow_fn(3u, square);
1070 let v = v.as_slice();
1071 assert_eq!(v.len(), 3u);
1072 assert_eq!(v[0], 0u);
1073 assert_eq!(v[1], 1u);
1074 assert_eq!(v[2], 4u);
1078 fn test_grow_set() {
1079 let mut v = vec![1, 2, 3];
1080 v.grow_set(4u, &4, 5);
1081 let v = v.as_slice();
1082 assert_eq!(v.len(), 5u);
1083 assert_eq!(v[0], 1);
1084 assert_eq!(v[1], 2);
1085 assert_eq!(v[2], 3);
1086 assert_eq!(v[3], 4);
1087 assert_eq!(v[4], 5);
1091 fn test_truncate() {
1092 let mut v = vec![box 6,box 5,box 4];
1094 let v = v.as_slice();
1095 assert_eq!(v.len(), 1);
1096 assert_eq!(*(v[0]), 6);
1097 // If the unsafe block didn't drop things properly, we blow up here.
1102 let mut v = vec![box 6,box 5,box 4];
1104 assert_eq!(v.len(), 0);
1105 // If the unsafe block didn't drop things properly, we blow up here.
1110 fn case(a: Vec<uint>, b: Vec<uint>) {
1115 case(vec![], vec![]);
1116 case(vec![1], vec![1]);
1117 case(vec![1,1], vec![1]);
1118 case(vec![1,2,3], vec![1,2,3]);
1119 case(vec![1,1,2,3], vec![1,2,3]);
1120 case(vec![1,2,2,3], vec![1,2,3]);
1121 case(vec![1,2,3,3], vec![1,2,3]);
1122 case(vec![1,1,2,2,2,3,3], vec![1,2,3]);
1126 fn test_dedup_unique() {
1127 let mut v0 = vec![box 1, box 1, box 2, box 3];
1129 let mut v1 = vec![box 1, box 2, box 2, box 3];
1131 let mut v2 = vec![box 1, box 2, box 3, box 3];
1134 * If the boxed pointers were leaked or otherwise misused, valgrind
1135 * and/or rustrt should raise errors.
1140 fn test_dedup_shared() {
1141 let mut v0 = vec![box 1, box 1, box 2, box 3];
1143 let mut v1 = vec![box 1, box 2, box 2, box 3];
1145 let mut v2 = vec![box 1, box 2, box 3, box 3];
1148 * If the pointers were leaked or otherwise misused, valgrind and/or
1149 * rustrt should raise errors.
1155 let mut v = vec![1, 2, 3, 4, 5];
1157 assert_eq!(v, vec![1, 3, 5]);
1161 fn test_element_swaps() {
1162 let mut v = [1, 2, 3];
1163 for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
1166 0 => assert!(v == [1, 3, 2]),
1167 1 => assert!(v == [3, 1, 2]),
1168 2 => assert!(v == [3, 2, 1]),
1169 3 => assert!(v == [2, 3, 1]),
1170 4 => assert!(v == [2, 1, 3]),
1171 5 => assert!(v == [1, 2, 3]),
1178 fn test_permutations() {
1180 let v: [int, ..0] = [];
1181 let mut it = v.permutations();
1182 let (min_size, max_opt) = it.size_hint();
1183 assert_eq!(min_size, 1);
1184 assert_eq!(max_opt.unwrap(), 1);
1185 assert_eq!(it.next(), Some(v.as_slice().to_owned()));
1186 assert_eq!(it.next(), None);
1189 let v = ["Hello".to_owned()];
1190 let mut it = v.permutations();
1191 let (min_size, max_opt) = it.size_hint();
1192 assert_eq!(min_size, 1);
1193 assert_eq!(max_opt.unwrap(), 1);
1194 assert_eq!(it.next(), Some(v.as_slice().to_owned()));
1195 assert_eq!(it.next(), None);
1199 let mut it = v.permutations();
1200 let (min_size, max_opt) = it.size_hint();
1201 assert_eq!(min_size, 3*2);
1202 assert_eq!(max_opt.unwrap(), 3*2);
1203 assert_eq!(it.next(), Some(box [1,2,3]));
1204 assert_eq!(it.next(), Some(box [1,3,2]));
1205 assert_eq!(it.next(), Some(box [3,1,2]));
1206 let (min_size, max_opt) = it.size_hint();
1207 assert_eq!(min_size, 3);
1208 assert_eq!(max_opt.unwrap(), 3);
1209 assert_eq!(it.next(), Some(box [3,2,1]));
1210 assert_eq!(it.next(), Some(box [2,3,1]));
1211 assert_eq!(it.next(), Some(box [2,1,3]));
1212 assert_eq!(it.next(), None);
1215 // check that we have N! permutations
1216 let v = ['A', 'B', 'C', 'D', 'E', 'F'];
1218 let mut it = v.permutations();
1219 let (min_size, max_opt) = it.size_hint();
1223 assert_eq!(amt, it.swaps.swaps_made);
1224 assert_eq!(amt, min_size);
1225 assert_eq!(amt, 2 * 3 * 4 * 5 * 6);
1226 assert_eq!(amt, max_opt.unwrap());
1231 fn test_position_elem() {
1232 assert!([].position_elem(&1).is_none());
1234 let v1 = box [1, 2, 3, 3, 2, 5];
1235 assert_eq!(v1.position_elem(&1), Some(0u));
1236 assert_eq!(v1.position_elem(&2), Some(1u));
1237 assert_eq!(v1.position_elem(&5), Some(5u));
1238 assert!(v1.position_elem(&4).is_none());
1242 fn test_bsearch_elem() {
1243 assert_eq!([1,2,3,4,5].bsearch_elem(&5), Some(4));
1244 assert_eq!([1,2,3,4,5].bsearch_elem(&4), Some(3));
1245 assert_eq!([1,2,3,4,5].bsearch_elem(&3), Some(2));
1246 assert_eq!([1,2,3,4,5].bsearch_elem(&2), Some(1));
1247 assert_eq!([1,2,3,4,5].bsearch_elem(&1), Some(0));
1249 assert_eq!([2,4,6,8,10].bsearch_elem(&1), None);
1250 assert_eq!([2,4,6,8,10].bsearch_elem(&5), None);
1251 assert_eq!([2,4,6,8,10].bsearch_elem(&4), Some(1));
1252 assert_eq!([2,4,6,8,10].bsearch_elem(&10), Some(4));
1254 assert_eq!([2,4,6,8].bsearch_elem(&1), None);
1255 assert_eq!([2,4,6,8].bsearch_elem(&5), None);
1256 assert_eq!([2,4,6,8].bsearch_elem(&4), Some(1));
1257 assert_eq!([2,4,6,8].bsearch_elem(&8), Some(3));
1259 assert_eq!([2,4,6].bsearch_elem(&1), None);
1260 assert_eq!([2,4,6].bsearch_elem(&5), None);
1261 assert_eq!([2,4,6].bsearch_elem(&4), Some(1));
1262 assert_eq!([2,4,6].bsearch_elem(&6), Some(2));
1264 assert_eq!([2,4].bsearch_elem(&1), None);
1265 assert_eq!([2,4].bsearch_elem(&5), None);
1266 assert_eq!([2,4].bsearch_elem(&2), Some(0));
1267 assert_eq!([2,4].bsearch_elem(&4), Some(1));
1269 assert_eq!([2].bsearch_elem(&1), None);
1270 assert_eq!([2].bsearch_elem(&5), None);
1271 assert_eq!([2].bsearch_elem(&2), Some(0));
1273 assert_eq!([].bsearch_elem(&1), None);
1274 assert_eq!([].bsearch_elem(&5), None);
1276 assert!([1,1,1,1,1].bsearch_elem(&1) != None);
1277 assert!([1,1,1,1,2].bsearch_elem(&1) != None);
1278 assert!([1,1,1,2,2].bsearch_elem(&1) != None);
1279 assert!([1,1,2,2,2].bsearch_elem(&1) != None);
1280 assert_eq!([1,2,2,2,2].bsearch_elem(&1), Some(0));
1282 assert_eq!([1,2,3,4,5].bsearch_elem(&6), None);
1283 assert_eq!([1,2,3,4,5].bsearch_elem(&0), None);
1288 let mut v: ~[int] = box [10, 20];
1289 assert_eq!(v[0], 10);
1290 assert_eq!(v[1], 20);
1292 assert_eq!(v[0], 20);
1293 assert_eq!(v[1], 10);
1295 let mut v3: ~[int] = box [];
1297 assert!(v3.is_empty());
1302 use realstd::slice::Vector;
1303 use realstd::clone::Clone;
1304 for len in range(4u, 25) {
1305 for _ in range(0, 100) {
1306 let mut v = task_rng().gen_vec::<uint>(len);
1307 let mut v1 = v.clone();
1309 v.as_mut_slice().sort();
1310 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
1312 v1.as_mut_slice().sort_by(|a, b| a.cmp(b));
1313 assert!(v1.as_slice().windows(2).all(|w| w[0] <= w[1]));
1315 v1.as_mut_slice().sort_by(|a, b| b.cmp(a));
1316 assert!(v1.as_slice().windows(2).all(|w| w[0] >= w[1]));
1320 // shouldn't fail/crash
1321 let mut v: [uint, .. 0] = [];
1324 let mut v = [0xDEADBEEFu];
1326 assert!(v == [0xDEADBEEF]);
1330 fn test_sort_stability() {
1331 for len in range(4, 25) {
1332 for _ in range(0 , 10) {
1333 let mut counts = [0, .. 10];
1335 // create a vector like [(6, 1), (5, 1), (6, 2), ...],
1336 // where the first item of each tuple is random, but
1337 // the second item represents which occurrence of that
1338 // number this element is, i.e. the second elements
1339 // will occur in sorted order.
1340 let mut v = range(0, len).map(|_| {
1341 let n = task_rng().gen::<uint>() % 10;
1344 }).collect::<Vec<(uint, int)>>();
1346 // only sort on the first element, so an unstable sort
1347 // may mix up the counts.
1348 v.sort_by(|&(a,_), &(b,_)| a.cmp(&b));
1350 // this comparison includes the count (the second item
1351 // of the tuple), so elements with equal first items
1352 // will need to be ordered with increasing
1353 // counts... i.e. exactly asserting that this sort is
1355 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
1361 fn test_partition() {
1362 assert_eq!((box []).partition(|x: &int| *x < 3), (vec![], vec![]));
1363 assert_eq!((box [1, 2, 3]).partition(|x: &int| *x < 4), (vec![1, 2, 3], vec![]));
1364 assert_eq!((box [1, 2, 3]).partition(|x: &int| *x < 2), (vec![1], vec![2, 3]));
1365 assert_eq!((box [1, 2, 3]).partition(|x: &int| *x < 0), (vec![], vec![1, 2, 3]));
1369 fn test_partitioned() {
1370 assert_eq!(([]).partitioned(|x: &int| *x < 3), (vec![], vec![]));
1371 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 4), (vec![1, 2, 3], vec![]));
1372 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 2), (vec![1], vec![2, 3]));
1373 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 0), (vec![], vec![1, 2, 3]));
1378 let v: [~[int], ..0] = [];
1379 assert_eq!(v.concat_vec(), vec![]);
1380 assert_eq!([box [1], box [2,3]].concat_vec(), vec![1, 2, 3]);
1382 assert_eq!([&[1], &[2,3]].concat_vec(), vec![1, 2, 3]);
1387 let v: [~[int], ..0] = [];
1388 assert_eq!(v.connect_vec(&0), vec![]);
1389 assert_eq!([box [1], box [2, 3]].connect_vec(&0), vec![1, 0, 2, 3]);
1390 assert_eq!([box [1], box [2], box [3]].connect_vec(&0), vec![1, 0, 2, 0, 3]);
1392 assert_eq!([&[1], &[2, 3]].connect_vec(&0), vec![1, 0, 2, 3]);
1393 assert_eq!([&[1], &[2], &[3]].connect_vec(&0), vec![1, 0, 2, 0, 3]);
1398 let mut x = vec![1, 2, 3];
1399 assert_eq!(x.shift(), Some(1));
1400 assert_eq!(&x, &vec![2, 3]);
1401 assert_eq!(x.shift(), Some(2));
1402 assert_eq!(x.shift(), Some(3));
1403 assert_eq!(x.shift(), None);
1404 assert_eq!(x.len(), 0);
1409 let mut x = vec![1, 2, 3];
1411 assert_eq!(x, vec![0, 1, 2, 3]);
1416 let mut a = vec![1, 2, 4];
1418 assert_eq!(a, vec![1, 2, 3, 4]);
1420 let mut a = vec![1, 2, 3];
1422 assert_eq!(a, vec![0, 1, 2, 3]);
1424 let mut a = vec![1, 2, 3];
1426 assert_eq!(a, vec![1, 2, 3, 4]);
1430 assert_eq!(a, vec![1]);
1435 fn test_insert_oob() {
1436 let mut a = vec![1, 2, 3];
1442 let mut a = vec![1,2,3,4];
1444 assert_eq!(a.remove(2), Some(3));
1445 assert_eq!(a, vec![1,2,4]);
1447 assert_eq!(a.remove(2), Some(4));
1448 assert_eq!(a, vec![1,2]);
1450 assert_eq!(a.remove(2), None);
1451 assert_eq!(a, vec![1,2]);
1453 assert_eq!(a.remove(0), Some(1));
1454 assert_eq!(a, vec![2]);
1456 assert_eq!(a.remove(0), Some(2));
1457 assert_eq!(a, vec![]);
1459 assert_eq!(a.remove(0), None);
1460 assert_eq!(a.remove(10), None);
1464 fn test_capacity() {
1465 let mut v = vec![0u64];
1466 v.reserve_exact(10u);
1467 assert_eq!(v.capacity(), 10u);
1468 let mut v = vec![0u32];
1469 v.reserve_exact(10u);
1470 assert_eq!(v.capacity(), 10u);
1475 let v = vec![1, 2, 3, 4, 5];
1476 let v = v.slice(1u, 3u);
1477 assert_eq!(v.len(), 2u);
1478 assert_eq!(v[0], 2);
1479 assert_eq!(v[1], 3);
1485 fn test_from_fn_fail() {
1486 Vec::from_fn(100, |v| {
1487 if v == 50 { fail!() }
1494 fn test_from_elem_fail() {
1500 boxes: (Box<int>, Rc<int>)
1504 fn clone(&self) -> S {
1505 self.f.set(self.f.get() + 1);
1506 if self.f.get() == 10 { fail!() }
1507 S { f: self.f, boxes: self.boxes.clone() }
1511 let s = S { f: Cell::new(0), boxes: (box 0, Rc::new(0)) };
1512 let _ = Vec::from_elem(100, s);
1517 fn test_grow_fn_fail() {
1520 v.grow_fn(100, |i| {
1530 fn test_permute_fail() {
1532 let v = [(box 0, Rc::new(0)), (box 0, Rc::new(0)),
1533 (box 0, Rc::new(0)), (box 0, Rc::new(0))];
1535 for _ in v.permutations() {
1545 fn test_copy_memory_oob() {
1547 let mut a = [1, 2, 3, 4];
1548 let b = [1, 2, 3, 4, 5];
1554 fn test_total_ord() {
1555 [1, 2, 3, 4].cmp(& &[1, 2, 3]) == Greater;
1556 [1, 2, 3].cmp(& &[1, 2, 3, 4]) == Less;
1557 [1, 2, 3, 4].cmp(& &[1, 2, 3, 4]) == Equal;
1558 [1, 2, 3, 4, 5, 5, 5, 5].cmp(& &[1, 2, 3, 4, 5, 6]) == Less;
1559 [2, 2].cmp(& &[1, 2, 3, 4]) == Greater;
1563 fn test_iterator() {
1565 let xs = [1, 2, 5, 10, 11];
1566 let mut it = xs.iter();
1567 assert_eq!(it.size_hint(), (5, Some(5)));
1568 assert_eq!(it.next().unwrap(), &1);
1569 assert_eq!(it.size_hint(), (4, Some(4)));
1570 assert_eq!(it.next().unwrap(), &2);
1571 assert_eq!(it.size_hint(), (3, Some(3)));
1572 assert_eq!(it.next().unwrap(), &5);
1573 assert_eq!(it.size_hint(), (2, Some(2)));
1574 assert_eq!(it.next().unwrap(), &10);
1575 assert_eq!(it.size_hint(), (1, Some(1)));
1576 assert_eq!(it.next().unwrap(), &11);
1577 assert_eq!(it.size_hint(), (0, Some(0)));
1578 assert!(it.next().is_none());
1582 fn test_random_access_iterator() {
1584 let xs = [1, 2, 5, 10, 11];
1585 let mut it = xs.iter();
1587 assert_eq!(it.indexable(), 5);
1588 assert_eq!(it.idx(0).unwrap(), &1);
1589 assert_eq!(it.idx(2).unwrap(), &5);
1590 assert_eq!(it.idx(4).unwrap(), &11);
1591 assert!(it.idx(5).is_none());
1593 assert_eq!(it.next().unwrap(), &1);
1594 assert_eq!(it.indexable(), 4);
1595 assert_eq!(it.idx(0).unwrap(), &2);
1596 assert_eq!(it.idx(3).unwrap(), &11);
1597 assert!(it.idx(4).is_none());
1599 assert_eq!(it.next().unwrap(), &2);
1600 assert_eq!(it.indexable(), 3);
1601 assert_eq!(it.idx(1).unwrap(), &10);
1602 assert!(it.idx(3).is_none());
1604 assert_eq!(it.next().unwrap(), &5);
1605 assert_eq!(it.indexable(), 2);
1606 assert_eq!(it.idx(1).unwrap(), &11);
1608 assert_eq!(it.next().unwrap(), &10);
1609 assert_eq!(it.indexable(), 1);
1610 assert_eq!(it.idx(0).unwrap(), &11);
1611 assert!(it.idx(1).is_none());
1613 assert_eq!(it.next().unwrap(), &11);
1614 assert_eq!(it.indexable(), 0);
1615 assert!(it.idx(0).is_none());
1617 assert!(it.next().is_none());
1621 fn test_iter_size_hints() {
1623 let mut xs = [1, 2, 5, 10, 11];
1624 assert_eq!(xs.iter().size_hint(), (5, Some(5)));
1625 assert_eq!(xs.mut_iter().size_hint(), (5, Some(5)));
1629 fn test_iter_clone() {
1631 let mut it = xs.iter();
1633 let mut jt = it.clone();
1634 assert_eq!(it.next(), jt.next());
1635 assert_eq!(it.next(), jt.next());
1636 assert_eq!(it.next(), jt.next());
1640 fn test_mut_iterator() {
1642 let mut xs = [1, 2, 3, 4, 5];
1643 for x in xs.mut_iter() {
1646 assert!(xs == [2, 3, 4, 5, 6])
1650 fn test_rev_iterator() {
1653 let xs = [1, 2, 5, 10, 11];
1654 let ys = [11, 10, 5, 2, 1];
1656 for &x in xs.iter().rev() {
1657 assert_eq!(x, ys[i]);
1664 fn test_mut_rev_iterator() {
1666 let mut xs = [1u, 2, 3, 4, 5];
1667 for (i,x) in xs.mut_iter().rev().enumerate() {
1670 assert!(xs == [5, 5, 5, 5, 5])
1674 fn test_move_iterator() {
1676 let xs = box [1u,2,3,4,5];
1677 assert_eq!(xs.move_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
1681 fn test_move_rev_iterator() {
1683 let xs = box [1u,2,3,4,5];
1684 assert_eq!(xs.move_iter().rev().fold(0, |a: uint, b: uint| 10*a + b), 54321);
1688 fn test_splitator() {
1689 let xs = &[1i,2,3,4,5];
1691 assert_eq!(xs.split(|x| *x % 2 == 0).collect::<Vec<&[int]>>().as_slice(),
1692 &[&[1], &[3], &[5]]);
1693 assert_eq!(xs.split(|x| *x == 1).collect::<Vec<&[int]>>().as_slice(),
1694 &[&[], &[2,3,4,5]]);
1695 assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[int]>>().as_slice(),
1696 &[&[1,2,3,4], &[]]);
1697 assert_eq!(xs.split(|x| *x == 10).collect::<Vec<&[int]>>().as_slice(),
1699 assert_eq!(xs.split(|_| true).collect::<Vec<&[int]>>().as_slice(),
1700 &[&[], &[], &[], &[], &[], &[]]);
1702 let xs: &[int] = &[];
1703 assert_eq!(xs.split(|x| *x == 5).collect::<Vec<&[int]>>().as_slice(), &[&[]]);
1707 fn test_splitnator() {
1708 let xs = &[1i,2,3,4,5];
1710 assert_eq!(xs.splitn(0, |x| *x % 2 == 0).collect::<Vec<&[int]>>().as_slice(),
1712 assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<Vec<&[int]>>().as_slice(),
1714 assert_eq!(xs.splitn(3, |_| true).collect::<Vec<&[int]>>().as_slice(),
1715 &[&[], &[], &[], &[4,5]]);
1717 let xs: &[int] = &[];
1718 assert_eq!(xs.splitn(1, |x| *x == 5).collect::<Vec<&[int]>>().as_slice(), &[&[]]);
1722 fn test_rsplitator() {
1723 let xs = &[1i,2,3,4,5];
1725 assert_eq!(xs.split(|x| *x % 2 == 0).rev().collect::<Vec<&[int]>>().as_slice(),
1726 &[&[5], &[3], &[1]]);
1727 assert_eq!(xs.split(|x| *x == 1).rev().collect::<Vec<&[int]>>().as_slice(),
1728 &[&[2,3,4,5], &[]]);
1729 assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[int]>>().as_slice(),
1730 &[&[], &[1,2,3,4]]);
1731 assert_eq!(xs.split(|x| *x == 10).rev().collect::<Vec<&[int]>>().as_slice(),
1734 let xs: &[int] = &[];
1735 assert_eq!(xs.split(|x| *x == 5).rev().collect::<Vec<&[int]>>().as_slice(), &[&[]]);
1739 fn test_rsplitnator() {
1740 let xs = &[1,2,3,4,5];
1742 assert_eq!(xs.rsplitn(0, |x| *x % 2 == 0).collect::<Vec<&[int]>>().as_slice(),
1744 assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<Vec<&[int]>>().as_slice(),
1746 assert_eq!(xs.rsplitn(3, |_| true).collect::<Vec<&[int]>>().as_slice(),
1747 &[&[], &[], &[], &[1,2]]);
1749 let xs: &[int] = &[];
1750 assert_eq!(xs.rsplitn(1, |x| *x == 5).collect::<Vec<&[int]>>().as_slice(), &[&[]]);
1754 fn test_windowsator() {
1755 let v = &[1i,2,3,4];
1757 assert_eq!(v.windows(2).collect::<Vec<&[int]>>().as_slice(), &[&[1,2], &[2,3], &[3,4]]);
1758 assert_eq!(v.windows(3).collect::<Vec<&[int]>>().as_slice(), &[&[1i,2,3], &[2,3,4]]);
1759 assert!(v.windows(6).next().is_none());
1764 fn test_windowsator_0() {
1765 let v = &[1i,2,3,4];
1766 let _it = v.windows(0);
1770 fn test_chunksator() {
1771 let v = &[1i,2,3,4,5];
1773 assert_eq!(v.chunks(2).collect::<Vec<&[int]>>().as_slice(), &[&[1i,2], &[3,4], &[5]]);
1774 assert_eq!(v.chunks(3).collect::<Vec<&[int]>>().as_slice(), &[&[1i,2,3], &[4,5]]);
1775 assert_eq!(v.chunks(6).collect::<Vec<&[int]>>().as_slice(), &[&[1i,2,3,4,5]]);
1777 assert_eq!(v.chunks(2).rev().collect::<Vec<&[int]>>().as_slice(), &[&[5i], &[3,4], &[1,2]]);
1778 let mut it = v.chunks(2);
1779 assert_eq!(it.indexable(), 3);
1780 assert_eq!(it.idx(0).unwrap(), &[1,2]);
1781 assert_eq!(it.idx(1).unwrap(), &[3,4]);
1782 assert_eq!(it.idx(2).unwrap(), &[5]);
1783 assert_eq!(it.idx(3), None);
1788 fn test_chunksator_0() {
1789 let v = &[1i,2,3,4];
1790 let _it = v.chunks(0);
1794 fn test_move_from() {
1795 let mut a = [1,2,3,4,5];
1796 let b = box [6,7,8];
1797 assert_eq!(a.move_from(b, 0, 3), 3);
1798 assert!(a == [6,7,8,4,5]);
1799 let mut a = [7,2,8,1];
1800 let b = box [3,1,4,1,5,9];
1801 assert_eq!(a.move_from(b, 0, 6), 4);
1802 assert!(a == [3,1,4,1]);
1803 let mut a = [1,2,3,4];
1804 let b = box [5,6,7,8,9,0];
1805 assert_eq!(a.move_from(b, 2, 3), 1);
1806 assert!(a == [7,2,3,4]);
1807 let mut a = [1,2,3,4,5];
1808 let b = box [5,6,7,8,9,0];
1809 assert_eq!(a.mut_slice(2,4).move_from(b,1,6), 2);
1810 assert!(a == [1,2,6,7,5]);
1814 fn test_copy_from() {
1815 let mut a = [1,2,3,4,5];
1817 assert_eq!(a.copy_from(b), 3);
1818 assert!(a == [6,7,8,4,5]);
1819 let mut c = [7,2,8,1];
1820 let d = [3,1,4,1,5,9];
1821 assert_eq!(c.copy_from(d), 4);
1822 assert!(c == [3,1,4,1]);
1826 fn test_reverse_part() {
1827 let mut values = [1,2,3,4,5];
1828 values.mut_slice(1, 4).reverse();
1829 assert!(values == [1,4,3,2,5]);
1834 macro_rules! test_show_vec(
1835 ($x:expr, $x_str:expr) => ({
1836 let (x, x_str) = ($x, $x_str);
1837 assert_eq!(format!("{}", x), x_str);
1838 assert_eq!(format!("{}", x.as_slice()), x_str);
1841 let empty: ~[int] = box [];
1842 test_show_vec!(empty, "[]".to_strbuf());
1843 test_show_vec!(box [1], "[1]".to_strbuf());
1844 test_show_vec!(box [1, 2, 3], "[1, 2, 3]".to_strbuf());
1845 test_show_vec!(box [box [], box [1u], box [1u, 1u]],
1846 "[[], [1], [1, 1]]".to_strbuf());
1848 let empty_mut: &mut [int] = &mut[];
1849 test_show_vec!(empty_mut, "[]".to_strbuf());
1850 test_show_vec!(&mut[1], "[1]".to_strbuf());
1851 test_show_vec!(&mut[1, 2, 3], "[1, 2, 3]".to_strbuf());
1852 test_show_vec!(&mut[&mut[], &mut[1u], &mut[1u, 1u]],
1853 "[[], [1], [1, 1]]".to_strbuf());
1857 fn test_vec_default() {
1858 use default::Default;
1861 let v: $ty = Default::default();
1862 assert!(v.is_empty());
1872 fn test_bytes_set_memory() {
1873 use slice::bytes::MutableByteVector;
1874 let mut values = [1u8,2,3,4,5];
1875 values.mut_slice(0,5).set_memory(0xAB);
1876 assert!(values == [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
1877 values.mut_slice(2,4).set_memory(0xFF);
1878 assert!(values == [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
1883 fn test_overflow_does_not_cause_segfault() {
1885 v.reserve_exact(-1);
1892 fn test_overflow_does_not_cause_segfault_managed() {
1894 let mut v = vec![Rc::new(1)];
1895 v.reserve_exact(-1);
1900 fn test_mut_split_at() {
1901 let mut values = [1u8,2,3,4,5];
1903 let (left, right) = values.mut_split_at(2);
1904 assert!(left.slice(0, left.len()) == [1, 2]);
1905 for p in left.mut_iter() {
1909 assert!(right.slice(0, right.len()) == [3, 4, 5]);
1910 for p in right.mut_iter() {
1915 assert!(values == [2, 3, 5, 6, 7]);
1918 #[deriving(Clone, Eq)]
1922 fn test_iter_zero_sized() {
1923 let mut v = vec![Foo, Foo, Foo];
1924 assert_eq!(v.len(), 3);
1933 for f in v.slice(1, 3).iter() {
1939 for f in v.mut_iter() {
1945 for f in v.move_iter() {
1949 assert_eq!(cnt, 11);
1951 let xs: [Foo, ..3] = [Foo, Foo, Foo];
1953 for f in xs.iter() {
1961 fn test_shrink_to_fit() {
1962 let mut xs = vec![0, 1, 2, 3];
1963 for i in range(4, 100) {
1966 assert_eq!(xs.capacity(), 128);
1968 assert_eq!(xs.capacity(), 100);
1969 assert_eq!(xs, range(0, 100).collect::<Vec<_>>());
1973 fn test_starts_with() {
1974 assert!(bytes!("foobar").starts_with(bytes!("foo")));
1975 assert!(!bytes!("foobar").starts_with(bytes!("oob")));
1976 assert!(!bytes!("foobar").starts_with(bytes!("bar")));
1977 assert!(!bytes!("foo").starts_with(bytes!("foobar")));
1978 assert!(!bytes!("bar").starts_with(bytes!("foobar")));
1979 assert!(bytes!("foobar").starts_with(bytes!("foobar")));
1980 let empty: &[u8] = [];
1981 assert!(empty.starts_with(empty));
1982 assert!(!empty.starts_with(bytes!("foo")));
1983 assert!(bytes!("foobar").starts_with(empty));
1987 fn test_ends_with() {
1988 assert!(bytes!("foobar").ends_with(bytes!("bar")));
1989 assert!(!bytes!("foobar").ends_with(bytes!("oba")));
1990 assert!(!bytes!("foobar").ends_with(bytes!("foo")));
1991 assert!(!bytes!("foo").ends_with(bytes!("foobar")));
1992 assert!(!bytes!("bar").ends_with(bytes!("foobar")));
1993 assert!(bytes!("foobar").ends_with(bytes!("foobar")));
1994 let empty: &[u8] = [];
1995 assert!(empty.ends_with(empty));
1996 assert!(!empty.ends_with(bytes!("foo")));
1997 assert!(bytes!("foobar").ends_with(empty));
2001 fn test_shift_ref() {
2002 let mut x: &[int] = [1, 2, 3, 4, 5];
2003 let h = x.shift_ref();
2004 assert_eq!(*h.unwrap(), 1);
2005 assert_eq!(x.len(), 4);
2006 assert_eq!(x[0], 2);
2007 assert_eq!(x[3], 5);
2009 let mut y: &[int] = [];
2010 assert_eq!(y.shift_ref(), None);
2015 let mut x: &[int] = [1, 2, 3, 4, 5];
2016 let h = x.pop_ref();
2017 assert_eq!(*h.unwrap(), 5);
2018 assert_eq!(x.len(), 4);
2019 assert_eq!(x[0], 1);
2020 assert_eq!(x[3], 4);
2022 let mut y: &[int] = [];
2023 assert!(y.pop_ref().is_none());
2027 fn test_mut_splitator() {
2028 let mut xs = [0,1,0,2,3,0,0,4,5,0];
2029 assert_eq!(xs.mut_split(|x| *x == 0).len(), 6);
2030 for slice in xs.mut_split(|x| *x == 0) {
2033 assert!(xs == [0,1,0,3,2,0,0,5,4,0]);
2035 let mut xs = [0,1,0,2,3,0,0,4,5,0,6,7];
2036 for slice in xs.mut_split(|x| *x == 0).take(5) {
2039 assert!(xs == [0,1,0,3,2,0,0,5,4,0,6,7]);
2043 fn test_mut_splitator_rev() {
2044 let mut xs = [1,2,0,3,4,0,0,5,6,0];
2045 for slice in xs.mut_split(|x| *x == 0).rev().take(4) {
2048 assert!(xs == [1,2,0,4,3,0,0,6,5,0]);
2052 fn test_mut_chunks() {
2053 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
2054 for (i, chunk) in v.mut_chunks(3).enumerate() {
2055 for x in chunk.mut_iter() {
2059 let result = [0u8, 0, 0, 1, 1, 1, 2];
2060 assert!(v == result);
2064 fn test_mut_chunks_rev() {
2065 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
2066 for (i, chunk) in v.mut_chunks(3).rev().enumerate() {
2067 for x in chunk.mut_iter() {
2071 let result = [2u8, 2, 2, 1, 1, 1, 0];
2072 assert!(v == result);
2077 fn test_mut_chunks_0() {
2078 let mut v = [1, 2, 3, 4];
2079 let _it = v.mut_chunks(0);
2083 fn test_mut_shift_ref() {
2084 let mut x: &mut [int] = [1, 2, 3, 4, 5];
2085 let h = x.mut_shift_ref();
2086 assert_eq!(*h.unwrap(), 1);
2087 assert_eq!(x.len(), 4);
2088 assert_eq!(x[0], 2);
2089 assert_eq!(x[3], 5);
2091 let mut y: &mut [int] = [];
2092 assert!(y.mut_shift_ref().is_none());
2096 fn test_mut_pop_ref() {
2097 let mut x: &mut [int] = [1, 2, 3, 4, 5];
2098 let h = x.mut_pop_ref();
2099 assert_eq!(*h.unwrap(), 5);
2100 assert_eq!(x.len(), 4);
2101 assert_eq!(x[0], 1);
2102 assert_eq!(x[3], 4);
2104 let mut y: &mut [int] = [];
2105 assert!(y.mut_pop_ref().is_none());
2109 fn test_mut_last() {
2110 let mut x = [1, 2, 3, 4, 5];
2111 let h = x.mut_last();
2112 assert_eq!(*h.unwrap(), 5);
2114 let y: &mut [int] = [];
2115 assert!(y.mut_last().is_none());
2122 use self::test::Bencher;
2126 use rand::{weak_rng, Rng};
2129 fn iterator(b: &mut Bencher) {
2130 // peculiar numbers to stop LLVM from optimising the summation
2132 let v = Vec::from_fn(100, |i| i ^ (i << 1) ^ (i >> 1));
2139 // sum == 11806, to stop dead code elimination.
2140 if sum == 0 {fail!()}
2145 fn mut_iterator(b: &mut Bencher) {
2146 let mut v = Vec::from_elem(100, 0);
2150 for x in v.mut_iter() {
2158 fn concat(b: &mut Bencher) {
2159 let xss: Vec<Vec<uint>> = Vec::from_fn(100, |i| range(0, i).collect());
2161 xss.as_slice().concat_vec()
2166 fn connect(b: &mut Bencher) {
2167 let xss: Vec<Vec<uint>> = Vec::from_fn(100, |i| range(0, i).collect());
2169 xss.as_slice().connect_vec(&0)
2174 fn push(b: &mut Bencher) {
2175 let mut vec: Vec<uint> = vec![];
2183 fn starts_with_same_vector(b: &mut Bencher) {
2184 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
2186 vec.as_slice().starts_with(vec.as_slice())
2191 fn starts_with_single_element(b: &mut Bencher) {
2192 let vec: Vec<uint> = vec![0];
2194 vec.as_slice().starts_with(vec.as_slice())
2199 fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
2200 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
2201 let mut match_vec: Vec<uint> = Vec::from_fn(99, |i| i);
2204 vec.as_slice().starts_with(match_vec.as_slice())
2209 fn ends_with_same_vector(b: &mut Bencher) {
2210 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
2212 vec.as_slice().ends_with(vec.as_slice())
2217 fn ends_with_single_element(b: &mut Bencher) {
2218 let vec: Vec<uint> = vec![0];
2220 vec.as_slice().ends_with(vec.as_slice())
2225 fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
2226 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
2227 let mut match_vec: Vec<uint> = Vec::from_fn(100, |i| i);
2228 match_vec.as_mut_slice()[0] = 200;
2230 vec.as_slice().starts_with(match_vec.as_slice())
2235 fn contains_last_element(b: &mut Bencher) {
2236 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
2243 fn zero_1kb_from_elem(b: &mut Bencher) {
2245 Vec::from_elem(1024, 0u8)
2250 fn zero_1kb_set_memory(b: &mut Bencher) {
2252 let mut v: Vec<uint> = Vec::with_capacity(1024);
2254 let vp = v.as_mut_ptr();
2255 ptr::set_memory(vp, 0, 1024);
2263 fn zero_1kb_fixed_repeat(b: &mut Bencher) {
2270 fn zero_1kb_loop_set(b: &mut Bencher) {
2272 let mut v: Vec<uint> = Vec::with_capacity(1024);
2276 for i in range(0u, 1024) {
2283 fn zero_1kb_mut_iter(b: &mut Bencher) {
2285 let mut v = Vec::with_capacity(1024);
2289 for x in v.mut_iter() {
2297 fn random_inserts(b: &mut Bencher) {
2298 let mut rng = weak_rng();
2300 let mut v = Vec::from_elem(30, (0u, 0u));
2301 for _ in range(0, 100) {
2303 v.insert(rng.gen::<uint>() % (l + 1),
2309 fn random_removes(b: &mut Bencher) {
2310 let mut rng = weak_rng();
2312 let mut v = Vec::from_elem(130, (0u, 0u));
2313 for _ in range(0, 100) {
2315 v.remove(rng.gen::<uint>() % l);
2321 fn sort_random_small(b: &mut Bencher) {
2322 let mut rng = weak_rng();
2324 let mut v = rng.gen_vec::<u64>(5);
2325 v.as_mut_slice().sort();
2327 b.bytes = 5 * mem::size_of::<u64>() as u64;
2331 fn sort_random_medium(b: &mut Bencher) {
2332 let mut rng = weak_rng();
2334 let mut v = rng.gen_vec::<u64>(100);
2335 v.as_mut_slice().sort();
2337 b.bytes = 100 * mem::size_of::<u64>() as u64;
2341 fn sort_random_large(b: &mut Bencher) {
2342 let mut rng = weak_rng();
2344 let mut v = rng.gen_vec::<u64>(10000);
2345 v.as_mut_slice().sort();
2347 b.bytes = 10000 * mem::size_of::<u64>() as u64;
2351 fn sort_sorted(b: &mut Bencher) {
2352 let mut v = Vec::from_fn(10000, |i| i);
2356 b.bytes = (v.len() * mem::size_of_val(v.get(0))) as u64;
2359 type BigSortable = (u64,u64,u64,u64);
2362 fn sort_big_random_small(b: &mut Bencher) {
2363 let mut rng = weak_rng();
2365 let mut v = rng.gen_vec::<BigSortable>(5);
2368 b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
2372 fn sort_big_random_medium(b: &mut Bencher) {
2373 let mut rng = weak_rng();
2375 let mut v = rng.gen_vec::<BigSortable>(100);
2378 b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
2382 fn sort_big_random_large(b: &mut Bencher) {
2383 let mut rng = weak_rng();
2385 let mut v = rng.gen_vec::<BigSortable>(10000);
2388 b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
2392 fn sort_big_sorted(b: &mut Bencher) {
2393 let mut v = Vec::from_fn(10000u, |i| (i, i, i, i));
2397 b.bytes = (v.len() * mem::size_of_val(v.get(0))) as u64;