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.Main; 013import org.openstreetmap.josm.data.coor.LatLon; 014import org.openstreetmap.josm.data.coor.QuadTiling; 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 case NW_INDEX: 244 if (se != null) 245 return se; 246 case SE_INDEX: 247 return ne; 248 } 249 return null; 250 } 251 252 QBLevel<T> nextNode() { 253 if (!this.hasChildren()) 254 return this.nextSibling(); 255 return this.firstChild(); 256 } 257 258 QBLevel<T> nextContentNode() { 259 QBLevel<T> next = this.nextNode(); 260 if (next == null) 261 return next; 262 if (next.hasContent()) 263 return next; 264 return next.nextContentNode(); 265 } 266 267 void doAdd(T o) { 268 if (consistency_testing) { 269 if (o instanceof Node && !matches(o, this)) { 270 o.getBBox().getIndex(level); 271 o.getBBox().getIndex(level - 1); 272 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + super.toString()); 273 } 274 } 275 doAddContent(o); 276 if (isLeaf() && content.size() > MAX_OBJECTS_PER_NODE && level < QuadTiling.NR_LEVELS) { 277 doSplit(); 278 } 279 } 280 281 void add(T o) { 282 findBucket(o.getBBox()).doAdd(o); 283 } 284 285 private void search(QuadBuckets<T> buckets, BBox searchBbox, List<T> result) { 286 if (!this.intersects(searchBbox)) 287 return; 288 else if (this.bounds(searchBbox)) { 289 buckets.searchCache = this; 290 } 291 292 if (this.hasContent()) { 293 searchContents(searchBbox, result); 294 } 295 296 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked 297 298 if (nw != null) { 299 nw.search(buckets, searchBbox, result); 300 } 301 if (ne != null) { 302 ne.search(buckets, searchBbox, result); 303 } 304 if (se != null) { 305 se.search(buckets, searchBbox, result); 306 } 307 if (sw != null) { 308 sw.search(buckets, searchBbox, result); 309 } 310 } 311 312 public String quads() { 313 return Long.toHexString(quad); 314 } 315 316 int indexOf(QBLevel<T> findThis) { 317 QBLevel<T>[] children = getChildren(); 318 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) { 319 if (children[i] == findThis) { 320 return i; 321 } 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 return (content == null || content.isEmpty()) && !this.hasChildren(); 351 } 352 } 353 354 private QBLevel<T> root; 355 private QBLevel<T> searchCache; 356 private int size; 357 private Collection<T> invalidBBoxPrimitives; 358 359 /** 360 * Constructs a new {@code QuadBuckets}. 361 */ 362 public QuadBuckets() { 363 clear(); 364 } 365 366 @Override 367 public final void clear() { 368 root = new QBLevel<>(); 369 invalidBBoxPrimitives = new LinkedHashSet<>(); 370 searchCache = null; 371 size = 0; 372 } 373 374 @Override 375 public boolean add(T n) { 376 if (n.getBBox().isValid()) { 377 root.add(n); 378 } else { 379 invalidBBoxPrimitives.add(n); 380 } 381 size++; 382 return true; 383 } 384 385 @Override 386 public boolean retainAll(Collection<?> objects) { 387 for (T o : this) { 388 if (objects.contains(o)) { 389 continue; 390 } 391 if (!this.remove(o)) { 392 return false; 393 } 394 } 395 return true; 396 } 397 398 @Override 399 public boolean removeAll(Collection<?> objects) { 400 boolean changed = false; 401 for (Object o : objects) { 402 changed = changed | remove(o); 403 } 404 return changed; 405 } 406 407 @Override 408 public boolean addAll(Collection<? extends T> objects) { 409 boolean changed = false; 410 for (T o : objects) { 411 changed = changed | this.add(o); 412 } 413 return changed; 414 } 415 416 @Override 417 public boolean containsAll(Collection<?> objects) { 418 for (Object o : objects) { 419 if (!this.contains(o)) { 420 return false; 421 } 422 } 423 return true; 424 } 425 426 @Override 427 public boolean remove(Object o) { 428 @SuppressWarnings("unchecked") 429 T t = (T) o; 430 searchCache = null; // Search cache might point to one of removed buckets 431 QBLevel<T> bucket = root.findBucket(t.getBBox()); 432 boolean removed = bucket.removeContent(t); 433 if (!removed) { 434 removed = invalidBBoxPrimitives.remove(o); 435 } 436 if (removed) { 437 size--; 438 } 439 return removed; 440 } 441 442 @Override 443 public boolean contains(Object o) { 444 @SuppressWarnings("unchecked") 445 T t = (T) o; 446 if (!t.getBBox().isValid()) { 447 return invalidBBoxPrimitives.contains(o); 448 } 449 QBLevel<T> bucket = root.findBucket(t.getBBox()); 450 return bucket != null && bucket.content != null && bucket.content.contains(t); 451 } 452 453 /** 454 * Converts to list. 455 * @return elements as list 456 */ 457 public List<T> toList() { 458 List<T> a = new ArrayList<>(); 459 for (T n : this) { 460 a.add(n); 461 } 462 return a; 463 } 464 465 @Override 466 public Object[] toArray() { 467 return this.toList().toArray(); 468 } 469 470 @Override 471 public <A> A[] toArray(A[] template) { 472 return this.toList().toArray(template); 473 } 474 475 class QuadBucketIterator implements Iterator<T> { 476 private QBLevel<T> currentNode; 477 private int contentIndex; 478 private final Iterator<T> invalidBBoxIterator = invalidBBoxPrimitives.iterator(); 479 boolean fromInvalidBBoxPrimitives; 480 QuadBuckets<T> qb; 481 482 final QBLevel<T> nextContentNode(QBLevel<T> q) { 483 if (q == null) 484 return null; 485 QBLevel<T> orig = q; 486 QBLevel<T> next; 487 next = q.nextContentNode(); 488 if (orig == next) { 489 abort("got same leaf back leaf: " + q.isLeaf()); 490 } 491 return next; 492 } 493 494 QuadBucketIterator(QuadBuckets<T> qb) { 495 if (!qb.root.hasChildren() || qb.root.hasContent()) { 496 currentNode = qb.root; 497 } else { 498 currentNode = nextContentNode(qb.root); 499 } 500 this.qb = qb; 501 } 502 503 @Override 504 public boolean hasNext() { 505 if (this.peek() == null) { 506 fromInvalidBBoxPrimitives = true; 507 return invalidBBoxIterator.hasNext(); 508 } 509 return true; 510 } 511 512 T peek() { 513 if (currentNode == null) 514 return null; 515 while ((currentNode.content == null) || (contentIndex >= currentNode.content.size())) { 516 contentIndex = 0; 517 currentNode = nextContentNode(currentNode); 518 if (currentNode == null) { 519 break; 520 } 521 } 522 if (currentNode == null || currentNode.content == null) 523 return null; 524 return currentNode.content.get(contentIndex); 525 } 526 527 @Override 528 public T next() { 529 if (fromInvalidBBoxPrimitives) { 530 return invalidBBoxIterator.next(); 531 } 532 T ret = peek(); 533 if (ret == null) 534 throw new NoSuchElementException(); 535 contentIndex++; 536 return ret; 537 } 538 539 @Override 540 public void remove() { 541 if (fromInvalidBBoxPrimitives) { 542 invalidBBoxIterator.remove(); 543 qb.size--; 544 } else { 545 // two uses 546 // 1. Back up to the thing we just returned 547 // 2. move the index back since we removed 548 // an element 549 contentIndex--; 550 T object = peek(); 551 if (currentNode.removeContent(object)) 552 qb.size--; 553 554 } 555 } 556 } 557 558 @Override 559 public Iterator<T> iterator() { 560 return new QuadBucketIterator(this); 561 } 562 563 @Override 564 public int size() { 565 return size; 566 } 567 568 @Override 569 public boolean isEmpty() { 570 return size == 0; 571 } 572 573 /** 574 * Search the tree for objects in the bbox (or crossing the bbox if they are ways) 575 * @param searchBbox the bbox 576 * @return List of primitives within the bbox (or crossing the bbox if they are ways). Can be empty, but not null. 577 */ 578 public List<T> search(BBox searchBbox) { 579 List<T> ret = new ArrayList<>(); 580 if (!searchBbox.isValid()) { 581 return ret; 582 } 583 584 // Doing this cuts down search cost on a real-life data set by about 25% 585 if (searchCache == null) { 586 searchCache = root; 587 } 588 // Walk back up the tree when the last search spot can not cover the current search 589 while (searchCache != null && !searchCache.bounds(searchBbox)) { 590 searchCache = searchCache.parent; 591 } 592 593 if (searchCache == null) { 594 searchCache = root; 595 Main.info("bbox: " + searchBbox + " is out of the world"); 596 } 597 598 // Save parent because searchCache might change during search call 599 QBLevel<T> tmp = searchCache.parent; 600 601 searchCache.search(this, searchBbox, ret); 602 603 // A way that spans this bucket may be stored in one 604 // of the nodes which is a parent of the search cache 605 while (tmp != null) { 606 tmp.searchContents(searchBbox, ret); 607 tmp = tmp.parent; 608 } 609 return ret; 610 } 611}