auto merge of #8120 : blake2-ppc/rust/iterator-fixes, r=thestinger

Implement RandomAccessIterator (RAI) where possible, for Iterator adaptors such as Map, Enumerate, Peek, Skip, Take, Cycle, where the adapted iterator is already RAI, and for collections where it is relevant (ringbuf and bitv).

After discussion with thestinger, remove the RAI impl for VecMutIterator, we cannot soundly provide mutable access with this trait.

Implement Extendable everywhere FromIterator is already implemented.

Fixes issue #8108.

5 files changed, 116 insertions, 39 deletions

diff --git a/src/libextra/bitv.rs b/src/libextra/bitv.rs
index 6e52802578c..90824a653fa 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,12 @@ 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}
+    }
+
+    #[inline]
+    pub fn rev_liter<'a>(&'a self) -> Invert<BitvIterator<'a>> {
+        self.iter().invert()
     }
 
     /// Returns true if all bits are 0
@@ -564,13 +571,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<bool> for BitvIterator<'self> {
     #[inline]
     fn next(&mut self) -> Option<bool> {
-        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 +588,39 @@ impl<'self> Iterator<bool> for BitvIterator<'self> {
     }
 
     fn size_hint(&self) -> (uint, Option<uint>) {
-        let rem = self.bitv.nbits - self.next_idx;
+        let rem = self.end_idx - self.next_idx;
         (rem, Some(rem))
     }
 }
 
+impl<'self> DoubleEndedIterator<bool> for BitvIterator<'self> {
+    #[inline]
+    fn next_back(&mut self) -> Option<bool> {
+        if self.next_idx != self.end_idx {
+            self.end_idx -= 1;
+            Some(self.bitv.get(self.end_idx))
+        } else {
+            None
+        }
+    }
+}
+
+impl<'self> RandomAccessIterator<bool> for BitvIterator<'self> {
+    #[inline]
+    fn indexable(&self) -> uint {
+        self.end_idx - self.next_idx
+    }
+
+    #[inline]
+    fn idx(&self, index: uint) -> Option<bool> {
+        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.
 ///
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<A> DoubleEndedIterator<A> for ConsumeIterator<A> {
 impl<A, T: Iterator<A>> FromIterator<A, T> for DList<A> {
     fn from_iterator(iterator: &mut T) -> DList<A> {
         let mut ret = DList::new();
-        for iterator.advance |elt| { ret.push_back(elt); }
+        ret.extend(iterator);
         ret
     }
 }
 
+impl<A, T: Iterator<A>> Extendable<A, T> for DList<A> {
+    fn extend(&mut self, iterator: &mut T) {
+        for iterator.advance |elt| { self.push_back(elt); }
+    }
+}
+
 impl<A: Eq> Eq for DList<A> {
     fn eq(&self, other: &DList<A>) -> 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<T: Ord, Iter: Iterator<T>> FromIterator<T, Iter> for PriorityQueue<T> {
-    pub fn from_iterator(iter: &mut Iter) -> PriorityQueue<T> {
+    fn from_iterator(iter: &mut Iter) -> PriorityQueue<T> {
+        let mut q = PriorityQueue::new();
+        q.extend(iter);
+
+        q
+    }
+}
+
+impl<T: Ord, Iter: Iterator<T>> Extendable<T, Iter> for PriorityQueue<T> {
+    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 200a409f63c..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};
+use std::iterator::{FromIterator, Invert, RandomAccessIterator, Extendable};
 
 use container::Deque;
 
@@ -176,8 +176,7 @@ impl<T> RingBuf<T> {
 
     /// 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<T> RingBuf<T> {
 
     /// 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<uint>) {
-                (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<T>],
@@ -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<T>],
@@ -314,11 +325,18 @@ impl<A: Eq> Eq for RingBuf<A> {
 
 impl<A, T: Iterator<A>> FromIterator<A, T> for RingBuf<A> {
     fn from_iterator(iterator: &mut T) -> RingBuf<A> {
-        let mut deq = RingBuf::new();
+        let (lower, _) = iterator.size_hint();
+        let mut deq = RingBuf::with_capacity(lower);
+        deq.extend(iterator);
+        deq
+    }
+}
+
+impl<A, T: Iterator<A>> Extendable<A, T> for RingBuf<A> {
+    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<K: TotalOrd, V>(node: &mut Option<~TreeNode<K, V>>,
 }
 
 impl<K: TotalOrd, V, T: Iterator<(K, V)>> FromIterator<(K, V), T> for TreeMap<K, V> {
-    pub fn from_iterator(iter: &mut T) -> TreeMap<K, V> {
+    fn from_iterator(iter: &mut T) -> TreeMap<K, V> {
         let mut map = TreeMap::new();
+        map.extend(iter);
+        map
+    }
+}
 
+impl<K: TotalOrd, V, T: Iterator<(K, V)>> Extendable<(K, V), T> for TreeMap<K, V> {
+    #[inline]
+    fn extend(&mut self, iter: &mut T) {
         for iter.advance |(k, v)| {
-            map.insert(k, v);
+            self.insert(k, v);
         }
-
-        map
     }
 }
 
 impl<T: TotalOrd, Iter: Iterator<T>> FromIterator<T, Iter> for TreeSet<T> {
     pub fn from_iterator(iter: &mut Iter) -> TreeSet<T> {
         let mut set = TreeSet::new();
+        set.extend(iter);
+        set
+    }
+}
 
+impl<T: TotalOrd, Iter: Iterator<T>> Extendable<T, Iter> for TreeSet<T> {
+    #[inline]
+    fn extend(&mut self, iter: &mut Iter) {
         for iter.advance |elem| {
-            set.insert(elem);
+            self.insert(elem);
         }
-
-        set
     }
 }