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