Implement Land2D::fill() + tests
authorunc0rr
Mon, 15 Oct 2018 23:10:03 +0200
changeset 13924 a140f28decc4
parent 13923 4d63acb2b978
child 13925 2ee07e751171
Implement Land2D::fill() + tests
rust/land2d/src/lib.rs
rust/vec2d/src/lib.rs
--- a/rust/land2d/src/lib.rs	Mon Oct 15 22:22:51 2018 +0300
+++ b/rust/land2d/src/lib.rs	Mon Oct 15 23:10:03 2018 +0200
@@ -8,7 +8,7 @@
     height_mask: usize,
 }
 
-impl<T: Default + Copy> Land2D<T> {
+impl<T: Default + Copy + PartialEq> Land2D<T> {
     pub fn new(width: usize, height: usize) -> Self {
         assert!(width.is_power_of_two());
         assert!(height.is_power_of_two());
@@ -21,7 +21,17 @@
     }
 
     #[inline]
-    fn is_valid_coordinate(&self, x: i32, y: i32) -> bool {
+    pub fn width(&self) -> usize {
+        self.pixels.width()
+    }
+
+    #[inline]
+    pub fn height(&self) -> usize {
+        self.pixels.height()
+    }
+
+    #[inline]
+    pub fn is_valid_coordinate(&self, x: i32, y: i32) -> bool {
         (x as usize & self.width_mask) == 0 && (y as usize & self.height_mask) == 0
     }
 
@@ -80,6 +90,83 @@
             self.map(y, x, |p| *p = value);
         }
     }
+
+    pub fn fill(&mut self, start_x: i32, start_y: i32, border_value: T, fill_value: T) {
+        debug_assert!(self.is_valid_coordinate(start_x - 1, start_y));
+        debug_assert!(self.is_valid_coordinate(start_x, start_y));
+
+        let mut stack: Vec<(usize, usize, usize, isize)> = Vec::new();
+        fn push<T: Default + Copy + PartialEq>(
+            land: &Land2D<T>,
+            stack: &mut Vec<(usize, usize, usize, isize)>,
+            xl: usize,
+            xr: usize,
+            y: usize,
+            dir: isize,
+        ) {
+            let yd = y as isize + dir;
+
+            if land.is_valid_coordinate(0, yd as i32) {
+                stack.push((xl, xr, yd as usize, dir));
+            }
+        };
+
+        let start_x_l = (start_x - 1) as usize;
+        let start_x_r = start_x as usize;
+        push(self, &mut stack, start_x_l, start_x_r, start_y as usize, -1);
+        push(self, &mut stack, start_x_l, start_x_r, start_y as usize, 1);
+
+        loop {
+            let a = stack.pop();
+            match a {
+                None => return,
+                Some(a) => {
+                    let (mut xl, mut xr, y, mut dir) = a;
+
+                    while xl > 0 && self
+                        .pixels
+                        .get(y, xl)
+                        .map_or(false, |v| *v != border_value && *v != fill_value)
+                    {
+                        xl -= 1;
+                    }
+
+                    while xr < self.width() - 1 && self
+                        .pixels
+                        .get(y, xr)
+                        .map_or(false, |v| *v != border_value && *v != fill_value)
+                    {
+                        xr += 1;
+                    }
+
+                    while xl < xr {
+                        while xl <= xr
+                            && (self.pixels[y][xl] == border_value
+                                || self.pixels[y][xl] == fill_value)
+                        {
+                            xl += 1;
+                        }
+
+                        let mut x = xl;
+
+                        while xl <= xr
+                            && (self.pixels[y][xl] != border_value
+                                && self.pixels[y][xl] != fill_value)
+                        {
+                            self.pixels[y][xl] = fill_value;
+
+                            xl += 1;
+                        }
+
+                        if x < xl {
+                            push(self, &mut stack, x, xl - 1, y, dir);
+                            push(self, &mut stack, x, xl - 1, y, -dir);
+                        }
+                    }
+                }
+            }
+        }
+    }
 }
 
 #[cfg(test)]
@@ -88,7 +175,7 @@
 
     #[test]
     fn basics() {
-        let  l:Land2D<u8> = Land2D::new(32, 64);
+        let l: Land2D<u8> = Land2D::new(32, 64);
 
         assert!(l.is_valid_coordinate(0, 0));
         assert!(!l.is_valid_coordinate(-1, -1));
@@ -98,4 +185,34 @@
         assert!(!l.is_valid_coordinate(31, 64));
     }
 
+    #[test]
+    fn fill() {
+        let mut l: Land2D<u8> = Land2D::new(128, 128);
+
+        l.draw_line(0, 0, 32, 96, 1);
+        l.draw_line(32, 96, 64, 32, 1);
+        l.draw_line(64, 32, 96, 80, 1);
+        l.draw_line(96, 80, 128, 0, 1);
+
+        l.draw_line(0, 128, 64, 96, 1);
+        l.draw_line(128, 128, 64, 96, 1);
+
+        l.fill(32, 32, 1, 2);
+        l.fill(16, 96, 1, 3);
+        l.fill(60, 100, 1, 4);
+
+        assert_eq!(l.pixels[0][0], 1);
+        assert_eq!(l.pixels[96][64], 1);
+
+        assert_eq!(l.pixels[40][32], 2);
+        assert_eq!(l.pixels[40][96], 2);
+        assert_eq!(l.pixels[5][0], 3);
+        assert_eq!(l.pixels[120][0], 3);
+        assert_eq!(l.pixels[5][127], 3);
+        assert_eq!(l.pixels[120][127], 3);
+        assert_eq!(l.pixels[35][64], 3);
+        assert_eq!(l.pixels[120][20], 4);
+        assert_eq!(l.pixels[120][100], 4);
+        assert_eq!(l.pixels[100][64], 4);
+    }
 }
--- a/rust/vec2d/src/lib.rs	Mon Oct 15 22:22:51 2018 +0300
+++ b/rust/vec2d/src/lib.rs	Mon Oct 15 23:10:03 2018 +0200
@@ -54,6 +54,11 @@
     pub fn get_mut(&mut self, row: usize, column: usize) -> Option<&mut <usize as SliceIndex<[T]>>::Output> {
         self.data.get_mut(row * self.width + column)
     }
+
+    #[inline]
+    pub fn get(&self, row: usize, column: usize) -> Option<&<usize as SliceIndex<[T]>>::Output> {
+        self.data.get(row * self.width + column)
+    }
 }
 
 #[cfg(test)]