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

Last change on this file since 6231 was 6203, checked in by Don-vip, 11 years ago

fix #9024 - bbox/bounds memory optimizations (modified patch by shinigami) + javadoc
  • Property svn:eol-style set to native
File size: 18.7 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.osm;
3
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.Main;
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 private static final boolean consistency_testing = false;
23 private static final int NW_INDEX = 1;
24 private static final int NE_INDEX = 3;
25 private static final int SE_INDEX = 2;
26 private static final int SW_INDEX = 0;
27
28 static void abort(String s) {
29 throw new AssertionError(s);
30 }
31
32 public static final int MAX_OBJECTS_PER_LEVEL = 16;
33
34 static class QBLevel<T extends OsmPrimitive> {
35 private final int level;
36 private final int index;
37 private final BBox bbox;
38 private final long quad;
39 private final QBLevel<T> parent;
40 private boolean isLeaf = true;
41
42 private List<T> content;
43 // child order by index is sw, nw, se, ne
44 private QBLevel<T> nw, ne, sw, se;
45
46 private final QuadBuckets<T> buckets;
47
48 private QBLevel<T> getChild(int index) {
49 switch (index) {
50 case NE_INDEX:
51 if (ne == null) {
52 ne = new QBLevel<T>(this, index, buckets);
53 }
54 return ne;
55 case NW_INDEX:
56 if (nw == null) {
57 nw = new QBLevel<T>(this, index, buckets);
58 }
59 return nw;
60 case SE_INDEX:
61 if (se == null) {
62 se = new QBLevel<T>(this, index, buckets);
63 }
64 return se;
65 case SW_INDEX:
66 if (sw == null) {
67 sw = new QBLevel<T>(this, index, buckets);
68 }
69 return sw;
70 default:
71 return null;
72 }
73 }
74
75 @SuppressWarnings("unchecked")
76 private QBLevel<T>[] getChildren() {
77 return new QBLevel[] {sw, nw, se, ne};
78 }
79
80 @Override
81 public String toString() {
82 return super.toString() + "[" + level + "]: " + bbox();
83 }
84
85 /**
86 * Constructor for root node
87 */
88 public QBLevel(final QuadBuckets<T> buckets) {
89 level = 0;
90 index = 0;
91 quad = 0;
92 parent = null;
93 bbox = new BBox(-180, 90, 180, -90);
94 this.buckets = buckets;
95 }
96
97 public QBLevel(QBLevel<T> parent, int parent_index, final QuadBuckets<T> buckets) {
98 this.parent = parent;
99 this.level = parent.level + 1;
100 this.index = parent_index;
101 this.buckets = buckets;
102
103 int shift = (QuadTiling.NR_LEVELS - level) * 2;
104 long mult = 1;
105 // Java blows the big one. It seems to wrap when you shift by > 31
106 if (shift >= 30) {
107 shift -= 30;
108 mult = 1 << 30;
109 }
110 long this_quadpart = mult * (parent_index << shift);
111 this.quad = parent.quad | this_quadpart;
112 this.bbox = calculateBBox(); // calculateBBox reference quad
113 }
114
115 private BBox calculateBBox() {
116 LatLon bottom_left = this.coor();
117 double lat = bottom_left.lat() + parent.height() / 2;
118 double lon = bottom_left.lon() + parent.width() / 2;
119 return new BBox(bottom_left.lon(), bottom_left.lat(), lon, lat);
120 }
121
122 QBLevel<T> findBucket(BBox bbox) {
123 if (!hasChildren())
124 return this;
125 else {
126 int index = bbox.getIndex(level);
127 if (index == -1)
128 return this;
129 return getChild(index).findBucket(bbox);
130 }
131 }
132
133 boolean remove_content(T o) {
134 // If two threads try to remove item at the same time from different buckets of this QBLevel,
135 // it might happen that one thread removes bucket but don't remove parent because it still sees
136 // another bucket set. Second thread do the same. Due to thread memory caching, it's possible that
137 // changes made by threads will show up in children array too late, leading to QBLevel with all children
138 // set to null
139 if (content == null)
140 return false;
141 boolean ret = this.content.remove(o);
142 if (this.content.isEmpty()) {
143 this.content = null;
144 }
145 if (this.canRemove()) {
146 this.remove_from_parent();
147 }
148 return ret;
149 }
150
151 /*
152 * There is a race between this and qb.nextContentNode().
153 * If nextContentNode() runs into this bucket, it may
154 * attempt to null out 'children' because it thinks this
155 * is a dead end.
156 */
157 void __split() {
158 List<T> tmpcontent = content;
159 content = null;
160
161 for (T o : tmpcontent) {
162 int index = o.getBBox().getIndex(level);
163 if (index == -1) {
164 __add_content(o);
165 } else {
166 getChild(index).doAdd(o);
167 }
168 }
169 isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1)
170 }
171
172 boolean __add_content(T o) {
173 boolean ret = false;
174 // The split_lock will keep two concurrent calls from overwriting content
175 if (content == null) {
176 content = new ArrayList<T>();
177 }
178 ret = content.add(o);
179 return ret;
180 }
181
182 boolean matches(final T o, final BBox search_bbox) {
183 if (o instanceof Node){
184 final LatLon latLon = ((Node)o).getCoor();
185 // node without coords -> bbox[0,0,0,0]
186 return search_bbox.bounds(latLon != null ? latLon : LatLon.ZERO);
187 }
188 return o.getBBox().intersects(search_bbox);
189 }
190
191 private void search_contents(BBox search_bbox, List<T> result) {
192 /*
193 * It is possible that this was created in a split
194 * but never got any content populated.
195 */
196 if (content == null)
197 return;
198
199 for (T o : content) {
200 if (matches(o, search_bbox)) {
201 result.add(o);
202 }
203 }
204 }
205
206 /*
207 * This is stupid. I tried to have a QBLeaf and QBBranch
208 * class descending from a QBLevel. It's more than twice
209 * as slow. So, this throws OO out the window, but it
210 * is fast. Runtime type determination must be slow.
211 */
212 boolean isLeaf() {
213 return isLeaf;
214 }
215
216 boolean hasChildren() {
217 return nw != null || ne != null || sw != null || se != null;
218 }
219
220 QBLevel<T> next_sibling() {
221 return (parent == null) ? null : parent.firstSiblingOf(this);
222 }
223
224 boolean hasContent() {
225 return content != null;
226 }
227
228 QBLevel<T> nextSibling() {
229 QBLevel<T> next = this;
230 QBLevel<T> sibling = next.next_sibling();
231 // Walk back up the tree to find the
232 // next sibling node. It may be either
233 // a leaf or branch.
234 while (sibling == null) {
235 next = next.parent;
236 if (next == null) {
237 break;
238 }
239 sibling = next.next_sibling();
240 }
241 next = sibling;
242 return next;
243 }
244
245 QBLevel<T> firstChild() {
246 if (sw != null)
247 return sw;
248 if (nw != null)
249 return nw;
250 if (se != null)
251 return se;
252 return ne;
253 }
254
255 QBLevel<T> firstSiblingOf(final QBLevel<T> child) {
256 switch (child.index) {
257 case SW_INDEX:
258 if (nw != null)
259 return nw;
260 case NW_INDEX:
261 if (se != null)
262 return se;
263 case SE_INDEX:
264 return ne;
265 }
266 return null;
267 }
268
269 QBLevel<T> nextNode() {
270 if (!this.hasChildren())
271 return this.nextSibling();
272 return this.firstChild();
273 }
274
275 QBLevel<T> nextContentNode() {
276 QBLevel<T> next = this.nextNode();
277 if (next == null)
278 return next;
279 if (next.hasContent())
280 return next;
281 return next.nextContentNode();
282 }
283
284 void doAdd(T o) {
285 if (consistency_testing) {
286 if (!matches(o, this.bbox())) {
287 o.getBBox().getIndex(level);
288 o.getBBox().getIndex(level - 1);
289 int nr = 0;
290 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
291 }
292 }
293 __add_content(o);
294 if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) {
295 __split();
296 }
297 }
298
299 void add(T o) {
300 findBucket(o.getBBox()).doAdd(o);
301 }
302
303 private void search(BBox search_bbox, List<T> result) {
304 if (!this.bbox().intersects(search_bbox))
305 return;
306 else if (bbox().bounds(search_bbox)) {
307 buckets.search_cache = this;
308 }
309
310 if (this.hasContent()) {
311 search_contents(search_bbox, result);
312 }
313
314 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
315
316 if (nw != null) {
317 nw.search(search_bbox, result);
318 }
319 if (ne != null) {
320 ne.search(search_bbox, result);
321 }
322 if (se != null) {
323 se.search(search_bbox, result);
324 }
325 if (sw != null) {
326 sw.search(search_bbox, result);
327 }
328 }
329
330 public String quads() {
331 return Long.toHexString(quad);
332 }
333
334 int index_of(QBLevel<T> find_this) {
335 QBLevel<T>[] children = getChildren();
336 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
337 if (children[i] == find_this)
338 return i;
339 }
340 return -1;
341 }
342
343 double width() {
344 return bbox.width();
345 }
346
347 double height() {
348 return bbox.height();
349 }
350
351 public BBox bbox() {
352 return bbox;
353 }
354
355 /*
356 * This gives the coordinate of the bottom-left
357 * corner of the box
358 */
359 LatLon coor() {
360 return QuadTiling.tile2LatLon(this.quad);
361 }
362
363 void remove_from_parent() {
364 if (parent == null)
365 return;
366
367 if (!canRemove()) {
368 abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren()));
369 }
370
371 if (parent.nw == this) {
372 parent.nw = null;
373 } else if (parent.ne == this) {
374 parent.ne = null;
375 } else if (parent.sw == this) {
376 parent.sw = null;
377 } else if (parent.se == this) {
378 parent.se = null;
379 }
380
381 if (parent.canRemove()) {
382 parent.remove_from_parent();
383 }
384 }
385
386 boolean canRemove() {
387 if (content != null && !content.isEmpty())
388 return false;
389 if (this.hasChildren())
390 return false;
391 return true;
392 }
393 }
394
395 private QBLevel<T> root;
396 private QBLevel<T> search_cache;
397 private int size;
398
399 /**
400 * Constructs a new {@code QuadBuckets}.
401 */
402 public QuadBuckets() {
403 clear();
404 }
405
406 @Override
407 public void clear() {
408 root = new QBLevel<T>(this);
409 search_cache = null;
410 size = 0;
411 }
412
413 @Override
414 public boolean add(T n) {
415 root.add(n);
416 size++;
417 return true;
418 }
419
420 @Override
421 public boolean retainAll(Collection<?> objects) {
422 for (T o : this) {
423 if (objects.contains(o)) {
424 continue;
425 }
426 if (!this.remove(o))
427 return false;
428 }
429 return true;
430 }
431
432 @Override
433 public boolean removeAll(Collection<?> objects) {
434 boolean changed = false;
435 for (Object o : objects) {
436 changed = changed | remove(o);
437 }
438 return changed;
439 }
440
441 @Override
442 public boolean addAll(Collection<? extends T> objects) {
443 boolean changed = false;
444 for (T o : objects) {
445 changed = changed | this.add(o);
446 }
447 return changed;
448 }
449
450 @Override
451 public boolean containsAll(Collection<?> objects) {
452 for (Object o : objects) {
453 if (!this.contains(o))
454 return false;
455 }
456 return true;
457 }
458
459 @Override
460 public boolean remove(Object o) {
461 @SuppressWarnings("unchecked")
462 T t = (T) o;
463 search_cache = null; // Search cache might point to one of removed buckets
464 QBLevel<T> bucket = root.findBucket(t.getBBox());
465 if (bucket.remove_content(t)) {
466 size--;
467 return true;
468 } else
469 return false;
470 }
471
472 @Override
473 public boolean contains(Object o) {
474 @SuppressWarnings("unchecked")
475 T t = (T) o;
476 QBLevel<T> bucket = root.findBucket(t.getBBox());
477 return bucket != null && bucket.content != null && bucket.content.contains(t);
478 }
479
480 public ArrayList<T> toArrayList() {
481 ArrayList<T> a = new ArrayList<T>();
482 for (T n : this) {
483 a.add(n);
484 }
485 return a;
486 }
487
488 @Override
489 public Object[] toArray() {
490 return this.toArrayList().toArray();
491 }
492
493 @Override
494 public <A> A[] toArray(A[] template) {
495 return this.toArrayList().toArray(template);
496 }
497
498 class QuadBucketIterator implements Iterator<T> {
499 QBLevel<T> current_node;
500 int content_index;
501 int iterated_over;
502
503 QBLevel<T> next_content_node(QBLevel<T> q) {
504 if (q == null)
505 return null;
506 QBLevel<T> orig = q;
507 QBLevel<T> next;
508 next = q.nextContentNode();
509 //if (consistency_testing && (orig == next))
510 if (orig == next) {
511 abort("got same leaf back leaf: " + q.isLeaf());
512 }
513 return next;
514 }
515
516 public QuadBucketIterator(QuadBuckets<T> qb) {
517 if (!qb.root.hasChildren() || qb.root.hasContent()) {
518 current_node = qb.root;
519 } else {
520 current_node = next_content_node(qb.root);
521 }
522 iterated_over = 0;
523 }
524
525 @Override
526 public boolean hasNext() {
527 if (this.peek() == null)
528 return false;
529 return true;
530 }
531
532 T peek() {
533 if (current_node == null)
534 return null;
535 while ((current_node.content == null) || (content_index >= current_node.content.size())) {
536 content_index = 0;
537 current_node = next_content_node(current_node);
538 if (current_node == null) {
539 break;
540 }
541 }
542 if (current_node == null || current_node.content == null)
543 return null;
544 return current_node.content.get(content_index);
545 }
546
547 @Override
548 public T next() {
549 T ret = peek();
550 content_index++;
551 iterated_over++;
552 return ret;
553 }
554
555 @Override
556 public void remove() {
557 // two uses
558 // 1. Back up to the thing we just returned
559 // 2. move the index back since we removed
560 // an element
561 content_index--;
562 T object = peek();
563 current_node.remove_content(object);
564 }
565 }
566
567 @Override
568 public Iterator<T> iterator() {
569 return new QuadBucketIterator(this);
570 }
571
572 @Override
573 public int size() {
574 return size;
575 }
576
577 @Override
578 public boolean isEmpty() {
579 if (this.size() == 0)
580 return true;
581 return false;
582 }
583
584 public List<T> search(BBox search_bbox) {
585 List<T> ret = new ArrayList<T>();
586 // Doing this cuts down search cost on a real-life data set by about 25%
587 boolean cache_searches = true;
588 if (cache_searches) {
589 if (search_cache == null) {
590 search_cache = root;
591 }
592 // Walk back up the tree when the last search spot can not cover the current search
593 while (search_cache != null && !search_cache.bbox().bounds(search_bbox)) {
594 search_cache = search_cache.parent;
595 }
596
597 if (search_cache == null) {
598 search_cache = root;
599 Main.info("bbox: " + search_bbox + " is out of the world");
600 }
601 } else {
602 search_cache = root;
603 }
604
605 // Save parent because search_cache might change during search call
606 QBLevel<T> tmp = search_cache.parent;
607
608 search_cache.search(search_bbox, ret);
609
610 // A way that spans this bucket may be stored in one
611 // of the nodes which is a parent of the search cache
612 while (tmp != null) {
613 tmp.search_contents(search_bbox, ret);
614 tmp = tmp.parent;
615 }
616 return ret;
617 }
618
619 public void printTree() {
620 printTreeRecursive(root, 0);
621 }
622
623 private void printTreeRecursive(QBLevel<T> level, int indent) {
624 if (level == null) {
625 printIndented(indent, "<empty child>");
626 return;
627 }
628 printIndented(indent, level);
629 if (level.hasContent()) {
630 for (T o : level.content) {
631 printIndented(indent, o);
632 }
633 }
634 for (QBLevel<T> child : level.getChildren()) {
635 printTreeRecursive(child, indent + 2);
636 }
637 }
638
639 private void printIndented(int indent, Object msg) {
640 for (int i = 0; i < indent; i++) {
641 System.out.print(' ');
642 }
643 System.out.println(msg);
644 }
645}
Note: See TracBrowser for help on using the repository browser.