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 * `.rev_iter()` returns an iterator with the same values as `.iter()`,
85 but going in the reverse order, starting with the back element.
86 * `.mut_iter()` returns an iterator that allows modifying each value.
87 * `.move_iter()` converts an owned vector into an iterator that
88 moves out a value from the vector each iteration.
89 * Further iterators exist that split, chunk or permute the vector.
91 ## Function definitions
93 There are a number of free functions that create or take vectors, for example:
95 * Creating a vector, like `from_elem` and `from_fn`
96 * Creating a vector with a given size: `with_capacity`
97 * Modifying a vector and returning it, like `append`
98 * Operations on paired elements, like `unzip`.
106 use container::Container;
107 use cmp::{Eq, TotalOrd, Ordering, Less, Equal, Greater};
109 use default::Default;
112 use num::{CheckedAdd, Saturating, div_rem};
114 use option::{None, Option, Some};
117 use rt::global_heap::{malloc_raw, exchange_free};
118 use result::{Ok, Err};
123 use unstable::finally::try_finally;
124 use raw::{Repr, Slice};
125 use RawVec = raw::Vec;
129 * Converts a pointer to A into a slice of length 1 (without copying).
131 pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] {
133 transmute(Slice { data: s, len: 1 })
138 * Converts a pointer to A into a slice of length 1 (without copying).
140 pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] {
142 let ptr: *A = transmute(s);
143 transmute(Slice { data: ptr, len: 1 })
147 /// An iterator over the slices of a vector separated by elements that
148 /// match a predicate function.
149 pub struct Splits<'a, T> {
152 pred: |t: &T|: 'a -> bool,
156 impl<'a, T> Iterator<&'a [T]> for Splits<'a, T> {
158 fn next(&mut self) -> Option<&'a [T]> {
159 if self.finished { return None; }
162 self.finished = true;
166 match self.v.iter().position(|x| (self.pred)(x)) {
168 self.finished = true;
172 let ret = Some(self.v.slice(0, idx));
173 self.v = self.v.slice(idx + 1, self.v.len());
181 fn size_hint(&self) -> (uint, Option<uint>) {
185 // if the predicate doesn't match anything, we yield one slice
186 // if it matches every element, we yield N+1 empty slices where
187 // N is either the number of elements or the number of splits.
188 match (self.v.len(), self.n) {
189 (0,_) => (1, Some(1)),
190 (_,0) => (1, Some(1)),
191 (l,n) => (1, cmp::min(l,n).checked_add(&1u))
196 /// An iterator over the slices of a vector separated by elements that
197 /// match a predicate function, from back to front.
198 pub struct RevSplits<'a, T> {
201 pred: |t: &T|: 'a -> bool,
205 impl<'a, T> Iterator<&'a [T]> for RevSplits<'a, T> {
207 fn next(&mut self) -> Option<&'a [T]> {
208 if self.finished { return None; }
211 self.finished = true;
215 match self.v.iter().rposition(|x| (self.pred)(x)) {
217 self.finished = true;
221 let ret = Some(self.v.slice(idx + 1, self.v.len()));
222 self.v = self.v.slice(0, idx);
230 fn size_hint(&self) -> (uint, Option<uint>) {
234 match (self.v.len(), self.n) {
235 (0,_) => (1, Some(1)),
236 (_,0) => (1, Some(1)),
237 (l,n) => (1, cmp::min(l,n).checked_add(&1u))
242 // Functional utilities
244 #[allow(missing_doc)]
245 pub trait VectorVector<T> {
246 // FIXME #5898: calling these .concat and .connect conflicts with
247 // StrVector::con{cat,nect}, since they have generic contents.
248 /// Flattens a vector of vectors of T into a single vector of T.
249 fn concat_vec(&self) -> ~[T];
251 /// Concatenate a vector of vectors, placing a given separator between each.
252 fn connect_vec(&self, sep: &T) -> ~[T];
255 impl<'a, T: Clone, V: Vector<T>> VectorVector<T> for &'a [V] {
256 fn concat_vec(&self) -> ~[T] {
257 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
258 let mut result = Vec::with_capacity(size);
259 for v in self.iter() {
260 result.push_all(v.as_slice())
262 result.move_iter().collect()
265 fn connect_vec(&self, sep: &T) -> ~[T] {
266 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
267 let mut result = Vec::with_capacity(size + self.len());
268 let mut first = true;
269 for v in self.iter() {
270 if first { first = false } else { result.push(sep.clone()) }
271 result.push_all(v.as_slice())
273 result.move_iter().collect()
278 * Convert an iterator of pairs into a pair of vectors.
280 * Returns a tuple containing two vectors where the i-th element of the first
281 * vector contains the first element of the i-th tuple of the input iterator,
282 * and the i-th element of the second vector contains the second element
283 * of the i-th tuple of the input iterator.
285 pub fn unzip<T, U, V: Iterator<(T, U)>>(mut iter: V) -> (~[T], ~[U]) {
286 let (lo, _) = iter.size_hint();
287 let mut ts = Vec::with_capacity(lo);
288 let mut us = Vec::with_capacity(lo);
293 (ts.move_iter().collect(), us.move_iter().collect())
296 /// An Iterator that yields the element swaps needed to produce
297 /// a sequence of all possible permutations for an indexed sequence of
298 /// elements. Each permutation is only a single swap apart.
300 /// The Steinhaus–Johnson–Trotter algorithm is used.
302 /// Generates even and odd permutations alternately.
304 /// The last generated swap is always (0, 1), and it returns the
305 /// sequence to its initial order.
306 pub struct ElementSwaps {
307 sdir: ~[SizeDirection],
308 /// If true, emit the last swap that returns the sequence to initial state
314 /// Create an `ElementSwaps` iterator for a sequence of `length` elements
315 pub fn new(length: uint) -> ElementSwaps {
316 // Initialize `sdir` with a direction that position should move in
317 // (all negative at the beginning) and the `size` of the
318 // element (equal to the original index).
321 sdir: range(0, length)
322 .map(|i| SizeDirection{ size: i, dir: Neg })
329 enum Direction { Pos, Neg }
331 /// An Index and Direction together
332 struct SizeDirection {
337 impl Iterator<(uint, uint)> for ElementSwaps {
339 fn next(&mut self) -> Option<(uint, uint)> {
340 fn new_pos(i: uint, s: Direction) -> uint {
341 i + match s { Pos => 1, Neg => -1 }
344 // Find the index of the largest mobile element:
345 // The direction should point into the vector, and the
346 // swap should be with a smaller `size` element.
347 let max = self.sdir.iter().map(|&x| x).enumerate()
349 new_pos(i, sd.dir) < self.sdir.len() &&
350 self.sdir[new_pos(i, sd.dir)].size < sd.size)
351 .max_by(|&(_, sd)| sd.size);
354 let j = new_pos(i, sd.dir);
355 self.sdir.swap(i, j);
357 // Swap the direction of each larger SizeDirection
358 for x in self.sdir.mut_iter() {
359 if x.size > sd.size {
360 x.dir = match x.dir { Pos => Neg, Neg => Pos };
363 self.swaps_made += 1;
366 None => if self.emit_reset {
367 self.emit_reset = false;
368 if self.sdir.len() > 1 {
370 self.swaps_made += 1;
373 // Vector is of the form [] or [x], and the only permutation is itself
374 self.swaps_made += 1;
382 fn size_hint(&self) -> (uint, Option<uint>) {
383 // For a vector of size n, there are exactly n! permutations.
384 let n = range(2, self.sdir.len() + 1).product();
385 (n - self.swaps_made, Some(n - self.swaps_made))
389 /// An Iterator that uses `ElementSwaps` to iterate through
390 /// all possible permutations of a vector.
392 /// The first iteration yields a clone of the vector as it is,
393 /// then each successive element is the vector with one
396 /// Generates even and odd permutations alternately.
397 pub struct Permutations<T> {
402 impl<T: Clone> Iterator<~[T]> for Permutations<T> {
404 fn next(&mut self) -> Option<~[T]> {
405 match self.swaps.next() {
407 Some((0,0)) => Some(self.v.clone()),
409 let elt = self.v.clone();
417 fn size_hint(&self) -> (uint, Option<uint>) {
418 self.swaps.size_hint()
422 /// An iterator over the (overlapping) slices of length `size` within
425 pub struct Windows<'a, T> {
430 impl<'a, T> Iterator<&'a [T]> for Windows<'a, T> {
432 fn next(&mut self) -> Option<&'a [T]> {
433 if self.size > self.v.len() {
436 let ret = Some(self.v.slice(0, self.size));
437 self.v = self.v.slice(1, self.v.len());
443 fn size_hint(&self) -> (uint, Option<uint>) {
444 if self.size > self.v.len() {
447 let x = self.v.len() - self.size;
448 (x.saturating_add(1), x.checked_add(&1u))
453 /// An iterator over a vector in (non-overlapping) chunks (`size`
454 /// elements at a time).
456 /// When the vector len is not evenly divided by the chunk size,
457 /// the last slice of the iteration will be the remainder.
459 pub struct Chunks<'a, T> {
464 impl<'a, T> Iterator<&'a [T]> for Chunks<'a, T> {
466 fn next(&mut self) -> Option<&'a [T]> {
467 if self.v.len() == 0 {
470 let chunksz = cmp::min(self.v.len(), self.size);
471 let (fst, snd) = (self.v.slice_to(chunksz),
472 self.v.slice_from(chunksz));
479 fn size_hint(&self) -> (uint, Option<uint>) {
480 if self.v.len() == 0 {
483 let (n, rem) = div_rem(self.v.len(), self.size);
484 let n = if rem > 0 { n+1 } else { n };
490 impl<'a, T> DoubleEndedIterator<&'a [T]> for Chunks<'a, T> {
492 fn next_back(&mut self) -> Option<&'a [T]> {
493 if self.v.len() == 0 {
496 let remainder = self.v.len() % self.size;
497 let chunksz = if remainder != 0 { remainder } else { self.size };
498 let (fst, snd) = (self.v.slice_to(self.v.len() - chunksz),
499 self.v.slice_from(self.v.len() - chunksz));
506 impl<'a, T> RandomAccessIterator<&'a [T]> for Chunks<'a, T> {
508 fn indexable(&self) -> uint {
509 self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
513 fn idx(&mut self, index: uint) -> Option<&'a [T]> {
514 if index < self.indexable() {
515 let lo = index * self.size;
516 let mut hi = lo + self.size;
517 if hi < lo || hi > self.v.len() { hi = self.v.len(); }
519 Some(self.v.slice(lo, hi))
529 #[allow(missing_doc)]
533 use container::Container;
535 use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Equiv};
536 use iter::{order, Iterator};
540 impl<'a,T:Eq> Eq for &'a [T] {
541 fn eq(&self, other: & &'a [T]) -> bool {
542 self.len() == other.len() &&
543 order::eq(self.iter(), other.iter())
545 fn ne(&self, other: & &'a [T]) -> bool {
546 self.len() != other.len() ||
547 order::ne(self.iter(), other.iter())
551 impl<T:Eq> Eq for ~[T] {
553 fn eq(&self, other: &~[T]) -> bool { self.as_slice() == *other }
555 fn ne(&self, other: &~[T]) -> bool { !self.eq(other) }
558 impl<'a,T:TotalEq> TotalEq for &'a [T] {}
560 impl<T:TotalEq> TotalEq for ~[T] {}
562 impl<'a,T:Eq, V: Vector<T>> Equiv<V> for &'a [T] {
564 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
567 impl<'a,T:Eq, V: Vector<T>> Equiv<V> for ~[T] {
569 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
572 impl<'a,T:TotalOrd> TotalOrd for &'a [T] {
573 fn cmp(&self, other: & &'a [T]) -> Ordering {
574 order::cmp(self.iter(), other.iter())
578 impl<T: TotalOrd> TotalOrd for ~[T] {
580 fn cmp(&self, other: &~[T]) -> Ordering { self.as_slice().cmp(&other.as_slice()) }
583 impl<'a, T: Ord> Ord for &'a [T] {
584 fn lt(&self, other: & &'a [T]) -> bool {
585 order::lt(self.iter(), other.iter())
588 fn le(&self, other: & &'a [T]) -> bool {
589 order::le(self.iter(), other.iter())
592 fn ge(&self, other: & &'a [T]) -> bool {
593 order::ge(self.iter(), other.iter())
596 fn gt(&self, other: & &'a [T]) -> bool {
597 order::gt(self.iter(), other.iter())
601 impl<T: Ord> Ord for ~[T] {
603 fn lt(&self, other: &~[T]) -> bool { self.as_slice() < other.as_slice() }
605 fn le(&self, other: &~[T]) -> bool { self.as_slice() <= other.as_slice() }
607 fn ge(&self, other: &~[T]) -> bool { self.as_slice() >= other.as_slice() }
609 fn gt(&self, other: &~[T]) -> bool { self.as_slice() > other.as_slice() }
612 impl<'a,T:Clone, V: Vector<T>> Add<V, ~[T]> for &'a [T] {
614 fn add(&self, rhs: &V) -> ~[T] {
615 let mut res = Vec::with_capacity(self.len() + rhs.as_slice().len());
617 res.push_all(rhs.as_slice());
618 res.move_iter().collect()
622 impl<T:Clone, V: Vector<T>> Add<V, ~[T]> for ~[T] {
624 fn add(&self, rhs: &V) -> ~[T] {
625 self.as_slice() + rhs.as_slice()
633 /// Any vector that can be represented as a slice.
634 pub trait Vector<T> {
635 /// Work with `self` as a slice.
636 fn as_slice<'a>(&'a self) -> &'a [T];
639 impl<'a,T> Vector<T> for &'a [T] {
641 fn as_slice<'a>(&'a self) -> &'a [T] { *self }
644 impl<T> Vector<T> for ~[T] {
646 fn as_slice<'a>(&'a self) -> &'a [T] { let v: &'a [T] = *self; v }
649 impl<'a, T> Container for &'a [T] {
650 /// Returns the length of a vector
652 fn len(&self) -> uint {
657 impl<T> Container for ~[T] {
658 /// Returns the length of a vector
660 fn len(&self) -> uint {
661 self.as_slice().len()
665 /// Extension methods for vector slices with cloneable elements
666 pub trait CloneableVector<T> {
667 /// Copy `self` into a new owned vector
668 fn to_owned(&self) -> ~[T];
670 /// Convert `self` into an owned vector, not making a copy if possible.
671 fn into_owned(self) -> ~[T];
674 /// Extension methods for vector slices
675 impl<'a, T: Clone> CloneableVector<T> for &'a [T] {
676 /// Returns a copy of `v`.
678 fn to_owned(&self) -> ~[T] {
679 let len = self.len();
680 let mut result = Vec::with_capacity(len);
681 // Unsafe code so this can be optimised to a memcpy (or something
682 // similarly fast) when T is Copy. LLVM is easily confused, so any
683 // extra operations during the loop can prevent this optimisation
686 let p = result.as_mut_ptr();
687 // Use try_finally here otherwise the write to length
688 // inside the loop stops LLVM from optimising this.
691 |i, ()| while *i < len {
693 &mut(*p.offset(*i as int)),
694 self.unsafe_ref(*i).clone());
697 |i| result.set_len(*i));
699 result.move_iter().collect()
703 fn into_owned(self) -> ~[T] { self.to_owned() }
706 /// Extension methods for owned vectors
707 impl<T: Clone> CloneableVector<T> for ~[T] {
709 fn to_owned(&self) -> ~[T] { self.clone() }
712 fn into_owned(self) -> ~[T] { self }
715 /// Extension methods for vectors
716 pub trait ImmutableVector<'a, T> {
718 * Returns a slice of self between `start` and `end`.
720 * Fails when `start` or `end` point outside the bounds of self,
721 * or when `start` > `end`.
723 fn slice(&self, start: uint, end: uint) -> &'a [T];
726 * Returns a slice of self from `start` to the end of the vec.
728 * Fails when `start` points outside the bounds of self.
730 fn slice_from(&self, start: uint) -> &'a [T];
733 * Returns a slice of self from the start of the vec to `end`.
735 * Fails when `end` points outside the bounds of self.
737 fn slice_to(&self, end: uint) -> &'a [T];
738 /// Returns an iterator over the vector
739 fn iter(self) -> Items<'a, T>;
740 /// Returns a reversed iterator over a vector
741 fn rev_iter(self) -> RevItems<'a, T>;
742 /// Returns an iterator over the subslices of the vector which are
743 /// separated by elements that match `pred`. The matched element
744 /// is not contained in the subslices.
745 fn split(self, pred: |&T|: 'a -> bool) -> Splits<'a, T>;
746 /// Returns an iterator over the subslices of the vector which are
747 /// separated by elements that match `pred`, limited to splitting
748 /// at most `n` times. The matched element is not contained in
750 fn splitn(self, n: uint, pred: |&T|: 'a -> bool) -> Splits<'a, T>;
751 /// Returns an iterator over the subslices of the vector which are
752 /// separated by elements that match `pred`. This starts at the
753 /// end of the vector and works backwards. The matched element is
754 /// not contained in the subslices.
755 fn rsplit(self, pred: |&T|: 'a -> bool) -> RevSplits<'a, T>;
756 /// Returns an iterator over the subslices of the vector which are
757 /// separated by elements that match `pred` limited to splitting
758 /// at most `n` times. This starts at the end of the vector and
759 /// works backwards. The matched element is not contained in the
761 fn rsplitn(self, n: uint, pred: |&T|: 'a -> bool) -> RevSplits<'a, T>;
764 * Returns an iterator over all contiguous windows of length
765 * `size`. The windows overlap. If the vector is shorter than
766 * `size`, the iterator returns no values.
770 * Fails if `size` is 0.
774 * Print the adjacent pairs of a vector (i.e. `[1,2]`, `[2,3]`,
778 * let v = &[1,2,3,4];
779 * for win in v.windows(2) {
780 * println!("{:?}", win);
785 fn windows(self, size: uint) -> Windows<'a, T>;
788 * Returns an iterator over `size` elements of the vector at a
789 * time. The chunks do not overlap. If `size` does not divide the
790 * length of the vector, then the last chunk will not have length
795 * Fails if `size` is 0.
799 * Print the vector two elements at a time (i.e. `[1,2]`,
803 * let v = &[1,2,3,4,5];
804 * for win in v.chunks(2) {
805 * println!("{:?}", win);
810 fn chunks(self, size: uint) -> Chunks<'a, T>;
812 /// Returns the element of a vector at the given index, or `None` if the
813 /// index is out of bounds
814 fn get(&self, index: uint) -> Option<&'a T>;
815 /// Returns the first element of a vector, or `None` if it is empty
816 fn head(&self) -> Option<&'a T>;
817 /// Returns all but the first element of a vector
818 fn tail(&self) -> &'a [T];
819 /// Returns all but the first `n' elements of a vector
820 fn tailn(&self, n: uint) -> &'a [T];
821 /// Returns all but the last element of a vector
822 fn init(&self) -> &'a [T];
823 /// Returns all but the last `n' elements of a vector
824 fn initn(&self, n: uint) -> &'a [T];
825 /// Returns the last element of a vector, or `None` if it is empty.
826 fn last(&self) -> Option<&'a T>;
828 /// Returns a pointer to the element at the given index, without doing
830 unsafe fn unsafe_ref(self, index: uint) -> &'a T;
833 * Returns an unsafe pointer to the vector's buffer
835 * The caller must ensure that the vector outlives the pointer this
836 * function returns, or else it will end up pointing to garbage.
838 * Modifying the vector may cause its buffer to be reallocated, which
839 * would also make any pointers to it invalid.
841 fn as_ptr(&self) -> *T;
844 * Binary search a sorted vector with a comparator function.
846 * The comparator function should implement an order consistent
847 * with the sort order of the underlying vector, returning an
848 * order code that indicates whether its argument is `Less`,
849 * `Equal` or `Greater` the desired target.
851 * Returns the index where the comparator returned `Equal`, or `None` if
854 fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint>;
857 * Returns a mutable reference to the first element in this slice
858 * and adjusts the slice in place so that it no longer contains
859 * that element. O(1).
864 * if self.len() == 0 { return None }
865 * let head = &self[0];
866 * *self = self.slice_from(1);
870 * Returns `None` if vector is empty
872 fn shift_ref(&mut self) -> Option<&'a T>;
875 * Returns a mutable reference to the last element in this slice
876 * and adjusts the slice in place so that it no longer contains
877 * that element. O(1).
882 * if self.len() == 0 { return None; }
883 * let tail = &self[self.len() - 1];
884 * *self = self.slice_to(self.len() - 1);
888 * Returns `None` if slice is empty.
890 fn pop_ref(&mut self) -> Option<&'a T>;
893 impl<'a,T> ImmutableVector<'a, T> for &'a [T] {
895 fn slice(&self, start: uint, end: uint) -> &'a [T] {
896 assert!(start <= end);
897 assert!(end <= self.len());
900 data: self.as_ptr().offset(start as int),
907 fn slice_from(&self, start: uint) -> &'a [T] {
908 self.slice(start, self.len())
912 fn slice_to(&self, end: uint) -> &'a [T] {
917 fn iter(self) -> Items<'a, T> {
919 let p = self.as_ptr();
920 if mem::size_of::<T>() == 0 {
922 end: (p as uint + self.len()) as *T,
923 marker: marker::ContravariantLifetime::<'a>}
926 end: p.offset(self.len() as int),
927 marker: marker::ContravariantLifetime::<'a>}
933 fn rev_iter(self) -> RevItems<'a, T> {
938 fn split(self, pred: |&T|: 'a -> bool) -> Splits<'a, T> {
939 self.splitn(uint::MAX, pred)
943 fn splitn(self, n: uint, pred: |&T|: 'a -> bool) -> Splits<'a, T> {
953 fn rsplit(self, pred: |&T|: 'a -> bool) -> RevSplits<'a, T> {
954 self.rsplitn(uint::MAX, pred)
958 fn rsplitn(self, n: uint, pred: |&T|: 'a -> bool) -> RevSplits<'a, T> {
968 fn windows(self, size: uint) -> Windows<'a, T> {
970 Windows { v: self, size: size }
974 fn chunks(self, size: uint) -> Chunks<'a, T> {
976 Chunks { v: self, size: size }
980 fn get(&self, index: uint) -> Option<&'a T> {
981 if index < self.len() { Some(&self[index]) } else { None }
985 fn head(&self) -> Option<&'a T> {
986 if self.len() == 0 { None } else { Some(&self[0]) }
990 fn tail(&self) -> &'a [T] { self.slice(1, self.len()) }
993 fn tailn(&self, n: uint) -> &'a [T] { self.slice(n, self.len()) }
996 fn init(&self) -> &'a [T] {
997 self.slice(0, self.len() - 1)
1001 fn initn(&self, n: uint) -> &'a [T] {
1002 self.slice(0, self.len() - n)
1006 fn last(&self) -> Option<&'a T> {
1007 if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
1011 unsafe fn unsafe_ref(self, index: uint) -> &'a T {
1012 transmute(self.repr().data.offset(index as int))
1016 fn as_ptr(&self) -> *T {
1021 fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint> {
1022 let mut base : uint = 0;
1023 let mut lim : uint = self.len();
1026 let ix = base + (lim >> 1);
1027 match f(&self[ix]) {
1028 Equal => return Some(ix),
1040 fn shift_ref(&mut self) -> Option<&'a T> {
1041 if self.len() == 0 { return None; }
1043 let s: &mut Slice<T> = transmute(self);
1044 Some(&*raw::shift_ptr(s))
1048 fn pop_ref(&mut self) -> Option<&'a T> {
1049 if self.len() == 0 { return None; }
1051 let s: &mut Slice<T> = transmute(self);
1052 Some(&*raw::pop_ptr(s))
1057 /// Extension methods for vectors contain `Eq` elements.
1058 pub trait ImmutableEqVector<T:Eq> {
1059 /// Find the first index containing a matching value
1060 fn position_elem(&self, t: &T) -> Option<uint>;
1062 /// Find the last index containing a matching value
1063 fn rposition_elem(&self, t: &T) -> Option<uint>;
1065 /// Return true if a vector contains an element with the given value
1066 fn contains(&self, x: &T) -> bool;
1068 /// Returns true if `needle` is a prefix of the vector.
1069 fn starts_with(&self, needle: &[T]) -> bool;
1071 /// Returns true if `needle` is a suffix of the vector.
1072 fn ends_with(&self, needle: &[T]) -> bool;
1075 impl<'a,T:Eq> ImmutableEqVector<T> for &'a [T] {
1077 fn position_elem(&self, x: &T) -> Option<uint> {
1078 self.iter().position(|y| *x == *y)
1082 fn rposition_elem(&self, t: &T) -> Option<uint> {
1083 self.iter().rposition(|x| *x == *t)
1087 fn contains(&self, x: &T) -> bool {
1088 self.iter().any(|elt| *x == *elt)
1092 fn starts_with(&self, needle: &[T]) -> bool {
1093 let n = needle.len();
1094 self.len() >= n && needle == self.slice_to(n)
1098 fn ends_with(&self, needle: &[T]) -> bool {
1099 let (m, n) = (self.len(), needle.len());
1100 m >= n && needle == self.slice_from(m - n)
1104 /// Extension methods for vectors containing `TotalOrd` elements.
1105 pub trait ImmutableTotalOrdVector<T: TotalOrd> {
1107 * Binary search a sorted vector for a given element.
1109 * Returns the index of the element or None if not found.
1111 fn bsearch_elem(&self, x: &T) -> Option<uint>;
1114 impl<'a, T: TotalOrd> ImmutableTotalOrdVector<T> for &'a [T] {
1115 fn bsearch_elem(&self, x: &T) -> Option<uint> {
1116 self.bsearch(|p| p.cmp(x))
1120 /// Extension methods for vectors containing `Clone` elements.
1121 pub trait ImmutableCloneableVector<T> {
1122 /// Partitions the vector into two vectors `(A,B)`, where all
1123 /// elements of `A` satisfy `f` and all elements of `B` do not.
1124 fn partitioned(&self, f: |&T| -> bool) -> (~[T], ~[T]);
1126 /// Create an iterator that yields every possible permutation of the
1127 /// vector in succession.
1128 fn permutations(self) -> Permutations<T>;
1131 impl<'a,T:Clone> ImmutableCloneableVector<T> for &'a [T] {
1133 fn partitioned(&self, f: |&T| -> bool) -> (~[T], ~[T]) {
1134 let mut lefts = Vec::new();
1135 let mut rights = Vec::new();
1137 for elt in self.iter() {
1139 lefts.push((*elt).clone());
1141 rights.push((*elt).clone());
1145 (lefts.move_iter().collect(), rights.move_iter().collect())
1148 fn permutations(self) -> Permutations<T> {
1150 swaps: ElementSwaps::new(self.len()),
1157 /// Extension methods for owned vectors.
1158 pub trait OwnedVector<T> {
1159 /// Creates a consuming iterator, that is, one that moves each
1160 /// value out of the vector (from start to end). The vector cannot
1161 /// be used after calling this.
1166 /// let v = ~["a".to_owned(), "b".to_owned()];
1167 /// for s in v.move_iter() {
1168 /// // s has type ~str, not &~str
1169 /// println!("{}", s);
1172 fn move_iter(self) -> MoveItems<T>;
1173 /// Creates a consuming iterator that moves out of the vector in
1175 fn move_rev_iter(self) -> RevMoveItems<T>;
1178 * Partitions the vector into two vectors `(A,B)`, where all
1179 * elements of `A` satisfy `f` and all elements of `B` do not.
1181 fn partition(self, f: |&T| -> bool) -> (~[T], ~[T]);
1184 impl<T> OwnedVector<T> for ~[T] {
1186 fn move_iter(self) -> MoveItems<T> {
1188 let iter = transmute(self.iter());
1189 let ptr = transmute(self);
1190 MoveItems { allocation: ptr, iter: iter }
1195 fn move_rev_iter(self) -> RevMoveItems<T> {
1196 self.move_iter().rev()
1200 fn partition(self, f: |&T| -> bool) -> (~[T], ~[T]) {
1201 let mut lefts = Vec::new();
1202 let mut rights = Vec::new();
1204 for elt in self.move_iter() {
1212 (lefts.move_iter().collect(), rights.move_iter().collect())
1216 fn insertion_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
1217 let len = v.len() as int;
1218 let buf_v = v.as_mut_ptr();
1221 for i in range(1, len) {
1222 // j satisfies: 0 <= j <= i;
1225 // `i` is in bounds.
1226 let read_ptr = buf_v.offset(i) as *T;
1228 // find where to insert, we need to do strict <,
1229 // rather than <=, to maintain stability.
1231 // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
1233 compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less {
1237 // shift everything to the right, to make space to
1238 // insert this value.
1240 // j + 1 could be `len` (for the last `i`), but in
1241 // that case, `i == j` so we don't copy. The
1242 // `.offset(j)` is always in bounds.
1245 let tmp = ptr::read(read_ptr);
1246 ptr::copy_memory(buf_v.offset(j + 1),
1249 ptr::copy_nonoverlapping_memory(buf_v.offset(j),
1258 fn merge_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
1259 // warning: this wildly uses unsafe.
1260 static BASE_INSERTION: uint = 32;
1261 static LARGE_INSERTION: uint = 16;
1263 // FIXME #12092: smaller insertion runs seems to make sorting
1264 // vectors of large elements a little faster on some platforms,
1265 // but hasn't been tested/tuned extensively
1266 let insertion = if size_of::<T>() <= 16 {
1274 // short vectors get sorted in-place via insertion sort to avoid allocations
1275 if len <= insertion {
1276 insertion_sort(v, compare);
1280 // allocate some memory to use as scratch memory, we keep the
1281 // length 0 so we can keep shallow copies of the contents of `v`
1282 // without risking the dtors running on an object twice if
1284 let mut working_space = Vec::with_capacity(2 * len);
1285 // these both are buffers of length `len`.
1286 let mut buf_dat = working_space.as_mut_ptr();
1287 let mut buf_tmp = unsafe {buf_dat.offset(len as int)};
1290 let buf_v = v.as_ptr();
1292 // step 1. sort short runs with insertion sort. This takes the
1293 // values from `v` and sorts them into `buf_dat`, leaving that
1294 // with sorted runs of length INSERTION.
1296 // We could hardcode the sorting comparisons here, and we could
1297 // manipulate/step the pointers themselves, rather than repeatedly
1299 for start in range_step(0, len, insertion) {
1300 // start <= i < len;
1301 for i in range(start, cmp::min(start + insertion, len)) {
1302 // j satisfies: start <= j <= i;
1303 let mut j = i as int;
1305 // `i` is in bounds.
1306 let read_ptr = buf_v.offset(i as int);
1308 // find where to insert, we need to do strict <,
1309 // rather than <=, to maintain stability.
1311 // start <= j - 1 < len, so .offset(j - 1) is in
1313 while j > start as int &&
1314 compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less {
1318 // shift everything to the right, to make space to
1319 // insert this value.
1321 // j + 1 could be `len` (for the last `i`), but in
1322 // that case, `i == j` so we don't copy. The
1323 // `.offset(j)` is always in bounds.
1324 ptr::copy_memory(buf_dat.offset(j + 1),
1325 &*buf_dat.offset(j),
1327 ptr::copy_nonoverlapping_memory(buf_dat.offset(j), read_ptr, 1);
1332 // step 2. merge the sorted runs.
1333 let mut width = insertion;
1335 // merge the sorted runs of length `width` in `buf_dat` two at
1336 // a time, placing the result in `buf_tmp`.
1338 // 0 <= start <= len.
1339 for start in range_step(0, len, 2 * width) {
1340 // manipulate pointers directly for speed (rather than
1341 // using a `for` loop with `range` and `.offset` inside
1344 // the end of the first run & start of the
1345 // second. Offset of `len` is defined, since this is
1346 // precisely one byte past the end of the object.
1347 let right_start = buf_dat.offset(cmp::min(start + width, len) as int);
1348 // end of the second. Similar reasoning to the above re safety.
1349 let right_end_idx = cmp::min(start + 2 * width, len);
1350 let right_end = buf_dat.offset(right_end_idx as int);
1352 // the pointers to the elements under consideration
1353 // from the two runs.
1355 // both of these are in bounds.
1356 let mut left = buf_dat.offset(start as int);
1357 let mut right = right_start;
1359 // where we're putting the results, it is a run of
1360 // length `2*width`, so we step it once for each step
1361 // of either `left` or `right`. `buf_tmp` has length
1362 // `len`, so these are in bounds.
1363 let mut out = buf_tmp.offset(start as int);
1364 let out_end = buf_tmp.offset(right_end_idx as int);
1366 while out < out_end {
1367 // Either the left or the right run are exhausted,
1368 // so just copy the remainder from the other run
1369 // and move on; this gives a huge speed-up (order
1370 // of 25%) for mostly sorted vectors (the best
1372 if left == right_start {
1373 // the number remaining in this run.
1374 let elems = (right_end as uint - right as uint) / mem::size_of::<T>();
1375 ptr::copy_nonoverlapping_memory(out, &*right, elems);
1377 } else if right == right_end {
1378 let elems = (right_start as uint - left as uint) / mem::size_of::<T>();
1379 ptr::copy_nonoverlapping_memory(out, &*left, elems);
1383 // check which side is smaller, and that's the
1384 // next element for the new run.
1386 // `left < right_start` and `right < right_end`,
1387 // so these are valid.
1388 let to_copy = if compare(&*left, &*right) == Greater {
1393 ptr::copy_nonoverlapping_memory(out, &*to_copy, 1);
1399 mem::swap(&mut buf_dat, &mut buf_tmp);
1404 // write the result to `v` in one go, so that there are never two copies
1405 // of the same object in `v`.
1407 ptr::copy_nonoverlapping_memory(v.as_mut_ptr(), &*buf_dat, len);
1410 // increment the pointer, returning the old pointer.
1412 unsafe fn step<T>(ptr: &mut *mut T) -> *mut T {
1414 *ptr = ptr.offset(1);
1419 /// Extension methods for vectors such that their elements are
1421 pub trait MutableVector<'a, T> {
1422 /// Work with `self` as a mut slice.
1423 /// Primarily intended for getting a &mut [T] from a [T, ..N].
1424 fn as_mut_slice(self) -> &'a mut [T];
1426 /// Return a slice that points into another slice.
1427 fn mut_slice(self, start: uint, end: uint) -> &'a mut [T];
1430 * Returns a slice of self from `start` to the end of the vec.
1432 * Fails when `start` points outside the bounds of self.
1434 fn mut_slice_from(self, start: uint) -> &'a mut [T];
1437 * Returns a slice of self from the start of the vec to `end`.
1439 * Fails when `end` points outside the bounds of self.
1441 fn mut_slice_to(self, end: uint) -> &'a mut [T];
1443 /// Returns an iterator that allows modifying each value
1444 fn mut_iter(self) -> MutItems<'a, T>;
1446 /// Returns a mutable pointer to the last item in the vector.
1447 fn mut_last(self) -> Option<&'a mut T>;
1449 /// Returns a reversed iterator that allows modifying each value
1450 fn mut_rev_iter(self) -> RevMutItems<'a, T>;
1452 /// Returns an iterator over the mutable subslices of the vector
1453 /// which are separated by elements that match `pred`. The
1454 /// matched element is not contained in the subslices.
1455 fn mut_split(self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T>;
1458 * Returns an iterator over `size` elements of the vector at a time.
1459 * The chunks are mutable and do not overlap. If `size` does not divide the
1460 * length of the vector, then the last chunk will not have length
1465 * Fails if `size` is 0.
1467 fn mut_chunks(self, chunk_size: uint) -> MutChunks<'a, T>;
1470 * Returns a mutable reference to the first element in this slice
1471 * and adjusts the slice in place so that it no longer contains
1472 * that element. O(1).
1477 * if self.len() == 0 { return None; }
1478 * let head = &mut self[0];
1479 * *self = self.mut_slice_from(1);
1483 * Returns `None` if slice is empty
1485 fn mut_shift_ref(&mut self) -> Option<&'a mut T>;
1488 * Returns a mutable reference to the last element in this slice
1489 * and adjusts the slice in place so that it no longer contains
1490 * that element. O(1).
1495 * if self.len() == 0 { return None; }
1496 * let tail = &mut self[self.len() - 1];
1497 * *self = self.mut_slice_to(self.len() - 1);
1501 * Returns `None` if slice is empty.
1503 fn mut_pop_ref(&mut self) -> Option<&'a mut T>;
1505 /// Swaps two elements in a vector.
1507 /// Fails if `a` or `b` are out of bounds.
1511 /// * a - The index of the first element
1512 /// * b - The index of the second element
1517 /// let mut v = ["a", "b", "c", "d"];
1519 /// assert!(v == ["a", "d", "c", "b"]);
1521 fn swap(self, a: uint, b: uint);
1524 /// Divides one `&mut` into two at an index.
1526 /// The first will contain all indices from `[0, mid)` (excluding
1527 /// the index `mid` itself) and the second will contain all
1528 /// indices from `[mid, len)` (excluding the index `len` itself).
1530 /// Fails if `mid > len`.
1535 /// let mut v = [1, 2, 3, 4, 5, 6];
1537 /// // scoped to restrict the lifetime of the borrows
1539 /// let (left, right) = v.mut_split_at(0);
1540 /// assert!(left == &mut []);
1541 /// assert!(right == &mut [1, 2, 3, 4, 5, 6]);
1545 /// let (left, right) = v.mut_split_at(2);
1546 /// assert!(left == &mut [1, 2]);
1547 /// assert!(right == &mut [3, 4, 5, 6]);
1551 /// let (left, right) = v.mut_split_at(6);
1552 /// assert!(left == &mut [1, 2, 3, 4, 5, 6]);
1553 /// assert!(right == &mut []);
1556 fn mut_split_at(self, mid: uint) -> (&'a mut [T], &'a mut [T]);
1558 /// Reverse the order of elements in a vector, in place.
1563 /// let mut v = [1, 2, 3];
1565 /// assert!(v == [3, 2, 1]);
1569 /// Sort the vector, in place, using `compare` to compare
1572 /// This sort is `O(n log n)` worst-case and stable, but allocates
1573 /// approximately `2 * n`, where `n` is the length of `self`.
1578 /// let mut v = [5i, 4, 1, 3, 2];
1579 /// v.sort_by(|a, b| a.cmp(b));
1580 /// assert!(v == [1, 2, 3, 4, 5]);
1582 /// // reverse sorting
1583 /// v.sort_by(|a, b| b.cmp(a));
1584 /// assert!(v == [5, 4, 3, 2, 1]);
1586 fn sort_by(self, compare: |&T, &T| -> Ordering);
1589 * Consumes `src` and moves as many elements as it can into `self`
1590 * from the range [start,end).
1592 * Returns the number of elements copied (the shorter of self.len()
1597 * * src - A mutable vector of `T`
1598 * * start - The index into `src` to start copying from
1599 * * end - The index into `str` to stop copying from
1601 fn move_from(self, src: ~[T], start: uint, end: uint) -> uint;
1603 /// Returns an unsafe mutable pointer to the element in index
1604 unsafe fn unsafe_mut_ref(self, index: uint) -> &'a mut T;
1606 /// Return an unsafe mutable pointer to the vector's buffer.
1608 /// The caller must ensure that the vector outlives the pointer this
1609 /// function returns, or else it will end up pointing to garbage.
1611 /// Modifying the vector may cause its buffer to be reallocated, which
1612 /// would also make any pointers to it invalid.
1614 fn as_mut_ptr(self) -> *mut T;
1616 /// Unsafely sets the element in index to the value.
1618 /// This performs no bounds checks, and it is undefined behaviour
1619 /// if `index` is larger than the length of `self`. However, it
1620 /// does run the destructor at `index`. It is equivalent to
1621 /// `self[index] = val`.
1626 /// let mut v = ~["foo".to_owned(), "bar".to_owned(), "baz".to_owned()];
1629 /// // `"baz".to_owned()` is deallocated.
1630 /// v.unsafe_set(2, "qux".to_owned());
1632 /// // Out of bounds: could cause a crash, or overwriting
1633 /// // other data, or something else.
1634 /// // v.unsafe_set(10, "oops".to_owned());
1637 unsafe fn unsafe_set(self, index: uint, val: T);
1639 /// Unchecked vector index assignment. Does not drop the
1640 /// old value and hence is only suitable when the vector
1641 /// is newly allocated.
1646 /// let mut v = ["foo".to_owned(), "bar".to_owned()];
1648 /// // memory leak! `"bar".to_owned()` is not deallocated.
1649 /// unsafe { v.init_elem(1, "baz".to_owned()); }
1651 unsafe fn init_elem(self, i: uint, val: T);
1653 /// Copies raw bytes from `src` to `self`.
1655 /// This does not run destructors on the overwritten elements, and
1656 /// ignores move semantics. `self` and `src` must not
1657 /// overlap. Fails if `self` is shorter than `src`.
1658 unsafe fn copy_memory(self, src: &[T]);
1661 impl<'a,T> MutableVector<'a, T> for &'a mut [T] {
1663 fn as_mut_slice(self) -> &'a mut [T] { self }
1665 fn mut_slice(self, start: uint, end: uint) -> &'a mut [T] {
1666 assert!(start <= end);
1667 assert!(end <= self.len());
1670 data: self.as_mut_ptr().offset(start as int) as *T,
1677 fn mut_slice_from(self, start: uint) -> &'a mut [T] {
1678 let len = self.len();
1679 self.mut_slice(start, len)
1683 fn mut_slice_to(self, end: uint) -> &'a mut [T] {
1684 self.mut_slice(0, end)
1688 fn mut_split_at(self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
1690 let len = self.len();
1691 let self2: &'a mut [T] = cast::transmute_copy(&self);
1692 (self.mut_slice(0, mid), self2.mut_slice(mid, len))
1697 fn mut_iter(self) -> MutItems<'a, T> {
1699 let p = self.as_mut_ptr();
1700 if mem::size_of::<T>() == 0 {
1702 end: (p as uint + self.len()) as *mut T,
1703 marker: marker::ContravariantLifetime::<'a>,
1704 marker2: marker::NoCopy}
1707 end: p.offset(self.len() as int),
1708 marker: marker::ContravariantLifetime::<'a>,
1709 marker2: marker::NoCopy}
1715 fn mut_last(self) -> Option<&'a mut T> {
1716 let len = self.len();
1717 if len == 0 { return None; }
1718 Some(&mut self[len - 1])
1722 fn mut_rev_iter(self) -> RevMutItems<'a, T> {
1723 self.mut_iter().rev()
1727 fn mut_split(self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T> {
1728 MutSplits { v: self, pred: pred, finished: false }
1732 fn mut_chunks(self, chunk_size: uint) -> MutChunks<'a, T> {
1733 assert!(chunk_size > 0);
1734 MutChunks { v: self, chunk_size: chunk_size }
1737 fn mut_shift_ref(&mut self) -> Option<&'a mut T> {
1738 if self.len() == 0 { return None; }
1740 let s: &mut Slice<T> = transmute(self);
1741 Some(cast::transmute_mut(&*raw::shift_ptr(s)))
1745 fn mut_pop_ref(&mut self) -> Option<&'a mut T> {
1746 if self.len() == 0 { return None; }
1748 let s: &mut Slice<T> = transmute(self);
1749 Some(cast::transmute_mut(&*raw::pop_ptr(s)))
1753 fn swap(self, a: uint, b: uint) {
1755 // Can't take two mutable loans from one vector, so instead just cast
1756 // them to their raw pointers to do the swap
1757 let pa: *mut T = &mut self[a];
1758 let pb: *mut T = &mut self[b];
1764 let mut i: uint = 0;
1765 let ln = self.len();
1767 self.swap(i, ln - i - 1);
1773 fn sort_by(self, compare: |&T, &T| -> Ordering) {
1774 merge_sort(self, compare)
1778 fn move_from(self, mut src: ~[T], start: uint, end: uint) -> uint {
1779 for (a, b) in self.mut_iter().zip(src.mut_slice(start, end).mut_iter()) {
1782 cmp::min(self.len(), end-start)
1786 unsafe fn unsafe_mut_ref(self, index: uint) -> &'a mut T {
1787 transmute((self.repr().data as *mut T).offset(index as int))
1791 fn as_mut_ptr(self) -> *mut T {
1792 self.repr().data as *mut T
1796 unsafe fn unsafe_set(self, index: uint, val: T) {
1797 *self.unsafe_mut_ref(index) = val;
1801 unsafe fn init_elem(self, i: uint, val: T) {
1802 mem::move_val_init(&mut (*self.as_mut_ptr().offset(i as int)), val);
1806 unsafe fn copy_memory(self, src: &[T]) {
1807 let len_src = src.len();
1808 assert!(self.len() >= len_src);
1809 ptr::copy_nonoverlapping_memory(self.as_mut_ptr(), src.as_ptr(), len_src)
1813 /// Trait for &[T] where T is Cloneable
1814 pub trait MutableCloneableVector<T> {
1815 /// Copies as many elements from `src` as it can into `self` (the
1816 /// shorter of `self.len()` and `src.len()`). Returns the number
1817 /// of elements copied.
1822 /// use std::slice::MutableCloneableVector;
1824 /// let mut dst = [0, 0, 0];
1825 /// let src = [1, 2];
1827 /// assert!(dst.copy_from(src) == 2);
1828 /// assert!(dst == [1, 2, 0]);
1830 /// let src2 = [3, 4, 5, 6];
1831 /// assert!(dst.copy_from(src2) == 3);
1832 /// assert!(dst == [3, 4, 5]);
1834 fn copy_from(self, &[T]) -> uint;
1837 impl<'a, T:Clone> MutableCloneableVector<T> for &'a mut [T] {
1839 fn copy_from(self, src: &[T]) -> uint {
1840 for (a, b) in self.mut_iter().zip(src.iter()) {
1843 cmp::min(self.len(), src.len())
1847 /// Methods for mutable vectors with orderable elements, such as
1848 /// in-place sorting.
1849 pub trait MutableTotalOrdVector<T> {
1850 /// Sort the vector, in place.
1852 /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`.
1857 /// let mut v = [-5, 4, 1, -3, 2];
1860 /// assert!(v == [-5, -3, 1, 2, 4]);
1864 impl<'a, T: TotalOrd> MutableTotalOrdVector<T> for &'a mut [T] {
1867 self.sort_by(|a,b| a.cmp(b))
1872 * Constructs a vector from an unsafe pointer to a buffer
1876 * * ptr - An unsafe pointer to a buffer of `T`
1877 * * elts - The number of elements in the buffer
1879 // Wrapper for fn in raw: needs to be called by net_tcp::on_tcp_read_cb
1880 pub unsafe fn from_buf<T>(ptr: *T, elts: uint) -> ~[T] {
1881 raw::from_buf_raw(ptr, elts)
1884 /// Unsafe operations
1886 use cast::transmute;
1891 use slice::{MutableVector, OwnedVector};
1895 * Form a slice from a pointer and length (as a number of units,
1899 pub unsafe fn buf_as_slice<T,U>(p: *T, len: uint, f: |v: &[T]| -> U)
1908 * Form a slice from a pointer and length (as a number of units,
1912 pub unsafe fn mut_buf_as_slice<T,
1916 f: |v: &mut [T]| -> U)
1925 * Constructs a vector from an unsafe pointer to a buffer
1929 * * ptr - An unsafe pointer to a buffer of `T`
1930 * * elts - The number of elements in the buffer
1932 // Was in raw, but needs to be called by net_tcp::on_tcp_read_cb
1934 pub unsafe fn from_buf_raw<T>(ptr: *T, elts: uint) -> ~[T] {
1935 let mut dst = Vec::with_capacity(elts);
1937 ptr::copy_memory(dst.as_mut_ptr(), ptr, elts);
1938 dst.move_iter().collect()
1942 * Returns a pointer to first element in slice and adjusts
1943 * slice so it no longer contains that element. Fails if
1944 * slice is empty. O(1).
1946 pub unsafe fn shift_ptr<T>(slice: &mut Slice<T>) -> *T {
1947 if slice.len == 0 { fail!("shift on empty slice"); }
1948 let head: *T = slice.data;
1949 slice.data = slice.data.offset(1);
1955 * Returns a pointer to last element in slice and adjusts
1956 * slice so it no longer contains that element. Fails if
1957 * slice is empty. O(1).
1959 pub unsafe fn pop_ptr<T>(slice: &mut Slice<T>) -> *T {
1960 if slice.len == 0 { fail!("pop on empty slice"); }
1961 let tail: *T = slice.data.offset((slice.len - 1) as int);
1967 /// Operations on `[u8]`.
1969 use container::Container;
1970 use slice::MutableVector;
1973 /// A trait for operations on mutable `[u8]`s.
1974 pub trait MutableByteVector {
1975 /// Sets all bytes of the receiver to the given value.
1976 fn set_memory(self, value: u8);
1979 impl<'a> MutableByteVector for &'a mut [u8] {
1981 fn set_memory(self, value: u8) {
1982 unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
1986 /// Copies data from `src` to `dst`
1988 /// `src` and `dst` must not overlap. Fails if the length of `dst`
1989 /// is less than the length of `src`.
1991 pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
1992 // Bound checks are done at .copy_memory.
1993 unsafe { dst.copy_memory(src) }
1997 impl<A: Clone> Clone for ~[A] {
1999 fn clone(&self) -> ~[A] {
2000 // Use the fast to_owned on &[A] for cloning
2001 self.as_slice().to_owned()
2005 impl<'a, T: fmt::Show> fmt::Show for &'a [T] {
2006 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2007 if f.flags & (1 << (fmt::parse::FlagAlternate as uint)) == 0 {
2008 try!(write!(f.buf, "["));
2010 let mut is_first = true;
2011 for x in self.iter() {
2015 try!(write!(f.buf, ", "));
2017 try!(write!(f.buf, "{}", *x))
2019 if f.flags & (1 << (fmt::parse::FlagAlternate as uint)) == 0 {
2020 try!(write!(f.buf, "]"));
2026 impl<'a, T: fmt::Show> fmt::Show for &'a mut [T] {
2027 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2028 self.as_slice().fmt(f)
2032 impl<T: fmt::Show> fmt::Show for ~[T] {
2033 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2034 self.as_slice().fmt(f)
2038 // This works because every lifetime is a sub-lifetime of 'static
2039 impl<'a, A> Default for &'a [A] {
2040 fn default() -> &'a [A] { &'a [] }
2043 impl<A> Default for ~[A] {
2044 fn default() -> ~[A] { ~[] }
2047 /// Immutable slice iterator
2048 pub struct Items<'a, T> {
2051 marker: marker::ContravariantLifetime<'a>
2054 /// Mutable slice iterator
2055 pub struct MutItems<'a, T> {
2058 marker: marker::ContravariantLifetime<'a>,
2059 marker2: marker::NoCopy
2062 macro_rules! iterator {
2063 (struct $name:ident -> $ptr:ty, $elem:ty) => {
2064 impl<'a, T> Iterator<$elem> for $name<'a, T> {
2066 fn next(&mut self) -> Option<$elem> {
2067 // could be implemented with slices, but this avoids bounds checks
2069 if self.ptr == self.end {
2073 self.ptr = if mem::size_of::<T>() == 0 {
2074 // purposefully don't use 'ptr.offset' because for
2075 // vectors with 0-size elements this would return the
2077 transmute(self.ptr as uint + 1)
2082 Some(transmute(old))
2088 fn size_hint(&self) -> (uint, Option<uint>) {
2089 let diff = (self.end as uint) - (self.ptr as uint);
2090 let exact = diff / mem::nonzero_size_of::<T>();
2091 (exact, Some(exact))
2095 impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
2097 fn next_back(&mut self) -> Option<$elem> {
2098 // could be implemented with slices, but this avoids bounds checks
2100 if self.end == self.ptr {
2103 self.end = if mem::size_of::<T>() == 0 {
2104 // See above for why 'ptr.offset' isn't used
2105 transmute(self.end as uint - 1)
2109 Some(transmute(self.end))
2117 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
2119 fn indexable(&self) -> uint {
2120 let (exact, _) = self.size_hint();
2125 fn idx(&mut self, index: uint) -> Option<&'a T> {
2127 if index < self.indexable() {
2128 transmute(self.ptr.offset(index as int))
2136 iterator!{struct Items -> *T, &'a T}
2137 pub type RevItems<'a, T> = Rev<Items<'a, T>>;
2139 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
2140 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
2142 impl<'a, T> Clone for Items<'a, T> {
2143 fn clone(&self) -> Items<'a, T> { *self }
2146 iterator!{struct MutItems -> *mut T, &'a mut T}
2147 pub type RevMutItems<'a, T> = Rev<MutItems<'a, T>>;
2149 /// An iterator over the subslices of the vector which are separated
2150 /// by elements that match `pred`.
2151 pub struct MutSplits<'a, T> {
2153 pred: |t: &T|: 'a -> bool,
2157 impl<'a, T> Iterator<&'a mut [T]> for MutSplits<'a, T> {
2159 fn next(&mut self) -> Option<&'a mut [T]> {
2160 if self.finished { return None; }
2162 let pred = &mut self.pred;
2163 match self.v.iter().position(|x| (*pred)(x)) {
2165 self.finished = true;
2166 let tmp = mem::replace(&mut self.v, &mut []);
2167 let len = tmp.len();
2168 let (head, tail) = tmp.mut_split_at(len);
2173 let tmp = mem::replace(&mut self.v, &mut []);
2174 let (head, tail) = tmp.mut_split_at(idx);
2175 self.v = tail.mut_slice_from(1);
2182 fn size_hint(&self) -> (uint, Option<uint>) {
2186 // if the predicate doesn't match anything, we yield one slice
2187 // if it matches every element, we yield len+1 empty slices.
2188 (1, Some(self.v.len() + 1))
2193 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutSplits<'a, T> {
2195 fn next_back(&mut self) -> Option<&'a mut [T]> {
2196 if self.finished { return None; }
2198 let pred = &mut self.pred;
2199 match self.v.iter().rposition(|x| (*pred)(x)) {
2201 self.finished = true;
2202 let tmp = mem::replace(&mut self.v, &mut []);
2206 let tmp = mem::replace(&mut self.v, &mut []);
2207 let (head, tail) = tmp.mut_split_at(idx);
2209 Some(tail.mut_slice_from(1))
2215 /// An iterator over a vector in (non-overlapping) mutable chunks (`size` elements at a time). When
2216 /// the vector len is not evenly divided by the chunk size, the last slice of the iteration will be
2218 pub struct MutChunks<'a, T> {
2223 impl<'a, T> Iterator<&'a mut [T]> for MutChunks<'a, T> {
2225 fn next(&mut self) -> Option<&'a mut [T]> {
2226 if self.v.len() == 0 {
2229 let sz = cmp::min(self.v.len(), self.chunk_size);
2230 let tmp = mem::replace(&mut self.v, &mut []);
2231 let (head, tail) = tmp.mut_split_at(sz);
2238 fn size_hint(&self) -> (uint, Option<uint>) {
2239 if self.v.len() == 0 {
2242 let (n, rem) = div_rem(self.v.len(), self.chunk_size);
2243 let n = if rem > 0 { n + 1 } else { n };
2249 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> {
2251 fn next_back(&mut self) -> Option<&'a mut [T]> {
2252 if self.v.len() == 0 {
2255 let remainder = self.v.len() % self.chunk_size;
2256 let sz = if remainder != 0 { remainder } else { self.chunk_size };
2257 let tmp = mem::replace(&mut self.v, &mut []);
2258 let tmp_len = tmp.len();
2259 let (head, tail) = tmp.mut_split_at(tmp_len - sz);
2266 /// An iterator that moves out of a vector.
2267 pub struct MoveItems<T> {
2268 allocation: *mut u8, // the block of memory allocated for the vector
2269 iter: Items<'static, T>
2272 impl<T> Iterator<T> for MoveItems<T> {
2274 fn next(&mut self) -> Option<T> {
2276 self.iter.next().map(|x| ptr::read(x))
2281 fn size_hint(&self) -> (uint, Option<uint>) {
2282 self.iter.size_hint()
2286 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
2288 fn next_back(&mut self) -> Option<T> {
2290 self.iter.next_back().map(|x| ptr::read(x))
2295 #[unsafe_destructor]
2296 impl<T> Drop for MoveItems<T> {
2297 fn drop(&mut self) {
2298 // destroy the remaining elements
2301 exchange_free(self.allocation as *u8)
2306 /// An iterator that moves out of a vector in reverse order.
2307 pub type RevMoveItems<T> = Rev<MoveItems<T>>;
2309 impl<A> FromIterator<A> for ~[A] {
2310 fn from_iter<T: Iterator<A>>(mut iterator: T) -> ~[A] {
2311 let mut xs: Vec<A> = iterator.collect();
2313 // Must shrink so the capacity is the same as the length. The length of
2314 // the ~[T] vector must exactly match the length of the allocation.
2318 assert!(len == xs.capacity());
2319 let data = xs.as_mut_ptr();
2321 let data_size = len.checked_mul(&mem::size_of::<A>());
2322 let data_size = data_size.expect("overflow in from_iter()");
2323 let size = mem::size_of::<RawVec<()>>().checked_add(&data_size);
2324 let size = size.expect("overflow in from_iter()");
2327 // This is some terribly awful code. Note that all of this will go away
2328 // with DST because creating ~[T] from Vec<T> will just be some pointer
2331 let ret = malloc_raw(size) as *mut RawVec<()>;
2333 (*ret).fill = len * mem::nonzero_size_of::<A>();
2334 (*ret).alloc = len * mem::nonzero_size_of::<A>();
2335 ptr::copy_nonoverlapping_memory(&mut (*ret).data as *mut _ as *mut u8,
2338 xs.set_len(0); // ownership has been transferred
2339 cast::transmute(ret)
2350 use rand::{Rng, task_rng};
2352 fn square(n: uint) -> uint { n * n }
2354 fn is_odd(n: &uint) -> bool { *n % 2u == 1u }
2357 fn test_unsafe_ptrs() {
2359 // Test on-stack copy-from-buf.
2361 let mut ptr = a.as_ptr();
2362 let b = from_buf(ptr, 3u);
2363 assert_eq!(b.len(), 3u);
2364 assert_eq!(b[0], 1);
2365 assert_eq!(b[1], 2);
2366 assert_eq!(b[2], 3);
2368 // Test on-heap copy-from-buf.
2369 let c = ~[1, 2, 3, 4, 5];
2371 let d = from_buf(ptr, 5u);
2372 assert_eq!(d.len(), 5u);
2373 assert_eq!(d[0], 1);
2374 assert_eq!(d[1], 2);
2375 assert_eq!(d[2], 3);
2376 assert_eq!(d[3], 4);
2377 assert_eq!(d[4], 5);
2383 // Test on-stack from_fn.
2384 let mut v = Vec::from_fn(3u, square);
2386 let v = v.as_slice();
2387 assert_eq!(v.len(), 3u);
2388 assert_eq!(v[0], 0u);
2389 assert_eq!(v[1], 1u);
2390 assert_eq!(v[2], 4u);
2393 // Test on-heap from_fn.
2394 v = Vec::from_fn(5u, square);
2396 let v = v.as_slice();
2397 assert_eq!(v.len(), 5u);
2398 assert_eq!(v[0], 0u);
2399 assert_eq!(v[1], 1u);
2400 assert_eq!(v[2], 4u);
2401 assert_eq!(v[3], 9u);
2402 assert_eq!(v[4], 16u);
2407 fn test_from_elem() {
2408 // Test on-stack from_elem.
2409 let mut v = Vec::from_elem(2u, 10u);
2411 let v = v.as_slice();
2412 assert_eq!(v.len(), 2u);
2413 assert_eq!(v[0], 10u);
2414 assert_eq!(v[1], 10u);
2417 // Test on-heap from_elem.
2418 v = Vec::from_elem(6u, 20u);
2420 let v = v.as_slice();
2421 assert_eq!(v[0], 20u);
2422 assert_eq!(v[1], 20u);
2423 assert_eq!(v[2], 20u);
2424 assert_eq!(v[3], 20u);
2425 assert_eq!(v[4], 20u);
2426 assert_eq!(v[5], 20u);
2431 fn test_is_empty() {
2432 let xs: [int, ..0] = [];
2433 assert!(xs.is_empty());
2434 assert!(![0].is_empty());
2438 fn test_len_divzero() {
2440 let v0 : &[Z] = &[];
2441 let v1 : &[Z] = &[[]];
2442 let v2 : &[Z] = &[[], []];
2443 assert_eq!(mem::size_of::<Z>(), 0);
2444 assert_eq!(v0.len(), 0);
2445 assert_eq!(v1.len(), 1);
2446 assert_eq!(v2.len(), 2);
2452 assert_eq!(a.get(1), None);
2454 assert_eq!(a.get(1).unwrap(), &12);
2456 assert_eq!(a.get(1).unwrap(), &12);
2462 assert_eq!(a.head(), None);
2464 assert_eq!(a.head().unwrap(), &11);
2466 assert_eq!(a.head().unwrap(), &11);
2472 assert_eq!(a.tail(), &[]);
2474 assert_eq!(a.tail(), &[12]);
2479 fn test_tail_empty() {
2480 let a: ~[int] = ~[];
2486 let mut a = ~[11, 12, 13];
2487 assert_eq!(a.tailn(0), &[11, 12, 13]);
2489 assert_eq!(a.tailn(2), &[13]);
2494 fn test_tailn_empty() {
2495 let a: ~[int] = ~[];
2502 assert_eq!(a.init(), &[]);
2504 assert_eq!(a.init(), &[11]);
2509 fn test_init_empty() {
2510 let a: ~[int] = ~[];
2516 let mut a = ~[11, 12, 13];
2517 assert_eq!(a.initn(0), &[11, 12, 13]);
2519 assert_eq!(a.initn(2), &[11]);
2524 fn test_initn_empty() {
2525 let a: ~[int] = ~[];
2532 assert_eq!(a.last(), None);
2534 assert_eq!(a.last().unwrap(), &11);
2536 assert_eq!(a.last().unwrap(), &12);
2541 // Test fixed length vector.
2542 let vec_fixed = [1, 2, 3, 4];
2543 let v_a = vec_fixed.slice(1u, vec_fixed.len()).to_owned();
2544 assert_eq!(v_a.len(), 3u);
2545 assert_eq!(v_a[0], 2);
2546 assert_eq!(v_a[1], 3);
2547 assert_eq!(v_a[2], 4);
2550 let vec_stack = &[1, 2, 3];
2551 let v_b = vec_stack.slice(1u, 3u).to_owned();
2552 assert_eq!(v_b.len(), 2u);
2553 assert_eq!(v_b[0], 2);
2554 assert_eq!(v_b[1], 3);
2556 // Test on exchange heap.
2557 let vec_unique = ~[1, 2, 3, 4, 5, 6];
2558 let v_d = vec_unique.slice(1u, 6u).to_owned();
2559 assert_eq!(v_d.len(), 5u);
2560 assert_eq!(v_d[0], 2);
2561 assert_eq!(v_d[1], 3);
2562 assert_eq!(v_d[2], 4);
2563 assert_eq!(v_d[3], 5);
2564 assert_eq!(v_d[4], 6);
2568 fn test_slice_from() {
2569 let vec = &[1, 2, 3, 4];
2570 assert_eq!(vec.slice_from(0), vec);
2571 assert_eq!(vec.slice_from(2), &[3, 4]);
2572 assert_eq!(vec.slice_from(4), &[]);
2576 fn test_slice_to() {
2577 let vec = &[1, 2, 3, 4];
2578 assert_eq!(vec.slice_to(4), vec);
2579 assert_eq!(vec.slice_to(2), &[1, 2]);
2580 assert_eq!(vec.slice_to(0), &[]);
2586 let mut v = vec![5];
2588 assert_eq!(v.len(), 0);
2589 assert_eq!(e, Some(5));
2591 assert_eq!(f, None);
2593 assert_eq!(g, None);
2597 fn test_swap_remove() {
2598 let mut v = vec![1, 2, 3, 4, 5];
2599 let mut e = v.swap_remove(0);
2600 assert_eq!(e, Some(1));
2601 assert_eq!(v, vec![5, 2, 3, 4]);
2602 e = v.swap_remove(3);
2603 assert_eq!(e, Some(4));
2604 assert_eq!(v, vec![5, 2, 3]);
2606 e = v.swap_remove(3);
2607 assert_eq!(e, None);
2608 assert_eq!(v, vec![5, 2, 3]);
2612 fn test_swap_remove_noncopyable() {
2613 // Tests that we don't accidentally run destructors twice.
2614 let mut v = vec![::unstable::sync::Exclusive::new(()),
2615 ::unstable::sync::Exclusive::new(()),
2616 ::unstable::sync::Exclusive::new(())];
2617 let mut _e = v.swap_remove(0);
2618 assert_eq!(v.len(), 2);
2619 _e = v.swap_remove(1);
2620 assert_eq!(v.len(), 1);
2621 _e = v.swap_remove(0);
2622 assert_eq!(v.len(), 0);
2627 // Test on-stack push().
2630 assert_eq!(v.len(), 1u);
2631 assert_eq!(v.as_slice()[0], 1);
2633 // Test on-heap push().
2635 assert_eq!(v.len(), 2u);
2636 assert_eq!(v.as_slice()[0], 1);
2637 assert_eq!(v.as_slice()[1], 2);
2642 // Test on-stack grow().
2646 let v = v.as_slice();
2647 assert_eq!(v.len(), 2u);
2648 assert_eq!(v[0], 1);
2649 assert_eq!(v[1], 1);
2652 // Test on-heap grow().
2655 let v = v.as_slice();
2656 assert_eq!(v.len(), 5u);
2657 assert_eq!(v[0], 1);
2658 assert_eq!(v[1], 1);
2659 assert_eq!(v[2], 2);
2660 assert_eq!(v[3], 2);
2661 assert_eq!(v[4], 2);
2668 v.grow_fn(3u, square);
2669 let v = v.as_slice();
2670 assert_eq!(v.len(), 3u);
2671 assert_eq!(v[0], 0u);
2672 assert_eq!(v[1], 1u);
2673 assert_eq!(v[2], 4u);
2677 fn test_grow_set() {
2678 let mut v = vec![1, 2, 3];
2679 v.grow_set(4u, &4, 5);
2680 let v = v.as_slice();
2681 assert_eq!(v.len(), 5u);
2682 assert_eq!(v[0], 1);
2683 assert_eq!(v[1], 2);
2684 assert_eq!(v[2], 3);
2685 assert_eq!(v[3], 4);
2686 assert_eq!(v[4], 5);
2690 fn test_truncate() {
2691 let mut v = vec![~6,~5,~4];
2693 let v = v.as_slice();
2694 assert_eq!(v.len(), 1);
2695 assert_eq!(*(v[0]), 6);
2696 // If the unsafe block didn't drop things properly, we blow up here.
2701 let mut v = vec![~6,~5,~4];
2703 assert_eq!(v.len(), 0);
2704 // If the unsafe block didn't drop things properly, we blow up here.
2709 fn case(a: Vec<uint>, b: Vec<uint>) {
2714 case(vec![], vec![]);
2715 case(vec![1], vec![1]);
2716 case(vec![1,1], vec![1]);
2717 case(vec![1,2,3], vec![1,2,3]);
2718 case(vec![1,1,2,3], vec![1,2,3]);
2719 case(vec![1,2,2,3], vec![1,2,3]);
2720 case(vec![1,2,3,3], vec![1,2,3]);
2721 case(vec![1,1,2,2,2,3,3], vec![1,2,3]);
2725 fn test_dedup_unique() {
2726 let mut v0 = vec![~1, ~1, ~2, ~3];
2728 let mut v1 = vec![~1, ~2, ~2, ~3];
2730 let mut v2 = vec![~1, ~2, ~3, ~3];
2733 * If the ~pointers were leaked or otherwise misused, valgrind and/or
2734 * rustrt should raise errors.
2739 fn test_dedup_shared() {
2740 let mut v0 = vec![~1, ~1, ~2, ~3];
2742 let mut v1 = vec![~1, ~2, ~2, ~3];
2744 let mut v2 = vec![~1, ~2, ~3, ~3];
2747 * If the pointers were leaked or otherwise misused, valgrind and/or
2748 * rustrt should raise errors.
2754 let mut v = vec![1, 2, 3, 4, 5];
2756 assert_eq!(v, vec![1, 3, 5]);
2760 fn test_zip_unzip() {
2761 let z1 = vec![(1, 4), (2, 5), (3, 6)];
2763 let (left, right) = unzip(z1.iter().map(|&x| x));
2765 assert_eq!((1, 4), (left[0], right[0]));
2766 assert_eq!((2, 5), (left[1], right[1]));
2767 assert_eq!((3, 6), (left[2], right[2]));
2771 fn test_element_swaps() {
2772 let mut v = [1, 2, 3];
2773 for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
2776 0 => assert!(v == [1, 3, 2]),
2777 1 => assert!(v == [3, 1, 2]),
2778 2 => assert!(v == [3, 2, 1]),
2779 3 => assert!(v == [2, 3, 1]),
2780 4 => assert!(v == [2, 1, 3]),
2781 5 => assert!(v == [1, 2, 3]),
2788 fn test_permutations() {
2790 let v: [int, ..0] = [];
2791 let mut it = v.permutations();
2792 let (min_size, max_opt) = it.size_hint();
2793 assert_eq!(min_size, 1);
2794 assert_eq!(max_opt.unwrap(), 1);
2795 assert_eq!(it.next(), Some(v.as_slice().to_owned()));
2796 assert_eq!(it.next(), None);
2799 let v = ["Hello".to_owned()];
2800 let mut it = v.permutations();
2801 let (min_size, max_opt) = it.size_hint();
2802 assert_eq!(min_size, 1);
2803 assert_eq!(max_opt.unwrap(), 1);
2804 assert_eq!(it.next(), Some(v.as_slice().to_owned()));
2805 assert_eq!(it.next(), None);
2809 let mut it = v.permutations();
2810 let (min_size, max_opt) = it.size_hint();
2811 assert_eq!(min_size, 3*2);
2812 assert_eq!(max_opt.unwrap(), 3*2);
2813 assert_eq!(it.next(), Some(~[1,2,3]));
2814 assert_eq!(it.next(), Some(~[1,3,2]));
2815 assert_eq!(it.next(), Some(~[3,1,2]));
2816 let (min_size, max_opt) = it.size_hint();
2817 assert_eq!(min_size, 3);
2818 assert_eq!(max_opt.unwrap(), 3);
2819 assert_eq!(it.next(), Some(~[3,2,1]));
2820 assert_eq!(it.next(), Some(~[2,3,1]));
2821 assert_eq!(it.next(), Some(~[2,1,3]));
2822 assert_eq!(it.next(), None);
2825 // check that we have N! permutations
2826 let v = ['A', 'B', 'C', 'D', 'E', 'F'];
2828 let mut it = v.permutations();
2829 let (min_size, max_opt) = it.size_hint();
2833 assert_eq!(amt, it.swaps.swaps_made);
2834 assert_eq!(amt, min_size);
2835 assert_eq!(amt, 2 * 3 * 4 * 5 * 6);
2836 assert_eq!(amt, max_opt.unwrap());
2841 fn test_position_elem() {
2842 assert!([].position_elem(&1).is_none());
2844 let v1 = ~[1, 2, 3, 3, 2, 5];
2845 assert_eq!(v1.position_elem(&1), Some(0u));
2846 assert_eq!(v1.position_elem(&2), Some(1u));
2847 assert_eq!(v1.position_elem(&5), Some(5u));
2848 assert!(v1.position_elem(&4).is_none());
2852 fn test_bsearch_elem() {
2853 assert_eq!([1,2,3,4,5].bsearch_elem(&5), Some(4));
2854 assert_eq!([1,2,3,4,5].bsearch_elem(&4), Some(3));
2855 assert_eq!([1,2,3,4,5].bsearch_elem(&3), Some(2));
2856 assert_eq!([1,2,3,4,5].bsearch_elem(&2), Some(1));
2857 assert_eq!([1,2,3,4,5].bsearch_elem(&1), Some(0));
2859 assert_eq!([2,4,6,8,10].bsearch_elem(&1), None);
2860 assert_eq!([2,4,6,8,10].bsearch_elem(&5), None);
2861 assert_eq!([2,4,6,8,10].bsearch_elem(&4), Some(1));
2862 assert_eq!([2,4,6,8,10].bsearch_elem(&10), Some(4));
2864 assert_eq!([2,4,6,8].bsearch_elem(&1), None);
2865 assert_eq!([2,4,6,8].bsearch_elem(&5), None);
2866 assert_eq!([2,4,6,8].bsearch_elem(&4), Some(1));
2867 assert_eq!([2,4,6,8].bsearch_elem(&8), Some(3));
2869 assert_eq!([2,4,6].bsearch_elem(&1), None);
2870 assert_eq!([2,4,6].bsearch_elem(&5), None);
2871 assert_eq!([2,4,6].bsearch_elem(&4), Some(1));
2872 assert_eq!([2,4,6].bsearch_elem(&6), Some(2));
2874 assert_eq!([2,4].bsearch_elem(&1), None);
2875 assert_eq!([2,4].bsearch_elem(&5), None);
2876 assert_eq!([2,4].bsearch_elem(&2), Some(0));
2877 assert_eq!([2,4].bsearch_elem(&4), Some(1));
2879 assert_eq!([2].bsearch_elem(&1), None);
2880 assert_eq!([2].bsearch_elem(&5), None);
2881 assert_eq!([2].bsearch_elem(&2), Some(0));
2883 assert_eq!([].bsearch_elem(&1), None);
2884 assert_eq!([].bsearch_elem(&5), None);
2886 assert!([1,1,1,1,1].bsearch_elem(&1) != None);
2887 assert!([1,1,1,1,2].bsearch_elem(&1) != None);
2888 assert!([1,1,1,2,2].bsearch_elem(&1) != None);
2889 assert!([1,1,2,2,2].bsearch_elem(&1) != None);
2890 assert_eq!([1,2,2,2,2].bsearch_elem(&1), Some(0));
2892 assert_eq!([1,2,3,4,5].bsearch_elem(&6), None);
2893 assert_eq!([1,2,3,4,5].bsearch_elem(&0), None);
2898 let mut v: ~[int] = ~[10, 20];
2899 assert_eq!(v[0], 10);
2900 assert_eq!(v[1], 20);
2902 assert_eq!(v[0], 20);
2903 assert_eq!(v[1], 10);
2905 let mut v3: ~[int] = ~[];
2907 assert!(v3.is_empty());
2912 use realstd::slice::Vector;
2913 use realstd::clone::Clone;
2914 for len in range(4u, 25) {
2915 for _ in range(0, 100) {
2916 let mut v = task_rng().gen_vec::<uint>(len);
2917 let mut v1 = v.clone();
2919 v.as_mut_slice().sort();
2920 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
2922 v1.as_mut_slice().sort_by(|a, b| a.cmp(b));
2923 assert!(v1.as_slice().windows(2).all(|w| w[0] <= w[1]));
2925 v1.as_mut_slice().sort_by(|a, b| b.cmp(a));
2926 assert!(v1.as_slice().windows(2).all(|w| w[0] >= w[1]));
2930 // shouldn't fail/crash
2931 let mut v: [uint, .. 0] = [];
2934 let mut v = [0xDEADBEEFu];
2936 assert!(v == [0xDEADBEEF]);
2940 fn test_sort_stability() {
2941 for len in range(4, 25) {
2942 for _ in range(0 , 10) {
2943 let mut counts = [0, .. 10];
2945 // create a vector like [(6, 1), (5, 1), (6, 2), ...],
2946 // where the first item of each tuple is random, but
2947 // the second item represents which occurrence of that
2948 // number this element is, i.e. the second elements
2949 // will occur in sorted order.
2950 let mut v = range(0, len).map(|_| {
2951 let n = task_rng().gen::<uint>() % 10;
2954 }).collect::<~[(uint, int)]>();
2956 // only sort on the first element, so an unstable sort
2957 // may mix up the counts.
2958 v.sort_by(|&(a,_), &(b,_)| a.cmp(&b));
2960 // this comparison includes the count (the second item
2961 // of the tuple), so elements with equal first items
2962 // will need to be ordered with increasing
2963 // counts... i.e. exactly asserting that this sort is
2965 assert!(v.windows(2).all(|w| w[0] <= w[1]));
2971 fn test_partition() {
2972 assert_eq!((~[]).partition(|x: &int| *x < 3), (~[], ~[]));
2973 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 4), (~[1, 2, 3], ~[]));
2974 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 2), (~[1], ~[2, 3]));
2975 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 0), (~[], ~[1, 2, 3]));
2979 fn test_partitioned() {
2980 assert_eq!(([]).partitioned(|x: &int| *x < 3), (~[], ~[]))
2981 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 4), (~[1, 2, 3], ~[]));
2982 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 2), (~[1], ~[2, 3]));
2983 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 0), (~[], ~[1, 2, 3]));
2988 let v: [~[int], ..0] = [];
2989 assert_eq!(v.concat_vec(), ~[]);
2990 assert_eq!([~[1], ~[2,3]].concat_vec(), ~[1, 2, 3]);
2992 assert_eq!([&[1], &[2,3]].concat_vec(), ~[1, 2, 3]);
2997 let v: [~[int], ..0] = [];
2998 assert_eq!(v.connect_vec(&0), ~[]);
2999 assert_eq!([~[1], ~[2, 3]].connect_vec(&0), ~[1, 0, 2, 3]);
3000 assert_eq!([~[1], ~[2], ~[3]].connect_vec(&0), ~[1, 0, 2, 0, 3]);
3002 assert_eq!(v.connect_vec(&0), ~[]);
3003 assert_eq!([&[1], &[2, 3]].connect_vec(&0), ~[1, 0, 2, 3]);
3004 assert_eq!([&[1], &[2], &[3]].connect_vec(&0), ~[1, 0, 2, 0, 3]);
3009 let mut x = vec![1, 2, 3];
3010 assert_eq!(x.shift(), Some(1));
3011 assert_eq!(&x, &vec![2, 3]);
3012 assert_eq!(x.shift(), Some(2));
3013 assert_eq!(x.shift(), Some(3));
3014 assert_eq!(x.shift(), None);
3015 assert_eq!(x.len(), 0);
3020 let mut x = vec![1, 2, 3];
3022 assert_eq!(x, vec![0, 1, 2, 3]);
3027 let mut a = vec![1, 2, 4];
3029 assert_eq!(a, vec![1, 2, 3, 4]);
3031 let mut a = vec![1, 2, 3];
3033 assert_eq!(a, vec![0, 1, 2, 3]);
3035 let mut a = vec![1, 2, 3];
3037 assert_eq!(a, vec![1, 2, 3, 4]);
3041 assert_eq!(a, vec![1]);
3046 fn test_insert_oob() {
3047 let mut a = vec![1, 2, 3];
3053 let mut a = vec![1,2,3,4];
3055 assert_eq!(a.remove(2), Some(3));
3056 assert_eq!(a, vec![1,2,4]);
3058 assert_eq!(a.remove(2), Some(4));
3059 assert_eq!(a, vec![1,2]);
3061 assert_eq!(a.remove(2), None);
3062 assert_eq!(a, vec![1,2]);
3064 assert_eq!(a.remove(0), Some(1));
3065 assert_eq!(a, vec![2]);
3067 assert_eq!(a.remove(0), Some(2));
3068 assert_eq!(a, vec![]);
3070 assert_eq!(a.remove(0), None);
3071 assert_eq!(a.remove(10), None);
3075 fn test_capacity() {
3076 let mut v = vec![0u64];
3077 v.reserve_exact(10u);
3078 assert_eq!(v.capacity(), 10u);
3079 let mut v = vec![0u32];
3080 v.reserve_exact(10u);
3081 assert_eq!(v.capacity(), 10u);
3086 let v = vec![1, 2, 3, 4, 5];
3087 let v = v.slice(1u, 3u);
3088 assert_eq!(v.len(), 2u);
3089 assert_eq!(v[0], 2);
3090 assert_eq!(v[1], 3);
3096 fn test_from_fn_fail() {
3097 Vec::from_fn(100, |v| {
3098 if v == 50 { fail!() }
3105 fn test_from_elem_fail() {
3111 boxes: (~int, Rc<int>)
3115 fn clone(&self) -> S {
3116 let s = unsafe { cast::transmute_mut(self) };
3118 if s.f == 10 { fail!() }
3119 S { f: s.f, boxes: s.boxes.clone() }
3123 let s = S { f: 0, boxes: (~0, Rc::new(0)) };
3124 let _ = Vec::from_elem(100, s);
3129 fn test_grow_fn_fail() {
3132 v.grow_fn(100, |i| {
3142 fn test_permute_fail() {
3144 let v = [(~0, Rc::new(0)), (~0, Rc::new(0)), (~0, Rc::new(0)), (~0, Rc::new(0))];
3146 for _ in v.permutations() {
3156 fn test_copy_memory_oob() {
3158 let mut a = [1, 2, 3, 4];
3159 let b = [1, 2, 3, 4, 5];
3165 fn test_total_ord() {
3166 [1, 2, 3, 4].cmp(& &[1, 2, 3]) == Greater;
3167 [1, 2, 3].cmp(& &[1, 2, 3, 4]) == Less;
3168 [1, 2, 3, 4].cmp(& &[1, 2, 3, 4]) == Equal;
3169 [1, 2, 3, 4, 5, 5, 5, 5].cmp(& &[1, 2, 3, 4, 5, 6]) == Less;
3170 [2, 2].cmp(& &[1, 2, 3, 4]) == Greater;
3174 fn test_iterator() {
3176 let xs = [1, 2, 5, 10, 11];
3177 let mut it = xs.iter();
3178 assert_eq!(it.size_hint(), (5, Some(5)));
3179 assert_eq!(it.next().unwrap(), &1);
3180 assert_eq!(it.size_hint(), (4, Some(4)));
3181 assert_eq!(it.next().unwrap(), &2);
3182 assert_eq!(it.size_hint(), (3, Some(3)));
3183 assert_eq!(it.next().unwrap(), &5);
3184 assert_eq!(it.size_hint(), (2, Some(2)));
3185 assert_eq!(it.next().unwrap(), &10);
3186 assert_eq!(it.size_hint(), (1, Some(1)));
3187 assert_eq!(it.next().unwrap(), &11);
3188 assert_eq!(it.size_hint(), (0, Some(0)));
3189 assert!(it.next().is_none());
3193 fn test_random_access_iterator() {
3195 let xs = [1, 2, 5, 10, 11];
3196 let mut it = xs.iter();
3198 assert_eq!(it.indexable(), 5);
3199 assert_eq!(it.idx(0).unwrap(), &1);
3200 assert_eq!(it.idx(2).unwrap(), &5);
3201 assert_eq!(it.idx(4).unwrap(), &11);
3202 assert!(it.idx(5).is_none());
3204 assert_eq!(it.next().unwrap(), &1);
3205 assert_eq!(it.indexable(), 4);
3206 assert_eq!(it.idx(0).unwrap(), &2);
3207 assert_eq!(it.idx(3).unwrap(), &11);
3208 assert!(it.idx(4).is_none());
3210 assert_eq!(it.next().unwrap(), &2);
3211 assert_eq!(it.indexable(), 3);
3212 assert_eq!(it.idx(1).unwrap(), &10);
3213 assert!(it.idx(3).is_none());
3215 assert_eq!(it.next().unwrap(), &5);
3216 assert_eq!(it.indexable(), 2);
3217 assert_eq!(it.idx(1).unwrap(), &11);
3219 assert_eq!(it.next().unwrap(), &10);
3220 assert_eq!(it.indexable(), 1);
3221 assert_eq!(it.idx(0).unwrap(), &11);
3222 assert!(it.idx(1).is_none());
3224 assert_eq!(it.next().unwrap(), &11);
3225 assert_eq!(it.indexable(), 0);
3226 assert!(it.idx(0).is_none());
3228 assert!(it.next().is_none());
3232 fn test_iter_size_hints() {
3234 let mut xs = [1, 2, 5, 10, 11];
3235 assert_eq!(xs.iter().size_hint(), (5, Some(5)));
3236 assert_eq!(xs.rev_iter().size_hint(), (5, Some(5)));
3237 assert_eq!(xs.mut_iter().size_hint(), (5, Some(5)));
3238 assert_eq!(xs.mut_rev_iter().size_hint(), (5, Some(5)));
3242 fn test_iter_clone() {
3244 let mut it = xs.iter();
3246 let mut jt = it.clone();
3247 assert_eq!(it.next(), jt.next());
3248 assert_eq!(it.next(), jt.next());
3249 assert_eq!(it.next(), jt.next());
3253 fn test_mut_iterator() {
3255 let mut xs = [1, 2, 3, 4, 5];
3256 for x in xs.mut_iter() {
3259 assert!(xs == [2, 3, 4, 5, 6])
3263 fn test_rev_iterator() {
3266 let xs = [1, 2, 5, 10, 11];
3267 let ys = [11, 10, 5, 2, 1];
3269 for &x in xs.rev_iter() {
3270 assert_eq!(x, ys[i]);
3277 fn test_mut_rev_iterator() {
3279 let mut xs = [1u, 2, 3, 4, 5];
3280 for (i,x) in xs.mut_rev_iter().enumerate() {
3283 assert!(xs == [5, 5, 5, 5, 5])
3287 fn test_move_iterator() {
3289 let xs = ~[1u,2,3,4,5];
3290 assert_eq!(xs.move_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
3294 fn test_move_rev_iterator() {
3296 let xs = ~[1u,2,3,4,5];
3297 assert_eq!(xs.move_rev_iter().fold(0, |a: uint, b: uint| 10*a + b), 54321);
3301 fn test_splitator() {
3302 let xs = &[1i,2,3,4,5];
3304 assert_eq!(xs.split(|x| *x % 2 == 0).collect::<~[&[int]]>(),
3305 ~[&[1], &[3], &[5]]);
3306 assert_eq!(xs.split(|x| *x == 1).collect::<~[&[int]]>(),
3307 ~[&[], &[2,3,4,5]]);
3308 assert_eq!(xs.split(|x| *x == 5).collect::<~[&[int]]>(),
3309 ~[&[1,2,3,4], &[]]);
3310 assert_eq!(xs.split(|x| *x == 10).collect::<~[&[int]]>(),
3312 assert_eq!(xs.split(|_| true).collect::<~[&[int]]>(),
3313 ~[&[], &[], &[], &[], &[], &[]]);
3315 let xs: &[int] = &[];
3316 assert_eq!(xs.split(|x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3320 fn test_splitnator() {
3321 let xs = &[1i,2,3,4,5];
3323 assert_eq!(xs.splitn(0, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3325 assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3327 assert_eq!(xs.splitn(3, |_| true).collect::<~[&[int]]>(),
3328 ~[&[], &[], &[], &[4,5]]);
3330 let xs: &[int] = &[];
3331 assert_eq!(xs.splitn(1, |x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3335 fn test_rsplitator() {
3336 let xs = &[1i,2,3,4,5];
3338 assert_eq!(xs.rsplit(|x| *x % 2 == 0).collect::<~[&[int]]>(),
3339 ~[&[5], &[3], &[1]]);
3340 assert_eq!(xs.rsplit(|x| *x == 1).collect::<~[&[int]]>(),
3341 ~[&[2,3,4,5], &[]]);
3342 assert_eq!(xs.rsplit(|x| *x == 5).collect::<~[&[int]]>(),
3343 ~[&[], &[1,2,3,4]]);
3344 assert_eq!(xs.rsplit(|x| *x == 10).collect::<~[&[int]]>(),
3347 let xs: &[int] = &[];
3348 assert_eq!(xs.rsplit(|x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3352 fn test_rsplitnator() {
3353 let xs = &[1,2,3,4,5];
3355 assert_eq!(xs.rsplitn(0, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3357 assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3359 assert_eq!(xs.rsplitn(3, |_| true).collect::<~[&[int]]>(),
3360 ~[&[], &[], &[], &[1,2]]);
3362 let xs: &[int] = &[];
3363 assert_eq!(xs.rsplitn(1, |x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3367 fn test_windowsator() {
3368 let v = &[1i,2,3,4];
3370 assert_eq!(v.windows(2).collect::<~[&[int]]>(), ~[&[1,2], &[2,3], &[3,4]]);
3371 assert_eq!(v.windows(3).collect::<~[&[int]]>(), ~[&[1i,2,3], &[2,3,4]]);
3372 assert!(v.windows(6).next().is_none());
3377 fn test_windowsator_0() {
3378 let v = &[1i,2,3,4];
3379 let _it = v.windows(0);
3383 fn test_chunksator() {
3384 let v = &[1i,2,3,4,5];
3386 assert_eq!(v.chunks(2).collect::<~[&[int]]>(), ~[&[1i,2], &[3,4], &[5]]);
3387 assert_eq!(v.chunks(3).collect::<~[&[int]]>(), ~[&[1i,2,3], &[4,5]]);
3388 assert_eq!(v.chunks(6).collect::<~[&[int]]>(), ~[&[1i,2,3,4,5]]);
3390 assert_eq!(v.chunks(2).rev().collect::<~[&[int]]>(), ~[&[5i], &[3,4], &[1,2]]);
3391 let mut it = v.chunks(2);
3392 assert_eq!(it.indexable(), 3);
3393 assert_eq!(it.idx(0).unwrap(), &[1,2]);
3394 assert_eq!(it.idx(1).unwrap(), &[3,4]);
3395 assert_eq!(it.idx(2).unwrap(), &[5]);
3396 assert_eq!(it.idx(3), None);
3401 fn test_chunksator_0() {
3402 let v = &[1i,2,3,4];
3403 let _it = v.chunks(0);
3407 fn test_move_from() {
3408 let mut a = [1,2,3,4,5];
3410 assert_eq!(a.move_from(b, 0, 3), 3);
3411 assert!(a == [6,7,8,4,5]);
3412 let mut a = [7,2,8,1];
3413 let b = ~[3,1,4,1,5,9];
3414 assert_eq!(a.move_from(b, 0, 6), 4);
3415 assert!(a == [3,1,4,1]);
3416 let mut a = [1,2,3,4];
3417 let b = ~[5,6,7,8,9,0];
3418 assert_eq!(a.move_from(b, 2, 3), 1);
3419 assert!(a == [7,2,3,4]);
3420 let mut a = [1,2,3,4,5];
3421 let b = ~[5,6,7,8,9,0];
3422 assert_eq!(a.mut_slice(2,4).move_from(b,1,6), 2);
3423 assert!(a == [1,2,6,7,5]);
3427 fn test_copy_from() {
3428 let mut a = [1,2,3,4,5];
3430 assert_eq!(a.copy_from(b), 3);
3431 assert!(a == [6,7,8,4,5]);
3432 let mut c = [7,2,8,1];
3433 let d = [3,1,4,1,5,9];
3434 assert_eq!(c.copy_from(d), 4);
3435 assert!(c == [3,1,4,1]);
3439 fn test_reverse_part() {
3440 let mut values = [1,2,3,4,5];
3441 values.mut_slice(1, 4).reverse();
3442 assert!(values == [1,4,3,2,5]);
3447 macro_rules! test_show_vec(
3448 ($x:expr, $x_str:expr) => ({
3449 let (x, x_str) = ($x, $x_str);
3450 assert_eq!(format!("{}", x), x_str);
3451 assert_eq!(format!("{}", x.as_slice()), x_str);
3454 let empty: ~[int] = ~[];
3455 test_show_vec!(empty, "[]".to_owned());
3456 test_show_vec!(~[1], "[1]".to_owned());
3457 test_show_vec!(~[1, 2, 3], "[1, 2, 3]".to_owned());
3458 test_show_vec!(~[~[], ~[1u], ~[1u, 1u]], "[[], [1], [1, 1]]".to_owned());
3460 let empty_mut: &mut [int] = &mut[];
3461 test_show_vec!(empty_mut, "[]".to_owned());
3462 test_show_vec!(&mut[1], "[1]".to_owned());
3463 test_show_vec!(&mut[1, 2, 3], "[1, 2, 3]".to_owned());
3464 test_show_vec!(&mut[&mut[], &mut[1u], &mut[1u, 1u]], "[[], [1], [1, 1]]".to_owned());
3468 fn test_vec_default() {
3469 use default::Default;
3472 let v: $ty = Default::default();
3473 assert!(v.is_empty());
3483 fn test_bytes_set_memory() {
3484 use slice::bytes::MutableByteVector;
3485 let mut values = [1u8,2,3,4,5];
3486 values.mut_slice(0,5).set_memory(0xAB);
3487 assert!(values == [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
3488 values.mut_slice(2,4).set_memory(0xFF);
3489 assert!(values == [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
3494 fn test_overflow_does_not_cause_segfault() {
3496 v.reserve_exact(-1);
3503 fn test_overflow_does_not_cause_segfault_managed() {
3505 let mut v = vec![Rc::new(1)];
3506 v.reserve_exact(-1);
3511 fn test_mut_split_at() {
3512 let mut values = [1u8,2,3,4,5];
3514 let (left, right) = values.mut_split_at(2);
3515 assert!(left.slice(0, left.len()) == [1, 2]);
3516 for p in left.mut_iter() {
3520 assert!(right.slice(0, right.len()) == [3, 4, 5]);
3521 for p in right.mut_iter() {
3526 assert!(values == [2, 3, 5, 6, 7]);
3529 #[deriving(Clone, Eq)]
3533 fn test_iter_zero_sized() {
3534 let mut v = vec![Foo, Foo, Foo];
3535 assert_eq!(v.len(), 3);
3544 for f in v.slice(1, 3).iter() {
3550 for f in v.mut_iter() {
3556 for f in v.move_iter() {
3560 assert_eq!(cnt, 11);
3562 let xs = vec![Foo, Foo, Foo];
3563 assert_eq!(format!("{:?}", xs.slice(0, 2).to_owned()),
3564 "~[slice::tests::Foo, slice::tests::Foo]".to_owned());
3566 let xs: [Foo, ..3] = [Foo, Foo, Foo];
3567 assert_eq!(format!("{:?}", xs.slice(0, 2).to_owned()),
3568 "~[slice::tests::Foo, slice::tests::Foo]".to_owned());
3570 for f in xs.iter() {
3578 fn test_shrink_to_fit() {
3579 let mut xs = vec![0, 1, 2, 3];
3580 for i in range(4, 100) {
3583 assert_eq!(xs.capacity(), 128);
3585 assert_eq!(xs.capacity(), 100);
3586 assert_eq!(xs, range(0, 100).collect::<Vec<_>>());
3590 fn test_starts_with() {
3591 assert!(bytes!("foobar").starts_with(bytes!("foo")));
3592 assert!(!bytes!("foobar").starts_with(bytes!("oob")));
3593 assert!(!bytes!("foobar").starts_with(bytes!("bar")));
3594 assert!(!bytes!("foo").starts_with(bytes!("foobar")));
3595 assert!(!bytes!("bar").starts_with(bytes!("foobar")));
3596 assert!(bytes!("foobar").starts_with(bytes!("foobar")));
3597 let empty: &[u8] = [];
3598 assert!(empty.starts_with(empty));
3599 assert!(!empty.starts_with(bytes!("foo")));
3600 assert!(bytes!("foobar").starts_with(empty));
3604 fn test_ends_with() {
3605 assert!(bytes!("foobar").ends_with(bytes!("bar")));
3606 assert!(!bytes!("foobar").ends_with(bytes!("oba")));
3607 assert!(!bytes!("foobar").ends_with(bytes!("foo")));
3608 assert!(!bytes!("foo").ends_with(bytes!("foobar")));
3609 assert!(!bytes!("bar").ends_with(bytes!("foobar")));
3610 assert!(bytes!("foobar").ends_with(bytes!("foobar")));
3611 let empty: &[u8] = [];
3612 assert!(empty.ends_with(empty));
3613 assert!(!empty.ends_with(bytes!("foo")));
3614 assert!(bytes!("foobar").ends_with(empty));
3618 fn test_shift_ref() {
3619 let mut x: &[int] = [1, 2, 3, 4, 5];
3620 let h = x.shift_ref();
3621 assert_eq!(*h.unwrap(), 1);
3622 assert_eq!(x.len(), 4);
3623 assert_eq!(x[0], 2);
3624 assert_eq!(x[3], 5);
3626 let mut y: &[int] = [];
3627 assert_eq!(y.shift_ref(), None);
3632 let mut x: &[int] = [1, 2, 3, 4, 5];
3633 let h = x.pop_ref();
3634 assert_eq!(*h.unwrap(), 5);
3635 assert_eq!(x.len(), 4);
3636 assert_eq!(x[0], 1);
3637 assert_eq!(x[3], 4);
3639 let mut y: &[int] = [];
3640 assert!(y.pop_ref().is_none());
3644 fn test_mut_splitator() {
3645 let mut xs = [0,1,0,2,3,0,0,4,5,0];
3646 assert_eq!(xs.mut_split(|x| *x == 0).len(), 6);
3647 for slice in xs.mut_split(|x| *x == 0) {
3650 assert!(xs == [0,1,0,3,2,0,0,5,4,0]);
3652 let mut xs = [0,1,0,2,3,0,0,4,5,0,6,7];
3653 for slice in xs.mut_split(|x| *x == 0).take(5) {
3656 assert!(xs == [0,1,0,3,2,0,0,5,4,0,6,7]);
3660 fn test_mut_splitator_rev() {
3661 let mut xs = [1,2,0,3,4,0,0,5,6,0];
3662 for slice in xs.mut_split(|x| *x == 0).rev().take(4) {
3665 assert!(xs == [1,2,0,4,3,0,0,6,5,0]);
3669 fn test_mut_chunks() {
3670 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
3671 for (i, chunk) in v.mut_chunks(3).enumerate() {
3672 for x in chunk.mut_iter() {
3676 let result = [0u8, 0, 0, 1, 1, 1, 2];
3677 assert!(v == result);
3681 fn test_mut_chunks_rev() {
3682 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
3683 for (i, chunk) in v.mut_chunks(3).rev().enumerate() {
3684 for x in chunk.mut_iter() {
3688 let result = [2u8, 2, 2, 1, 1, 1, 0];
3689 assert!(v == result);
3694 fn test_mut_chunks_0() {
3695 let mut v = [1, 2, 3, 4];
3696 let _it = v.mut_chunks(0);
3700 fn test_mut_shift_ref() {
3701 let mut x: &mut [int] = [1, 2, 3, 4, 5];
3702 let h = x.mut_shift_ref();
3703 assert_eq!(*h.unwrap(), 1);
3704 assert_eq!(x.len(), 4);
3705 assert_eq!(x[0], 2);
3706 assert_eq!(x[3], 5);
3708 let mut y: &mut [int] = [];
3709 assert!(y.mut_shift_ref().is_none());
3713 fn test_mut_pop_ref() {
3714 let mut x: &mut [int] = [1, 2, 3, 4, 5];
3715 let h = x.mut_pop_ref();
3716 assert_eq!(*h.unwrap(), 5);
3717 assert_eq!(x.len(), 4);
3718 assert_eq!(x[0], 1);
3719 assert_eq!(x[3], 4);
3721 let mut y: &mut [int] = [];
3722 assert!(y.mut_pop_ref().is_none());
3726 fn test_mut_last() {
3727 let mut x = [1, 2, 3, 4, 5];
3728 let h = x.mut_last();
3729 assert_eq!(*h.unwrap(), 5);
3731 let y: &mut [int] = [];
3732 assert!(y.mut_last().is_none());
3739 use self::test::Bencher;
3743 use rand::{weak_rng, Rng};
3746 fn iterator(b: &mut Bencher) {
3747 // peculiar numbers to stop LLVM from optimising the summation
3749 let v = Vec::from_fn(100, |i| i ^ (i << 1) ^ (i >> 1));
3756 // sum == 11806, to stop dead code elimination.
3757 if sum == 0 {fail!()}
3762 fn mut_iterator(b: &mut Bencher) {
3763 let mut v = Vec::from_elem(100, 0);
3767 for x in v.mut_iter() {
3775 fn add(b: &mut Bencher) {
3776 let xs: &[int] = [5, ..10];
3777 let ys: &[int] = [5, ..10];
3784 fn concat(b: &mut Bencher) {
3785 let xss: Vec<Vec<uint>> = Vec::from_fn(100, |i| range(0, i).collect());
3787 xss.as_slice().concat_vec()
3792 fn connect(b: &mut Bencher) {
3793 let xss: Vec<Vec<uint>> = Vec::from_fn(100, |i| range(0, i).collect());
3795 xss.as_slice().connect_vec(&0)
3800 fn push(b: &mut Bencher) {
3801 let mut vec: Vec<uint> = vec![];
3809 fn starts_with_same_vector(b: &mut Bencher) {
3810 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3812 vec.as_slice().starts_with(vec.as_slice())
3817 fn starts_with_single_element(b: &mut Bencher) {
3818 let vec: Vec<uint> = vec![0];
3820 vec.as_slice().starts_with(vec.as_slice())
3825 fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
3826 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3827 let mut match_vec: Vec<uint> = Vec::from_fn(99, |i| i);
3830 vec.as_slice().starts_with(match_vec.as_slice())
3835 fn ends_with_same_vector(b: &mut Bencher) {
3836 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3838 vec.as_slice().ends_with(vec.as_slice())
3843 fn ends_with_single_element(b: &mut Bencher) {
3844 let vec: Vec<uint> = vec![0];
3846 vec.as_slice().ends_with(vec.as_slice())
3851 fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
3852 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3853 let mut match_vec: Vec<uint> = Vec::from_fn(100, |i| i);
3854 match_vec.as_mut_slice()[0] = 200;
3856 vec.as_slice().starts_with(match_vec.as_slice())
3861 fn contains_last_element(b: &mut Bencher) {
3862 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3869 fn zero_1kb_from_elem(b: &mut Bencher) {
3871 Vec::from_elem(1024, 0u8)
3876 fn zero_1kb_set_memory(b: &mut Bencher) {
3878 let mut v: Vec<uint> = Vec::with_capacity(1024);
3880 let vp = v.as_mut_ptr();
3881 ptr::set_memory(vp, 0, 1024);
3889 fn zero_1kb_fixed_repeat(b: &mut Bencher) {
3896 fn zero_1kb_loop_set(b: &mut Bencher) {
3898 let mut v: Vec<uint> = Vec::with_capacity(1024);
3902 for i in range(0u, 1024) {
3909 fn zero_1kb_mut_iter(b: &mut Bencher) {
3911 let mut v = Vec::with_capacity(1024);
3915 for x in v.mut_iter() {
3923 fn random_inserts(b: &mut Bencher) {
3924 let mut rng = weak_rng();
3926 let mut v = Vec::from_elem(30, (0u, 0u));
3927 for _ in range(0, 100) {
3929 v.insert(rng.gen::<uint>() % (l + 1),
3935 fn random_removes(b: &mut Bencher) {
3936 let mut rng = weak_rng();
3938 let mut v = Vec::from_elem(130, (0u, 0u));
3939 for _ in range(0, 100) {
3941 v.remove(rng.gen::<uint>() % l);
3947 fn sort_random_small(b: &mut Bencher) {
3948 let mut rng = weak_rng();
3950 let mut v = rng.gen_vec::<u64>(5);
3951 v.as_mut_slice().sort();
3953 b.bytes = 5 * mem::size_of::<u64>() as u64;
3957 fn sort_random_medium(b: &mut Bencher) {
3958 let mut rng = weak_rng();
3960 let mut v = rng.gen_vec::<u64>(100);
3961 v.as_mut_slice().sort();
3963 b.bytes = 100 * mem::size_of::<u64>() as u64;
3967 fn sort_random_large(b: &mut Bencher) {
3968 let mut rng = weak_rng();
3970 let mut v = rng.gen_vec::<u64>(10000);
3971 v.as_mut_slice().sort();
3973 b.bytes = 10000 * mem::size_of::<u64>() as u64;
3977 fn sort_sorted(b: &mut Bencher) {
3978 let mut v = Vec::from_fn(10000, |i| i);
3982 b.bytes = (v.len() * mem::size_of_val(v.get(0))) as u64;
3985 type BigSortable = (u64,u64,u64,u64);
3988 fn sort_big_random_small(b: &mut Bencher) {
3989 let mut rng = weak_rng();
3991 let mut v = rng.gen_vec::<BigSortable>(5);
3994 b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
3998 fn sort_big_random_medium(b: &mut Bencher) {
3999 let mut rng = weak_rng();
4001 let mut v = rng.gen_vec::<BigSortable>(100);
4004 b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
4008 fn sort_big_random_large(b: &mut Bencher) {
4009 let mut rng = weak_rng();
4011 let mut v = rng.gen_vec::<BigSortable>(10000);
4014 b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
4018 fn sort_big_sorted(b: &mut Bencher) {
4019 let mut v = Vec::from_fn(10000u, |i| (i, i, i, i));
4023 b.bytes = (v.len() * mem::size_of_val(v.get(0))) as u64;