Changeset 3151 in josm for trunk/src/org/openstreetmap
- Timestamp:
- 2010-03-21T13:13:42+01:00 (15 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java
r3150 r3151 5 5 import java.util.Arrays; 6 6 import java.util.Collection; 7 import java.util.Collections;8 7 import java.util.Iterator; 9 import java.util.LinkedList;10 8 import java.util.List; 11 9 … … 222 220 return o.getBBox().intersects(search_bbox); 223 221 } 224 private List<T> search_contents(BBox search_bbox)222 private void search_contents(BBox search_bbox, List<T> result) 225 223 { 226 224 if (debug) { … … 232 230 */ 233 231 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 242 234 for (T o : content) { 243 235 if (matches(o, search_bbox)) { 244 re t.add(o);236 result.add(o); 245 237 } 246 238 } … … 248 240 out("done searching quad " + Long.toHexString(this.quad)); 249 241 } 250 return ret;251 242 } 252 243 /* … … 445 436 } 446 437 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 { 450 440 if (debug) { 451 441 System.out.print("[" + level + "] qb bbox: " + this.bbox() + " "); … … 456 446 //QuadTiling.tile2xy(this.quad); 457 447 } 458 return ret;448 return; 459 449 } 460 450 if (this.hasContent()) { 461 ret = this.search_contents(search_bbox);451 search_contents(search_bbox, result); 462 452 } 463 453 if (this.isLeaf()) 464 return ret; 465 //if (this.hasContent()) 466 // abort("branch had stuff"); 454 return; 455 467 456 if (debug) { 468 457 out("hit " + this.quads()); … … 483 472 System.out.print(i+": "); 484 473 } 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); 494 475 if (q.bbox().bounds(search_bbox)) { 495 476 search_cache = q; … … 497 478 // other tiles if this one wholly contained 498 479 // 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"); 504 482 } 505 }506 }507 return ret;483 break; 484 } 485 } 508 486 } 509 487 public String quads() … … 852 830 return false; 853 831 } 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) { 888 833 if (debug) { 889 834 out("qb root search at " + search_bbox); 890 835 out("root bbox: " + root.bbox()); 891 836 } 892 List<T> ret ;837 List<T> ret = new ArrayList<T>(); 893 838 // Doing this cuts down search cost on a real-life data 894 839 // set by about 25% … … 921 866 QBLevel tmp = search_cache.parent; 922 867 923 ret = search_cache.search(search_bbox); 924 if (ret == null) { 925 ret = new ArrayList<T>(); 926 } 868 search_cache.search(search_bbox, ret); 927 869 928 870 // A way that spans this bucket may be stored in one 929 871 // of the nodes which is a parent of the search cache 930 872 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); 935 874 tmp = tmp.parent; 936 875 }
Note:
See TracChangeset
for help on using the changeset viewer.