auto merge of #7420 : mozilla/rust/rollup, r=thestinger

6 files changed, 217 insertions, 79 deletions

diff --git a/src/libextra/deque.rs b/src/libextra/deque.rs
index c8bb984736a..e6a7dd64837 100644
--- a/src/libextra/deque.rs
+++ b/src/libextra/deque.rs
@@ -9,12 +9,12 @@
 // except according to those terms.
 
 //! A double-ended queue implemented as a circular buffer
-
 use core::prelude::*;
 
 use core::uint;
 use core::util::replace;
 use core::vec;
+use core::cast::transmute;
 
 static initial_capacity: uint = 32u; // 2^5
 
@@ -153,7 +153,86 @@ impl<T> Deque<T> {
     pub fn reserve_at_least(&mut self, n: uint) {
         vec::reserve_at_least(&mut self.elts, n);
     }
+
+    /// Front-to-back iterator.
+    pub fn iter<'a>(&'a self) -> DequeIterator<'a, T> {
+    DequeIterator { idx: self.lo, nelts: self.nelts, used: 0, vec: self.elts }
+    }
+
+    /// Front-to-back iterator which returns mutable values.
+    pub fn mut_iter<'a>(&'a mut self) -> DequeMutIterator<'a, T> {
+    DequeMutIterator { idx: self.lo, nelts: self.nelts, used: 0, vec: self.elts }
+    }
+
+    /// Back-to-front iterator.
+    pub fn rev_iter<'a>(&'a self) -> DequeRevIterator<'a, T> {
+    DequeRevIterator { idx: self.hi - 1u, nelts: self.nelts, used: 0, vec: self.elts }
+    }
+
+    /// Back-to-front iterator which returns mutable values.
+    pub fn mut_rev_iter<'a>(&'a mut self) -> DequeMutRevIterator<'a, T> {
+    DequeMutRevIterator { idx: self.hi - 1u, nelts: self.nelts, used: 0, vec: self.elts }
+    }
+}
+
+macro_rules! iterator {
+    (impl $name:ident -> $elem:ty, $step:expr) => {
+        impl<'self, T> Iterator<$elem> for $name<'self, T> {
+            #[inline]
+            fn next(&mut self) -> Option<$elem> {
+                if self.used >= self.nelts {
+                    return None;
+                }
+                let ret = unsafe {
+                    match self.vec[self.idx % self.vec.len()] {
+                        Some(ref e) => Some(transmute(e)),
+                        None => None
+                    }
+                };
+                self.idx += $step;
+                self.used += 1;
+                ret
+            }
+        }
+    }
+}
+
+/// Deque iterator
+pub struct DequeIterator<'self, T> {
+    priv idx: uint,
+    priv nelts: uint,
+    priv used: uint,
+    priv vec: &'self [Option<T>]
 }
