From 2f10d1e295d0ba0b2ce2777443fbfbeb9711787d Mon Sep 17 00:00:00 2001 From: blake2-ppc Date: Mon, 29 Jul 2013 21:22:54 +0200 Subject: extra: Implement DoubleEnded and RandomAccess iterators for bitv --- src/libextra/bitv.rs | 39 +++++++++++++++++++++++++++++++++++---- 1 file changed, 35 insertions(+), 4 deletions(-) (limited to 'src/libextra') diff --git a/src/libextra/bitv.rs b/src/libextra/bitv.rs index 6e52802578c..914aa20792f 100644 --- a/src/libextra/bitv.rs +++ b/src/libextra/bitv.rs @@ -12,11 +12,13 @@ use std::cmp; +use std::iterator::{DoubleEndedIterator, RandomAccessIterator, Invert}; use std::num; use std::ops; use std::uint; use std::vec; + #[deriving(Clone)] struct SmallBitv { /// only the lowest nbits of this value are used. the rest is undefined. @@ -404,7 +406,7 @@ impl Bitv { #[inline] pub fn iter<'a>(&'a self) -> BitvIterator<'a> { - BitvIterator {bitv: self, next_idx: 0} + BitvIterator {bitv: self, next_idx: 0, end_idx: self.nbits} } /// Returns true if all bits are 0 @@ -564,13 +566,14 @@ fn iterate_bits(base: uint, bits: uint, f: &fn(uint) -> bool) -> bool { /// An iterator for Bitv pub struct BitvIterator<'self> { priv bitv: &'self Bitv, - priv next_idx: uint + priv next_idx: uint, + priv end_idx: uint, } impl<'self> Iterator for BitvIterator<'self> { #[inline] fn next(&mut self) -> Option { - if self.next_idx < self.bitv.nbits { + if self.next_idx != self.end_idx { let idx = self.next_idx; self.next_idx += 1; Some(self.bitv.get(idx)) @@ -580,11 +583,39 @@ impl<'self> Iterator for BitvIterator<'self> { } fn size_hint(&self) -> (uint, Option) { - let rem = self.bitv.nbits - self.next_idx; + let rem = self.end_idx - self.next_idx; (rem, Some(rem)) } } +impl<'self> DoubleEndedIterator for BitvIterator<'self> { + #[inline] + fn next_back(&mut self) -> Option { + if self.next_idx != self.end_idx { + self.end_idx -= 1; + Some(self.bitv.get(self.end_idx)) + } else { + None + } + } +} + +impl<'self> RandomAccessIterator for BitvIterator<'self> { + #[inline] + fn indexable(&self) -> uint { + self.end_idx - self.next_idx + } + + #[inline] + fn idx(&self, index: uint) -> Option { + if index >= self.indexable() { + None + } else { + Some(self.bitv.get(index)) + } + } +} + /// An implementation of a set using a bit vector as an underlying /// representation for holding numerical elements. /// -- cgit 1.4.1-3-g733a5 From f68621326ec295de6fd383a5230b807049ec4820 Mon Sep 17 00:00:00 2001 From: blake2-ppc Date: Mon, 29 Jul 2013 20:16:26 +0200 Subject: extra: Implement RandomAccessIterator for RingBuf --- src/libextra/ringbuf.rs | 41 ++++++++++++++++++++++++++--------------- 1 file changed, 26 insertions(+), 15 deletions(-) (limited to 'src/libextra') diff --git a/src/libextra/ringbuf.rs b/src/libextra/ringbuf.rs index 200a409f63c..90f37cbf526 100644 --- a/src/libextra/ringbuf.rs +++ b/src/libextra/ringbuf.rs @@ -16,7 +16,7 @@ use std::num; use std::uint; use std::vec; -use std::iterator::{FromIterator, Invert}; +use std::iterator::{FromIterator, Invert, RandomAccessIterator}; use container::Deque; @@ -176,8 +176,7 @@ impl RingBuf { /// Front-to-back iterator. pub fn iter<'a>(&'a self) -> RingBufIterator<'a, T> { - RingBufIterator{index: 0, rindex: self.nelts - 1, - nelts: self.nelts, elts: self.elts, lo: self.lo} + RingBufIterator{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts} } /// Back-to-front iterator. @@ -187,8 +186,7 @@ impl RingBuf { /// Front-to-back iterator which returns mutable values. pub fn mut_iter<'a>(&'a mut self) -> RingBufMutIterator<'a, T> { - RingBufMutIterator{index: 0, rindex: self.nelts - 1, - nelts: self.nelts, elts: self.elts, lo: self.lo} + RingBufMutIterator{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts} } /// Back-to-front iterator which returns mutable values. @@ -202,18 +200,18 @@ macro_rules! iterator { impl<'self, T> Iterator<$elem> for $name<'self, T> { #[inline] fn next(&mut self) -> Option<$elem> { - if self.nelts == 0 { + if self.index == self.rindex { return None; } let raw_index = raw_index(self.lo, self.elts.len(), self.index); self.index += 1; - self.nelts -= 1; - Some(self.elts[raw_index]. $getter ()) + Some(self.elts[raw_index] . $getter ()) } #[inline] fn size_hint(&self) -> (uint, Option) { - (self.nelts, Some(self.nelts)) + let len = self.rindex - self.index; + (len, Some(len)) } } } @@ -224,22 +222,21 @@ macro_rules! iterator_rev { impl<'self, T> DoubleEndedIterator<$elem> for $name<'self, T> { #[inline] fn next_back(&mut self) -> Option<$elem> { - if self.nelts == 0 { + if self.index == self.rindex { return None; } - let raw_index = raw_index(self.lo, self.elts.len(), self.rindex); self.rindex -= 1; - self.nelts -= 1; - Some(self.elts[raw_index]. $getter ()) + let raw_index = raw_index(self.lo, self.elts.len(), self.rindex); + Some(self.elts[raw_index] . $getter ()) } } } } + /// RingBuf iterator pub struct RingBufIterator<'self, T> { priv lo: uint, - priv nelts: uint, priv index: uint, priv rindex: uint, priv elts: &'self [Option], @@ -247,10 +244,24 @@ pub struct RingBufIterator<'self, T> { iterator!{impl RingBufIterator -> &'self T, get_ref} iterator_rev!{impl RingBufIterator -> &'self T, get_ref} +impl<'self, T> RandomAccessIterator<&'self T> for RingBufIterator<'self, T> { + #[inline] + fn indexable(&self) -> uint { self.rindex - self.index } + + #[inline] + fn idx(&self, j: uint) -> Option<&'self T> { + if j >= self.indexable() { + None + } else { + let raw_index = raw_index(self.lo, self.elts.len(), self.index + j); + Some(self.elts[raw_index].get_ref()) + } + } +} + /// RingBuf mutable iterator pub struct RingBufMutIterator<'self, T> { priv lo: uint, - priv nelts: uint, priv index: uint, priv rindex: uint, priv elts: &'self mut [Option], -- cgit 1.4.1-3-g733a5 From f8ae526f707c9a9e0540b80209838d2e75dc960b Mon Sep 17 00:00:00 2001 From: blake2-ppc Date: Tue, 30 Jul 2013 02:06:49 +0200 Subject: extra: Implement iterator::Extendable --- src/libextra/dlist.rs | 10 ++++++++-- src/libextra/priority_queue.rs | 21 ++++++++++++++------- src/libextra/ringbuf.rs | 15 +++++++++++---- src/libextra/treemap.rs | 26 ++++++++++++++++++-------- 4 files changed, 51 insertions(+), 21 deletions(-) (limited to 'src/libextra') diff --git a/src/libextra/dlist.rs b/src/libextra/dlist.rs index b8ba7e58f2a..88159ce5552 100644 --- a/src/libextra/dlist.rs +++ b/src/libextra/dlist.rs @@ -25,7 +25,7 @@ use std::cast; use std::ptr; use std::util; -use std::iterator::{FromIterator, Invert}; +use std::iterator::{FromIterator, Extendable, Invert}; use container::Deque; @@ -541,11 +541,17 @@ impl DoubleEndedIterator for ConsumeIterator { impl> FromIterator for DList { fn from_iterator(iterator: &mut T) -> DList { let mut ret = DList::new(); - for iterator.advance |elt| { ret.push_back(elt); } + ret.extend(iterator); ret } } +impl> Extendable for DList { + fn extend(&mut self, iterator: &mut T) { + for iterator.advance |elt| { self.push_back(elt); } + } +} + impl Eq for DList { fn eq(&self, other: &DList) -> bool { self.len() == other.len() && diff --git a/src/libextra/priority_queue.rs b/src/libextra/priority_queue.rs index dd24a2a9eb9..1c92a4f34e5 100644 --- a/src/libextra/priority_queue.rs +++ b/src/libextra/priority_queue.rs @@ -16,7 +16,7 @@ use std::clone::Clone; use std::unstable::intrinsics::{move_val_init, init}; use std::util::{replace, swap}; use std::vec; -use std::iterator::FromIterator; +use std::iterator::{FromIterator, Extendable}; /// A priority queue implemented with a binary heap #[deriving(Clone)] @@ -191,17 +191,24 @@ impl<'self, T> Iterator<&'self T> for PriorityQueueIterator<'self, T> { } impl> FromIterator for PriorityQueue { - pub fn from_iterator(iter: &mut Iter) -> PriorityQueue { + fn from_iterator(iter: &mut Iter) -> PriorityQueue { + let mut q = PriorityQueue::new(); + q.extend(iter); + + q + } +} + +impl> Extendable for PriorityQueue { + fn extend(&mut self, iter: &mut Iter) { let (lower, _) = iter.size_hint(); - let mut q = PriorityQueue::new(); - q.reserve_at_least(lower); + let len = self.capacity(); + self.reserve_at_least(len + lower); for iter.advance |elem| { - q.push(elem); + self.push(elem); } - - q } } diff --git a/src/libextra/ringbuf.rs b/src/libextra/ringbuf.rs index 90f37cbf526..92183f22d3b 100644 --- a/src/libextra/ringbuf.rs +++ b/src/libextra/ringbuf.rs @@ -16,7 +16,7 @@ use std::num; use std::uint; use std::vec; -use std::iterator::{FromIterator, Invert, RandomAccessIterator}; +use std::iterator::{FromIterator, Invert, RandomAccessIterator, Extendable}; use container::Deque; @@ -325,11 +325,18 @@ impl Eq for RingBuf { impl> FromIterator for RingBuf { fn from_iterator(iterator: &mut T) -> RingBuf { - let mut deq = RingBuf::new(); + let (lower, _) = iterator.size_hint(); + let mut deq = RingBuf::with_capacity(lower); + deq.extend(iterator); + deq + } +} + +impl> Extendable for RingBuf { + fn extend(&mut self, iterator: &mut T) { for iterator.advance |elt| { - deq.push_back(elt); + self.push_back(elt); } - deq } } diff --git a/src/libextra/treemap.rs b/src/libextra/treemap.rs index 8c7ace56412..6148e14b79f 100644 --- a/src/libextra/treemap.rs +++ b/src/libextra/treemap.rs @@ -15,7 +15,7 @@ use std::num; use std::util::{swap, replace}; -use std::iterator::FromIterator; +use std::iterator::{FromIterator, Extendable}; // This is implemented as an AA tree, which is a simplified variation of // a red-black tree where red (horizontal) nodes can only be added @@ -753,26 +753,36 @@ fn remove(node: &mut Option<~TreeNode>, } impl> FromIterator<(K, V), T> for TreeMap { - pub fn from_iterator(iter: &mut T) -> TreeMap { + fn from_iterator(iter: &mut T) -> TreeMap { let mut map = TreeMap::new(); + map.extend(iter); + map + } +} +impl> Extendable<(K, V), T> for TreeMap { + #[inline] + fn extend(&mut self, iter: &mut T) { for iter.advance |(k, v)| { - map.insert(k, v); + self.insert(k, v); } - - map } } impl> FromIterator for TreeSet { pub fn from_iterator(iter: &mut Iter) -> TreeSet { let mut set = TreeSet::new(); + set.extend(iter); + set + } +} +impl> Extendable for TreeSet { + #[inline] + fn extend(&mut self, iter: &mut Iter) { for iter.advance |elem| { - set.insert(elem); + self.insert(elem); } - - set } } -- cgit 1.4.1-3-g733a5 From ae09d95160919f8801caa22e2867e9680e6cb05b Mon Sep 17 00:00:00 2001 From: blake2-ppc Date: Tue, 30 Jul 2013 02:48:40 +0200 Subject: extra: Add .rev_iter() for bitv --- src/libextra/bitv.rs | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'src/libextra') diff --git a/src/libextra/bitv.rs b/src/libextra/bitv.rs index 914aa20792f..90824a653fa 100644 --- a/src/libextra/bitv.rs +++ b/src/libextra/bitv.rs @@ -409,6 +409,11 @@ impl Bitv { BitvIterator {bitv: self, next_idx: 0, end_idx: self.nbits} } + #[inline] + pub fn rev_liter<'a>(&'a self) -> Invert> { + self.iter().invert() + } + /// Returns true if all bits are 0 pub fn is_false(&self) -> bool { match self.rep { -- cgit 1.4.1-3-g733a5