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

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

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