source: josm/trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java@ 2388

Last change on this file since 2388 was 2388, checked in by jttt, 14 years ago

Replace Dataset.nodes with getNodes(), etc
File size: 36.8 KB
Line 
1package org.openstreetmap.josm.data.osm;
2import java.lang.reflect.Array;
3import java.util.ArrayList;
4import java.util.Collection;
5import java.util.Collections;
6import java.util.HashMap;
7import java.util.Iterator;
8import java.util.LinkedList;
9import java.util.List;
10
11import org.openstreetmap.josm.data.coor.LatLon;
12import org.openstreetmap.josm.data.coor.QuadTiling;
13
14
15public class QuadBuckets<T extends OsmPrimitive> implements Collection<T>
16{
17 public static boolean debug = false;
18 static boolean consistency_testing = false;
19
20 static void abort(String s)
21 {
22 out(s);
23 Object o = null;
24 o.hashCode();
25 }
26 static void out(String s)
27 {
28 System.out.println(s);
29 }
30 // periodic output
31 long last_out = -1;
32 void pout(String s)
33 {
34 long now = System.currentTimeMillis();
35 if (now - last_out < 300)
36 return;
37 last_out = now;
38 System.out.print(s + "\r");
39 }
40 void pout(String s, int i, int total)
41 {
42 long now = System.currentTimeMillis();
43 if ((now - last_out < 300) &&
44 ((i+1) < total))
45 return;
46 last_out = now;
47 // cast to float to keep the output size down
48 System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done \r");
49 }
50 // 24 levels of buckets gives us bottom-level
51 // buckets that are about 2 meters on a side.
52 // That should do. :)
53 public static int NR_LEVELS = 24;
54 public static double WORLD_PARTS = (1 << NR_LEVELS);
55
56 public static int MAX_OBJECTS_PER_LEVEL = 16;
57 // has to be a power of 2
58 public static int TILES_PER_LEVEL_SHIFT = 2;
59 public static int TILES_PER_LEVEL = 1<<TILES_PER_LEVEL_SHIFT;
60 // Maybe this should just be a Rectangle??
61 public static class BBox
62 {
63 private double xmin = Double.POSITIVE_INFINITY;
64 private double xmax = Double.NEGATIVE_INFINITY;
65 private double ymin = Double.POSITIVE_INFINITY;
66 private double ymax = Double.NEGATIVE_INFINITY;
67 void sanity()
68 {
69 if (xmin < -180.0) {
70 xmin = -180.0;
71 }
72 if (xmax > 180.0) {
73 xmax = 180.0;
74 }
75 if (ymin < -90.0) {
76 ymin = -90.0;
77 }
78 if (ymax > 90.0) {
79 ymax = 90.0;
80 }
81 if ((xmin < -180.0) ||
82 (xmax > 180.0) ||
83 (ymin < -90.0) ||
84 (ymax > 90.0)) {
85 out("bad BBox: " + this);
86 Object o = null;
87 o.hashCode();
88 }
89 }
90 @Override
91 public String toString()
92 {
93 return "[ x: " + xmin + " -> " + xmax +
94 ", y: " + ymin + " -> " + ymax + " ]";
95 }
96 double min(double a, double b)
97 {
98 if (a < b)
99 return a;
100 return b;
101 }
102 double max(double a, double b)
103 {
104 if (a > b)
105 return a;
106 return b;
107 }
108 private void add(LatLon c)
109 {
110 xmin = min(xmin, c.lon());
111 xmax = max(xmax, c.lon());
112 ymin = min(ymin, c.lat());
113 ymax = max(ymax, c.lat());
114 }
115 public BBox(LatLon a, LatLon b)
116 {
117 add(a);
118 add(b);
119 sanity();
120 }
121 public BBox(double a_x, double a_y, double b_x, double b_y)
122 {
123 xmin = min(a_x, b_x);
124 xmax = max(a_x, b_x);
125 ymin = min(a_y, b_y);
126 ymax = max(a_y, b_y);
127 sanity();
128 }
129 public BBox(Way w)
130 {
131 for (Node n : w.getNodes()) {
132 LatLon coor = n.getCoor();
133 if (coor == null) {
134 continue;
135 }
136 add(coor);
137 }
138 this.sanity();
139 }
140 public double height()
141 {
142 return ymax-ymin;
143 }
144 public double width()
145 {
146 return xmax-xmin;
147 }
148 boolean bounds(BBox b)
149 {
150 if (!(xmin <= b.xmin) ||
151 !(xmax >= b.xmax) ||
152 !(ymin <= b.ymin) ||
153 !(ymax >= b.ymax))
154 return false;
155 return true;
156 }
157 boolean bounds(LatLon c)
158 {
159 if ((xmin <= c.lon()) &&
160 (xmax >= c.lon()) &&
161 (ymin <= c.lat()) &&
162 (ymax >= c.lat()))
163 return true;
164 return false;
165 }
166 boolean inside(BBox b)
167 {
168 if (xmin >= b.xmax)
169 return false;
170 if (xmax <= b.xmin)
171 return false;
172 if (ymin >= b.ymax)
173 return false;
174 if (ymax <= b.ymin)
175 return false;
176 return true;
177 }
178 boolean intersects(BBox b)
179 {
180 return this.inside(b) || b.inside(this);
181 }
182 List<LatLon> points()
183 {
184 LatLon p1 = new LatLon(ymin, xmin);
185 LatLon p2 = new LatLon(ymin, xmax);
186 LatLon p3 = new LatLon(ymax, xmin);
187 LatLon p4 = new LatLon(ymax, xmax);
188 List<LatLon> ret = new ArrayList<LatLon>();
189 ret.add(p1);
190 ret.add(p2);
191 ret.add(p3);
192 ret.add(p4);
193 return ret;
194 }
195 }
196 /*
197 * This is a quick hack. The problem is that we need the
198 * way's bounding box a *bunch* of times when it gets
199 * inserted. It gets expensive if we have to recreate
200 * them each time.
201 *
202 * An alternative would be to calculate it at .add() time
203 * and passing it down the call chain.
204 */
205 HashMap<Way,BBox> way_bbox_cache = new HashMap<Way, BBox>();
206 BBox way_bbox(Way w)
207 {
208 if (way_bbox_cache.size() > 100) {
209 way_bbox_cache.clear();
210 }
211 BBox b = way_bbox_cache.get(w);
212 if (b == null) {
213 b = new BBox(w);
214 way_bbox_cache.put(w, b);
215 }
216 return b;
217 //return new BBox(w);
218 }
219
220 class QBLevel
221 {
222 int level;
223 long quad;
224 QBLevel parent;
225
226 public List<T> content;
227 public QBLevel children[];
228 @Override
229 public String toString()
230 {
231 return super.toString()+ "["+level+"]: " + bbox;
232 }
233 public QBLevel(QBLevel parent)
234 {
235 init(parent);
236 }
237 String quads(T o)
238 {
239 if (o instanceof Node) {
240 LatLon coor = ((Node)o).getCoor();
241 if (coor == null)
242 return "null node coordinates";
243 return Long.toHexString(QuadTiling.quadTile(coor));
244 }
245 return "Way??";
246 }
247 boolean remove_content(T o)
248 {
249 boolean ret = this.content.remove(o);
250 if (this.content.size() == 0) {
251 this.content = null;
252 }
253 return ret;
254 }
255 @SuppressWarnings("unchecked")
256 QBLevel[] newChildren()
257 {
258 // This is ugly and hackish. But, it seems to work,
259 // and using an ArrayList here seems to cost us
260 // a significant performance penalty -- 50% in my
261 // testing. Child access is one of the single
262 // hottest code paths in this entire class.
263 return (QBLevel[])Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL);
264 }
265 // Get the correct index for the given primitive
266 // at the given level. If the primitive can not
267 // fit into a single quad at this level, return -1
268 int get_index(T o, int level)
269 {
270 if (debug) {
271 out("getting index for " + o + " at level: " + level);
272 }
273 if (o instanceof Node) {
274 Node n = (Node)o;
275 LatLon coor = ((Node)o).getCoor();
276 if (coor == null)
277 return -1;
278 return QuadTiling.index(coor, level);
279 }
280 if (o instanceof Way) {
281 Way w = (Way)o;
282 int index = -1;
283 //for (Node n : w.getNodes()) {
284 for (LatLon c : way_bbox(w).points()) {
285 // LatLon c = n.getCoor();
286 if (debug) {
287 out("getting index for point: " + c);
288 }
289 if (index == -1) {
290 index = QuadTiling.index(c, level);
291 if (debug) {
292 out("set initial way index to: " + index);
293 }
294 continue;
295 }
296 int node_index = QuadTiling.index(c, level);
297 if (debug) {
298 out("other node way index: " + node_index);
299 }
300 if (node_index != index) {
301 // This happens at level 0 sometimes when a way has no
302 // nodes present.
303 if (debug) {
304 out("way ("+w.getId()+") would have gone across two quads "
305 + node_index + "/" + index + " at level: " + level + " ");
306 out("node count: " + w.getNodes().size());
307 for (LatLon c2 : way_bbox(w).points()) {
308 out("points: " + c2);
309 }
310 }
311 return -1;
312 }
313 }
314 return index;
315 }
316 abort("bad primitive: " + o);
317 return -1;
318 }
319 void split()
320 {
321 if (debug) {
322 out("splitting "+this.bbox()+" level "+level+" with "
323 + content.size() + " entries (my dimensions: "
324 + this.bbox.width()+", "+this.bbox.height()+")");
325 }
326 if (children != null) {
327 abort("overwrote children");
328 }
329 children = newChildren();
330 // deferring allocation of children until use
331 // seems a bit faster
332 //for (int i = 0; i < TILES_PER_LEVEL; i++)
333 // children[i] = new QBLevel(this, i);
334 List<T> tmpcontent = content;
335 content = null;
336 for (T o : tmpcontent) {
337 int new_index = get_index(o, level);
338 if (new_index == -1) {
339 this.add_content(o);
340 //out("adding content to branch: " + this);
341 continue;
342 }
343 if (children[new_index] == null) {
344 children[new_index] = new QBLevel(this, new_index);
345 }
346 QBLevel child = children[new_index];
347 if (debug) {
348 out("putting "+o+"(q:"+quads(o)+") into ["+new_index+"] " + child.bbox());
349 }
350 child.add(o);
351 }
352 }
353 boolean add_content(T o)
354 {
355 boolean ret = false;
356 if (content == null) {
357 content = new ArrayList<T>();
358 }
359 ret = content.add(o);
360 if (debug && !this.isLeaf()) {
361 pout("added "+o.getClass().getName()+" to non-leaf with size: " + content.size());
362 }
363 return ret;
364 }
365 void add_to_leaf(T o)
366 {
367 QBLevel ret = this;
368 add_content(o);
369 if (content.size() > MAX_OBJECTS_PER_LEVEL) {
370 if (debug) {
371 out("["+level+"] deciding to split");
372 }
373 if (level >= NR_LEVELS-1) {
374 out("can not split, but too deep: " + level + " size: " + content.size());
375 return;
376 }
377 int before_size = -1;
378 if (consistency_testing) {
379 before_size = this.size();
380 }
381 this.split();
382 if (consistency_testing) {
383 int after_size = this.size();
384 if (before_size != after_size) {
385 abort("["+level+"] split done before: " + before_size + " after: " + after_size);
386 }
387 }
388 return;
389 }
390 }
391
392 boolean matches(T o, BBox search_bbox)
393 {
394 if (o instanceof Node) {
395 LatLon coor = ((Node)o).getCoor();
396 if (coor == null)
397 return false;
398 return search_bbox.bounds(coor);
399 }
400 if (o instanceof Way) {
401 BBox bbox = way_bbox((Way)o);
402 return bbox.intersects(search_bbox);
403 }
404 abort("matches() bad primitive: " + o);
405 return false;
406 }
407 private List<T> search_contents(BBox search_bbox)
408 {
409 String size = "null";
410 if (content != null) {
411 size = ""+content.size();
412 }
413 if (debug) {
414 out("searching contents (size: "+size+") for " + search_bbox);
415 }
416 /*
417 * It is possible that this was created in a split
418 * but never got any content populated.
419 */
420 if (content == null)
421 return null;
422 // We could delay allocating this. But, the way it is currently
423 // used, we almost always have a node in the area that we're
424 // searching since we're searching around other nodes.
425 //
426 // the iterator's calls to ArrayList.size() were showing up in
427 // some profiles, so I'm trying a LinkedList instead
428 List<T> ret = new LinkedList<T>();
429 for (T o : content) {
430 if (matches(o, search_bbox)) {
431 ret.add(o);
432 }
433 }
434 if (debug) {
435 out("done searching quad " + Long.toHexString(this.quad));
436 }
437 return ret;
438 }
439 /*
440 * This is stupid. I tried to have a QBLeaf and QBBranch
441 * class decending from a QBLevel. It's more than twice
442 * as slow. So, this throws OO out the window, but it
443 * is fast. Runtime type determination must be slow.
444 */
445 boolean isLeaf()
446 {
447 if (children == null)
448 return true;
449 return false;
450 }
451 QBLevel next_sibling()
452 {
453 boolean found_me = false;
454 if (parent == null)
455 return null;
456 int __nr = 0;
457 for (QBLevel sibling : parent.children) {
458 __nr++;
459 int nr = __nr-1;
460 if (sibling == null) {
461 if (debug) {
462 out("[" + this.level + "] null child nr: " + nr);
463 }
464 continue;
465 }
466 // We're looking for the *next* child
467 // after us.
468 if (sibling == this) {
469 if (debug) {
470 out("[" + this.level + "] I was child nr: " + nr);
471 }
472 found_me = true;
473 continue;
474 }
475 if (found_me) {
476 if (debug) {
477 out("[" + this.level + "] next sibling was child nr: " + nr);
478 }
479 return sibling;
480 }
481 if (debug) {
482 out("[" + this.level + "] nr: " + nr + " is before me, ignoring...");
483 }
484 }
485 return null;
486 }
487 boolean hasContent()
488 {
489 if (content == null)
490 return false;
491 return true;
492 }
493 QBLevel nextContentNode()
494 {
495 QBLevel next = this;
496 if (this.isLeaf()) {
497 QBLevel sibling = next.next_sibling();
498 // Walk back up the tree to find the
499 // next sibling node. It may be either
500 // a leaf or branch.
501 while (sibling == null) {
502 if (debug) {
503 out("no siblings at level["+next.level+"], moving to parent");
504 }
505 next = next.parent;
506 if (next == null) {
507 break;
508 }
509 sibling = next.next_sibling();
510 }
511 next = sibling;
512 }
513 if (next == null)
514 return null;
515 // all branches are guaranteed to have
516 // at least one leaf. It may not have
517 // any contents, but there *will* be a
518 // leaf. So, walk back down the tree
519 // and find the first leaf
520 while (!next.isLeaf()) {
521 if (next.hasContent() && next != this) {
522 break;
523 }
524 if (debug) {
525 out("["+next.level+"] next node ("+next+") is a branch (content: "+next.hasContent()+"), moving down...");
526 }
527 for (QBLevel child : next.children) {
528 if (child == null) {
529 continue;
530 }
531 next = child;
532 break;
533 }
534 }
535 return next;
536 }
537 int size()
538 {
539 if (isLeaf())
540 return size_leaf();
541 return size_branch();
542 }
543 private int size_leaf()
544 {
545 if (content == null) {
546 if (debug) {
547 out("["+level+"] leaf size: null content, children? " + children);
548 }
549 return 0;
550 }
551 if (debug) {
552 out("["+level+"] leaf size: " + content.size());
553 }
554 return content.size();
555 }
556 private int size_branch()
557 {
558 int ret = 0;
559 for (QBLevel l : children) {
560 if (l == null) {
561 continue;
562 }
563 ret += l.size();
564 }
565 if (content != null) {
566 ret += content.size();
567 }
568 if (debug) {
569 out("["+level+"] branch size: " + ret);
570 }
571 return ret;
572 }
573 boolean contains(T n)
574 {
575 QBLevel res = find_exact(n);
576 if (res == null)
577 return false;
578 return true;
579 }
580 QBLevel find_exact(T n)
581 {
582 QBLevel ret = null;
583 if (content != null && content.contains(n))
584 return this;
585 return find_exact_child(n);
586 }
587 private QBLevel find_exact_child(T n)
588 {
589 QBLevel ret = null;
590 if (children == null)
591 return ret;
592 for (QBLevel l : children) {
593 if (l == null) {
594 continue;
595 }
596 ret = l.find_exact(n);
597 if (ret != null) {
598 break;
599 }
600 }
601 return ret;
602 }
603 boolean add(T n)
604 {
605 if (consistency_testing) {
606 if (!matches(n, this.bbox())) {
607 out("-----------------------------");
608 debug = true;
609 get_index(n, level);
610 abort("object " + n + " does not belong in node at level: " + level + " bbox: " + this.bbox());
611 }
612 }
613 if (isLeaf()) {
614 add_to_leaf(n);
615 } else {
616 add_to_branch(n);
617 }
618 return true;
619 }
620 QBLevel add_to_branch(T n)
621 {
622 int index = get_index(n, level);
623 if (index == -1) {
624 if (debug) {
625 out("unable to get index for " + n + "at level: " + level + ", adding content to branch: " + this);
626 }
627 this.add_content(n);
628 return this;
629 }
630 if (debug) {
631 out("[" + level + "]: " + n +
632 " index " + index + " levelquad:" + this.quads() + " level bbox:" + this.bbox());
633 out(" put in child["+index+"]");
634 }
635 if (children[index] == null) {
636 children[index] = new QBLevel(this, index);
637 }
638 children[index].add(n);
639 return this;
640 }
641 private List<T> search(BBox search_bbox)
642 {
643 List<T> ret = null;
644 if (debug) {
645 System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
646 }
647 if (!this.bbox().intersects(search_bbox)) {
648 if (debug) {
649 out("miss " + Long.toHexString(this.quad));
650 //QuadTiling.tile2xy(this.quad);
651 }
652 return ret;
653 }
654 if (this.hasContent()) {
655 ret = this.search_contents(search_bbox);
656 }
657 if (this.isLeaf())
658 return ret;
659 //if (this.hasContent())
660 // abort("branch had stuff");
661 if (debug) {
662 out("hit " + this.quads());
663 }
664
665 if (debug) {
666 out("[" + level + "] not leaf, moving down");
667 }
668 for (int i = 0; i < children.length; i++) {
669 QBLevel q = children[i];
670 if (debug) {
671 out("child["+i+"]: " + q);
672 }
673 if (q == null) {
674 continue;
675 }
676 if (debug) {
677 System.out.print(i+": ");
678 }
679 List<T> coors = q.search(search_bbox);
680 if (coors == null) {
681 continue;
682 }
683 if (ret == null) {
684 ret = coors;
685 } else {
686 ret.addAll(coors);
687 }
688 if (q.bbox().bounds(search_bbox)) {
689 search_cache = q;
690 // optimization: do not continue searching
691 // other tiles if this one wholly contained
692 // what we were looking for.
693 if (coors.size() > 0 ) {
694 if (debug) {
695 out("break early");
696 }
697 break;
698 }
699 }
700 }
701 return ret;
702 }
703 public String quads()
704 {
705 return Long.toHexString(quad);
706 }
707 public void init(QBLevel parent)
708 {
709 this.parent = parent;
710 if (parent == null) {
711 this.level = 0;
712 } else {
713 this.level = parent.level + 1;
714 }
715 this.quad = 0;
716 }
717 int index_of(QBLevel find_this)
718 {
719 if (this.isLeaf())
720 return -1;
721
722 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
723 if (children[i] == find_this)
724 return i;
725 }
726 return -1;
727 }
728 public QBLevel(QBLevel parent, int parent_index)
729 {
730 this.init(parent);
731 int shift = (QuadBuckets.NR_LEVELS - level) * 2;
732 long mult = 1;
733 // Java blows the big one. It seems to wrap when
734 // you shift by > 31
735 if (shift >= 30) {
736 shift -= 30;
737 mult = 1<<30;
738 }
739 long this_quadpart = mult * (parent_index << shift);
740 this.quad = parent.quad | this_quadpart;
741 if (debug) {
742 out("new level["+this.level+"] bbox["+parent_index+"]: " + this.bbox()
743 + " coor: " + this.coor()
744 + " quadpart: " + Long.toHexString(this_quadpart)
745 + " quad: " + Long.toHexString(this.quad));
746 }
747 }
748 /*
749 * Surely we can calculate these efficiently instead of storing
750 */
751 double width = Double.NEGATIVE_INFINITY;
752 double width()
753 {
754 if (width != Double.NEGATIVE_INFINITY)
755 return this.width;
756 if (level == 0) {
757 width = this.bbox().width();
758 } else {
759 width = parent.width()/2;
760 }
761 return width;
762 }
763 double height()
764 {
765 return width()/2;
766 }
767 BBox bbox = null;
768 public BBox bbox()
769 {
770 if (bbox != null) {
771 bbox.sanity();
772 return bbox;
773 }
774 if (level == 0) {
775 bbox = new BBox(-180, 90, 180, -90);
776 } else {
777 LatLon bottom_left = this.coor();
778 double lat = bottom_left.lat() + this.height();
779 double lon = bottom_left.lon() + this.width();
780 LatLon top_right = new LatLon(lat, lon);
781 bbox = new BBox(bottom_left, top_right);
782 }
783 bbox.sanity();
784 return bbox;
785 }
786 /*
787 * This gives the coordinate of the bottom-left
788 * corner of the box
789 */
790 LatLon coor()
791 {
792 return QuadTiling.tile2LatLon(this.quad);
793 }
794 }
795
796 private QBLevel root;
797 private QBLevel search_cache;
798 public QuadBuckets()
799 {
800 clear();
801 }
802 public void clear()
803 {
804 root = new QBLevel(null);
805 search_cache = null;
806 if (debug) {
807 out("QuadBuckets() cleared: " + this);
808 out("root: " + root + " level: " + root.level + " bbox: " + root.bbox());
809 }
810 }
811 public boolean add(T n)
812 {
813 if (debug) {
814 out("QuadBuckets() add: " + n + " size now: " + this.size());
815 }
816 int before_size = -1;
817 if (consistency_testing) {
818 before_size = root.size();
819 }
820 boolean ret;
821 // A way with no nodes will have an infinitely large
822 // bounding box. Just stash it in the root node.
823 if (!n.isUsable()) {
824 ret = root.add_content(n);
825 } else {
826 ret = root.add(n);
827 }
828 if (consistency_testing) {
829 int end_size = root.size();
830 if (ret) {
831 end_size--;
832 }
833 if (before_size != end_size) {
834 abort("size inconsistency before add: " + before_size + " after: " + end_size);
835 }
836 }
837 if (debug) {
838 out("QuadBuckets() add: " + n + " size after: " + this.size());
839 }
840 return ret;
841 }
842 public void reindex()
843 {
844 QBLevel newroot = new QBLevel(null);
845 Iterator<T> i = this.iterator();
846 while (i.hasNext()) {
847 T o = i.next();
848 newroot.add(o);
849 }
850 root = newroot;
851 }
852 public void unsupported()
853 {
854 out("unsupported operation");
855 throw new UnsupportedOperationException();
856 }
857 public boolean retainAll(Collection objects)
858 {
859 for (T o : this) {
860 if (objects.contains(o)) {
861 continue;
862 }
863 if (!this.remove(o))
864 return false;
865 }
866 return true;
867 }
868 boolean canStore(Object o)
869 {
870 if (o instanceof Way)
871 return true;
872 if (o instanceof Node)
873 return true;
874 return false;
875 }
876 public boolean removeAll(Collection objects)
877 {
878 for (Object o : objects) {
879 if (!canStore(o))
880 return false;
881 if (!this.remove(o))
882 return false;
883 }
884 return true;
885 }
886 public boolean addAll(Collection objects)
887 {
888 for (Object o : objects) {
889 if (!canStore(o))
890 return false;
891 if (!this.add(convert(o)))
892 return false;
893 }
894 return true;
895 }
896 public boolean containsAll(Collection objects)
897 {
898 boolean ret = true;
899 for (Object o : objects) {
900 if (!canStore(o))
901 return false;
902 if (!this.contains(o))
903 return false;
904 }
905 return true;
906 }
907 private void check_type(Object o)
908 {
909 if (canStore(o))
910 return;
911 unsupported();
912 }
913 // If anyone has suggestions for how to fix
914 // this properly, I'm listening :)
915 @SuppressWarnings("unchecked")
916 private T convert(Object raw)
917 {
918 return (T)raw;
919 }
920 public boolean remove(Object o)
921 {
922 check_type(o);
923 return this.remove(convert(o));
924 }
925 public boolean remove_slow(T removeme)
926 {
927 boolean ret = false;
928 Iterator<T> i = this.iterator();
929 while (i.hasNext()) {
930 T o = i.next();
931 if (o != removeme) {
932 continue;
933 }
934 i.remove();
935 ret = true;
936 break;
937 }
938 if (debug) {
939 out("qb slow remove result: " + ret);
940 }
941 return ret;
942 }
943 public boolean remove(T o)
944 {
945 /*
946 * We first try a locational search
947 */
948 QBLevel bucket = root.find_exact(o);
949 if (o instanceof Way) {
950 way_bbox_cache.remove(o);
951 }
952 /*
953 * That may fail because the object was
954 * moved or changed in some way, so we
955 * resort to an iterative search:
956 */
957 if (bucket == null)
958 return remove_slow(o);
959 boolean ret = bucket.remove_content(o);
960 if (debug) {
961 out("qb remove result: " + ret);
962 }
963 return ret;
964 }
965 public boolean contains(Object o)
966 {
967 if (!canStore(o))
968 return false;
969 QBLevel bucket = root.find_exact(convert(o));
970 if (bucket == null)
971 return false;
972 return true;
973 }
974 public ArrayList<T> toArrayList()
975 {
976 ArrayList<T> a = new ArrayList<T>();
977 for (T n : this) {
978 a.add(n);
979 }
980 if (debug) {
981 out("returning array list with size: " + a.size());
982 }
983 return a;
984 }
985 public Object[] toArray()
986 {
987 return this.toArrayList().toArray();
988 }
989 public <T> T[] toArray(T[] template)
990 {
991 return this.toArrayList().toArray(template);
992 }
993 class QuadBucketIterator implements Iterator<T>
994 {
995 QBLevel current_node;
996 int content_index;
997 int iterated_over;
998 QBLevel next_content_node(QBLevel q)
999 {
1000 if (q == null)
1001 return null;
1002 QBLevel orig = q;
1003 QBLevel next = q.nextContentNode();
1004 //if (consistency_testing && (orig == next))
1005 if (orig == next) {
1006 abort("got same leaf back leaf: " + q.isLeaf());
1007 }
1008 return next;
1009 }
1010 public QuadBucketIterator(QuadBuckets<T> qb)
1011 {
1012 if (debug) {
1013 out(this + " is a new iterator qb: " + qb + " size: " + qb.size());
1014 }
1015 if (qb.root.isLeaf() || qb.root.hasContent()) {
1016 current_node = qb.root;
1017 } else {
1018 current_node = next_content_node(qb.root);
1019 }
1020 if (debug) {
1021 out("\titerator first leaf: " + current_node);
1022 }
1023 iterated_over = 0;
1024 }
1025 public boolean hasNext()
1026 {
1027 if (this.peek() == null) {
1028 if (debug) {
1029 out(this + " no hasNext(), but iterated over so far: " + iterated_over);
1030 }
1031 return false;
1032 }
1033 return true;
1034 }
1035 T peek()
1036 {
1037 if (current_node == null) {
1038 if (debug) {
1039 out("null current leaf, nowhere to go");
1040 }
1041 return null;
1042 }
1043 while((current_node.content == null) ||
1044 (content_index >= current_node.content.size())) {
1045 if (debug) {
1046 out("moving to next leaf");
1047 }
1048 content_index = 0;
1049 current_node = next_content_node(current_node);
1050 if (current_node == null) {
1051 break;
1052 }
1053 }
1054 if (current_node == null || current_node.content == null) {
1055 if (debug) {
1056 out("late nowhere to go " + current_node);
1057 }
1058 return null;
1059 }
1060 return current_node.content.get(content_index);
1061 }
1062 public T next()
1063 {
1064 T ret = peek();
1065 content_index++;
1066 if (debug) {
1067 out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node);
1068 }
1069 iterated_over++;
1070 if (ret == null) {
1071 if (debug) {
1072 out(this + " no next node, but iterated over so far: " + iterated_over);
1073 }
1074 }
1075 return ret;
1076 }
1077 public void remove()
1078 {
1079 // two uses
1080 // 1. Back up to the thing we just returned
1081 // 2. move the index back since we removed
1082 // an element
1083 content_index--;
1084 T object = peek();
1085 current_node.content.remove(content_index);
1086 }
1087 }
1088 public Iterator<T> iterator()
1089 {
1090 return new QuadBucketIterator(this);
1091 }
1092 public int size()
1093 {
1094 // This can certainly by optimized
1095 int ret = root.size();
1096 if (debug) {
1097 out(this + " QuadBuckets size: " + ret);
1098 }
1099 return ret;
1100 }
1101 public int size_iter()
1102 {
1103 int count = 0;
1104 Iterator<T> i = this.iterator();
1105 while (i.hasNext()) {
1106 i.next();
1107 count++;
1108 }
1109 return count;
1110 }
1111 public boolean isEmpty()
1112 {
1113 if (this.size() == 0)
1114 return true;
1115 return false;
1116 }
1117 public BBox search_to_bbox(LatLon point, double radius)
1118 {
1119 BBox bbox = new BBox(point.lon() - radius, point.lat() - radius,
1120 point.lon() + radius, point.lat() + radius);
1121 if (debug) {
1122 out("search bbox before sanity: " + bbox);
1123 }
1124 bbox.sanity();
1125 if (debug) {
1126 out("search bbox after sanity: " + bbox);
1127 }
1128 return bbox;
1129 }
1130 List<T> search(Way w)
1131 {
1132 BBox way_bbox = new BBox(w);
1133 return this.search(way_bbox);
1134 }
1135 public List<T> search(Node n, double radius)
1136 {
1137 return this.search(n.getCoor(), radius);
1138 }
1139 public List<T> search(LatLon point, double radius)
1140 {
1141 if (point == null)
1142 return Collections.emptyList();
1143 return this.search(search_to_bbox(point, radius));
1144 }
1145 public List<T> search(LatLon b1, LatLon b2)
1146 {
1147 BBox bbox = new BBox(b1.lon(), b1.lat(), b2.lon(), b2.lat());
1148 bbox.sanity();
1149 return this.search(bbox);
1150 }
1151 List<T> search(BBox search_bbox)
1152 {
1153 if (debug) {
1154 out("qb root search at " + search_bbox);
1155 out("root bbox: " + root.bbox());
1156 }
1157 List<T> ret;
1158 // Doing this cuts down search cost on a real-life data
1159 // set by about 25%
1160 boolean cache_searches = true;
1161 if (cache_searches) {
1162 if (search_cache == null) {
1163 search_cache = root;
1164 }
1165 // Walk back up the tree when the last
1166 // search spot can not cover the current
1167 // search
1168 while (!search_cache.bbox().bounds(search_bbox)) {
1169 if (debug) {
1170 out("bbox: " + search_bbox);
1171 }
1172 if (debug) {
1173 out("search_cache: " + search_cache + " level: " + search_cache.level);
1174 out("search_cache.bbox(): " + search_cache.bbox());
1175 }
1176 search_cache = search_cache.parent;
1177 if (debug) {
1178 out("new search_cache: " + search_cache);
1179 }
1180 }
1181 } else {
1182 search_cache = root;
1183 }
1184 ret = search_cache.search(search_bbox);
1185 if (ret == null) {
1186 ret = new ArrayList<T>();
1187 }
1188 // A way that spans this bucket may be stored in one
1189 // of the nodes which is a parent of the search cache
1190 QBLevel tmp = search_cache.parent;
1191 while (tmp != null) {
1192 List<T> content_result = tmp.search_contents(search_bbox);
1193 if (content_result != null) {
1194 ret.addAll(content_result);
1195 }
1196 tmp = tmp.parent;
1197 }
1198 if (ret == null || ret.size() == 0)
1199 return Collections.emptyList();
1200 if (debug) {
1201 out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size());
1202 }
1203 return ret;
1204 }
1205}
Note: See TracBrowser for help on using the repository browser.