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

Last change on this file since 13795 was 13764, checked in by Don-vip, 6 years ago

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