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 let pred = &mut self.pred;
216 match self.v.iter().rposition(|x| (*pred)(x)) {
218 self.finished = true;
222 let ret = Some(self.v.slice(idx + 1, self.v.len()));
223 self.v = self.v.slice(0, idx);
231 fn size_hint(&self) -> (uint, Option<uint>) {
235 match (self.v.len(), self.n) {
236 (0,_) => (1, Some(1)),
237 (_,0) => (1, Some(1)),
238 (l,n) => (1, cmp::min(l,n).checked_add(&1u))
243 // Functional utilities
245 #[allow(missing_doc)]
246 pub trait VectorVector<T> {
247 // FIXME #5898: calling these .concat and .connect conflicts with
248 // StrVector::con{cat,nect}, since they have generic contents.
249 /// Flattens a vector of vectors of T into a single vector of T.
250 fn concat_vec(&self) -> ~[T];
252 /// Concatenate a vector of vectors, placing a given separator between each.
253 fn connect_vec(&self, sep: &T) -> ~[T];
256 impl<'a, T: Clone, V: Vector<T>> VectorVector<T> for &'a [V] {
257 fn concat_vec(&self) -> ~[T] {
258 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
259 let mut result = Vec::with_capacity(size);
260 for v in self.iter() {
261 result.push_all(v.as_slice())
263 result.move_iter().collect()
266 fn connect_vec(&self, sep: &T) -> ~[T] {
267 let size = self.iter().fold(0u, |acc, v| acc + v.as_slice().len());
268 let mut result = Vec::with_capacity(size + self.len());
269 let mut first = true;
270 for v in self.iter() {
271 if first { first = false } else { result.push(sep.clone()) }
272 result.push_all(v.as_slice())
274 result.move_iter().collect()
279 * Convert an iterator of pairs into a pair of vectors.
281 * Returns a tuple containing two vectors where the i-th element of the first
282 * vector contains the first element of the i-th tuple of the input iterator,
283 * and the i-th element of the second vector contains the second element
284 * of the i-th tuple of the input iterator.
286 pub fn unzip<T, U, V: Iterator<(T, U)>>(mut iter: V) -> (~[T], ~[U]) {
287 let (lo, _) = iter.size_hint();
288 let mut ts = Vec::with_capacity(lo);
289 let mut us = Vec::with_capacity(lo);
294 (ts.move_iter().collect(), us.move_iter().collect())
297 /// An Iterator that yields the element swaps needed to produce
298 /// a sequence of all possible permutations for an indexed sequence of
299 /// elements. Each permutation is only a single swap apart.
301 /// The Steinhaus–Johnson–Trotter algorithm is used.
303 /// Generates even and odd permutations alternately.
305 /// The last generated swap is always (0, 1), and it returns the
306 /// sequence to its initial order.
307 pub struct ElementSwaps {
308 sdir: ~[SizeDirection],
309 /// 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 })
328 enum Direction { Pos, Neg }
330 /// An Index and Direction together
331 struct SizeDirection {
336 impl Iterator<(uint, uint)> for ElementSwaps {
338 fn next(&mut self) -> Option<(uint, uint)> {
339 fn new_pos(i: uint, s: Direction) -> uint {
340 i + match s { Pos => 1, Neg => -1 }
343 // Find the index of the largest mobile element:
344 // The direction should point into the vector, and the
345 // swap should be with a smaller `size` element.
346 let max = self.sdir.iter().map(|&x| x).enumerate()
348 new_pos(i, sd.dir) < self.sdir.len() &&
349 self.sdir[new_pos(i, sd.dir)].size < sd.size)
350 .max_by(|&(_, sd)| sd.size);
353 let j = new_pos(i, sd.dir);
354 self.sdir.swap(i, j);
356 // Swap the direction of each larger SizeDirection
357 for x in self.sdir.mut_iter() {
358 if x.size > sd.size {
359 x.dir = match x.dir { Pos => Neg, Neg => Pos };
364 None => if self.emit_reset && self.sdir.len() > 1 {
365 self.emit_reset = false;
374 /// An Iterator that uses `ElementSwaps` to iterate through
375 /// all possible permutations of a vector.
377 /// The first iteration yields a clone of the vector as it is,
378 /// then each successive element is the vector with one
381 /// Generates even and odd permutations alternately.
382 pub struct Permutations<T> {
387 impl<T: Clone> Iterator<~[T]> for Permutations<T> {
389 fn next(&mut self) -> Option<~[T]> {
390 match self.swaps.next() {
393 let elt = self.v.clone();
401 /// An iterator over the (overlapping) slices of length `size` within
404 pub struct Windows<'a, T> {
409 impl<'a, T> Iterator<&'a [T]> for Windows<'a, T> {
411 fn next(&mut self) -> Option<&'a [T]> {
412 if self.size > self.v.len() {
415 let ret = Some(self.v.slice(0, self.size));
416 self.v = self.v.slice(1, self.v.len());
422 fn size_hint(&self) -> (uint, Option<uint>) {
423 if self.size > self.v.len() {
426 let x = self.v.len() - self.size;
427 (x.saturating_add(1), x.checked_add(&1u))
432 /// An iterator over a vector in (non-overlapping) chunks (`size`
433 /// elements at a time).
435 /// When the vector len is not evenly divided by the chunk size,
436 /// the last slice of the iteration will be the remainder.
438 pub struct Chunks<'a, T> {
443 impl<'a, T> Iterator<&'a [T]> for Chunks<'a, T> {
445 fn next(&mut self) -> Option<&'a [T]> {
446 if self.v.len() == 0 {
449 let chunksz = cmp::min(self.v.len(), self.size);
450 let (fst, snd) = (self.v.slice_to(chunksz),
451 self.v.slice_from(chunksz));
458 fn size_hint(&self) -> (uint, Option<uint>) {
459 if self.v.len() == 0 {
462 let (n, rem) = div_rem(self.v.len(), self.size);
463 let n = if rem > 0 { n+1 } else { n };
469 impl<'a, T> DoubleEndedIterator<&'a [T]> for Chunks<'a, T> {
471 fn next_back(&mut self) -> Option<&'a [T]> {
472 if self.v.len() == 0 {
475 let remainder = self.v.len() % self.size;
476 let chunksz = if remainder != 0 { remainder } else { self.size };
477 let (fst, snd) = (self.v.slice_to(self.v.len() - chunksz),
478 self.v.slice_from(self.v.len() - chunksz));
485 impl<'a, T> RandomAccessIterator<&'a [T]> for Chunks<'a, T> {
487 fn indexable(&self) -> uint {
488 self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
492 fn idx(&self, index: uint) -> Option<&'a [T]> {
493 if index < self.indexable() {
494 let lo = index * self.size;
495 let mut hi = lo + self.size;
496 if hi < lo || hi > self.v.len() { hi = self.v.len(); }
498 Some(self.v.slice(lo, hi))
508 #[allow(missing_doc)]
512 use container::Container;
514 use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering, Equiv};
515 use iter::{order, Iterator};
519 impl<'a,T:Eq> Eq for &'a [T] {
520 fn eq(&self, other: & &'a [T]) -> bool {
521 self.len() == other.len() &&
522 order::eq(self.iter(), other.iter())
524 fn ne(&self, other: & &'a [T]) -> bool {
525 self.len() != other.len() ||
526 order::ne(self.iter(), other.iter())
530 impl<T:Eq> Eq for ~[T] {
532 fn eq(&self, other: &~[T]) -> bool { self.as_slice() == *other }
534 fn ne(&self, other: &~[T]) -> bool { !self.eq(other) }
537 impl<'a,T:TotalEq> TotalEq for &'a [T] {}
539 impl<T:TotalEq> TotalEq for ~[T] {}
541 impl<'a,T:Eq, V: Vector<T>> Equiv<V> for &'a [T] {
543 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
546 impl<'a,T:Eq, V: Vector<T>> Equiv<V> for ~[T] {
548 fn equiv(&self, other: &V) -> bool { self.as_slice() == other.as_slice() }
551 impl<'a,T:TotalOrd> TotalOrd for &'a [T] {
552 fn cmp(&self, other: & &'a [T]) -> Ordering {
553 order::cmp(self.iter(), other.iter())
557 impl<T: TotalOrd> TotalOrd for ~[T] {
559 fn cmp(&self, other: &~[T]) -> Ordering { self.as_slice().cmp(&other.as_slice()) }
562 impl<'a, T: Ord> Ord for &'a [T] {
563 fn lt(&self, other: & &'a [T]) -> bool {
564 order::lt(self.iter(), other.iter())
567 fn le(&self, other: & &'a [T]) -> bool {
568 order::le(self.iter(), other.iter())
571 fn ge(&self, other: & &'a [T]) -> bool {
572 order::ge(self.iter(), other.iter())
575 fn gt(&self, other: & &'a [T]) -> bool {
576 order::gt(self.iter(), other.iter())
580 impl<T: Ord> Ord for ~[T] {
582 fn lt(&self, other: &~[T]) -> bool { self.as_slice() < other.as_slice() }
584 fn le(&self, other: &~[T]) -> bool { self.as_slice() <= other.as_slice() }
586 fn ge(&self, other: &~[T]) -> bool { self.as_slice() >= other.as_slice() }
588 fn gt(&self, other: &~[T]) -> bool { self.as_slice() > other.as_slice() }
591 impl<'a,T:Clone, V: Vector<T>> Add<V, ~[T]> for &'a [T] {
593 fn add(&self, rhs: &V) -> ~[T] {
594 let mut res = Vec::with_capacity(self.len() + rhs.as_slice().len());
596 res.push_all(rhs.as_slice());
597 res.move_iter().collect()
601 impl<T:Clone, V: Vector<T>> Add<V, ~[T]> for ~[T] {
603 fn add(&self, rhs: &V) -> ~[T] {
604 self.as_slice() + rhs.as_slice()
612 /// Any vector that can be represented as a slice.
613 pub trait Vector<T> {
614 /// Work with `self` as a slice.
615 fn as_slice<'a>(&'a self) -> &'a [T];
618 impl<'a,T> Vector<T> for &'a [T] {
620 fn as_slice<'a>(&'a self) -> &'a [T] { *self }
623 impl<T> Vector<T> for ~[T] {
625 fn as_slice<'a>(&'a self) -> &'a [T] { let v: &'a [T] = *self; v }
628 impl<'a, T> Container for &'a [T] {
629 /// Returns the length of a vector
631 fn len(&self) -> uint {
636 impl<T> Container for ~[T] {
637 /// Returns the length of a vector
639 fn len(&self) -> uint {
640 self.as_slice().len()
644 /// Extension methods for vector slices with cloneable elements
645 pub trait CloneableVector<T> {
646 /// Copy `self` into a new owned vector
647 fn to_owned(&self) -> ~[T];
649 /// Convert `self` into an owned vector, not making a copy if possible.
650 fn into_owned(self) -> ~[T];
653 /// Extension methods for vector slices
654 impl<'a, T: Clone> CloneableVector<T> for &'a [T] {
655 /// Returns a copy of `v`.
657 fn to_owned(&self) -> ~[T] {
658 let len = self.len();
659 let mut result = Vec::with_capacity(len);
660 // Unsafe code so this can be optimised to a memcpy (or something
661 // similarly fast) when T is Copy. LLVM is easily confused, so any
662 // extra operations during the loop can prevent this optimisation
665 let p = result.as_mut_ptr();
666 // Use try_finally here otherwise the write to length
667 // inside the loop stops LLVM from optimising this.
670 |i, ()| while *i < len {
672 &mut(*p.offset(*i as int)),
673 self.unsafe_ref(*i).clone());
676 |i| result.set_len(*i));
678 result.move_iter().collect()
682 fn into_owned(self) -> ~[T] { self.to_owned() }
685 /// Extension methods for owned vectors
686 impl<T: Clone> CloneableVector<T> for ~[T] {
688 fn to_owned(&self) -> ~[T] { self.clone() }
691 fn into_owned(self) -> ~[T] { self }
694 /// Extension methods for vectors
695 pub trait ImmutableVector<'a, T> {
697 * Returns a slice of self between `start` and `end`.
699 * Fails when `start` or `end` point outside the bounds of self,
700 * or when `start` > `end`.
702 fn slice(&self, start: uint, end: uint) -> &'a [T];
705 * Returns a slice of self from `start` to the end of the vec.
707 * Fails when `start` points outside the bounds of self.
709 fn slice_from(&self, start: uint) -> &'a [T];
712 * Returns a slice of self from the start of the vec to `end`.
714 * Fails when `end` points outside the bounds of self.
716 fn slice_to(&self, end: uint) -> &'a [T];
717 /// Returns an iterator over the vector
718 fn iter(self) -> Items<'a, T>;
719 /// Returns a reversed iterator over a vector
720 fn rev_iter(self) -> RevItems<'a, T>;
721 /// Returns an iterator over the subslices of the vector which are
722 /// separated by elements that match `pred`. The matched element
723 /// is not contained in the subslices.
724 fn split(self, pred: |&T|: 'a -> bool) -> Splits<'a, T>;
725 /// Returns an iterator over the subslices of the vector which are
726 /// separated by elements that match `pred`, limited to splitting
727 /// at most `n` times. The matched element is not contained in
729 fn splitn(self, n: uint, pred: |&T|: 'a -> bool) -> Splits<'a, T>;
730 /// Returns an iterator over the subslices of the vector which are
731 /// separated by elements that match `pred`. This starts at the
732 /// end of the vector and works backwards. The matched element is
733 /// not contained in the subslices.
734 fn rsplit(self, pred: |&T|: 'a -> bool) -> RevSplits<'a, T>;
735 /// Returns an iterator over the subslices of the vector which are
736 /// separated by elements that match `pred` limited to splitting
737 /// at most `n` times. This starts at the end of the vector and
738 /// works backwards. The matched element is not contained in the
740 fn rsplitn(self, n: uint, pred: |&T|: 'a -> bool) -> RevSplits<'a, T>;
743 * Returns an iterator over all contiguous windows of length
744 * `size`. The windows overlap. If the vector is shorter than
745 * `size`, the iterator returns no values.
749 * Fails if `size` is 0.
753 * Print the adjacent pairs of a vector (i.e. `[1,2]`, `[2,3]`,
757 * let v = &[1,2,3,4];
758 * for win in v.windows(2) {
759 * println!("{:?}", win);
764 fn windows(self, size: uint) -> Windows<'a, T>;
767 * Returns an iterator over `size` elements of the vector at a
768 * time. The chunks do not overlap. If `size` does not divide the
769 * length of the vector, then the last chunk will not have length
774 * Fails if `size` is 0.
778 * Print the vector two elements at a time (i.e. `[1,2]`,
782 * let v = &[1,2,3,4,5];
783 * for win in v.chunks(2) {
784 * println!("{:?}", win);
789 fn chunks(self, size: uint) -> Chunks<'a, T>;
791 /// Returns the element of a vector at the given index, or `None` if the
792 /// index is out of bounds
793 fn get(&self, index: uint) -> Option<&'a T>;
794 /// Returns the first element of a vector, or `None` if it is empty
795 fn head(&self) -> Option<&'a T>;
796 /// Returns all but the first element of a vector
797 fn tail(&self) -> &'a [T];
798 /// Returns all but the first `n' elements of a vector
799 fn tailn(&self, n: uint) -> &'a [T];
800 /// Returns all but the last element of a vector
801 fn init(&self) -> &'a [T];
802 /// Returns all but the last `n' elements of a vector
803 fn initn(&self, n: uint) -> &'a [T];
804 /// Returns the last element of a vector, or `None` if it is empty.
805 fn last(&self) -> Option<&'a T>;
807 /// Returns a pointer to the element at the given index, without doing
809 unsafe fn unsafe_ref(self, index: uint) -> &'a T;
812 * Returns an unsafe pointer to the vector's buffer
814 * The caller must ensure that the vector outlives the pointer this
815 * function returns, or else it will end up pointing to garbage.
817 * Modifying the vector may cause its buffer to be reallocated, which
818 * would also make any pointers to it invalid.
820 fn as_ptr(&self) -> *T;
823 * Binary search a sorted vector with a comparator function.
825 * The comparator function should implement an order consistent
826 * with the sort order of the underlying vector, returning an
827 * order code that indicates whether its argument is `Less`,
828 * `Equal` or `Greater` the desired target.
830 * Returns the index where the comparator returned `Equal`, or `None` if
833 fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint>;
836 * Returns a mutable reference to the first element in this slice
837 * and adjusts the slice in place so that it no longer contains
838 * that element. O(1).
843 * if self.len() == 0 { return None }
844 * let head = &self[0];
845 * *self = self.slice_from(1);
849 * Returns `None` if vector is empty
851 fn shift_ref(&mut self) -> Option<&'a T>;
854 * Returns a mutable reference to the last element in this slice
855 * and adjusts the slice in place so that it no longer contains
856 * that element. O(1).
861 * if self.len() == 0 { return None; }
862 * let tail = &self[self.len() - 1];
863 * *self = self.slice_to(self.len() - 1);
867 * Returns `None` if slice is empty.
869 fn pop_ref(&mut self) -> Option<&'a T>;
872 impl<'a,T> ImmutableVector<'a, T> for &'a [T] {
874 fn slice(&self, start: uint, end: uint) -> &'a [T] {
875 assert!(start <= end);
876 assert!(end <= self.len());
879 data: self.as_ptr().offset(start as int),
886 fn slice_from(&self, start: uint) -> &'a [T] {
887 self.slice(start, self.len())
891 fn slice_to(&self, end: uint) -> &'a [T] {
896 fn iter(self) -> Items<'a, T> {
898 let p = self.as_ptr();
899 if mem::size_of::<T>() == 0 {
901 end: (p as uint + self.len()) as *T,
902 marker: marker::ContravariantLifetime::<'a>}
905 end: p.offset(self.len() as int),
906 marker: marker::ContravariantLifetime::<'a>}
912 fn rev_iter(self) -> RevItems<'a, T> {
917 fn split(self, pred: |&T|: 'a -> bool) -> Splits<'a, T> {
918 self.splitn(uint::MAX, pred)
922 fn splitn(self, n: uint, pred: |&T|: 'a -> bool) -> Splits<'a, T> {
932 fn rsplit(self, pred: |&T|: 'a -> bool) -> RevSplits<'a, T> {
933 self.rsplitn(uint::MAX, pred)
937 fn rsplitn(self, n: uint, pred: |&T|: 'a -> bool) -> RevSplits<'a, T> {
947 fn windows(self, size: uint) -> Windows<'a, T> {
949 Windows { v: self, size: size }
953 fn chunks(self, size: uint) -> Chunks<'a, T> {
955 Chunks { v: self, size: size }
959 fn get(&self, index: uint) -> Option<&'a T> {
960 if index < self.len() { Some(&self[index]) } else { None }
964 fn head(&self) -> Option<&'a T> {
965 if self.len() == 0 { None } else { Some(&self[0]) }
969 fn tail(&self) -> &'a [T] { self.slice(1, self.len()) }
972 fn tailn(&self, n: uint) -> &'a [T] { self.slice(n, self.len()) }
975 fn init(&self) -> &'a [T] {
976 self.slice(0, self.len() - 1)
980 fn initn(&self, n: uint) -> &'a [T] {
981 self.slice(0, self.len() - n)
985 fn last(&self) -> Option<&'a T> {
986 if self.len() == 0 { None } else { Some(&self[self.len() - 1]) }
990 unsafe fn unsafe_ref(self, index: uint) -> &'a T {
991 transmute(self.repr().data.offset(index as int))
995 fn as_ptr(&self) -> *T {
1000 fn bsearch(&self, f: |&T| -> Ordering) -> Option<uint> {
1001 let mut base : uint = 0;
1002 let mut lim : uint = self.len();
1005 let ix = base + (lim >> 1);
1006 match f(&self[ix]) {
1007 Equal => return Some(ix),
1019 fn shift_ref(&mut self) -> Option<&'a T> {
1020 if self.len() == 0 { return None; }
1022 let s: &mut Slice<T> = transmute(self);
1023 Some(&*raw::shift_ptr(s))
1027 fn pop_ref(&mut self) -> Option<&'a T> {
1028 if self.len() == 0 { return None; }
1030 let s: &mut Slice<T> = transmute(self);
1031 Some(&*raw::pop_ptr(s))
1036 /// Extension methods for vectors contain `Eq` elements.
1037 pub trait ImmutableEqVector<T:Eq> {
1038 /// Find the first index containing a matching value
1039 fn position_elem(&self, t: &T) -> Option<uint>;
1041 /// Find the last index containing a matching value
1042 fn rposition_elem(&self, t: &T) -> Option<uint>;
1044 /// Return true if a vector contains an element with the given value
1045 fn contains(&self, x: &T) -> bool;
1047 /// Returns true if `needle` is a prefix of the vector.
1048 fn starts_with(&self, needle: &[T]) -> bool;
1050 /// Returns true if `needle` is a suffix of the vector.
1051 fn ends_with(&self, needle: &[T]) -> bool;
1054 impl<'a,T:Eq> ImmutableEqVector<T> for &'a [T] {
1056 fn position_elem(&self, x: &T) -> Option<uint> {
1057 self.iter().position(|y| *x == *y)
1061 fn rposition_elem(&self, t: &T) -> Option<uint> {
1062 self.iter().rposition(|x| *x == *t)
1066 fn contains(&self, x: &T) -> bool {
1067 self.iter().any(|elt| *x == *elt)
1071 fn starts_with(&self, needle: &[T]) -> bool {
1072 let n = needle.len();
1073 self.len() >= n && needle == self.slice_to(n)
1077 fn ends_with(&self, needle: &[T]) -> bool {
1078 let (m, n) = (self.len(), needle.len());
1079 m >= n && needle == self.slice_from(m - n)
1083 /// Extension methods for vectors containing `TotalOrd` elements.
1084 pub trait ImmutableTotalOrdVector<T: TotalOrd> {
1086 * Binary search a sorted vector for a given element.
1088 * Returns the index of the element or None if not found.
1090 fn bsearch_elem(&self, x: &T) -> Option<uint>;
1093 impl<'a, T: TotalOrd> ImmutableTotalOrdVector<T> for &'a [T] {
1094 fn bsearch_elem(&self, x: &T) -> Option<uint> {
1095 self.bsearch(|p| p.cmp(x))
1099 /// Extension methods for vectors containing `Clone` elements.
1100 pub trait ImmutableCloneableVector<T> {
1101 /// Partitions the vector into two vectors `(A,B)`, where all
1102 /// elements of `A` satisfy `f` and all elements of `B` do not.
1103 fn partitioned(&self, f: |&T| -> bool) -> (~[T], ~[T]);
1105 /// Create an iterator that yields every possible permutation of the
1106 /// vector in succession.
1107 fn permutations(self) -> Permutations<T>;
1110 impl<'a,T:Clone> ImmutableCloneableVector<T> for &'a [T] {
1112 fn partitioned(&self, f: |&T| -> bool) -> (~[T], ~[T]) {
1113 let mut lefts = Vec::new();
1114 let mut rights = Vec::new();
1116 for elt in self.iter() {
1118 lefts.push((*elt).clone());
1120 rights.push((*elt).clone());
1124 (lefts.move_iter().collect(), rights.move_iter().collect())
1127 fn permutations(self) -> Permutations<T> {
1129 swaps: ElementSwaps::new(self.len()),
1136 /// Extension methods for owned vectors.
1137 pub trait OwnedVector<T> {
1138 /// Creates a consuming iterator, that is, one that moves each
1139 /// value out of the vector (from start to end). The vector cannot
1140 /// be used after calling this.
1145 /// let v = ~[~"a", ~"b"];
1146 /// for s in v.move_iter() {
1147 /// // s has type ~str, not &~str
1148 /// println!("{}", s);
1151 fn move_iter(self) -> MoveItems<T>;
1152 /// Creates a consuming iterator that moves out of the vector in
1154 fn move_rev_iter(self) -> RevMoveItems<T>;
1157 * Partitions the vector into two vectors `(A,B)`, where all
1158 * elements of `A` satisfy `f` and all elements of `B` do not.
1160 fn partition(self, f: |&T| -> bool) -> (~[T], ~[T]);
1163 impl<T> OwnedVector<T> for ~[T] {
1165 fn move_iter(self) -> MoveItems<T> {
1167 let iter = transmute(self.iter());
1168 let ptr = transmute(self);
1169 MoveItems { allocation: ptr, iter: iter }
1174 fn move_rev_iter(self) -> RevMoveItems<T> {
1175 self.move_iter().rev()
1179 fn partition(self, f: |&T| -> bool) -> (~[T], ~[T]) {
1180 let mut lefts = Vec::new();
1181 let mut rights = Vec::new();
1183 for elt in self.move_iter() {
1191 (lefts.move_iter().collect(), rights.move_iter().collect())
1195 fn insertion_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
1196 let len = v.len() as int;
1197 let buf_v = v.as_mut_ptr();
1200 for i in range(1, len) {
1201 // j satisfies: 0 <= j <= i;
1204 // `i` is in bounds.
1205 let read_ptr = buf_v.offset(i) as *T;
1207 // find where to insert, we need to do strict <,
1208 // rather than <=, to maintain stability.
1210 // 0 <= j - 1 < len, so .offset(j - 1) is in bounds.
1212 compare(&*read_ptr, &*buf_v.offset(j - 1)) == Less {
1216 // shift everything to the right, to make space to
1217 // insert this value.
1219 // j + 1 could be `len` (for the last `i`), but in
1220 // that case, `i == j` so we don't copy. The
1221 // `.offset(j)` is always in bounds.
1224 let tmp = ptr::read(read_ptr);
1225 ptr::copy_memory(buf_v.offset(j + 1),
1228 ptr::copy_nonoverlapping_memory(buf_v.offset(j),
1237 fn merge_sort<T>(v: &mut [T], compare: |&T, &T| -> Ordering) {
1238 // warning: this wildly uses unsafe.
1239 static BASE_INSERTION: uint = 32;
1240 static LARGE_INSERTION: uint = 16;
1242 // FIXME #12092: smaller insertion runs seems to make sorting
1243 // vectors of large elements a little faster on some platforms,
1244 // but hasn't been tested/tuned extensively
1245 let insertion = if size_of::<T>() <= 16 {
1253 // short vectors get sorted in-place via insertion sort to avoid allocations
1254 if len <= insertion {
1255 insertion_sort(v, compare);
1259 // allocate some memory to use as scratch memory, we keep the
1260 // length 0 so we can keep shallow copies of the contents of `v`
1261 // without risking the dtors running on an object twice if
1263 let mut working_space = Vec::with_capacity(2 * len);
1264 // these both are buffers of length `len`.
1265 let mut buf_dat = working_space.as_mut_ptr();
1266 let mut buf_tmp = unsafe {buf_dat.offset(len as int)};
1269 let buf_v = v.as_ptr();
1271 // step 1. sort short runs with insertion sort. This takes the
1272 // values from `v` and sorts them into `buf_dat`, leaving that
1273 // with sorted runs of length INSERTION.
1275 // We could hardcode the sorting comparisons here, and we could
1276 // manipulate/step the pointers themselves, rather than repeatedly
1278 for start in range_step(0, len, insertion) {
1279 // start <= i < len;
1280 for i in range(start, cmp::min(start + insertion, len)) {
1281 // j satisfies: start <= j <= i;
1282 let mut j = i as int;
1284 // `i` is in bounds.
1285 let read_ptr = buf_v.offset(i as int);
1287 // find where to insert, we need to do strict <,
1288 // rather than <=, to maintain stability.
1290 // start <= j - 1 < len, so .offset(j - 1) is in
1292 while j > start as int &&
1293 compare(&*read_ptr, &*buf_dat.offset(j - 1)) == Less {
1297 // shift everything to the right, to make space to
1298 // insert this value.
1300 // j + 1 could be `len` (for the last `i`), but in
1301 // that case, `i == j` so we don't copy. The
1302 // `.offset(j)` is always in bounds.
1303 ptr::copy_memory(buf_dat.offset(j + 1),
1304 &*buf_dat.offset(j),
1306 ptr::copy_nonoverlapping_memory(buf_dat.offset(j), read_ptr, 1);
1311 // step 2. merge the sorted runs.
1312 let mut width = insertion;
1314 // merge the sorted runs of length `width` in `buf_dat` two at
1315 // a time, placing the result in `buf_tmp`.
1317 // 0 <= start <= len.
1318 for start in range_step(0, len, 2 * width) {
1319 // manipulate pointers directly for speed (rather than
1320 // using a `for` loop with `range` and `.offset` inside
1323 // the end of the first run & start of the
1324 // second. Offset of `len` is defined, since this is
1325 // precisely one byte past the end of the object.
1326 let right_start = buf_dat.offset(cmp::min(start + width, len) as int);
1327 // end of the second. Similar reasoning to the above re safety.
1328 let right_end_idx = cmp::min(start + 2 * width, len);
1329 let right_end = buf_dat.offset(right_end_idx as int);
1331 // the pointers to the elements under consideration
1332 // from the two runs.
1334 // both of these are in bounds.
1335 let mut left = buf_dat.offset(start as int);
1336 let mut right = right_start;
1338 // where we're putting the results, it is a run of
1339 // length `2*width`, so we step it once for each step
1340 // of either `left` or `right`. `buf_tmp` has length
1341 // `len`, so these are in bounds.
1342 let mut out = buf_tmp.offset(start as int);
1343 let out_end = buf_tmp.offset(right_end_idx as int);
1345 while out < out_end {
1346 // Either the left or the right run are exhausted,
1347 // so just copy the remainder from the other run
1348 // and move on; this gives a huge speed-up (order
1349 // of 25%) for mostly sorted vectors (the best
1351 if left == right_start {
1352 // the number remaining in this run.
1353 let elems = (right_end as uint - right as uint) / mem::size_of::<T>();
1354 ptr::copy_nonoverlapping_memory(out, &*right, elems);
1356 } else if right == right_end {
1357 let elems = (right_start as uint - left as uint) / mem::size_of::<T>();
1358 ptr::copy_nonoverlapping_memory(out, &*left, elems);
1362 // check which side is smaller, and that's the
1363 // next element for the new run.
1365 // `left < right_start` and `right < right_end`,
1366 // so these are valid.
1367 let to_copy = if compare(&*left, &*right) == Greater {
1372 ptr::copy_nonoverlapping_memory(out, &*to_copy, 1);
1378 mem::swap(&mut buf_dat, &mut buf_tmp);
1383 // write the result to `v` in one go, so that there are never two copies
1384 // of the same object in `v`.
1386 ptr::copy_nonoverlapping_memory(v.as_mut_ptr(), &*buf_dat, len);
1389 // increment the pointer, returning the old pointer.
1391 unsafe fn step<T>(ptr: &mut *mut T) -> *mut T {
1393 *ptr = ptr.offset(1);
1398 /// Extension methods for vectors such that their elements are
1400 pub trait MutableVector<'a, T> {
1401 /// Work with `self` as a mut slice.
1402 /// Primarily intended for getting a &mut [T] from a [T, ..N].
1403 fn as_mut_slice(self) -> &'a mut [T];
1405 /// Return a slice that points into another slice.
1406 fn mut_slice(self, start: uint, end: uint) -> &'a mut [T];
1409 * Returns a slice of self from `start` to the end of the vec.
1411 * Fails when `start` points outside the bounds of self.
1413 fn mut_slice_from(self, start: uint) -> &'a mut [T];
1416 * Returns a slice of self from the start of the vec to `end`.
1418 * Fails when `end` points outside the bounds of self.
1420 fn mut_slice_to(self, end: uint) -> &'a mut [T];
1422 /// Returns an iterator that allows modifying each value
1423 fn mut_iter(self) -> MutItems<'a, T>;
1425 /// Returns a mutable pointer to the last item in the vector.
1426 fn mut_last(self) -> Option<&'a mut T>;
1428 /// Returns a reversed iterator that allows modifying each value
1429 fn mut_rev_iter(self) -> RevMutItems<'a, T>;
1431 /// Returns an iterator over the mutable subslices of the vector
1432 /// which are separated by elements that match `pred`. The
1433 /// matched element is not contained in the subslices.
1434 fn mut_split(self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T>;
1437 * Returns an iterator over `size` elements of the vector at a time.
1438 * The chunks are mutable and do not overlap. If `size` does not divide the
1439 * length of the vector, then the last chunk will not have length
1444 * Fails if `size` is 0.
1446 fn mut_chunks(self, chunk_size: uint) -> MutChunks<'a, T>;
1449 * Returns a mutable reference to the first element in this slice
1450 * and adjusts the slice in place so that it no longer contains
1451 * that element. O(1).
1456 * if self.len() == 0 { return None; }
1457 * let head = &mut self[0];
1458 * *self = self.mut_slice_from(1);
1462 * Returns `None` if slice is empty
1464 fn mut_shift_ref(&mut self) -> Option<&'a mut T>;
1467 * Returns a mutable reference to the last element in this slice
1468 * and adjusts the slice in place so that it no longer contains
1469 * that element. O(1).
1474 * if self.len() == 0 { return None; }
1475 * let tail = &mut self[self.len() - 1];
1476 * *self = self.mut_slice_to(self.len() - 1);
1480 * Returns `None` if slice is empty.
1482 fn mut_pop_ref(&mut self) -> Option<&'a mut T>;
1484 /// Swaps two elements in a vector.
1486 /// Fails if `a` or `b` are out of bounds.
1490 /// * a - The index of the first element
1491 /// * b - The index of the second element
1496 /// let mut v = ["a", "b", "c", "d"];
1498 /// assert!(v == ["a", "d", "c", "b"]);
1500 fn swap(self, a: uint, b: uint);
1503 /// Divides one `&mut` into two at an index.
1505 /// The first will contain all indices from `[0, mid)` (excluding
1506 /// the index `mid` itself) and the second will contain all
1507 /// indices from `[mid, len)` (excluding the index `len` itself).
1509 /// Fails if `mid > len`.
1514 /// let mut v = [1, 2, 3, 4, 5, 6];
1516 /// // scoped to restrict the lifetime of the borrows
1518 /// let (left, right) = v.mut_split_at(0);
1519 /// assert!(left == &mut []);
1520 /// assert!(right == &mut [1, 2, 3, 4, 5, 6]);
1524 /// let (left, right) = v.mut_split_at(2);
1525 /// assert!(left == &mut [1, 2]);
1526 /// assert!(right == &mut [3, 4, 5, 6]);
1530 /// let (left, right) = v.mut_split_at(6);
1531 /// assert!(left == &mut [1, 2, 3, 4, 5, 6]);
1532 /// assert!(right == &mut []);
1535 fn mut_split_at(self, mid: uint) -> (&'a mut [T], &'a mut [T]);
1537 /// Reverse the order of elements in a vector, in place.
1542 /// let mut v = [1, 2, 3];
1544 /// assert!(v == [3, 2, 1]);
1548 /// Sort the vector, in place, using `compare` to compare
1551 /// This sort is `O(n log n)` worst-case and stable, but allocates
1552 /// approximately `2 * n`, where `n` is the length of `self`.
1557 /// let mut v = [5i, 4, 1, 3, 2];
1558 /// v.sort_by(|a, b| a.cmp(b));
1559 /// assert!(v == [1, 2, 3, 4, 5]);
1561 /// // reverse sorting
1562 /// v.sort_by(|a, b| b.cmp(a));
1563 /// assert!(v == [5, 4, 3, 2, 1]);
1565 fn sort_by(self, compare: |&T, &T| -> Ordering);
1568 * Consumes `src` and moves as many elements as it can into `self`
1569 * from the range [start,end).
1571 * Returns the number of elements copied (the shorter of self.len()
1576 * * src - A mutable vector of `T`
1577 * * start - The index into `src` to start copying from
1578 * * end - The index into `str` to stop copying from
1580 fn move_from(self, src: ~[T], start: uint, end: uint) -> uint;
1582 /// Returns an unsafe mutable pointer to the element in index
1583 unsafe fn unsafe_mut_ref(self, index: uint) -> &'a mut T;
1585 /// Return an unsafe mutable pointer to the vector's buffer.
1587 /// The caller must ensure that the vector outlives the pointer this
1588 /// function returns, or else it will end up pointing to garbage.
1590 /// Modifying the vector may cause its buffer to be reallocated, which
1591 /// would also make any pointers to it invalid.
1593 fn as_mut_ptr(self) -> *mut T;
1595 /// Unsafely sets the element in index to the value.
1597 /// This performs no bounds checks, and it is undefined behaviour
1598 /// if `index` is larger than the length of `self`. However, it
1599 /// does run the destructor at `index`. It is equivalent to
1600 /// `self[index] = val`.
1605 /// let mut v = ~[~"foo", ~"bar", ~"baz"];
1608 /// // `~"baz"` is deallocated.
1609 /// v.unsafe_set(2, ~"qux");
1611 /// // Out of bounds: could cause a crash, or overwriting
1612 /// // other data, or something else.
1613 /// // v.unsafe_set(10, ~"oops");
1616 unsafe fn unsafe_set(self, index: uint, val: T);
1618 /// Unchecked vector index assignment. Does not drop the
1619 /// old value and hence is only suitable when the vector
1620 /// is newly allocated.
1625 /// let mut v = [~"foo", ~"bar"];
1627 /// // memory leak! `~"bar"` is not deallocated.
1628 /// unsafe { v.init_elem(1, ~"baz"); }
1630 unsafe fn init_elem(self, i: uint, val: T);
1632 /// Copies raw bytes from `src` to `self`.
1634 /// This does not run destructors on the overwritten elements, and
1635 /// ignores move semantics. `self` and `src` must not
1636 /// overlap. Fails if `self` is shorter than `src`.
1637 unsafe fn copy_memory(self, src: &[T]);
1640 impl<'a,T> MutableVector<'a, T> for &'a mut [T] {
1642 fn as_mut_slice(self) -> &'a mut [T] { self }
1644 fn mut_slice(self, start: uint, end: uint) -> &'a mut [T] {
1645 assert!(start <= end);
1646 assert!(end <= self.len());
1649 data: self.as_mut_ptr().offset(start as int) as *T,
1656 fn mut_slice_from(self, start: uint) -> &'a mut [T] {
1657 let len = self.len();
1658 self.mut_slice(start, len)
1662 fn mut_slice_to(self, end: uint) -> &'a mut [T] {
1663 self.mut_slice(0, end)
1667 fn mut_split_at(self, mid: uint) -> (&'a mut [T], &'a mut [T]) {
1669 let len = self.len();
1670 let self2: &'a mut [T] = cast::transmute_copy(&self);
1671 (self.mut_slice(0, mid), self2.mut_slice(mid, len))
1676 fn mut_iter(self) -> MutItems<'a, T> {
1678 let p = self.as_mut_ptr();
1679 if mem::size_of::<T>() == 0 {
1681 end: (p as uint + self.len()) as *mut T,
1682 marker: marker::ContravariantLifetime::<'a>,
1683 marker2: marker::NoCopy}
1686 end: p.offset(self.len() as int),
1687 marker: marker::ContravariantLifetime::<'a>,
1688 marker2: marker::NoCopy}
1694 fn mut_last(self) -> Option<&'a mut T> {
1695 let len = self.len();
1696 if len == 0 { return None; }
1697 Some(&mut self[len - 1])
1701 fn mut_rev_iter(self) -> RevMutItems<'a, T> {
1702 self.mut_iter().rev()
1706 fn mut_split(self, pred: |&T|: 'a -> bool) -> MutSplits<'a, T> {
1707 MutSplits { v: self, pred: pred, finished: false }
1711 fn mut_chunks(self, chunk_size: uint) -> MutChunks<'a, T> {
1712 assert!(chunk_size > 0);
1713 MutChunks { v: self, chunk_size: chunk_size }
1716 fn mut_shift_ref(&mut self) -> Option<&'a mut T> {
1717 if self.len() == 0 { return None; }
1719 let s: &mut Slice<T> = transmute(self);
1720 Some(cast::transmute_mut(&*raw::shift_ptr(s)))
1724 fn mut_pop_ref(&mut self) -> Option<&'a mut T> {
1725 if self.len() == 0 { return None; }
1727 let s: &mut Slice<T> = transmute(self);
1728 Some(cast::transmute_mut(&*raw::pop_ptr(s)))
1732 fn swap(self, a: uint, b: uint) {
1734 // Can't take two mutable loans from one vector, so instead just cast
1735 // them to their raw pointers to do the swap
1736 let pa: *mut T = &mut self[a];
1737 let pb: *mut T = &mut self[b];
1743 let mut i: uint = 0;
1744 let ln = self.len();
1746 self.swap(i, ln - i - 1);
1752 fn sort_by(self, compare: |&T, &T| -> Ordering) {
1753 merge_sort(self, compare)
1757 fn move_from(self, mut src: ~[T], start: uint, end: uint) -> uint {
1758 for (a, b) in self.mut_iter().zip(src.mut_slice(start, end).mut_iter()) {
1761 cmp::min(self.len(), end-start)
1765 unsafe fn unsafe_mut_ref(self, index: uint) -> &'a mut T {
1766 transmute((self.repr().data as *mut T).offset(index as int))
1770 fn as_mut_ptr(self) -> *mut T {
1771 self.repr().data as *mut T
1775 unsafe fn unsafe_set(self, index: uint, val: T) {
1776 *self.unsafe_mut_ref(index) = val;
1780 unsafe fn init_elem(self, i: uint, val: T) {
1781 mem::move_val_init(&mut (*self.as_mut_ptr().offset(i as int)), val);
1785 unsafe fn copy_memory(self, src: &[T]) {
1786 let len_src = src.len();
1787 assert!(self.len() >= len_src);
1788 ptr::copy_nonoverlapping_memory(self.as_mut_ptr(), src.as_ptr(), len_src)
1792 /// Trait for &[T] where T is Cloneable
1793 pub trait MutableCloneableVector<T> {
1794 /// Copies as many elements from `src` as it can into `self` (the
1795 /// shorter of `self.len()` and `src.len()`). Returns the number
1796 /// of elements copied.
1801 /// use std::slice::MutableCloneableVector;
1803 /// let mut dst = [0, 0, 0];
1804 /// let src = [1, 2];
1806 /// assert!(dst.copy_from(src) == 2);
1807 /// assert!(dst == [1, 2, 0]);
1809 /// let src2 = [3, 4, 5, 6];
1810 /// assert!(dst.copy_from(src2) == 3);
1811 /// assert!(dst == [3, 4, 5]);
1813 fn copy_from(self, &[T]) -> uint;
1816 impl<'a, T:Clone> MutableCloneableVector<T> for &'a mut [T] {
1818 fn copy_from(self, src: &[T]) -> uint {
1819 for (a, b) in self.mut_iter().zip(src.iter()) {
1822 cmp::min(self.len(), src.len())
1826 /// Methods for mutable vectors with orderable elements, such as
1827 /// in-place sorting.
1828 pub trait MutableTotalOrdVector<T> {
1829 /// Sort the vector, in place.
1831 /// This is equivalent to `self.sort_by(|a, b| a.cmp(b))`.
1836 /// let mut v = [-5, 4, 1, -3, 2];
1839 /// assert!(v == [-5, -3, 1, 2, 4]);
1843 impl<'a, T: TotalOrd> MutableTotalOrdVector<T> for &'a mut [T] {
1846 self.sort_by(|a,b| a.cmp(b))
1851 * Constructs a vector from an unsafe pointer to a buffer
1855 * * ptr - An unsafe pointer to a buffer of `T`
1856 * * elts - The number of elements in the buffer
1858 // Wrapper for fn in raw: needs to be called by net_tcp::on_tcp_read_cb
1859 pub unsafe fn from_buf<T>(ptr: *T, elts: uint) -> ~[T] {
1860 raw::from_buf_raw(ptr, elts)
1863 /// Unsafe operations
1865 use cast::transmute;
1870 use slice::{MutableVector, OwnedVector};
1874 * Form a slice from a pointer and length (as a number of units,
1878 pub unsafe fn buf_as_slice<T,U>(p: *T, len: uint, f: |v: &[T]| -> U)
1887 * Form a slice from a pointer and length (as a number of units,
1891 pub unsafe fn mut_buf_as_slice<T,
1895 f: |v: &mut [T]| -> U)
1904 * Constructs a vector from an unsafe pointer to a buffer
1908 * * ptr - An unsafe pointer to a buffer of `T`
1909 * * elts - The number of elements in the buffer
1911 // Was in raw, but needs to be called by net_tcp::on_tcp_read_cb
1913 pub unsafe fn from_buf_raw<T>(ptr: *T, elts: uint) -> ~[T] {
1914 let mut dst = Vec::with_capacity(elts);
1916 ptr::copy_memory(dst.as_mut_ptr(), ptr, elts);
1917 dst.move_iter().collect()
1921 * Returns a pointer to first element in slice and adjusts
1922 * slice so it no longer contains that element. Fails if
1923 * slice is empty. O(1).
1925 pub unsafe fn shift_ptr<T>(slice: &mut Slice<T>) -> *T {
1926 if slice.len == 0 { fail!("shift on empty slice"); }
1927 let head: *T = slice.data;
1928 slice.data = slice.data.offset(1);
1934 * Returns a pointer to last element in slice and adjusts
1935 * slice so it no longer contains that element. Fails if
1936 * slice is empty. O(1).
1938 pub unsafe fn pop_ptr<T>(slice: &mut Slice<T>) -> *T {
1939 if slice.len == 0 { fail!("pop on empty slice"); }
1940 let tail: *T = slice.data.offset((slice.len - 1) as int);
1946 /// Operations on `[u8]`.
1948 use container::Container;
1949 use slice::MutableVector;
1952 /// A trait for operations on mutable `[u8]`s.
1953 pub trait MutableByteVector {
1954 /// Sets all bytes of the receiver to the given value.
1955 fn set_memory(self, value: u8);
1958 impl<'a> MutableByteVector for &'a mut [u8] {
1960 fn set_memory(self, value: u8) {
1961 unsafe { ptr::set_memory(self.as_mut_ptr(), value, self.len()) };
1965 /// Copies data from `src` to `dst`
1967 /// `src` and `dst` must not overlap. Fails if the length of `dst`
1968 /// is less than the length of `src`.
1970 pub fn copy_memory(dst: &mut [u8], src: &[u8]) {
1971 // Bound checks are done at .copy_memory.
1972 unsafe { dst.copy_memory(src) }
1976 impl<A: Clone> Clone for ~[A] {
1978 fn clone(&self) -> ~[A] {
1979 // Use the fast to_owned on &[A] for cloning
1980 self.as_slice().to_owned()
1984 impl<'a, T: fmt::Show> fmt::Show for &'a [T] {
1985 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1986 if f.flags & (1 << (fmt::parse::FlagAlternate as uint)) == 0 {
1987 try!(write!(f.buf, "["));
1989 let mut is_first = true;
1990 for x in self.iter() {
1994 try!(write!(f.buf, ", "));
1996 try!(write!(f.buf, "{}", *x))
1998 if f.flags & (1 << (fmt::parse::FlagAlternate as uint)) == 0 {
1999 try!(write!(f.buf, "]"));
2005 impl<T: fmt::Show> fmt::Show for ~[T] {
2006 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2007 self.as_slice().fmt(f)
2011 // This works because every lifetime is a sub-lifetime of 'static
2012 impl<'a, A> Default for &'a [A] {
2013 fn default() -> &'a [A] { &'a [] }
2016 impl<A> Default for ~[A] {
2017 fn default() -> ~[A] { ~[] }
2020 /// Immutable slice iterator
2021 pub struct Items<'a, T> {
2024 marker: marker::ContravariantLifetime<'a>
2027 /// Mutable slice iterator
2028 pub struct MutItems<'a, T> {
2031 marker: marker::ContravariantLifetime<'a>,
2032 marker2: marker::NoCopy
2035 macro_rules! iterator {
2036 (struct $name:ident -> $ptr:ty, $elem:ty) => {
2037 impl<'a, T> Iterator<$elem> for $name<'a, T> {
2039 fn next(&mut self) -> Option<$elem> {
2040 // could be implemented with slices, but this avoids bounds checks
2042 if self.ptr == self.end {
2046 self.ptr = if mem::size_of::<T>() == 0 {
2047 // purposefully don't use 'ptr.offset' because for
2048 // vectors with 0-size elements this would return the
2050 transmute(self.ptr as uint + 1)
2055 Some(transmute(old))
2061 fn size_hint(&self) -> (uint, Option<uint>) {
2062 let diff = (self.end as uint) - (self.ptr as uint);
2063 let exact = diff / mem::nonzero_size_of::<T>();
2064 (exact, Some(exact))
2068 impl<'a, T> DoubleEndedIterator<$elem> for $name<'a, T> {
2070 fn next_back(&mut self) -> Option<$elem> {
2071 // could be implemented with slices, but this avoids bounds checks
2073 if self.end == self.ptr {
2076 self.end = if mem::size_of::<T>() == 0 {
2077 // See above for why 'ptr.offset' isn't used
2078 transmute(self.end as uint - 1)
2082 Some(transmute(self.end))
2090 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
2092 fn indexable(&self) -> uint {
2093 let (exact, _) = self.size_hint();
2098 fn idx(&self, index: uint) -> Option<&'a T> {
2100 if index < self.indexable() {
2101 transmute(self.ptr.offset(index as int))
2109 iterator!{struct Items -> *T, &'a T}
2110 pub type RevItems<'a, T> = Rev<Items<'a, T>>;
2112 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
2113 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
2115 impl<'a, T> Clone for Items<'a, T> {
2116 fn clone(&self) -> Items<'a, T> { *self }
2119 iterator!{struct MutItems -> *mut T, &'a mut T}
2120 pub type RevMutItems<'a, T> = Rev<MutItems<'a, T>>;
2122 /// An iterator over the subslices of the vector which are separated
2123 /// by elements that match `pred`.
2124 pub struct MutSplits<'a, T> {
2126 pred: |t: &T|: 'a -> bool,
2130 impl<'a, T> Iterator<&'a mut [T]> for MutSplits<'a, T> {
2132 fn next(&mut self) -> Option<&'a mut [T]> {
2133 if self.finished { return None; }
2135 match self.v.iter().position(|x| (self.pred)(x)) {
2137 self.finished = true;
2138 let tmp = mem::replace(&mut self.v, &mut []);
2139 let len = tmp.len();
2140 let (head, tail) = tmp.mut_split_at(len);
2145 let tmp = mem::replace(&mut self.v, &mut []);
2146 let (head, tail) = tmp.mut_split_at(idx);
2147 self.v = tail.mut_slice_from(1);
2154 fn size_hint(&self) -> (uint, Option<uint>) {
2158 // if the predicate doesn't match anything, we yield one slice
2159 // if it matches every element, we yield len+1 empty slices.
2160 (1, Some(self.v.len() + 1))
2165 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutSplits<'a, T> {
2167 fn next_back(&mut self) -> Option<&'a mut [T]> {
2168 if self.finished { return None; }
2170 match self.v.iter().rposition(|x| (self.pred)(x)) {
2172 self.finished = true;
2173 let tmp = mem::replace(&mut self.v, &mut []);
2177 let tmp = mem::replace(&mut self.v, &mut []);
2178 let (head, tail) = tmp.mut_split_at(idx);
2180 Some(tail.mut_slice_from(1))
2186 /// An iterator over a vector in (non-overlapping) mutable chunks (`size` elements at a time). When
2187 /// the vector len is not evenly divided by the chunk size, the last slice of the iteration will be
2189 pub struct MutChunks<'a, T> {
2194 impl<'a, T> Iterator<&'a mut [T]> for MutChunks<'a, T> {
2196 fn next(&mut self) -> Option<&'a mut [T]> {
2197 if self.v.len() == 0 {
2200 let sz = cmp::min(self.v.len(), self.chunk_size);
2201 let tmp = mem::replace(&mut self.v, &mut []);
2202 let (head, tail) = tmp.mut_split_at(sz);
2209 fn size_hint(&self) -> (uint, Option<uint>) {
2210 if self.v.len() == 0 {
2213 let (n, rem) = div_rem(self.v.len(), self.chunk_size);
2214 let n = if rem > 0 { n + 1 } else { n };
2220 impl<'a, T> DoubleEndedIterator<&'a mut [T]> for MutChunks<'a, T> {
2222 fn next_back(&mut self) -> Option<&'a mut [T]> {
2223 if self.v.len() == 0 {
2226 let remainder = self.v.len() % self.chunk_size;
2227 let sz = if remainder != 0 { remainder } else { self.chunk_size };
2228 let tmp = mem::replace(&mut self.v, &mut []);
2229 let tmp_len = tmp.len();
2230 let (head, tail) = tmp.mut_split_at(tmp_len - sz);
2237 /// An iterator that moves out of a vector.
2238 pub struct MoveItems<T> {
2239 allocation: *mut u8, // the block of memory allocated for the vector
2240 iter: Items<'static, T>
2243 impl<T> Iterator<T> for MoveItems<T> {
2245 fn next(&mut self) -> Option<T> {
2247 self.iter.next().map(|x| ptr::read(x))
2252 fn size_hint(&self) -> (uint, Option<uint>) {
2253 self.iter.size_hint()
2257 impl<T> DoubleEndedIterator<T> for MoveItems<T> {
2259 fn next_back(&mut self) -> Option<T> {
2261 self.iter.next_back().map(|x| ptr::read(x))
2266 #[unsafe_destructor]
2267 impl<T> Drop for MoveItems<T> {
2268 fn drop(&mut self) {
2269 // destroy the remaining elements
2272 exchange_free(self.allocation as *u8)
2277 /// An iterator that moves out of a vector in reverse order.
2278 pub type RevMoveItems<T> = Rev<MoveItems<T>>;
2280 impl<A> FromIterator<A> for ~[A] {
2281 fn from_iter<T: Iterator<A>>(mut iterator: T) -> ~[A] {
2282 let mut xs: Vec<A> = iterator.collect();
2284 // Must shrink so the capacity is the same as the length. The length of
2285 // the ~[T] vector must exactly match the length of the allocation.
2289 assert!(len == xs.capacity());
2290 let data = xs.as_mut_ptr();
2292 let data_size = len.checked_mul(&mem::size_of::<A>());
2293 let data_size = data_size.expect("overflow in from_iter()");
2294 let size = mem::size_of::<RawVec<()>>().checked_add(&data_size);
2295 let size = size.expect("overflow in from_iter()");
2298 // This is some terribly awful code. Note that all of this will go away
2299 // with DST because creating ~[T] from Vec<T> will just be some pointer
2302 let ret = malloc_raw(size) as *mut RawVec<()>;
2304 (*ret).fill = len * mem::nonzero_size_of::<A>();
2305 (*ret).alloc = len * mem::nonzero_size_of::<A>();
2306 ptr::copy_nonoverlapping_memory(&mut (*ret).data as *mut _ as *mut u8,
2309 xs.set_len(0); // ownership has been transferred
2310 cast::transmute(ret)
2321 use rand::{Rng, task_rng};
2323 fn square(n: uint) -> uint { n * n }
2325 fn is_odd(n: &uint) -> bool { *n % 2u == 1u }
2328 fn test_unsafe_ptrs() {
2330 // Test on-stack copy-from-buf.
2332 let mut ptr = a.as_ptr();
2333 let b = from_buf(ptr, 3u);
2334 assert_eq!(b.len(), 3u);
2335 assert_eq!(b[0], 1);
2336 assert_eq!(b[1], 2);
2337 assert_eq!(b[2], 3);
2339 // Test on-heap copy-from-buf.
2340 let c = ~[1, 2, 3, 4, 5];
2342 let d = from_buf(ptr, 5u);
2343 assert_eq!(d.len(), 5u);
2344 assert_eq!(d[0], 1);
2345 assert_eq!(d[1], 2);
2346 assert_eq!(d[2], 3);
2347 assert_eq!(d[3], 4);
2348 assert_eq!(d[4], 5);
2354 // Test on-stack from_fn.
2355 let mut v = Vec::from_fn(3u, square);
2357 let v = v.as_slice();
2358 assert_eq!(v.len(), 3u);
2359 assert_eq!(v[0], 0u);
2360 assert_eq!(v[1], 1u);
2361 assert_eq!(v[2], 4u);
2364 // Test on-heap from_fn.
2365 v = Vec::from_fn(5u, square);
2367 let v = v.as_slice();
2368 assert_eq!(v.len(), 5u);
2369 assert_eq!(v[0], 0u);
2370 assert_eq!(v[1], 1u);
2371 assert_eq!(v[2], 4u);
2372 assert_eq!(v[3], 9u);
2373 assert_eq!(v[4], 16u);
2378 fn test_from_elem() {
2379 // Test on-stack from_elem.
2380 let mut v = Vec::from_elem(2u, 10u);
2382 let v = v.as_slice();
2383 assert_eq!(v.len(), 2u);
2384 assert_eq!(v[0], 10u);
2385 assert_eq!(v[1], 10u);
2388 // Test on-heap from_elem.
2389 v = Vec::from_elem(6u, 20u);
2391 let v = v.as_slice();
2392 assert_eq!(v[0], 20u);
2393 assert_eq!(v[1], 20u);
2394 assert_eq!(v[2], 20u);
2395 assert_eq!(v[3], 20u);
2396 assert_eq!(v[4], 20u);
2397 assert_eq!(v[5], 20u);
2402 fn test_is_empty() {
2403 let xs: [int, ..0] = [];
2404 assert!(xs.is_empty());
2405 assert!(![0].is_empty());
2409 fn test_len_divzero() {
2411 let v0 : &[Z] = &[];
2412 let v1 : &[Z] = &[[]];
2413 let v2 : &[Z] = &[[], []];
2414 assert_eq!(mem::size_of::<Z>(), 0);
2415 assert_eq!(v0.len(), 0);
2416 assert_eq!(v1.len(), 1);
2417 assert_eq!(v2.len(), 2);
2423 assert_eq!(a.get(1), None);
2425 assert_eq!(a.get(1).unwrap(), &12);
2427 assert_eq!(a.get(1).unwrap(), &12);
2433 assert_eq!(a.head(), None);
2435 assert_eq!(a.head().unwrap(), &11);
2437 assert_eq!(a.head().unwrap(), &11);
2443 assert_eq!(a.tail(), &[]);
2445 assert_eq!(a.tail(), &[12]);
2450 fn test_tail_empty() {
2451 let a: ~[int] = ~[];
2457 let mut a = ~[11, 12, 13];
2458 assert_eq!(a.tailn(0), &[11, 12, 13]);
2460 assert_eq!(a.tailn(2), &[13]);
2465 fn test_tailn_empty() {
2466 let a: ~[int] = ~[];
2473 assert_eq!(a.init(), &[]);
2475 assert_eq!(a.init(), &[11]);
2480 fn test_init_empty() {
2481 let a: ~[int] = ~[];
2487 let mut a = ~[11, 12, 13];
2488 assert_eq!(a.initn(0), &[11, 12, 13]);
2490 assert_eq!(a.initn(2), &[11]);
2495 fn test_initn_empty() {
2496 let a: ~[int] = ~[];
2503 assert_eq!(a.last(), None);
2505 assert_eq!(a.last().unwrap(), &11);
2507 assert_eq!(a.last().unwrap(), &12);
2512 // Test fixed length vector.
2513 let vec_fixed = [1, 2, 3, 4];
2514 let v_a = vec_fixed.slice(1u, vec_fixed.len()).to_owned();
2515 assert_eq!(v_a.len(), 3u);
2516 assert_eq!(v_a[0], 2);
2517 assert_eq!(v_a[1], 3);
2518 assert_eq!(v_a[2], 4);
2521 let vec_stack = &[1, 2, 3];
2522 let v_b = vec_stack.slice(1u, 3u).to_owned();
2523 assert_eq!(v_b.len(), 2u);
2524 assert_eq!(v_b[0], 2);
2525 assert_eq!(v_b[1], 3);
2527 // Test on exchange heap.
2528 let vec_unique = ~[1, 2, 3, 4, 5, 6];
2529 let v_d = vec_unique.slice(1u, 6u).to_owned();
2530 assert_eq!(v_d.len(), 5u);
2531 assert_eq!(v_d[0], 2);
2532 assert_eq!(v_d[1], 3);
2533 assert_eq!(v_d[2], 4);
2534 assert_eq!(v_d[3], 5);
2535 assert_eq!(v_d[4], 6);
2539 fn test_slice_from() {
2540 let vec = &[1, 2, 3, 4];
2541 assert_eq!(vec.slice_from(0), vec);
2542 assert_eq!(vec.slice_from(2), &[3, 4]);
2543 assert_eq!(vec.slice_from(4), &[]);
2547 fn test_slice_to() {
2548 let vec = &[1, 2, 3, 4];
2549 assert_eq!(vec.slice_to(4), vec);
2550 assert_eq!(vec.slice_to(2), &[1, 2]);
2551 assert_eq!(vec.slice_to(0), &[]);
2557 let mut v = vec![5];
2559 assert_eq!(v.len(), 0);
2560 assert_eq!(e, Some(5));
2562 assert_eq!(f, None);
2564 assert_eq!(g, None);
2568 fn test_swap_remove() {
2569 let mut v = vec![1, 2, 3, 4, 5];
2570 let mut e = v.swap_remove(0);
2571 assert_eq!(e, Some(1));
2572 assert_eq!(v, vec![5, 2, 3, 4]);
2573 e = v.swap_remove(3);
2574 assert_eq!(e, Some(4));
2575 assert_eq!(v, vec![5, 2, 3]);
2577 e = v.swap_remove(3);
2578 assert_eq!(e, None);
2579 assert_eq!(v, vec![5, 2, 3]);
2583 fn test_swap_remove_noncopyable() {
2584 // Tests that we don't accidentally run destructors twice.
2585 let mut v = vec![::unstable::sync::Exclusive::new(()),
2586 ::unstable::sync::Exclusive::new(()),
2587 ::unstable::sync::Exclusive::new(())];
2588 let mut _e = v.swap_remove(0);
2589 assert_eq!(v.len(), 2);
2590 _e = v.swap_remove(1);
2591 assert_eq!(v.len(), 1);
2592 _e = v.swap_remove(0);
2593 assert_eq!(v.len(), 0);
2598 // Test on-stack push().
2601 assert_eq!(v.len(), 1u);
2602 assert_eq!(v.as_slice()[0], 1);
2604 // Test on-heap push().
2606 assert_eq!(v.len(), 2u);
2607 assert_eq!(v.as_slice()[0], 1);
2608 assert_eq!(v.as_slice()[1], 2);
2613 // Test on-stack grow().
2617 let v = v.as_slice();
2618 assert_eq!(v.len(), 2u);
2619 assert_eq!(v[0], 1);
2620 assert_eq!(v[1], 1);
2623 // Test on-heap grow().
2626 let v = v.as_slice();
2627 assert_eq!(v.len(), 5u);
2628 assert_eq!(v[0], 1);
2629 assert_eq!(v[1], 1);
2630 assert_eq!(v[2], 2);
2631 assert_eq!(v[3], 2);
2632 assert_eq!(v[4], 2);
2639 v.grow_fn(3u, square);
2640 let v = v.as_slice();
2641 assert_eq!(v.len(), 3u);
2642 assert_eq!(v[0], 0u);
2643 assert_eq!(v[1], 1u);
2644 assert_eq!(v[2], 4u);
2648 fn test_grow_set() {
2649 let mut v = vec![1, 2, 3];
2650 v.grow_set(4u, &4, 5);
2651 let v = v.as_slice();
2652 assert_eq!(v.len(), 5u);
2653 assert_eq!(v[0], 1);
2654 assert_eq!(v[1], 2);
2655 assert_eq!(v[2], 3);
2656 assert_eq!(v[3], 4);
2657 assert_eq!(v[4], 5);
2661 fn test_truncate() {
2662 let mut v = vec![~6,~5,~4];
2664 let v = v.as_slice();
2665 assert_eq!(v.len(), 1);
2666 assert_eq!(*(v[0]), 6);
2667 // If the unsafe block didn't drop things properly, we blow up here.
2672 let mut v = vec![~6,~5,~4];
2674 assert_eq!(v.len(), 0);
2675 // If the unsafe block didn't drop things properly, we blow up here.
2680 fn case(a: Vec<uint>, b: Vec<uint>) {
2685 case(vec![], vec![]);
2686 case(vec![1], vec![1]);
2687 case(vec![1,1], vec![1]);
2688 case(vec![1,2,3], vec![1,2,3]);
2689 case(vec![1,1,2,3], vec![1,2,3]);
2690 case(vec![1,2,2,3], vec![1,2,3]);
2691 case(vec![1,2,3,3], vec![1,2,3]);
2692 case(vec![1,1,2,2,2,3,3], vec![1,2,3]);
2696 fn test_dedup_unique() {
2697 let mut v0 = vec![~1, ~1, ~2, ~3];
2699 let mut v1 = vec![~1, ~2, ~2, ~3];
2701 let mut v2 = vec![~1, ~2, ~3, ~3];
2704 * If the ~pointers were leaked or otherwise misused, valgrind and/or
2705 * rustrt should raise errors.
2710 fn test_dedup_shared() {
2711 let mut v0 = vec![~1, ~1, ~2, ~3];
2713 let mut v1 = vec![~1, ~2, ~2, ~3];
2715 let mut v2 = vec![~1, ~2, ~3, ~3];
2718 * If the pointers were leaked or otherwise misused, valgrind and/or
2719 * rustrt should raise errors.
2725 let mut v = vec![1, 2, 3, 4, 5];
2727 assert_eq!(v, vec![1, 3, 5]);
2731 fn test_zip_unzip() {
2732 let z1 = vec![(1, 4), (2, 5), (3, 6)];
2734 let (left, right) = unzip(z1.iter().map(|&x| x));
2736 assert_eq!((1, 4), (left[0], right[0]));
2737 assert_eq!((2, 5), (left[1], right[1]));
2738 assert_eq!((3, 6), (left[2], right[2]));
2742 fn test_element_swaps() {
2743 let mut v = [1, 2, 3];
2744 for (i, (a, b)) in ElementSwaps::new(v.len()).enumerate() {
2747 0 => assert!(v == [1, 3, 2]),
2748 1 => assert!(v == [3, 1, 2]),
2749 2 => assert!(v == [3, 2, 1]),
2750 3 => assert!(v == [2, 3, 1]),
2751 4 => assert!(v == [2, 1, 3]),
2752 5 => assert!(v == [1, 2, 3]),
2759 fn test_permutations() {
2761 let v: [int, ..0] = [];
2762 let mut it = v.permutations();
2763 assert_eq!(it.next(), None);
2767 let mut it = v.permutations();
2768 assert_eq!(it.next(), None);
2772 let mut it = v.permutations();
2773 assert_eq!(it.next(), Some(~[1,2,3]));
2774 assert_eq!(it.next(), Some(~[1,3,2]));
2775 assert_eq!(it.next(), Some(~[3,1,2]));
2776 assert_eq!(it.next(), Some(~[3,2,1]));
2777 assert_eq!(it.next(), Some(~[2,3,1]));
2778 assert_eq!(it.next(), Some(~[2,1,3]));
2779 assert_eq!(it.next(), None);
2782 // check that we have N! permutations
2783 let v = ['A', 'B', 'C', 'D', 'E', 'F'];
2785 for _perm in v.permutations() {
2788 assert_eq!(amt, 2 * 3 * 4 * 5 * 6);
2793 fn test_position_elem() {
2794 assert!([].position_elem(&1).is_none());
2796 let v1 = ~[1, 2, 3, 3, 2, 5];
2797 assert_eq!(v1.position_elem(&1), Some(0u));
2798 assert_eq!(v1.position_elem(&2), Some(1u));
2799 assert_eq!(v1.position_elem(&5), Some(5u));
2800 assert!(v1.position_elem(&4).is_none());
2804 fn test_bsearch_elem() {
2805 assert_eq!([1,2,3,4,5].bsearch_elem(&5), Some(4));
2806 assert_eq!([1,2,3,4,5].bsearch_elem(&4), Some(3));
2807 assert_eq!([1,2,3,4,5].bsearch_elem(&3), Some(2));
2808 assert_eq!([1,2,3,4,5].bsearch_elem(&2), Some(1));
2809 assert_eq!([1,2,3,4,5].bsearch_elem(&1), Some(0));
2811 assert_eq!([2,4,6,8,10].bsearch_elem(&1), None);
2812 assert_eq!([2,4,6,8,10].bsearch_elem(&5), None);
2813 assert_eq!([2,4,6,8,10].bsearch_elem(&4), Some(1));
2814 assert_eq!([2,4,6,8,10].bsearch_elem(&10), Some(4));
2816 assert_eq!([2,4,6,8].bsearch_elem(&1), None);
2817 assert_eq!([2,4,6,8].bsearch_elem(&5), None);
2818 assert_eq!([2,4,6,8].bsearch_elem(&4), Some(1));
2819 assert_eq!([2,4,6,8].bsearch_elem(&8), Some(3));
2821 assert_eq!([2,4,6].bsearch_elem(&1), None);
2822 assert_eq!([2,4,6].bsearch_elem(&5), None);
2823 assert_eq!([2,4,6].bsearch_elem(&4), Some(1));
2824 assert_eq!([2,4,6].bsearch_elem(&6), Some(2));
2826 assert_eq!([2,4].bsearch_elem(&1), None);
2827 assert_eq!([2,4].bsearch_elem(&5), None);
2828 assert_eq!([2,4].bsearch_elem(&2), Some(0));
2829 assert_eq!([2,4].bsearch_elem(&4), Some(1));
2831 assert_eq!([2].bsearch_elem(&1), None);
2832 assert_eq!([2].bsearch_elem(&5), None);
2833 assert_eq!([2].bsearch_elem(&2), Some(0));
2835 assert_eq!([].bsearch_elem(&1), None);
2836 assert_eq!([].bsearch_elem(&5), None);
2838 assert!([1,1,1,1,1].bsearch_elem(&1) != None);
2839 assert!([1,1,1,1,2].bsearch_elem(&1) != None);
2840 assert!([1,1,1,2,2].bsearch_elem(&1) != None);
2841 assert!([1,1,2,2,2].bsearch_elem(&1) != None);
2842 assert_eq!([1,2,2,2,2].bsearch_elem(&1), Some(0));
2844 assert_eq!([1,2,3,4,5].bsearch_elem(&6), None);
2845 assert_eq!([1,2,3,4,5].bsearch_elem(&0), None);
2850 let mut v: ~[int] = ~[10, 20];
2851 assert_eq!(v[0], 10);
2852 assert_eq!(v[1], 20);
2854 assert_eq!(v[0], 20);
2855 assert_eq!(v[1], 10);
2857 let mut v3: ~[int] = ~[];
2859 assert!(v3.is_empty());
2864 use realstd::slice::Vector;
2865 use realstd::clone::Clone;
2866 for len in range(4u, 25) {
2867 for _ in range(0, 100) {
2868 let mut v = task_rng().gen_vec::<uint>(len);
2869 let mut v1 = v.clone();
2871 v.as_mut_slice().sort();
2872 assert!(v.as_slice().windows(2).all(|w| w[0] <= w[1]));
2874 v1.as_mut_slice().sort_by(|a, b| a.cmp(b));
2875 assert!(v1.as_slice().windows(2).all(|w| w[0] <= w[1]));
2877 v1.as_mut_slice().sort_by(|a, b| b.cmp(a));
2878 assert!(v1.as_slice().windows(2).all(|w| w[0] >= w[1]));
2882 // shouldn't fail/crash
2883 let mut v: [uint, .. 0] = [];
2886 let mut v = [0xDEADBEEFu];
2888 assert!(v == [0xDEADBEEF]);
2892 fn test_sort_stability() {
2893 for len in range(4, 25) {
2894 for _ in range(0 , 10) {
2895 let mut counts = [0, .. 10];
2897 // create a vector like [(6, 1), (5, 1), (6, 2), ...],
2898 // where the first item of each tuple is random, but
2899 // the second item represents which occurrence of that
2900 // number this element is, i.e. the second elements
2901 // will occur in sorted order.
2902 let mut v = range(0, len).map(|_| {
2903 let n = task_rng().gen::<uint>() % 10;
2906 }).collect::<~[(uint, int)]>();
2908 // only sort on the first element, so an unstable sort
2909 // may mix up the counts.
2910 v.sort_by(|&(a,_), &(b,_)| a.cmp(&b));
2912 // this comparison includes the count (the second item
2913 // of the tuple), so elements with equal first items
2914 // will need to be ordered with increasing
2915 // counts... i.e. exactly asserting that this sort is
2917 assert!(v.windows(2).all(|w| w[0] <= w[1]));
2923 fn test_partition() {
2924 assert_eq!((~[]).partition(|x: &int| *x < 3), (~[], ~[]));
2925 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 4), (~[1, 2, 3], ~[]));
2926 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 2), (~[1], ~[2, 3]));
2927 assert_eq!((~[1, 2, 3]).partition(|x: &int| *x < 0), (~[], ~[1, 2, 3]));
2931 fn test_partitioned() {
2932 assert_eq!(([]).partitioned(|x: &int| *x < 3), (~[], ~[]))
2933 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 4), (~[1, 2, 3], ~[]));
2934 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 2), (~[1], ~[2, 3]));
2935 assert_eq!(([1, 2, 3]).partitioned(|x: &int| *x < 0), (~[], ~[1, 2, 3]));
2940 let v: [~[int], ..0] = [];
2941 assert_eq!(v.concat_vec(), ~[]);
2942 assert_eq!([~[1], ~[2,3]].concat_vec(), ~[1, 2, 3]);
2944 assert_eq!([&[1], &[2,3]].concat_vec(), ~[1, 2, 3]);
2949 let v: [~[int], ..0] = [];
2950 assert_eq!(v.connect_vec(&0), ~[]);
2951 assert_eq!([~[1], ~[2, 3]].connect_vec(&0), ~[1, 0, 2, 3]);
2952 assert_eq!([~[1], ~[2], ~[3]].connect_vec(&0), ~[1, 0, 2, 0, 3]);
2954 assert_eq!(v.connect_vec(&0), ~[]);
2955 assert_eq!([&[1], &[2, 3]].connect_vec(&0), ~[1, 0, 2, 3]);
2956 assert_eq!([&[1], &[2], &[3]].connect_vec(&0), ~[1, 0, 2, 0, 3]);
2961 let mut x = vec![1, 2, 3];
2962 assert_eq!(x.shift(), Some(1));
2963 assert_eq!(&x, &vec![2, 3]);
2964 assert_eq!(x.shift(), Some(2));
2965 assert_eq!(x.shift(), Some(3));
2966 assert_eq!(x.shift(), None);
2967 assert_eq!(x.len(), 0);
2972 let mut x = vec![1, 2, 3];
2974 assert_eq!(x, vec![0, 1, 2, 3]);
2979 let mut a = vec![1, 2, 4];
2981 assert_eq!(a, vec![1, 2, 3, 4]);
2983 let mut a = vec![1, 2, 3];
2985 assert_eq!(a, vec![0, 1, 2, 3]);
2987 let mut a = vec![1, 2, 3];
2989 assert_eq!(a, vec![1, 2, 3, 4]);
2993 assert_eq!(a, vec![1]);
2998 fn test_insert_oob() {
2999 let mut a = vec![1, 2, 3];
3005 let mut a = vec![1,2,3,4];
3007 assert_eq!(a.remove(2), Some(3));
3008 assert_eq!(a, vec![1,2,4]);
3010 assert_eq!(a.remove(2), Some(4));
3011 assert_eq!(a, vec![1,2]);
3013 assert_eq!(a.remove(2), None);
3014 assert_eq!(a, vec![1,2]);
3016 assert_eq!(a.remove(0), Some(1));
3017 assert_eq!(a, vec![2]);
3019 assert_eq!(a.remove(0), Some(2));
3020 assert_eq!(a, vec![]);
3022 assert_eq!(a.remove(0), None);
3023 assert_eq!(a.remove(10), None);
3027 fn test_capacity() {
3028 let mut v = vec![0u64];
3029 v.reserve_exact(10u);
3030 assert_eq!(v.capacity(), 10u);
3031 let mut v = vec![0u32];
3032 v.reserve_exact(10u);
3033 assert_eq!(v.capacity(), 10u);
3038 let v = vec![1, 2, 3, 4, 5];
3039 let v = v.slice(1u, 3u);
3040 assert_eq!(v.len(), 2u);
3041 assert_eq!(v[0], 2);
3042 assert_eq!(v[1], 3);
3048 fn test_from_fn_fail() {
3049 Vec::from_fn(100, |v| {
3050 if v == 50 { fail!() }
3057 fn test_from_elem_fail() {
3063 boxes: (~int, Rc<int>)
3067 fn clone(&self) -> S {
3068 let s = unsafe { cast::transmute_mut(self) };
3070 if s.f == 10 { fail!() }
3071 S { f: s.f, boxes: s.boxes.clone() }
3075 let s = S { f: 0, boxes: (~0, Rc::new(0)) };
3076 let _ = Vec::from_elem(100, s);
3081 fn test_grow_fn_fail() {
3084 v.grow_fn(100, |i| {
3094 fn test_permute_fail() {
3096 let v = [(~0, Rc::new(0)), (~0, Rc::new(0)), (~0, Rc::new(0)), (~0, Rc::new(0))];
3098 for _ in v.permutations() {
3108 fn test_copy_memory_oob() {
3110 let mut a = [1, 2, 3, 4];
3111 let b = [1, 2, 3, 4, 5];
3117 fn test_total_ord() {
3118 [1, 2, 3, 4].cmp(& &[1, 2, 3]) == Greater;
3119 [1, 2, 3].cmp(& &[1, 2, 3, 4]) == Less;
3120 [1, 2, 3, 4].cmp(& &[1, 2, 3, 4]) == Equal;
3121 [1, 2, 3, 4, 5, 5, 5, 5].cmp(& &[1, 2, 3, 4, 5, 6]) == Less;
3122 [2, 2].cmp(& &[1, 2, 3, 4]) == Greater;
3126 fn test_iterator() {
3128 let xs = [1, 2, 5, 10, 11];
3129 let mut it = xs.iter();
3130 assert_eq!(it.size_hint(), (5, Some(5)));
3131 assert_eq!(it.next().unwrap(), &1);
3132 assert_eq!(it.size_hint(), (4, Some(4)));
3133 assert_eq!(it.next().unwrap(), &2);
3134 assert_eq!(it.size_hint(), (3, Some(3)));
3135 assert_eq!(it.next().unwrap(), &5);
3136 assert_eq!(it.size_hint(), (2, Some(2)));
3137 assert_eq!(it.next().unwrap(), &10);
3138 assert_eq!(it.size_hint(), (1, Some(1)));
3139 assert_eq!(it.next().unwrap(), &11);
3140 assert_eq!(it.size_hint(), (0, Some(0)));
3141 assert!(it.next().is_none());
3145 fn test_random_access_iterator() {
3147 let xs = [1, 2, 5, 10, 11];
3148 let mut it = xs.iter();
3150 assert_eq!(it.indexable(), 5);
3151 assert_eq!(it.idx(0).unwrap(), &1);
3152 assert_eq!(it.idx(2).unwrap(), &5);
3153 assert_eq!(it.idx(4).unwrap(), &11);
3154 assert!(it.idx(5).is_none());
3156 assert_eq!(it.next().unwrap(), &1);
3157 assert_eq!(it.indexable(), 4);
3158 assert_eq!(it.idx(0).unwrap(), &2);
3159 assert_eq!(it.idx(3).unwrap(), &11);
3160 assert!(it.idx(4).is_none());
3162 assert_eq!(it.next().unwrap(), &2);
3163 assert_eq!(it.indexable(), 3);
3164 assert_eq!(it.idx(1).unwrap(), &10);
3165 assert!(it.idx(3).is_none());
3167 assert_eq!(it.next().unwrap(), &5);
3168 assert_eq!(it.indexable(), 2);
3169 assert_eq!(it.idx(1).unwrap(), &11);
3171 assert_eq!(it.next().unwrap(), &10);
3172 assert_eq!(it.indexable(), 1);
3173 assert_eq!(it.idx(0).unwrap(), &11);
3174 assert!(it.idx(1).is_none());
3176 assert_eq!(it.next().unwrap(), &11);
3177 assert_eq!(it.indexable(), 0);
3178 assert!(it.idx(0).is_none());
3180 assert!(it.next().is_none());
3184 fn test_iter_size_hints() {
3186 let mut xs = [1, 2, 5, 10, 11];
3187 assert_eq!(xs.iter().size_hint(), (5, Some(5)));
3188 assert_eq!(xs.rev_iter().size_hint(), (5, Some(5)));
3189 assert_eq!(xs.mut_iter().size_hint(), (5, Some(5)));
3190 assert_eq!(xs.mut_rev_iter().size_hint(), (5, Some(5)));
3194 fn test_iter_clone() {
3196 let mut it = xs.iter();
3198 let mut jt = it.clone();
3199 assert_eq!(it.next(), jt.next());
3200 assert_eq!(it.next(), jt.next());
3201 assert_eq!(it.next(), jt.next());
3205 fn test_mut_iterator() {
3207 let mut xs = [1, 2, 3, 4, 5];
3208 for x in xs.mut_iter() {
3211 assert!(xs == [2, 3, 4, 5, 6])
3215 fn test_rev_iterator() {
3218 let xs = [1, 2, 5, 10, 11];
3219 let ys = [11, 10, 5, 2, 1];
3221 for &x in xs.rev_iter() {
3222 assert_eq!(x, ys[i]);
3229 fn test_mut_rev_iterator() {
3231 let mut xs = [1u, 2, 3, 4, 5];
3232 for (i,x) in xs.mut_rev_iter().enumerate() {
3235 assert!(xs == [5, 5, 5, 5, 5])
3239 fn test_move_iterator() {
3241 let xs = ~[1u,2,3,4,5];
3242 assert_eq!(xs.move_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
3246 fn test_move_rev_iterator() {
3248 let xs = ~[1u,2,3,4,5];
3249 assert_eq!(xs.move_rev_iter().fold(0, |a: uint, b: uint| 10*a + b), 54321);
3253 fn test_splitator() {
3254 let xs = &[1i,2,3,4,5];
3256 assert_eq!(xs.split(|x| *x % 2 == 0).collect::<~[&[int]]>(),
3257 ~[&[1], &[3], &[5]]);
3258 assert_eq!(xs.split(|x| *x == 1).collect::<~[&[int]]>(),
3259 ~[&[], &[2,3,4,5]]);
3260 assert_eq!(xs.split(|x| *x == 5).collect::<~[&[int]]>(),
3261 ~[&[1,2,3,4], &[]]);
3262 assert_eq!(xs.split(|x| *x == 10).collect::<~[&[int]]>(),
3264 assert_eq!(xs.split(|_| true).collect::<~[&[int]]>(),
3265 ~[&[], &[], &[], &[], &[], &[]]);
3267 let xs: &[int] = &[];
3268 assert_eq!(xs.split(|x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3272 fn test_splitnator() {
3273 let xs = &[1i,2,3,4,5];
3275 assert_eq!(xs.splitn(0, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3277 assert_eq!(xs.splitn(1, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3279 assert_eq!(xs.splitn(3, |_| true).collect::<~[&[int]]>(),
3280 ~[&[], &[], &[], &[4,5]]);
3282 let xs: &[int] = &[];
3283 assert_eq!(xs.splitn(1, |x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3287 fn test_rsplitator() {
3288 let xs = &[1i,2,3,4,5];
3290 assert_eq!(xs.rsplit(|x| *x % 2 == 0).collect::<~[&[int]]>(),
3291 ~[&[5], &[3], &[1]]);
3292 assert_eq!(xs.rsplit(|x| *x == 1).collect::<~[&[int]]>(),
3293 ~[&[2,3,4,5], &[]]);
3294 assert_eq!(xs.rsplit(|x| *x == 5).collect::<~[&[int]]>(),
3295 ~[&[], &[1,2,3,4]]);
3296 assert_eq!(xs.rsplit(|x| *x == 10).collect::<~[&[int]]>(),
3299 let xs: &[int] = &[];
3300 assert_eq!(xs.rsplit(|x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3304 fn test_rsplitnator() {
3305 let xs = &[1,2,3,4,5];
3307 assert_eq!(xs.rsplitn(0, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3309 assert_eq!(xs.rsplitn(1, |x| *x % 2 == 0).collect::<~[&[int]]>(),
3311 assert_eq!(xs.rsplitn(3, |_| true).collect::<~[&[int]]>(),
3312 ~[&[], &[], &[], &[1,2]]);
3314 let xs: &[int] = &[];
3315 assert_eq!(xs.rsplitn(1, |x| *x == 5).collect::<~[&[int]]>(), ~[&[]]);
3319 fn test_windowsator() {
3320 let v = &[1i,2,3,4];
3322 assert_eq!(v.windows(2).collect::<~[&[int]]>(), ~[&[1,2], &[2,3], &[3,4]]);
3323 assert_eq!(v.windows(3).collect::<~[&[int]]>(), ~[&[1i,2,3], &[2,3,4]]);
3324 assert!(v.windows(6).next().is_none());
3329 fn test_windowsator_0() {
3330 let v = &[1i,2,3,4];
3331 let _it = v.windows(0);
3335 fn test_chunksator() {
3336 let v = &[1i,2,3,4,5];
3338 assert_eq!(v.chunks(2).collect::<~[&[int]]>(), ~[&[1i,2], &[3,4], &[5]]);
3339 assert_eq!(v.chunks(3).collect::<~[&[int]]>(), ~[&[1i,2,3], &[4,5]]);
3340 assert_eq!(v.chunks(6).collect::<~[&[int]]>(), ~[&[1i,2,3,4,5]]);
3342 assert_eq!(v.chunks(2).rev().collect::<~[&[int]]>(), ~[&[5i], &[3,4], &[1,2]]);
3343 let it = v.chunks(2);
3344 assert_eq!(it.indexable(), 3);
3345 assert_eq!(it.idx(0).unwrap(), &[1,2]);
3346 assert_eq!(it.idx(1).unwrap(), &[3,4]);
3347 assert_eq!(it.idx(2).unwrap(), &[5]);
3348 assert_eq!(it.idx(3), None);
3353 fn test_chunksator_0() {
3354 let v = &[1i,2,3,4];
3355 let _it = v.chunks(0);
3359 fn test_move_from() {
3360 let mut a = [1,2,3,4,5];
3362 assert_eq!(a.move_from(b, 0, 3), 3);
3363 assert!(a == [6,7,8,4,5]);
3364 let mut a = [7,2,8,1];
3365 let b = ~[3,1,4,1,5,9];
3366 assert_eq!(a.move_from(b, 0, 6), 4);
3367 assert!(a == [3,1,4,1]);
3368 let mut a = [1,2,3,4];
3369 let b = ~[5,6,7,8,9,0];
3370 assert_eq!(a.move_from(b, 2, 3), 1);
3371 assert!(a == [7,2,3,4]);
3372 let mut a = [1,2,3,4,5];
3373 let b = ~[5,6,7,8,9,0];
3374 assert_eq!(a.mut_slice(2,4).move_from(b,1,6), 2);
3375 assert!(a == [1,2,6,7,5]);
3379 fn test_copy_from() {
3380 let mut a = [1,2,3,4,5];
3382 assert_eq!(a.copy_from(b), 3);
3383 assert!(a == [6,7,8,4,5]);
3384 let mut c = [7,2,8,1];
3385 let d = [3,1,4,1,5,9];
3386 assert_eq!(c.copy_from(d), 4);
3387 assert!(c == [3,1,4,1]);
3391 fn test_reverse_part() {
3392 let mut values = [1,2,3,4,5];
3393 values.mut_slice(1, 4).reverse();
3394 assert!(values == [1,4,3,2,5]);
3399 macro_rules! test_show_vec(
3400 ($x:expr, $x_str:expr) => ({
3401 let (x, x_str) = ($x, $x_str);
3402 assert_eq!(format!("{}", x), x_str);
3403 assert_eq!(format!("{}", x.as_slice()), x_str);
3406 let empty: ~[int] = ~[];
3407 test_show_vec!(empty, ~"[]");
3408 test_show_vec!(~[1], ~"[1]");
3409 test_show_vec!(~[1, 2, 3], ~"[1, 2, 3]");
3410 test_show_vec!(~[~[], ~[1u], ~[1u, 1u]], ~"[[], [1], [1, 1]]");
3414 fn test_vec_default() {
3415 use default::Default;
3418 let v: $ty = Default::default();
3419 assert!(v.is_empty());
3429 fn test_bytes_set_memory() {
3430 use slice::bytes::MutableByteVector;
3431 let mut values = [1u8,2,3,4,5];
3432 values.mut_slice(0,5).set_memory(0xAB);
3433 assert!(values == [0xAB, 0xAB, 0xAB, 0xAB, 0xAB]);
3434 values.mut_slice(2,4).set_memory(0xFF);
3435 assert!(values == [0xAB, 0xAB, 0xFF, 0xFF, 0xAB]);
3440 fn test_overflow_does_not_cause_segfault() {
3442 v.reserve_exact(-1);
3449 fn test_overflow_does_not_cause_segfault_managed() {
3451 let mut v = vec![Rc::new(1)];
3452 v.reserve_exact(-1);
3457 fn test_mut_split_at() {
3458 let mut values = [1u8,2,3,4,5];
3460 let (left, right) = values.mut_split_at(2);
3461 assert!(left.slice(0, left.len()) == [1, 2]);
3462 for p in left.mut_iter() {
3466 assert!(right.slice(0, right.len()) == [3, 4, 5]);
3467 for p in right.mut_iter() {
3472 assert!(values == [2, 3, 5, 6, 7]);
3475 #[deriving(Clone, Eq)]
3479 fn test_iter_zero_sized() {
3480 let mut v = vec![Foo, Foo, Foo];
3481 assert_eq!(v.len(), 3);
3490 for f in v.slice(1, 3).iter() {
3496 for f in v.mut_iter() {
3502 for f in v.move_iter() {
3506 assert_eq!(cnt, 11);
3508 let xs = vec![Foo, Foo, Foo];
3509 assert_eq!(format!("{:?}", xs.slice(0, 2).to_owned()),
3510 ~"~[slice::tests::Foo, slice::tests::Foo]");
3512 let xs: [Foo, ..3] = [Foo, Foo, Foo];
3513 assert_eq!(format!("{:?}", xs.slice(0, 2).to_owned()),
3514 ~"~[slice::tests::Foo, slice::tests::Foo]");
3516 for f in xs.iter() {
3524 fn test_shrink_to_fit() {
3525 let mut xs = vec![0, 1, 2, 3];
3526 for i in range(4, 100) {
3529 assert_eq!(xs.capacity(), 128);
3531 assert_eq!(xs.capacity(), 100);
3532 assert_eq!(xs, range(0, 100).collect::<Vec<_>>());
3536 fn test_starts_with() {
3537 assert!(bytes!("foobar").starts_with(bytes!("foo")));
3538 assert!(!bytes!("foobar").starts_with(bytes!("oob")));
3539 assert!(!bytes!("foobar").starts_with(bytes!("bar")));
3540 assert!(!bytes!("foo").starts_with(bytes!("foobar")));
3541 assert!(!bytes!("bar").starts_with(bytes!("foobar")));
3542 assert!(bytes!("foobar").starts_with(bytes!("foobar")));
3543 let empty: &[u8] = [];
3544 assert!(empty.starts_with(empty));
3545 assert!(!empty.starts_with(bytes!("foo")));
3546 assert!(bytes!("foobar").starts_with(empty));
3550 fn test_ends_with() {
3551 assert!(bytes!("foobar").ends_with(bytes!("bar")));
3552 assert!(!bytes!("foobar").ends_with(bytes!("oba")));
3553 assert!(!bytes!("foobar").ends_with(bytes!("foo")));
3554 assert!(!bytes!("foo").ends_with(bytes!("foobar")));
3555 assert!(!bytes!("bar").ends_with(bytes!("foobar")));
3556 assert!(bytes!("foobar").ends_with(bytes!("foobar")));
3557 let empty: &[u8] = [];
3558 assert!(empty.ends_with(empty));
3559 assert!(!empty.ends_with(bytes!("foo")));
3560 assert!(bytes!("foobar").ends_with(empty));
3564 fn test_shift_ref() {
3565 let mut x: &[int] = [1, 2, 3, 4, 5];
3566 let h = x.shift_ref();
3567 assert_eq!(*h.unwrap(), 1);
3568 assert_eq!(x.len(), 4);
3569 assert_eq!(x[0], 2);
3570 assert_eq!(x[3], 5);
3572 let mut y: &[int] = [];
3573 assert_eq!(y.shift_ref(), None);
3578 let mut x: &[int] = [1, 2, 3, 4, 5];
3579 let h = x.pop_ref();
3580 assert_eq!(*h.unwrap(), 5);
3581 assert_eq!(x.len(), 4);
3582 assert_eq!(x[0], 1);
3583 assert_eq!(x[3], 4);
3585 let mut y: &[int] = [];
3586 assert!(y.pop_ref().is_none());
3590 fn test_mut_splitator() {
3591 let mut xs = [0,1,0,2,3,0,0,4,5,0];
3592 assert_eq!(xs.mut_split(|x| *x == 0).len(), 6);
3593 for slice in xs.mut_split(|x| *x == 0) {
3596 assert!(xs == [0,1,0,3,2,0,0,5,4,0]);
3598 let mut xs = [0,1,0,2,3,0,0,4,5,0,6,7];
3599 for slice in xs.mut_split(|x| *x == 0).take(5) {
3602 assert!(xs == [0,1,0,3,2,0,0,5,4,0,6,7]);
3606 fn test_mut_splitator_rev() {
3607 let mut xs = [1,2,0,3,4,0,0,5,6,0];
3608 for slice in xs.mut_split(|x| *x == 0).rev().take(4) {
3611 assert!(xs == [1,2,0,4,3,0,0,6,5,0]);
3615 fn test_mut_chunks() {
3616 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
3617 for (i, chunk) in v.mut_chunks(3).enumerate() {
3618 for x in chunk.mut_iter() {
3622 let result = [0u8, 0, 0, 1, 1, 1, 2];
3623 assert!(v == result);
3627 fn test_mut_chunks_rev() {
3628 let mut v = [0u8, 1, 2, 3, 4, 5, 6];
3629 for (i, chunk) in v.mut_chunks(3).rev().enumerate() {
3630 for x in chunk.mut_iter() {
3634 let result = [2u8, 2, 2, 1, 1, 1, 0];
3635 assert!(v == result);
3640 fn test_mut_chunks_0() {
3641 let mut v = [1, 2, 3, 4];
3642 let _it = v.mut_chunks(0);
3646 fn test_mut_shift_ref() {
3647 let mut x: &mut [int] = [1, 2, 3, 4, 5];
3648 let h = x.mut_shift_ref();
3649 assert_eq!(*h.unwrap(), 1);
3650 assert_eq!(x.len(), 4);
3651 assert_eq!(x[0], 2);
3652 assert_eq!(x[3], 5);
3654 let mut y: &mut [int] = [];
3655 assert!(y.mut_shift_ref().is_none());
3659 fn test_mut_pop_ref() {
3660 let mut x: &mut [int] = [1, 2, 3, 4, 5];
3661 let h = x.mut_pop_ref();
3662 assert_eq!(*h.unwrap(), 5);
3663 assert_eq!(x.len(), 4);
3664 assert_eq!(x[0], 1);
3665 assert_eq!(x[3], 4);
3667 let mut y: &mut [int] = [];
3668 assert!(y.mut_pop_ref().is_none());
3672 fn test_mut_last() {
3673 let mut x = [1, 2, 3, 4, 5];
3674 let h = x.mut_last();
3675 assert_eq!(*h.unwrap(), 5);
3677 let y: &mut [int] = [];
3678 assert!(y.mut_last().is_none());
3685 use self::test::Bencher;
3689 use rand::{weak_rng, Rng};
3692 fn iterator(b: &mut Bencher) {
3693 // peculiar numbers to stop LLVM from optimising the summation
3695 let v = Vec::from_fn(100, |i| i ^ (i << 1) ^ (i >> 1));
3702 // sum == 11806, to stop dead code elimination.
3703 if sum == 0 {fail!()}
3708 fn mut_iterator(b: &mut Bencher) {
3709 let mut v = Vec::from_elem(100, 0);
3713 for x in v.mut_iter() {
3721 fn add(b: &mut Bencher) {
3722 let xs: &[int] = [5, ..10];
3723 let ys: &[int] = [5, ..10];
3730 fn concat(b: &mut Bencher) {
3731 let xss: Vec<Vec<uint>> = Vec::from_fn(100, |i| range(0, i).collect());
3733 xss.as_slice().concat_vec()
3738 fn connect(b: &mut Bencher) {
3739 let xss: Vec<Vec<uint>> = Vec::from_fn(100, |i| range(0, i).collect());
3741 xss.as_slice().connect_vec(&0)
3746 fn push(b: &mut Bencher) {
3747 let mut vec: Vec<uint> = vec![];
3755 fn starts_with_same_vector(b: &mut Bencher) {
3756 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3758 vec.as_slice().starts_with(vec.as_slice())
3763 fn starts_with_single_element(b: &mut Bencher) {
3764 let vec: Vec<uint> = vec![0];
3766 vec.as_slice().starts_with(vec.as_slice())
3771 fn starts_with_diff_one_element_at_end(b: &mut Bencher) {
3772 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3773 let mut match_vec: Vec<uint> = Vec::from_fn(99, |i| i);
3776 vec.as_slice().starts_with(match_vec.as_slice())
3781 fn ends_with_same_vector(b: &mut Bencher) {
3782 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3784 vec.as_slice().ends_with(vec.as_slice())
3789 fn ends_with_single_element(b: &mut Bencher) {
3790 let vec: Vec<uint> = vec![0];
3792 vec.as_slice().ends_with(vec.as_slice())
3797 fn ends_with_diff_one_element_at_beginning(b: &mut Bencher) {
3798 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3799 let mut match_vec: Vec<uint> = Vec::from_fn(100, |i| i);
3800 match_vec.as_mut_slice()[0] = 200;
3802 vec.as_slice().starts_with(match_vec.as_slice())
3807 fn contains_last_element(b: &mut Bencher) {
3808 let vec: Vec<uint> = Vec::from_fn(100, |i| i);
3815 fn zero_1kb_from_elem(b: &mut Bencher) {
3817 Vec::from_elem(1024, 0u8)
3822 fn zero_1kb_set_memory(b: &mut Bencher) {
3824 let mut v: Vec<uint> = Vec::with_capacity(1024);
3826 let vp = v.as_mut_ptr();
3827 ptr::set_memory(vp, 0, 1024);
3835 fn zero_1kb_fixed_repeat(b: &mut Bencher) {
3842 fn zero_1kb_loop_set(b: &mut Bencher) {
3844 let mut v: Vec<uint> = Vec::with_capacity(1024);
3848 for i in range(0u, 1024) {
3855 fn zero_1kb_mut_iter(b: &mut Bencher) {
3857 let mut v = Vec::with_capacity(1024);
3861 for x in v.mut_iter() {
3869 fn random_inserts(b: &mut Bencher) {
3870 let mut rng = weak_rng();
3872 let mut v = Vec::from_elem(30, (0u, 0u));
3873 for _ in range(0, 100) {
3875 v.insert(rng.gen::<uint>() % (l + 1),
3881 fn random_removes(b: &mut Bencher) {
3882 let mut rng = weak_rng();
3884 let mut v = Vec::from_elem(130, (0u, 0u));
3885 for _ in range(0, 100) {
3887 v.remove(rng.gen::<uint>() % l);
3893 fn sort_random_small(b: &mut Bencher) {
3894 let mut rng = weak_rng();
3896 let mut v = rng.gen_vec::<u64>(5);
3897 v.as_mut_slice().sort();
3899 b.bytes = 5 * mem::size_of::<u64>() as u64;
3903 fn sort_random_medium(b: &mut Bencher) {
3904 let mut rng = weak_rng();
3906 let mut v = rng.gen_vec::<u64>(100);
3907 v.as_mut_slice().sort();
3909 b.bytes = 100 * mem::size_of::<u64>() as u64;
3913 fn sort_random_large(b: &mut Bencher) {
3914 let mut rng = weak_rng();
3916 let mut v = rng.gen_vec::<u64>(10000);
3917 v.as_mut_slice().sort();
3919 b.bytes = 10000 * mem::size_of::<u64>() as u64;
3923 fn sort_sorted(b: &mut Bencher) {
3924 let mut v = Vec::from_fn(10000, |i| i);
3928 b.bytes = (v.len() * mem::size_of_val(v.get(0))) as u64;
3931 type BigSortable = (u64,u64,u64,u64);
3934 fn sort_big_random_small(b: &mut Bencher) {
3935 let mut rng = weak_rng();
3937 let mut v = rng.gen_vec::<BigSortable>(5);
3940 b.bytes = 5 * mem::size_of::<BigSortable>() as u64;
3944 fn sort_big_random_medium(b: &mut Bencher) {
3945 let mut rng = weak_rng();
3947 let mut v = rng.gen_vec::<BigSortable>(100);
3950 b.bytes = 100 * mem::size_of::<BigSortable>() as u64;
3954 fn sort_big_random_large(b: &mut Bencher) {
3955 let mut rng = weak_rng();
3957 let mut v = rng.gen_vec::<BigSortable>(10000);
3960 b.bytes = 10000 * mem::size_of::<BigSortable>() as u64;
3964 fn sort_big_sorted(b: &mut Bencher) {
3965 let mut v = Vec::from_fn(10000u, |i| (i, i, i, i));
3969 b.bytes = (v.len() * mem::size_of_val(v.get(0))) as u64;