bundles/org.simantics.utils.datastructures/src/org/simantics/utils/datastructures/collections/QuadTree2.java

   1 package org.simantics.utils.datastructures.collections;
   2
   3 import java.awt.geom.Point2D;
   4 import java.awt.geom.Rectangle2D;
   5 import java.util.HashMap;
   6 import java.util.Map;
   7 import java.util.Set;
   8
   9 /**
  10  * Improved QuadTree with spatial removes.
  11  *
  12  * If application logic contains lots of tree modifications (remove + add), removals are much faster done spatially.
  13  *
  14  * @author MarkoLuukkainen
  15  *
  16  * @param <T>
  17  */
  18 public class QuadTree2<T> {
  19
  20         QuadTree<T> qt;
  21         Map<T,Rectangle2D> map;
  22
  23         public QuadTree2(Point2D center, double width, double height, int depth) {
  24                 this.qt = new QuadTree<T>(center, width, height, depth);
  25                 this.map = new HashMap<T, Rectangle2D>();
  26         }
  27
  28         public void insert(T object, Rectangle2D bounds) {
  29                 Rectangle2D r = map.put(object, bounds);
  30                 if (r != null) {
  31                         qt.remove(object, r);
  32                 }
  33
  34                 qt.insert(object, bounds);
  35         }
  36
  37         public void remove(T object) {
  38                 Rectangle2D r = map.remove(object);
  39                 if (r != null) {
  40                         qt.remove(object, r);
  41                 }
  42         }
  43
  44         public boolean contains(T object) {
  45                 return map.containsKey(object);
  46         }
  47
  48         public void get(Rectangle2D bounds, Set<T> set) {
  49                 qt.get(bounds, set);
  50         }
  51
  52         public void clear() {
  53                 map.clear();
  54                 qt.clear();
  55         }
  56
  57 }