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

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

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