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

Last change on this file since 5339 was 4869, checked in by jttt, 12 years ago

Use final were appropriate
  • Property svn:eol-style set to native
File size: 24.5 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 final 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 return null;
321 }
322 boolean hasContent()
323 {
324 return content != null;
325 }
326 QBLevel nextSibling()
327 {
328 QBLevel next = this;
329 QBLevel sibling = next.next_sibling();
330 // Walk back up the tree to find the
331 // next sibling node. It may be either
332 // a leaf or branch.
333 while (sibling == null) {
334 /*if (debug) {
335 out("no siblings at level["+next.level+"], moving to parent");
336 }*/
337 next = next.parent;
338 if (next == null) {
339 break;
340 }
341 sibling = next.next_sibling();
342 }
343 next = sibling;
344 return next;
345 }
346 QBLevel firstChild()
347 {
348 QBLevel ret = null;
349 for (QBLevel child : getChildren()) {
350 if (child == null) {
351 continue;
352 }
353 ret = child;
354 break;
355 }
356 return ret;
357 }
358 QBLevel nextNode()
359 {
360 if (!this.hasChildren())
361 return this.nextSibling();
362 return this.firstChild();
363 }
364 QBLevel nextContentNode()
365 {
366 QBLevel next = this.nextNode();
367 if (next == null)
368 return next;
369 if (next.hasContent())
370 return next;
371 return next.nextContentNode();
372 }
373
374 void doAdd(T o) {
375 if (consistency_testing) {
376 if (!matches(o, this.bbox())) {
377 /*out("-----------------------------");
378 debug = true;*/
379 get_index(o.getBBox(), level);
380 get_index(o.getBBox(), level-1);
381 int nr = 0;
382 /*for (QBLevel sibling : parent.getChildren()) {
383 out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling));
384 }*/
385 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
386 }
387 }
388 __add_content(o);
389 if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) {
390 __split();
391 }
392 }
393
394 void add(T o) {
395 findBucket(o.getBBox()).doAdd(o);
396 }
397
398 private void search(BBox search_bbox, List<T> result)
399 {
400 /*if (debug) {
401 System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
402 }*/
403 if (!this.bbox().intersects(search_bbox))
404 /*if (debug) {
405 out("miss " + Long.toHexString(this.quad));
406 //QuadTiling.tile2xy(this.quad);
407 }*/
408 return;
409 else if (bbox().bounds(search_bbox)) {
410 search_cache = this;
411 }
412
413 if (this.hasContent()) {
414 search_contents(search_bbox, result);
415 }
416
417 /*if (debug) {
418 out("hit " + this.quads());
419 out("[" + level + "] not leaf, moving down");
420 }*/
421
422 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
423
424 if (nw != null) {
425 nw.search(search_bbox, result);
426 }
427 if (ne != null) {
428 ne.search(search_bbox, result);
429 }
430 if (se != null) {
431 se.search(search_bbox, result);
432 }
433 if (sw != null) {
434 sw.search(search_bbox, result);
435 }
436 }
437 public String quads()
438 {
439 return Long.toHexString(quad);
440 }
441 int index_of(QBLevel find_this)
442 {
443 QBLevel[] children = getChildren();
444 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
445 if (children[i] == find_this)
446 return i;
447 }
448 return -1;
449 }
450 double width() {
451 return bbox.width();
452 }
453
454 double height() {
455 return bbox.height();
456 }
457
458 public BBox bbox() {
459 return bbox;
460 }
461 /*
462 * This gives the coordinate of the bottom-left
463 * corner of the box
464 */
465 LatLon coor()
466 {
467 return QuadTiling.tile2LatLon(this.quad);
468 }
469 void remove_from_parent()
470 {
471 if (parent == null)
472 return;
473
474 if (!canRemove()) {
475 abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren()));
476 }
477
478 if (parent.nw == this) {
479 parent.nw = null;
480 } else if (parent.ne == this) {
481 parent.ne = null;
482 } else if (parent.sw == this) {
483 parent.sw = null;
484 } else if (parent.se == this) {
485 parent.se = null;
486 }
487
488 if (parent.canRemove()) {
489 parent.remove_from_parent();
490 }
491 }
492 boolean canRemove()
493 {
494 if (content != null && content.size() > 0)
495 return false;
496 if (this.hasChildren())
497 return false;
498 return true;
499 }
500 }
501
502 private QBLevel root;
503 private QBLevel search_cache;
504 private int size;
505
506 public QuadBuckets()
507 {
508 clear();
509 }
510 public void clear() {
511 root = new QBLevel();
512 search_cache = null;
513 size = 0;
514 /*if (debug) {
515 out("QuadBuckets() cleared: " + this);
516 out("root: " + root + " level: " + root.level + " bbox: " + root.bbox());
517 }*/
518 }
519 public boolean add(T n) {
520 root.add(n);
521 size++;
522 return true;
523 }
524
525 public boolean retainAll(Collection<?> objects)
526 {
527 for (T o : this) {
528 if (objects.contains(o)) {
529 continue;
530 }
531 if (!this.remove(o))
532 return false;
533 }
534 return true;
535 }
536 public boolean removeAll(Collection<?> objects)
537 {
538 boolean changed = false;
539 for (Object o : objects) {
540 changed = changed | remove(o);
541 }
542 return changed;
543 }
544 public boolean addAll(Collection<? extends T> objects)
545 {
546 boolean changed = false;
547 for (T o : objects) {
548 changed = changed | this.add(o);
549 }
550 return changed;
551 }
552 public boolean containsAll(Collection<?> objects)
553 {
554 for (Object o : objects) {
555 if (!this.contains(o))
556 return false;
557 }
558 return true;
559 }
560 public boolean remove(Object o) {
561 @SuppressWarnings("unchecked") T t = (T) o;
562 search_cache = null; // Search cache might point to one of removed buckets
563 QBLevel bucket = root.findBucket(t.getBBox());
564 if (bucket.remove_content(t)) {
565 size--;
566 return true;
567 } else
568 return false;
569 }
570 public boolean contains(Object o) {
571 @SuppressWarnings("unchecked") T t = (T) o;
572 QBLevel bucket = root.findBucket(t.getBBox());
573 return bucket != null && bucket.content != null && bucket.content.contains(t);
574 }
575
576 public ArrayList<T> toArrayList()
577 {
578 ArrayList<T> a = new ArrayList<T>();
579 for (T n : this) {
580 a.add(n);
581 }
582 /*if (debug) {
583 out("returning array list with size: " + a.size());
584 }*/
585 return a;
586 }
587 public Object[] toArray()
588 {
589 return this.toArrayList().toArray();
590 }
591 public <A> A[] toArray(A[] template)
592 {
593 return this.toArrayList().toArray(template);
594 }
595 class QuadBucketIterator implements Iterator<T>
596 {
597 QBLevel current_node;
598 int content_index;
599 int iterated_over;
600 QBLevel next_content_node(QBLevel q)
601 {
602 if (q == null)
603 return null;
604 QBLevel orig = q;
605 QBLevel next;
606 next = q.nextContentNode();
607 //if (consistency_testing && (orig == next))
608 if (orig == next) {
609 abort("got same leaf back leaf: " + q.isLeaf());
610 }
611 return next;
612 }
613 public QuadBucketIterator(QuadBuckets<T> qb)
614 {
615 /*if (debug) {
616 out(this + " is a new iterator qb: " + qb + " size: " + qb.size());
617 }*/
618 if (!qb.root.hasChildren() || qb.root.hasContent()) {
619 current_node = qb.root;
620 } else {
621 current_node = next_content_node(qb.root);
622 }
623 /*if (debug) {
624 out("\titerator first leaf: " + current_node);
625 }*/
626 iterated_over = 0;
627 }
628 public boolean hasNext()
629 {
630 if (this.peek() == null)
631 /*if (debug) {
632 out(this + " no hasNext(), but iterated over so far: " + iterated_over);
633 }*/
634 return false;
635 return true;
636 }
637 T peek()
638 {
639 if (current_node == null)
640 /*if (debug) {
641 out("null current leaf, nowhere to go");
642 }*/
643 return null;
644 while((current_node.content == null) ||
645 (content_index >= current_node.content.size())) {
646 /*if (debug) {
647 out("moving to next leaf");
648 }*/
649 content_index = 0;
650 current_node = next_content_node(current_node);
651 if (current_node == null) {
652 break;
653 }
654 }
655 if (current_node == null || current_node.content == null)
656 /*if (debug) {
657 out("late nowhere to go " + current_node);
658 }*/
659 return null;
660 return current_node.content.get(content_index);
661 }
662 public T next()
663 {
664 T ret = peek();
665 content_index++;
666 /*if (debug) {
667 out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node);
668 }*/
669 iterated_over++;
670 if (ret == null) {
671 /*if (debug) {
672 out(this + " no next node, but iterated over so far: " + iterated_over);
673 }*/
674 }
675 return ret;
676 }
677 public void remove()
678 {
679 // two uses
680 // 1. Back up to the thing we just returned
681 // 2. move the index back since we removed
682 // an element
683 content_index--;
684 T object = peek();
685 current_node.remove_content(object);
686 }
687 }
688 public Iterator<T> iterator()
689 {
690 return new QuadBucketIterator(this);
691 }
692 public int size() {
693 return size;
694 }
695
696 public boolean isEmpty()
697 {
698 if (this.size() == 0)
699 return true;
700 return false;
701 }
702 public List<T> search(BBox search_bbox) {
703 /*if (debug) {
704 out("qb root search at " + search_bbox);
705 out("root bbox: " + root.bbox());
706 }*/
707 List<T> ret = new ArrayList<T>();
708 // Doing this cuts down search cost on a real-life data
709 // set by about 25%
710 boolean cache_searches = true;
711 if (cache_searches) {
712 if (search_cache == null) {
713 search_cache = root;
714 }
715 // Walk back up the tree when the last
716 // search spot can not cover the current
717 // search
718 while (search_cache != null && !search_cache.bbox().bounds(search_bbox)) {
719 /*if (debug) {
720 out("bbox: " + search_bbox);
721 out("search_cache: " + search_cache + " level: " + search_cache.level);
722 out("search_cache.bbox(): " + search_cache.bbox());
723 }*/
724 search_cache = search_cache.parent;
725 /*if (debug) {
726 out("new search_cache: " + search_cache);
727 }*/
728 }
729
730 if (search_cache == null) {
731 search_cache = root;
732 out("bbox: " + search_bbox + " is out of the world");
733 }
734 } else {
735 search_cache = root;
736 }
737
738 // Save parent because search_cache might change during search call
739 QBLevel tmp = search_cache.parent;
740
741 search_cache.search(search_bbox, ret);
742
743 // A way that spans this bucket may be stored in one
744 // of the nodes which is a parent of the search cache
745 while (tmp != null) {
746 tmp.search_contents(search_bbox, ret);
747 tmp = tmp.parent;
748 }
749 /*if (debug) {
750 out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size());
751 }*/
752 return ret;
753 }
754
755 public void printTree() {
756 printTreeRecursive(root, 0);
757 }
758
759 private void printTreeRecursive(QBLevel level, int indent) {
760 if (level == null) {
761 printIndented(indent, "<empty child>");
762 return;
763 }
764 printIndented(indent, level);
765 if (level.hasContent()) {
766 for (T o:level.content) {
767 printIndented(indent, o);
768 }
769 }
770 for (QBLevel child:level.getChildren()) {
771 printTreeRecursive(child, indent + 2);
772 }
773 }
774
775 private void printIndented(int indent, Object msg) {
776 for (int i=0; i<indent; i++) {
777 System.out.print(' ');
778 }
779 System.out.println(msg);
780 }
781}
Note: See TracBrowser for help on using the repository browser.