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 / QuadTree.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 b22fa27035ef6eec49126a54415089ffb48a98d6..0a97064cfcf0d862a1b59e39614bb8763fb0c009 100644 (file)
--- 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);