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

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

Fix iterator
  • Property svn:eol-style set to native
File size: 24.6 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.Iterator;
8import java.util.List;
9
10import org.openstreetmap.josm.data.coor.LatLon;
11import org.openstreetmap.josm.data.coor.QuadTiling;
12
13/**
14 * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must
15 * be removed and readded.
16 *
17 * This class is (no longer) thread safe.
18 *
19 */
20public class QuadBuckets<T extends OsmPrimitive> implements Collection<T>
21{
22 private static boolean debug = false;
23 private static final boolean consistency_testing = false;
24 private static final int NW_INDEX = 1;
25 private static final int NE_INDEX = 3;
26 private static final int SE_INDEX = 2;
27 private static final int SW_INDEX = 0;
28
29 static void abort(String s)
30 {
31 throw new AssertionError(s);
32 }
33 static void out(String s)
34 {
35 System.out.println(s);
36 }
37 // periodic output
38 long last_out = -1;
39 void pout(String s)
40 {
41 long now = System.currentTimeMillis();
42 if (now - last_out < 300)
43 return;
44 last_out = now;
45 System.out.print(s + "\r");
46 }
47 void pout(String s, int i, int total)
48 {
49 long now = System.currentTimeMillis();
50 if ((now - last_out < 300) &&
51 ((i+1) < total))
52 return;
53 last_out = now;
54 // cast to float to keep the output size down
55 System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done \r");
56 }
57
58 public static int MAX_OBJECTS_PER_LEVEL = 16;
59 class QBLevel
60 {
61 final int level;
62 private final BBox bbox;
63 final long quad;
64 final QBLevel parent;
65 private boolean isLeaf = true;
66
67 public List<T> content;
68 public QBLevel nw, ne, sw, se;
69
70 private QBLevel getChild(int index) {
71 switch (index) {
72 case NE_INDEX:
73 if (ne == null) {
74 ne = new QBLevel(this, index);
75 }
76 return ne;
77 case NW_INDEX:
78 if (nw == null) {
79 nw = new QBLevel(this, index);
80 }
81 return nw;
82 case SE_INDEX:
83 if (se == null) {
84 se = new QBLevel(this, index);
85 }
86 return se;
87 case SW_INDEX:
88 if (sw == null) {
89 sw = new QBLevel(this, index);
90 }
91 return sw;
92 default:
93 return null;
94 }
95 }
96
97 private QBLevel[] getChildren() {
98 // This is ugly and hackish. But, it seems to work,
99 // and using an ArrayList here seems to cost us
100 // a significant performance penalty -- 50% in my
101 // testing. Child access is one of the single
102 // hottest code paths in this entire class.
103 QBLevel[] result = (QBLevel[]) Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL);
104 result[NW_INDEX] = nw;
105 result[NE_INDEX] = ne;
106 result[SW_INDEX] = sw;
107 result[SE_INDEX] = se;
108 return result;
109 }
110
111 @Override
112 public String toString() {
113 return super.toString()+ "["+level+"]: " + bbox();
114 }
115 /**
116 * Constructor for root node
117 */
118 public QBLevel() {
119 level = 0;
120 quad = 0;
121 parent = null;
122 bbox = new BBox(-180, 90, 180, -90);
123 }
124
125 public QBLevel(QBLevel parent, int parent_index) {
126 this.parent = parent;
127 this.level = parent.level + 1;
128 int shift = (QuadTiling.NR_LEVELS - level) * 2;
129 long mult = 1;
130 // Java blows the big one. It seems to wrap when
131 // you shift by > 31
132 if (shift >= 30) {
133 shift -= 30;
134 mult = 1<<30;
135 }
136 long this_quadpart = mult * (parent_index << shift);
137 this.quad = parent.quad | this_quadpart;
138 this.bbox = calculateBBox(); // calculateBBox reference quad
139 if (debug) {
140 out("new level["+this.level+"] bbox["+parent_index+"]: " + this.bbox()
141 + " coor: " + this.coor()
142 + " quadpart: " + Long.toHexString(this_quadpart)
143 + " quad: " + Long.toHexString(this.quad));
144 }
145 }
146
147 private BBox calculateBBox() {
148 LatLon bottom_left = this.coor();
149 double lat = bottom_left.lat() + parent.height() / 2;
150 double lon = bottom_left.lon() + parent.width() / 2;
151 LatLon top_right = new LatLon(lat, lon);
152 return new BBox(bottom_left, top_right);
153 }
154
155 QBLevel findBucket(BBox bbox) {
156 if (!hasChildren())
157 return this;
158 else {
159 int index = get_index(bbox, level);
160 if (index == -1)
161 return this;
162 return getChild(index).findBucket(bbox);
163 }
164 }
165
166 boolean remove_content(T o)
167 {
168 // If two threads try to remove item at the same time from different buckets of this QBLevel,
169 // it might happen that one thread removes bucket but don't remove parent because it still sees
170 // another bucket set. Second thread do the same. Due to thread memory caching, it's possible that
171 // changes made by threads will show up in children array too late, leading to QBLevel with all children
172 // set to null
173 if (content == null)
174 return false;
175 boolean ret = this.content.remove(o);
176 if (this.content.size() == 0) {
177 this.content = null;
178 }
179 if (this.canRemove()) {
180 this.remove_from_parent();
181 }
182 return ret;
183 }
184 // Get the correct index for the given primitive
185 // at the given level. If the primitive can not
186 // fit into a single quad at this level, return -1
187 int get_index(BBox bbox, int level) {
188 int index = -1;
189 for (LatLon c : bbox.points()) {
190 if (debug) {
191 out("getting index for point: " + c);
192 }
193 if (index == -1) {
194 index = QuadTiling.index(c, level);
195 if (debug) {
196 out("set initial index to: " + index);
197 }
198 continue;
199 }
200 int another_index = QuadTiling.index(c, level);
201 if (debug) {
202 out("other point index: " + another_index);
203 }
204 if (another_index != index)
205 return -1;
206 }
207 return index;
208 }
209 /*
210 * There is a race between this and qb.nextContentNode().
211 * If nextContentNode() runs into this bucket, it may
212 * attempt to null out 'children' because it thinks this
213 * is a dead end.
214 */
215 void __split() {
216 if (debug) {
217 out("splitting "+this.bbox()+" level "+level+" with "
218 + content.size() + " entries (my dimensions: "
219 + this.bbox().width()+", "+this.bbox().height()+")");
220 }
221 List<T> tmpcontent = content;
222 content = null;
223
224 for (T o: tmpcontent) {
225 int index = get_index(o.getBBox(), level);
226 if (index == -1) {
227 __add_content(o);
228 } else {
229 getChild(index).doAdd(o);
230 }
231 }
232 isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1)
233 }
234
235 boolean __add_content(T o)
236 {
237 boolean ret = false;
238 // The split_lock will keep two concurrent
239 // calls from overwriting content
240 if (content == null) {
241 content = new ArrayList<T>();
242 }
243 ret = content.add(o);
244 if (debug && !this.isLeaf()) {
245 pout("added "+o.getClass().getName()+" to non-leaf with size: " + content.size());
246 }
247 return ret;
248 }
249 boolean matches(T o, BBox search_bbox)
250 {
251 // This can be optimized when o is a node
252 //return search_bbox.bounds(coor));
253 return o.getBBox().intersects(search_bbox);
254 }
255 private void search_contents(BBox search_bbox, List<T> result)
256 {
257 if (debug) {
258 out("searching contents (size: " + content == null?"<null>":content.size() + ") for " + search_bbox);
259 }
260 /*
261 * It is possible that this was created in a split
262 * but never got any content populated.
263 */
264 if (content == null)
265 return;
266
267 for (T o : content) {
268 if (matches(o, search_bbox)) {
269 result.add(o);
270 }
271 }
272 if (debug) {
273 out("done searching quad " + Long.toHexString(this.quad));
274 }
275 }
276 /*
277 * This is stupid. I tried to have a QBLeaf and QBBranch
278 * class decending from a QBLevel. It's more than twice
279 * as slow. So, this throws OO out the window, but it
280 * is fast. Runtime type determination must be slow.
281 */
282 boolean isLeaf() {
283 return isLeaf;
284 }
285 boolean hasChildren() {
286 return nw != null || ne != null || sw != null || se != null;
287 }
288
289 QBLevel next_sibling()
290 {
291 boolean found_me = false;
292 if (parent == null)
293 return null;
294 int __nr = 0;
295 for (QBLevel sibling : parent.getChildren()) {
296 __nr++;
297 int nr = __nr-1;
298 if (sibling == null) {
299 if (debug) {
300 out("[" + this.level + "] null child nr: " + nr);
301 }
302 continue;
303 }
304 // We're looking for the *next* child
305 // after us.
306 if (sibling == this) {
307 if (debug) {
308 out("[" + this.level + "] I was child nr: " + nr);
309 }
310 found_me = true;
311 continue;
312 }
313 if (found_me) {
314 if (debug) {
315 out("[" + this.level + "] next sibling was child nr: " + nr);
316 }
317 return sibling;
318 }
319 if (debug) {
320 out("[" + this.level + "] nr: " + nr + " is before me, ignoring...");
321 }
322 }
323 return null;
324 }
325 boolean hasContent()
326 {
327 return content != null;
328 }
329 QBLevel nextSibling()
330 {
331 QBLevel next = this;
332 QBLevel sibling = next.next_sibling();
333 // Walk back up the tree to find the
334 // next sibling node. It may be either
335 // a leaf or branch.
336 while (sibling == null) {
337 if (debug) {
338 out("no siblings at level["+next.level+"], moving to parent");
339 }
340 next = next.parent;
341 if (next == null) {
342 break;
343 }
344 sibling = next.next_sibling();
345 }
346 next = sibling;
347 return next;
348 }
349 QBLevel firstChild()
350 {
351 QBLevel ret = null;
352 for (QBLevel child : getChildren()) {
353 if (child == null) {
354 continue;
355 }
356 ret = child;
357 break;
358 }
359 return ret;
360 }
361 QBLevel nextNode()
362 {
363 if (!this.hasChildren())
364 return this.nextSibling();
365 return this.firstChild();
366 }
367 QBLevel nextContentNode()
368 {
369 QBLevel next = this.nextNode();
370 if (next == null)
371 return next;
372 if (next.hasContent())
373 return next;
374 return next.nextContentNode();
375 }
376
377 void doAdd(T o) {
378 if (consistency_testing) {
379 if (!matches(o, this.bbox())) {
380 out("-----------------------------");
381 debug = true;
382 get_index(o.getBBox(), level);
383 get_index(o.getBBox(), level-1);
384 int nr = 0;
385 for (QBLevel sibling : parent.getChildren()) {
386 out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling));
387 }
388 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
389 }
390 }
391 __add_content(o);
392 if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) {
393 __split();
394 }
395 }
396
397 void add(T o) {
398 findBucket(o.getBBox()).doAdd(o);
399 }
400
401 private void search(BBox search_bbox, List<T> result)
402 {
403 if (debug) {
404 System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
405 }
406 if (!this.bbox().intersects(search_bbox)) {
407 if (debug) {
408 out("miss " + Long.toHexString(this.quad));
409 //QuadTiling.tile2xy(this.quad);
410 }
411 return;
412 } else if (bbox().bounds(search_bbox)) {
413 search_cache = this;
414 }
415
416 if (this.hasContent()) {
417 search_contents(search_bbox, result);
418 }
419
420 if (debug) {
421 out("hit " + this.quads());
422 }
423
424 if (debug) {
425 out("[" + level + "] not leaf, moving down");
426 }
427
428 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
429
430 if (nw != null) {
431 nw.search(search_bbox, result);
432 }
433 if (ne != null) {
434 ne.search(search_bbox, result);
435 }
436 if (se != null) {
437 se.search(search_bbox, result);
438 }
439 if (sw != null) {
440 sw.search(search_bbox, result);
441 }
442 }
443 public String quads()
444 {
445 return Long.toHexString(quad);
446 }
447 int index_of(QBLevel find_this)
448 {
449 QBLevel[] children = getChildren();
450 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
451 if (children[i] == find_this)
452 return i;
453 }
454 return -1;
455 }
456 double width() {
457 return bbox.width();
458 }
459
460 double height() {
461 return bbox.height();
462 }
463
464 public BBox bbox() {
465 return bbox;
466 }
467 /*
468 * This gives the coordinate of the bottom-left
469 * corner of the box
470 */
471 LatLon coor()
472 {
473 return QuadTiling.tile2LatLon(this.quad);
474 }
475 void remove_from_parent()
476 {
477 if (parent == null)
478 return;
479
480 if (!canRemove()) {
481 abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren()));
482 }
483
484 if (parent.nw == this) {
485 parent.nw = null;
486 } else if (parent.ne == this) {
487 parent.ne = null;
488 } else if (parent.sw == this) {
489 parent.sw = null;
490 } else if (parent.se == this) {
491 parent.se = null;
492 }
493
494 if (parent.canRemove()) {
495 parent.remove_from_parent();
496 }
497 }
498 boolean canRemove()
499 {
500 if (content != null && content.size() > 0)
501 return false;
502 if (this.hasChildren())
503 return false;
504 return true;
505 }
506 }
507
508 private QBLevel root;
509 private QBLevel search_cache;
510 private int size;
511
512 public QuadBuckets()
513 {
514 clear();
515 }
516 public void clear() {
517 root = new QBLevel();
518 search_cache = null;
519 size = 0;
520 if (debug) {
521 out("QuadBuckets() cleared: " + this);
522 out("root: " + root + " level: " + root.level + " bbox: " + root.bbox());
523 }
524 }
525 public boolean add(T n) {
526 root.add(n);
527 size++;
528 return true;
529 }
530
531 public void unsupported()
532 {
533 out("unsupported operation");
534 throw new UnsupportedOperationException();
535 }
536 public boolean retainAll(Collection<?> objects)
537 {
538 for (T o : this) {
539 if (objects.contains(o)) {
540 continue;
541 }
542 if (!this.remove(o))
543 return false;
544 }
545 return true;
546 }
547 public boolean removeAll(Collection<?> objects)
548 {
549 boolean changed = false;
550 for (Object o : objects) {
551 changed = changed | remove(o);
552 }
553 return changed;
554 }
555 public boolean addAll(Collection<? extends T> objects)
556 {
557 boolean changed = false;
558 for (T o : objects) {
559 changed = changed | this.add(o);
560 }
561 return changed;
562 }
563 public boolean containsAll(Collection<?> objects)
564 {
565 for (Object o : objects) {
566 if (!this.contains(o))
567 return false;
568 }
569 return true;
570 }
571 public boolean remove(Object o) {
572 @SuppressWarnings("unchecked") T t = (T) o;
573 search_cache = null; // Search cache might point to one of removed buckets
574 QBLevel bucket = root.findBucket(t.getBBox());
575 if (bucket.remove_content(t)) {
576 size--;
577 return true;
578 } else
579 return false;
580 }
581 public boolean contains(Object o) {
582 @SuppressWarnings("unchecked") T t = (T) o;
583 QBLevel bucket = root.findBucket(t.getBBox());
584 return bucket != null && bucket.content != null && bucket.content.contains(t);
585 }
586
587 public ArrayList<T> toArrayList()
588 {
589 ArrayList<T> a = new ArrayList<T>();
590 for (T n : this) {
591 a.add(n);
592 }
593 if (debug) {
594 out("returning array list with size: " + a.size());
595 }
596 return a;
597 }
598 public Object[] toArray()
599 {
600 return this.toArrayList().toArray();
601 }
602 public <A> A[] toArray(A[] template)
603 {
604 return this.toArrayList().toArray(template);
605 }
606 class QuadBucketIterator implements Iterator<T>
607 {
608 QBLevel current_node;
609 int content_index;
610 int iterated_over;
611 QBLevel next_content_node(QBLevel q)
612 {
613 if (q == null)
614 return null;
615 QBLevel orig = q;
616 QBLevel next;
617 next = q.nextContentNode();
618 //if (consistency_testing && (orig == next))
619 if (orig == next) {
620 abort("got same leaf back leaf: " + q.isLeaf());
621 }
622 return next;
623 }
624 public QuadBucketIterator(QuadBuckets<T> qb)
625 {
626 if (debug) {
627 out(this + " is a new iterator qb: " + qb + " size: " + qb.size());
628 }
629 if (!qb.root.hasChildren() || qb.root.hasContent()) {
630 current_node = qb.root;
631 } else {
632 current_node = next_content_node(qb.root);
633 }
634 if (debug) {
635 out("\titerator first leaf: " + current_node);
636 }
637 iterated_over = 0;
638 }
639 public boolean hasNext()
640 {
641 if (this.peek() == null) {
642 if (debug) {
643 out(this + " no hasNext(), but iterated over so far: " + iterated_over);
644 }
645 return false;
646 }
647 return true;
648 }
649 T peek()
650 {
651 if (current_node == null) {
652 if (debug) {
653 out("null current leaf, nowhere to go");
654 }
655 return null;
656 }
657 while((current_node.content == null) ||
658 (content_index >= current_node.content.size())) {
659 if (debug) {
660 out("moving to next leaf");
661 }
662 content_index = 0;
663 current_node = next_content_node(current_node);
664 if (current_node == null) {
665 break;
666 }
667 }
668 if (current_node == null || current_node.content == null) {
669 if (debug) {
670 out("late nowhere to go " + current_node);
671 }
672 return null;
673 }
674 return current_node.content.get(content_index);
675 }
676 public T next()
677 {
678 T ret = peek();
679 content_index++;
680 if (debug) {
681 out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node);
682 }
683 iterated_over++;
684 if (ret == null) {
685 if (debug) {
686 out(this + " no next node, but iterated over so far: " + iterated_over);
687 }
688 }
689 return ret;
690 }
691 public void remove()
692 {
693 // two uses
694 // 1. Back up to the thing we just returned
695 // 2. move the index back since we removed
696 // an element
697 content_index--;
698 T object = peek();
699 current_node.remove_content(object);
700 }
701 }
702 public Iterator<T> iterator()
703 {
704 return new QuadBucketIterator(this);
705 }
706 public int size() {
707 return size;
708 }
709
710 public boolean isEmpty()
711 {
712 if (this.size() == 0)
713 return true;
714 return false;
715 }
716 public List<T> search(BBox search_bbox) {
717 if (debug) {
718 out("qb root search at " + search_bbox);
719 out("root bbox: " + root.bbox());
720 }
721 List<T> ret = new ArrayList<T>();
722 // Doing this cuts down search cost on a real-life data
723 // set by about 25%
724 boolean cache_searches = true;
725 if (cache_searches) {
726 if (search_cache == null) {
727 search_cache = root;
728 }
729 // Walk back up the tree when the last
730 // search spot can not cover the current
731 // search
732 while (!search_cache.bbox().bounds(search_bbox)) {
733 if (debug) {
734 out("bbox: " + search_bbox);
735 }
736 if (debug) {
737 out("search_cache: " + search_cache + " level: " + search_cache.level);
738 out("search_cache.bbox(): " + search_cache.bbox());
739 }
740 search_cache = search_cache.parent;
741 if (debug) {
742 out("new search_cache: " + search_cache);
743 }
744 }
745 } else {
746 search_cache = root;
747 }
748
749 // Save parent because search_cache might change during search call
750 QBLevel tmp = search_cache.parent;
751
752 search_cache.search(search_bbox, ret);
753
754 // A way that spans this bucket may be stored in one
755 // of the nodes which is a parent of the search cache
756 while (tmp != null) {
757 tmp.search_contents(search_bbox, ret);
758 tmp = tmp.parent;
759 }
760 if (debug) {
761 out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size());
762 }
763 return ret;
764 }
765
766 public void printTree() {
767 printTreeRecursive(root, 0);
768 }
769
770 private void printTreeRecursive(QBLevel level, int indent) {
771 if (level == null) {
772 printIndented(indent, "<empty child>");
773 return;
774 }
775 printIndented(indent, level);
776 if (level.hasContent()) {
777 for (T o:level.content) {
778 printIndented(indent, o);
779 }
780 }
781 for (QBLevel child:level.getChildren()) {
782 printTreeRecursive(child, indent + 2);
783 }
784 }
785
786 private void printIndented(int indent, Object msg) {
787 for (int i=0; i<indent; i++) {
788 System.out.print(' ');
789 }
790 System.out.println(msg);
791 }
792}
Note: See TracBrowser for help on using the repository browser.