1 // Copyright 2012-2013 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.
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 `VecIterator`, 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 = ~[0, 1, 2];
59 // numbers is now ~[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 borrowed pointers 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`.
102 #[warn(non_camel_case_types)];
106 use clone::{Clone, DeepClone};
107 use container::{Container, Mutable};
108 use cmp::{Eq, TotalOrd, Ordering, Less, Equal, Greater};
110 use default::Default;
112 use libc::{c_char, c_void};
113 use num::{Integer, CheckedAdd, Saturating};
114 use option::{None, Option, Some};
115 use ptr::to_unsafe_ptr;
118 use rt::global_heap::{malloc_raw, realloc_raw, exchange_free};
119 use rt::local_heap::local_free;
123 use unstable::finally::Finally;
124 use unstable::intrinsics;
125 use unstable::intrinsics::{get_tydesc, owns_managed};
126 use unstable::raw::{Box, Repr, Slice, Vec};
130 * Creates and initializes an owned vector.
132 * Creates an owned vector of size `n_elts` and initializes the elements
133 * to the value returned by the function `op`.
135 pub fn from_fn<T>(n_elts: uint, op: |uint| -> T) -> ~[T] {
137 let mut v = with_capacity(n_elts);
138 let p = v.as_mut_ptr();
139 let mut i: uint = 0u;
142 intrinsics::move_val_init(&mut(*ptr::mut_offset(p, i as int)), op(i));
153 * Creates and initializes an owned vector.
155 * Creates an owned vector of size `n_elts` and initializes the elements
158 pub fn from_elem<T:Clone>(n_elts: uint, t: T) -> ~[T] {
159 // FIXME (#7136): manually inline from_fn for 2x plus speedup (sadly very
160 // important, from_elem is a bottleneck in borrowck!). Unfortunately it
161 // still is substantially slower than using the unsafe
162 // vec::with_capacity/ptr::set_memory for primitive types.
164 let mut v = with_capacity(n_elts);
165 let p = v.as_mut_ptr();
169 intrinsics::move_val_init(&mut(*ptr::mut_offset(p, i as int)), t.clone());
179 /// Creates a new vector with a capacity of `capacity`
181 pub fn with_capacity<T>(capacity: uint) -> ~[T] {
183 if owns_managed::<T>() {
185 vec.reserve(capacity);
188 let alloc = capacity * mem::nonzero_size_of::<T>();
189 let size = alloc + mem::size_of::<Vec<()>>();
190 if alloc / mem::nonzero_size_of::<T>() != capacity || size < alloc {
191 fail!("vector size is too large: {}", capacity);
193 let ptr = malloc_raw(size) as *mut Vec<()>;
194 (*ptr).alloc = alloc;
202 * Builds a vector by calling a provided function with an argument
203 * function that pushes an element to the back of a vector.
204 * The initial capacity for the vector may optionally be specified.
208 * * size - An option, maybe containing initial size of the vector to reserve
209 * * builder - A function that will construct the vector. It receives
210 * as an argument a function that will push an element
211 * onto the vector being constructed.
214 pub fn build<A>(size: Option<uint>, builder: |push: |v: A||) -> ~[A] {
215 let mut vec = with_capacity(size.unwrap_or(4));
216 builder(|x| vec.push(x));
220 /// An iterator over the slices of a vector separated by elements that
221 /// match a predicate function.
222 pub struct SplitIterator<'a, T> {
225 priv pred: 'a |t: &T| -> bool,
229 impl<'a, T> Iterator<&'a [T]> for SplitIterator<'a, T> {
231 fn next(&mut self) -> Option<&'a [T]> {
232 if self.finished { return None; }
235 self.finished = true;
239 match self.v.iter().position(|x| (self.pred)(x)) {
241 self.finished = true;
245 let ret = Some(self.v.slice(0, idx));
246 self.v = self.v.slice(idx + 1, self.v.len());
254 fn size_hint(&self) -> (uint, Option<uint>) {
258 // if the predicate doesn't match anything, we yield one slice
259 // if it matches every element, we yield N+1 empty slices where
260 // N is either the number of elements or the number of splits.
261 match (self.v.len(), self.n) {
262 (0,_) => (1, Some(1)),
263 (_,0) => (1, Some(1)),
264 (l,n) => (1, cmp::min(l,n).checked_add(&1u))
269 /// An iterator over the slices of a vector separated by elements that
270 /// match a predicate function, from back to front.
271 pub struct RSplitIterator<'a, T> {
274 priv pred: 'a |t: &T| -> bool,
278 impl<'a, T> Iterator<&'a [T]> for RSplitIterator<'a, T> {
280 fn next(&mut self) -> Option<&'a [T]> {
281 if self.finished { return None; }
284 self.finished = true;
288 match self.v.iter().rposition(|x| (self.pred)(x)) {
290 self.finished = true;
294 let ret = Some(self.v.slice(idx + 1, self.v.len()));
295 self.v = self.v.slice(0, idx);
303 fn size_hint(&self) -> (uint, Option<uint>) {
307 match (self.v.len(), self.n) {
308 (0,_) => (1, Some(1)),
309 (_,0) => (1, Some(1)),
310 (l,n) => (1, cmp::min(l,n).checked_add(&1u))
317 /// Iterates over the `rhs` vector, copying each element and appending it to the
318 /// `lhs`. Afterwards, the `lhs` is then returned for use again.
320 pub fn append<T:Clone>(lhs: ~[T], rhs: &[T]) -> ~[T] {
326 /// Appends one element to the vector provided. The vector itself is then
327 /// returned for use again.
329 pub fn append_one<T>(lhs: ~[T], x: T) -> ~[T] {
335 // Functional utilities
338 * Apply a function to each element of a vector and return a concatenation
339 * of each result vector
341 pub fn flat_map<T, U>(v: &[T], f: |t: &T| -> ~[U]) -> ~[U] {
342 let mut result = ~[];
343 for elem in v.iter() { result.push_all_move(f(elem)); }
347 #[allow(missing_doc)]
348 pub trait VectorVector<T> {
349 // FIXME #5898: calling these .concat and .connect conflicts with
350 // StrVector::con{cat,nect}, since they have generic contents.
351 /// Flattens a vector of vectors of T into a single vector of T.
352 fn concat_vec(&self) -> ~[T];
354 /// Concatenate a vector of vectors, placing a given separator between each.
355 fn connect_vec(&self, sep: &T) -> ~[T];
358 impl<'a, T: Clone, V: Vector<T>> VectorVector<T> for &'a [V] {
359 fn concat_vec(&self) -> ~[T] {
360 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
361 let mut result = with_capacity(size);
362 for v in self.iter() {
363 result.push_all(v.as_slice())
368 fn connect_vec(&self, sep: &T) -> ~[T] {
369 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
370 let mut result = with_capacity(size + self.len());
371 let mut first = true;
372 for v in self.iter() {
373 if first { first = false } else { result.push(sep.clone()) }
374 result.push_all(v.as_slice())
381 * Convert an iterator of pairs into a pair of vectors.
383 * Returns a tuple containing two vectors where the i-th element of the first
384 * vector contains the first element of the i-th tuple of the input iterator,
385 * and the i-th element of the second vector contains the second element
386 * of the i-th tuple of the input iterator.
388 pub fn unzip<T, U, V: Iterator<(T, U)>>(mut iter: V) -> (~[T], ~[U]) {
389 let (lo, _) = iter.size_hint();
390 let mut ts = with_capacity(lo);
391 let mut us = with_capacity(lo);
399 /// An Iterator that yields the element swaps needed to produce
400 /// a sequence of all possible permutations for an indexed sequence of
401 /// elements. Each permutation is only a single swap apart.
403 /// The Steinhaus–Johnson–Trotter algorithm is used.
405 /// Generates even and odd permutations alternately.
407 /// The last generated swap is always (0, 1), and it returns the
408 /// sequence to its initial order.
409 pub struct ElementSwaps {
410 priv sdir: ~[SizeDirection],
411 /// If true, emit the last swap that returns the sequence to initial state
412 priv emit_reset: bool,
416 /// Create an `ElementSwaps` iterator for a sequence of `length` elements
417 pub fn new(length: uint) -> ElementSwaps {
418 // Initialize `sdir` with a direction that position should move in
419 // (all negative at the beginning) and the `size` of the
420 // element (equal to the original index).
423 sdir: range(0, length)
424 .map(|i| SizeDirection{ size: i, dir: Neg })
430 enum Direction { Pos, Neg }
432 /// An Index and Direction together
433 struct SizeDirection {
438 impl Iterator<(uint, uint)> for ElementSwaps {
440 fn next(&mut self) -> Option<(uint, uint)> {
441 fn new_pos(i: uint, s: Direction) -> uint {
442 i + match s { Pos => 1, Neg => -1 }
445 // Find the index of the largest mobile element:
446 // The direction should point into the vector, and the
447 // swap should be with a smaller `size` element.
448 let max = self.sdir.iter().map(|&x| x).enumerate()
450 new_pos(i, sd.dir) < self.sdir.len() &&
451 self.sdir[new_pos(i, sd.dir)].size < sd.size)
452 .max_by(|&(_, sd)| sd.size);
455 let j = new_pos(i, sd.dir);
456 self.sdir.swap(i, j);
458 // Swap the direction of each larger SizeDirection
459 for x in self.sdir.mut_iter() {
460 if x.size > sd.size {
461 x.dir = match x.dir { Pos => Neg, Neg => Pos };
466 None => if self.emit_reset && self.sdir.len() > 1 {
467 self.emit_reset = false;
476 /// An Iterator that uses `ElementSwaps` to iterate through
477 /// all possible permutations of a vector.
479 /// The first iteration yields a clone of the vector as it is,
480 /// then each successive element is the vector with one
483 /// Generates even and odd permutations alternately.
484 pub struct Permutations<T> {
485 priv swaps: ElementSwaps,
489 impl<T: Clone> Iterator<~[T]> for Permutations<T> {
491 fn next(&mut self) -> Option<~[T]> {
492 match self.swaps.next() {
495 let elt = self.v.clone();
503 /// An iterator over the (overlapping) slices of length `size` within
506 pub struct WindowIter<'a, T> {
511 impl<'a, T> Iterator<&'a [T]> for WindowIter<'a, T> {
513 fn next(&mut self) -> Option<&'a [T]> {
514 if self.size > self.v.len() {
517 let ret = Some(self.v.slice(0, self.size));
518 self.v = self.v.slice(1, self.v.len());
524 fn size_hint(&self) -> (uint, Option<uint>) {
525 if self.size > self.v.len() {
528 let x = self.v.len() - self.size;
529 (x.saturating_add(1), x.checked_add(&1u))
534 /// An iterator over a vector in (non-overlapping) chunks (`size`
535 /// elements at a time).
537 /// When the vector len is not evenly divided by the chunk size,
538 /// the last slice of the iteration will be the remainder.
540 pub struct ChunkIter<'a, T> {
545 impl<'a, T> Iterator<&'a [T]> for ChunkIter<'a, T> {
547 fn next(&mut self) -> Option<&'a [T]> {
548 if self.v.len() == 0 {
551 let chunksz = cmp::min(self.v.len(), self.size);
552 let (fst, snd) = (self.v.slice_to(chunksz),
553 self.v.slice_from(chunksz));
560 fn size_hint(&self) -> (uint, Option<uint>) {
561 if self.v.len() == 0 {
564 let (n, rem) = self.v.len().div_rem(&self.size);
565 let n = if rem > 0 { n+1 } else { n };
571 impl<'a, T> DoubleEndedIterator<&'a [T]> for ChunkIter<'a, T> {
573 fn next_back(&mut self) -> Option<&'a [T]> {
574 if self.v.len() == 0 {
577 let remainder = self.v.len() % self.size;
578 let chunksz = if remainder != 0 { remainder } else { self.size };
579 let (fst, snd) = (self.v.slice_to(self.v.len() - chunksz),
580 self.v.slice_from(self.v.len() - chunksz));
587 impl<'a, T> RandomAccessIterator<&'a [T]> for ChunkIter<'a, T> {
589 fn indexable(&self) -> uint {
590 self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
594 fn idx(&self, index: uint) -> Option<&'a [T]> {
595 if index < self.indexable() {
596 let lo = index * self.size;
597 let mut hi = lo + self.size;
598 if hi < lo || hi > self.v.len() { hi = self.v.len(); }
600 Some(self.v.slice(lo, hi))
610 #[allow(missing_doc)]
615 use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Equiv};
619 impl<'a,T:Eq> Eq for &'a [T] {
620 fn eq(&self, other: & &'a [T]) -> bool {
621 self.len() == other.len() &&
622 order::eq(self.iter(), other.iter())
624 fn ne(&self, other: & &'a [T]) -> bool {
625 self.len() != other.len() ||
626 order::ne(self.iter(), other.iter())
630 impl<T:Eq> Eq for ~[T] {
632 fn eq(&self, other: &~[T]) -> bool { self.as_slice() == *other }
634 fn ne(&self, other: &~[T]) -> bool { !self.eq(other) }
637 impl<T:Eq> Eq for @[T] {
639 fn eq(&self, other: &@[T]) -> bool { self.as_slice() == *other }
641 fn ne(&self, other: &@[T]) -> bool { !self.eq(other) }
644 impl<'a,T:TotalEq> TotalEq for &'a [T] {
645 fn equals(&self, other: & &'a [T]) -> bool {
646 self.len() == other.len() &&
647 order::equals(self.iter(), other.iter())
651 impl<T:TotalEq> TotalEq for ~[T] {
653 fn equals(&self, other: &~[T]) -> bool { self.as_slice().equals(&other.as_slice()) }
656 impl<T:TotalEq> TotalEq for @[T] {
658 fn equals(&self, other: &@[T]) -> bool { self.as_slice().equals(&other.as_slice()) }
661 impl<'a,T:Eq, V: Vector<T>> Equiv<V> for &'a [T] {
663 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
666 impl<'a,T:Eq, V: Vector<T>> Equiv<V> for ~[T] {
668 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
671 impl<'a,T:Eq, V: Vector<T>> Equiv<V> for @[T] {
673 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
676 impl<'a,T:TotalOrd> TotalOrd for &'a [T] {
677 fn cmp(&self, other: & &'a [T]) -> Ordering {
678 order::cmp(self.iter(), other.iter())
682 impl<T: TotalOrd> TotalOrd for ~[T] {
684 fn cmp(&self, other: &~[T]) -> Ordering { self.as_slice().cmp(&other.as_slice()) }
687 impl<T: TotalOrd> TotalOrd for @[T] {
689 fn cmp(&self, other: &@[T]) -> Ordering { self.as_slice().cmp(&other.as_slice()) }
692 impl<'a, T: Eq + Ord> Ord for &'a [T] {
693 fn lt(&self, other: & &'a [T]) -> bool {
694 order::lt(self.iter(), other.iter())
697 fn le(&self, other: & &'a [T]) -> bool {
698 order::le(self.iter(), other.iter())
701 fn ge(&self, other: & &'a [T]) -> bool {
702 order::ge(self.iter(), other.iter())
705 fn gt(&self, other: & &'a [T]) -> bool {
706 order::gt(self.iter(), other.iter())
710 impl<T: Eq + Ord> Ord for ~[T] {
712 fn lt(&self, other: &~[T]) -> bool { self.as_slice() < other.as_slice() }
714 fn le(&self, other: &~[T]) -> bool { self.as_slice() <= other.as_slice() }
716 fn ge(&self, other: &~[T]) -> bool { self.as_slice() >= other.as_slice() }
718 fn gt(&self, other: &~[T]) -> bool { self.as_slice() > other.as_slice() }
721 impl<T: Eq + Ord> Ord for @[T] {
723 fn lt(&self, other: &@[T]) -> bool { self.as_slice() < other.as_slice() }
725 fn le(&self, other: &@[T]) -> bool { self.as_slice() <= other.as_slice() }
727 fn ge(&self, other: &@[T]) -> bool { self.as_slice() >= other.as_slice() }
729 fn gt(&self, other: &@[T]) -> bool { self.as_slice() > other.as_slice() }
732 impl<'a,T:Clone, V: Vector<T>> Add<V, ~[T]> for &'a [T] {
734 fn add(&self, rhs: &V) -> ~[T] {
735 let mut res = with_capacity(self.len() + rhs.as_slice().len());
737 res.push_all(rhs.as_slice());
742 impl<T:Clone, V: Vector<T>> Add<V, ~[T]> for ~[T] {
744 fn add(&self, rhs: &V) -> ~[T] {
745 self.as_slice() + rhs.as_slice()
753 /// Any vector that can be represented as a slice.
754 pub trait Vector<T> {
755 /// Work with `self` as a slice.
756 fn as_slice<'a>(&'a self) -> &'a [T];
759 impl<'a,T> Vector<T> for &'a [T] {
761 fn as_slice<'a>(&'a self) -> &'a [T] { *self }
764 impl<T> Vector<T> for ~[T] {
766 fn as_slice<'a>(&'a self) -> &'a [T] { let v: &'a [T] = *self; v }
769 impl<T> Vector<T> for @[T] {
771 fn as_slice<'a>(&'a self) -> &'a [T] { let v: &'a [T] = *self; v }
774 impl<'a, T> Container for &'a [T] {
775 /// Returns the length of a vector
777 fn len(&self) -> uint {
782 impl<T> Container for ~[T] {
783 /// Returns the length of a vector
785 fn len(&self) -> uint {
790 /// Extension methods for vector slices with copyable elements
791 pub trait CopyableVector<T> {
792 /// Copy `self` into a new owned vector
793 fn to_owned(&self) -> ~[T];
795 /// Convert `self` into a owned vector, not making a copy if possible.
796 fn into_owned(self) -> ~[T];
799 /// Extension methods for vector slices
800 impl<'a, T: Clone> CopyableVector<T> for &'a [T] {
801 /// Returns a copy of `v`.
803 fn to_owned(&self) -> ~[T] {
804 let mut result = with_capacity(self.len());
805 for e in self.iter() {
806 result.push((*e).clone());
812 fn into_owned(self) -> ~[T] { self.to_owned() }
815 /// Extension methods for owned vectors
816 impl<T: Clone> CopyableVector<T> for ~[T] {
818 fn to_owned(&self) -> ~[T] { self.clone() }
821 fn into_owned(self) -> ~[T] { self }
824 /// Extension methods for managed vectors
825 impl<T: Clone> CopyableVector<T> for @[T] {
827 fn to_owned(&self) -> ~[T] { self.as_slice().to_owned() }
830 fn into_owned(self) -> ~[T] { self.to_owned() }
833 /// Extension methods for vectors
834 pub trait ImmutableVector<'a, T> {
836 * Returns a slice of self between `start` and `end`.
838 * Fails when `start` or `end` point outside the bounds of self,
839 * or when `start` > `end`.
841 fn slice(&self, start: uint, end: uint) -> &'a [T];
844 * Returns a slice of self from `start` to the end of the vec.
846 * Fails when `start` points outside the bounds of self.
848 fn slice_from(&self, start: uint) -> &'a [T];
851 * Returns a slice of self from the start of the vec to `end`.
853 * Fails when `end` points outside the bounds of self.
855 fn slice_to(&self, end: uint) -> &'a [T];
856 /// Returns an iterator over the vector
857 fn iter(self) -> VecIterator<'a, T>;
858 /// Returns a reversed iterator over a vector
859 fn rev_iter(self) -> RevIterator<'a, T>;
860 /// Returns an iterator over the subslices of the vector which are
861 /// separated by elements that match `pred`. The matched element
862 /// is not contained in the subslices.
863 fn split(self, pred: 'a |&T| -> bool) -> SplitIterator<'a, T>;
864 /// Returns an iterator over the subslices of the vector which are
865 /// separated by elements that match `pred`, limited to splitting
866 /// at most `n` times. The matched element is not contained in
868 fn splitn(self, n: uint, pred: 'a |&T| -> bool) -> SplitIterator<'a, T>;
869 /// Returns an iterator over the subslices of the vector which are
870 /// separated by elements that match `pred`. This starts at the
871 /// end of the vector and works backwards. The matched element is
872 /// not contained in the subslices.
873 fn rsplit(self, pred: 'a |&T| -> bool) -> RSplitIterator<'a, T>;
874 /// Returns an iterator over the subslices of the vector which are
875 /// separated by elements that match `pred` limited to splitting
876 /// at most `n` times. This starts at the end of the vector and
877 /// works backwards. The matched element is not contained in the
879 fn rsplitn(self, n: uint, pred: 'a |&T| -> bool) -> RSplitIterator<'a, T>;
882 * Returns an iterator over all contiguous windows of length
883 * `size`. The windows overlap. If the vector is shorter than
884 * `size`, the iterator returns no values.
888 * Fails if `size` is 0.
892 * Print the adjacent pairs of a vector (i.e. `[1,2]`, `[2,3]`,
896 * let v = &[1,2,3,4];
897 * for win in v.windows(2) {
898 * println!("{:?}", win);
903 fn windows(self, size: uint) -> WindowIter<'a, T>;
906 * Returns an iterator over `size` elements of the vector at a
907 * time. The chunks do not overlap. If `size` does not divide the
908 * length of the vector, then the last chunk will not have length
913 * Fails if `size` is 0.
917 * Print the vector two elements at a time (i.e. `[1,2]`,
921 * let v = &[1,2,3,4,5];
922 * for win in v.chunks(2) {
923 * println!("{:?}", win);
928 fn chunks(self, size: uint) -> ChunkIter<'a, T>;
930 /// Returns the element of a vector at the given index, or `None` if the
931 /// index is out of bounds
932 fn get_opt(&self, index: uint) -> Option<&'a T>;
933 /// Returns the first element of a vector, failing if the vector is empty.
934 fn head(&self) -> &'a T;
935 /// Returns the first element of a vector, or `None` if it is empty
936 fn head_opt(&self) -> Option<&'a T>;
937 /// Returns all but the first element of a vector
938 fn tail(&self) -> &'a [T];
939 /// Returns all but the first `n' elements of a vector
940 fn tailn(&self, n: uint) -> &'a [T];
941 /// Returns all but the last element of a vector
942 fn init(&self) -> &'a [T];
943 /// Returns all but the last `n' elements of a vector
944 fn initn(&self, n: uint) -> &'a [T];
945 /// Returns the last element of a vector, failing if the vector is empty.
946 fn last(&self) -> &'a T;
947 /// Returns the last element of a vector, or `None` if it is empty.
948 fn last_opt(&self) -> Option<&'a T>;
950 * Apply a function to each element of a vector and return a concatenation
951 * of each result vector
953 fn flat_map<U>(&self, f: |t: &T| -> ~[U]) -> ~[U];
954 /// Returns a pointer to the element at the given index, without doing
956 unsafe fn unsafe_ref(&self, index: uint) -> *T;
959 * Returns an unsafe pointer to the vector's buffer
961 * The caller must ensure that the vector outlives the pointer this
962 * function returns, or else it will end up pointing to garbage.
964 * Modifying the vector may cause its buffer to be reallocated, which
965 * would also make any pointers to it invalid.
967 fn as_ptr(&self) -> *T;
970 * Binary search a sorted vector with a comparator function.
972 * The comparator function should implement an order consistent
973 * with the sort order of the underlying vector, returning an
974 * order code that indicates whether its argument is `Less`,
975 * `Equal` or `Greater` the desired target.
977 * Returns the index where the comparator returned `Equal`, or `None` if
980 fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint>;
982 /// Deprecated, use iterators where possible
983 /// (`self.iter().map(f)`). Apply a function to each element
984 /// of a vector and return the results.
985 fn map<U>(&self, |t: &T| -> U) -> ~[U];
988 * Returns a mutable reference to the first element in this slice
989 * and adjusts the slice in place so that it no longer contains
990 * that element. O(1).
995 * let head = &self[0];
996 * *self = self.slice_from(1);
1000 * Fails if slice is empty.
1002 fn shift_ref(&mut self) -> &'a T;
1005 * Returns a mutable reference to the last element in this slice
1006 * and adjusts the slice in place so that it no longer contains
1007 * that element. O(1).
1012 * let tail = &self[self.len() - 1];
1013 * *self = self.slice_to(self.len() - 1);
1017 * Fails if slice is empty.
1019 fn pop_ref(&mut self) -> &'a T;
1022 impl<'a,T> ImmutableVector<'a, T> for &'a [T] {
1024 fn slice(&self, start: uint, end: uint) -> &'a [T] {
1025 assert!(start <= end);
1026 assert!(end <= self.len());
1028 cast::transmute(Slice {
1029 data: self.as_ptr().offset(start as int),
1036 fn slice_from(&self, start: uint) -> &'a [T] {
1037 self.slice(start, self.len())
1041 fn slice_to(&self, end: uint) -> &'a [T] {
1046 fn iter(self) -> VecIterator<'a, T> {
1048 let p = self.as_ptr();
1049 if mem::size_of::<T>() == 0 {
1051 end: (p as uint + self.len()) as *T,
1055 end: p.offset(self.len() as int),
1062 fn rev_iter(self) -> RevIterator<'a, T> {
1063 self.iter().invert()
1067 fn split(self, pred: 'a |&T| -> bool) -> SplitIterator<'a, T> {
1068 self.splitn(uint::max_value, pred)
1072 fn splitn(self, n: uint, pred: 'a |&T| -> bool) -> SplitIterator<'a, T> {
1082 fn rsplit(self, pred: 'a |&T| -> bool) -> RSplitIterator<'a, T> {
1083 self.rsplitn(uint::max_value, pred)
1087 fn rsplitn(self, n: uint, pred: 'a |&T| -> bool) -> RSplitIterator<'a, T> {
1097 fn windows(self, size: uint) -> WindowIter<'a, T> {
1099 WindowIter { v: self, size: size }
1103 fn chunks(self, size: uint) -> ChunkIter<'a, T> {
1105 ChunkIter { v: self, size: size }
1109 fn get_opt(&self, index: uint) -> Option<&'a T> {
1110 if index < self.len() { Some(&self[index]) } else { None }
1114 fn head(&self) -> &'a T {
1115 if self.len() == 0 { fail!("head: empty vector") }
1120 fn head_opt(&self) -> Option<&'a T> {
1121 if self.len() == 0 { None } else { Some(&self[0]) }
1125 fn tail(&self) -> &'a [T] { self.slice(1, self.len()) }
1128 fn tailn(&self, n: uint) -> &'a [T] { self.slice(n, self.len()) }
1131 fn init(&self) -> &'a [T] {
1132 self.slice(0, self.len() - 1)
1136 fn initn(&self, n: uint) -> &'a [T] {
1137 self.slice(0, self.len() - n)
1141 fn last(&self) -> &'a T {
1142 if self.len() == 0 { fail!("last: empty vector") }
1143 &self[self.len() - 1]
1147 fn last_opt(&self) -> Option<&'a T> {
1148 if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
1152 fn flat_map<U>(&self, f: |t: &T| -> ~[U]) -> ~[U] {
1157 unsafe fn unsafe_ref(&self, index: uint) -> *T {
1158 self.repr().data.offset(index as int)
1162 fn as_ptr(&self) -> *T {
1167 fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint> {
1168 let mut base : uint = 0;
1169 let mut lim : uint = self.len();
1172 let ix = base + (lim >> 1);
1173 match f(&self[ix]) {
1174 Equal => return Some(ix),
1186 fn map<U>(&self, f: |t: &T| -> U) -> ~[U] {
1187 self.iter().map(f).collect()
1190 fn shift_ref(&mut self) -> &'a T {
1192 let s: &mut Slice<T> = cast::transmute(self);
1197 fn pop_ref(&mut self) -> &'a T {
1199 let s: &mut Slice<T> = cast::transmute(self);
1205 /// Extension methods for vectors contain `Eq` elements.
1206 pub trait ImmutableEqVector<T:Eq> {
1207 /// Find the first index containing a matching value
1208 fn position_elem(&self, t: &T) -> Option<uint>;
1210 /// Find the last index containing a matching value
1211 fn rposition_elem(&self, t: &T) -> Option<uint>;
1213 /// Return true if a vector contains an element with the given value
1214 fn contains(&self, x: &T) -> bool;
1216 /// Returns true if `needle` is a prefix of the vector.
1217 fn starts_with(&self, needle: &[T]) -> bool;
1219 /// Returns true if `needle` is a suffix of the vector.
1220 fn ends_with(&self, needle: &[T]) -> bool;
1223 impl<'a,T:Eq> ImmutableEqVector<T> for &'a [T] {
1225 fn position_elem(&self, x: &T) -> Option<uint> {
1226 self.iter().position(|y| *x == *y)
1230 fn rposition_elem(&self, t: &T) -> Option<uint> {
1231 self.iter().rposition(|x| *x == *t)
1235 fn contains(&self, x: &T) -> bool {
1236 self.iter().any(|elt| *x == *elt)
1240 fn starts_with(&self, needle: &[T]) -> bool {
1241 let n = needle.len();
1242 self.len() >= n && needle == self.slice_to(n)
1246 fn ends_with(&self, needle: &[T]) -> bool {
1247 let (m, n) = (self.len(), needle.len());
1248 m >= n && needle == self.slice_from(m - n)
1252 /// Extension methods for vectors containing `TotalOrd` elements.
1253 pub trait ImmutableTotalOrdVector<T: TotalOrd> {
1255 * Binary search a sorted vector for a given element.
1257 * Returns the index of the element or None if not found.
1259 fn bsearch_elem(&self, x: &T) -> Option<uint>;
1262 impl<'a, T: TotalOrd> ImmutableTotalOrdVector<T> for &'a [T] {
1263 fn bsearch_elem(&self, x: &T) -> Option<uint> {
1264 self.bsearch(|p| p.cmp(x))
1268 /// Extension methods for vectors containing `Clone` elements.
1269 pub trait ImmutableCopyableVector<T> {
1271 * Partitions the vector into those that satisfies the predicate, and
1272 * those that do not.
1274 fn partitioned(&self, f: |&T| -> bool) -> (~[T], ~[T]);
1276 /// Create an iterator that yields every possible permutation of the
1277 /// vector in succession.
1278 fn permutations(self) -> Permutations<T>;
1281 impl<'a,T:Clone> ImmutableCopyableVector<T> for &'a [T] {
1283 fn partitioned(&self, f: |&T| -> bool) -> (~[T], ~[T]) {
1284 let mut lefts = ~[];
1285 let mut rights = ~[];
1287 for elt in self.iter() {
1289 lefts.push((*elt).clone());
1291 rights.push((*elt).clone());
1298 fn permutations(self) -> Permutations<T> {
1300 swaps: ElementSwaps::new(self.len()),
1307 /// Extension methods for owned vectors.
1308 pub trait OwnedVector<T> {
1309 /// Creates a consuming iterator, that is, one that moves each
1310 /// value out of the vector (from start to end). The vector cannot
1311 /// be used after calling this.
1316 /// let v = ~[~"a", ~"b"];
1317 /// for s in v.move_iter() {
1318 /// // s has type ~str, not &~str
1322 fn move_iter(self) -> MoveIterator<T>;
1323 /// Creates a consuming iterator that moves out of the vector in
1325 fn move_rev_iter(self) -> MoveRevIterator<T>;
1328 * Reserves capacity for exactly `n` elements in the given vector.
1330 * If the capacity for `self` is already equal to or greater than the requested
1331 * capacity, then no action is taken.
1335 * * n - The number of elements to reserve space for
1339 * This method always succeeds in reserving space for `n` elements, or it does
1342 fn reserve(&mut self, n: uint);
1344 * Reserves capacity for at least `n` elements in the given vector.
1346 * This function will over-allocate in order to amortize the allocation costs
1347 * in scenarios where the caller may need to repeatedly reserve additional
1350 * If the capacity for `self` is already equal to or greater than the requested
1351 * capacity, then no action is taken.
1355 * * n - The number of elements to reserve space for
1357 fn reserve_at_least(&mut self, n: uint);
1359 * Reserves capacity for at least `n` additional elements in the given vector.
1363 * Fails if the new required capacity overflows uint.
1365 * May also fail if `reserve` fails.
1367 fn reserve_additional(&mut self, n: uint);
1368 /// Returns the number of elements the vector can hold without reallocating.
1369 fn capacity(&self) -> uint;
1370 /// Shrink the capacity of the vector to match the length
1371 fn shrink_to_fit(&mut self);
1373 /// Append an element to a vector
1374 fn push(&mut self, t: T);
1375 /// Takes ownership of the vector `rhs`, moving all elements into
1376 /// the current vector. This does not copy any elements, and it is
1377 /// illegal to use the `rhs` vector after calling this method
1378 /// (because it is moved here).
1383 /// let mut a = ~[~1];
1384 /// a.push_all_move(~[~2, ~3, ~4]);
1385 /// assert!(a == ~[~1, ~2, ~3, ~4]);
1387 fn push_all_move(&mut self, rhs: ~[T]);
1388 /// Remove the last element from a vector and return it, failing if it is empty
1389 fn pop(&mut self) -> T;
1390 /// Remove the last element from a vector and return it, or `None` if it is empty
1391 fn pop_opt(&mut self) -> Option<T>;
1392 /// Removes the first element from a vector and return it
1393 fn shift(&mut self) -> T;
1394 /// Removes the first element from a vector and return it, or `None` if it is empty
1395 fn shift_opt(&mut self) -> Option<T>;
1396 /// Prepend an element to the vector
1397 fn unshift(&mut self, x: T);
1399 /// Insert an element at position i within v, shifting all
1400 /// elements after position i one position to the right.
1401 fn insert(&mut self, i: uint, x:T);
1403 /// Remove and return the element at position i within v, shifting
1404 /// all elements after position i one position to the left.
1405 fn remove(&mut self, i: uint) -> T;
1408 * Remove an element from anywhere in the vector and return it, replacing it
1409 * with the last element. This does not preserve ordering, but is O(1).
1411 * Fails if index >= length.
1413 fn swap_remove(&mut self, index: uint) -> T;
1415 /// Shorten a vector, dropping excess elements.
1416 fn truncate(&mut self, newlen: uint);
1419 * Like `filter()`, but in place. Preserves order of `v`. Linear time.
1421 fn retain(&mut self, f: |t: &T| -> bool);
1423 * Partitions the vector into those that satisfies the predicate, and
1424 * those that do not.
1426 fn partition(self, f: |&T| -> bool) -> (~[T], ~[T]);
1429 * Expands a vector in place, initializing the new elements to the result of
1432 * Function `init_op` is called `n` times with the values [0..`n`)
1436 * * n - The number of elements to add
1437 * * init_op - A function to call to retrieve each appended element's
1440 fn grow_fn(&mut self, n: uint, op: |uint| -> T);
1443 * Sets the length of a vector
1445 * This will explicitly set the size of the vector, without actually
1446 * modifying its buffers, so it is up to the caller to ensure that
1447 * the vector is actually the specified size.
1449 unsafe fn set_len(&mut self, new_len: uint);
1452 impl<T> OwnedVector<T> for ~[T] {
1454 fn move_iter(self) -> MoveIterator<T> {
1456 let iter = cast::transmute(self.iter());
1457 let ptr = cast::transmute(self);
1458 MoveIterator { allocation: ptr, iter: iter }
1463 fn move_rev_iter(self) -> MoveRevIterator<T> {
1464 self.move_iter().invert()
1467 fn reserve(&mut self, n: uint) {
1468 // Only make the (slow) call into the runtime if we have to
1469 if self.capacity() < n {
1471 let td = get_tydesc::<T>();
1472 if owns_managed::<T>() {
1473 let ptr: *mut *mut Box<Vec<()>> = cast::transmute(self);
1474 ::at_vec::raw::reserve_raw(td, ptr, n);
1476 let ptr: *mut *mut Vec<()> = cast::transmute(self);
1477 let alloc = n * mem::nonzero_size_of::<T>();
1478 let size = alloc + mem::size_of::<Vec<()>>();
1479 if alloc / mem::nonzero_size_of::<T>() != n || size < alloc {
1480 fail!("vector size is too large: {}", n);
1482 *ptr = realloc_raw(*ptr as *mut c_void, size)
1484 (**ptr).alloc = alloc;
1491 fn reserve_at_least(&mut self, n: uint) {
1492 self.reserve(uint::next_power_of_two_opt(n).unwrap_or(n));
1496 fn reserve_additional(&mut self, n: uint) {
1497 if self.capacity() - self.len() < n {
1498 match self.len().checked_add(&n) {
1499 None => fail!("vec::reserve_additional: `uint` overflow"),
1500 Some(new_cap) => self.reserve_at_least(new_cap)
1506 fn capacity(&self) -> uint {
1508 if owns_managed::<T>() {
1509 let repr: **Box<Vec<()>> = cast::transmute(self);
1510 (**repr).data.alloc / mem::nonzero_size_of::<T>()
1512 let repr: **Vec<()> = cast::transmute(self);
1513 (**repr).alloc / mem::nonzero_size_of::<T>()
1518 fn shrink_to_fit(&mut self) {
1520 let ptr: *mut *mut Vec<()> = cast::transmute(self);
1521 let alloc = (**ptr).fill;
1522 let size = alloc + mem::size_of::<Vec<()>>();
1523 *ptr = realloc_raw(*ptr as *mut c_void, size) as *mut Vec<()>;
1524 (**ptr).alloc = alloc;
1529 fn push(&mut self, t: T) {
1531 if owns_managed::<T>() {
1532 let repr: **Box<Vec<()>> = cast::transmute(&mut *self);
1533 let fill = (**repr).data.fill;
1534 if (**repr).data.alloc <= fill {
1535 self.reserve_additional(1);
1540 let repr: **Vec<()> = cast::transmute(&mut *self);
1541 let fill = (**repr).fill;
1542 if (**repr).alloc <= fill {
1543 self.reserve_additional(1);
1550 // This doesn't bother to make sure we have space.
1551 #[inline] // really pretty please
1552 unsafe fn push_fast<T>(this: &mut ~[T], t: T) {
1553 if owns_managed::<T>() {
1554 let repr: **mut Box<Vec<u8>> = cast::transmute(this);
1555 let fill = (**repr).data.fill;
1556 (**repr).data.fill += mem::nonzero_size_of::<T>();
1557 let p = to_unsafe_ptr(&((**repr).data.data));
1558 let p = ptr::offset(p, fill as int) as *mut T;
1559 intrinsics::move_val_init(&mut(*p), t);
1561 let repr: **mut Vec<u8> = cast::transmute(this);
1562 let fill = (**repr).fill;
1563 (**repr).fill += mem::nonzero_size_of::<T>();
1564 let p = to_unsafe_ptr(&((**repr).data));
1565 let p = ptr::offset(p, fill as int) as *mut T;
1566 intrinsics::move_val_init(&mut(*p), t);
1573 fn push_all_move(&mut self, mut rhs: ~[T]) {
1574 let self_len = self.len();
1575 let rhs_len = rhs.len();
1576 let new_len = self_len + rhs_len;
1577 self.reserve_additional(rhs.len());
1578 unsafe { // Note: infallible.
1579 let self_p = self.as_mut_ptr();
1580 let rhs_p = rhs.as_ptr();
1581 ptr::copy_memory(ptr::mut_offset(self_p, self_len as int), rhs_p, rhs_len);
1582 self.set_len(new_len);
1587 fn pop_opt(&mut self) -> Option<T> {
1591 let valptr = ptr::to_mut_unsafe_ptr(&mut self[ln - 1u]);
1593 self.set_len(ln - 1u);
1594 Some(ptr::read_ptr(&*valptr))
1602 fn pop(&mut self) -> T {
1603 self.pop_opt().expect("pop: empty vector")
1607 fn shift(&mut self) -> T {
1608 self.shift_opt().expect("shift: empty vector")
1611 fn shift_opt(&mut self) -> Option<T> {
1614 1 => self.pop_opt(),
1616 let last = self.pop();
1617 let first = self.pop_opt();
1623 let next_len = len - 1;
1625 let ptr = self.as_ptr();
1627 // copy out the head element, for the moment it exists
1628 // unsafely on the stack and as the first element of the
1630 let head = ptr::read_ptr(ptr);
1632 // Memcpy everything to the left one element (leaving the
1633 // last element unsafely in two consecutive memory
1635 ptr::copy_memory(self.as_mut_ptr(), ptr.offset(1), next_len);
1637 // set the new length, which means the second instance of
1638 // the last element is forgotten.
1639 self.set_len(next_len);
1647 fn unshift(&mut self, x: T) {
1648 let v = util::replace(self, ~[x]);
1649 self.push_all_move(v);
1651 fn insert(&mut self, i: uint, x:T) {
1652 let len = self.len();
1658 self.swap(j, j - 1);
1662 fn remove(&mut self, i: uint) -> T {
1663 let len = self.len();
1668 self.swap(j, j + 1);
1673 fn swap_remove(&mut self, index: uint) -> T {
1674 let ln = self.len();
1676 fail!("vec::swap_remove - index {} >= length {}", index, ln);
1679 self.swap(index, ln - 1);
1683 fn truncate(&mut self, newlen: uint) {
1684 let oldlen = self.len();
1685 assert!(newlen <= oldlen);
1688 let p = self.as_mut_ptr();
1689 // This loop is optimized out for non-drop types.
1690 for i in range(newlen, oldlen) {
1691 ptr::read_and_zero_ptr(p.offset(i as int));
1694 unsafe { self.set_len(newlen); }
1697 fn retain(&mut self, f: |t: &T| -> bool) {
1698 let len = self.len();
1699 let mut deleted: uint = 0;
1701 for i in range(0u, len) {
1704 } else if deleted > 0 {
1705 self.swap(i - deleted, i);
1710 self.truncate(len - deleted);
1715 fn partition(self, f: |&T| -> bool) -> (~[T], ~[T]) {
1716 let mut lefts = ~[];
1717 let mut rights = ~[];
1719 for elt in self.move_iter() {
1729 fn grow_fn(&mut self, n: uint, op: |uint| -> T) {
1730 let new_len = self.len() + n;
1731 self.reserve_at_least(new_len);
1732 let mut i: uint = 0u;
1739 unsafe fn set_len(&mut self, new_len: uint) {
1740 if owns_managed::<T>() {
1741 let repr: **mut Box<Vec<()>> = cast::transmute(self);
1742 (**repr).data.fill = new_len * mem::nonzero_size_of::<T>();
1744 let repr: **mut Vec<()> = cast::transmute(self);
1745 (**repr).fill = new_len * mem::nonzero_size_of::<T>();
1750 impl<T> Mutable for ~[T] {
1751 /// Clear the vector, removing all values.
1752 fn clear(&mut self) { self.truncate(0) }
1755 /// Extension methods for owned vectors containing `Clone` elements.
1756 pub trait OwnedCopyableVector<T:Clone> {
1757 /// Iterates over the slice `rhs`, copies each element, and then appends it to
1758 /// the vector provided `v`. The `rhs` vector is traversed in-order.
1763 /// let mut a = ~[1];
1764 /// a.push_all([2, 3, 4]);
1765 /// assert!(a == ~[1, 2, 3, 4]);
1767 fn push_all(&mut self, rhs: &[T]);
1770 * Expands a vector in place, initializing the new elements to a given value
1774 * * n - The number of elements to add
1775 * * initval - The value for the new elements
1777 fn grow(&mut self, n: uint, initval: &T);
1780 * Sets the value of a vector element at a given index, growing the vector as
1783 * Sets the element at position `index` to `val`. If `index` is past the end
1784 * of the vector, expands the vector by replicating `initval` to fill the
1785 * intervening space.
1787 fn grow_set(&mut self, index: uint, initval: &T, val: T);
1790 impl<T:Clone> OwnedCopyableVector<T> for ~[T] {
1792 fn push_all(&mut self, rhs: &[T]) {
1793 let new_len = self.len() + rhs.len();
1794 self.reserve(new_len);
1796 for elt in rhs.iter() {
1797 self.push((*elt).clone())
1800 fn grow(&mut self, n: uint, initval: &T) {
1801 let new_len = self.len() + n;
1802 self.reserve_at_least(new_len);
1803 let mut i: uint = 0u;
1806 self.push((*initval).clone());
1810 fn grow_set(&mut self, index: uint, initval: &T, val: T) {
1812 if index >= l { self.grow(index - l + 1u, initval); }
1817 /// Extension methods for owned vectors containing `Eq` elements.
1818 pub trait OwnedEqVector<T:Eq> {
1820 * Remove consecutive repeated elements from a vector; if the vector is
1821 * sorted, this removes all duplicates.
1823 fn dedup(&mut self);
1826 impl<T:Eq> OwnedEqVector<T> for ~[T] {
1827 fn dedup(&mut self) {
1829 // Although we have a mutable reference to `self`, we cannot make
1830 // *arbitrary* changes. There exists the possibility that this
1831 // vector is contained with an `@mut` box and hence is still
1832 // readable by the outside world during the `Eq` comparisons.
1833 // Moreover, those comparisons could fail, so we must ensure
1834 // that the vector is in a valid state at all time.
1836 // The way that we handle this is by using swaps; we iterate
1837 // over all the elements, swapping as we go so that at the end
1838 // the elements we wish to keep are in the front, and those we
1839 // wish to reject are at the back. We can then truncate the
1840 // vector. This operation is still O(n).
1842 // Example: We start in this state, where `r` represents "next
1843 // read" and `w` represents "next_write`.
1846 // +---+---+---+---+---+---+
1847 // | 0 | 1 | 1 | 2 | 3 | 3 |
1848 // +---+---+---+---+---+---+
1851 // Comparing self[r] against self[w-1], tis is not a duplicate, so
1852 // we swap self[r] and self[w] (no effect as r==w) and then increment both
1853 // r and w, leaving us with:
1856 // +---+---+---+---+---+---+
1857 // | 0 | 1 | 1 | 2 | 3 | 3 |
1858 // +---+---+---+---+---+---+
1861 // Comparing self[r] against self[w-1], this value is a duplicate,
1862 // so we increment `r` but leave everything else unchanged:
1865 // +---+---+---+---+---+---+
1866 // | 0 | 1 | 1 | 2 | 3 | 3 |
1867 // +---+---+---+---+---+---+
1870 // Comparing self[r] against self[w-1], this is not a duplicate,
1871 // so swap self[r] and self[w] and advance r and w:
1874 // +---+---+---+---+---+---+
1875 // | 0 | 1 | 2 | 1 | 3 | 3 |
1876 // +---+---+---+---+---+---+
1879 // Not a duplicate, repeat:
1882 // +---+---+---+---+---+---+
1883 // | 0 | 1 | 2 | 3 | 1 | 3 |
1884 // +---+---+---+---+---+---+
1887 // Duplicate, advance r. End of vec. Truncate to w.
1889 let ln = self.len();
1890 if ln < 1 { return; }
1892 // Avoid bounds checks by using unsafe pointers.
1893 let p = self.as_mut_ptr();
1898 let p_r = ptr::mut_offset(p, r as int);
1899 let p_wm1 = ptr::mut_offset(p, (w - 1) as int);
1902 let p_w = ptr::mut_offset(p_wm1, 1);
1903 util::swap(&mut *p_r, &mut *p_w);
1915 /// Extension methods for vectors such that their elements are
1917 pub trait MutableVector<'a, T> {
1918 /// Return a slice that points into another slice.
1919 fn mut_slice(self, start: uint, end: uint) -> &'a mut [T];
1922 * Returns a slice of self from `start` to the end of the vec.
1924 * Fails when `start` points outside the bounds of self.
1926 fn mut_slice_from(self, start: uint) -> &'a mut [T];
1929 * Returns a slice of self from the start of the vec to `end`.
1931 * Fails when `end` points outside the bounds of self.
1933 fn mut_slice_to(self, end: uint) -> &'a mut [T];
1935 /// Returns an iterator that allows modifying each value
1936 fn mut_iter(self) -> VecMutIterator<'a, T>;
1938 /// Returns a reversed iterator that allows modifying each value
1939 fn mut_rev_iter(self) -> MutRevIterator<'a, T>;
1941 /// Returns an iterator over the mutable subslices of the vector
1942 /// which are separated by elements that match `pred`. The
1943 /// matched element is not contained in the subslices.
1944 fn mut_split(self, pred: 'a |&T| -> bool) -> MutSplitIterator<'a, T>;
1947 * Returns an iterator over `size` elements of the vector at a time.
1948 * The chunks are mutable and do not overlap. If `size` does not divide the
1949 * length of the vector, then the last chunk will not have length
1954 * Fails if `size` is 0.
1956 fn mut_chunks(self, chunk_size: uint) -> MutChunkIter<'a, T>;
1959 * Returns a mutable reference to the first element in this slice
1960 * and adjusts the slice in place so that it no longer contains
1961 * that element. O(1).
1966 * let head = &mut self[0];
1967 * *self = self.mut_slice_from(1);
1971 * Fails if slice is empty.
1973 fn mut_shift_ref(&mut self) -> &'a mut T;
1976 * Returns a mutable reference to the last element in this slice
1977 * and adjusts the slice in place so that it no longer contains
1978 * that element. O(1).
1983 * let tail = &mut self[self.len() - 1];
1984 * *self = self.mut_slice_to(self.len() - 1);
1988 * Fails if slice is empty.
1990 fn mut_pop_ref(&mut self) -> &'a mut T;
1993 * Swaps two elements in a vector
1997 * * a - The index of the first element
1998 * * b - The index of the second element
2000 fn swap(self, a: uint, b: uint);
2003 * Divides one `&mut` into two. The first will
2004 * contain all indices from `0..mid` (excluding the index `mid`
2005 * itself) and the second will contain all indices from
2006 * `mid..len` (excluding the index `len` itself).
2008 fn mut_split_at(self, mid: uint) -> (&'a mut [T],
2011 /// Reverse the order of elements in a vector, in place
2015 * Consumes `src` and moves as many elements as it can into `self`
2016 * from the range [start,end).
2018 * Returns the number of elements copied (the shorter of self.len()
2023 * * src - A mutable vector of `T`
2024 * * start - The index into `src` to start copying from
2025 * * end - The index into `str` to stop copying from
2027 fn move_from(self, src: ~[T], start: uint, end: uint) -> uint;
2029 /// Returns an unsafe mutable pointer to the element in index
2030 unsafe fn unsafe_mut_ref(self, index: uint) -> *mut T;
2032 /// Return an unsafe mutable pointer to the vector's buffer.
2034 /// The caller must ensure that the vector outlives the pointer this
2035 /// function returns, or else it will end up pointing to garbage.
2037 /// Modifying the vector may cause its buffer to be reallocated, which
2038 /// would also make any pointers to it invalid.
2040 fn as_mut_ptr(self) -> *mut T;
2042 /// Unsafely sets the element in index to the value
2043 unsafe fn unsafe_set(self, index: uint, val: T);
2046 * Unchecked vector index assignment. Does not drop the
2047 * old value and hence is only suitable when the vector
2048 * is newly allocated.
2050 unsafe fn init_elem(self, i: uint, val: T);
2052 /// Copies data from `src` to `self`.
2054 /// `self` and `src` must not overlap. Fails if `self` is
2055 /// shorter than `src`.
2056 unsafe fn copy_memory(self, src: &[T]);
2059 impl<'a,T> MutableVector<'a, T> for &'a mut [T] {
2061 fn mut_slice(self, start: uint, end: uint) -> &'a mut [T] {
2062 assert!(start <= end);
2063 assert!(end <= self.len());
2065 cast::transmute(Slice {
2066 data: self.as_mut_ptr().offset(start as int) as *T,
2073 fn mut_slice_from(self, start: uint) -> &'a mut [T] {
2074 let len = self.len();
2075 self.mut_slice(start, len)
2079 fn mut_slice_to(self, end: uint) -> &'a mut [T] {
2080 self.mut_slice(0, end)
2084 fn mut_split_at(self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
2086 let len = self.len();
2087 let self2: &'a mut [T] = cast::transmute_copy(&self);
2088 (self.mut_slice(0, mid), self2.mut_slice(mid, len))
2093 fn mut_iter(self) -> VecMutIterator<'a, T> {
2095 let p = self.as_mut_ptr();
2096 if mem::size_of::<T>() == 0 {
2097 VecMutIterator{ptr: p,
2098 end: (p as uint + self.len()) as *mut T,
2101 VecMutIterator{ptr: p,
2102 end: p.offset(self.len() as int),
2109 fn mut_rev_iter(self) -> MutRevIterator<'a, T> {
2110 self.mut_iter().invert()
2114 fn mut_split(self, pred: 'a |&T| -> bool) -> MutSplitIterator<'a, T> {
2115 MutSplitIterator { v: self, pred: pred, finished: false }
2119 fn mut_chunks(self, chunk_size: uint) -> MutChunkIter<'a, T> {
2120 assert!(chunk_size > 0);
2121 let len = self.len();
2122 MutChunkIter { v: self, chunk_size: chunk_size, remaining: len }
2125 fn mut_shift_ref(&mut self) -> &'a mut T {
2127 let s: &mut Slice<T> = cast::transmute(self);
2128 cast::transmute_mut(&*raw::shift_ptr(s))
2132 fn mut_pop_ref(&mut self) -> &'a mut T {
2134 let s: &mut Slice<T> = cast::transmute(self);
2135 cast::transmute_mut(&*raw::pop_ptr(s))
2139 fn swap(self, a: uint, b: uint) {
2141 // Can't take two mutable loans from one vector, so instead just cast
2142 // them to their raw pointers to do the swap
2143 let pa: *mut T = &mut self[a];
2144 let pb: *mut T = &mut self[b];
2145 ptr::swap_ptr(pa, pb);
2150 let mut i: uint = 0;
2151 let ln = self.len();
2153 self.swap(i, ln - i - 1);
2159 fn move_from(self, mut src: ~[T], start: uint, end: uint) -> uint {
2160 for (a, b) in self.mut_iter().zip(src.mut_slice(start, end).mut_iter()) {
2163 cmp::min(self.len(), end-start)
2167 unsafe fn unsafe_mut_ref(self, index: uint) -> *mut T {
2168 ptr::mut_offset(self.repr().data as *mut T, index as int)
2172 fn as_mut_ptr(self) -> *mut T {
2173 self.repr().data as *mut T
2177 unsafe fn unsafe_set(self, index: uint, val: T) {
2178 *self.unsafe_mut_ref(index) = val;
2182 unsafe fn init_elem(self, i: uint, val: T) {
2183 intrinsics::move_val_init(&mut (*self.as_mut_ptr().offset(i as int)), val);
2187 unsafe fn copy_memory(self, src: &[T]) {
2188 let len_src = src.len();
2189 assert!(self.len() >= len_src);
2190 ptr::copy_nonoverlapping_memory(self.as_mut_ptr(), src.as_ptr(), len_src)
2194 /// Trait for &[T] where T is Cloneable
2195 pub trait MutableCloneableVector<T> {
2196 /// Copies as many elements from `src` as it can into `self`
2197 /// (the shorter of self.len() and src.len()). Returns the number of elements copied.
2198 fn copy_from(self, &[T]) -> uint;
2201 impl<'a, T:Clone> MutableCloneableVector<T> for &'a mut [T] {
2203 fn copy_from(self, src: &[T]) -> uint {
2204 for (a, b) in self.mut_iter().zip(src.iter()) {
2207 cmp::min(self.len(), src.len())
2212 * Constructs a vector from an unsafe pointer to a buffer
2216 * * ptr - An unsafe pointer to a buffer of `T`
2217 * * elts - The number of elements in the buffer
2219 // Wrapper for fn in raw: needs to be called by net_tcp::on_tcp_read_cb
2220 pub unsafe fn from_buf<T>(ptr: *T, elts: uint) -> ~[T] {
2221 raw::from_buf_raw(ptr, elts)
2224 /// Unsafe operations
2228 use vec::{with_capacity, MutableVector};
2229 use unstable::raw::Slice;
2232 * Form a slice from a pointer and length (as a number of units,
2236 pub unsafe fn buf_as_slice<T,U>(p: *T, len: uint, f: |v: &[T]| -> U)
2238 f(cast::transmute(Slice {
2245 * Form a slice from a pointer and length (as a number of units,
2249 pub unsafe fn mut_buf_as_slice<T,
2253 f: |v: &mut [T]| -> U)
2255 f(cast::transmute(Slice {
2262 * Constructs a vector from an unsafe pointer to a buffer
2266 * * ptr - An unsafe pointer to a buffer of `T`
2267 * * elts - The number of elements in the buffer
2269 // Was in raw, but needs to be called by net_tcp::on_tcp_read_cb
2271 pub unsafe fn from_buf_raw<T>(ptr: *T, elts: uint) -> ~[T] {
2272 let mut dst = with_capacity(elts);
2274 ptr::copy_memory(dst.as_mut_ptr(), ptr, elts);
2279 * Returns a pointer to first element in slice and adjusts
2280 * slice so it no longer contains that element. Fails if
2281 * slice is empty. O(1).
2283 pub unsafe fn shift_ptr<T>(slice: &mut Slice<T>) -> *T {
2284 if slice.len == 0 { fail!("shift on empty slice"); }
2285 let head: *T = slice.data;
2286 slice.data = ptr::offset(slice.data, 1);
2292 * Returns a pointer to last element in slice and adjusts
2293 * slice so it no longer contains that element. Fails if
2294 * slice is empty. O(1).
2296 pub unsafe fn pop_ptr<T>(slice: &mut Slice<T>) -> *T {
2297 if slice.len == 0 { fail!("pop on empty slice"); }
2298 let tail: *T = ptr::offset(slice.data, (slice.len - 1) as int);
2304 /// Operations on `[u8]`.
2306 use container::Container;
2307 use vec::MutableVector;
2310 /// A trait for operations on mutable `[u8]`s.
2311 pub trait MutableByteVector {
2312 /// Sets all bytes of the receiver to the given value.
2313 fn set_memory(self, value: u8);
2316 impl<'a> MutableByteVector for &'a mut [u8] {
2318 fn set_memory(self, value: u8) {
2319 unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
2323 /// Copies data from `src` to `dst`
2325 /// `src` and `dst` must not overlap. Fails if the length of `dst`
2326 /// is less than the length of `src`.
2328 pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
2329 // Bound checks are done at .copy_memory.
2330 unsafe { dst.copy_memory(src) }
2334 * Allocate space in `dst` and append the data to `src`.
2337 pub fn push_bytes(dst: &mut ~[u8], src: &[u8]) {
2338 let old_len = dst.len();
2339 dst.reserve_additional(src.len());
2341 ptr::copy_memory(dst.as_mut_ptr().offset(old_len as int), src.as_ptr(), src.len());
2342 dst.set_len(old_len + src.len());
2347 impl<A: Clone> Clone for ~[A] {
2349 fn clone(&self) -> ~[A] {
2350 self.iter().map(|item| item.clone()).collect()
2353 fn clone_from(&mut self, source: &~[A]) {
2354 if self.len() < source.len() {
2355 *self = source.clone()
2357 self.truncate(source.len());
2358 for (x, y) in self.mut_iter().zip(source.iter()) {
2365 impl<A: DeepClone> DeepClone for ~[A] {
2367 fn deep_clone(&self) -> ~[A] {
2368 self.iter().map(|item| item.deep_clone()).collect()
2371 fn deep_clone_from(&mut self, source: &~[A]) {
2372 if self.len() < source.len() {
2373 *self = source.deep_clone()
2375 self.truncate(source.len());
2376 for (x, y) in self.mut_iter().zip(source.iter()) {
2377 x.deep_clone_from(y);
2383 // This works because every lifetime is a sub-lifetime of 'static
2384 impl<'a, A> Default for &'a [A] {
2385 fn default() -> &'a [A] { &'a [] }
2388 impl<A> Default for ~[A] {
2389 fn default() -> ~[A] { ~[] }
2392 impl<A> Default for @[A] {
2393 fn default() -> @[A] { @[] }
2396 macro_rules! iterator {
2397 (struct $name:ident -> $ptr:ty, $elem:ty) => {
2398 /// An iterator for iterating over a vector.
2399 pub struct $name<'a, T> {
2402 priv lifetime: Option<$elem> // FIXME: #5922
2405 impl<'a, T> Iterator<$elem> for $name<'a, T> {
2407 fn next(&mut self) -> Option<$elem> {
2408 // could be implemented with slices, but this avoids bounds checks
2410 if self.ptr == self.end {
2414 self.ptr = if mem::size_of::<T>() == 0 {
2415 // purposefully don't use 'ptr.offset' because for
2416 // vectors with 0-size elements this would return the
2418 cast::transmute(self.ptr as uint + 1)
2423 Some(cast::transmute(old))
2429 fn size_hint(&self) -> (uint, Option<uint>) {
2430 let diff = (self.end as uint) - (self.ptr as uint);
2431 let exact = diff / mem::nonzero_size_of::<T>();
2432 (exact, Some(exact))
2436 impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
2438 fn next_back(&mut self) -> Option<$elem> {
2439 // could be implemented with slices, but this avoids bounds checks
2441 if self.end == self.ptr {
2444 self.end = if mem::size_of::<T>() == 0 {
2445 // See above for why 'ptr.offset' isn't used
2446 cast::transmute(self.end as uint - 1)
2450 Some(cast::transmute(self.end))
2458 impl<'a, T> RandomAccessIterator<&'a T> for VecIterator<'a, T> {
2460 fn indexable(&self) -> uint {
2461 let (exact, _) = self.size_hint();
2466 fn idx(&self, index: uint) -> Option<&'a T> {
2468 if index < self.indexable() {
2469 cast::transmute(self.ptr.offset(index as int))
2477 iterator!{struct VecIterator -> *T, &'a T}
2478 pub type RevIterator<'a, T> = Invert<VecIterator<'a, T>>;
2480 impl<'a, T> ExactSize<&'a T> for VecIterator<'a, T> {}
2481 impl<'a, T> ExactSize<&'a mut T> for VecMutIterator<'a, T> {}
2483 impl<'a, T> Clone for VecIterator<'a, T> {
2484 fn clone(&self) -> VecIterator<'a, T> { *self }
2487 iterator!{struct VecMutIterator -> *mut T, &'a mut T}
2488 pub type MutRevIterator<'a, T> = Invert<VecMutIterator<'a, T>>;
2490 /// An iterator over the subslices of the vector which are separated
2491 /// by elements that match `pred`.
2492 pub struct MutSplitIterator<'a, T> {
2493 priv v: &'a mut [T],
2494 priv pred: 'a |t: &T| -> bool,
2498 impl<'a, T> Iterator<&'a mut [T]> for MutSplitIterator<'a, T> {
2500 fn next(&mut self) -> Option<&'a mut [T]> {
2501 if self.finished { return None; }
2503 match self.v.iter().position(|x| (self.pred)(x)) {
2505 self.finished = true;
2506 let tmp = util::replace(&mut self.v, &mut []);
2507 let len = tmp.len();
2508 let (head, tail) = tmp.mut_split_at(len);
2513 let tmp = util::replace(&mut self.v, &mut []);
2514 let (head, tail) = tmp.mut_split_at(idx);
2515 self.v = tail.mut_slice_from(1);
2522 fn size_hint(&self) -> (uint, Option<uint>) {
2523 if self.finished { return (0, Some(0)) }
2525 // if the predicate doesn't match anything, we yield one slice
2526 // if it matches every element, we yield len+1 empty slices.
2528 //(1, Some(self.v.len() + 1))
2533 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutSplitIterator<'a, T> {
2535 fn next_back(&mut self) -> Option<&'a mut [T]> {
2536 if self.finished { return None; }
2538 match self.v.iter().rposition(|x| (self.pred)(x)) {
2540 self.finished = true;
2541 let tmp = util::replace(&mut self.v, &mut []);
2542 let len = tmp.len();
2543 let (head, tail) = tmp.mut_split_at(len);
2548 let tmp = util::replace(&mut self.v, &mut []);
2549 let (head, tail) = tmp.mut_split_at(idx);
2551 Some(tail.mut_slice_from(1))
2557 /// An iterator over a vector in (non-overlapping) mutable chunks (`size` elements at a time). When
2558 /// the vector len is not evenly divided by the chunk size, the last slice of the iteration will be
2560 pub struct MutChunkIter<'a, T> {
2561 priv v: &'a mut [T],
2562 priv chunk_size: uint,
2563 priv remaining: uint
2566 impl<'a, T> Iterator<&'a mut [T]> for MutChunkIter<'a, T> {
2568 fn next(&mut self) -> Option<&'a mut [T]> {
2569 if self.remaining == 0 {
2572 let sz = cmp::min(self.remaining, self.chunk_size);
2573 let tmp = util::replace(&mut self.v, &mut []);
2574 let (head, tail) = tmp.mut_split_at(sz);
2576 self.remaining -= sz;
2582 fn size_hint(&self) -> (uint, Option<uint>) {
2583 if self.remaining == 0 {
2586 let (n, rem) = self.remaining.div_rem(&self.chunk_size);
2587 let n = if rem > 0 { n + 1 } else { n };
2593 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunkIter<'a, T> {
2595 fn next_back(&mut self) -> Option<&'a mut [T]> {
2596 if self.remaining == 0 {
2599 let remainder = self.remaining % self.chunk_size;
2600 let sz = if remainder != 0 { remainder } else { self.chunk_size };
2601 let tmp = util::replace(&mut self.v, &mut []);
2602 let (head, tail) = tmp.mut_split_at(self.remaining - sz);
2604 self.remaining -= sz;
2610 /// An iterator that moves out of a vector.
2611 pub struct MoveIterator<T> {
2612 priv allocation: *mut u8, // the block of memory allocated for the vector
2613 priv iter: VecIterator<'static, T>
2616 impl<T> Iterator<T> for MoveIterator<T> {
2618 fn next(&mut self) -> Option<T> {
2620 self.iter.next().map(|x| ptr::read_ptr(x))
2625 fn size_hint(&self) -> (uint, Option<uint>) {
2626 self.iter.size_hint()
2630 impl<T> DoubleEndedIterator<T> for MoveIterator<T> {
2632 fn next_back(&mut self) -> Option<T> {
2634 self.iter.next_back().map(|x| ptr::read_ptr(x))
2639 #[unsafe_destructor]
2640 impl<T> Drop for MoveIterator<T> {
2641 fn drop(&mut self) {
2642 // destroy the remaining elements
2645 if owns_managed::<T>() {
2646 local_free(self.allocation as *u8 as *c_char)
2648 exchange_free(self.allocation as *u8 as *c_char)
2654 /// An iterator that moves out of a vector in reverse order.
2655 pub type MoveRevIterator<T> = Invert<MoveIterator<T>>;
2657 impl<A> FromIterator<A> for ~[A] {
2658 fn from_iterator<T: Iterator<A>>(iterator: &mut T) -> ~[A] {
2659 let (lower, _) = iterator.size_hint();
2660 let mut xs = with_capacity(lower);
2661 for x in *iterator {
2668 impl<A> Extendable<A> for ~[A] {
2669 fn extend<T: Iterator<A>>(&mut self, iterator: &mut T) {
2670 let (lower, _) = iterator.size_hint();
2671 let len = self.len();
2672 self.reserve(len + lower);
2673 for x in *iterator {
2681 use option::{None, Option, Some};
2687 fn square(n: uint) -> uint { n * n }
2689 fn square_ref(n: &uint) -> uint { square(*n) }
2691 fn is_three(n: &uint) -> bool { *n == 3u }
2693 fn is_odd(n: &uint) -> bool { *n % 2u == 1u }
2695 fn is_equal(x: &uint, y:&uint) -> bool { *x == *y }
2697 fn square_if_odd_r(n: &uint) -> Option<uint> {
2698 if *n % 2u == 1u { Some(*n * *n) } else { None }
2701 fn square_if_odd_v(n: uint) -> Option<uint> {
2702 if n % 2u == 1u { Some(n * n) } else { None }
2705 fn add(x: uint, y: &uint) -> uint { x + *y }
2708 fn test_unsafe_ptrs() {
2710 // Test on-stack copy-from-buf.
2712 let mut ptr = a.as_ptr();
2713 let b = from_buf(ptr, 3u);
2714 assert_eq!(b.len(), 3u);
2715 assert_eq!(b[0], 1);
2716 assert_eq!(b[1], 2);
2717 assert_eq!(b[2], 3);
2719 // Test on-heap copy-from-buf.
2720 let c = ~[1, 2, 3, 4, 5];
2722 let d = from_buf(ptr, 5u);
2723 assert_eq!(d.len(), 5u);
2724 assert_eq!(d[0], 1);
2725 assert_eq!(d[1], 2);
2726 assert_eq!(d[2], 3);
2727 assert_eq!(d[3], 4);
2728 assert_eq!(d[4], 5);
2734 // Test on-stack from_fn.
2735 let mut v = from_fn(3u, square);
2736 assert_eq!(v.len(), 3u);
2737 assert_eq!(v[0], 0u);
2738 assert_eq!(v[1], 1u);
2739 assert_eq!(v[2], 4u);
2741 // Test on-heap from_fn.
2742 v = from_fn(5u, square);
2743 assert_eq!(v.len(), 5u);
2744 assert_eq!(v[0], 0u);
2745 assert_eq!(v[1], 1u);
2746 assert_eq!(v[2], 4u);
2747 assert_eq!(v[3], 9u);
2748 assert_eq!(v[4], 16u);
2752 fn test_from_elem() {
2753 // Test on-stack from_elem.
2754 let mut v = from_elem(2u, 10u);
2755 assert_eq!(v.len(), 2u);
2756 assert_eq!(v[0], 10u);
2757 assert_eq!(v[1], 10u);
2759 // Test on-heap from_elem.
2760 v = from_elem(6u, 20u);
2761 assert_eq!(v[0], 20u);
2762 assert_eq!(v[1], 20u);
2763 assert_eq!(v[2], 20u);
2764 assert_eq!(v[3], 20u);
2765 assert_eq!(v[4], 20u);
2766 assert_eq!(v[5], 20u);
2770 fn test_is_empty() {
2771 let xs: [int, ..0] = [];
2772 assert!(xs.is_empty());
2773 assert!(![0].is_empty());
2777 fn test_len_divzero() {
2779 let v0 : &[Z] = &[];
2780 let v1 : &[Z] = &[[]];
2781 let v2 : &[Z] = &[[], []];
2782 assert_eq!(mem::size_of::<Z>(), 0);
2783 assert_eq!(v0.len(), 0);
2784 assert_eq!(v1.len(), 1);
2785 assert_eq!(v2.len(), 2);
2791 assert_eq!(a.get_opt(1), None);
2793 assert_eq!(a.get_opt(1).unwrap(), &12);
2795 assert_eq!(a.get_opt(1).unwrap(), &12);
2801 assert_eq!(a.head(), &11);
2803 assert_eq!(a.head(), &11);
2808 fn test_head_empty() {
2809 let a: ~[int] = ~[];
2814 fn test_head_opt() {
2816 assert_eq!(a.head_opt(), None);
2818 assert_eq!(a.head_opt().unwrap(), &11);
2820 assert_eq!(a.head_opt().unwrap(), &11);
2826 assert_eq!(a.tail(), &[]);
2828 assert_eq!(a.tail(), &[12]);
2833 fn test_tail_empty() {
2834 let a: ~[int] = ~[];
2840 let mut a = ~[11, 12, 13];
2841 assert_eq!(a.tailn(0), &[11, 12, 13]);
2843 assert_eq!(a.tailn(2), &[13]);
2848 fn test_tailn_empty() {
2849 let a: ~[int] = ~[];
2856 assert_eq!(a.init(), &[]);
2858 assert_eq!(a.init(), &[11]);
2863 fn test_init_empty() {
2864 let a: ~[int] = ~[];
2870 let mut a = ~[11, 12, 13];
2871 assert_eq!(a.initn(0), &[11, 12, 13]);
2873 assert_eq!(a.initn(2), &[11]);
2878 fn test_initn_empty() {
2879 let a: ~[int] = ~[];
2886 assert_eq!(a.last(), &11);
2888 assert_eq!(a.last(), &12);
2893 fn test_last_empty() {
2894 let a: ~[int] = ~[];
2899 fn test_last_opt() {
2901 assert_eq!(a.last_opt(), None);
2903 assert_eq!(a.last_opt().unwrap(), &11);
2905 assert_eq!(a.last_opt().unwrap(), &12);
2910 // Test fixed length vector.
2911 let vec_fixed = [1, 2, 3, 4];
2912 let v_a = vec_fixed.slice(1u, vec_fixed.len()).to_owned();
2913 assert_eq!(v_a.len(), 3u);
2914 assert_eq!(v_a[0], 2);
2915 assert_eq!(v_a[1], 3);
2916 assert_eq!(v_a[2], 4);
2919 let vec_stack = &[1, 2, 3];
2920 let v_b = vec_stack.slice(1u, 3u).to_owned();
2921 assert_eq!(v_b.len(), 2u);
2922 assert_eq!(v_b[0], 2);
2923 assert_eq!(v_b[1], 3);
2925 // Test on managed heap.
2926 let vec_managed = @[1, 2, 3, 4, 5];
2927 let v_c = vec_managed.slice(0u, 3u).to_owned();
2928 assert_eq!(v_c.len(), 3u);
2929 assert_eq!(v_c[0], 1);
2930 assert_eq!(v_c[1], 2);
2931 assert_eq!(v_c[2], 3);
2933 // Test on exchange heap.
2934 let vec_unique = ~[1, 2, 3, 4, 5, 6];
2935 let v_d = vec_unique.slice(1u, 6u).to_owned();
2936 assert_eq!(v_d.len(), 5u);
2937 assert_eq!(v_d[0], 2);
2938 assert_eq!(v_d[1], 3);
2939 assert_eq!(v_d[2], 4);
2940 assert_eq!(v_d[3], 5);
2941 assert_eq!(v_d[4], 6);
2945 fn test_slice_from() {
2946 let vec = &[1, 2, 3, 4];
2947 assert_eq!(vec.slice_from(0), vec);
2948 assert_eq!(vec.slice_from(2), &[3, 4]);
2949 assert_eq!(vec.slice_from(4), &[]);
2953 fn test_slice_to() {
2954 let vec = &[1, 2, 3, 4];
2955 assert_eq!(vec.slice_to(4), vec);
2956 assert_eq!(vec.slice_to(2), &[1, 2]);
2957 assert_eq!(vec.slice_to(0), &[]);
2962 // Test on-heap pop.
2963 let mut v = ~[1, 2, 3, 4, 5];
2965 assert_eq!(v.len(), 4u);
2966 assert_eq!(v[0], 1);
2967 assert_eq!(v[1], 2);
2968 assert_eq!(v[2], 3);
2969 assert_eq!(v[3], 4);
2976 let e = v.pop_opt();
2977 assert_eq!(v.len(), 0);
2978 assert_eq!(e, Some(5));
2979 let f = v.pop_opt();
2980 assert_eq!(f, None);
2981 let g = v.pop_opt();
2982 assert_eq!(g, None);
2985 fn test_swap_remove() {
2986 let mut v = ~[1, 2, 3, 4, 5];
2987 let mut e = v.swap_remove(0);
2988 assert_eq!(v.len(), 4);
2990 assert_eq!(v[0], 5);
2991 e = v.swap_remove(3);
2992 assert_eq!(v.len(), 3);
2994 assert_eq!(v[0], 5);
2995 assert_eq!(v[1], 2);
2996 assert_eq!(v[2], 3);
3000 fn test_swap_remove_noncopyable() {
3001 // Tests that we don't accidentally run destructors twice.
3002 let mut v = ~[::unstable::sync::Exclusive::new(()),
3003 ::unstable::sync::Exclusive::new(()),
3004 ::unstable::sync::Exclusive::new(())];
3005 let mut _e = v.swap_remove(0);
3006 assert_eq!(v.len(), 2);
3007 _e = v.swap_remove(1);
3008 assert_eq!(v.len(), 1);
3009 _e = v.swap_remove(0);
3010 assert_eq!(v.len(), 0);
3015 // Test on-stack push().
3018 assert_eq!(v.len(), 1u);
3019 assert_eq!(v[0], 1);
3021 // Test on-heap push().
3023 assert_eq!(v.len(), 2u);
3024 assert_eq!(v[0], 1);
3025 assert_eq!(v[1], 2);
3030 // Test on-stack grow().
3033 assert_eq!(v.len(), 2u);
3034 assert_eq!(v[0], 1);
3035 assert_eq!(v[1], 1);
3037 // Test on-heap grow().
3039 assert_eq!(v.len(), 5u);
3040 assert_eq!(v[0], 1);
3041 assert_eq!(v[1], 1);
3042 assert_eq!(v[2], 2);
3043 assert_eq!(v[3], 2);
3044 assert_eq!(v[4], 2);
3050 v.grow_fn(3u, square);
3051 assert_eq!(v.len(), 3u);
3052 assert_eq!(v[0], 0u);
3053 assert_eq!(v[1], 1u);
3054 assert_eq!(v[2], 4u);
3058 fn test_grow_set() {
3059 let mut v = ~[1, 2, 3];
3060 v.grow_set(4u, &4, 5);
3061 assert_eq!(v.len(), 5u);
3062 assert_eq!(v[0], 1);
3063 assert_eq!(v[1], 2);
3064 assert_eq!(v[2], 3);
3065 assert_eq!(v[3], 4);
3066 assert_eq!(v[4], 5);
3070 fn test_truncate() {
3071 let mut v = ~[@6,@5,@4];
3073 assert_eq!(v.len(), 1);
3074 assert_eq!(*(v[0]), 6);
3075 // If the unsafe block didn't drop things properly, we blow up here.
3080 let mut v = ~[@6,@5,@4];
3082 assert_eq!(v.len(), 0);
3083 // If the unsafe block didn't drop things properly, we blow up here.
3088 fn case(a: ~[uint], b: ~[uint]) {
3096 case(~[1,2,3], ~[1,2,3]);
3097 case(~[1,1,2,3], ~[1,2,3]);
3098 case(~[1,2,2,3], ~[1,2,3]);
3099 case(~[1,2,3,3], ~[1,2,3]);
3100 case(~[1,1,2,2,2,3,3], ~[1,2,3]);
3104 fn test_dedup_unique() {
3105 let mut v0 = ~[~1, ~1, ~2, ~3];
3107 let mut v1 = ~[~1, ~2, ~2, ~3];
3109 let mut v2 = ~[~1, ~2, ~3, ~3];
3112 * If the ~pointers were leaked or otherwise misused, valgrind and/or
3113 * rustrt should raise errors.
3118 fn test_dedup_shared() {
3119 let mut v0 = ~[@1, @1, @2, @3];
3121 let mut v1 = ~[@1, @2, @2, @3];
3123 let mut v2 = ~[@1, @2, @3, @3];
3126 * If the @pointers were leaked or otherwise misused, valgrind and/or
3127 * rustrt should raise errors.
3133 // Test on-stack map.
3134 let v = &[1u, 2u, 3u];
3135 let mut w = v.map(square_ref);
3136 assert_eq!(w.len(), 3u);
3137 assert_eq!(w[0], 1u);
3138 assert_eq!(w[1], 4u);
3139 assert_eq!(w[2], 9u);
3141 // Test on-heap map.
3142 let v = ~[1u, 2u, 3u, 4u, 5u];
3143 w = v.map(square_ref);
3144 assert_eq!(w.len(), 5u);
3145 assert_eq!(w[0], 1u);
3146 assert_eq!(w[1], 4u);
3147 assert_eq!(w[2], 9u);
3148 assert_eq!(w[3], 16u);
3149 assert_eq!(w[4], 25u);
3154 let mut v = ~[1, 2, 3, 4, 5];
3156 assert_eq!(v, ~[1, 3, 5]);
3160 fn test_zip_unzip() {
3161 let z1 = ~[(1, 4), (2, 5), (3, 6)];
3163 let (left, right) = unzip(z1.iter().map(|&x| x));
3165 assert_eq!((1, 4), (left[0], right[0]));
3166 assert_eq!((2, 5), (left[1], right[1]));
3167 assert_eq!((3, 6), (left[2], right[2]));
3171 fn test_element_swaps() {
3172 let mut v = [1, 2, 3];
3173 for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
3176 0 => assert_eq!(v, [1, 3, 2]),
3177 1 => assert_eq!(v, [3, 1, 2]),
3178 2 => assert_eq!(v, [3, 2, 1]),
3179 3 => assert_eq!(v, [2, 3, 1]),
3180 4 => assert_eq!(v, [2, 1, 3]),
3181 5 => assert_eq!(v, [1, 2, 3]),
3188 fn test_permutations() {
3191 let v: [int, ..0] = [];
3192 let mut it = v.permutations();
3193 assert_eq!(it.next(), None);
3197 let mut it = v.permutations();
3198 assert_eq!(it.next(), None);
3202 let mut it = v.permutations();
3203 assert_eq!(it.next(), Some(~[1,2,3]));
3204 assert_eq!(it.next(), Some(~[1,3,2]));
3205 assert_eq!(it.next(), Some(~[3,1,2]));
3206 assert_eq!(it.next(), Some(~[3,2,1]));
3207 assert_eq!(it.next(), Some(~[2,3,1]));
3208 assert_eq!(it.next(), Some(~[2,1,3]));
3209 assert_eq!(it.next(), None);
3212 // check that we have N! unique permutations
3213 let mut set = hashmap::HashSet::new();
3214 let v = ['A', 'B', 'C', 'D', 'E', 'F'];
3215 for perm in v.permutations() {
3218 assert_eq!(set.len(), 2 * 3 * 4 * 5 * 6);
3223 fn test_position_elem() {
3224 assert!([].position_elem(&1).is_none());
3226 let v1 = ~[1, 2, 3, 3, 2, 5];
3227 assert_eq!(v1.position_elem(&1), Some(0u));
3228 assert_eq!(v1.position_elem(&2), Some(1u));
3229 assert_eq!(v1.position_elem(&5), Some(5u));
3230 assert!(v1.position_elem(&4).is_none());
3234 fn test_bsearch_elem() {
3235 assert_eq!([1,2,3,4,5].bsearch_elem(&5), Some(4));
3236 assert_eq!([1,2,3,4,5].bsearch_elem(&4), Some(3));
3237 assert_eq!([1,2,3,4,5].bsearch_elem(&3), Some(2));
3238 assert_eq!([1,2,3,4,5].bsearch_elem(&2), Some(1));
3239 assert_eq!([1,2,3,4,5].bsearch_elem(&1), Some(0));
3241 assert_eq!([2,4,6,8,10].bsearch_elem(&1), None);
3242 assert_eq!([2,4,6,8,10].bsearch_elem(&5), None);
3243 assert_eq!([2,4,6,8,10].bsearch_elem(&4), Some(1));
3244 assert_eq!([2,4,6,8,10].bsearch_elem(&10), Some(4));
3246 assert_eq!([2,4,6,8].bsearch_elem(&1), None);
3247 assert_eq!([2,4,6,8].bsearch_elem(&5), None);
3248 assert_eq!([2,4,6,8].bsearch_elem(&4), Some(1));
3249 assert_eq!([2,4,6,8].bsearch_elem(&8), Some(3));
3251 assert_eq!([2,4,6].bsearch_elem(&1), None);
3252 assert_eq!([2,4,6].bsearch_elem(&5), None);
3253 assert_eq!([2,4,6].bsearch_elem(&4), Some(1));
3254 assert_eq!([2,4,6].bsearch_elem(&6), Some(2));
3256 assert_eq!([2,4].bsearch_elem(&1), None);
3257 assert_eq!([2,4].bsearch_elem(&5), None);
3258 assert_eq!([2,4].bsearch_elem(&2), Some(0));
3259 assert_eq!([2,4].bsearch_elem(&4), Some(1));
3261 assert_eq!([2].bsearch_elem(&1), None);
3262 assert_eq!([2].bsearch_elem(&5), None);
3263 assert_eq!([2].bsearch_elem(&2), Some(0));
3265 assert_eq!([].bsearch_elem(&1), None);
3266 assert_eq!([].bsearch_elem(&5), None);
3268 assert!([1,1,1,1,1].bsearch_elem(&1) != None);
3269 assert!([1,1,1,1,2].bsearch_elem(&1) != None);
3270 assert!([1,1,1,2,2].bsearch_elem(&1) != None);
3271 assert!([1,1,2,2,2].bsearch_elem(&1) != None);
3272 assert_eq!([1,2,2,2,2].bsearch_elem(&1), Some(0));
3274 assert_eq!([1,2,3,4,5].bsearch_elem(&6), None);
3275 assert_eq!([1,2,3,4,5].bsearch_elem(&0), None);
3280 let mut v: ~[int] = ~[10, 20];
3281 assert_eq!(v[0], 10);
3282 assert_eq!(v[1], 20);
3284 assert_eq!(v[0], 20);
3285 assert_eq!(v[1], 10);
3287 let mut v3: ~[int] = ~[];
3289 assert!(v3.is_empty());
3293 fn test_partition() {
3294 assert_eq!((~[]).partition(|x: &int| *x < 3), (~[], ~[]));
3295 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 4), (~[1, 2, 3], ~[]));
3296 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 2), (~[1], ~[2, 3]));
3297 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 0), (~[], ~[1, 2, 3]));
3301 fn test_partitioned() {
3302 assert_eq!(([]).partitioned(|x: &int| *x < 3), (~[], ~[]))
3303 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 4), (~[1, 2, 3], ~[]));
3304 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 2), (~[1], ~[2, 3]));
3305 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 0), (~[], ~[1, 2, 3]));
3310 let v: [~[int], ..0] = [];
3311 assert_eq!(v.concat_vec(), ~[]);
3312 assert_eq!([~[1], ~[2,3]].concat_vec(), ~[1, 2, 3]);
3314 assert_eq!([&[1], &[2,3]].concat_vec(), ~[1, 2, 3]);
3319 let v: [~[int], ..0] = [];
3320 assert_eq!(v.connect_vec(&0), ~[]);
3321 assert_eq!([~[1], ~[2, 3]].connect_vec(&0), ~[1, 0, 2, 3]);
3322 assert_eq!([~[1], ~[2], ~[3]].connect_vec(&0), ~[1, 0, 2, 0, 3]);
3324 assert_eq!(v.connect_vec(&0), ~[]);
3325 assert_eq!([&[1], &[2, 3]].connect_vec(&0), ~[1, 0, 2, 3]);
3326 assert_eq!([&[1], &[2], &[3]].connect_vec(&0), ~[1, 0, 2, 0, 3]);
3331 let mut x = ~[1, 2, 3];
3332 assert_eq!(x.shift(), 1);
3333 assert_eq!(&x, &~[2, 3]);
3334 assert_eq!(x.shift(), 2);
3335 assert_eq!(x.shift(), 3);
3336 assert_eq!(x.len(), 0);
3340 fn test_shift_opt() {
3341 let mut x = ~[1, 2, 3];
3342 assert_eq!(x.shift_opt(), Some(1));
3343 assert_eq!(&x, &~[2, 3]);
3344 assert_eq!(x.shift_opt(), Some(2));
3345 assert_eq!(x.shift_opt(), Some(3));
3346 assert_eq!(x.shift_opt(), None);
3347 assert_eq!(x.len(), 0);
3352 let mut x = ~[1, 2, 3];
3354 assert_eq!(x, ~[0, 1, 2, 3]);
3359 let mut a = ~[1, 2, 4];
3361 assert_eq!(a, ~[1, 2, 3, 4]);
3363 let mut a = ~[1, 2, 3];
3365 assert_eq!(a, ~[0, 1, 2, 3]);
3367 let mut a = ~[1, 2, 3];
3369 assert_eq!(a, ~[1, 2, 3, 4]);
3373 assert_eq!(a, ~[1]);
3378 fn test_insert_oob() {
3379 let mut a = ~[1, 2, 3];
3385 let mut a = ~[1, 2, 3, 4];
3387 assert_eq!(a, ~[1, 2, 4]);
3389 let mut a = ~[1, 2, 3];
3391 assert_eq!(a, ~[2, 3]);
3400 fn test_remove_oob() {
3401 let mut a = ~[1, 2, 3];
3406 fn test_capacity() {
3407 let mut v = ~[0u64];
3409 assert_eq!(v.capacity(), 10u);
3410 let mut v = ~[0u32];
3412 assert_eq!(v.capacity(), 10u);
3417 let v = ~[1, 2, 3, 4, 5];
3418 let v = v.slice(1u, 3u);
3419 assert_eq!(v.len(), 2u);
3420 assert_eq!(v[0], 2);
3421 assert_eq!(v[1], 3);
3427 fn test_from_fn_fail() {
3429 if v == 50 { fail!() }
3436 fn test_from_elem_fail() {
3445 fn clone(&self) -> S {
3446 let s = unsafe { cast::transmute_mut(self) };
3448 if s.f == 10 { fail!() }
3449 S { f: s.f, boxes: s.boxes.clone() }
3453 let s = S { f: 0, boxes: (~0, @0) };
3454 let _ = from_elem(100, s);
3459 fn test_build_fail() {
3460 build(None, |push| {
3471 fn test_grow_fn_fail() {
3473 v.grow_fn(100, |i| {
3483 fn test_map_fail() {
3484 let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
3497 fn test_flat_map_fail() {
3498 let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
3500 flat_map(v, |_elt| {
3511 fn test_permute_fail() {
3512 let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)];
3514 for _ in v.permutations() {
3524 fn test_copy_memory_oob() {
3526 let mut a = [1, 2, 3, 4];
3527 let b = [1, 2, 3, 4, 5];
3533 fn test_total_ord() {
3534 [1, 2, 3, 4].cmp(& &[1, 2, 3]) == Greater;
3535 [1, 2, 3].cmp(& &[1, 2, 3, 4]) == Less;
3536 [1, 2, 3, 4].cmp(& &[1, 2, 3, 4]) == Equal;
3537 [1, 2, 3, 4, 5, 5, 5, 5].cmp(& &[1, 2, 3, 4, 5, 6]) == Less;
3538 [2, 2].cmp(& &[1, 2, 3, 4]) == Greater;
3542 fn test_iterator() {
3544 let xs = [1, 2, 5, 10, 11];
3545 let mut it = xs.iter();
3546 assert_eq!(it.size_hint(), (5, Some(5)));
3547 assert_eq!(it.next().unwrap(), &1);
3548 assert_eq!(it.size_hint(), (4, Some(4)));
3549 assert_eq!(it.next().unwrap(), &2);
3550 assert_eq!(it.size_hint(), (3, Some(3)));
3551 assert_eq!(it.next().unwrap(), &5);
3552 assert_eq!(it.size_hint(), (2, Some(2)));
3553 assert_eq!(it.next().unwrap(), &10);
3554 assert_eq!(it.size_hint(), (1, Some(1)));
3555 assert_eq!(it.next().unwrap(), &11);
3556 assert_eq!(it.size_hint(), (0, Some(0)));
3557 assert!(it.next().is_none());
3561 fn test_random_access_iterator() {
3563 let xs = [1, 2, 5, 10, 11];
3564 let mut it = xs.iter();
3566 assert_eq!(it.indexable(), 5);
3567 assert_eq!(it.idx(0).unwrap(), &1);
3568 assert_eq!(it.idx(2).unwrap(), &5);
3569 assert_eq!(it.idx(4).unwrap(), &11);
3570 assert!(it.idx(5).is_none());
3572 assert_eq!(it.next().unwrap(), &1);
3573 assert_eq!(it.indexable(), 4);
3574 assert_eq!(it.idx(0).unwrap(), &2);
3575 assert_eq!(it.idx(3).unwrap(), &11);
3576 assert!(it.idx(4).is_none());
3578 assert_eq!(it.next().unwrap(), &2);
3579 assert_eq!(it.indexable(), 3);
3580 assert_eq!(it.idx(1).unwrap(), &10);
3581 assert!(it.idx(3).is_none());
3583 assert_eq!(it.next().unwrap(), &5);
3584 assert_eq!(it.indexable(), 2);
3585 assert_eq!(it.idx(1).unwrap(), &11);
3587 assert_eq!(it.next().unwrap(), &10);
3588 assert_eq!(it.indexable(), 1);
3589 assert_eq!(it.idx(0).unwrap(), &11);
3590 assert!(it.idx(1).is_none());
3592 assert_eq!(it.next().unwrap(), &11);
3593 assert_eq!(it.indexable(), 0);
3594 assert!(it.idx(0).is_none());
3596 assert!(it.next().is_none());
3600 fn test_iter_size_hints() {
3602 let mut xs = [1, 2, 5, 10, 11];
3603 assert_eq!(xs.iter().size_hint(), (5, Some(5)));
3604 assert_eq!(xs.rev_iter().size_hint(), (5, Some(5)));
3605 assert_eq!(xs.mut_iter().size_hint(), (5, Some(5)));
3606 assert_eq!(xs.mut_rev_iter().size_hint(), (5, Some(5)));
3610 fn test_iter_clone() {
3612 let mut it = xs.iter();
3614 let mut jt = it.clone();
3615 assert_eq!(it.next(), jt.next());
3616 assert_eq!(it.next(), jt.next());
3617 assert_eq!(it.next(), jt.next());
3621 fn test_mut_iterator() {
3623 let mut xs = [1, 2, 3, 4, 5];
3624 for x in xs.mut_iter() {
3627 assert_eq!(xs, [2, 3, 4, 5, 6])
3631 fn test_rev_iterator() {
3634 let xs = [1, 2, 5, 10, 11];
3635 let ys = [11, 10, 5, 2, 1];
3637 for &x in xs.rev_iter() {
3638 assert_eq!(x, ys[i]);
3645 fn test_mut_rev_iterator() {
3647 let mut xs = [1u, 2, 3, 4, 5];
3648 for (i,x) in xs.mut_rev_iter().enumerate() {
3651 assert_eq!(xs, [5, 5, 5, 5, 5])
3655 fn test_move_iterator() {
3657 let xs = ~[1u,2,3,4,5];
3658 assert_eq!(xs.move_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
3662 fn test_move_rev_iterator() {
3664 let xs = ~[1u,2,3,4,5];
3665 assert_eq!(xs.move_rev_iter().fold(0, |a: uint, b: uint| 10*a + b), 54321);
3669 fn test_splitator() {
3670 let xs = &[1i,2,3,4,5];
3672 assert_eq!(xs.split(|x| *x % 2 == 0).collect::<~[&[int]]>(),
3673 ~[&[1], &[3], &[5]]);
3674 assert_eq!(xs.split(|x| *x == 1).collect::<~[&[int]]>(),
3675 ~[&[], &[2,3,4,5]]);
3676 assert_eq!(xs.split(|x| *x == 5).collect::<~[&[int]]>(),
3677 ~[&[1,2,3,4], &[]]);
3678 assert_eq!(xs.split(|x| *x == 10).collect::<~[&[int]]>(),
3680 assert_eq!(xs.split(|_| true).collect::<~[&[int]]>(),
3681 ~[&[], &[], &[], &[], &[], &[]]);
3683 let xs: &[int] = &[];
3684 assert_eq!(xs.split(|x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3688 fn test_splitnator() {
3689 let xs = &[1i,2,3,4,5];
3691 assert_eq!(xs.splitn(0, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3693 assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3695 assert_eq!(xs.splitn(3, |_| true).collect::<~[&[int]]>(),
3696 ~[&[], &[], &[], &[4,5]]);
3698 let xs: &[int] = &[];
3699 assert_eq!(xs.splitn(1, |x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3703 fn test_rsplitator() {
3704 let xs = &[1i,2,3,4,5];
3706 assert_eq!(xs.rsplit(|x| *x % 2 == 0).collect::<~[&[int]]>(),
3707 ~[&[5], &[3], &[1]]);
3708 assert_eq!(xs.rsplit(|x| *x == 1).collect::<~[&[int]]>(),
3709 ~[&[2,3,4,5], &[]]);
3710 assert_eq!(xs.rsplit(|x| *x == 5).collect::<~[&[int]]>(),
3711 ~[&[], &[1,2,3,4]]);
3712 assert_eq!(xs.rsplit(|x| *x == 10).collect::<~[&[int]]>(),
3715 let xs: &[int] = &[];
3716 assert_eq!(xs.rsplit(|x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3720 fn test_rsplitnator() {
3721 let xs = &[1,2,3,4,5];
3723 assert_eq!(xs.rsplitn(0, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3725 assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3727 assert_eq!(xs.rsplitn(3, |_| true).collect::<~[&[int]]>(),
3728 ~[&[], &[], &[], &[1,2]]);
3730 let xs: &[int] = &[];
3731 assert_eq!(xs.rsplitn(1, |x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3735 fn test_windowsator() {
3736 let v = &[1i,2,3,4];
3738 assert_eq!(v.windows(2).collect::<~[&[int]]>(), ~[&[1,2], &[2,3], &[3,4]]);
3739 assert_eq!(v.windows(3).collect::<~[&[int]]>(), ~[&[1i,2,3], &[2,3,4]]);
3740 assert!(v.windows(6).next().is_none());
3745 fn test_windowsator_0() {
3746 let v = &[1i,2,3,4];
3747 let _it = v.windows(0);
3751 fn test_chunksator() {
3752 let v = &[1i,2,3,4,5];
3754 assert_eq!(v.chunks(2).collect::<~[&[int]]>(), ~[&[1i,2], &[3,4], &[5]]);
3755 assert_eq!(v.chunks(3).collect::<~[&[int]]>(), ~[&[1i,2,3], &[4,5]]);
3756 assert_eq!(v.chunks(6).collect::<~[&[int]]>(), ~[&[1i,2,3,4,5]]);
3758 assert_eq!(v.chunks(2).invert().collect::<~[&[int]]>(), ~[&[5i], &[3,4], &[1,2]]);
3759 let it = v.chunks(2);
3760 assert_eq!(it.indexable(), 3);
3761 assert_eq!(it.idx(0).unwrap(), &[1,2]);
3762 assert_eq!(it.idx(1).unwrap(), &[3,4]);
3763 assert_eq!(it.idx(2).unwrap(), &[5]);
3764 assert_eq!(it.idx(3), None);
3769 fn test_chunksator_0() {
3770 let v = &[1i,2,3,4];
3771 let _it = v.chunks(0);
3775 fn test_move_from() {
3776 let mut a = [1,2,3,4,5];
3778 assert_eq!(a.move_from(b, 0, 3), 3);
3779 assert_eq!(a, [6,7,8,4,5]);
3780 let mut a = [7,2,8,1];
3781 let b = ~[3,1,4,1,5,9];
3782 assert_eq!(a.move_from(b, 0, 6), 4);
3783 assert_eq!(a, [3,1,4,1]);
3784 let mut a = [1,2,3,4];
3785 let b = ~[5,6,7,8,9,0];
3786 assert_eq!(a.move_from(b, 2, 3), 1);
3787 assert_eq!(a, [7,2,3,4]);
3788 let mut a = [1,2,3,4,5];
3789 let b = ~[5,6,7,8,9,0];
3790 assert_eq!(a.mut_slice(2,4).move_from(b,1,6), 2);
3791 assert_eq!(a, [1,2,6,7,5]);
3795 fn test_copy_from() {
3796 let mut a = [1,2,3,4,5];
3798 assert_eq!(a.copy_from(b), 3);
3799 assert_eq!(a, [6,7,8,4,5]);
3800 let mut c = [7,2,8,1];
3801 let d = [3,1,4,1,5,9];
3802 assert_eq!(c.copy_from(d), 4);
3803 assert_eq!(c, [3,1,4,1]);
3807 fn test_reverse_part() {
3808 let mut values = [1,2,3,4,5];
3809 values.mut_slice(1, 4).reverse();
3810 assert_eq!(values, [1,4,3,2,5]);
3814 fn test_vec_default() {
3815 use default::Default;
3818 let v: $ty = Default::default();
3819 assert!(v.is_empty());
3829 fn test_bytes_set_memory() {
3830 use vec::bytes::MutableByteVector;
3831 let mut values = [1u8,2,3,4,5];
3832 values.mut_slice(0,5).set_memory(0xAB);
3833 assert_eq!(values, [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
3834 values.mut_slice(2,4).set_memory(0xFF);
3835 assert_eq!(values, [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
3840 fn test_overflow_does_not_cause_segfault() {
3849 fn test_overflow_does_not_cause_segfault_managed() {
3856 fn test_mut_split_at() {
3857 let mut values = [1u8,2,3,4,5];
3859 let (left, right) = values.mut_split_at(2);
3860 assert_eq!(left.slice(0, left.len()), [1, 2]);
3861 for p in left.mut_iter() {
3865 assert_eq!(right.slice(0, right.len()), [3, 4, 5]);
3866 for p in right.mut_iter() {
3871 assert_eq!(values, [2, 3, 5, 6, 7]);
3874 #[deriving(Clone, Eq)]
3878 fn test_iter_zero_sized() {
3879 let mut v = ~[Foo, Foo, Foo];
3880 assert_eq!(v.len(), 3);
3889 for f in v.slice(1, 3).iter() {
3895 for f in v.mut_iter() {
3901 for f in v.move_iter() {
3905 assert_eq!(cnt, 11);
3907 let xs = ~[Foo, Foo, Foo];
3908 assert_eq!(format!("{:?}", xs.slice(0, 2).to_owned()),
3909 ~"~[vec::tests::Foo, vec::tests::Foo]");
3911 let xs: [Foo, ..3] = [Foo, Foo, Foo];
3912 assert_eq!(format!("{:?}", xs.slice(0, 2).to_owned()),
3913 ~"~[vec::tests::Foo, vec::tests::Foo]");
3915 for f in xs.iter() {
3923 fn test_shrink_to_fit() {
3924 let mut xs = ~[0, 1, 2, 3];
3925 for i in range(4, 100) {
3928 assert_eq!(xs.capacity(), 128);
3930 assert_eq!(xs.capacity(), 100);
3931 assert_eq!(xs, range(0, 100).to_owned_vec());
3935 fn test_starts_with() {
3936 assert!(bytes!("foobar").starts_with(bytes!("foo")));
3937 assert!(!bytes!("foobar").starts_with(bytes!("oob")));
3938 assert!(!bytes!("foobar").starts_with(bytes!("bar")));
3939 assert!(!bytes!("foo").starts_with(bytes!("foobar")));
3940 assert!(!bytes!("bar").starts_with(bytes!("foobar")));
3941 assert!(bytes!("foobar").starts_with(bytes!("foobar")));
3942 let empty: &[u8] = [];
3943 assert!(empty.starts_with(empty));
3944 assert!(!empty.starts_with(bytes!("foo")));
3945 assert!(bytes!("foobar").starts_with(empty));
3949 fn test_ends_with() {
3950 assert!(bytes!("foobar").ends_with(bytes!("bar")));
3951 assert!(!bytes!("foobar").ends_with(bytes!("oba")));
3952 assert!(!bytes!("foobar").ends_with(bytes!("foo")));
3953 assert!(!bytes!("foo").ends_with(bytes!("foobar")));
3954 assert!(!bytes!("bar").ends_with(bytes!("foobar")));
3955 assert!(bytes!("foobar").ends_with(bytes!("foobar")));
3956 let empty: &[u8] = [];
3957 assert!(empty.ends_with(empty));
3958 assert!(!empty.ends_with(bytes!("foo")));
3959 assert!(bytes!("foobar").ends_with(empty));
3963 fn test_shift_ref() {
3964 let mut x: &[int] = [1, 2, 3, 4, 5];
3965 let h = x.shift_ref();
3967 assert_eq!(x.len(), 4);
3968 assert_eq!(x[0], 2);
3969 assert_eq!(x[3], 5);
3974 fn test_shift_ref_empty() {
3975 let mut x: &[int] = [];
3981 let mut x: &[int] = [1, 2, 3, 4, 5];
3982 let h = x.pop_ref();
3984 assert_eq!(x.len(), 4);
3985 assert_eq!(x[0], 1);
3986 assert_eq!(x[3], 4);
3991 fn test_pop_ref_empty() {
3992 let mut x: &[int] = [];
3997 fn test_mut_splitator() {
3998 let mut xs = [0,1,0,2,3,0,0,4,5,0];
3999 assert_eq!(xs.mut_split(|x| *x == 0).len(), 6);
4000 for slice in xs.mut_split(|x| *x == 0) {
4003 assert_eq!(xs, [0,1,0,3,2,0,0,5,4,0]);
4005 let mut xs = [0,1,0,2,3,0,0,4,5,0,6,7];
4006 for slice in xs.mut_split(|x| *x == 0).take(5) {
4009 assert_eq!(xs, [0,1,0,3,2,0,0,5,4,0,6,7]);
4013 fn test_mut_splitator_invert() {
4014 let mut xs = [1,2,0,3,4,0,0,5,6,0];
4015 for slice in xs.mut_split(|x| *x == 0).invert().take(4) {
4018 assert_eq!(xs, [1,2,0,4,3,0,0,6,5,0]);
4022 fn test_mut_chunks() {
4023 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
4024 for (i, chunk) in v.mut_chunks(3).enumerate() {
4025 for x in chunk.mut_iter() {
4029 let result = [0u8, 0, 0, 1, 1, 1, 2];
4030 assert_eq!(v, result);
4034 fn test_mut_chunks_invert() {
4035 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
4036 for (i, chunk) in v.mut_chunks(3).invert().enumerate() {
4037 for x in chunk.mut_iter() {
4041 let result = [2u8, 2, 2, 1, 1, 1, 0];
4042 assert_eq!(v, result);
4047 fn test_mut_chunks_0() {
4048 let mut v = [1, 2, 3, 4];
4049 let _it = v.mut_chunks(0);
4053 fn test_mut_shift_ref() {
4054 let mut x: &mut [int] = [1, 2, 3, 4, 5];
4055 let h = x.mut_shift_ref();
4057 assert_eq!(x.len(), 4);
4058 assert_eq!(x[0], 2);
4059 assert_eq!(x[3], 5);
4064 fn test_mut_shift_ref_empty() {
4065 let mut x: &mut [int] = [];
4070 fn test_mut_pop_ref() {
4071 let mut x: &mut [int] = [1, 2, 3, 4, 5];
4072 let h = x.mut_pop_ref();
4074 assert_eq!(x.len(), 4);
4075 assert_eq!(x[0], 1);
4076 assert_eq!(x[3], 4);
4081 fn test_mut_pop_ref_empty() {
4082 let mut x: &mut [int] = [];
4089 use extra::test::BenchHarness;
4092 use vec::VectorVector;
4097 fn iterator(bh: &mut BenchHarness) {
4098 // peculiar numbers to stop LLVM from optimising the summation
4100 let v = vec::from_fn(100, |i| i ^ (i << 1) ^ (i >> 1));
4107 // sum == 11806, to stop dead code elimination.
4108 if sum == 0 {fail!()}
4113 fn mut_iterator(bh: &mut BenchHarness) {
4114 let mut v = vec::from_elem(100, 0);
4118 for x in v.mut_iter() {
4126 fn add(bh: &mut BenchHarness) {
4127 let xs: &[int] = [5, ..10];
4128 let ys: &[int] = [5, ..10];
4135 fn concat(bh: &mut BenchHarness) {
4136 let xss: &[~[uint]] = vec::from_fn(100, |i| range(0, i).collect());
4138 let _ = xss.concat_vec();
4143 fn connect(bh: &mut BenchHarness) {
4144 let xss: &[~[uint]] = vec::from_fn(100, |i| range(0, i).collect());
4146 let _ = xss.connect_vec(&0);
4151 fn push(bh: &mut BenchHarness) {
4152 let mut vec: ~[uint] = ~[0u];
4159 fn starts_with_same_vector(bh: &mut BenchHarness) {
4160 let vec: ~[uint] = vec::from_fn(100, |i| i);
4162 vec.starts_with(vec);
4167 fn starts_with_single_element(bh: &mut BenchHarness) {
4168 let vec: ~[uint] = ~[0u];
4170 vec.starts_with(vec);
4175 fn starts_with_diff_one_element_at_end(bh: &mut BenchHarness) {
4176 let vec: ~[uint] = vec::from_fn(100, |i| i);
4177 let mut match_vec: ~[uint] = vec::from_fn(99, |i| i);
4180 vec.starts_with(match_vec);
4185 fn ends_with_same_vector(bh: &mut BenchHarness) {
4186 let vec: ~[uint] = vec::from_fn(100, |i| i);
4193 fn ends_with_single_element(bh: &mut BenchHarness) {
4194 let vec: ~[uint] = ~[0u];
4201 fn ends_with_diff_one_element_at_beginning(bh: &mut BenchHarness) {
4202 let vec: ~[uint] = vec::from_fn(100, |i| i);
4203 let mut match_vec: ~[uint] = vec::from_fn(100, |i| i);
4206 vec.starts_with(match_vec);
4211 fn contains_last_element(bh: &mut BenchHarness) {
4212 let vec: ~[uint] = vec::from_fn(100, |i| i);
4219 fn zero_1kb_from_elem(bh: &mut BenchHarness) {
4221 let _v: ~[u8] = vec::from_elem(1024, 0u8);
4226 fn zero_1kb_set_memory(bh: &mut BenchHarness) {
4228 let mut v: ~[u8] = vec::with_capacity(1024);
4230 let vp = v.as_mut_ptr();
4231 ptr::set_memory(vp, 0, 1024);
4238 fn zero_1kb_fixed_repeat(bh: &mut BenchHarness) {
4240 let _v: ~[u8] = ~[0u8, ..1024];
4245 fn zero_1kb_loop_set(bh: &mut BenchHarness) {
4246 // Slower because the { len, cap, [0 x T] }* repr allows a pointer to the length
4247 // field to be aliased (in theory) and prevents LLVM from optimizing loads away.
4249 let mut v: ~[u8] = vec::with_capacity(1024);
4253 for i in range(0, 1024) {
4260 fn zero_1kb_mut_iter(bh: &mut BenchHarness) {
4262 let mut v: ~[u8] = vec::with_capacity(1024);
4266 for x in v.mut_iter() {