From 930fd58d2e231b26ecb444f1e8e449829756add7 Mon Sep 17 00:00:00 2001
From: Marko Luukkainen <marko.luukkainen@semantum.fi>
Date: Wed, 16 Nov 2022 10:18:15 +0200
Subject: [PATCH] A QuadTree with better element remove implementation.

gitlab #880

Change-Id: I979b31232c81b0524c7733bbbf6bf6f4e1d831c5
---
 .../datastructures/collections/QuadTree.java  | 44 ++++++++++++++
 .../datastructures/collections/QuadTree2.java | 57 +++++++++++++++++++
 2 files changed, 101 insertions(+)
 create mode 100644 bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree2.java

diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree.java
index b22fa2703..0a97064cf 100644
--- a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree.java
+++ b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree.java
@@ -104,6 +104,50 @@ public class QuadTree<T> {
 		}
 	}
 	
+	public void remove(T object, Rectangle2D bounds) {
+		if (leaf) {
+			contains.remove(object);
+		} else {
+			
+			boolean pX = bounds.getMinX() > center.getX();
+			boolean nX = bounds.getMaxX() < center.getX();
+			boolean pY = bounds.getMinY() > center.getY();
+			boolean nY = bounds.getMaxY() < center.getY();
+			
+			if (pX) {
+				if (pY) {
+					pXpY.remove(object, bounds);
+				} else if (nY) {
+					pXnY.remove(object, bounds);
+				} else {
+					pXpY.remove(object, bounds);
+					pXnY.remove(object, bounds);
+				}
+			} else if (nX) {
+				if (pY) {
+					nXpY.remove(object, bounds);
+				} else if (nY) {
+					nXnY.remove(object, bounds);
+				} else {
+					nXpY.remove(object, bounds);
+					nXnY.remove(object, bounds);
+				}
+			} else if (pY) {
+				pXpY.remove(object, bounds);
+				nXpY.remove(object, bounds);
+			} else if (nY) {
+				pXnY.remove(object, bounds);
+				nXnY.remove(object, bounds);
+			} else {
+				pXpY.remove(object, bounds);
+				pXnY.remove(object, bounds);
+				nXpY.remove(object, bounds);
+				nXnY.remove(object, bounds);
+			}
+			
+		}
+	}
+	
 	public boolean contains(T object) {
 		if (leaf) {
 			return contains.contains(object);
diff --git a/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree2.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree2.java
new file mode 100644
index 000000000..e617a5221
--- /dev/null
+++ b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree2.java
@@ -0,0 +1,57 @@
+package org.simantics.utils.datastructures.collections;
+
+import java.awt.geom.Point2D;
+import java.awt.geom.Rectangle2D;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Improved QuadTree with spatial removes.
+ * 
+ * If application logic contains lots of tree modifications (remove + add), removals are much faster done spatially.
+ * 
+ * @author MarkoLuukkainen
+ *
+ * @param <T>
+ */
+public class QuadTree2<T> {
+	
+	QuadTree<T> qt;
+	Map<T,Rectangle2D> map;
+	
+	public QuadTree2(Point2D center, double width, double height, int depth) {
+		this.qt = new QuadTree<T>(center, width, height, depth);
+		this.map = new HashMap<T, Rectangle2D>();
+	}
+	
+	public void insert(T object, Rectangle2D bounds) {
+		Rectangle2D r = map.put(object, bounds);
+		if (r != null) {
+			qt.remove(object, r);
+		}
+		
+		qt.insert(object, bounds);
+	}
+	
+	public void remove(T object) {
+		Rectangle2D r = map.remove(object);
+		if (r != null) {
+			qt.remove(object, r);
+		}
+	}
+	
+	public boolean contains(T object) {
+		return map.containsKey(object);
+	}
+	
+	public void get(Rectangle2D bounds, Set<T> set) {
+		qt.get(bounds, set);
+	}
+	
+	public void clear() {
+		map.clear();
+		qt.clear();
+	}
+
+}
-- 
2.45.1