+iterator!{impl DequeIterator -> &'self T, 1}
+
+/// Deque reverse iterator
+pub struct DequeRevIterator<'self, T> {
+    priv idx: uint,
+    priv nelts: uint,
+    priv used: uint,
+    priv vec: &'self [Option<T>]
+}
+iterator!{impl DequeRevIterator -> &'self T, -1}
+
+/// Deque mutable iterator
+pub struct DequeMutIterator<'self, T> {
+    priv idx: uint,
+    priv nelts: uint,
+    priv used: uint,
+    priv vec: &'self mut [Option<T>]
+
+}
+iterator!{impl DequeMutIterator -> &'self mut T, 1}
+
+/// Deque mutable reverse iterator
+pub struct DequeMutRevIterator<'self, T> {
+    priv idx: uint,
+    priv nelts: uint,
+    priv used: uint,
+    priv vec: &'self mut [Option<T>]
+}
+iterator!{impl DequeMutRevIterator -> &'self mut T, -1}
 
 /// Grow is only called on full elts, so nelts is also len(elts), unlike
 /// elsewhere.
@@ -178,6 +257,7 @@ mod tests {
     use core::cmp::Eq;
     use core::kinds::Copy;
     use core::vec::capacity;
+    use core;
 
     #[test]
     fn test_simple() {
@@ -318,8 +398,7 @@ mod tests {
 
     #[test]
     fn test_param_taggy() {
-        test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3),
-                                    Two(17, 42));
+        test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
     }
 
     #[test]
@@ -382,4 +461,31 @@ mod tests {
         assert_eq!(capacity(&mut d.elts), 64);
     }
 
+    #[test]
+    fn test_iter() {
+        let mut d = Deque::new();
+        for core::int::range(0,5) |i| {
+            d.add_back(i);
+        }
+        assert_eq!(d.iter().collect::<~[&int]>(), ~[&0,&1,&2,&3,&4]);
+
+        for core::int::range(6,9) |i| {
+            d.add_front(i);
+        }
+        assert_eq!(d.iter().collect::<~[&int]>(), ~[&8,&7,&6,&0,&1,&2,&3,&4]);
+    }
+
+    #[test]
+    fn test_rev_iter() {
+        let mut d = Deque::new();
+        for core::int::range(0,5) |i| {
+            d.add_back(i);
+        }
+        assert_eq!(d.rev_iter().collect::<~[&int]>(), ~[&4,&3,&2,&1,&0]);
+
+        for core::int::range(6,9) |i| {
+            d.add_front(i);
+        }
+        assert_eq!(d.rev_iter().collect::<~[&int]>(), ~[&4,&3,&2,&1,&0,&6,&7,&8]);
+    }
 }
diff --git a/src/libextra/priority_queue.rs b/src/libextra/priority_queue.rs
index 4e201a6538b..af891edf9e5 100644
--- a/src/libextra/priority_queue.rs
+++ b/src/libextra/priority_queue.rs
@@ -37,10 +37,11 @@ impl<T:Ord> Mutable for PriorityQueue<T> {
 }
 
 impl<T:Ord> PriorityQueue<T> {
-    /// Visit all values in the underlying vector.
-    ///
-    /// The values are **not** visited in order.
-    pub fn each(&self, f: &fn(&T) -> bool) -> bool { self.data.iter().advance(f) }
+    /// An iterator visiting all values in underlying vector, in
+    /// arbitrary order.
+    pub fn iter<'a>(&'a self) -> PriorityQueueIterator<'a, T> {
+        PriorityQueueIterator { iter: self.data.iter() }
+    }
 
     /// Returns the greatest item in the queue - fails if empty
     pub fn top<'a>(&'a self) -> &'a T { &self.data[0] }
@@ -178,12 +179,34 @@ impl<T:Ord> PriorityQueue<T> {
     }
 }
 
