extra: Implement DoubleEnded and RandomAccess iterators for bitv

1 files changed, 35 insertions, 4 deletions

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<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 +583,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.
 ///