1 files changed, 129 insertions, 0 deletions
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 _))
+            }
+        }
+    }
+}