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

Last change on this file since 11357 was 11277, checked in by Don-vip, 7 years ago

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