Changeset 6171 in josm

Timestamp:

2013-08-21T13:38:23+02:00 (11 years ago)

Author:

Don-vip

Message:

fix #8986 - Data loading/bbox index counting optimization (patch by shinigami) + code cleanup in Quad* classes

Location:

trunk/src/org/openstreetmap/josm/data

Files:

• coor/QuadTiling.java (modified) (5 diffs)
• osm/BBox.java (modified) (3 diffs)
• osm/QuadBuckets.java (modified) (39 diffs)

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

@@ -9 +9 @@
     public static final int TILES_PER_LEVEL_SHIFT = 2; // Has to be 2. Other parts of QuadBuckets code rely on it
     public static final int TILES_PER_LEVEL = 1<<TILES_PER_LEVEL_SHIFT;
-    static public final int X_PARTS = 360;
-    static public final int X_BIAS = -180;
+    public static final int X_PARTS = 360;
+    public static final int X_BIAS = -180;
 
-    static public final int Y_PARTS = 180;
-    static public final int Y_BIAS = -90;
+    public static final int Y_PARTS = 180;
+    public static final int Y_BIAS = -90;
 
-    public static LatLon tile2LatLon(long quad)
-    {
+    public static LatLon tile2LatLon(long quad) {
         // The world is divided up into X_PARTS,Y_PARTS.
         // The question is how far we move for each bit
@@ -44 +43 @@
         return new LatLon(y, x);
     }
-    static long xy2tile(long x, long y)
-    {
+    
+    static long xy2tile(long x, long y) {
         long tile = 0;
         int i;
@@ -58 +57 @@
         return tile;
     }
-    static long coorToTile(LatLon coor)
-    {
+    
+    static long coorToTile(LatLon coor) {
         return quadTile(coor);
     }
-    static long lon2x(double lon)
-    {
+    
+    static long lon2x(double lon) {
         //return Math.round((lon + 180.0) * QuadBuckets.WORLD_PARTS / 360.0)-1;
         long ret = (long)((lon + 180.0) * WORLD_PARTS / 360.0);
@@ -71 +70 @@
         return ret;
     }
-    static long lat2y(double lat)
-    {
+    
+    static long lat2y(double lat) {
         //return Math.round((lat + 90.0) * QuadBuckets.WORLD_PARTS / 180.0)-1;
         long ret = (long)((lat + 90.0) * WORLD_PARTS / 180.0);
@@ -80 +79 @@
         return ret;
     }
-    static public long quadTile(LatLon coor)
-    {
-        return xy2tile(lon2x(coor.lon()),
-                lat2y(coor.lat()));
+    
+    public static long quadTile(LatLon coor) {
+        return xy2tile(lon2x(coor.lon()), lat2y(coor.lat()));
     }
-    static public int index(int level, long quad)
-    {
+    
+    public static int index(int level, long quad) {
         long mask = 0x00000003;
         int total_shift = TILES_PER_LEVEL_SHIFT*(NR_LEVELS-level-1);
         return (int)(mask & (quad >> total_shift));
     }
-    static public int index(LatLon coor, int level) {
-        // The nodes that don't return coordinates will all get
-        // stuck in a single tile.  Hopefully there are not too
-        // many of them
+    
+    /**
+     * Returns quad tiling index for given coordinates and level.
+     *
+     * @param coor coordinates
+     * @param level level
+     *
+     * @return quad tiling index for given coordinates and level.
+     * @since 2263
+     */
+    public static int index(LatLon coor, int level) {
+        // The nodes that don't return coordinates will all get stuck in a single tile. 
+        // Hopefully there are not too many of them
         if (coor == null)
             return 0;
 
-        long x = lon2x(coor.lon());
-        long y = lat2y(coor.lat());
+        return index(coor.lat(), coor.lon(), level);
+    }
+
+    /**
+     * Returns quad tiling index for given coordinates and level.
+     *
+     * @param lat latitude
+     * @param lon longitude
+     * @param level level
+     *
+     * @return quad tiling index for given coordinates and level.
+     * @since 6171
+     */
+    public static int 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));

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

@@ -8 +8 @@
 import org.openstreetmap.josm.data.Bounds;
 import org.openstreetmap.josm.data.coor.LatLon;
+import org.openstreetmap.josm.data.coor.QuadTiling;
 import org.openstreetmap.josm.tools.Utils;
 
@@ -152 +153 @@
     }
 
-    /**
-     * Returns a list of all 4 corners of the bbox rectangle.
-     */
-    public List<LatLon> points()  {
-        LatLon p1 = new LatLon(ymin, xmin);
-        LatLon p2 = new LatLon(ymin, xmax);
-        LatLon p3 = new LatLon(ymax, xmin);
-        LatLon p4 = new LatLon(ymax, xmax);
-        List<LatLon> ret = new ArrayList<LatLon>(4);
-        ret.add(p1);
-        ret.add(p2);
-        ret.add(p3);
-        ret.add(p4);
-        return ret;
-    }
-
     public LatLon getTopLeft() {
         return new LatLon(ymax, xmin);
@@ -178 +163 @@
     public LatLon getCenter() {
         return new LatLon(ymin + (ymax-ymin)/2.0, xmin + (xmax-xmin)/2.0);
+    }
+
+    int getIndex(final int level) {
+
+        int idx1 = QuadTiling.index(ymin, xmin, level);
+
+        final int 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);
+        if (idx1 == -1) idx1 = idx3;
+        else if (idx1 != idx3) return -1;
+
+        final int idx4 = QuadTiling.index(ymax, xmax, level);
+        if (idx1 == -1) idx1 = idx4;
+        else if (idx1 != idx4) return -1;
+
+        return idx1;
     }
 

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

@@ -9 +9 @@
 import java.util.List;
 
+import org.openstreetmap.josm.Main;
 import org.openstreetmap.josm.data.coor.LatLon;
 import org.openstreetmap.josm.data.coor.QuadTiling;
@@ -21 +22 @@
 public class QuadBuckets<T extends OsmPrimitive> implements Collection<T>
 {
-    //private static boolean debug = false;
     private static final boolean consistency_testing = false;
     private static final int NW_INDEX = 1;
@@ -28 +28 @@
     private static final int SW_INDEX = 0;
 
-    static void abort(String s)
-    {
+    static void abort(String s) {
         throw new AssertionError(s);
     }
-    static void out(String s)
-    {
-        System.out.println(s);
-    }
-    // periodic output
-    long last_out = -1;
-    void pout(String s)
-    {
-        long now = System.currentTimeMillis();
-        if (now - last_out < 300)
-            return;
-        last_out = now;
-        System.out.print(s + "\r");
-    }
-    void pout(String s, int i, int total)
-    {
-        long now = System.currentTimeMillis();
-        if ((now - last_out < 300) &&
-                ((i+1) < total))
-            return;
-        last_out = now;
-        // cast to float to keep the output size down
-        System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done    \r");
-    }
 
     public static final int MAX_OBJECTS_PER_LEVEL = 16;
+    
     class QBLevel
     {
@@ -115 +91 @@
             return super.toString()+ "["+level+"]: " + bbox();
         }
+        
         /**
          * Constructor for root node
@@ -130 +107 @@
             int shift = (QuadTiling.NR_LEVELS - level) * 2;
             long mult = 1;
-            // Java blows the big one.  It seems to wrap when
-            // you shift by > 31
+            // Java blows the big one. It seems to wrap when you shift by > 31
             if (shift >= 30) {
                 shift -= 30;
@@ -139 +115 @@
             this.quad = parent.quad | this_quadpart;
             this.bbox = calculateBBox(); // calculateBBox reference quad
-            /*if (debug) {
-                out("new level["+this.level+"] bbox["+parent_index+"]: " + this.bbox()
-                        + " coor: " + this.coor()
-                        + " quadpart: " + Long.toHexString(this_quadpart)
-                        + " quad: " + Long.toHexString(this.quad));
-            }*/
         }
 
@@ -159 +129 @@
                 return this;
             else {
-                int index = get_index(bbox, level);
+                int index = bbox.getIndex(level);
                 if (index == -1)
                     return this;
@@ -166 +136 @@
         }
 
-        boolean remove_content(T o)
-        {
+        boolean remove_content(T o) {
             // If two threads try to remove item at the same time from different buckets of this QBLevel,
             // it might happen that one thread removes bucket but don't remove parent because it still sees
@@ -184 +153 @@
             return ret;
         }
-        // Get the correct index for the given primitive
-        // at the given level.  If the primitive can not
-        // fit into a single quad at this level, return -1
-        int get_index(BBox bbox, int level) {
-            int index = -1;
-            for (LatLon c : bbox.points()) {
-                /*if (debug) {
-                    out("getting index for point: " + c);
-                }*/
-                if (index == -1) {
-                    index = QuadTiling.index(c, level);
-                    /*if (debug) {
-                        out("set initial index to: " + index);
-                    }*/
-                    continue;
-                }
-                int another_index = QuadTiling.index(c, level);
-                /*if (debug) {
-                    out("other point index: " + another_index);
-                }*/
-                if (another_index != index)
-                    return -1;
-            }
-            return index;
-        }
+
         /*
          * There is a race between this and qb.nextContentNode().
@@ -216 +161 @@
          */
         void __split() {
-            /*if (debug) {
-                out("splitting "+this.bbox()+" level "+level+" with "
-                        + content.size() + " entries (my dimensions: "
-                        + this.bbox().width()+", "+this.bbox().height()+")");
-            }*/
             List<T> tmpcontent = content;
             content = null;
 
             for (T o: tmpcontent) {
-                int index = get_index(o.getBBox(), level);
+                int index = o.getBBox().getIndex(level);
                 if (index == -1) {
                     __add_content(o);
@@ -235 +175 @@
         }
 
-        boolean __add_content(T o)
-        {
+        boolean __add_content(T o) {
             boolean ret = false;
-            // The split_lock will keep two concurrent
-            // calls from overwriting content
+            // The split_lock will keep two concurrent calls from overwriting content
             if (content == null) {
                 content = new ArrayList<T>();
             }
             ret = content.add(o);
-            /*if (debug && !this.isLeaf()) {
-                pout("added "+o.getClass().getName()+" to non-leaf with size: " + content.size());
-            }*/
             return ret;
         }
-        boolean matches(T o, BBox search_bbox)
-        {
+        
+        boolean matches(T o, BBox search_bbox) {
             // This can be optimized when o is a node
-            //return search_bbox.bounds(coor));
             return o.getBBox().intersects(search_bbox);
         }
-        private void search_contents(BBox search_bbox, List<T> result)
-        {
-            /*if (debug) {
-                out("searching contents (size: " + content == null?"<null>":content.size() + ") for " + search_bbox);
-            }*/
+        
+        private void search_contents(BBox search_bbox, List<T> result) {
             /*
              * It is possible that this was created in a split
@@ -272 +203 @@
                 }
             }
-            /*if (debug) {
-                out("done searching quad " + Long.toHexString(this.quad));
-            }*/
-        }
+        }
+        
         /*
-         * This is stupid.  I tried to have a QBLeaf and QBBranch
-         * class decending from a QBLevel.  It's more than twice
-         * as slow.  So, this throws OO out the window, but it
-         * is fast.  Runtime type determination must be slow.
+         * This is stupid. I tried to have a QBLeaf and QBBranch
+         * class decending from a QBLevel. It's more than twice
+         * as slow. So, this throws OO out the window, but it
+         * is fast. Runtime type determination must be slow.
          */
         boolean isLeaf() {
             return isLeaf;
         }
+        
         boolean hasChildren() {
             return nw != null || ne != null || sw != null || se != null;
         }
 
-        QBLevel next_sibling()
-        {
+        QBLevel next_sibling() {
             boolean found_me = false;
             if (parent == null)
                 return null;
-            int __nr = 0;
             for (QBLevel sibling : parent.getChildren()) {
-                __nr++;
-                int nr = __nr-1;
                 if (sibling == null) {
-                    /*if (debug) {
-                        out("[" + this.level + "] null child nr: " + nr);
-                    }*/
                     continue;
                 }
-                // We're looking for the *next* child
-                // after us.
+                // We're looking for the *next* child after us.
                 if (sibling == this) {
-                    /*if (debug) {
-                        out("[" + this.level + "] I was child nr: " + nr);
-                    }*/
                     found_me = true;
                     continue;
                 }
                 if (found_me)
-                    /*if (debug) {
-                        out("[" + this.level + "] next sibling was child nr: " + nr);
-                    }*/
                     return sibling;
             }
             return null;
         }
-        boolean hasContent()
-        {
+        
+        boolean hasContent() {
             return content != null;
         }
-        QBLevel nextSibling()
-        {
+        
+        QBLevel nextSibling() {
             QBLevel next = this;
             QBLevel sibling = next.next_sibling();
@@ -333 +249 @@
             // a leaf or branch.
             while (sibling == null) {
-                /*if (debug) {
-                    out("no siblings at level["+next.level+"], moving to parent");
-                }*/
                 next = next.parent;
                 if (next == null) {
@@ -345 +258 @@
             return next;
         }
-        QBLevel firstChild()
-        {
+        
+        QBLevel firstChild() {
             QBLevel ret = null;
             for (QBLevel child : getChildren()) {
@@ -357 +270 @@
             return ret;
         }
-        QBLevel nextNode()
-        {
+        
+        QBLevel nextNode() {
             if (!this.hasChildren())
                 return this.nextSibling();
             return this.firstChild();
         }
-        QBLevel nextContentNode()
-        {
+        
+        QBLevel nextContentNode() {
             QBLevel next = this.nextNode();
             if (next == null)
@@ -376 +289 @@
             if (consistency_testing) {
                 if (!matches(o, this.bbox())) {
-                    /*out("-----------------------------");
-                    debug = true;*/
-                    get_index(o.getBBox(), level);
-                    get_index(o.getBBox(), level-1);
+                    o.getBBox().getIndex(level);
+                    o.getBBox().getIndex(level-1);
                     int nr = 0;
-                    /*for (QBLevel sibling : parent.getChildren()) {
-                        out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling));
-                    }*/
                     abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
                 }
@@ -397 +305 @@
         }
 
-        private void search(BBox search_bbox, List<T> result)
-        {
-            /*if (debug) {
-                System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
-            }*/
+        private void search(BBox search_bbox, List<T> result) {
             if (!this.bbox().intersects(search_bbox))
-                /*if (debug) {
-                    out("miss " + Long.toHexString(this.quad));
-                    //QuadTiling.tile2xy(this.quad);
-                }*/
                 return;
             else if (bbox().bounds(search_bbox)) {
@@ -416 +316 @@
             }
 
-            /*if (debug) {
-                out("hit " + this.quads());
-                out("[" + level + "] not leaf, moving down");
-            }*/
-
             //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
 
@@ -436 +331 @@
             }
         }
-        public String quads()
-        {
+        
+        public String quads() {
             return Long.toHexString(quad);
         }
-        int index_of(QBLevel find_this)
-        {
+        
+        int index_of(QBLevel find_this) {
             QBLevel[] children = getChildren();
             for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
@@ -449 +344 @@
             return -1;
         }
+        
         double width() {
             return bbox.width();
@@ -460 +356 @@
             return bbox;
         }
+        
         /*
          * This gives the coordinate of the bottom-left
          * corner of the box
          */
-        LatLon coor()
-        {
+        LatLon coor() {
             return QuadTiling.tile2LatLon(this.quad);
         }
-        void remove_from_parent()
-        {
+        
+        void remove_from_parent() {
             if (parent == null)
                 return;
@@ -491 +387 @@
             }
         }
-        boolean canRemove()
-        {
+        
+        boolean canRemove() {
             if (content != null && !content.isEmpty())
                 return false;
@@ -505 +401 @@
     private int size;
 
-    public QuadBuckets()
-    {
+    /**
+     * Constructs a new {@code QuadBuckets}.
+     */
+    public QuadBuckets() {
         clear();
     }
+    
     @Override
     public void clear()  {
@@ -514 +413 @@
         search_cache = null;
         size = 0;
-        /*if (debug) {
-            out("QuadBuckets() cleared: " + this);
-            out("root: " + root + " level: " + root.level + " bbox: " + root.bbox());
-        }*/
-    }
+    }
+    
     @Override
     public boolean add(T n) {
@@ -527 +423 @@
 
     @Override
-    public boolean retainAll(Collection<?> objects)
-    {
+    public boolean retainAll(Collection<?> objects) {
         for (T o : this) {
             if (objects.contains(o)) {
@@ -538 +433 @@
         return true;
     }
-    @Override
-    public boolean removeAll(Collection<?> objects)
-    {
+    
+    @Override
+    public boolean removeAll(Collection<?> objects) {
         boolean changed = false;
         for (Object o : objects) {
@@ -547 +442 @@
         return changed;
     }
-    @Override
-    public boolean addAll(Collection<? extends T> objects)
-    {
+    
+    @Override
+    public boolean addAll(Collection<? extends T> objects) {
         boolean changed = false;
         for (T o : objects) {
@@ -556 +451 @@
         return changed;
     }
-    @Override
-    public boolean containsAll(Collection<?> objects)
-    {
+    
+    @Override
+    public boolean containsAll(Collection<?> objects) {
         for (Object o : objects) {
             if (!this.contains(o))
@@ -565 +460 @@
         return true;
     }
+    
     @Override
     public boolean remove(Object o) {
@@ -576 +472 @@
             return false;
     }
+    
     @Override
     public boolean contains(Object o) {
@@ -583 +480 @@
     }
 
-    public ArrayList<T> toArrayList()
-    {
+    public ArrayList<T> toArrayList() {
         ArrayList<T> a = new ArrayList<T>();
         for (T n : this) {
             a.add(n);
         }
-        /*if (debug) {
-            out("returning array list with size: " + a.size());
-        }*/
         return a;
     }
-    @Override
-    public Object[] toArray()
-    {
+    
+    @Override
+    public Object[] toArray() {
         return this.toArrayList().toArray();
     }
-    @Override
-    public <A> A[] toArray(A[] template)
-    {
+    
+    @Override
+    public <A> A[] toArray(A[] template) {
         return this.toArrayList().toArray(template);
     }
+    
     class QuadBucketIterator implements Iterator<T>
     {
@@ -609 +503 @@
         int content_index;
         int iterated_over;
-        QBLevel next_content_node(QBLevel q)
-        {
+        QBLevel next_content_node(QBLevel q) {
             if (q == null)
                 return null;
@@ -622 +515 @@
             return next;
         }
-        public QuadBucketIterator(QuadBuckets<T> qb)
-        {
-            /*if (debug) {
-                out(this + " is a new iterator qb: " + qb + " size: " + qb.size());
-            }*/
+        
+        public QuadBucketIterator(QuadBuckets<T> qb) {
             if (!qb.root.hasChildren() || qb.root.hasContent()) {
                 current_node = qb.root;
@@ -632 +522 @@
                 current_node = next_content_node(qb.root);
             }
-            /*if (debug) {
-                out("\titerator first leaf: " + current_node);
-            }*/
             iterated_over = 0;
         }
+        
         @Override
-        public boolean hasNext()
-        {
+        public boolean hasNext() {
             if (this.peek() == null)
-                /*if (debug) {
-                    out(this + " no hasNext(), but iterated over so far: " + iterated_over);
-                }*/
                 return false;
             return true;
         }
-        T peek()
-        {
+        
+        T peek() {
             if (current_node == null)
-                /*if (debug) {
-                    out("null current leaf, nowhere to go");
-                }*/
                 return null;
             while((current_node.content == null) ||
                     (content_index >= current_node.content.size())) {
-                /*if (debug) {
-                    out("moving to next leaf");
-                }*/
                 content_index = 0;
                 current_node = next_content_node(current_node);
@@ -666 +544 @@
             }
             if (current_node == null || current_node.content == null)
-                /*if (debug) {
-                    out("late nowhere to go " + current_node);
-                }*/
                 return null;
             return current_node.content.get(content_index);
         }
+        
         @Override
-        public T next()
-        {
+        public T next() {
             T ret = peek();
             content_index++;
-            /*if (debug) {
-                out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node);
-            }*/
             iterated_over++;
-            if (ret == null) {
-                /*if (debug) {
-                    out(this + " no next node, but iterated over so far: " + iterated_over);
-                }*/
-            }
             return ret;
         }
+        
         @Override
-        public void remove()
-        {
+        public void remove() {
             // two uses
             // 1. Back up to the thing we just returned
@@ -700 +567 @@
         }
     }
-    @Override
-    public Iterator<T> iterator()
-    {
+    
+    @Override
+    public Iterator<T> iterator() {
         return new QuadBucketIterator(this);
     }
+
     @Override
     public int size() {
@@ -711 +579 @@
 
     @Override
-    public boolean isEmpty()
-    {
+    public boolean isEmpty() {
         if (this.size() == 0)
             return true;
         return false;
     }
+    
     public List<T> search(BBox search_bbox) {
-        /*if (debug) {
-            out("qb root search at " + search_bbox);
-            out("root bbox: " + root.bbox());
-        }*/
         List<T> ret = new ArrayList<T>();
-        // Doing this cuts down search cost on a real-life data
-        // set by about 25%
+        // Doing this cuts down search cost on a real-life data set by about 25%
         boolean cache_searches = true;
         if (cache_searches) {
@@ -730 +593 @@
                 search_cache = root;
             }
-            // Walk back up the tree when the last
-            // search spot can not cover the current
-            // search
+            // Walk back up the tree when the last search spot can not cover the current search
             while (search_cache != null && !search_cache.bbox().bounds(search_bbox)) {
-                /*if (debug) {
-                    out("bbox: " + search_bbox);
-                    out("search_cache: " + search_cache + " level: " + search_cache.level);
-                    out("search_cache.bbox(): " + search_cache.bbox());
-                }*/
                 search_cache = search_cache.parent;
-                /*if (debug) {
-                    out("new search_cache: " + search_cache);
-                }*/
             }
 
             if (search_cache == null) {
                 search_cache = root;
-                out("bbox: " + search_bbox + " is out of the world");
+                Main.info("bbox: " + search_bbox + " is out of the world");
             }
         } else {
@@ -764 +617 @@
             tmp = tmp.parent;
         }
-        /*if (debug) {
-            out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size());
-        }*/
         return ret;
     }