From 2b89b786a97b788ef8063b2777c6bc65a207033f Mon Sep 17 00:00:00 2001
From: Akshay <nerdy@peppe.rs>
Date: Fri, 2 Apr 2021 12:36:30 +0530
Subject: fix rare index error, more functional flood fill algo

---
 src/bitmap.rs | 39 ++++++++++++++++++++++-----------------
 1 file changed, 22 insertions(+), 17 deletions(-)

(limited to 'src/bitmap.rs')

diff --git a/src/bitmap.rs b/src/bitmap.rs
index dc66d73..6aa6b12 100644
--- a/src/bitmap.rs
+++ b/src/bitmap.rs
@@ -1,4 +1,5 @@
 use std::{
+    collections::HashSet,
     convert::{From, Into, TryFrom},
     ops::{Add, Sub},
 };
@@ -10,7 +11,7 @@ pub struct Pixmap<T> {
     pub data: Vec<T>,
 }
 
-#[derive(Copy, Clone, Debug)]
+#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)]
 pub struct MapPoint {
     pub x: u32,
     pub y: u32,
@@ -249,22 +250,26 @@ where
             .collect()
     }
 
-    pub fn flood_fill(
-        &mut self,
-        start: MapPoint,
-        target: T,
-        replacement: T,
-        pts: &mut Vec<MapPoint>,
-    ) {
-        if !self.contains(start) || self.get(start) != target || self.get(start) == replacement {
-            return;
-        } else {
-            pts.push(start);
-            self.set(start, replacement);
-            for (x, y) in [(1, 0), (0, 1), (-1, 0), (0, -1)].iter() {
-                let dir = MapPoint::try_from((start.x as i64 - x, start.y as i64 + y));
-                if let Ok(pt) = dir {
-                    self.flood_fill(pt, target, replacement, pts);
+    pub fn flood_fill(&mut self, start: MapPoint, target: T, replacement: T) -> Vec<MapPoint> {
+        let mut queue = vec![start];
+        let mut area = HashSet::new();
+        loop {
+            if queue.is_empty() {
+                break area.drain().collect();
+            } else {
+                let last = queue.pop().unwrap();
+                area.insert(last);
+                for (x, y) in [(1, 0), (0, 1), (-1, 0), (0, -1)].iter() {
+                    let dir = MapPoint::try_from((last.x as i64 + x, last.y as i64 + y));
+                    if let Ok(pt) = dir {
+                        if self.contains(pt)
+                            && self.get(pt) == target
+                            && self.get(pt) != replacement
+                            && !area.contains(&pt)
+                        {
+                            queue.push(pt);
+                        }
+                    }
                 }
             }
         }
-- 
cgit v1.2.3