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

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

Simply QuadBuckets iterator.

This should make things much clearer and less buggy. There
have been a good number of bugs in here lately.
File size: 36.9 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 nextNode()
474 {
475 if (this.isLeaf())
476 return this.nextSibling();
477 return this.firstChild();
478 }
479 QBLevel nextContentNode()
480 {
481 QBLevel next = this.nextNode();
482 if (next == null)
483 return next;
484 if (next.hasContent())
485 return next;
486 return next.nextContentNode();
487 }
488 int size()
489 {
490 if (isLeaf())
491 return size_leaf();
492 return size_branch();
493 }
494 private int size_leaf()
495 {
496 if (content == null) {
497 if (debug) {
498 out("["+level+"] leaf size: null content, children? " + Arrays.toString(children));
499 }
500 return 0;
501 }
502 if (debug) {
503 out("["+level+"] leaf size: " + content.size());
504 }
505 return content.size();
506 }
507 private int size_branch()
508 {
509 int ret = 0;
510 for (QBLevel l : children) {
511 if (l == null) {
512 continue;
513 }
514 ret += l.size();
515 }
516 if (content != null) {
517 ret += content.size();
518 }
519 if (debug) {
520 out("["+level+"] branch size: " + ret);
521 }
522 return ret;
523 }
524 boolean contains(T n)
525 {
526 QBLevel res = find_exact(n);
527 if (res == null)
528 return false;
529 return true;
530 }
531 QBLevel find_exact(T n)
532 {
533 if (content != null && content.contains(n))
534 return this;
535 return find_exact_child(n);
536 }
537 private QBLevel find_exact_child(T n)
538 {
539 QBLevel ret = null;
540 if (children == null)
541 return ret;
542 for (QBLevel l : children) {
543 if (l == null) {
544 continue;
545 }
546 ret = l.find_exact(n);
547 if (ret != null) {
548 break;
549 }
550 }
551 return ret;
552 }
553 boolean add(T n)
554 {
555 if (consistency_testing) {
556 if (!matches(n, this.bbox())) {
557 out("-----------------------------");
558 debug = true;
559 get_index(n, level);
560 get_index(n, level-1);
561 int nr = 0;
562 for (QBLevel sibling : parent.children) {
563 out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling));
564 }
565 abort("\nobject " + n + " does not belong in node at level: " + level + " bbox: " + this.bbox());
566 }
567 }
568 synchronized (split_lock) {
569 if (isLeaf()) {
570 __add_to_leaf(n);
571 } else {
572 __add_to_branch(n);
573 }
574 }
575 return true;
576 }
577 QBLevel __add_to_branch(T n)
578 {
579 int index = get_index(n, level);
580 if (index == -1) {
581 if (debug) {
582 out("unable to get index for " + n + "at level: " + level + ", adding content to branch: " + this);
583 }
584 this.__add_content(n);
585 return this;
586 }
587 if (debug) {
588 out("[" + level + "]: " + n +
589 " index " + index + " levelquad:" + this.quads() + " level bbox:" + this.bbox());
590 out(" put in child["+index+"]");
591 }
592 if (children[index] == null) {
593 children[index] = new QBLevel(this, index);
594 }
595 children[index].add(n);
596 return this;
597 }
598 private List<T> search(BBox search_bbox)
599 {
600 List<T> ret = null;
601 if (debug) {
602 System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
603 }
604 if (!this.bbox().intersects(search_bbox)) {
605 if (debug) {
606 out("miss " + Long.toHexString(this.quad));
607 //QuadTiling.tile2xy(this.quad);
608 }
609 return ret;
610 }
611 if (this.hasContent()) {
612 ret = this.search_contents(search_bbox);
613 }
614 if (this.isLeaf())
615 return ret;
616 //if (this.hasContent())
617 // abort("branch had stuff");
618 if (debug) {
619 out("hit " + this.quads());
620 }
621
622 if (debug) {
623 out("[" + level + "] not leaf, moving down");
624 }
625 for (int i = 0; i < children.length; i++) {
626 QBLevel q = children[i];
627 if (debug) {
628 out("child["+i+"]: " + q);
629 }
630 if (q == null) {
631 continue;
632 }
633 if (debug) {
634 System.out.print(i+": ");
635 }
636 List<T> coors = q.search(search_bbox);
637 if (coors == null) {
638 continue;
639 }
640 if (ret == null) {
641 ret = coors;
642 } else {
643 ret.addAll(coors);
644 }
645 if (q.bbox().bounds(search_bbox)) {
646 search_cache = q;
647 // optimization: do not continue searching
648 // other tiles if this one wholly contained
649 // what we were looking for.
650 if (coors.size() > 0 ) {
651 if (debug) {
652 out("break early");
653 }
654 break;
655 }
656 }
657 }
658 return ret;
659 }
660 public String quads()
661 {
662 return Long.toHexString(quad);
663 }
664 public void init(QBLevel parent)
665 {
666 this.parent = parent;
667 if (parent == null) {
668 this.level = 0;
669 } else {
670 this.level = parent.level + 1;
671 }
672 this.quad = 0;
673 }
674 int index_of(QBLevel find_this)
675 {
676 if (this.isLeaf())
677 return -1;
678
679 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
680 if (children[i] == find_this)
681 return i;
682 }
683 return -1;
684 }
685 public QBLevel(QBLevel parent, int parent_index)
686 {
687 this.init(parent);
688 int shift = (QuadBuckets.NR_LEVELS - level) * 2;
689 long mult = 1;
690 // Java blows the big one. It seems to wrap when
691 // you shift by > 31
692 if (shift >= 30) {
693 shift -= 30;
694 mult = 1<<30;
695 }
696 long this_quadpart = mult * (parent_index << shift);
697 this.quad = parent.quad | this_quadpart;
698 if (debug) {
699 out("new level["+this.level+"] bbox["+parent_index+"]: " + this.bbox()
700 + " coor: " + this.coor()
701 + " quadpart: " + Long.toHexString(this_quadpart)
702 + " quad: " + Long.toHexString(this.quad));
703 }
704 }
705 /*
706 * Surely we can calculate these efficiently instead of storing
707 */
708 double width = Double.NEGATIVE_INFINITY;
709 double width()
710 {
711 if (width != Double.NEGATIVE_INFINITY)
712 return this.width;
713 if (level == 0) {
714 width = this.bbox().width();
715 } else {
716 width = parent.width()/2;
717 }
718 return width;
719 }
720 double height()
721 {
722 return width()/2;
723 }
724 BBox bbox = null;
725 public BBox bbox()
726 {
727 if (bbox != null) {
728 bbox.sanity();
729 return bbox;
730 }
731 if (level == 0) {
732 bbox = new BBox(-180, 90, 180, -90);
733 } else {
734 LatLon bottom_left = this.coor();
735 double lat = bottom_left.lat() + this.height();
736 double lon = bottom_left.lon() + this.width();
737 LatLon top_right = new LatLon(lat, lon);
738 bbox = new BBox(bottom_left, top_right);
739 }
740 bbox.sanity();
741 return bbox;
742 }
743 /*
744 * This gives the coordinate of the bottom-left
745 * corner of the box
746 */
747 LatLon coor()
748 {
749 return QuadTiling.tile2LatLon(this.quad);
750 }
751 boolean hasChildren()
752 {
753 if (children == null)
754 return false;
755
756 for (QBLevel child : children) {
757 if (child != null)
758 return true;
759 }
760 return false;
761 }
762 void remove_from_parent()
763 {
764 if (parent == null)
765 return;
766
767 int nr_siblings = 0;
768 for (int i = 0; i < parent.children.length; i++) {
769 QBLevel sibling = parent.children[i];
770 if (sibling != null) {
771 nr_siblings++;
772 }
773 if (sibling != this) {
774 continue;
775 }
776 if (!canRemove()) {
777 abort("attempt to remove non-empty child: " + this.content + " " + this.children);
778 }
779 parent.children[i] = null;
780 nr_siblings--;
781 }
782 if (parent.canRemove()) {
783 parent.remove_from_parent();
784 }
785 }
786 boolean canRemove()
787 {
788 if (content != null && content.size() > 0)
789 return false;
790 if (this.hasChildren())
791 return false;
792 return true;
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 synchronized (split_lock) {
825 ret = root.__add_content(n);
826 }
827 } else {
828 ret = root.add(n);
829 }
830 if (consistency_testing) {
831 int end_size = root.size();
832 if (ret) {
833 end_size--;
834 }
835 if (before_size != end_size) {
836 abort("size inconsistency before add: " + before_size + " after: " + end_size);
837 }
838 }
839 if (debug) {
840 out("QuadBuckets() add: " + n + " size after: " + this.size());
841 }
842 return ret;
843 }
844 public void reindex()
845 {
846 QBLevel newroot = new QBLevel(null);
847 Iterator<T> i = this.iterator();
848 while (i.hasNext()) {
849 T o = i.next();
850 newroot.add(o);
851 }
852 root = newroot;
853 }
854 public void unsupported()
855 {
856 out("unsupported operation");
857 throw new UnsupportedOperationException();
858 }
859 public boolean retainAll(Collection<?> objects)
860 {
861 for (T o : this) {
862 if (objects.contains(o)) {
863 continue;
864 }
865 if (!this.remove(o))
866 return false;
867 }
868 return true;
869 }
870 public boolean removeAll(Collection<?> objects)
871 {
872 boolean changed = false;
873 for (Object o : objects) {
874 changed = changed | remove(o);
875 }
876 return changed;
877 }
878 public boolean addAll(Collection<? extends T> objects)
879 {
880 boolean changed = false;
881 for (Object o : objects) {
882 changed = changed | this.add(convert(o));
883 }
884 return changed;
885 }
886 public boolean containsAll(Collection<?> objects)
887 {
888 for (Object o : objects) {
889 if (!this.contains(o))
890 return false;
891 }
892 return true;
893 }
894 // If anyone has suggestions for how to fix
895 // this properly, I'm listening :)
896 @SuppressWarnings("unchecked")
897 private T convert(Object raw)
898 {
899 return (T)raw;
900 }
901 public boolean remove(Object o)
902 {
903 return this.remove(convert(o));
904 }
905 public boolean remove_slow(T removeme)
906 {
907 boolean ret = false;
908 Iterator<T> i = this.iterator();
909 while (i.hasNext()) {
910 T o = i.next();
911 if (o != removeme) {
912 continue;
913 }
914 i.remove();
915 ret = true;
916 break;
917 }
918 if (debug) {
919 out("qb slow remove result: " + ret);
920 }
921 return ret;
922 }
923 public boolean remove(T o)
924 {
925 /*
926 * We first try a locational search
927 */
928 QBLevel bucket = root.find_exact(o);
929 /*
930 * That may fail because the object was
931 * moved or changed in some way, so we
932 * resort to an iterative search:
933 */
934 if (bucket == null)
935 return remove_slow(o);
936 boolean ret = bucket.remove_content(o);
937 if (debug) {
938 out("qb remove result: " + ret);
939 }
940 return ret;
941 }
942 public boolean contains(Object o)
943 {
944 QBLevel bucket = root.find_exact(convert(o));
945 if (bucket == null)
946 return false;
947 return true;
948 }
949 public ArrayList<T> toArrayList()
950 {
951 ArrayList<T> a = new ArrayList<T>();
952 for (T n : this) {
953 a.add(n);
954 }
955 if (debug) {
956 out("returning array list with size: " + a.size());
957 }
958 return a;
959 }
960 public Object[] toArray()
961 {
962 return this.toArrayList().toArray();
963 }
964 public <A> A[] toArray(A[] template)
965 {
966 return this.toArrayList().toArray(template);
967 }
968 class QuadBucketIterator implements Iterator<T>
969 {
970 QBLevel current_node;
971 int content_index;
972 int iterated_over;
973 QBLevel next_content_node(QBLevel q)
974 {
975 if (q == null)
976 return null;
977 QBLevel orig = q;
978 QBLevel next;
979 synchronized (split_lock) {
980 next = q.nextContentNode();
981 }
982 //if (consistency_testing && (orig == next))
983 if (orig == next) {
984 abort("got same leaf back leaf: " + q.isLeaf());
985 }
986 return next;
987 }
988 public QuadBucketIterator(QuadBuckets<T> qb)
989 {
990 if (debug) {
991 out(this + " is a new iterator qb: " + qb + " size: " + qb.size());
992 }
993 if (qb.root.isLeaf() || qb.root.hasContent()) {
994 current_node = qb.root;
995 } else {
996 current_node = next_content_node(qb.root);
997 }
998 if (debug) {
999 out("\titerator first leaf: " + current_node);
1000 }
1001 iterated_over = 0;
1002 }
1003 public boolean hasNext()
1004 {
1005 if (this.peek() == null) {
1006 if (debug) {
1007 out(this + " no hasNext(), but iterated over so far: " + iterated_over);
1008 }
1009 return false;
1010 }
1011 return true;
1012 }
1013 T peek()
1014 {
1015 if (current_node == null) {
1016 if (debug) {
1017 out("null current leaf, nowhere to go");
1018 }
1019 return null;
1020 }
1021 while((current_node.content == null) ||
1022 (content_index >= current_node.content.size())) {
1023 if (debug) {
1024 out("moving to next leaf");
1025 }
1026 content_index = 0;
1027 current_node = next_content_node(current_node);
1028 if (current_node == null) {
1029 break;
1030 }
1031 }
1032 if (current_node == null || current_node.content == null) {
1033 if (debug) {
1034 out("late nowhere to go " + current_node);
1035 }
1036 return null;
1037 }
1038 return current_node.content.get(content_index);
1039 }
1040 public T next()
1041 {
1042 T ret = peek();
1043 content_index++;
1044 if (debug) {
1045 out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node);
1046 }
1047 iterated_over++;
1048 if (ret == null) {
1049 if (debug) {
1050 out(this + " no next node, but iterated over so far: " + iterated_over);
1051 }
1052 }
1053 return ret;
1054 }
1055 public void remove()
1056 {
1057 // two uses
1058 // 1. Back up to the thing we just returned
1059 // 2. move the index back since we removed
1060 // an element
1061 content_index--;
1062 T object = peek(); //TODO Is the call to peek() necessary?
1063 current_node.remove_content(object);
1064 }
1065 }
1066 public Iterator<T> iterator()
1067 {
1068 return new QuadBucketIterator(this);
1069 }
1070 public int size()
1071 {
1072 // This can certainly by optimized
1073 int ret = root.size();
1074 if (debug) {
1075 out(this + " QuadBuckets size: " + ret);
1076 }
1077 return ret;
1078 }
1079 public int size_iter()
1080 {
1081 int count = 0;
1082 Iterator<T> i = this.iterator();
1083 while (i.hasNext()) {
1084 i.next();
1085 count++;
1086 }
1087 return count;
1088 }
1089 public boolean isEmpty()
1090 {
1091 if (this.size() == 0)
1092 return true;
1093 return false;
1094 }
1095 public static BBox search_to_bbox(LatLon point, double radius)
1096 {
1097 BBox bbox = new BBox(point.lon() - radius, point.lat() - radius,
1098 point.lon() + radius, point.lat() + radius);
1099 if (debug) {
1100 out("search bbox before sanity: " + bbox);
1101 }
1102 bbox.sanity();
1103 if (debug) {
1104 out("search bbox after sanity: " + bbox);
1105 }
1106 return bbox;
1107 }
1108 List<T> search(Way w)
1109 {
1110 BBox way_bbox = new BBox(w);
1111 return this.search(way_bbox);
1112 }
1113 public List<T> search(Node n, double radius)
1114 {
1115 return this.search(n.getCoor(), radius);
1116 }
1117 public List<T> search(LatLon point, double radius)
1118 {
1119 if (point == null)
1120 return Collections.emptyList();
1121 return this.search(search_to_bbox(point, radius));
1122 }
1123 public List<T> search(LatLon b1, LatLon b2)
1124 {
1125 BBox bbox = new BBox(b1.lon(), b1.lat(), b2.lon(), b2.lat());
1126 bbox.sanity();
1127 return this.search(bbox);
1128 }
1129 List<T> search(BBox search_bbox)
1130 {
1131 if (debug) {
1132 out("qb root search at " + search_bbox);
1133 out("root bbox: " + root.bbox());
1134 }
1135 List<T> ret;
1136 // Doing this cuts down search cost on a real-life data
1137 // set by about 25%
1138 boolean cache_searches = true;
1139 if (cache_searches) {
1140 if (search_cache == null) {
1141 search_cache = root;
1142 }
1143 // Walk back up the tree when the last
1144 // search spot can not cover the current
1145 // search
1146 while (!search_cache.bbox().bounds(search_bbox)) {
1147 if (debug) {
1148 out("bbox: " + search_bbox);
1149 }
1150 if (debug) {
1151 out("search_cache: " + search_cache + " level: " + search_cache.level);
1152 out("search_cache.bbox(): " + search_cache.bbox());
1153 }
1154 search_cache = search_cache.parent;
1155 if (debug) {
1156 out("new search_cache: " + search_cache);
1157 }
1158 }
1159 } else {
1160 search_cache = root;
1161 }
1162
1163 // Save parent because search_cache might change during search call
1164 QBLevel tmp = search_cache.parent;
1165
1166 ret = search_cache.search(search_bbox);
1167 if (ret == null) {
1168 ret = new ArrayList<T>();
1169 }
1170
1171 // A way that spans this bucket may be stored in one
1172 // of the nodes which is a parent of the search cache
1173 while (tmp != null) {
1174 List<T> content_result = tmp.search_contents(search_bbox);
1175 if (content_result != null) {
1176 ret.addAll(content_result);
1177 }
1178 tmp = tmp.parent;
1179 }
1180 if (debug) {
1181 out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size());
1182 }
1183 return ret;
1184 }
1185
1186 public void printTree() {
1187 printTreeRecursive(root, 0);
1188 }
1189
1190 private void printTreeRecursive(QBLevel level, int indent) {
1191 if (level == null) {
1192 printIndented(indent, "<empty child>");
1193 return;
1194 }
1195 printIndented(indent, level);
1196 if (level.hasContent()) {
1197 for (T o:level.content) {
1198 printIndented(indent, o);
1199 }
1200 }
1201 if (level.children != null) {
1202 for (QBLevel child:level.children) {
1203 printTreeRecursive(child, indent + 2);
1204 }
1205 }
1206 }
1207
1208 private void printIndented(int indent, Object msg) {
1209 for (int i=0; i<indent; i++) {
1210 System.out.print(' ');
1211 }
1212 System.out.println(msg);
1213 }
1214}
Note: See TracBrowser for help on using the repository browser.