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

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

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