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

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

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