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

Last change on this file since 11266 was 11237, checked in by bastiK, 7 years ago

applied #13933 - Simplify QuadBuckets and improve memory footprint (patch by Gerd Petermann, minor modifications)
  • Property svn:eol-style set to native
File size: 17.0 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 re-added.
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 byte NW_INDEX = 1;
26 private static final byte NE_INDEX = 3;
27 private static final byte SE_INDEX = 2;
28 private static final byte SW_INDEX = 0;
29
30 static void abort(String s) {
31 throw new AssertionError(s);
32 }
33
34 private static final int MAX_OBJECTS_PER_NODE = 48;
35
36 static class QBLevel<T extends OsmPrimitive> extends BBox {
37 private final byte level;
38 private final byte index;
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 QBLevel<T> getChild(byte index) {
48 switch (index) {
49 case NE_INDEX:
50 if (ne == null) {
51 ne = new QBLevel<>(this, index);
52 }
53 return ne;
54 case NW_INDEX:
55 if (nw == null) {
56 nw = new QBLevel<>(this, index);
57 }
58 return nw;
59 case SE_INDEX:
60 if (se == null) {
61 se = new QBLevel<>(this, index);
62 }
63 return se;
64 case SW_INDEX:
65 if (sw == null) {
66 sw = new QBLevel<>(this, index);
67 }
68 return sw;
69 default:
70 return null;
71 }
72 }
73
74 @SuppressWarnings("unchecked")
75 private QBLevel<T>[] getChildren() {
76 return new QBLevel[] {sw, nw, se, ne};
77 }
78
79 @Override
80 public String toString() {
81 return super.toString() + '[' + level + "]: ";
82 }
83
84 /**
85 * Constructor for root node
86 */
87 QBLevel() {
88 super(-180, 90, 180, -90);
89 level = 0;
90 index = 0;
91 quad = 0;
92 parent = null;
93 }
94
95 QBLevel(QBLevel<T> parent, byte index) {
96 this.parent = parent;
97 this.level = (byte) (parent.level + 1);
98 this.index = index;
99
100 int shift = (QuadTiling.NR_LEVELS - level) * 2;
101 long quadpart = (long) index << shift;
102 this.quad = parent.quad | quadpart;
103 LatLon bottomLeft = QuadTiling.tile2LatLon(this.quad);
104 xmin = bottomLeft.lon();
105 ymin = bottomLeft.lat();
106 xmax = xmin + parent.width() / 2;
107 ymax = ymin + parent.height() / 2;
108 }
109
110 QBLevel<T> findBucket(BBox bbox) {
111 if (!hasChildren())
112 return this;
113 else {
114 byte idx = bbox.getIndex(level);
115 if (idx == -1)
116 return this;
117 return getChild(idx).findBucket(bbox);
118 }
119 }
120
121 boolean removeContent(T o) {
122 // If two threads try to remove item at the same time from different buckets of this QBLevel,
123 // it might happen that one thread removes bucket but don't remove parent because it still sees
124 // another bucket set. Second thread do the same. Due to thread memory caching, it's possible that
125 // changes made by threads will show up in children array too late, leading to QBLevel with all children
126 // set to null
127 if (content == null)
128 return false;
129 boolean ret = this.content.remove(o);
130 if (this.content.isEmpty()) {
131 this.content = null;
132 }
133 if (this.canRemove()) {
134 this.removeFromParent();
135 }
136 return ret;
137 }
138
139 /*
140 * There is a race between this and qb.nextContentNode().
141 * If nextContentNode() runs into this bucket, it may
142 * attempt to null out 'children' because it thinks this
143 * is a dead end.
144 */
145 void doSplit() {
146 List<T> tmpcontent = content;
147 content = null;
148
149 for (T o : tmpcontent) {
150 byte idx = o.getBBox().getIndex(level);
151 if (idx == -1) {
152 doAddContent(o);
153 } else {
154 getChild(idx).doAdd(o);
155 }
156 }
157 isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1)
158 }
159
160 boolean doAddContent(T o) {
161 // The split_lock will keep two concurrent calls from overwriting content
162 if (content == null) {
163 content = new ArrayList<>();
164 }
165 return content.add(o);
166 }
167
168 boolean matches(final T o, final BBox searchBbox) {
169 if (o instanceof Node) {
170 final LatLon latLon = ((Node) o).getCoor();
171 // node without coords -> bbox[0,0,0,0]
172 return searchBbox.bounds(latLon != null ? latLon : LatLon.ZERO);
173 }
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 case NW_INDEX:
245 if (se != null)
246 return se;
247 case SE_INDEX:
248 return ne;
249 }
250 return null;
251 }
252
253 QBLevel<T> nextNode() {
254 if (!this.hasChildren())
255 return this.nextSibling();
256 return this.firstChild();
257 }
258
259 QBLevel<T> nextContentNode() {
260 QBLevel<T> next = this.nextNode();
261 if (next == null)
262 return next;
263 if (next.hasContent())
264 return next;
265 return next.nextContentNode();
266 }
267
268 void doAdd(T o) {
269 if (consistency_testing) {
270 if (o instanceof Node && !matches(o, this)) {
271 o.getBBox().getIndex(level);
272 o.getBBox().getIndex(level - 1);
273 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + super.toString());
274 }
275 }
276 doAddContent(o);
277 if (isLeaf() && content.size() > MAX_OBJECTS_PER_NODE && level < QuadTiling.NR_LEVELS) {
278 doSplit();
279 }
280 }
281
282 void add(T o) {
283 findBucket(o.getBBox()).doAdd(o);
284 }
285
286 private void search(QuadBuckets<T> buckets, BBox searchBbox, List<T> result) {
287 if (!this.intersects(searchBbox))
288 return;
289 else if (this.bounds(searchBbox)) {
290 buckets.searchCache = this;
291 }
292
293 if (this.hasContent()) {
294 searchContents(searchBbox, result);
295 }
296
297 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
298
299 if (nw != null) {
300 nw.search(buckets, searchBbox, result);
301 }
302 if (ne != null) {
303 ne.search(buckets, searchBbox, result);
304 }
305 if (se != null) {
306 se.search(buckets, searchBbox, result);
307 }
308 if (sw != null) {
309 sw.search(buckets, searchBbox, result);
310 }
311 }
312
313 public String quads() {
314 return Long.toHexString(quad);
315 }
316
317 int indexOf(QBLevel<T> findThis) {
318 QBLevel<T>[] children = getChildren();
319 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
320 if (children[i] == findThis)
321 return i;
322 }
323 return -1;
324 }
325
326 void removeFromParent() {
327 if (parent == null)
328 return;
329
330 if (!canRemove()) {
331 abort("attempt to remove non-empty child: " + this.content + ' ' + Arrays.toString(this.getChildren()));
332 }
333
334 if (parent.nw == this) {
335 parent.nw = null;
336 } else if (parent.ne == this) {
337 parent.ne = null;
338 } else if (parent.sw == this) {
339 parent.sw = null;
340 } else if (parent.se == this) {
341 parent.se = null;
342 }
343
344 if (parent.canRemove()) {
345 parent.removeFromParent();
346 }
347 }
348
349 boolean canRemove() {
350 if (content != null && !content.isEmpty())
351 return false;
352 if (this.hasChildren())
353 return false;
354 return true;
355 }
356 }
357
358 private QBLevel<T> root;
359 private QBLevel<T> searchCache;
360 private int size;
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 searchCache = null;
373 size = 0;
374 }
375
376 @Override
377 public boolean add(T n) {
378 root.add(n);
379 size++;
380 return true;
381 }
382
383 @Override
384 public boolean retainAll(Collection<?> objects) {
385 for (T o : this) {
386 if (objects.contains(o)) {
387 continue;
388 }
389 if (!this.remove(o))
390 return false;
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 return true;
420 }
421
422 @Override
423 public boolean remove(Object o) {
424 @SuppressWarnings("unchecked")
425 T t = (T) o;
426 searchCache = null; // Search cache might point to one of removed buckets
427 QBLevel<T> bucket = root.findBucket(t.getBBox());
428 if (bucket.removeContent(t)) {
429 size--;
430 return true;
431 } else
432 return false;
433 }
434
435 @Override
436 public boolean contains(Object o) {
437 @SuppressWarnings("unchecked")
438 T t = (T) o;
439 QBLevel<T> bucket = root.findBucket(t.getBBox());
440 return bucket != null && bucket.content != null && bucket.content.contains(t);
441 }
442
443 /**
444 * Converts to list.
445 * @return elements as list
446 */
447 public List<T> toList() {
448 List<T> a = new ArrayList<>();
449 for (T n : this) {
450 a.add(n);
451 }
452 return a;
453 }
454
455 @Override
456 public Object[] toArray() {
457 return this.toList().toArray();
458 }
459
460 @Override
461 public <A> A[] toArray(A[] template) {
462 return this.toList().toArray(template);
463 }
464
465 class QuadBucketIterator implements Iterator<T> {
466 private QBLevel<T> currentNode;
467 private int contentIndex;
468 QuadBuckets<T> qb;
469
470 final QBLevel<T> nextContentNode(QBLevel<T> q) {
471 if (q == null)
472 return null;
473 QBLevel<T> orig = q;
474 QBLevel<T> next;
475 next = q.nextContentNode();
476 if (orig == next) {
477 abort("got same leaf back leaf: " + q.isLeaf());
478 }
479 return next;
480 }
481
482 QuadBucketIterator(QuadBuckets<T> qb) {
483 if (!qb.root.hasChildren() || qb.root.hasContent()) {
484 currentNode = qb.root;
485 } else {
486 currentNode = nextContentNode(qb.root);
487 }
488 this.qb = qb;
489 }
490
491 @Override
492 public boolean hasNext() {
493 if (this.peek() == null)
494 return false;
495 return true;
496 }
497
498 T peek() {
499 if (currentNode == null)
500 return null;
501 while ((currentNode.content == null) || (contentIndex >= currentNode.content.size())) {
502 contentIndex = 0;
503 currentNode = nextContentNode(currentNode);
504 if (currentNode == null) {
505 break;
506 }
507 }
508 if (currentNode == null || currentNode.content == null)
509 return null;
510 return currentNode.content.get(contentIndex);
511 }
512
513 @Override
514 public T next() {
515 T ret = peek();
516 if (ret == null)
517 throw new NoSuchElementException();
518 contentIndex++;
519 return ret;
520 }
521
522 @Override
523 public void remove() {
524 // two uses
525 // 1. Back up to the thing we just returned
526 // 2. move the index back since we removed
527 // an element
528 contentIndex--;
529 T object = peek();
530 if (currentNode.removeContent(object))
531 qb.size--;
532 }
533 }
534
535 @Override
536 public Iterator<T> iterator() {
537 return new QuadBucketIterator(this);
538 }
539
540 @Override
541 public int size() {
542 return size;
543 }
544
545 @Override
546 public boolean isEmpty() {
547 return size == 0;
548 }
549
550 /**
551 * Search the tree for objects in the bbox (or crossing the bbox if they are ways)
552 * @param searchBbox the bbox
553 * @return List of primitives within the bbox (or crossing the bbox if they are ways). Can be empty, but not null.
554 */
555 public List<T> search(BBox searchBbox) {
556 List<T> ret = new ArrayList<>();
557 // Doing this cuts down search cost on a real-life data set by about 25%
558 if (searchCache == null) {
559 searchCache = root;
560 }
561 // Walk back up the tree when the last search spot can not cover the current search
562 while (searchCache != null && !searchCache.bounds(searchBbox)) {
563 searchCache = searchCache.parent;
564 }
565
566 if (searchCache == null) {
567 searchCache = root;
568 Main.info("bbox: " + searchBbox + " is out of the world");
569 }
570
571 // Save parent because searchCache might change during search call
572 QBLevel<T> tmp = searchCache.parent;
573
574 searchCache.search(this, searchBbox, ret);
575
576 // A way that spans this bucket may be stored in one
577 // of the nodes which is a parent of the search cache
578 while (tmp != null) {
579 tmp.searchContents(searchBbox, ret);
580 tmp = tmp.parent;
581 }
582 return ret;
583 }
584}
Note: See TracBrowser for help on using the repository browser.