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<T>(this, index, buckets); 053 } 054 return ne; 055 case NW_INDEX: 056 if (nw == null) { 057 nw = new QBLevel<T>(this, index, buckets); 058 } 059 return nw; 060 case SE_INDEX: 061 if (se == null) { 062 se = new QBLevel<T>(this, index, buckets); 063 } 064 return se; 065 case SW_INDEX: 066 if (sw == null) { 067 sw = new QBLevel<T>(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 public 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 public 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 boolean ret = false; 174 // The split_lock will keep two concurrent calls from overwriting content 175 if (content == null) { 176 content = new ArrayList<T>(); 177 } 178 ret = content.add(o); 179 return ret; 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 232 // next sibling node. It may be either 233 // a leaf or branch. 234 while (sibling == null) { 235 next = next.parent; 236 if (next == null) { 237 break; 238 } 239 sibling = next.next_sibling(); 240 } 241 next = sibling; 242 return next; 243 } 244 245 QBLevel<T> firstChild() { 246 if (sw != null) 247 return sw; 248 if (nw != null) 249 return nw; 250 if (se != null) 251 return se; 252 return ne; 253 } 254 255 QBLevel<T> firstSiblingOf(final QBLevel<T> child) { 256 switch (child.index) { 257 case SW_INDEX: 258 if (nw != null) 259 return nw; 260 case NW_INDEX: 261 if (se != null) 262 return se; 263 case SE_INDEX: 264 return ne; 265 } 266 return null; 267 } 268 269 QBLevel<T> nextNode() { 270 if (!this.hasChildren()) 271 return this.nextSibling(); 272 return this.firstChild(); 273 } 274 275 QBLevel<T> nextContentNode() { 276 QBLevel<T> next = this.nextNode(); 277 if (next == null) 278 return next; 279 if (next.hasContent()) 280 return next; 281 return next.nextContentNode(); 282 } 283 284 void doAdd(T o) { 285 if (consistency_testing) { 286 if (!matches(o, this.bbox())) { 287 o.getBBox().getIndex(level); 288 o.getBBox().getIndex(level - 1); 289 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox()); 290 } 291 } 292 __add_content(o); 293 if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) { 294 __split(); 295 } 296 } 297 298 void add(T o) { 299 findBucket(o.getBBox()).doAdd(o); 300 } 301 302 private void search(BBox search_bbox, List<T> result) { 303 if (!this.bbox().intersects(search_bbox)) 304 return; 305 else if (bbox().bounds(search_bbox)) { 306 buckets.search_cache = this; 307 } 308 309 if (this.hasContent()) { 310 search_contents(search_bbox, result); 311 } 312 313 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked 314 315 if (nw != null) { 316 nw.search(search_bbox, result); 317 } 318 if (ne != null) { 319 ne.search(search_bbox, result); 320 } 321 if (se != null) { 322 se.search(search_bbox, result); 323 } 324 if (sw != null) { 325 sw.search(search_bbox, result); 326 } 327 } 328 329 public String quads() { 330 return Long.toHexString(quad); 331 } 332 333 int index_of(QBLevel<T> find_this) { 334 QBLevel<T>[] children = getChildren(); 335 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) { 336 if (children[i] == find_this) 337 return i; 338 } 339 return -1; 340 } 341 342 double width() { 343 return bbox.width(); 344 } 345 346 double height() { 347 return bbox.height(); 348 } 349 350 public BBox bbox() { 351 return bbox; 352 } 353 354 /* 355 * This gives the coordinate of the bottom-left 356 * corner of the box 357 */ 358 LatLon coor() { 359 return QuadTiling.tile2LatLon(this.quad); 360 } 361 362 void remove_from_parent() { 363 if (parent == null) 364 return; 365 366 if (!canRemove()) { 367 abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren())); 368 } 369 370 if (parent.nw == this) { 371 parent.nw = null; 372 } else if (parent.ne == this) { 373 parent.ne = null; 374 } else if (parent.sw == this) { 375 parent.sw = null; 376 } else if (parent.se == this) { 377 parent.se = null; 378 } 379 380 if (parent.canRemove()) { 381 parent.remove_from_parent(); 382 } 383 } 384 385 boolean canRemove() { 386 if (content != null && !content.isEmpty()) 387 return false; 388 if (this.hasChildren()) 389 return false; 390 return true; 391 } 392 } 393 394 private QBLevel<T> root; 395 private QBLevel<T> search_cache; 396 private int size; 397 398 /** 399 * Constructs a new {@code QuadBuckets}. 400 */ 401 public QuadBuckets() { 402 clear(); 403 } 404 405 @Override 406 public void clear() { 407 root = new QBLevel<T>(this); 408 search_cache = null; 409 size = 0; 410 } 411 412 @Override 413 public boolean add(T n) { 414 root.add(n); 415 size++; 416 return true; 417 } 418 419 @Override 420 public boolean retainAll(Collection<?> objects) { 421 for (T o : this) { 422 if (objects.contains(o)) { 423 continue; 424 } 425 if (!this.remove(o)) 426 return false; 427 } 428 return true; 429 } 430 431 @Override 432 public boolean removeAll(Collection<?> objects) { 433 boolean changed = false; 434 for (Object o : objects) { 435 changed = changed | remove(o); 436 } 437 return changed; 438 } 439 440 @Override 441 public boolean addAll(Collection<? extends T> objects) { 442 boolean changed = false; 443 for (T o : objects) { 444 changed = changed | this.add(o); 445 } 446 return changed; 447 } 448 449 @Override 450 public boolean containsAll(Collection<?> objects) { 451 for (Object o : objects) { 452 if (!this.contains(o)) 453 return false; 454 } 455 return true; 456 } 457 458 @Override 459 public boolean remove(Object o) { 460 @SuppressWarnings("unchecked") 461 T t = (T) o; 462 search_cache = null; // Search cache might point to one of removed buckets 463 QBLevel<T> bucket = root.findBucket(t.getBBox()); 464 if (bucket.remove_content(t)) { 465 size--; 466 return true; 467 } else 468 return false; 469 } 470 471 @Override 472 public boolean contains(Object o) { 473 @SuppressWarnings("unchecked") 474 T t = (T) o; 475 QBLevel<T> bucket = root.findBucket(t.getBBox()); 476 return bucket != null && bucket.content != null && bucket.content.contains(t); 477 } 478 479 public ArrayList<T> toArrayList() { 480 ArrayList<T> a = new ArrayList<T>(); 481 for (T n : this) { 482 a.add(n); 483 } 484 return a; 485 } 486 487 @Override 488 public Object[] toArray() { 489 return this.toArrayList().toArray(); 490 } 491 492 @Override 493 public <A> A[] toArray(A[] template) { 494 return this.toArrayList().toArray(template); 495 } 496 497 class QuadBucketIterator implements Iterator<T> { 498 QBLevel<T> current_node; 499 int content_index; 500 int iterated_over; 501 502 QBLevel<T> next_content_node(QBLevel<T> q) { 503 if (q == null) 504 return null; 505 QBLevel<T> orig = q; 506 QBLevel<T> next; 507 next = q.nextContentNode(); 508 if (orig == next) { 509 abort("got same leaf back leaf: " + q.isLeaf()); 510 } 511 return next; 512 } 513 514 public QuadBucketIterator(QuadBuckets<T> qb) { 515 if (!qb.root.hasChildren() || qb.root.hasContent()) { 516 current_node = qb.root; 517 } else { 518 current_node = next_content_node(qb.root); 519 } 520 iterated_over = 0; 521 } 522 523 @Override 524 public boolean hasNext() { 525 if (this.peek() == null) 526 return false; 527 return true; 528 } 529 530 T peek() { 531 if (current_node == null) 532 return null; 533 while ((current_node.content == null) || (content_index >= current_node.content.size())) { 534 content_index = 0; 535 current_node = next_content_node(current_node); 536 if (current_node == null) { 537 break; 538 } 539 } 540 if (current_node == null || current_node.content == null) 541 return null; 542 return current_node.content.get(content_index); 543 } 544 545 @Override 546 public T next() { 547 T ret = peek(); 548 content_index++; 549 iterated_over++; 550 return ret; 551 } 552 553 @Override 554 public void remove() { 555 // two uses 556 // 1. Back up to the thing we just returned 557 // 2. move the index back since we removed 558 // an element 559 content_index--; 560 T object = peek(); 561 current_node.remove_content(object); 562 } 563 } 564 565 @Override 566 public Iterator<T> iterator() { 567 return new QuadBucketIterator(this); 568 } 569 570 @Override 571 public int size() { 572 return size; 573 } 574 575 @Override 576 public boolean isEmpty() { 577 if (this.size() == 0) 578 return true; 579 return false; 580 } 581 582 public List<T> search(BBox search_bbox) { 583 List<T> ret = new ArrayList<T>(); 584 // Doing this cuts down search cost on a real-life data set by about 25% 585 boolean cache_searches = true; 586 if (cache_searches) { 587 if (search_cache == null) { 588 search_cache = root; 589 } 590 // Walk back up the tree when the last search spot can not cover the current search 591 while (search_cache != null && !search_cache.bbox().bounds(search_bbox)) { 592 search_cache = search_cache.parent; 593 } 594 595 if (search_cache == null) { 596 search_cache = root; 597 Main.info("bbox: " + search_bbox + " is out of the world"); 598 } 599 } else { 600 search_cache = root; 601 } 602 603 // Save parent because search_cache might change during search call 604 QBLevel<T> tmp = search_cache.parent; 605 606 search_cache.search(search_bbox, ret); 607 608 // A way that spans this bucket may be stored in one 609 // of the nodes which is a parent of the search cache 610 while (tmp != null) { 611 tmp.search_contents(search_bbox, ret); 612 tmp = tmp.parent; 613 } 614 return ret; 615 } 616 617 public void printTree() { 618 printTreeRecursive(root, 0); 619 } 620 621 private void printTreeRecursive(QBLevel<T> level, int indent) { 622 if (level == null) { 623 printIndented(indent, "<empty child>"); 624 return; 625 } 626 printIndented(indent, level); 627 if (level.hasContent()) { 628 for (T o : level.content) { 629 printIndented(indent, o); 630 } 631 } 632 for (QBLevel<T> child : level.getChildren()) { 633 printTreeRecursive(child, indent + 2); 634 } 635 } 636 637 private void printIndented(int indent, Object msg) { 638 for (int i = 0; i < indent; i++) { 639 System.out.print(' '); 640 } 641 System.out.println(msg); 642 } 643}