001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.osm; 003 004import java.util.ArrayList; 005import java.util.Arrays; 006import java.util.Collection; 007import java.util.Iterator; 008import java.util.LinkedHashSet; 009import java.util.List; 010import java.util.NoSuchElementException; 011import java.util.stream.IntStream; 012 013import org.openstreetmap.josm.data.IQuadBucketType; 014import org.openstreetmap.josm.data.coor.LatLon; 015import org.openstreetmap.josm.data.coor.QuadTiling; 016import org.openstreetmap.josm.tools.Logging; 017import org.openstreetmap.josm.tools.Utils; 018 019/** 020 * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must 021 * be removed and re-added. 022 * 023 * This class is (no longer) thread safe. 024 * @param <T> type of object extending {@link IQuadBucketType}. 025 * @since 2165 ({@link IPrimitive} only), 17459 for {@link IQuadBucketType} 026 */ 027public class QuadBuckets<T extends IQuadBucketType> implements Collection<T> { 028 private static final boolean CONSISTENCY_TESTING = false; 029 private static final byte NW_INDEX = 1; 030 private static final byte NE_INDEX = 3; 031 private static final byte SE_INDEX = 2; 032 private static final byte SW_INDEX = 0; 033 034 static void abort(String s) { 035 throw new AssertionError(s); 036 } 037 038 private static final int MAX_OBJECTS_PER_NODE = 48; 039 040 static class QBLevel<T extends IQuadBucketType> extends BBox { 041 private final byte level; 042 private final byte index; 043 private final long quad; 044 private final QBLevel<T> parent; 045 private boolean isLeaf = true; 046 047 private List<T> content; 048 // child order by index is sw, nw, se, ne 049 private QBLevel<T> nw, ne, sw, se; 050 051 private QBLevel<T> getChild(byte index) { 052 switch (index) { 053 case NE_INDEX: 054 if (ne == null) { 055 ne = new QBLevel<>(this, index); 056 } 057 return ne; 058 case NW_INDEX: 059 if (nw == null) { 060 nw = new QBLevel<>(this, index); 061 } 062 return nw; 063 case SE_INDEX: 064 if (se == null) { 065 se = new QBLevel<>(this, index); 066 } 067 return se; 068 case SW_INDEX: 069 if (sw == null) { 070 sw = new QBLevel<>(this, index); 071 } 072 return sw; 073 default: 074 return null; 075 } 076 } 077 078 @SuppressWarnings("unchecked") 079 private QBLevel<T>[] getChildren() { 080 return new QBLevel[] {sw, nw, se, ne}; 081 } 082 083 @Override 084 public String toString() { 085 return super.toString() + '[' + level + "]: "; 086 } 087 088 /** 089 * Constructor for root node 090 */ 091 QBLevel() { 092 super(-180, 90, 180, -90); 093 level = 0; 094 index = 0; 095 quad = 0; 096 parent = null; 097 } 098 099 QBLevel(QBLevel<T> parent, byte index) { 100 this.parent = parent; 101 this.level = (byte) (parent.level + 1); 102 this.index = index; 103 104 int shift = (QuadTiling.NR_LEVELS - level) * 2; 105 long quadpart = (long) index << shift; 106 this.quad = parent.quad | quadpart; 107 LatLon bottomLeft = QuadTiling.tile2LatLon(this.quad); 108 xmin = bottomLeft.lon(); 109 ymin = bottomLeft.lat(); 110 xmax = xmin + parent.width() / 2; 111 ymax = ymin + parent.height() / 2; 112 } 113 114 QBLevel<T> findBucket(BBox bbox) { 115 if (!hasChildren()) 116 return this; 117 else { 118 byte idx = bbox.getIndex(level); 119 if (idx == -1) 120 return this; 121 QBLevel<T> child = getChild(idx); 122 if (child == null) 123 return this; 124 return child.findBucket(bbox); 125 } 126 } 127 128 boolean removeContent(T o) { 129 // If two threads try to remove item at the same time from different buckets of this QBLevel, 130 // it might happen that one thread removes bucket but don't remove parent because it still sees 131 // another bucket set. Second thread do the same. Due to thread memory caching, it's possible that 132 // changes made by threads will show up in children array too late, leading to QBLevel with all children 133 // set to null 134 if (content == null) 135 return false; 136 boolean ret = this.content.remove(o); 137 if (this.content.isEmpty()) { 138 this.content = null; 139 } 140 if (this.canRemove()) { 141 this.removeFromParent(); 142 } 143 return ret; 144 } 145 146 /* 147 * There is a race between this and qb.nextContentNode(). 148 * If nextContentNode() runs into this bucket, it may attempt to null out 'children' because it thinks this is a dead end. 149 */ 150 void doSplit() { 151 List<T> tmpcontent = content; 152 content = null; 153 154 for (T o : tmpcontent) { 155 byte idx = o.getBBox().getIndex(level); 156 if (idx == -1) { 157 doAddContent(o); 158 } else { 159 QBLevel<T> child = getChild(idx); 160 if (child != null) 161 child.doAdd(o); 162 } 163 } 164 isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1) 165 } 166 167 boolean doAddContent(T o) { 168 // The split_lock will keep two concurrent calls from overwriting content 169 if (content == null) { 170 content = new ArrayList<>(); 171 } 172 return content.add(o); 173 } 174 175 boolean matches(final T o, final BBox searchBbox) { 176 return o.getBBox().intersects(searchBbox); 177 } 178 179 private void searchContents(BBox searchBbox, List<T> result) { 180 /* 181 * It is possible that this was created in a split 182 * but never got any content populated. 183 */ 184 if (content == null) 185 return; 186 187 for (T o : content) { 188 if (matches(o, searchBbox)) { 189 result.add(o); 190 } 191 } 192 } 193 194 /* 195 * This is stupid. I tried to have a QBLeaf and QBBranch 196 * class descending from a QBLevel. It's more than twice 197 * as slow. So, this throws OO out the window, but it 198 * is fast. Runtime type determination must be slow. 199 */ 200 boolean isLeaf() { 201 return isLeaf; 202 } 203 204 boolean hasChildren() { 205 return nw != null || ne != null || sw != null || se != null; 206 } 207 208 QBLevel<T> findNextSibling() { 209 return (parent == null) ? null : parent.firstSiblingOf(this); 210 } 211 212 boolean hasContent() { 213 return content != null; 214 } 215 216 QBLevel<T> nextSibling() { 217 QBLevel<T> next = this; 218 QBLevel<T> sibling = next.findNextSibling(); 219 // Walk back up the tree to find the next sibling node. 220 // It may be either a leaf or branch. 221 while (sibling == null) { 222 next = next.parent; 223 if (next == null) { 224 break; 225 } 226 sibling = next.findNextSibling(); 227 } 228 return sibling; 229 } 230 231 QBLevel<T> firstChild() { 232 if (sw != null) 233 return sw; 234 if (nw != null) 235 return nw; 236 if (se != null) 237 return se; 238 return ne; 239 } 240 241 QBLevel<T> firstSiblingOf(final QBLevel<T> child) { 242 switch (child.index) { 243 case SW_INDEX: 244 if (nw != null) 245 return nw; 246 if (se != null) 247 return se; 248 return ne; 249 case NW_INDEX: 250 if (se != null) 251 return se; 252 return ne; 253 case SE_INDEX: 254 return ne; 255 default: 256 return null; 257 } 258 } 259 260 QBLevel<T> nextNode() { 261 if (!this.hasChildren()) 262 return this.nextSibling(); 263 return this.firstChild(); 264 } 265 266 QBLevel<T> nextContentNode() { 267 QBLevel<T> next = this.nextNode(); 268 if (next == null) 269 return next; 270 if (next.hasContent()) 271 return next; 272 return next.nextContentNode(); 273 } 274 275 void doAdd(T o) { 276 if (CONSISTENCY_TESTING) { 277 if (o instanceof Node && !matches(o, this)) { 278 o.getBBox().getIndex(level); 279 o.getBBox().getIndex(level - 1); 280 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + super.toString()); 281 } 282 } 283 doAddContent(o); 284 if (level < QuadTiling.NR_LEVELS && isLeaf() && content.size() > MAX_OBJECTS_PER_NODE) { 285 doSplit(); 286 } 287 } 288 289 void add(T o) { 290 findBucket(o.getBBox()).doAdd(o); 291 } 292 293 private void search(QuadBuckets<T> buckets, BBox searchBbox, List<T> result) { 294 if (!this.intersects(searchBbox)) 295 return; 296 else if (this.bounds(searchBbox)) { 297 buckets.searchCache = this; 298 } 299 300 if (this.hasContent()) { 301 searchContents(searchBbox, result); 302 } 303 304 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked 305 306 if (nw != null) { 307 nw.search(buckets, searchBbox, result); 308 } 309 if (ne != null) { 310 ne.search(buckets, searchBbox, result); 311 } 312 if (se != null) { 313 se.search(buckets, searchBbox, result); 314 } 315 if (sw != null) { 316 sw.search(buckets, searchBbox, result); 317 } 318 } 319 320 public String quads() { 321 return Long.toHexString(quad); 322 } 323 324 int indexOf(QBLevel<T> findThis) { 325 QBLevel<T>[] children = getChildren(); 326 return IntStream.range(0, QuadTiling.TILES_PER_LEVEL) 327 .filter(i -> children[i] == findThis) 328 .findFirst().orElse(-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 Utils.isEmpty(content) && !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 return objects.stream().map(this::remove).reduce(false, (a, b) -> a || b); 409 } 410 411 @Override 412 public boolean addAll(Collection<? extends T> objects) { 413 return objects.stream().map(this::add).reduce(false, (a, b) -> a || b); 414 } 415 416 @Override 417 public boolean containsAll(Collection<?> objects) { 418 return objects.stream().allMatch(this::contains); 419 } 420 421 @Override 422 public boolean remove(Object o) { 423 @SuppressWarnings("unchecked") 424 T t = (T) o; 425 searchCache = null; // Search cache might point to one of removed buckets 426 QBLevel<T> bucket = root.findBucket(t.getBBox()); 427 boolean removed = bucket.removeContent(t); 428 if (!removed) { 429 removed = invalidBBoxPrimitives.remove(o); 430 } 431 if (removed) { 432 size--; 433 } 434 return removed; 435 } 436 437 @Override 438 public boolean contains(Object o) { 439 @SuppressWarnings("unchecked") 440 T t = (T) o; 441 if (!t.getBBox().isValid()) { 442 return invalidBBoxPrimitives.contains(o); 443 } 444 QBLevel<T> bucket = root.findBucket(t.getBBox()); 445 return bucket != null && bucket.content != null && bucket.content.contains(t); 446 } 447 448 /** 449 * Converts to list. 450 * @return elements as list 451 */ 452 public List<T> toList() { 453 return new ArrayList<>(this); 454 } 455 456 @Override 457 public Object[] toArray() { 458 // Don't call toList() -- in some cases, this can produce an infinite loop 459 // For example, ArrayList may call toArray to get the initial array. However, since we are 460 // creating a new ArrayList in toList with `this`, this creates an infinite recursion loop. 461 // So a `toArray` call becomes `toArray -> toList -> toArray -> toList -> toArray -> ...` 462 // For more information, see #20587. 463 return this.stream().toArray(); 464 } 465 466 @Override 467 public <A> A[] toArray(A[] template) { 468 return this.toList().toArray(template); 469 } 470 471 class QuadBucketIterator implements Iterator<T> { 472 private QBLevel<T> currentNode; 473 private int contentIndex; 474 private final Iterator<T> invalidBBoxIterator = invalidBBoxPrimitives.iterator(); 475 boolean fromInvalidBBoxPrimitives; 476 QuadBuckets<T> qb; 477 478 final QBLevel<T> nextContentNode(QBLevel<T> q) { 479 if (q == null) 480 return null; 481 QBLevel<T> orig = q; 482 QBLevel<T> next; 483 next = q.nextContentNode(); 484 if (orig == next) { 485 abort("got same leaf back leaf: " + q.isLeaf()); 486 } 487 return next; 488 } 489 490 QuadBucketIterator(QuadBuckets<T> qb) { 491 if (!qb.root.hasChildren() || qb.root.hasContent()) { 492 currentNode = qb.root; 493 } else { 494 currentNode = nextContentNode(qb.root); 495 } 496 this.qb = qb; 497 } 498 499 @Override 500 public boolean hasNext() { 501 if (this.peek() == null) { 502 fromInvalidBBoxPrimitives = true; 503 return invalidBBoxIterator.hasNext(); 504 } 505 return true; 506 } 507 508 T peek() { 509 if (currentNode == null) 510 return null; 511 while ((currentNode.content == null) || (contentIndex >= currentNode.content.size())) { 512 contentIndex = 0; 513 currentNode = nextContentNode(currentNode); 514 if (currentNode == null) { 515 break; 516 } 517 } 518 if (currentNode == null || currentNode.content == null) 519 return null; 520 return currentNode.content.get(contentIndex); 521 } 522 523 @Override 524 public T next() { 525 if (fromInvalidBBoxPrimitives) { 526 return invalidBBoxIterator.next(); 527 } 528 T ret = peek(); 529 if (ret == null) 530 throw new NoSuchElementException(); 531 contentIndex++; 532 return ret; 533 } 534 535 @Override 536 public void remove() { 537 if (fromInvalidBBoxPrimitives) { 538 invalidBBoxIterator.remove(); 539 qb.size--; 540 } else { 541 // two uses 542 // 1. Back up to the thing we just returned 543 // 2. move the index back since we removed 544 // an element 545 contentIndex--; 546 T object = peek(); 547 if (currentNode.removeContent(object)) 548 qb.size--; 549 550 } 551 } 552 } 553 554 @Override 555 public Iterator<T> iterator() { 556 return new QuadBucketIterator(this); 557 } 558 559 @Override 560 public int size() { 561 return size; 562 } 563 564 @Override 565 public boolean isEmpty() { 566 return size == 0; 567 } 568 569 /** 570 * Search the tree for objects in the bbox (or crossing the bbox if they are ways) 571 * @param searchBbox the bbox 572 * @return List of primitives within the bbox (or crossing the bbox if they are ways). Can be empty, but not null. 573 */ 574 public List<T> search(BBox searchBbox) { 575 List<T> ret = new ArrayList<>(); 576 if (searchBbox == null || !searchBbox.isValid()) { 577 return ret; 578 } 579 580 // Doing this cuts down search cost on a real-life data set by about 25% 581 if (searchCache == null) { 582 searchCache = root; 583 } 584 // Walk back up the tree when the last search spot can not cover the current search 585 while (searchCache != null && !searchCache.bounds(searchBbox)) { 586 searchCache = searchCache.parent; 587 } 588 589 if (searchCache == null) { 590 searchCache = root; 591 Logging.info("bbox: " + searchBbox + " is out of the world"); 592 } 593 594 // Save parent because searchCache might change during search call 595 QBLevel<T> tmp = searchCache.parent; 596 597 searchCache.search(this, searchBbox, ret); 598 599 // A way that spans this bucket may be stored in one 600 // of the nodes which is a parent of the search cache 601 while (tmp != null) { 602 tmp.searchContents(searchBbox, ret); 603 tmp = tmp.parent; 604 } 605 return ret; 606 } 607}