Merge "A QuadTree with better element remove implementation." into release/1.43.1

[simantics/platform.git] / 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/QuadTree2.java b/bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree2.java
new file mode 100644 (file)
index 0000000..e617a52
--- /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();
+       }
+
+}