From c61a912f6221a320ec4787cd883527b0e7f26a8e Mon Sep 17 00:00:00 2001 From: Joe Wilm Date: Sat, 19 May 2018 11:18:37 -0700 Subject: Optimize Row::reset Now, only cells that have been used are cleared. This is achieved by using a "occupied" memo on the Row itself. The value, `occ`, is updated wherever the Row is accessed mutably, and it's cleared to zero in Row::reset. The tests for grid scroll_up and scroll_down were updated to include a test on the value `occ` and slightly refactored, but are otherwise equivalent to the previous implementation of those tests. Because of the change to the `Row` struct, the ref tests were updated so Deserialization keeps working as expected. --- src/grid/row.rs | 96 ++++++++++++++++++++++++++++++++++--------------------- src/grid/tests.rs | 92 +++++++++++++++++++++++++++------------------------- 2 files changed, 108 insertions(+), 80 deletions(-) (limited to 'src/grid') diff --git a/src/grid/row.rs b/src/grid/row.rs index 55c82a0d..ea8804a7 100644 --- a/src/grid/row.rs +++ b/src/grid/row.rs @@ -14,43 +14,78 @@ //! Defines the Row type which makes up lines in the grid -use std::ops::{Deref, DerefMut, Index, IndexMut}; +use std::ops::{Index, IndexMut}; use std::ops::{Range, RangeTo, RangeFrom, RangeFull}; +use std::cmp::{max, min}; use std::slice; use index::Column; /// A row in the grid -#[derive(Default, Clone, Debug, Serialize, Deserialize, Eq, PartialEq)] -pub struct Row(Vec); +#[derive(Default, Clone, Debug, Serialize, Deserialize)] +pub struct Row { + inner: Vec, + + /// occupied entries + /// + /// Semantically, this value can be understood as the **end** of an + /// Exclusive Range. Thus, + /// + /// - Zero means there are no occupied entries + /// - 1 means there is a value at index zero, but nowhere else + /// - `occ == inner.len` means every value is occupied + pub(crate) occ: usize, +} + +impl PartialEq for Row { + fn eq(&self, other: &Self) -> bool { + self.inner == other.inner + } +} impl Row { pub fn new(columns: Column, template: &T) -> Row { - Row(vec![*template; *columns]) + Row { + inner: vec![*template; *columns], + occ: 0, + } } pub fn grow(&mut self, cols: Column, template: &T) { assert!(self.len() < * cols); while self.len() != *cols { - self.0.push(*template); + self.inner.push(*template); } } /// Resets contents to the contents of `other` - #[inline] + #[inline(never)] pub fn reset(&mut self, other: &T) { - for item in &mut self.0 { + let occ = self.occ; + for item in &mut self.inner[..occ] { *item = *other; } + + self.occ = 0; } } impl Row { pub fn shrink(&mut self, cols: Column) { while self.len() != *cols { - self.pop(); + self.inner.pop(); } + + self.occ = min(self.occ, *cols); + } + + pub fn len(&self) -> usize { + self.inner.len() + } + + pub fn iter<'a>(&'a self) -> slice::Iter<'a, T> { + self.inner.iter() } } @@ -71,24 +106,8 @@ impl<'a, T> IntoIterator for &'a mut Row { #[inline] fn into_iter(self) -> slice::IterMut<'a, T> { - self.iter_mut() - } -} - -impl Deref for Row { - type Target = Vec; - - #[inline] - fn deref(&self) -> &Self::Target { - &self.0 - } -} - - -impl DerefMut for Row { - #[inline] - fn deref_mut(&mut self) -> &mut Self::Target { - &mut self.0 + self.occ = self.len(); + self.inner.iter_mut() } } @@ -97,14 +116,15 @@ impl Index for Row { #[inline] fn index(&self, index: Column) -> &T { - &self.0[index.0] + &self.inner[index.0] } } impl IndexMut for Row { #[inline] fn index_mut(&mut self, index: Column) -> &mut T { - &mut self.0[index.0] + self.occ = max(self.occ, *index + 1); + &mut self.inner[index.0] } } @@ -117,14 +137,15 @@ impl Index> for Row { #[inline] fn index(&self, index: Range) -> &[T] { - &self.0[(index.start.0)..(index.end.0)] + &self.inner[(index.start.0)..(index.end.0)] } } impl IndexMut> for Row { #[inline] fn index_mut(&mut self, index: Range) -> &mut [T] { - &mut self.0[(index.start.0)..(index.end.0)] + self.occ = max(self.occ, *index.end); + &mut self.inner[(index.start.0)..(index.end.0)] } } @@ -133,14 +154,15 @@ impl Index> for Row { #[inline] fn index(&self, index: RangeTo) -> &[T] { - &self.0[..(index.end.0)] + &self.inner[..(index.end.0)] } } impl IndexMut> for Row { #[inline] fn index_mut(&mut self, index: RangeTo) -> &mut [T] { - &mut self.0[..(index.end.0)] + self.occ = max(self.occ, *index.end); + &mut self.inner[..(index.end.0)] } } @@ -149,14 +171,15 @@ impl Index> for Row { #[inline] fn index(&self, index: RangeFrom) -> &[T] { - &self.0[(index.start.0)..] + &self.inner[(index.start.0)..] } } impl IndexMut> for Row { #[inline] fn index_mut(&mut self, index: RangeFrom) -> &mut [T] { - &mut self.0[(index.start.0)..] + self.occ = self.len(); + &mut self.inner[(index.start.0)..] } } @@ -165,13 +188,14 @@ impl Index for Row { #[inline] fn index(&self, _: RangeFull) -> &[T] { - &self.0[..] + &self.inner[..] } } impl IndexMut for Row { #[inline] fn index_mut(&mut self, _: RangeFull) -> &mut [T] { - &mut self.0[..] + self.occ = self.len(); + &mut self.inner[..] } } diff --git a/src/grid/tests.rs b/src/grid/tests.rs index 3e229fb6..435f0c3d 100644 --- a/src/grid/tests.rs +++ b/src/grid/tests.rs @@ -20,73 +20,77 @@ use index::{Point, Line, Column}; // Scroll up moves lines upwards #[test] fn scroll_up() { - info!(""); + println!(""); let mut grid = Grid::new(Line(10), Column(1), 0, 0); for i in 0..10 { grid[Line(i)][Column(0)] = i; } - info!("grid: {:?}", grid); + println!("grid: {:?}", grid); grid.scroll_up(&(Line(0)..Line(10)), Line(2), &0); - info!("grid: {:?}", grid); - - let mut other = Grid::new(Line(10), Column(1), 0, 9); - - other[Line(0)][Column(0)] = 2; - other[Line(1)][Column(0)] = 3; - other[Line(2)][Column(0)] = 4; - other[Line(3)][Column(0)] = 5; - other[Line(4)][Column(0)] = 6; - other[Line(5)][Column(0)] = 7; - other[Line(6)][Column(0)] = 8; - other[Line(7)][Column(0)] = 9; - other[Line(8)][Column(0)] = 0; // should be cleared on scroll; was 0 - other[Line(9)][Column(0)] = 0; // should be cleared on scroll; was 1 - - for i in 0..10 { - assert_eq!(grid[Line(i)][Column(0)], other[Line(i)][Column(0)], - "index={}; actual: {:?}, expected: {:?}", - Line(i), grid[Line(i)][Column(0)], other[Line(i)][Column(0)]); - } + println!("grid: {:?}", grid); + + assert_eq!(grid[Line(0)][Column(0)], 2); + assert_eq!(grid[Line(0)].occ, 1); + assert_eq!(grid[Line(1)][Column(0)], 3); + assert_eq!(grid[Line(1)].occ, 1); + assert_eq!(grid[Line(2)][Column(0)], 4); + assert_eq!(grid[Line(2)].occ, 1); + assert_eq!(grid[Line(3)][Column(0)], 5); + assert_eq!(grid[Line(3)].occ, 1); + assert_eq!(grid[Line(4)][Column(0)], 6); + assert_eq!(grid[Line(4)].occ, 1); + assert_eq!(grid[Line(5)][Column(0)], 7); + assert_eq!(grid[Line(5)].occ, 1); + assert_eq!(grid[Line(6)][Column(0)], 8); + assert_eq!(grid[Line(6)].occ, 1); + assert_eq!(grid[Line(7)][Column(0)], 9); + assert_eq!(grid[Line(7)].occ, 1); + assert_eq!(grid[Line(8)][Column(0)], 0); // was 0 + assert_eq!(grid[Line(8)].occ, 0); + assert_eq!(grid[Line(9)][Column(0)], 0); // was 1 + assert_eq!(grid[Line(9)].occ, 0); } // Scroll down moves lines downwards #[test] fn scroll_down() { - info!(""); + println!(""); let mut grid = Grid::new(Line(10), Column(1), 0, 0); for i in 0..10 { grid[Line(i)][Column(0)] = i; } - info!("grid: {:?}", grid); + println!("grid: {:?}", grid); grid.scroll_down(&(Line(0)..Line(10)), Line(2), &0); - info!("grid: {:?}", grid); - - let mut other = Grid::new(Line(10), Column(1), 0, 9); - - other[Line(0)][Column(0)] = 0; // Should be cleared upon recycle; was 8 - other[Line(1)][Column(0)] = 0; // Should be cleared upon recycle; was 9 - other[Line(2)][Column(0)] = 0; - other[Line(3)][Column(0)] = 1; - other[Line(4)][Column(0)] = 2; - other[Line(5)][Column(0)] = 3; - other[Line(6)][Column(0)] = 4; - other[Line(7)][Column(0)] = 5; - other[Line(8)][Column(0)] = 6; - other[Line(9)][Column(0)] = 7; - - for i in 0..10 { - assert_eq!(grid[Line(i)][Column(0)], other[Line(i)][Column(0)], - "index={}; actual: {:?}, expected: {:?}", - Line(i), grid[Line(i)][Column(0)], other[Line(i)][Column(0)]); - } + println!("grid: {:?}", grid); + + assert_eq!(grid[Line(0)][Column(0)], 0); // was 8 + assert_eq!(grid[Line(0)].occ, 0); + assert_eq!(grid[Line(1)][Column(0)], 0); // was 9 + assert_eq!(grid[Line(1)].occ, 0); + assert_eq!(grid[Line(2)][Column(0)], 0); + assert_eq!(grid[Line(2)].occ, 1); + assert_eq!(grid[Line(3)][Column(0)], 1); + assert_eq!(grid[Line(3)].occ, 1); + assert_eq!(grid[Line(4)][Column(0)], 2); + assert_eq!(grid[Line(4)].occ, 1); + assert_eq!(grid[Line(5)][Column(0)], 3); + assert_eq!(grid[Line(5)].occ, 1); + assert_eq!(grid[Line(6)][Column(0)], 4); + assert_eq!(grid[Line(6)].occ, 1); + assert_eq!(grid[Line(7)][Column(0)], 5); + assert_eq!(grid[Line(7)].occ, 1); + assert_eq!(grid[Line(8)][Column(0)], 6); + assert_eq!(grid[Line(8)].occ, 1); + assert_eq!(grid[Line(9)][Column(0)], 7); + assert_eq!(grid[Line(9)].occ, 1); } // Test that GridIterator works -- cgit v1.2.3-54-g00ecf