diff options
Diffstat (limited to 'src/libstd')
| -rw-r--r-- | src/libstd/hashmap.rs | 26 | ||||
| -rw-r--r-- | src/libstd/iterator.rs | 306 | ||||
| -rw-r--r-- | src/libstd/str.rs | 27 | ||||
| -rw-r--r-- | src/libstd/trie.rs | 26 | ||||
| -rw-r--r-- | src/libstd/vec.rs | 33 |
5 files changed, 355 insertions, 63 deletions
diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs index a9a11b611d6..e43293f3212 100644 --- a/src/libstd/hashmap.rs +++ b/src/libstd/hashmap.rs @@ -19,7 +19,7 @@ use container::{Container, Mutable, Map, MutableMap, Set, MutableSet}; use clone::Clone; use cmp::{Eq, Equiv}; use hash::Hash; -use iterator::{Iterator, IteratorUtil, FromIterator, Chain}; +use iterator::{Iterator, IteratorUtil, FromIterator, Extendable, Chain}; use num; use option::{None, Option, Some}; use rand::RngUtil; @@ -618,15 +618,19 @@ impl<K> Iterator<K> for HashSetConsumeIterator<K> { } impl<K: Eq + Hash, V, T: Iterator<(K, V)>> FromIterator<(K, V), T> for HashMap<K, V> { - pub fn from_iterator(iter: &mut T) -> HashMap<K, V> { + fn from_iterator(iter: &mut T) -> HashMap<K, V> { let (lower, _) = iter.size_hint(); let mut map = HashMap::with_capacity(lower); + map.extend(iter); + map + } +} +impl<K: Eq + Hash, V, T: Iterator<(K, V)>> Extendable<(K, V), T> for HashMap<K, V> { + fn extend(&mut self, iter: &mut T) { for iter.advance |(k, v)| { - map.insert(k, v); + self.insert(k, v); } - - map } } @@ -771,15 +775,19 @@ impl<T:Hash + Eq> HashSet<T> { } impl<K: Eq + Hash, T: Iterator<K>> FromIterator<K, T> for HashSet<K> { - pub fn from_iterator(iter: &mut T) -> HashSet<K> { + fn from_iterator(iter: &mut T) -> HashSet<K> { let (lower, _) = iter.size_hint(); let mut set = HashSet::with_capacity(lower); + set.extend(iter); + set + } +} +impl<K: Eq + Hash, T: Iterator<K>> Extendable<K, T> for HashSet<K> { + fn extend(&mut self, iter: &mut T) { for iter.advance |k| { - set.insert(k); + self.insert(k); } - - set } } diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs index 6828de51622..9fe865333a2 100644 --- a/src/libstd/iterator.rs +++ b/src/libstd/iterator.rs @@ -529,7 +529,7 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T { #[inline] fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U) -> FlatMap<'r, A, T, U> { - FlatMap{iter: self, f: f, subiter: None } + FlatMap{iter: self, f: f, frontiter: None, backiter: None } } // FIXME: #5898: should be called `peek` @@ -811,6 +811,30 @@ impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> { } } +impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> { + #[inline] + fn indexable(&self) -> uint { + if self.orig.indexable() > 0 { + uint::max_value + } else { + 0 + } + } + + #[inline] + fn idx(&self, index: uint) -> Option<A> { + let liter = self.iter.indexable(); + let lorig = self.orig.indexable(); + if lorig == 0 { + None + } else if index < liter { + self.iter.idx(index) + } else { + self.orig.idx((index - liter) % lorig) + } + } +} + /// An iterator which strings two iterators together #[deriving(Clone)] pub struct Chain<T, U> { @@ -924,20 +948,44 @@ impl<A, B, T: Iterator<A>, U: Iterator<B>> Iterator<(A, B)> for Zip<T, U> { } } +impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator<B>> +RandomAccessIterator<(A, B)> for Zip<T, U> { + #[inline] + fn indexable(&self) -> uint { + cmp::min(self.a.indexable(), self.b.indexable()) + } + + #[inline] + fn idx(&self, index: uint) -> Option<(A, B)> { + match (self.a.idx(index), self.b.idx(index)) { + (Some(x), Some(y)) => Some((x, y)), + _ => None + } + } +} + /// An iterator which maps the values of `iter` with `f` pub struct Map<'self, A, B, T> { priv iter: T, priv f: &'self fn(A) -> B } -impl<'self, A, B, T: Iterator<A>> Iterator<B> for Map<'self, A, B, T> { +impl<'self, A, B, T> Map<'self, A, B, T> { #[inline] - fn next(&mut self) -> Option<B> { - match self.iter.next() { + fn do_map(&self, elt: Option<A>) -> Option<B> { + match elt { Some(a) => Some((self.f)(a)), _ => None } } +} + +impl<'self, A, B, T: Iterator<A>> Iterator<B> for Map<'self, A, B, T> { + #[inline] + fn next(&mut self) -> Option<B> { + let next = self.iter.next(); + self.do_map(next) + } #[inline] fn size_hint(&self) -> (uint, Option<uint>) { @@ -949,10 +997,21 @@ impl<'self, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator<B> for Map<'self, A, B, T> { #[inline] fn next_back(&mut self) -> Option<B> { - match self.iter.next_back() { - Some(a) => Some((self.f)(a)), - _ => None - } + let next = self.iter.next_back(); + self.do_map(next) + } +} + +impl<'self, A, B, T: RandomAccessIterator<A>> RandomAccessIterator<B> +for Map<'self, A, B, T> { + #[inline] + fn indexable(&self) -> uint { + self.iter.indexable() + } + + #[inline] + fn idx(&self, index: uint) -> Option<B> { + self.do_map(self.iter.idx(index)) } } @@ -1069,6 +1128,21 @@ impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> { } } +impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> { + #[inline] + fn indexable(&self) -> uint { + self.iter.indexable() + } + + #[inline] + fn idx(&self, index: uint) -> Option<(uint, A)> { + match self.iter.idx(index) { + Some(a) => Some((self.count + index, a)), + _ => None, + } + } +} + /// An iterator which rejects elements while `predicate` is true pub struct SkipWhile<'self, A, T> { priv iter: T, @@ -1189,6 +1263,27 @@ impl<A, T: Iterator<A>> Iterator<A> for Skip<T> { } } +impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> { + #[inline] + fn indexable(&self) -> uint { + let N = self.iter.indexable(); + if N < self.n { + 0 + } else { + N - self.n + } + } + + #[inline] + fn idx(&self, index: uint) -> Option<A> { + if index >= self.indexable() { + None + } else { + self.iter.idx(index + self.n) + } + } +} + /// An iterator which only iterates over the first `n` iterations of `iter`. #[deriving(Clone)] pub struct Take<T> { @@ -1223,6 +1318,23 @@ impl<A, T: Iterator<A>> Iterator<A> for Take<T> { } } +impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> { + #[inline] + fn indexable(&self) -> uint { + cmp::min(self.iter.indexable(), self.n) + } + + #[inline] + fn idx(&self, index: uint) -> Option<A> { + if index >= self.n { + None + } else { + self.iter.idx(index) + } + } +} + + /// An iterator to maintain state while iterating another iterator pub struct Scan<'self, A, B, T, St> { priv iter: T, @@ -1251,7 +1363,8 @@ impl<'self, A, B, T: Iterator<A>, St> Iterator<B> for Scan<'self, A, B, T, St> { pub struct FlatMap<'self, A, T, U> { priv iter: T, priv f: &'self fn(A) -> U, - priv subiter: Option<U>, + priv frontiter: Option<U>, + priv backiter: Option<U>, } impl<'self, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for @@ -1259,14 +1372,45 @@ impl<'self, A, T: Iterator<A>, B, U: Iterator<B>> Iterator<B> for #[inline] fn next(&mut self) -> Option<B> { loop { - for self.subiter.mut_iter().advance |inner| { + for self.frontiter.mut_iter().advance |inner| { for inner.advance |x| { return Some(x) } } match self.iter.next().map_consume(|x| (self.f)(x)) { - None => return None, - next => self.subiter = next, + None => return self.backiter.chain_mut_ref(|it| it.next()), + next => self.frontiter = next, + } + } + } + + #[inline] + fn size_hint(&self) -> (uint, Option<uint>) { + let (flo, fhi) = self.frontiter.map_default((0, Some(0)), |it| it.size_hint()); + let (blo, bhi) = self.backiter.map_default((0, Some(0)), |it| it.size_hint()); + match (self.iter.size_hint(), fhi, bhi) { + ((0, Some(0)), Some(a), Some(b)) => (flo + blo, Some(a + b)), + _ => (flo + blo, None) + } + } +} + +impl<'self, + A, T: DoubleEndedIterator<A>, + B, U: DoubleEndedIterator<B>> DoubleEndedIterator<B> + for FlatMap<'self, A, T, U> { + #[inline] + fn next_back(&mut self) -> Option<B> { + loop { + for self.backiter.mut_iter().advance |inner| { + match inner.next_back() { + None => (), + y => return y + } + } + match self.iter.next_back().map_consume(|x| (self.f)(x)) { + None => return self.frontiter.chain_mut_ref(|it| it.next_back()), + next => self.backiter = next, } } } @@ -1279,17 +1423,23 @@ pub struct Peek<'self, A, T> { priv f: &'self fn(&A) } -impl<'self, A, T: Iterator<A>> Iterator<A> for Peek<'self, A, T> { +impl<'self, A, T> Peek<'self, A, T> { #[inline] - fn next(&mut self) -> Option<A> { - let next = self.iter.next(); - - match next { + fn do_peek(&self, elt: Option<A>) -> Option<A> { + match elt { Some(ref a) => (self.f)(a), None => () } - next + elt + } +} + +impl<'self, A, T: Iterator<A>> Iterator<A> for Peek<'self, A, T> { + #[inline] + fn next(&mut self) -> Option<A> { + let next = self.iter.next(); + self.do_peek(next) } #[inline] @@ -1302,13 +1452,19 @@ impl<'self, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Peek<'self, #[inline] fn next_back(&mut self) -> Option<A> { let next = self.iter.next_back(); + self.do_peek(next) + } +} - match next { - Some(ref a) => (self.f)(a), - None => () - } +impl<'self, A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Peek<'self, A, T> { + #[inline] + fn indexable(&self) -> uint { + self.iter.indexable() + } - next + #[inline] + fn idx(&self, index: uint) -> Option<A> { + self.do_peek(self.iter.idx(index)) } } @@ -1376,6 +1532,7 @@ mod tests { use super::*; use prelude::*; + use cmp; use uint; #[test] @@ -1768,6 +1925,43 @@ mod tests { assert_eq!(it.next_back(), None) } + #[cfg(test)] + fn check_randacc_iter<A: Eq, T: Clone + RandomAccessIterator<A>>(a: T, len: uint) + { + let mut b = a.clone(); + assert_eq!(len, b.indexable()); + let mut n = 0; + for a.enumerate().advance |(i, elt)| { + assert_eq!(Some(elt), b.idx(i)); + n += 1; + } + assert_eq!(n, len); + assert_eq!(None, b.idx(n)); + // call recursively to check after picking off an element + if len > 0 { + b.next(); + check_randacc_iter(b, len-1); + } + } + + + #[test] + fn test_double_ended_flat_map() { + let u = [0u,1]; + let v = [5,6,7,8]; + let mut it = u.iter().flat_map_(|x| v.slice(*x, v.len()).iter()); + assert_eq!(it.next_back().unwrap(), &8); + assert_eq!(it.next().unwrap(), &5); + assert_eq!(it.next_back().unwrap(), &7); + assert_eq!(it.next_back().unwrap(), &6); + assert_eq!(it.next_back().unwrap(), &8); + assert_eq!(it.next().unwrap(), &6); + assert_eq!(it.next_back().unwrap(), &7); + assert_eq!(it.next_back(), None); + assert_eq!(it.next(), None); + assert_eq!(it.next_back(), None); + } + #[test] fn test_random_access_chain() { let xs = [1, 2, 3, 4, 5]; @@ -1785,5 +1979,71 @@ mod tests { assert_eq!(it.idx(0).unwrap(), &3); assert_eq!(it.idx(4).unwrap(), &9); assert!(it.idx(6).is_none()); + + check_randacc_iter(it, xs.len() + ys.len() - 3); + } + + #[test] + fn test_random_access_enumerate() { + let xs = [1, 2, 3, 4, 5]; + check_randacc_iter(xs.iter().enumerate(), xs.len()); + } + + #[test] + fn test_random_access_zip() { + let xs = [1, 2, 3, 4, 5]; + let ys = [7, 9, 11]; + check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len())); + } + + #[test] + fn test_random_access_take() { + let xs = [1, 2, 3, 4, 5]; + let empty: &[int] = []; + check_randacc_iter(xs.iter().take_(3), 3); + check_randacc_iter(xs.iter().take_(20), xs.len()); + check_randacc_iter(xs.iter().take_(0), 0); + check_randacc_iter(empty.iter().take_(2), 0); + } + + #[test] + fn test_random_access_skip() { + let xs = [1, 2, 3, 4, 5]; + let empty: &[int] = []; + check_randacc_iter(xs.iter().skip(2), xs.len() - 2); + check_randacc_iter(empty.iter().skip(2), 0); + } + + #[test] + fn test_random_access_peek() { + let xs = [1, 2, 3, 4, 5]; + + // test .transform and .peek_ that don't implement Clone + let it = xs.iter().peek_(|_| {}); + assert_eq!(xs.len(), it.indexable()); + for xs.iter().enumerate().advance |(i, elt)| { + assert_eq!(Some(elt), it.idx(i)); + } + + } + + #[test] + fn test_random_access_transform() { + let xs = [1, 2, 3, 4, 5]; + + // test .transform and .peek_ that don't implement Clone + let it = xs.iter().transform(|x| *x); + assert_eq!(xs.len(), it.indexable()); + for xs.iter().enumerate().advance |(i, elt)| { + assert_eq!(Some(*elt), it.idx(i)); + } + } + + #[test] + fn test_random_access_cycle() { + let xs = [1, 2, 3, 4, 5]; + let empty: &[int] = []; + check_randacc_iter(xs.iter().cycle().take_(27), 27); + check_randacc_iter(empty.iter().cycle(), 0); } } diff --git a/src/libstd/str.rs b/src/libstd/str.rs index 2aa5f586dd8..fff859321fb 100644 --- a/src/libstd/str.rs +++ b/src/libstd/str.rs @@ -23,7 +23,8 @@ use char::Char; use clone::Clone; use container::{Container, Mutable}; use iter::Times; -use iterator::{Iterator, FromIterator, IteratorUtil, Filter, AdditiveIterator, Map}; +use iterator::{Iterator, FromIterator, Extendable, IteratorUtil}; +use iterator::{Filter, AdditiveIterator, Map}; use libc; use num::Zero; use option::{None, Option, Some}; @@ -2323,10 +2324,20 @@ impl<T: Iterator<char>> FromIterator<char, T> for ~str { fn from_iterator(iterator: &mut T) -> ~str { let (lower, _) = iterator.size_hint(); let mut buf = with_capacity(lower); + buf.extend(iterator); + buf + } +} + +impl<T: Iterator<char>> Extendable<char, T> for ~str { + #[inline] + fn extend(&mut self, iterator: &mut T) { + let (lower, _) = iterator.size_hint(); + let reserve = lower + self.len(); + self.reserve_at_least(reserve); for iterator.advance |ch| { - buf.push_char(ch) + self.push_char(ch) } - buf } } @@ -2504,6 +2515,16 @@ mod tests { } #[test] + fn test_extend() { + let data = ~"ประเทศไทย中"; + let mut cpy = data.clone(); + let other = "abc"; + let mut it = other.iter(); + cpy.extend(&mut it); + assert_eq!(cpy, data + other); + } + + #[test] fn test_clear() { let mut empty = ~""; empty.clear(); diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs index 4665f361340..6a0554a8c8d 100644 --- a/src/libstd/trie.rs +++ b/src/libstd/trie.rs @@ -11,7 +11,7 @@ //! An ordered map and set for integer keys implemented as a radix trie use prelude::*; -use iterator::{IteratorUtil, FromIterator}; +use iterator::{IteratorUtil, FromIterator, Extendable}; use uint; use util::{swap, replace}; @@ -155,14 +155,18 @@ impl<T> TrieMap<T> { } impl<T, Iter: Iterator<(uint, T)>> FromIterator<(uint, T), Iter> for TrieMap<T> { - pub fn from_iterator(iter: &mut Iter) -> TrieMap<T> { + fn from_iterator(iter: &mut Iter) -> TrieMap<T> { let mut map = TrieMap::new(); + map.extend(iter); + map + } +} +impl<T, Iter: Iterator<(uint, T)>> Extendable<(uint, T), Iter> for TrieMap<T> { + fn extend(&mut self, iter: &mut Iter) { for iter.advance |(k, v)| { - map.insert(k, v); + self.insert(k, v); } - - map } } @@ -222,14 +226,18 @@ impl TrieSet { } impl<Iter: Iterator<uint>> FromIterator<uint, Iter> for TrieSet { - pub fn from_iterator(iter: &mut Iter) -> TrieSet { + fn from_iterator(iter: &mut Iter) -> TrieSet { let mut set = TrieSet::new(); + set.extend(iter); + set + } +} +impl<Iter: Iterator<uint>> Extendable<uint, Iter> for TrieSet { + fn extend(&mut self, iter: &mut Iter) { for iter.advance |elem| { - set.insert(elem); + self.insert(elem); } - - set } } diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs index fdfe357ae51..cfd28fcfc5e 100644 --- a/src/libstd/vec.rs +++ b/src/libstd/vec.rs @@ -2106,7 +2106,8 @@ macro_rules! iterator { #[inline] fn size_hint(&self) -> (uint, Option<uint>) { - let exact = self.indexable(); + let diff = (self.end as uint) - (self.ptr as uint); + let exact = diff / sys::nonzero_size_of::<T>(); (exact, Some(exact)) } } @@ -2134,23 +2135,19 @@ macro_rules! double_ended_iterator { } } -macro_rules! random_access_iterator { - (impl $name:ident -> $elem:ty) => { - impl<'self, T> RandomAccessIterator<$elem> for $name<'self, T> { - #[inline] - fn indexable(&self) -> uint { - let diff = (self.end as uint) - (self.ptr as uint); - diff / sys::nonzero_size_of::<T>() - } +impl<'self, T> RandomAccessIterator<&'self T> for VecIterator<'self, T> { + #[inline] + fn indexable(&self) -> uint { + let (exact, _) = self.size_hint(); + exact + } - fn idx(&self, index: uint) -> Option<$elem> { - unsafe { - if index < self.indexable() { - cast::transmute(self.ptr.offset(index)) - } else { - None - } - } + fn idx(&self, index: uint) -> Option<&'self T> { + unsafe { + if index < self.indexable() { + cast::transmute(self.ptr.offset(index)) + } else { + None } } } @@ -2165,7 +2162,6 @@ pub struct VecIterator<'self, T> { } iterator!{impl VecIterator -> &'self T} double_ended_iterator!{impl VecIterator -> &'self T} -random_access_iterator!{impl VecIterator -> &'self T} pub type RevIterator<'self, T> = Invert<VecIterator<'self, T>>; impl<'self, T> Clone for VecIterator<'self, T> { @@ -2181,7 +2177,6 @@ pub struct VecMutIterator<'self, T> { } iterator!{impl VecMutIterator -> &'self mut T} double_ended_iterator!{impl VecMutIterator -> &'self mut T} -random_access_iterator!{impl VecMutIterator -> &'self mut T} pub type MutRevIterator<'self, T> = Invert<VecMutIterator<'self, T>>; /// An iterator that moves out of a vector. |