Changeset 3151 in josm for trunk


Ignore:
Timestamp:
2010-03-21T13:13:42+01:00 (10 years ago)
Author:
jttt
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java

    r3150 r3151  
    55import java.util.Arrays;
    66import java.util.Collection;
    7 import java.util.Collections;
    87import java.util.Iterator;
    9 import java.util.LinkedList;
    108import java.util.List;
    119
     
    222220            return o.getBBox().intersects(search_bbox);
    223221        }
    224         private List<T> search_contents(BBox search_bbox)
     222        private void search_contents(BBox search_bbox, List<T> result)
    225223        {
    226224            if (debug) {
     
    232230             */
    233231            if (content == null)
    234                 return null;
    235             // We could delay allocating this.  But, the way it is currently
    236             // used, we almost always have a node in the area that we're
    237             // searching since we're searching around other nodes.
    238             //
    239             // the iterator's calls to ArrayList.size() were showing up in
    240             // some profiles, so I'm trying a LinkedList instead
    241             List<T> ret = new LinkedList<T>();
     232                return;
     233
    242234            for (T o : content) {
    243235                if (matches(o, search_bbox)) {
    244                     ret.add(o);
     236                    result.add(o);
    245237                }
    246238            }
     
    248240                out("done searching quad " + Long.toHexString(this.quad));
    249241            }
    250             return ret;
    251242        }
    252243        /*
     
    445436        }
    446437
    447         private List<T> search(BBox search_bbox)
    448         {
    449             List<T> ret = null;
     438        private void search(BBox search_bbox, List<T> result)
     439        {
    450440            if (debug) {
    451441                System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
     
    456446                    //QuadTiling.tile2xy(this.quad);
    457447                }
    458                 return ret;
     448                return;
    459449            }
    460450            if (this.hasContent()) {
    461                 ret = this.search_contents(search_bbox);
     451                search_contents(search_bbox, result);
    462452            }
    463453            if (this.isLeaf())
    464                 return ret;
    465             //if (this.hasContent())
    466             //    abort("branch had stuff");
     454                return;
     455
    467456            if (debug) {
    468457                out("hit " + this.quads());
     
    483472                    System.out.print(i+": ");
    484473                }
    485                 List<T> coors = q.search(search_bbox);
    486                 if (coors == null) {
    487                     continue;
    488                 }
    489                 if (ret == null) {
    490                     ret = coors;
    491                 } else {
    492                     ret.addAll(coors);
    493                 }
     474                q.search(search_bbox, result);
    494475                if (q.bbox().bounds(search_bbox)) {
    495476                    search_cache = q;
     
    497478                    // other tiles if this one wholly contained
    498479                    // what we were looking for.
    499                     if (coors.size() > 0 ) {
    500                         if (debug) {
    501                             out("break early");
    502                         }
    503                         break;
     480                    if (debug) {
     481                        out("break early");
    504482                    }
    505                 }
    506             }
    507             return ret;
     483                    break;
     484                }
     485            }
    508486        }
    509487        public String quads()
     
    852830        return false;
    853831    }
    854     public static BBox search_to_bbox(LatLon point, double radius)
    855     {
    856         BBox bbox = new BBox(point.lon() - radius, point.lat() - radius,
    857                 point.lon() + radius, point.lat() + radius);
    858         if (debug) {
    859             out("search bbox before sanity: " +  bbox);
    860         }
    861         if (debug) {
    862             out("search bbox after sanity: " +  bbox);
    863         }
    864         return bbox;
    865     }
    866     List<T> search(Way w)
    867     {
    868         BBox way_bbox = new BBox(w);
    869         return this.search(way_bbox);
    870     }
    871     public List<T> search(Node n, double radius)
    872     {
    873         return this.search(n.getCoor(), radius);
    874     }
    875     public List<T> search(LatLon point, double radius)
    876     {
    877         if (point == null)
    878             return Collections.emptyList();
    879         return this.search(search_to_bbox(point, radius));
    880     }
    881     public List<T> search(LatLon b1, LatLon b2)
    882     {
    883         BBox bbox = new BBox(b1.lon(), b1.lat(), b2.lon(), b2.lat());
    884         return this.search(bbox);
    885     }
    886     List<T> search(BBox search_bbox)
    887     {
     832    public List<T> search(BBox search_bbox) {
    888833        if (debug) {
    889834            out("qb root search at " + search_bbox);
    890835            out("root bbox: " + root.bbox());
    891836        }
    892         List<T> ret;
     837        List<T> ret = new ArrayList<T>();
    893838        // Doing this cuts down search cost on a real-life data
    894839        // set by about 25%
     
    921866        QBLevel tmp = search_cache.parent;
    922867
    923         ret = search_cache.search(search_bbox);
    924         if (ret == null) {
    925             ret = new ArrayList<T>();
    926         }
     868        search_cache.search(search_bbox, ret);
    927869
    928870        // A way that spans this bucket may be stored in one
    929871        // of the nodes which is a parent of the search cache
    930872        while (tmp != null) {
    931             List<T> content_result = tmp.search_contents(search_bbox);
    932             if (content_result != null) {
    933                 ret.addAll(content_result);
    934             }
     873            tmp.search_contents(search_bbox, ret);
    935874            tmp = tmp.parent;
    936875        }
Note: See TracChangeset for help on using the changeset viewer.