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.List; 009import java.util.NoSuchElementException; 010 011import org.openstreetmap.josm.Main; 012import org.openstreetmap.josm.data.coor.LatLon; 013import org.openstreetmap.josm.data.coor.QuadTiling; 014 015/** 016 * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must 017 * be removed and readded. 018 * 019 * This class is (no longer) thread safe. 020 * @param <T> type of primitives 021 * @since 2165 022 */ 023public class QuadBuckets<T extends OsmPrimitive> implements Collection<T> { 024 private static final boolean consistency_testing = false; 025 private static final int NW_INDEX = 1; 026 private static final int NE_INDEX = 3; 027 private static final int SE_INDEX = 2; 028 private static final int SW_INDEX = 0; 029 030 static void abort(String s) { 031 throw new AssertionError(s); 032 } 033 034 public static final int MAX_OBJECTS_PER_LEVEL = 16; 035 036 static class QBLevel<T extends OsmPrimitive> { 037 private final int level; 038 private final int index; 039 private final BBox bbox; 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 final QuadBuckets<T> buckets; 049 050 private QBLevel<T> getChild(int index) { 051 switch (index) { 052 case NE_INDEX: 053 if (ne == null) { 054 ne = new QBLevel<>(this, index, buckets); 055 } 056 return ne; 057 case NW_INDEX: 058 if (nw == null) { 059 nw = new QBLevel<>(this, index, buckets); 060 } 061 return nw; 062 case SE_INDEX: 063 if (se == null) { 064 se = new QBLevel<>(this, index, buckets); 065 } 066 return se; 067 case SW_INDEX: 068 if (sw == null) { 069 sw = new QBLevel<>(this, index, buckets); 070 } 071 return sw; 072 default: 073 return null; 074 } 075 } 076 077 @SuppressWarnings("unchecked") 078 private QBLevel<T>[] getChildren() { 079 return new QBLevel[] {sw, nw, se, ne}; 080 } 081 082 @Override 083 public String toString() { 084 return super.toString() + '[' + level + "]: " + bbox(); 085 } 086 087 /** 088 * Constructor for root node 089 * @param buckets quadbuckets 090 */ 091 QBLevel(final QuadBuckets<T> buckets) { 092 level = 0; 093 index = 0; 094 quad = 0; 095 parent = null; 096 bbox = new BBox(-180, 90, 180, -90); 097 this.buckets = buckets; 098 } 099 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 removeContent(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.removeFromParent(); 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 doSplit() { 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 doAddContent(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 doAddContent(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 searchContents(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> findNextSibling() { 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.findNextSibling(); 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.findNextSibling(); 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 doAddContent(o); 292 if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) { 293 doSplit(); 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 searchContents(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 indexOf(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 removeFromParent() { 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.removeFromParent(); 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.removeContent(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 QuadBuckets<T> qb; 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 this.qb = qb; 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 return ret; 555 } 556 557 @Override 558 public void remove() { 559 // two uses 560 // 1. Back up to the thing we just returned 561 // 2. move the index back since we removed 562 // an element 563 contentIndex--; 564 T object = peek(); 565 if (currentNode.removeContent(object)) 566 qb.size--; 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.searchContents(searchBbox, ret); 610 tmp = tmp.parent; 611 } 612 return ret; 613 } 614}