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

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

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