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

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

This should fix #3909

We created empty branches when we attempted to split a QB node
with ways in it and none of the ways could fit into a child.
The children were allocated before we knew that we had something
to put in them, and we ended up with an empty array of children.
That triggered this check.

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