Changeset 11237 in josm for trunk/src

Timestamp:

2016-11-11T17:43:17+01:00 (8 years ago)

Author:

bastiK

Message:

applied #13933 - Simplify QuadBuckets and improve memory footprint (patch by Gerd Petermann, minor modifications)

Location:

trunk/src/org/openstreetmap/josm/data

Files:

• coor/QuadTiling.java (modified) (1 diff)
• osm/BBox.java (modified) (2 diffs)
• osm/QuadBuckets.java (modified) (15 diffs)

trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java

@@ -75 +75 @@
      * @since 6171
      */
-    public static int index(final double lat, final double lon, final int level) {
+    public static byte index(final double lat, final double lon, final int level) {
         long x = lon2x(lon);
         long y = lat2y(lat);
         int shift = NR_LEVELS-level-1;
-        return (int) ((x >> shift & 1) * 2 + (y >> shift & 1));
+        return (byte) ((x >> shift & 1) * 2 + (y >> shift & 1));
     }
 }

trunk/src/org/openstreetmap/josm/data/osm/BBox.java

@@ -12 +12 @@
 public class BBox {
 
-    private double xmin = Double.POSITIVE_INFINITY;
-    private double xmax = Double.NEGATIVE_INFINITY;
-    private double ymin = Double.POSITIVE_INFINITY;
-    private double ymax = Double.NEGATIVE_INFINITY;
+    protected double xmin = Double.POSITIVE_INFINITY;
+    protected double xmax = Double.NEGATIVE_INFINITY;
+    protected double ymin = Double.POSITIVE_INFINITY;
+    protected double ymax = Double.NEGATIVE_INFINITY;
+
+    /**
+     * Constructs a new (invalid) BBox
+     */
+    protected BBox() { }
+
 
     /**
@@ -242 +248 @@
     }
 
-    int getIndex(final int level) {
-
-        int idx1 = QuadTiling.index(ymin, xmin, level);
-
-        final int idx2 = QuadTiling.index(ymin, xmax, level);
+    byte getIndex(final int level) {
+
+        byte idx1 = QuadTiling.index(ymin, xmin, level);
+
+        final byte idx2 = QuadTiling.index(ymin, xmax, level);
         if (idx1 == -1) idx1 = idx2;
         else if (idx1 != idx2) return -1;
 
-        final int idx3 = QuadTiling.index(ymax, xmin, level);
+        final byte idx3 = QuadTiling.index(ymax, xmin, level);
         if (idx1 == -1) idx1 = idx3;
         else if (idx1 != idx3) return -1;
 
-        final int idx4 = QuadTiling.index(ymax, xmax, level);
+        final byte idx4 = QuadTiling.index(ymax, xmax, level);
         if (idx1 == -1) idx1 = idx4;
         else if (idx1 != idx4) return -1;

trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java

@@ -15 +15 @@
 /**
  * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must
- * be removed and readded.
+ * be removed and re-added.
  *
  * This class is (no longer) thread safe.
@@ -23 +23 @@
 public class QuadBuckets<T extends OsmPrimitive> implements Collection<T> {
     private static final boolean consistency_testing = false;
-    private static final int NW_INDEX = 1;
-    private static final int NE_INDEX = 3;
-    private static final int SE_INDEX = 2;
-    private static final int SW_INDEX = 0;
+    private static final byte NW_INDEX = 1;
+    private static final byte NE_INDEX = 3;
+    private static final byte SE_INDEX = 2;
+    private static final byte SW_INDEX = 0;
 
     static void abort(String s) {
@@ -32 +32 @@
     }
 
-    public static final int MAX_OBJECTS_PER_LEVEL = 16;
-
-    static class QBLevel<T extends OsmPrimitive> {
-        private final int level;
-        private final int index;
-        private final BBox bbox;
+    private static final int MAX_OBJECTS_PER_NODE = 48;
+
+    static class QBLevel<T extends OsmPrimitive> extends BBox {
+        private final byte level;
+        private final byte index;
         private final long quad;
         private final QBLevel<T> parent;
@@ -46 +45 @@
         private QBLevel<T> nw, ne, sw, se;
 
-        private final QuadBuckets<T> buckets;
-
-        private QBLevel<T> getChild(int index) {
+        private QBLevel<T> getChild(byte index) {
             switch (index) {
             case NE_INDEX:
                 if (ne == null) {
-                    ne = new QBLevel<>(this, index, buckets);
+                    ne = new QBLevel<>(this, index);
                 }
                 return ne;
             case NW_INDEX:
                 if (nw == null) {
-                    nw = new QBLevel<>(this, index, buckets);
+                    nw = new QBLevel<>(this, index);
                 }
                 return nw;
             case SE_INDEX:
                 if (se == null) {
-                    se = new QBLevel<>(this, index, buckets);
+                    se = new QBLevel<>(this, index);
                 }
                 return se;
             case SW_INDEX:
                 if (sw == null) {
-                    sw = new QBLevel<>(this, index, buckets);
+                    sw = new QBLevel<>(this, index);
                 }
                 return sw;
@@ -82 +79 @@
         @Override
         public String toString() {
-            return super.toString() + '[' + level + "]: " + bbox();
+            return super.toString() + '[' + level + "]: ";
         }
 
         /**
          * Constructor for root node
-         * @param buckets quadbuckets
          */
-        QBLevel(final QuadBuckets<T> buckets) {
+        QBLevel() {
+            super(-180, 90, 180, -90);
             level = 0;
             index = 0;
             quad = 0;
             parent = null;
-            bbox = new BBox(-180, 90, 180, -90);
-            this.buckets = buckets;
-        }
-
-        QBLevel(QBLevel<T> parent, int parentIndex, final QuadBuckets<T> buckets) {
+        }
+
+        QBLevel(QBLevel<T> parent, byte index) {
             this.parent = parent;
-            this.level = parent.level + 1;
-            this.index = parentIndex;
-            this.buckets = buckets;
+            this.level = (byte) (parent.level + 1);
+            this.index = index;
 
             int shift = (QuadTiling.NR_LEVELS - level) * 2;
-            long mult = 1;
-            // Java blows the big one. It seems to wrap when you shift by > 31
-            if (shift >= 30) {
-                shift -= 30;
-                mult = 1 << 30;
-            }
-            long quadpart = mult * (parentIndex << shift);
+            long quadpart = (long) index << shift;
             this.quad = parent.quad | quadpart;
-            this.bbox = calculateBBox(); // calculateBBox reference quad
-        }
-
-        private BBox calculateBBox() {
-            LatLon bottomLeft = this.coor();
-            double lat = bottomLeft.lat() + parent.height() / 2;
-            double lon = bottomLeft.lon() + parent.width() / 2;
-            return new BBox(bottomLeft.lon(), bottomLeft.lat(), lon, lat);
+            LatLon bottomLeft = QuadTiling.tile2LatLon(this.quad);
+            xmin = bottomLeft.lon();
+            ymin = bottomLeft.lat();
+            xmax = xmin + parent.width() / 2;
+            ymax = ymin + parent.height() / 2;
         }
 
@@ -127 +112 @@
                 return this;
             else {
-                int idx = bbox.getIndex(level);
+                byte idx = bbox.getIndex(level);
                 if (idx == -1)
                     return this;
@@ -163 +148 @@
 
             for (T o : tmpcontent) {
-                int idx = o.getBBox().getIndex(level);
+                byte idx = o.getBBox().getIndex(level);
                 if (idx == -1) {
                     doAddContent(o);
@@ -283 +268 @@
         void doAdd(T o) {
             if (consistency_testing) {
-                if (!matches(o, this.bbox())) {
+                if (o instanceof Node && !matches(o, this)) {
                     o.getBBox().getIndex(level);
                     o.getBBox().getIndex(level - 1);
-                    abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
+                    abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + super.toString());
                 }
             }
             doAddContent(o);
-            if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) {
+            if (isLeaf() && content.size() > MAX_OBJECTS_PER_NODE && level < QuadTiling.NR_LEVELS) {
                 doSplit();
             }
@@ -299 +284 @@
         }
 
-        private void search(BBox searchBbox, List<T> result) {
-            if (!this.bbox().intersects(searchBbox))
+        private void search(QuadBuckets<T> buckets, BBox searchBbox, List<T> result) {
+            if (!this.intersects(searchBbox))
                 return;
-            else if (bbox().bounds(searchBbox)) {
+            else if (this.bounds(searchBbox)) {
                 buckets.searchCache = this;
             }
@@ -313 +298 @@
 
             if (nw != null) {
-                nw.search(searchBbox, result);
+                nw.search(buckets, searchBbox, result);
             }
             if (ne != null) {
-                ne.search(searchBbox, result);
+                ne.search(buckets, searchBbox, result);
             }
             if (se != null) {
-                se.search(searchBbox, result);
+                se.search(buckets, searchBbox, result);
             }
             if (sw != null) {
-                sw.search(searchBbox, result);
+                sw.search(buckets, searchBbox, result);
             }
         }
@@ -337 +322 @@
             }
             return -1;
-        }
-
-        double width() {
-            return bbox.width();
-        }
-
-        double height() {
-            return bbox.height();
-        }
-
-        public BBox bbox() {
-            return bbox;
-        }
-
-        /*
-         * This gives the coordinate of the bottom-left
-         * corner of the box
-         */
-        final LatLon coor() {
-            return QuadTiling.tile2LatLon(this.quad);
         }
 
@@ -404 +369 @@
     @Override
     public final void clear() {
-        root = new QBLevel<>(this);
+        root = new QBLevel<>();
         searchCache = null;
         size = 0;
@@ -583 +548 @@
     }
 
+    /**
+     * Search the tree for objects in the bbox (or crossing the bbox if they are ways)
+     * @param searchBbox the bbox
+     * @return List of primitives within the bbox (or crossing the bbox if they are ways). Can be empty, but not null.
+     */
     public List<T> search(BBox searchBbox) {
         List<T> ret = new ArrayList<>();
@@ -590 +560 @@
         }
         // Walk back up the tree when the last search spot can not cover the current search
-        while (searchCache != null && !searchCache.bbox().bounds(searchBbox)) {
+        while (searchCache != null && !searchCache.bounds(searchBbox)) {
             searchCache = searchCache.parent;
         }
@@ -602 +572 @@
         QBLevel<T> tmp = searchCache.parent;
 
-        searchCache.search(searchBbox, ret);
+        searchCache.search(this, searchBbox, ret);
 
         // A way that spans this bucket may be stored in one