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

Last change on this file since 16445 was 16445, checked in by simon04, 4 years ago

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