...

3 files changed, 168 insertions, 7 deletions

diff --git a/Cargo.lock b/Cargo.lock
index 34e5a1d..0ba1546 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -25,6 +25,12 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "1d49d90015b3c36167a20fe2810c5cd875ad504b39cff3d4eae7977e6b7c1cb2"
 
 [[package]]
+name = "autocfg"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "f8aac770f1885fd7e387acedd76065302551364496e46b3dd00860b2f8359b9d"
+
+[[package]]
 name = "bitflags"
 version = "1.2.1"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -94,6 +100,7 @@ version = "0.1.0"
 dependencies = [
  "crc",
  "hex",
+ "indexmap",
  "libc",
  "lru",
  "nix",
@@ -109,7 +116,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "8e6073d0ca812575946eb5f35ff68dbe519907b25c42530389ff946dc84c6ead"
 dependencies = [
  "ahash",
- "autocfg",
+ "autocfg 0.1.7",
 ]
 
 [[package]]
@@ -119,6 +126,15 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "644f9158b2f133fd50f5fb3242878846d9eb792e445c893805ff0e3824006e35"
 
 [[package]]
+name = "indexmap"
+version = "1.4.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+checksum = "c398b2b113b55809ceb9ee3e753fcbac793f1956663f3c36549c1346015c2afe"
+dependencies = [
+ "autocfg 1.0.0",
+]
+
+[[package]]
 name = "lazy_static"
 version = "1.4.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
diff --git a/Cargo.toml b/Cargo.toml
index 1a60577..7eae306 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -17,6 +17,7 @@ hex = "0.4.2"
 libc = "0.2.44"
 nix = "0.17.0"
 rand = "0.7.3"
+indexmap = "1.4.0"
 
 [lib]
 name = "growthring"
diff --git a/tests/common/mod.rs b/tests/common/mod.rs
index 2fd7bbb..209e8af 100644
--- a/tests/common/mod.rs
+++ b/tests/common/mod.rs
@@ -3,11 +3,14 @@
 
 extern crate growthring;
 use growthring::wal::{WALFile, WALStore, WALPos, WALBytes};
-use std::collections::{HashMap, hash_map::Entry};
+use indexmap::{IndexMap, map::Entry};
+use rand::Rng;
+use std::collections::{HashMap, hash_map};
 use std::cell::RefCell;
 use std::rc::Rc;
+use std::convert::TryInto;
+use std::collections::VecDeque;
 
-/*
 thread_local! {
     //pub static RNG: RefCell<rand::rngs::StdRng> = RefCell::new(<rand::rngs::StdRng as rand::SeedableRng>::from_seed([0; 32]));
     pub static RNG: RefCell<rand::rngs::ThreadRng> = RefCell::new(rand::thread_rng());
@@ -16,10 +19,9 @@ thread_local! {
 pub fn gen_rand_letters(i: usize) -> String {
     //let mut rng = rand::thread_rng();
     RNG.with(|rng| {
-        (0..i).map(|_| (rng.borrow_mut().gen::<u8>() % 26 + 'a' as u8) as char).collect()
+        (0..i).map(|_| (rng.borrow_mut().gen_range(0, 26) + 'a' as u8) as char).collect()
     })
 }
-*/
 
 struct FileContentEmul(RefCell<Vec<u8>>);
 
@@ -103,11 +105,11 @@ impl<'a, G: 'static + FailGen> WALStore for WALStoreEmul<'a, G> {
     fn open_file(&mut self, filename: &str, touch: bool) -> Result<Box<dyn WALFile>, ()> {
         if self.fgen.next_fail() { return Err(()) }
         match self.state.files.entry(filename.to_string()) {
-            Entry::Occupied(e) => Ok(Box::new(WALFileEmul {
+            hash_map::Entry::Occupied(e) => Ok(Box::new(WALFileEmul {
                 file: e.get().clone(),
                 fgen: self.fgen.clone()
             })),
-            Entry::Vacant(e) => if touch {
+            hash_map::Entry::Vacant(e) => if touch {
                 Ok(Box::new(WALFileEmul {
                     file: e.insert(Rc::new(FileContentEmul::new())).clone(),
                     fgen: self.fgen.clone()
@@ -166,3 +168,145 @@ pub struct ZeroFailGen;
 impl FailGen for ZeroFailGen {
     fn next_fail(&self) -> bool { false }
 }
+
+/// An ordered list of intervals: `(begin, end, color)*`.
+pub struct PaintStrokes(Vec<(u32, u32, u32)>);
+
+impl PaintStrokes {
+    pub fn new() -> Self { PaintStrokes(Vec::new()) }
+    pub fn to_bytes(&self) -> WALBytes {
+        let mut res: Vec<u8> = Vec::new();
+        let is = std::mem::size_of::<u32>();
+        let len = self.0.len() as u32;
+        res.resize(is * (1 + 3 * self.0.len()), 0);
+        let mut rs = &mut res[..];
+        &mut rs[..is].copy_from_slice(&len.to_le_bytes());
+        rs = &mut rs[is..];
+        for (s, e, c) in self.0.iter() {
+            &mut rs[..is].copy_from_slice(&s.to_le_bytes());
+            &mut rs[is..is * 2].copy_from_slice(&e.to_le_bytes());
+            &mut rs[is * 2..is * 3].copy_from_slice(&c.to_le_bytes());
+            rs = &mut rs[is * 3..];
+        }
+        res.into_boxed_slice()
+    }
+
+    pub fn from_bytes(raw: &[u8]) -> Self {
+        assert!(raw.len() > 4);
+        assert!(raw.len() & 3 == 0);
+        let is = std::mem::size_of::<u32>();
+        let (len_raw, mut rest) = raw.split_at(is);
+        let len = u32::from_le_bytes(len_raw.try_into().unwrap());
+        let mut res = Vec::new();
+        for _ in 0..len {
+            let (s_raw, rest1) = rest.split_at(is);
+            let (e_raw, rest2) = rest1.split_at(is);
+            let (c_raw, rest3) = rest2.split_at(is);
+            res.push((u32::from_le_bytes(s_raw.try_into().unwrap()),
+                    u32::from_le_bytes(e_raw.try_into().unwrap()),
+                    u32::from_le_bytes(c_raw.try_into().unwrap())));
+            rest = rest3
+        }
+        PaintStrokes(res)
+    }
+    
+    pub fn stroke(&mut self, start: u32, end: u32, color: u32) {
+        self.0.push((start, end, color))
+    }
+
+    pub fn into_vec(self) -> Vec<(u32, u32, u32)> { self.0 }
+}
+
+#[test]
+fn test_paint_strokes() {
+    let mut p = PaintStrokes::new();
+    for i in 0..3 {
+        p.stroke(i, i + 3, i + 10)
+    }
+    let pr = p.to_bytes();
+    for ((s, e, c), i) in PaintStrokes::from_bytes(&pr)
+                            .into_vec().into_iter().zip(0..) {
+        assert_eq!(s, i);
+        assert_eq!(e, i + 3);
+        assert_eq!(c, i + 10);
+    }
+}
+
+type CanvasTrace = Vec<(u32, u32)>;
+
+pub struct Canvas {
+    queue: IndexMap<u32, VecDeque<u32>>,
+    canvas: Box<[u32]>
+}
+
+impl Canvas {
+    pub fn new(size: usize) -> Self {
+        let mut canvas = Vec::new();
+        // fill the backgroudn color 0
+        canvas.resize(size, 0);
+        let canvas = canvas.into_boxed_slice();
+        Canvas {
+            queue: IndexMap::new(),
+            canvas
+        }
+    }
+
+    fn get_queued(&mut self, pos: u32) -> &mut VecDeque<u32> {
+        match self.queue.entry(pos) {
+            Entry::Occupied(e) => e.into_mut(),
+            Entry::Vacant(e) => e.insert(VecDeque::new())
+        }
+    }
+
+    pub fn prepaint(&mut self, strokes: &PaintStrokes) {
+        for (s, e, c) in strokes.0.iter() {
+            for i in *s..*e {
+                self.get_queued(i).push_back(*c)
+            }
+        }
+    }
+
+    // TODO: allow customized scheduler
+    pub fn rand_paint<R: rand::Rng>(&mut self, rng: &mut R) -> u32 {
+        println!("{}", self.queue.len());
+        let idx = rng.gen_range(0, self.queue.len());
+        let (pos, _) = self.queue.get_index_mut(idx).unwrap();
+        let pos = *pos;
+        self.paint(pos);
+        pos
+    }
+
+    pub fn paint(&mut self, pos: u32) {
+        let q = self.queue.get_mut(&pos).unwrap();
+        self.canvas[pos as usize] = q.pop_front().unwrap();
+        if q.is_empty() { self.queue.remove(&pos); }
+    }
+
+    pub fn is_same(&self, other: &Canvas) -> bool {
+        self.canvas.cmp(&other.canvas) == std::cmp::Ordering::Equal
+    }
+}
+
+#[test]
+fn test_canvas() {
+    let mut canvas1 = Canvas::new(10);
+    let mut canvas2 = Canvas::new(10);
+    let canvas3 = Canvas::new(11);
+    let mut s1 = PaintStrokes::new();
+    s1.stroke(0, 1, 1);
+    let mut s2 = PaintStrokes::new();
+    s2.stroke(1, 2, 2);
+    assert!(canvas1.is_same(&canvas2));
+    assert!(!canvas2.is_same(&canvas3));
+    canvas1.prepaint(&s1);
+    canvas1.prepaint(&s2);
+    canvas2.prepaint(&s1);
+    canvas2.prepaint(&s2);
+    assert!(canvas1.is_same(&canvas2));
+    RNG.with(|rng| canvas1.rand_paint(&mut *rng.borrow_mut()));
+    assert!(!canvas1.is_same(&canvas2));
+    RNG.with(|rng| canvas1.rand_paint(&mut *rng.borrow_mut()));
+    RNG.with(|rng| canvas2.rand_paint(&mut *rng.borrow_mut()));
+    RNG.with(|rng| canvas2.rand_paint(&mut *rng.borrow_mut()));
+    assert!(canvas1.is_same(&canvas2));
+}