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; 009 010import org.openstreetmap.josm.Main; 011import org.openstreetmap.josm.data.coor.LatLon; 012import org.openstreetmap.josm.data.coor.QuadTiling; 013 014/** 015 * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must 016 * be removed and readded. 017 * 018 * This class is (no longer) thread safe. 019 * @param <T> type of primitives 020 * @since 2165 021 */ 022public class QuadBuckets<T extends OsmPrimitive> implements Collection<T> { 023 private static final boolean consistency_testing = false; 024 private static final int NW_INDEX = 1; 025 private static final int NE_INDEX = 3; 026 private static final int SE_INDEX = 2; 027 private static final int SW_INDEX = 0; 028 029 static void abort(String s) { 030 throw new AssertionError(s); 031 } 032 033 public static final int MAX_OBJECTS_PER_LEVEL = 16; 034 035 static class QBLevel<T extends OsmPrimitive> { 036 private final int level; 037 private final int index; 038 private final BBox bbox; 039 private final long quad; 040 private final QBLevel<T> parent; 041 private boolean isLeaf = true; 042 043 private List<T> content; 044 // child order by index is sw, nw, se, ne 045 private QBLevel<T> nw, ne, sw, se; 046 047 private final QuadBuckets<T> buckets; 048 049 private QBLevel<T> getChild(int index) { 050 switch (index) { 051 case NE_INDEX: 052 if (ne == null) { 053 ne = new QBLevel<>(this, index, buckets); 054 } 055 return ne; 056 case NW_INDEX: 057 if (nw == null) { 058 nw = new QBLevel<>(this, index, buckets); 059 } 060 return nw; 061 case SE_INDEX: 062 if (se == null) { 063 se = new QBLevel<>(this, index, buckets); 064 } 065 return se; 066 case SW_INDEX: 067 if (sw == null) { 068 sw = new QBLevel<>(this, index, buckets); 069 } 070 return sw; 071 default: 072 return null; 073 } 074 } 075 076 @SuppressWarnings("unchecked") 077 private QBLevel<T>[] getChildren() { 078 return new QBLevel[] {sw, nw, se, ne}; 079 } 080 081 @Override 082 public String toString() { 083 return super.toString() + '[' + level + "]: " + bbox(); 084 } 085 086 /** 087 * Constructor for root node 088 * @param buckets quadbuckets 089 */ 090 QBLevel(final QuadBuckets<T> buckets) { 091 level = 0; 092 index = 0; 093 quad = 0; 094 parent = null; 095 bbox = new BBox(-180, 90, 180, -90); 096 this.buckets = buckets; 097 } 098 099 QBLevel(QBLevel<T> parent, int parent_index, final QuadBuckets<T> buckets) { 100 this.parent = parent; 101 this.level = parent.level + 1; 102 this.index = parent_index; 103 this.buckets = buckets; 104 105 int shift = (QuadTiling.NR_LEVELS - level) * 2; 106 long mult = 1; 107 // Java blows the big one. It seems to wrap when you shift by > 31 108 if (shift >= 30) { 109 shift -= 30; 110 mult = 1 << 30; 111 } 112 long this_quadpart = mult * (parent_index << shift); 113 this.quad = parent.quad | this_quadpart; 114 this.bbox = calculateBBox(); // calculateBBox reference quad 115 } 116 117 private BBox calculateBBox() { 118 LatLon bottom_left = this.coor(); 119 double lat = bottom_left.lat() + parent.height() / 2; 120 double lon = bottom_left.lon() + parent.width() / 2; 121 return new BBox(bottom_left.lon(), bottom_left.lat(), lon, lat); 122 } 123 124 QBLevel<T> findBucket(BBox bbox) { 125 if (!hasChildren()) 126 return this; 127 else { 128 int idx = bbox.getIndex(level); 129 if (idx == -1) 130 return this; 131 return getChild(idx).findBucket(bbox); 132 } 133 } 134 135 boolean remove_content(T o) { 136 // If two threads try to remove item at the same time from different buckets of this QBLevel, 137 // it might happen that one thread removes bucket but don't remove parent because it still sees 138 // another bucket set. Second thread do the same. Due to thread memory caching, it's possible that 139 // changes made by threads will show up in children array too late, leading to QBLevel with all children 140 // set to null 141 if (content == null) 142 return false; 143 boolean ret = this.content.remove(o); 144 if (this.content.isEmpty()) { 145 this.content = null; 146 } 147 if (this.canRemove()) { 148 this.remove_from_parent(); 149 } 150 return ret; 151 } 152 153 /* 154 * There is a race between this and qb.nextContentNode(). 155 * If nextContentNode() runs into this bucket, it may 156 * attempt to null out 'children' because it thinks this 157 * is a dead end. 158 */ 159 void __split() { 160 List<T> tmpcontent = content; 161 content = null; 162 163 for (T o : tmpcontent) { 164 int idx = o.getBBox().getIndex(level); 165 if (idx == -1) { 166 __add_content(o); 167 } else { 168 getChild(idx).doAdd(o); 169 } 170 } 171 isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1) 172 } 173 174 boolean __add_content(T o) { 175 // The split_lock will keep two concurrent calls from overwriting content 176 if (content == null) { 177 content = new ArrayList<>(); 178 } 179 return content.add(o); 180 } 181 182 boolean matches(final T o, final BBox search_bbox) { 183 if (o instanceof Node) { 184 final LatLon latLon = ((Node) o).getCoor(); 185 // node without coords -> bbox[0,0,0,0] 186 return search_bbox.bounds(latLon != null ? latLon : LatLon.ZERO); 187 } 188 return o.getBBox().intersects(search_bbox); 189 } 190 191 private void search_contents(BBox search_bbox, List<T> result) { 192 /* 193 * It is possible that this was created in a split 194 * but never got any content populated. 195 */ 196 if (content == null) 197 return; 198 199 for (T o : content) { 200 if (matches(o, search_bbox)) { 201 result.add(o); 202 } 203 } 204 } 205 206 /* 207 * This is stupid. I tried to have a QBLeaf and QBBranch 208 * class descending from a QBLevel. It's more than twice 209 * as slow. So, this throws OO out the window, but it 210 * is fast. Runtime type determination must be slow. 211 */ 212 boolean isLeaf() { 213 return isLeaf; 214 } 215 216 boolean hasChildren() { 217 return nw != null || ne != null || sw != null || se != null; 218 } 219 220 QBLevel<T> next_sibling() { 221 return (parent == null) ? null : parent.firstSiblingOf(this); 222 } 223 224 boolean hasContent() { 225 return content != null; 226 } 227 228 QBLevel<T> nextSibling() { 229 QBLevel<T> next = this; 230 QBLevel<T> sibling = next.next_sibling(); 231 // Walk back up the tree to find the next sibling node. 232 // It may be either a leaf or branch. 233 while (sibling == null) { 234 next = next.parent; 235 if (next == null) { 236 break; 237 } 238 sibling = next.next_sibling(); 239 } 240 return sibling; 241 } 242 243 QBLevel<T> firstChild() { 244 if (sw != null) 245 return sw; 246 if (nw != null) 247 return nw; 248 if (se != null) 249 return se; 250 return ne; 251 } 252 253 QBLevel<T> firstSiblingOf(final QBLevel<T> child) { 254 switch (child.index) { 255 case SW_INDEX: 256 if (nw != null) 257 return nw; 258 case NW_INDEX: 259 if (se != null) 260 return se; 261 case SE_INDEX: 262 return ne; 263 } 264 return null; 265 } 266 267 QBLevel<T> nextNode() { 268 if (!this.hasChildren()) 269 return this.nextSibling(); 270 return this.firstChild(); 271 } 272 273 QBLevel<T> nextContentNode() { 274 QBLevel<T> next = this.nextNode(); 275 if (next == null) 276 return next; 277 if (next.hasContent()) 278 return next; 279 return next.nextContentNode(); 280 } 281 282 void doAdd(T o) { 283 if (consistency_testing) { 284 if (!matches(o, this.bbox())) { 285 o.getBBox().getIndex(level); 286 o.getBBox().getIndex(level - 1); 287 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox()); 288 } 289 } 290 __add_content(o); 291 if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) { 292 __split(); 293 } 294 } 295 296 void add(T o) { 297 findBucket(o.getBBox()).doAdd(o); 298 } 299 300 private void search(BBox search_bbox, List<T> result) { 301 if (!this.bbox().intersects(search_bbox)) 302 return; 303 else if (bbox().bounds(search_bbox)) { 304 buckets.searchCache = this; 305 } 306 307 if (this.hasContent()) { 308 search_contents(search_bbox, result); 309 } 310 311 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked 312 313 if (nw != null) { 314 nw.search(search_bbox, result); 315 } 316 if (ne != null) { 317 ne.search(search_bbox, result); 318 } 319 if (se != null) { 320 se.search(search_bbox, result); 321 } 322 if (sw != null) { 323 sw.search(search_bbox, result); 324 } 325 } 326 327 public String quads() { 328 return Long.toHexString(quad); 329 } 330 331 int index_of(QBLevel<T> find_this) { 332 QBLevel<T>[] children = getChildren(); 333 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) { 334 if (children[i] == find_this) 335 return i; 336 } 337 return -1; 338 } 339 340 double width() { 341 return bbox.width(); 342 } 343 344 double height() { 345 return bbox.height(); 346 } 347 348 public BBox bbox() { 349 return bbox; 350 } 351 352 /* 353 * This gives the coordinate of the bottom-left 354 * corner of the box 355 */ 356 final LatLon coor() { 357 return QuadTiling.tile2LatLon(this.quad); 358 } 359 360 void remove_from_parent() { 361 if (parent == null) 362 return; 363 364 if (!canRemove()) { 365 abort("attempt to remove non-empty child: " + this.content + ' ' + Arrays.toString(this.getChildren())); 366 } 367 368 if (parent.nw == this) { 369 parent.nw = null; 370 } else if (parent.ne == this) { 371 parent.ne = null; 372 } else if (parent.sw == this) { 373 parent.sw = null; 374 } else if (parent.se == this) { 375 parent.se = null; 376 } 377 378 if (parent.canRemove()) { 379 parent.remove_from_parent(); 380 } 381 } 382 383 boolean canRemove() { 384 if (content != null && !content.isEmpty()) 385 return false; 386 if (this.hasChildren()) 387 return false; 388 return true; 389 } 390 } 391 392 private QBLevel<T> root; 393 private QBLevel<T> searchCache; 394 private int size; 395 396 /** 397 * Constructs a new {@code QuadBuckets}. 398 */ 399 public QuadBuckets() { 400 clear(); 401 } 402 403 @Override 404 public final void clear() { 405 root = new QBLevel<>(this); 406 searchCache = null; 407 size = 0; 408 } 409 410 @Override 411 public boolean add(T n) { 412 root.add(n); 413 size++; 414 return true; 415 } 416 417 @Override 418 public boolean retainAll(Collection<?> objects) { 419 for (T o : this) { 420 if (objects.contains(o)) { 421 continue; 422 } 423 if (!this.remove(o)) 424 return false; 425 } 426 return true; 427 } 428 429 @Override 430 public boolean removeAll(Collection<?> objects) { 431 boolean changed = false; 432 for (Object o : objects) { 433 changed = changed | remove(o); 434 } 435 return changed; 436 } 437 438 @Override 439 public boolean addAll(Collection<? extends T> objects) { 440 boolean changed = false; 441 for (T o : objects) { 442 changed = changed | this.add(o); 443 } 444 return changed; 445 } 446 447 @Override 448 public boolean containsAll(Collection<?> objects) { 449 for (Object o : objects) { 450 if (!this.contains(o)) 451 return false; 452 } 453 return true; 454 } 455 456 @Override 457 public boolean remove(Object o) { 458 @SuppressWarnings("unchecked") 459 T t = (T) o; 460 searchCache = null; // Search cache might point to one of removed buckets 461 QBLevel<T> bucket = root.findBucket(t.getBBox()); 462 if (bucket.remove_content(t)) { 463 size--; 464 return true; 465 } else 466 return false; 467 } 468 469 @Override 470 public boolean contains(Object o) { 471 @SuppressWarnings("unchecked") 472 T t = (T) o; 473 QBLevel<T> bucket = root.findBucket(t.getBBox()); 474 return bucket != null && bucket.content != null && bucket.content.contains(t); 475 } 476 477 public List<T> toList() { 478 List<T> a = new ArrayList<>(); 479 for (T n : this) { 480 a.add(n); 481 } 482 return a; 483 } 484 485 @Override 486 public Object[] toArray() { 487 return this.toList().toArray(); 488 } 489 490 @Override 491 public <A> A[] toArray(A[] template) { 492 return this.toList().toArray(template); 493 } 494 495 class QuadBucketIterator implements Iterator<T> { 496 private QBLevel<T> currentNode; 497 private int contentIndex; 498 private int iteratedOver; 499 500 final QBLevel<T> next_content_node(QBLevel<T> q) { 501 if (q == null) 502 return null; 503 QBLevel<T> orig = q; 504 QBLevel<T> next; 505 next = q.nextContentNode(); 506 if (orig == next) { 507 abort("got same leaf back leaf: " + q.isLeaf()); 508 } 509 return next; 510 } 511 512 QuadBucketIterator(QuadBuckets<T> qb) { 513 if (!qb.root.hasChildren() || qb.root.hasContent()) { 514 currentNode = qb.root; 515 } else { 516 currentNode = next_content_node(qb.root); 517 } 518 iteratedOver = 0; 519 } 520 521 @Override 522 public boolean hasNext() { 523 if (this.peek() == null) 524 return false; 525 return true; 526 } 527 528 T peek() { 529 if (currentNode == null) 530 return null; 531 while ((currentNode.content == null) || (contentIndex >= currentNode.content.size())) { 532 contentIndex = 0; 533 currentNode = next_content_node(currentNode); 534 if (currentNode == null) { 535 break; 536 } 537 } 538 if (currentNode == null || currentNode.content == null) 539 return null; 540 return currentNode.content.get(contentIndex); 541 } 542 543 @Override 544 public T next() { 545 T ret = peek(); 546 contentIndex++; 547 iteratedOver++; 548 return ret; 549 } 550 551 @Override 552 public void remove() { 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 currentNode.remove_content(object); 560 } 561 } 562 563 @Override 564 public Iterator<T> iterator() { 565 return new QuadBucketIterator(this); 566 } 567 568 @Override 569 public int size() { 570 return size; 571 } 572 573 @Override 574 public boolean isEmpty() { 575 return size == 0; 576 } 577 578 public List<T> search(BBox search_bbox) { 579 List<T> ret = new ArrayList<>(); 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.bbox().bounds(search_bbox)) { 586 searchCache = searchCache.parent; 587 } 588 589 if (searchCache == null) { 590 searchCache = root; 591 Main.info("bbox: " + search_bbox + " 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(search_bbox, 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.search_contents(search_bbox, ret); 603 tmp = tmp.parent; 604 } 605 return ret; 606 } 607}