diff options
Diffstat (limited to 'src/libstd/vec.rs')
| -rw-r--r-- | src/libstd/vec.rs | 523 |
1 files changed, 98 insertions, 425 deletions
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index d8424f4a29e..6137b589bdb 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -1066,138 +1066,12 @@ impl<'self, T:Copy> VectorVector<T> for &'self [&'self [T]] { } } -/** - * Reduces a vector from left to right. - * - * # Arguments - * * `z` - initial accumulator value - * * `v` - vector to iterate over - * * `p` - a closure to operate on vector elements - * - * # Examples - * - * Sum all values in the vector [1, 2, 3]: - * - * ~~~ {.rust} - * vec::foldl(0, [1, 2, 3], |a, b| a + *b); - * ~~~ - * - */ -pub fn foldl<'a, T, U>(z: T, v: &'a [U], p: &fn(t: T, u: &'a U) -> T) -> T { - let mut accum = z; - let mut i = 0; - let l = v.len(); - while i < l { - // Use a while loop so that liveness analysis can handle moving - // the accumulator. - accum = p(accum, &v[i]); - i += 1; - } - accum -} - -/** - * Reduces a vector from right to left. Note that the argument order is - * reversed compared to `foldl` to reflect the order they are provided to - * the closure. - * - * # Arguments - * * `v` - vector to iterate over - * * `z` - initial accumulator value - * * `p` - a closure to do operate on vector elements - * - * # Examples - * - * Sum all values in the vector [1, 2, 3]: - * - * ~~~ {.rust} - * vec::foldr([1, 2, 3], 0, |a, b| a + *b); - * ~~~ - * - */ -pub fn foldr<'a, T, U>(v: &'a [T], mut z: U, p: &fn(t: &'a T, u: U) -> U) -> U { - let mut i = v.len(); - while i > 0 { - i -= 1; - z = p(&v[i], z); - } - return z; -} - -/** - * Return true if a predicate matches any elements - * - * If the vector contains no elements then false is returned. - */ -pub fn any<T>(v: &[T], f: &fn(t: &T) -> bool) -> bool { - for each(v) |elem| { if f(elem) { return true; } } - false -} - -/** - * Return true if a predicate matches any elements in both vectors. - * - * If the vectors contains no elements then false is returned. - */ -pub fn any2<T, U>(v0: &[T], v1: &[U], - f: &fn(a: &T, b: &U) -> bool) -> bool { - let v0_len = len(v0); - let v1_len = len(v1); - let mut i = 0u; - while i < v0_len && i < v1_len { - if f(&v0[i], &v1[i]) { return true; }; - i += 1u; - } - false -} - -/** - * Return true if a predicate matches all elements - * - * If the vector contains no elements then true is returned. - */ -pub fn all<T>(v: &[T], f: &fn(t: &T) -> bool) -> bool { - for each(v) |elem| { if !f(elem) { return false; } } - true -} - -/** - * Return true if a predicate matches all elements - * - * If the vector contains no elements then true is returned. - */ -pub fn alli<T>(v: &[T], f: &fn(uint, t: &T) -> bool) -> bool { - for eachi(v) |i, elem| { if !f(i, elem) { return false; } } - true -} - -/** - * Return true if a predicate matches all elements in both vectors. - * - * If the vectors are not the same size then false is returned. - */ -pub fn all2<T, U>(v0: &[T], v1: &[U], - f: &fn(t: &T, u: &U) -> bool) -> bool { - let v0_len = len(v0); - if v0_len != len(v1) { return false; } - let mut i = 0u; - while i < v0_len { if !f(&v0[i], &v1[i]) { return false; }; i += 1u; } - true -} - /// Return true if a vector contains an element with the given value pub fn contains<T:Eq>(v: &[T], x: &T) -> bool { for each(v) |elt| { if *x == *elt { return true; } } false } -/// Returns the number of elements that are equal to a given value -pub fn count<T:Eq>(v: &[T], x: &T) -> uint { - let mut cnt = 0u; - for each(v) |elt| { if *x == *elt { cnt += 1u; } } - cnt -} - /** * Search for the first element that matches a given predicate * @@ -1599,34 +1473,6 @@ pub fn eachi<'r,T>(v: &'r [T], f: &fn(uint, v: &'r T) -> bool) -> bool { } /** - * Iterates over a vector's elements in reverse - * - * Return true to continue, false to break. - */ -#[inline(always)] -pub fn each_reverse<'r,T>(v: &'r [T], blk: &fn(v: &'r T) -> bool) -> bool { - eachi_reverse(v, |_i, v| blk(v)) -} - -/** - * Iterates over a vector's elements and indices in reverse - * - * Return true to continue, false to break. - */ -#[inline(always)] -pub fn eachi_reverse<'r,T>(v: &'r [T], - blk: &fn(i: uint, v: &'r T) -> bool) -> bool { - let mut i = v.len(); - while i > 0 { - i -= 1; - if !blk(i, &v[i]) { - return false; - } - } - return true; -} - -/** * Iterate over all permutations of vector `v`. * * Permutations are produced in lexicographic order with respect to the order @@ -1964,6 +1810,7 @@ impl<'self,T:Copy> CopyableVector<T> for &'self [T] { pub trait ImmutableVector<'self, T> { fn slice(&self, start: uint, end: uint) -> &'self [T]; fn iter(self) -> VecIterator<'self, T>; + fn rev_iter(self) -> VecRevIterator<'self, T>; fn head(&self) -> &'self T; fn head_opt(&self) -> Option<&'self T>; fn tail(&self) -> &'self [T]; @@ -1974,13 +1821,9 @@ pub trait ImmutableVector<'self, T> { fn last_opt(&self) -> Option<&'self T>; fn position(&self, f: &fn(t: &T) -> bool) -> Option<uint>; fn rposition(&self, f: &fn(t: &T) -> bool) -> Option<uint>; - fn each_reverse(&self, blk: &fn(&T) -> bool) -> bool; - fn eachi_reverse(&self, blk: &fn(uint, &T) -> bool) -> bool; - fn foldr<'a, U>(&'a self, z: U, p: &fn(t: &'a T, u: U) -> U) -> U; fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U]; fn mapi<U>(&self, f: &fn(uint, t: &T) -> U) -> ~[U]; fn map_r<U>(&self, f: &fn(x: &T) -> U) -> ~[U]; - fn alli(&self, f: &fn(uint, t: &T) -> bool) -> bool; fn flat_map<U>(&self, f: &fn(t: &T) -> ~[U]) -> ~[U]; fn filter_mapped<U:Copy>(&self, f: &fn(t: &T) -> Option<U>) -> ~[U]; unsafe fn unsafe_ref(&self, index: uint) -> *T; @@ -2002,6 +1845,15 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] { lifetime: cast::transmute(p)} } } + #[inline] + fn rev_iter(self) -> VecRevIterator<'self, T> { + unsafe { + let p = vec::raw::to_ptr(self); + VecRevIterator{ptr: p.offset(self.len() - 1), + end: p.offset(-1), + lifetime: cast::transmute(p)} + } + } /// Returns the first element of a vector, failing if the vector is empty. #[inline] @@ -2059,24 +1911,6 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] { rposition(*self, f) } - /// Iterates over a vector's elements in reverse. - #[inline] - fn each_reverse(&self, blk: &fn(&T) -> bool) -> bool { - each_reverse(*self, blk) - } - - /// Iterates over a vector's elements and indices in reverse. - #[inline] - fn eachi_reverse(&self, blk: &fn(uint, &T) -> bool) -> bool { - eachi_reverse(*self, blk) - } - - /// Reduce a vector from right to left - #[inline] - fn foldr<'a, U>(&'a self, z: U, p: &fn(t: &'a T, u: U) -> U) -> U { - foldr(*self, z, p) - } - /// Apply a function to each element of a vector and return the results #[inline] fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U] { map(*self, f) } @@ -2101,14 +1935,6 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] { } /** - * Returns true if the function returns true for all elements. - * - * If the vector is empty, true is returned. - */ - fn alli(&self, f: &fn(uint, t: &T) -> bool) -> bool { - alli(*self, f) - } - /** * Apply a function to each element of a vector and return a concatenation * of each result vector */ @@ -2350,7 +2176,8 @@ impl<T:Eq> OwnedEqVector<T> for ~[T] { #[allow(missing_doc)] pub trait MutableVector<'self, T> { fn mut_slice(self, start: uint, end: uint) -> &'self mut [T]; - fn mut_iter(self) -> MutVecIterator<'self, T>; + fn mut_iter(self) -> VecMutIterator<'self, T>; + fn mut_rev_iter(self) -> VecMutRevIterator<'self, T>; unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T; unsafe fn unsafe_set(&self, index: uint, val: T); @@ -2363,14 +2190,23 @@ impl<'self,T> MutableVector<'self, T> for &'self mut [T] { } #[inline] - fn mut_iter(self) -> MutVecIterator<'self, T> { + fn mut_iter(self) -> VecMutIterator<'self, T> { unsafe { let p = vec::raw::to_mut_ptr(self); - MutVecIterator{ptr: p, end: p.offset(self.len()), + VecMutIterator{ptr: p, end: p.offset(self.len()), lifetime: cast::transmute(p)} } } + fn mut_rev_iter(self) -> VecMutRevIterator<'self, T> { + unsafe { + let p = vec::raw::to_mut_ptr(self); + VecMutRevIterator{ptr: p.offset(self.len() - 1), + end: p.offset(-1), + lifetime: cast::transmute(p)} + } + } + #[inline(always)] unsafe fn unsafe_mut_ref(&self, index: uint) -> *mut T { let pair_ptr: &(*mut T, uint) = transmute(self); @@ -2872,52 +2708,69 @@ impl<A:Clone> Clone for ~[A] { } } -/// An external iterator for vectors (use with the std::iterator module) +macro_rules! iterator { + /* FIXME: #4375 Cannot attach documentation/attributes to a macro generated struct. + (struct $name:ident -> $ptr:ty, $elem:ty) => { + pub struct $name<'self, T> { + priv ptr: $ptr, + priv end: $ptr, + priv lifetime: $elem // FIXME: #5922 + } + };*/ + (impl $name:ident -> $elem:ty, $step:expr) => { + // could be implemented with &[T] with .slice(), but this avoids bounds checks + impl<'self, T> Iterator<$elem> for $name<'self, T> { + #[inline] + fn next(&mut self) -> Option<$elem> { + unsafe { + if self.ptr == self.end { + None + } else { + let old = self.ptr; + self.ptr = self.ptr.offset($step); + Some(cast::transmute(old)) + } + } + } + } + } +} + +//iterator!{struct VecIterator -> *T, &'self T} +/// An iterator for iterating over a vector pub struct VecIterator<'self, T> { priv ptr: *T, priv end: *T, priv lifetime: &'self T // FIXME: #5922 } +iterator!{impl VecIterator -> &'self T, 1} -// could be implemented with &[T] with .slice(), but this avoids bounds checks -impl<'self, T> Iterator<&'self T> for VecIterator<'self, T> { - #[inline] - fn next(&mut self) -> Option<&'self T> { - unsafe { - if self.ptr == self.end { - None - } else { - let old = self.ptr; - self.ptr = self.ptr.offset(1); - Some(cast::transmute(old)) - } - } - } +//iterator!{struct VecRevIterator -> *T, &'self T} +/// An iterator for iterating over a vector in reverse +pub struct VecRevIterator<'self, T> { + priv ptr: *T, + priv end: *T, + priv lifetime: &'self T // FIXME: #5922 } +iterator!{impl VecRevIterator -> &'self T, -1} -/// An external iterator for vectors with the possibility of mutating -/// elements. (use with the std::iterator module) -pub struct MutVecIterator<'self, T> { +//iterator!{struct VecMutIterator -> *mut T, &'self mut T} +/// An iterator for mutating the elements of a vector +pub struct VecMutIterator<'self, T> { priv ptr: *mut T, priv end: *mut T, priv lifetime: &'self mut T // FIXME: #5922 } +iterator!{impl VecMutIterator -> &'self mut T, 1} -// could be implemented with &[T] with .slice(), but this avoids bounds checks -impl<'self, T> Iterator<&'self mut T> for MutVecIterator<'self, T> { - #[inline] - fn next(&mut self) -> Option<&'self mut T> { - unsafe { - if self.ptr == self.end { - None - } else { - let old = self.ptr; - self.ptr = self.ptr.offset(1); - Some(cast::transmute(old)) - } - } - } +//iterator!{struct VecMutRevIterator -> *mut T, &'self mut T} +/// An iterator for mutating the elements of a vector in reverse +pub struct VecMutRevIterator<'self, T> { + priv ptr: *mut T, + priv end: *mut T, + priv lifetime: &'self mut T // FIXME: #5922 } +iterator!{impl VecMutRevIterator -> &'self mut T, -1} impl<T> FromIter<T> for ~[T]{ #[inline(always)] @@ -3468,39 +3321,6 @@ mod tests { } #[test] - fn test_foldl() { - // Test on-stack fold. - let mut v = ~[1u, 2u, 3u]; - let mut sum = foldl(0u, v, add); - assert_eq!(sum, 6u); - - // Test on-heap fold. - v = ~[1u, 2u, 3u, 4u, 5u]; - sum = foldl(0u, v, add); - assert_eq!(sum, 15u); - } - - #[test] - fn test_foldl2() { - fn sub(a: int, b: &int) -> int { - a - *b - } - let v = ~[1, 2, 3, 4]; - let sum = foldl(0, v, sub); - assert_eq!(sum, -10); - } - - #[test] - fn test_foldr() { - fn sub(a: &int, b: int) -> int { - *a - b - } - let v = ~[1, 2, 3, 4]; - let sum = foldr(v, 0, sub); - assert_eq!(sum, -2); - } - - #[test] fn test_each_empty() { for each::<int>([]) |_v| { fail!(); // should never be executed @@ -3528,51 +3348,14 @@ mod tests { } #[test] - fn test_each_reverse_empty() { - let v: ~[int] = ~[]; - for v.each_reverse |_v| { - fail!(); // should never execute - } - } - - #[test] - fn test_each_reverse_nonempty() { - let mut i = 0; - for each_reverse([1, 2, 3]) |v| { - if i == 0 { assert!(*v == 3); } - i += *v - } - assert_eq!(i, 6); - } - - #[test] - fn test_eachi_reverse() { - let mut i = 0; - for eachi_reverse([0, 1, 2]) |j, v| { - if i == 0 { assert!(*v == 2); } - assert_eq!(j, *v as uint); - i += *v; - } - assert_eq!(i, 3); - } - - #[test] - fn test_eachi_reverse_empty() { - let v: ~[int] = ~[]; - for v.eachi_reverse |_i, _v| { - fail!(); // should never execute - } - } - - #[test] fn test_each_ret_len0() { - let mut a0 : [int, .. 0] = []; + let a0 : [int, .. 0] = []; assert_eq!(each(a0, |_p| fail!()), true); } #[test] fn test_each_ret_len1() { - let mut a1 = [17]; + let a1 = [17]; assert_eq!(each(a1, |_p| true), true); assert_eq!(each(a1, |_p| false), false); } @@ -3601,33 +3384,6 @@ mod tests { } #[test] - fn test_any_and_all() { - assert!(any([1u, 2u, 3u], is_three)); - assert!(!any([0u, 1u, 2u], is_three)); - assert!(any([1u, 2u, 3u, 4u, 5u], is_three)); - assert!(!any([1u, 2u, 4u, 5u, 6u], is_three)); - - assert!(all([3u, 3u, 3u], is_three)); - assert!(!all([3u, 3u, 2u], is_three)); - assert!(all([3u, 3u, 3u, 3u, 3u], is_three)); - assert!(!all([3u, 3u, 0u, 1u, 2u], is_three)); - } - - #[test] - fn test_any2_and_all2() { - - assert!(any2([2u, 4u, 6u], [2u, 4u, 6u], is_equal)); - assert!(any2([1u, 2u, 3u], [4u, 5u, 3u], is_equal)); - assert!(!any2([1u, 2u, 3u], [4u, 5u, 6u], is_equal)); - assert!(any2([2u, 4u, 6u], [2u, 4u], is_equal)); - - assert!(all2([2u, 4u, 6u], [2u, 4u, 6u], is_equal)); - assert!(!all2([1u, 2u, 3u], [4u, 5u, 3u], is_equal)); - assert!(!all2([1u, 2u, 3u], [4u, 5u, 6u], is_equal)); - assert!(!all2([2u, 4u, 6u], [2u, 4u], is_equal)); - } - - #[test] fn test_zip_unzip() { let v1 = ~[1, 2, 3]; let v2 = ~[4, 5, 6]; @@ -4375,113 +4131,6 @@ mod tests { #[ignore(windows)] #[should_fail] #[allow(non_implicitly_copyable_typarams)] - fn test_foldl_fail() { - let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; - let mut i = 0; - do foldl((~0, @0), v) |_a, _b| { - if i == 2 { - fail!() - } - i += 0; - (~0, @0) - }; - } - - #[test] - #[ignore(windows)] - #[should_fail] - #[allow(non_implicitly_copyable_typarams)] - fn test_foldr_fail() { - let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; - let mut i = 0; - do foldr(v, (~0, @0)) |_a, _b| { - if i == 2 { - fail!() - } - i += 0; - (~0, @0) - }; - } - - #[test] - #[ignore(windows)] - #[should_fail] - fn test_any_fail() { - let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; - let mut i = 0; - do any(v) |_elt| { - if i == 2 { - fail!() - } - i += 0; - false - }; - } - - #[test] - #[ignore(windows)] - #[should_fail] - fn test_any2_fail() { - let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; - let mut i = 0; - do any(v) |_elt| { - if i == 2 { - fail!() - } - i += 0; - false - }; - } - - #[test] - #[ignore(windows)] - #[should_fail] - fn test_all_fail() { - let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; - let mut i = 0; - do all(v) |_elt| { - if i == 2 { - fail!() - } - i += 0; - true - }; - } - - #[test] - #[ignore(windows)] - #[should_fail] - fn test_alli_fail() { - let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; - let mut i = 0; - do alli(v) |_i, _elt| { - if i == 2 { - fail!() - } - i += 0; - true - }; - } - - #[test] - #[ignore(windows)] - #[should_fail] - fn test_all2_fail() { - let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; - let mut i = 0; - do all2(v, v) |_elt1, _elt2| { - if i == 2 { - fail!() - } - i += 0; - true - }; - } - - #[test] - #[ignore(windows)] - #[should_fail] - #[allow(non_implicitly_copyable_typarams)] fn test_find_fail() { let v = [(~0, @0), (~0, @0), (~0, @0), (~0, @0)]; let mut i = 0; @@ -4643,6 +4292,30 @@ mod tests { } #[test] + fn test_rev_iterator() { + use iterator::*; + + let xs = [1, 2, 5, 10, 11]; + let ys = [11, 10, 5, 2, 1]; + let mut i = 0; + for xs.rev_iter().advance |&x| { + assert_eq!(x, ys[i]); + i += 1; + } + assert_eq!(i, 5); + } + + #[test] + fn test_mut_rev_iterator() { + use iterator::*; + let mut xs = [1u, 2, 3, 4, 5]; + for xs.mut_rev_iter().enumerate().advance |(i,x)| { + *x += i; + } + assert_eq!(xs, [5, 5, 5, 5, 5]) + } + + #[test] fn test_reverse_part() { let mut values = [1,2,3,4,5]; reverse_part(values,1,4); |