WIP optimize scroll in region

This intends to optimize the case where the top of the scrolling region
is the top of the screen. In theory, scrolling in this case can be
optimized to shifting the start/end of the visible region, and then
rearranging any lines that were not supposed to be scrolled (at the
bottom of the region). However, this didn't produce quite the speedup I
expected.

2 files changed, 187 insertions, 32 deletions

diff --git a/src/grid/mod.rs b/src/grid/mod.rs
index e790dd41..8e30915c 100644
--- a/src/grid/mod.rs
+++ b/src/grid/mod.rs
@@ -21,7 +21,6 @@
 //! ranges is currently supported.
 
 use std::cmp::Ordering;
-use std::collections::{VecDeque, vec_deque};
 use std::iter::IntoIterator;
 use std::ops::{Deref, Range, RangeTo, RangeFrom, RangeFull, Index, IndexMut};
 
@@ -33,6 +32,9 @@ pub use self::row::Row;
 #[cfg(test)]
 mod tests;
 
+mod storage;
+use self::storage::Storage;
+
 /// Convert a type to a linear index range.
 pub trait ToRange {
     fn to_range(&self) -> RangeInclusive<index::Linear>;
@@ -64,7 +66,7 @@ impl<T> Deref for Indexed<T> {
 pub struct Grid<T> {
     /// Lines in the grid. Each row holds a list of cells corresponding to the
     /// columns in that row.
-    raw: VecDeque<Row<T>>,
+    raw: Storage<Row<T>>,
 
     /// Number of columns
     cols: index::Column,
@@ -82,6 +84,9 @@ pub struct Grid<T> {
 
     /// Template cell for populating template_row
     template: T,
+
+    /// Temporary row storage for scrolling with a region
+    temp: Vec<Row<T>>,
 }
 
 pub struct GridIterator<'a, T: 'a> {
@@ -91,10 +96,10 @@ pub struct GridIterator<'a, T: 'a> {
 
 impl<T: Copy + Clone> Grid<T> {
     pub fn new(lines: index::Line, cols: index::Column, template: T) -> Grid<T> {
-        let mut raw = VecDeque::with_capacity(*lines);
+        let mut raw = Storage::with_capacity(*lines);
         let template_row = Row::new(cols, &template);
         for _ in IndexRange(index::Line(0)..lines) {
-            raw.push_back(template_row.clone());
+            raw.push(template_row.clone());
         }
 
         Grid {
@@ -103,6 +108,7 @@ impl<T: Copy + Clone> Grid<T> {
             lines,
             template_row,
             template,
+            temp: Vec::new(),
         }
     }
 
@@ -127,7 +133,7 @@ impl<T: Copy + Clone> Grid<T> {
 
     fn grow_lines(&mut self, lines: index::Line) {
         for _ in IndexRange(self.num_lines()..lines) {
-            self.raw.push_back(self.template_row.clone());
+            self.raw.push(self.template_row.clone());
         }
 
         self.lines = lines;
@@ -147,12 +153,25 @@ impl<T: Copy + Clone> Grid<T> {
 
     #[inline]
     pub fn scroll_down(&mut self, region: &Range<index::Line>, positions: index::Line) {
-        if region.start == Line(0) && region.end == self.num_lines() {
-            // Full rotation
-            for _ in 0..positions.0 {
-                let mut item = self.raw.pop_back().unwrap();
-                item.reset(&self.template_row);
-                self.raw.push_front(item);
+        // Whether or not there is a scrolling region active, as long as it
+        // starts at the top, we can do a full rotation which just involves
+        // changing the start index.
+        //
+        // To accomodate scroll regions, rows are reordered at the end.
+        if region.start == Line(0) {
+            // Rotate the entire line buffer. If there's a scrolling region
+            // active, the bottom lines are restored in the next step.
+            self.raw.rotate(-(*positions as isize));
+
+            // Now, restore any scroll region lines
+            for i in IndexRange(region.end .. self.num_lines()) {
+                // First do the swap
+                self.raw.swap(*i, *i + *positions);
+            }
+
+            // Finally, reset recycled lines
+            for i in 0..*positions {
+                self.raw[i].reset(&self.template_row);
             }
         } else {
             // Subregion rotation
@@ -160,23 +179,33 @@ impl<T: Copy + Clone> Grid<T> {
                 self.swap_lines(line, line - positions);
             }
 
-            let template = &self.template_row;
             for i in IndexRange(Line(0)..positions) {
-                self.raw
-                    .get_mut(*(region.start + i))
-                    .map(|row| row.reset(template));
+                self.raw[*(region.start - i - 1)].reset(&self.template_row);
             }
         }
     }
 
     #[inline]
     pub fn scroll_up(&mut self, region: &Range<index::Line>, positions: index::Line) {
-        if region.start == Line(0) && region.end == self.num_lines() {
-            // Full rotation
-            for _ in 0..positions.0 {
-                let mut item = self.raw.pop_front().unwrap();
-                item.reset(&self.template_row);
-                self.raw.push_back(item);
+        if region.start == Line(0) {
+            // Rotate the entire line buffer. If there's a scrolling region
+            // active, the bottom lines are restored in the next step.
+            self.raw.rotate(*positions as isize);
+
+            // Now, restore any lines outside the scroll region
+            let mut i = 0;
+            for _ in IndexRange(region.end .. self.num_lines()) {
+                let idx = *self.num_lines() - i - 1;
+                // First do the swap
+                self.raw.swap(idx, idx - *positions);
+                i += 1;
+            }
+
+            // Finally, reset recycled lines
+            //
+            // Recycled lines are just above the end of the scrolling region.
+            for i in 0..*positions {
+                self.raw[*region.end - i - 1].reset(&self.template_row);
             }
         } else {
             // Subregion rotation
@@ -185,11 +214,8 @@ impl<T: Copy + Clone> Grid<T> {
             }
 
             // Clear reused lines
-            let template = &self.template_row;
             for i in IndexRange(Line(0)..positions) {
-                self.raw
-                    .get_mut(*(region.end - i - 1))
-                    .map(|row| row.reset(template));
+                self.raw[*(region.start - i - 1)].reset(&self.template_row);
             }
         }
     }
@@ -229,7 +255,7 @@ impl<T> Grid<T> {
 
     fn shrink_lines(&mut self, lines: index::Line) {
         while index::Line(self.raw.len()) != lines {
-            self.raw.pop_back();
+            self.raw.pop();
         }
 
         self.lines = lines;
@@ -322,10 +348,10 @@ impl<'point, T> IndexMut<&'point Point> for Grid<T> {
 
 impl<'a, T> IntoIterator for &'a Grid<T> {
     type Item = &'a Row<T>;
-    type IntoIter = vec_deque::Iter<'a, Row<T>>;
+    type IntoIter = self::storage::Iter<'a, Row<T>>;
 
     #[inline]
-    fn into_iter(self) -> vec_deque::Iter<'a, Row<T>> {
+    fn into_iter(self) -> self::storage::Iter<'a, Row<T>> {
         self.raw.iter()
     }
 }
@@ -340,7 +366,7 @@ impl<'a, T> IntoIterator for &'a Grid<T> {
 pub struct Region<'a, T: 'a> {
     start: Line,
     end: Line,
-    raw: &'a VecDeque<Row<T>>,
+    raw: &'a Storage<Row<T>>,
 }
 
 /// A mutable subset of lines in the grid
@@ -349,7 +375,7 @@ pub struct Region<'a, T: 'a> {
 pub struct RegionMut<'a, T: 'a> {
     start: Line,
     end: Line,
-    raw: &'a mut VecDeque<Row<T>>,
+    raw: &'a mut Storage<Row<T>>,
 }
 
 impl<'a, T> RegionMut<'a, T> {
@@ -453,13 +479,13 @@ impl<T> IndexRegion<RangeFull, T> for Grid<T> {
 pub struct RegionIter<'a, T: 'a> {
     end: Line,
     cur: Line,
-    raw: &'a VecDeque<Row<T>>,
+    raw: &'a Storage<Row<T>>,
 }
 
 pub struct RegionIterMut<'a, T: 'a> {
     end: Line,
     cur: Line,
-    raw: &'a mut VecDeque<Row<T>>,
+    raw: &'a mut Storage<Row<T>>,
 }
 
 impl<'a, T> IntoIterator for Region<'a, T> {
diff --git a/src/grid/storage.rs b/src/grid/storage.rs
new file mode 100644
index 00000000..f5c2d87e
--- /dev/null
+++ b/src/grid/storage.rs
@@ -0,0 +1,129 @@
+/// Wrapper around Vec which supports fast indexing and rotation
+///
+/// The rotation implemented by grid::Storage is a simple integer addition.
+/// Compare with standard library rotation which requires rearranging items in
+/// memory.
+///
+/// As a consequence, the indexing operators need to be reimplemented for this
+/// type to account for the 0th element not always being at the start of the
+/// allocation.
+///
+/// Because certain Vec operations are no longer valid on this type, no Deref
+/// implementation is provided. Anything from Vec that should be exposed must be
+/// done so manually.
+use std::ops::{Index, IndexMut};
+
+#[derive(Clone, Debug, Deserialize, Serialize, Eq, PartialEq)]
+pub struct Storage<T> {
+    inner: Vec<T>,
+    zero: usize,
+}
+
+impl<T> Storage<T> {
+    #[inline]
+    pub fn with_capacity(cap: usize) -> Storage<T> {
+        Storage {
+            inner: Vec::with_capacity(cap),
+            zero: 0
+        }
+    }
+
+    #[inline]
+    pub fn push(&mut self, item: T) {
+        self.inner.push(item)
+    }
+
+    #[inline]
+    pub fn pop(&mut self) -> Option<T> {
+        self.inner.pop()
+    }
+
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.inner.len()
+    }
+
+    /// Compute actual index in underlying storage given the requested index.
+    #[inline]
+    fn compute_index(&self, requested: usize) -> usize {
+        (requested + self.zero) % self.len()
+    }
+
+    pub fn swap(&mut self, a: usize, b: usize) {
+        let a = self.compute_index(a);
+        let b = self.compute_index(b);
+        self.inner.swap(a, b);
+    }
+
+    pub fn iter(&self) -> Iter<T> {
+        Iter { storage: self, index: 0 }
+    }
+
+    pub fn iter_mut(&mut self) -> IterMut<T> {
+        IterMut { storage: self, index: 0 }
+    }
+
+    pub fn rotate(&mut self, count: isize) {
+        let len = self.len();
+        assert!(count.abs() as usize <= len);
+        self.zero += (count + len as isize) as usize % len;
+    }
+}
+
+impl<T> Index<usize> for Storage<T> {
+    type Output = T;
+    #[inline]
+    fn index(&self, index: usize) -> &T {
+        let index = self.compute_index(index); // borrowck
+        &self.inner[index]
+    }
+}
+
+impl<T> IndexMut<usize> for Storage<T> {
+    #[inline]
+    fn index_mut(&mut self, index: usize) -> &mut T {
+        let index = self.compute_index(index); // borrowck
+        &mut self.inner[index]
+    }
+}
+
+pub struct Iter<'a, T: 'a> {
+    storage: &'a Storage<T>,
+    index: usize,
+}
+
+pub struct IterMut<'a, T: 'a> {
+    storage: &'a mut Storage<T>,
+    index: usize,
+}
+
+impl<'a, T: 'a> Iterator for Iter<'a, T> {
+    type Item = &'a T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.index == self.storage.len() {
+            None
+        } else {
+            let res = Some(&self.storage[self.index]);
+            self.index += 1;
+            res
+        }
+    }
+}
+
+impl<'a, T: 'a> Iterator for IterMut<'a, T> {
+    type Item = &'a mut T;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        if self.index == self.storage.len() {
+            None
+        } else {
+            let index = self.index;
+            self.index += 1;
+
+            unsafe {
+                Some(&mut *(&mut self.storage[index] as *mut _))
+            }
+        }
+    }
+}