+/// PriorityQueue iterator
+pub struct PriorityQueueIterator <'self, T> {
+    priv iter: vec::VecIterator<'self, T>,
+}
+
+impl<'self, T> Iterator<&'self T> for PriorityQueueIterator<'self, T> {
+    #[inline]
+    fn next(&mut self) -> Option<(&'self T)> { self.iter.next() }
+}
+
 #[cfg(test)]
 mod tests {
     use sort::merge_sort;
     use priority_queue::PriorityQueue;
 
     #[test]
+    fn test_iterator() {
+        let data = ~[5, 9, 3];
+        let iterout = ~[9, 5, 3];
+        let pq = PriorityQueue::from_vec(data);
+        let mut i = 0;
+        for pq.iter().advance |el| {
+            assert_eq!(*el, iterout[i]);
+            i += 1;
+        }
+    }
+
+    #[test]
     fn test_top_and_pop() {
         let data = ~[2u, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1];
         let mut sorted = merge_sort(data, |x, y| x.le(y));
diff --git a/src/libextra/serialize.rs b/src/libextra/serialize.rs
index 345b217871c..3d35d1332b2 100644
--- a/src/libextra/serialize.rs
+++ b/src/libextra/serialize.rs
@@ -832,7 +832,7 @@ impl<
     fn encode(&self, e: &mut E) {
         do e.emit_map(self.len()) |e| {
             let mut i = 0;
-            for self.each |key, val| {
+            for self.iter().advance |(key, val)| {
                 e.emit_map_elt_key(i, |e| key.encode(e));
                 e.emit_map_elt_val(i, |e| val.encode(e));
                 i += 1;
@@ -866,7 +866,7 @@ impl<
     fn encode(&self, s: &mut S) {
         do s.emit_seq(self.len()) |s| {
             let mut i = 0;
-            for self.each |e| {
+            for self.iter().advance |e| {
                 s.emit_seq_elt(i, |s| e.encode(s));
                 i += 1;
             }
diff --git a/src/libextra/term.rs b/src/libextra/term.rs
index 782a73deadf..9a4469cb526 100644
--- a/src/libextra/term.rs
+++ b/src/libextra/term.rs
@@ -24,35 +24,38 @@ use core::io;
 
 // FIXME (#2807): Windows support.
 
-pub static color_black: u8 = 0u8;
-pub static color_red: u8 = 1u8;
-pub static color_green: u8 = 2u8;
-pub static color_yellow: u8 = 3u8;
-pub static color_blue: u8 = 4u8;
-pub static color_magenta: u8 = 5u8;
-pub static color_cyan: u8 = 6u8;
-pub static color_light_gray: u8 = 7u8;
-pub static color_light_grey: u8 = 7u8;
-pub static color_dark_gray: u8 = 8u8;
-pub static color_dark_grey: u8 = 8u8;
-pub static color_bright_red: u8 = 9u8;
-pub static color_bright_green: u8 = 10u8;
-pub static color_bright_yellow: u8 = 11u8;
-pub static color_bright_blue: u8 = 12u8;
-pub static color_bright_magenta: u8 = 13u8;
-pub static color_bright_cyan: u8 = 14u8;
-pub static color_bright_white: u8 = 15u8;
+pub mod color {
+    pub type Color = u16;
+
+    pub static black:   Color = 0u16;
+    pub static red:     Color = 1u16;
+    pub static green:   Color = 2u16;
+    pub static yellow:  Color = 3u16;
+    pub static blue:    Color = 4u16;
+    pub static magenta: Color = 5u16;
+    pub static cyan:    Color = 6u16;
+    pub static white:   Color = 7u16;
+
+    pub static bright_black:   Color = 8u16;
+    pub static bright_red:     Color = 9u16;
+    pub static bright_green:   Color = 10u16;
+    pub static bright_yellow:  Color = 11u16;
+    pub static bright_blue:    Color = 12u16;
+    pub static bright_magenta: Color = 13u16;
+    pub static bright_cyan:    Color = 14u16;
+    pub static bright_white:   Color = 15u16;
+}
 
 #[cfg(not(target_os = "win32"))]
 pub struct Terminal {
-    color_supported: bool,
+    num_colors: u16,
     priv out: @io::Writer,
     priv ti: ~TermInfo
 }
 
 #[cfg(target_os = "win32")]
 pub struct Terminal {
-    color_supported: bool,
+    num_colors: u16,
     priv out: @io::Writer,
 }
 
@@ -66,66 +69,81 @@ impl Terminal {
 
         let entry = open(term.unwrap());
         if entry.is_err() {
-            return Err(entry.get_err());
+            return Err(entry.unwrap_err());
         }
 
-        let ti = parse(entry.get(), false);
+        let ti = parse(entry.unwrap(), false);
         if ti.is_err() {
-            return Err(entry.get_err());
+            return Err(ti.unwrap_err());
         }
 
-        let mut inf = ti.get();
-        let cs = *inf.numbers.find_or_insert(~"colors", 0) >= 16
-            && inf.strings.find(&~"setaf").is_some()
-            && inf.strings.find_equiv(&("setab")).is_some();
+        let inf = ti.unwrap();
+        let nc = if inf.strings.find_equiv(&("setaf")).is_some()
+                 && inf.strings.find_equiv(&("setab")).is_some() {
+                     inf.numbers.find_equiv(&("colors")).map_consume_default(0, |&n| n)
+                 } else { 0 };
 
-        return Ok(Terminal {out: out, ti: inf, color_supported: cs});
+        return Ok(Terminal {out: out, ti: inf, num_colors: nc});
     }
-    pub fn fg(&self, color: u8) {
-        if self.color_supported {
+    /// Sets the foreground color to the given color.
+    ///
+    /// If the color is a bright color, but the terminal only supports 8 colors,
+    /// the corresponding normal color will be used instead.
+    pub fn fg(&self, color: color::Color) {
+        let color = self.dim_if_necessary(color);
+        if self.num_colors > color {
             let s = expand(*self.ti.strings.find_equiv(&("setaf")).unwrap(),
                            [Number(color as int)], &mut Variables::new());
             if s.is_ok() {
-                self.out.write(s.get());
+                self.out.write(s.unwrap());
             } else {
-                warn!(s.get_err());
+                warn!(s.unwrap_err());
             }
         }
     }
-    pub fn bg(&self, color: u8) {
-        if self.color_supported {
+    /// Sets the background color to the given color.
+    ///
+    /// If the color is a bright color, but the terminal only supports 8 colors,
+    /// the corresponding normal color will be used instead.
+    pub fn bg(&self, color: color::Color) {
+        let color = self.dim_if_necessary(color);
+        if self.num_colors > color {
             let s = expand(*self.ti.strings.find_equiv(&("setab")).unwrap(),
                            [Number(color as int)], &mut Variables::new());
             if s.is_ok() {
-                self.out.write(s.get());
+                self.out.write(s.unwrap());
             } else {
-                warn!(s.get_err());
+                warn!(s.unwrap_err());
             }
         }
     }
     pub fn reset(&self) {
-        if self.color_supported {
-            let mut vars = Variables::new();
-            let s = expand(*self.ti.strings.find_equiv(&("op")).unwrap(), [], &mut vars);
-            if s.is_ok() {
-                self.out.write(s.get());
-            } else {
-                warn!(s.get_err());
-            }
+        let mut vars = Variables::new();
+        let s = expand(*self.ti.strings.find_equiv(&("op")).unwrap(), [], &mut vars);
+        if s.is_ok() {
+            self.out.write(s.unwrap());
+        } else {
+            warn!(s.unwrap_err());
         }
     }
+
+    priv fn dim_if_necessary(&self, color: color::Color) -> color::Color {
+        if color >= self.num_colors && color >= 8 && color < 16 {
+            color-8
+        } else { color }
+    }
 }
 
 #[cfg(target_os = "win32")]
 impl Terminal {
     pub fn new(out: @io::Writer) -> Result<Terminal, ~str> {
-        return Ok(Terminal {out: out, color_supported: false});
+        return Ok(Terminal {out: out, num_colors: 0});
     }
 
-    pub fn fg(&self, _color: u8) {
+    pub fn fg(&self, _color: color::Color) {
     }
 
-    pub fn bg(&self, _color: u8) {
+    pub fn bg(&self, _color: color::Color) {
     }
 
     pub fn reset(&self) {
diff --git a/src/libextra/test.rs b/src/libextra/test.rs
index ee0d3649467..72e70943ce1 100644
--- a/src/libextra/test.rs
+++ b/src/libextra/test.rs
@@ -326,33 +326,33 @@ pub fn run_tests_console(opts: &TestOpts,
     }
 
     fn write_ok(out: @io::Writer, use_color: bool) {
-        write_pretty(out, "ok", term::color_green, use_color);
+        write_pretty(out, "ok", term::color::green, use_color);
     }
 
     fn write_failed(out: @io::Writer, use_color: bool) {
-        write_pretty(out, "FAILED", term::color_red, use_color);
+        write_pretty(out, "FAILED", term::color::red, use_color);
     }
 
     fn write_ignored(out: @io::Writer, use_color: bool) {
-        write_pretty(out, "ignored", term::color_yellow, use_color);
+        write_pretty(out, "ignored", term::color::yellow, use_color);
     }
 
     fn write_bench(out: @io::Writer, use_color: bool) {
-        write_pretty(out, "bench", term::color_cyan, use_color);
+        write_pretty(out, "bench", term::color::cyan, use_color);
     }
 
     fn write_pretty(out: @io::Writer,
                     word: &str,
-                    color: u8,
+                    color: term::color::Color,
                     use_color: bool) {
         let t = term::Terminal::new(out);
         match t {
             Ok(term)  => {
-                if use_color && term.color_supported {
+                if use_color {
                     term.fg(color);
                 }
                 out.write_str(word);
-                if use_color && term.color_supported {
+                if use_color {
                     term.reset();
                 }
             },
diff --git a/src/libextra/treemap.rs b/src/libextra/treemap.rs
index fd83fd19916..33ec4ae94ba 100644
--- a/src/libextra/treemap.rs
+++ b/src/libextra/treemap.rs
@@ -164,19 +164,14 @@ impl<K: TotalOrd, V> TreeMap<K, V> {
     /// Create an empty TreeMap
     pub fn new() -> TreeMap<K, V> { TreeMap{root: None, length: 0} }
 
-    /// Visit all key-value pairs in order
-    pub fn each<'a>(&'a self, f: &fn(&'a K, &'a V) -> bool) -> bool {
-        each(&self.root, f)
-    }
-
     /// Visit all keys in order
     pub fn each_key(&self, f: &fn(&K) -> bool) -> bool {
-        self.each(|k, _| f(k))
+        self.iter().advance(|(k, _)| f(k))
     }
 
     /// Visit all values in order
     pub fn each_value<'a>(&'a self, f: &fn(&'a V) -> bool) -> bool {
-        self.each(|_, v| f(v))
+        self.iter().advance(|(_, v)| f(v))
     }
 
     /// Iterate over the map and mutate the contained values
@@ -484,10 +479,6 @@ impl<T: TotalOrd> TreeSet<T> {
         TreeSetIterator{iter: self.map.iter()}
     }
 
-    /// Visit all values in order
-    #[inline]
-    pub fn each(&self, f: &fn(&T) -> bool) -> bool { self.map.each_key(f) }
-
     /// Visit all values in reverse order
     #[inline]
     pub fn each_reverse(&self, f: &fn(&T) -> bool) -> bool {
@@ -779,7 +770,7 @@ mod test_treemap {
             let &(k, v) = x;
             assert!(map.find(&k).unwrap() == &v)
         }
-        for map.each |map_k, map_v| {
+        for map.iter().advance |(map_k, map_v)| {
             let mut found = false;
             for ctrl.iter().advance |x| {
                 let &(ctrl_k, ctrl_v) = x;
@@ -885,7 +876,7 @@ mod test_treemap {
     }
 
     #[test]
-    fn test_each() {
+    fn test_iterator() {
         let mut m = TreeMap::new();
 
         assert!(m.insert(3, 6));
@@ -895,7 +886,7 @@ mod test_treemap {
         assert!(m.insert(1, 2));
 
         let mut n = 0;
-        for m.each |k, v| {
+        for m.iter().advance |(k, v)| {
             assert_eq!(*k, n);
             assert_eq!(*v, n * 2);
             n += 1;
@@ -1090,7 +1081,7 @@ mod test_set {
     }
 
     #[test]
-    fn test_each() {
+    fn test_iterator() {
         let mut m = TreeSet::new();
 
         assert!(m.insert(3));
@@ -1100,7 +1091,7 @@ mod test_set {
         assert!(m.insert(1));
 
         let mut n = 0;
-        for m.each |x| {
+        for m.iter().advance |x| {
             println(fmt!("%?", x));
             assert_eq!(*x, n);
             n += 1