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

Last change on this file since 3779 was 3719, checked in by bastiK, 13 years ago

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