Change the way that events are represented.

The bulk of this commit is changing instances of Vec to RingBuf which is
optimized for the push_back() / pop_front() strategy that is used
internaly in the event system.

The glutin custom iterators are now just wrappers around the RingBuf
iterator type.  This will bring the running time of iterator traversal from
O(n^2) to O(n) because shifting-on-delete won't be performed.

8 files changed, 77 insertions, 65 deletions

diff --git a/src/android/mod.rs b/src/android/mod.rs
index b8514f1..c548f2f 100644
--- a/src/android/mod.rs
+++ b/src/android/mod.rs
@@ -7,6 +7,8 @@ use events::ElementState::{Pressed, Released};
 use events::Event::{MouseInput, MouseMoved};
 use events::MouseButton::LeftMouseButton;
 
+use std::collections::RingBuf;
+
 use BuilderAttribs;
 
 pub struct Window {
@@ -20,8 +22,10 @@ pub struct MonitorID;
 
 mod ffi;
 
-pub fn get_available_monitors() -> Vec<MonitorID> {
-    vec![ MonitorID ]
+pub fn get_available_monitors() -> RingBuf <MonitorID> {
+    let rb = RingBuf::new();
+    rb.push_back(MonitorId);
+    rb
 }
 
 pub fn get_primary_monitor() -> MonitorID {
@@ -215,19 +219,19 @@ impl Window {
         WindowProxy
     }
 
-    pub fn poll_events(&self) -> Vec<Event> {
-        let mut events = Vec::new();
+    pub fn poll_events(&self) -> RingBuf<Event> {
+        let mut events = RingBuf::new();
         loop {
             match self.event_rx.try_recv() {
                 Ok(event) => match event {
                     android_glue::Event::EventDown => {
-                        events.push(MouseInput(Pressed, LeftMouseButton));
+                        events.push_back(MouseInput(Pressed, LeftMouseButton));
                     },
                     android_glue::Event::EventUp => {
-                        events.push(MouseInput(Released, LeftMouseButton));
+                        events.push_back(MouseInput(Released, LeftMouseButton));
                     },
                     android_glue::Event::EventMove(x, y) => {
-                        events.push(MouseMoved((x as int, y as int)));
+                        events.push_back(MouseMoved((x as int, y as int)));
                     },
                 },
                 Err(_) => {
@@ -238,7 +242,7 @@ impl Window {
         events
     }
 
-    pub fn wait_events(&self) -> Vec<Event> {
+    pub fn wait_events(&self) -> RingBuf<Event> {
         use std::time::Duration;
         use std::io::timer;
         timer::sleep(Duration::milliseconds(16));
diff --git a/src/lib.rs b/src/lib.rs
index 6a1c23b..3c780a0 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -43,6 +43,7 @@ extern crate core_graphics;
 pub use events::*;
 
 use std::default::Default;
+use std::collections::ring_buf::IntoIter as RingBufIter;
 
 #[cfg(all(not(target_os = "windows"), not(target_os = "linux"), not(target_os = "macos"), not(target_os = "android")))]
 use this_platform_is_not_supported;
@@ -97,7 +98,7 @@ pub struct WindowBuilder<'a> {
     attribs: BuilderAttribs<'a>
 }
 
-/// Attributes 
+/// Attributes
 struct BuilderAttribs<'a> {
     headless: bool,
     strict: bool,
@@ -487,7 +488,7 @@ impl Window {
     /// Contrary to `wait_events`, this function never blocks.
     #[inline]
     pub fn poll_events(&self) -> PollEventsIterator {
-        PollEventsIterator { data: self.window.poll_events() }
+        PollEventsIterator { data: self.window.poll_events().into_iter() }
     }
 
     /// Waits for an event, then returns an iterator to all the events that are currently
@@ -497,7 +498,7 @@ impl Window {
     ///  this function will block until there is one.
     #[inline]
     pub fn wait_events(&self) -> WaitEventsIterator {
-        WaitEventsIterator { data: self.window.wait_events() }
+        WaitEventsIterator { data: self.window.wait_events().into_iter() }
     }
 
     /// Sets the context as the current context.
@@ -637,12 +638,12 @@ impl gl_common::GlFunctionsSource for HeadlessContext {
 // Implementation note: we retreive the list once, then serve each element by one by one.
 // This may change in the future.
 pub struct PollEventsIterator<'a> {
-    data: Vec<Event>,
+    data: RingBufIter<Event>,
 }
 
 impl<'a> Iterator<Event> for PollEventsIterator<'a> {
     fn next(&mut self) -> Option<Event> {
-        self.data.remove(0)
+        self.data.next()
     }
 }
 
@@ -650,12 +651,12 @@ impl<'a> Iterator<Event> for PollEventsIterator<'a> {
 // Implementation note: we retreive the list once, then serve each element by one by one.
 // This may change in the future.
 pub struct WaitEventsIterator<'a> {
-    data: Vec<Event>,
+    data: RingBufIter<Event>,
 }
 
 impl<'a> Iterator<Event> for WaitEventsIterator<'a> {
     fn next(&mut self) -> Option<Event> {
-        self.data.remove(0)
+        self.data.next()
     }
 }
 
@@ -664,13 +665,13 @@ impl<'a> Iterator<Event> for WaitEventsIterator<'a> {
 // This may change in the future.
 #[cfg(feature = "window")]
 pub struct AvailableMonitorsIter {
-    data: Vec<winimpl::MonitorID>,
+    data: RingBufIter<winimpl::MonitorID>,
 }
 
 #[cfg(feature = "window")]
 impl Iterator<MonitorID> for AvailableMonitorsIter {
     fn next(&mut self) -> Option<MonitorID> {
-        self.data.remove(0).map(|id| MonitorID(id))
+        self.data.next().map(|id| MonitorID(id))
     }
 }
 
@@ -678,7 +679,7 @@ impl Iterator<MonitorID> for AvailableMonitorsIter {
 #[cfg(feature = "window")]
 pub fn get_available_monitors() -> AvailableMonitorsIter {
     let data = winimpl::get_available_monitors();
-    AvailableMonitorsIter{ data: data }
+    AvailableMonitorsIter{ data: data.into_iter() }
 }
 
 /// Returns the primary monitor of the system.
diff --git a/src/osx/mod.rs b/src/osx/mod.rs
index b65f67a..80e08da 100644
--- a/src/osx/mod.rs
+++ b/src/osx/mod.rs
@@ -21,6 +21,7 @@ use std::cell::Cell;
 use std::c_str::CString;
 use std::mem;
 use std::ptr;
+use std::collections::RingBuf;
 
 use events::Event::{MouseInput, MouseMoved, ReceivedCharacter, KeyboardInput, MouseWheel};
 use events::ElementState::{Pressed, Released};
@@ -337,8 +338,8 @@ impl Window {
         WindowProxy
     }
 
-    pub fn poll_events(&self) -> Vec<Event> {
-        let mut events = Vec::new();
+    pub fn poll_events(&self) -> RingBuf<Event> {
+        let mut events = RingBuf::new();
 
         loop {
             unsafe {
@@ -370,53 +371,53 @@ impl Window {
 }
 
                 match event.get_type() {
-                    NSLeftMouseDown         => { events.push(MouseInput(Pressed, LeftMouseButton)); },
-                    NSLeftMouseUp           => { events.push(MouseInput(Released, LeftMouseButton)); },
-                    NSRightMouseDown        => { events.push(MouseInput(Pressed, RightMouseButton)); },
-                    NSRightMouseUp          => { events.push(MouseInput(Released, RightMouseButton)); },
+                    NSLeftMouseDown         => { events.push_back(MouseInput(Pressed, LeftMouseButton)); },
+                    NSLeftMouseUp           => { events.push_back(MouseInput(Released, LeftMouseButton)); },
+                    NSRightMouseDown        => { events.push_back(MouseInput(Pressed, RightMouseButton)); },
+                    NSRightMouseUp          => { events.push_back(MouseInput(Released, RightMouseButton)); },
                     NSMouseMoved            => {
                         let window_point = event.locationInWindow();
                         let view_point = self.view.convertPoint_fromView_(window_point, nil);
-                        events.push(MouseMoved((view_point.x as int, view_point.y as int)));
+                        events.push_back(MouseMoved((view_point.x as int, view_point.y as int)));
                     },
                     NSKeyDown               => {
                         let received_str = CString::new(event.characters().UTF8String(), false);
                         for received_char in received_str.as_str().unwrap().chars() {
                             if received_char.is_ascii() {
-                                events.push(ReceivedCharacter(received_char));
+                                events.push_back(ReceivedCharacter(received_char));
                             }
                         }
 
                         let vkey =  event::vkeycode_to_element(event.keycode());
-                        events.push(KeyboardInput(Pressed, event.keycode() as u8, vkey));
+                        events.push_back(KeyboardInput(Pressed, event.keycode() as u8, vkey));
                     },
                     NSKeyUp                 => {
                         let vkey =  event::vkeycode_to_element(event.keycode());
-                        events.push(KeyboardInput(Released, event.keycode() as u8, vkey));
+                        events.push_back(KeyboardInput(Released, event.keycode() as u8, vkey));
                     },
                     NSFlagsChanged          => {
                         let shift_modifier = Window::modifier_event(event, appkit::NSShiftKeyMask as u64, events::VirtualKeyCode::LShift, shift_pressed);
                         if shift_modifier.is_some() {
                             shift_pressed = !shift_pressed;
-                            events.push(shift_modifier.unwrap());
+                            events.push_back(shift_modifier.unwrap());
                         }
                         let ctrl_modifier = Window::modifier_event(event, appkit::NSControlKeyMask as u64, events::VirtualKeyCode::LControl, ctrl_pressed);
                         if ctrl_modifier.is_some() {
                             ctrl_pressed = !ctrl_pressed;
-                            events.push(ctrl_modifier.unwrap());
+                            events.push_back(ctrl_modifier.unwrap());
                         }
                         let win_modifier = Window::modifier_event(event, appkit::NSCommandKeyMask as u64, events::VirtualKeyCode::LWin, win_pressed);
                         if win_modifier.is_some() {
                             win_pressed = !win_pressed;
-                            events.push(win_modifier.unwrap());
+                            events.push_back(win_modifier.unwrap());
                         }
                         let alt_modifier = Window::modifier_event(event, appkit::NSAlternateKeyMask as u64, events::VirtualKeyCode::LAlt, alt_pressed);
                         if alt_modifier.is_some() {
                             alt_pressed = !alt_pressed;
-                            events.push(alt_modifier.unwrap());
+                            events.push_back(alt_modifier.unwrap());
                         }
                     },
-                    NSScrollWheel           => { events.push(MouseWheel(-event.scrollingDeltaY() as i32)); },
+                    NSScrollWheel           => { events.push_back(MouseWheel(-event.scrollingDeltaY() as i32)); },
                     NSOtherMouseDown        => { },
                     NSOtherMouseUp          => { },
                     NSOtherMouseDragged     => { },
@@ -442,7 +443,7 @@ impl Window {
         event.modifierFlags() & modifier != 0
     }
 
-    pub fn wait_events(&self) -> Vec<Event> {
+    pub fn wait_events(&self) -> RingBuf<Event> {
         unsafe {
             let event = NSApp().nextEventMatchingMask_untilDate_inMode_dequeue_(
                 NSAnyEventMask as u64,
diff --git a/src/osx/monitor.rs b/src/osx/monitor.rs
index 383fd32..3fb1d74 100644
--- a/src/osx/monitor.rs
+++ b/src/osx/monitor.rs
@@ -1,9 +1,10 @@
 use core_graphics::display;
+use std::collections::RingBuf;
 
 pub struct MonitorID(u32);
 
 pub fn get_available_monitors() -> Vec<MonitorID> {
-    let mut monitors = Vec::new();
+    let mut monitors = RingBuf::new();
     unsafe {
         let max_displays = 10u32;
         let mut active_displays = [0u32, ..10];
@@ -12,7 +13,7 @@ pub fn get_available_monitors() -> Vec<MonitorID> {
                                                         &mut active_displays[0],
                                                         &mut display_count);
         for i in range(0u, display_count as uint) {
-            monitors.push(MonitorID(active_displays[i]));
+            monitors.push_back(MonitorID(active_displays[i]));
         }
     }
     monitors
diff --git a/src/win32/mod.rs b/src/win32/mod.rs
index e90f93f..75706f6 100644
--- a/src/win32/mod.rs
+++ b/src/win32/mod.rs
@@ -1,5 +1,6 @@
 use std::sync::atomic::AtomicBool;
 use std::ptr;
+use std::collections::RingBuf;
 use libc;
 use {CreationError, Event};
 
@@ -14,7 +15,7 @@ mod gl;
 mod init;
 mod monitor;
 
-/// 
+///
 pub struct HeadlessContext(Window);
 
 impl HeadlessContext {
@@ -105,7 +106,7 @@ impl Window {
     }
 
     /// See the docs in the crate root file.
-    /// 
+    ///
     /// Calls SetWindowText on the HWND.
     pub fn set_title(&self, text: &str) {
         unsafe {
@@ -200,11 +201,11 @@ impl Window {
 
     /// See the docs in the crate root file.
     // TODO: return iterator
-    pub fn poll_events(&self) -> Vec<Event> {
-        let mut events = Vec::new();
+    pub fn poll_events(&self) -> RingBuf<Event> {
+        let mut events = RingBuf::new();
         loop {
             match self.events_receiver.try_recv() {
-                Ok(ev) => events.push(ev),
+                Ok(ev) => events.push_back(ev),
                 Err(_) => break
             }
         }
@@ -214,13 +215,13 @@ impl Window {
             use std::sync::atomic::Relaxed;
             self.is_closed.store(true, Relaxed);
         }
-        
+
         events
     }
 
     /// See the docs in the crate root file.
     // TODO: return iterator
-    pub fn wait_events(&self) -> Vec<Event> {
+    pub fn wait_events(&self) -> RingBuf<Event> {
         match self.events_receiver.recv_opt() {
             Ok(ev) => {
                 // if the received event is `Closed`, setting `is_closed` to true
@@ -241,7 +242,7 @@ impl Window {
             Err(_) => {
                 use std::sync::atomic::Relaxed;
                 self.is_closed.store(true, Relaxed);
-                vec![]
+                RingBuf::new()
             }
         }
     }
diff --git a/src/win32/monitor.rs b/src/win32/monitor.rs
index f841f1e..82ee02a 100644
--- a/src/win32/monitor.rs
+++ b/src/win32/monitor.rs
@@ -1,5 +1,7 @@
 use winapi;
 
+use std::collections::RingBuf;
+
 /// Win32 implementation of the main `MonitorID` object.
 pub struct MonitorID {
     /// The system name of the monitor.
@@ -22,11 +24,11 @@ pub struct MonitorID {
 }
 
 /// Win32 implementation of the main `get_available_monitors` function.
-pub fn get_available_monitors() -> Vec<MonitorID> {
+pub fn get_available_monitors() -> RingBuf<MonitorID> {
     use std::{iter, mem, ptr};
 
     // return value
-    let mut result = Vec::new();
+    let mut result = RingBuf::new();
 
     // enumerating the devices is done by querying device 0, then device 1, then device 2, etc.
     //  until the query function returns null
@@ -78,7 +80,7 @@ pub fn get_available_monitors() -> Vec<MonitorID> {
         };
 
         // adding to the resulting list
-        result.push(MonitorID {
+        result.push_back(MonitorID {
             name: output.DeviceName,
             readable_name: readable_name,
             flags: output.StateFlags,
@@ -123,7 +125,7 @@ impl MonitorID {
     }
 
     /// This is a Win32-only function for `MonitorID` that returns the position of the
-    ///  monitor on the desktop. 
+    ///  monitor on the desktop.
     /// A window that is positionned at these coordinates will overlap the monitor.
     pub fn get_position(&self) -> (uint, uint) {
         self.position
diff --git a/src/x11/window/mod.rs b/src/x11/window/mod.rs
index fc622ea..768d480 100644
--- a/src/x11/window/mod.rs
+++ b/src/x11/window/mod.rs
@@ -5,6 +5,7 @@ use libc;
 use std::{mem, ptr};
 use std::cell::Cell;
 use std::sync::atomic::AtomicBool;
+use std::collections::RingBuf;
 use super::ffi;
 use std::sync::{Arc, Once, ONCE_INIT};
 
@@ -424,10 +425,10 @@ impl Window {
         }
     }
 
-    pub fn poll_events(&self) -> Vec<Event> {
+    pub fn poll_events(&self) -> RingBuf<Event> {
         use std::mem;
 
-        let mut events = Vec::new();
+        let mut events = RingBuf::new();
 
         loop {
             use std::num::Int;
@@ -456,9 +457,9 @@ impl Window {
 
                     if client_msg.l[0] == self.wm_delete_window as libc::c_long {
                         self.is_closed.store(true, Relaxed);
-                        events.push(Closed);
+                        events.push_back(Closed);
                     } else {
-                        events.push(Awakened);
+                        events.push_back(Awakened);
                     }
                 },
 
@@ -468,14 +469,14 @@ impl Window {
                     let (current_width, current_height) = self.current_size.get();
                     if current_width != cfg_event.width || current_height != cfg_event.height {
                         self.current_size.set((cfg_event.width, cfg_event.height));
-                        events.push(Resized(cfg_event.width as uint, cfg_event.height as uint));
+                        events.push_back(Resized(cfg_event.width as uint, cfg_event.height as uint));
                     }
                 },
 
                 ffi::MotionNotify => {
                     use events::Event::MouseMoved;
                     let event: &ffi::XMotionEvent = unsafe { mem::transmute(&xev) };
-                    events.push(MouseMoved((event.x as int, event.y as int)));
+                    events.push_back(MouseMoved((event.x as int, event.y as int)));
                 },
 
                 ffi::KeyPress | ffi::KeyRelease => {
@@ -504,7 +505,7 @@ impl Window {
                     };
 
                     for chr in written.as_slice().chars() {
-                        events.push(ReceivedCharacter(chr));
+                        events.push_back(ReceivedCharacter(chr));
                     }
 
                     let keysym = unsafe {
@@ -513,7 +514,7 @@ impl Window {
 
                     let vkey =  events::keycode_to_element(keysym as libc::c_uint);
 
-                    events.push(KeyboardInput(state, event.keycode as u8, vkey));
+                    events.push_back(KeyboardInput(state, event.keycode as u8, vkey));
                 },
 
                 ffi::ButtonPress | ffi::ButtonRelease => {
@@ -530,11 +531,11 @@ impl Window {
                         ffi::Button2 => Some(MiddleMouseButton),
                         ffi::Button3 => Some(RightMouseButton),
                         ffi::Button4 => {
-                            events.push(MouseWheel(1));
+                            events.push_back(MouseWheel(1));
                             None
                         }
                         ffi::Button5 => {
-                            events.push(MouseWheel(-1));
+                            events.push_back(MouseWheel(-1));
                             None
                         }
                         _ => None
@@ -542,7 +543,7 @@ impl Window {
 
                     match button {
                         Some(button) =>
-                            events.push(MouseInput(state, button)),
+                            events.push_back(MouseInput(state, button)),
                         None => ()
                     };
                 },
@@ -554,7 +555,7 @@ impl Window {
         events
     }
 
-    pub fn wait_events(&self) -> Vec<Event> {
+    pub fn wait_events(&self) -> RingBuf<Event> {
         use std::mem;
 
         loop {
diff --git a/src/x11/window/monitor.rs b/src/x11/window/monitor.rs
index f62a8ef..596dca7 100644
--- a/src/x11/window/monitor.rs
+++ b/src/x11/window/monitor.rs
@@ -1,10 +1,11 @@
-use std::{ptr};
+use std::ptr;
+use std::collections::RingBuf;
 use super::super::ffi;
 use super::ensure_thread_init;
 
 pub struct MonitorID(pub uint);
 
-pub fn get_available_monitors() -> Vec<MonitorID> {
+pub fn get_available_monitors() -> RingBuf<MonitorID> {
     ensure_thread_init();
     let nb_monitors = unsafe {
         let display = ffi::XOpenDisplay(ptr::null());
@@ -16,9 +17,9 @@ pub fn get_available_monitors() -> Vec<MonitorID> {
         nb_monitors
     };
 
-    let mut vec = Vec::new();
-    vec.grow_fn(nb_monitors as uint, |i| MonitorID(i));
-    vec
+    let mut monitors = RingBuf::new();
+    monitors.extend(range(0, nb_monitors).map(|i| MonitorID(i as uint)));
+    monitors
 }
 
 pub fn get_primary_monitor() -> MonitorID {