X-Git-Url: https://gerrit.simantics.org/r/gitweb?a=blobdiff_plain;f=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2Fcollections%2FQuadTree2.java;fp=bundles%2Forg.simantics.utils.datastructures%2Fsrc%2Forg%2Fsimantics%2Futils%2Fdatastructures%2Fcollections%2FQuadTree2.java;h=e617a52213b0f4e1023cc207d4d247f7e7234922;hb=930fd58d2e231b26ecb444f1e8e449829756add7;hp=0000000000000000000000000000000000000000;hpb=ca0f4eb1114af9a04ee46dcd8626132f0dff786d;p=simantics%2Fplatform.git

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();
+	}
+
+}