Changeset 3151 in josm for trunk

Timestamp:

2010-03-21T13:13:42+01:00 (14 years ago)

Author:

jttt

Message:

QuadBuckets.search - use only one list instead of creating and copying results for each QBLevel

File:

• trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (modified) (10 diffs)

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

@@ -5 +5 @@
 import java.util.Arrays;
 import java.util.Collection;
-import java.util.Collections;
 import java.util.Iterator;
-import java.util.LinkedList;
 import java.util.List;
 
@@ -222 +220 @@
             return o.getBBox().intersects(search_bbox);
         }
-        private List<T> search_contents(BBox search_bbox)
+        private void search_contents(BBox search_bbox, List<T> result)
         {
             if (debug) {
@@ -232 +230 @@
              */
             if (content == null)
-                return null;
-            // We could delay allocating this.  But, the way it is currently
-            // used, we almost always have a node in the area that we're
-            // searching since we're searching around other nodes.
-            //
-            // the iterator's calls to ArrayList.size() were showing up in
-            // some profiles, so I'm trying a LinkedList instead
-            List<T> ret = new LinkedList<T>();
+                return;
+
             for (T o : content) {
                 if (matches(o, search_bbox)) {
-                    ret.add(o);
+                    result.add(o);
                 }
             }
@@ -248 +240 @@
                 out("done searching quad " + Long.toHexString(this.quad));
             }
-            return ret;
         }
         /*
@@ -445 +436 @@
         }
 
-        private List<T> search(BBox search_bbox)
-        {
-            List<T> ret = null;
+        private void search(BBox search_bbox, List<T> result)
+        {
             if (debug) {
                 System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
@@ -456 +446 @@
                     //QuadTiling.tile2xy(this.quad);
                 }
-                return ret;
+                return;
             }
             if (this.hasContent()) {
-                ret = this.search_contents(search_bbox);
+                search_contents(search_bbox, result);
             }
             if (this.isLeaf())
-                return ret;
-            //if (this.hasContent())
-            //    abort("branch had stuff");
+                return;
+
             if (debug) {
                 out("hit " + this.quads());
@@ -483 +472 @@
                     System.out.print(i+": ");
                 }
-                List<T> coors = q.search(search_bbox);
-                if (coors == null) {
-                    continue;
-                }
-                if (ret == null) {
-                    ret = coors;
-                } else {
-                    ret.addAll(coors);
-                }
+                q.search(search_bbox, result);
                 if (q.bbox().bounds(search_bbox)) {
                     search_cache = q;
@@ -497 +478 @@
                     // other tiles if this one wholly contained
                     // what we were looking for.
-                    if (coors.size() > 0 ) {
-                        if (debug) {
-                            out("break early");
-                        }
-                        break;
+                    if (debug) {
+                        out("break early");
                     }
-                }
-            }
-            return ret;
+                    break;
+                }
+            }
         }
         public String quads()
@@ -852 +830 @@
         return false;
     }
-    public static BBox search_to_bbox(LatLon point, double radius)
-    {
-        BBox bbox = new BBox(point.lon() - radius, point.lat() - radius,
-                point.lon() + radius, point.lat() + radius);
-        if (debug) {
-            out("search bbox before sanity: " +  bbox);
-        }
-        if (debug) {
-            out("search bbox after sanity: " +  bbox);
-        }
-        return bbox;
-    }
-    List<T> search(Way w)
-    {
-        BBox way_bbox = new BBox(w);
-        return this.search(way_bbox);
-    }
-    public List<T> search(Node n, double radius)
-    {
-        return this.search(n.getCoor(), radius);
-    }
-    public List<T> search(LatLon point, double radius)
-    {
-        if (point == null)
-            return Collections.emptyList();
-        return this.search(search_to_bbox(point, radius));
-    }
-    public List<T> search(LatLon b1, LatLon b2)
-    {
-        BBox bbox = new BBox(b1.lon(), b1.lat(), b2.lon(), b2.lat());
-        return this.search(bbox);
-    }
-    List<T> search(BBox search_bbox)
-    {
+    public List<T> search(BBox search_bbox) {
         if (debug) {
             out("qb root search at " + search_bbox);
             out("root bbox: " + root.bbox());
         }
-        List<T> ret;
+        List<T> ret = new ArrayList<T>();
         // Doing this cuts down search cost on a real-life data
         // set by about 25%
@@ -921 +866 @@
         QBLevel tmp = search_cache.parent;
 
-        ret = search_cache.search(search_bbox);
-        if (ret == null) {
-            ret = new ArrayList<T>();
-        }
+        search_cache.search(search_bbox, ret);
 
         // A way that spans this bucket may be stored in one
         // of the nodes which is a parent of the search cache
         while (tmp != null) {
-            List<T> content_result = tmp.search_contents(search_bbox);
-            if (content_result != null) {
-                ret.addAll(content_result);
-            }
+            tmp.search_contents(search_bbox, ret);
             tmp = tmp.parent;
         }