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; 011 012import org.openstreetmap.josm.data.coor.LatLon; 013import org.openstreetmap.josm.data.coor.QuadTiling; 014import org.openstreetmap.josm.tools.Logging; 015 016/** 017 * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must 018 * be removed and re-added. 019 * 020 * This class is (no longer) thread safe. 021 * @param <T> type of primitives 022 * @since 2165 023 */ 024public class QuadBuckets<T extends OsmPrimitive> implements Collection<T> { 025 private static final boolean CONSISTENCY_TESTING = false; 026 private static final byte NW_INDEX = 1; 027 private static final byte NE_INDEX = 3; 028 private static final byte SE_INDEX = 2; 029 private static final byte SW_INDEX = 0; 030 031 static void abort(String s) { 032 throw new AssertionError(s); 033 } 034 035 private static final int MAX_OBJECTS_PER_NODE = 48; 036 037 static class QBLevel<T extends OsmPrimitive> extends BBox { 038 private final byte level; 039 private final byte index; 040 private final long quad; 041 private final QBLevel<T> parent; 042 private boolean isLeaf = true; 043 044 private List<T> content; 045 // child order by index is sw, nw, se, ne 046 private QBLevel<T> nw, ne, sw, se; 047 048 private QBLevel<T> getChild(byte index) { 049 switch (index) { 050 case NE_INDEX: 051 if (ne == null) { 052 ne = new QBLevel<>(this, index); 053 } 054 return ne; 055 case NW_INDEX: 056 if (nw == null) { 057 nw = new QBLevel<>(this, index); 058 } 059 return nw; 060 case SE_INDEX: 061 if (se == null) { 062 se = new QBLevel<>(this, index); 063 } 064 return se; 065 case SW_INDEX: 066 if (sw == null) { 067 sw = new QBLevel<>(this, index); 068 } 069 return sw; 070 default: 071 return null; 072 } 073 } 074 075 @SuppressWarnings("unchecked") 076 private QBLevel<T>[] getChildren() { 077 return new QBLevel[] {sw, nw, se, ne}; 078 } 079 080 @Override 081 public String toString() { 082 return super.toString() + '[' + level + "]: "; 083 } 084 085 /** 086 * Constructor for root node 087 */ 088 QBLevel() { 089 super(-180, 90, 180, -90); 090 level = 0; 091 index = 0; 092 quad = 0; 093 parent = null; 094 } 095 096 QBLevel(QBLevel<T> parent, byte index) { 097 this.parent = parent; 098 this.level = (byte) (parent.level + 1); 099 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}