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

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

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