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

Last change on this file since 9853 was 9243, checked in by Don-vip, 8 years ago

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