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

Last change on this file since 2425 was 2425, checked in by hansendc, 14 years ago

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