001 // License: GPL. For details, see LICENSE file. 002 package org.openstreetmap.josm.data.osm; 003 004 import java.lang.reflect.Array; 005 import java.util.ArrayList; 006 import java.util.Arrays; 007 import java.util.Collection; 008 import java.util.Iterator; 009 import java.util.List; 010 011 import org.openstreetmap.josm.data.coor.LatLon; 012 import 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 */ 021 public class QuadBuckets<T extends OsmPrimitive> implements Collection<T> 022 { 023 //private static boolean debug = false; 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 { 032 throw new AssertionError(s); 033 } 034 static void out(String s) 035 { 036 System.out.println(s); 037 } 038 // periodic output 039 long last_out = -1; 040 void pout(String s) 041 { 042 long now = System.currentTimeMillis(); 043 if (now - last_out < 300) 044 return; 045 last_out = now; 046 System.out.print(s + "\r"); 047 } 048 void pout(String s, int i, int total) 049 { 050 long now = System.currentTimeMillis(); 051 if ((now - last_out < 300) && 052 ((i+1) < total)) 053 return; 054 last_out = now; 055 // cast to float to keep the output size down 056 System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done \r"); 057 } 058 059 public static final int MAX_OBJECTS_PER_LEVEL = 16; 060 class QBLevel 061 { 062 final int level; 063 private final BBox bbox; 064 final long quad; 065 final QBLevel parent; 066 private boolean isLeaf = true; 067 068 public List<T> content; 069 public QBLevel nw, ne, sw, se; 070 071 private QBLevel getChild(int index) { 072 switch (index) { 073 case NE_INDEX: 074 if (ne == null) { 075 ne = new QBLevel(this, index); 076 } 077 return ne; 078 case NW_INDEX: 079 if (nw == null) { 080 nw = new QBLevel(this, index); 081 } 082 return nw; 083 case SE_INDEX: 084 if (se == null) { 085 se = new QBLevel(this, index); 086 } 087 return se; 088 case SW_INDEX: 089 if (sw == null) { 090 sw = new QBLevel(this, index); 091 } 092 return sw; 093 default: 094 return null; 095 } 096 } 097 098 private QBLevel[] getChildren() { 099 // This is ugly and hackish. But, it seems to work, 100 // and using an ArrayList here seems to cost us 101 // a significant performance penalty -- 50% in my 102 // testing. Child access is one of the single 103 // hottest code paths in this entire class. 104 QBLevel[] result = (QBLevel[]) Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL); 105 result[NW_INDEX] = nw; 106 result[NE_INDEX] = ne; 107 result[SW_INDEX] = sw; 108 result[SE_INDEX] = se; 109 return result; 110 } 111 112 @Override 113 public String toString() { 114 return super.toString()+ "["+level+"]: " + bbox(); 115 } 116 /** 117 * Constructor for root node 118 */ 119 public QBLevel() { 120 level = 0; 121 quad = 0; 122 parent = null; 123 bbox = new BBox(-180, 90, 180, -90); 124 } 125 126 public QBLevel(QBLevel parent, int parent_index) { 127 this.parent = parent; 128 this.level = parent.level + 1; 129 int shift = (QuadTiling.NR_LEVELS - level) * 2; 130 long mult = 1; 131 // Java blows the big one. It seems to wrap when 132 // you shift by > 31 133 if (shift >= 30) { 134 shift -= 30; 135 mult = 1<<30; 136 } 137 long this_quadpart = mult * (parent_index << shift); 138 this.quad = parent.quad | this_quadpart; 139 this.bbox = calculateBBox(); // calculateBBox reference quad 140 /*if (debug) { 141 out("new level["+this.level+"] bbox["+parent_index+"]: " + this.bbox() 142 + " coor: " + this.coor() 143 + " quadpart: " + Long.toHexString(this_quadpart) 144 + " quad: " + Long.toHexString(this.quad)); 145 }*/ 146 } 147 148 private BBox calculateBBox() { 149 LatLon bottom_left = this.coor(); 150 double lat = bottom_left.lat() + parent.height() / 2; 151 double lon = bottom_left.lon() + parent.width() / 2; 152 LatLon top_right = new LatLon(lat, lon); 153 return new BBox(bottom_left, top_right); 154 } 155 156 QBLevel findBucket(BBox bbox) { 157 if (!hasChildren()) 158 return this; 159 else { 160 int index = get_index(bbox, level); 161 if (index == -1) 162 return this; 163 return getChild(index).findBucket(bbox); 164 } 165 } 166 167 boolean remove_content(T o) 168 { 169 // If two threads try to remove item at the same time from different buckets of this QBLevel, 170 // it might happen that one thread removes bucket but don't remove parent because it still sees 171 // another bucket set. Second thread do the same. Due to thread memory caching, it's possible that 172 // changes made by threads will show up in children array too late, leading to QBLevel with all children 173 // set to null 174 if (content == null) 175 return false; 176 boolean ret = this.content.remove(o); 177 if (this.content.size() == 0) { 178 this.content = null; 179 } 180 if (this.canRemove()) { 181 this.remove_from_parent(); 182 } 183 return ret; 184 } 185 // Get the correct index for the given primitive 186 // at the given level. If the primitive can not 187 // fit into a single quad at this level, return -1 188 int get_index(BBox bbox, int level) { 189 int index = -1; 190 for (LatLon c : bbox.points()) { 191 /*if (debug) { 192 out("getting index for point: " + c); 193 }*/ 194 if (index == -1) { 195 index = QuadTiling.index(c, level); 196 /*if (debug) { 197 out("set initial index to: " + index); 198 }*/ 199 continue; 200 } 201 int another_index = QuadTiling.index(c, level); 202 /*if (debug) { 203 out("other point index: " + another_index); 204 }*/ 205 if (another_index != index) 206 return -1; 207 } 208 return index; 209 } 210 /* 211 * There is a race between this and qb.nextContentNode(). 212 * If nextContentNode() runs into this bucket, it may 213 * attempt to null out 'children' because it thinks this 214 * is a dead end. 215 */ 216 void __split() { 217 /*if (debug) { 218 out("splitting "+this.bbox()+" level "+level+" with " 219 + content.size() + " entries (my dimensions: " 220 + this.bbox().width()+", "+this.bbox().height()+")"); 221 }*/ 222 List<T> tmpcontent = content; 223 content = null; 224 225 for (T o: tmpcontent) { 226 int index = get_index(o.getBBox(), level); 227 if (index == -1) { 228 __add_content(o); 229 } else { 230 getChild(index).doAdd(o); 231 } 232 } 233 isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1) 234 } 235 236 boolean __add_content(T o) 237 { 238 boolean ret = false; 239 // The split_lock will keep two concurrent 240 // calls from overwriting content 241 if (content == null) { 242 content = new ArrayList<T>(); 243 } 244 ret = content.add(o); 245 /*if (debug && !this.isLeaf()) { 246 pout("added "+o.getClass().getName()+" to non-leaf with size: " + content.size()); 247 }*/ 248 return ret; 249 } 250 boolean matches(T o, BBox search_bbox) 251 { 252 // This can be optimized when o is a node 253 //return search_bbox.bounds(coor)); 254 return o.getBBox().intersects(search_bbox); 255 } 256 private void search_contents(BBox search_bbox, List<T> result) 257 { 258 /*if (debug) { 259 out("searching contents (size: " + content == null?"<null>":content.size() + ") for " + search_bbox); 260 }*/ 261 /* 262 * It is possible that this was created in a split 263 * but never got any content populated. 264 */ 265 if (content == null) 266 return; 267 268 for (T o : content) { 269 if (matches(o, search_bbox)) { 270 result.add(o); 271 } 272 } 273 /*if (debug) { 274 out("done searching quad " + Long.toHexString(this.quad)); 275 }*/ 276 } 277 /* 278 * This is stupid. I tried to have a QBLeaf and QBBranch 279 * class decending from a QBLevel. It's more than twice 280 * as slow. So, this throws OO out the window, but it 281 * is fast. Runtime type determination must be slow. 282 */ 283 boolean isLeaf() { 284 return isLeaf; 285 } 286 boolean hasChildren() { 287 return nw != null || ne != null || sw != null || se != null; 288 } 289 290 QBLevel next_sibling() 291 { 292 boolean found_me = false; 293 if (parent == null) 294 return null; 295 int __nr = 0; 296 for (QBLevel sibling : parent.getChildren()) { 297 __nr++; 298 int nr = __nr-1; 299 if (sibling == null) { 300 /*if (debug) { 301 out("[" + this.level + "] null child nr: " + nr); 302 }*/ 303 continue; 304 } 305 // We're looking for the *next* child 306 // after us. 307 if (sibling == this) { 308 /*if (debug) { 309 out("[" + this.level + "] I was child nr: " + nr); 310 }*/ 311 found_me = true; 312 continue; 313 } 314 if (found_me) 315 /*if (debug) { 316 out("[" + this.level + "] next sibling was child nr: " + nr); 317 }*/ 318 return sibling; 319 } 320 return null; 321 } 322 boolean hasContent() 323 { 324 return content != null; 325 } 326 QBLevel nextSibling() 327 { 328 QBLevel next = this; 329 QBLevel sibling = next.next_sibling(); 330 // Walk back up the tree to find the 331 // next sibling node. It may be either 332 // a leaf or branch. 333 while (sibling == null) { 334 /*if (debug) { 335 out("no siblings at level["+next.level+"], moving to parent"); 336 }*/ 337 next = next.parent; 338 if (next == null) { 339 break; 340 } 341 sibling = next.next_sibling(); 342 } 343 next = sibling; 344 return next; 345 } 346 QBLevel firstChild() 347 { 348 QBLevel ret = null; 349 for (QBLevel child : getChildren()) { 350 if (child == null) { 351 continue; 352 } 353 ret = child; 354 break; 355 } 356 return ret; 357 } 358 QBLevel nextNode() 359 { 360 if (!this.hasChildren()) 361 return this.nextSibling(); 362 return this.firstChild(); 363 } 364 QBLevel nextContentNode() 365 { 366 QBLevel next = this.nextNode(); 367 if (next == null) 368 return next; 369 if (next.hasContent()) 370 return next; 371 return next.nextContentNode(); 372 } 373 374 void doAdd(T o) { 375 if (consistency_testing) { 376 if (!matches(o, this.bbox())) { 377 /*out("-----------------------------"); 378 debug = true;*/ 379 get_index(o.getBBox(), level); 380 get_index(o.getBBox(), level-1); 381 int nr = 0; 382 /*for (QBLevel sibling : parent.getChildren()) { 383 out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling)); 384 }*/ 385 abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox()); 386 } 387 } 388 __add_content(o); 389 if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) { 390 __split(); 391 } 392 } 393 394 void add(T o) { 395 findBucket(o.getBBox()).doAdd(o); 396 } 397 398 private void search(BBox search_bbox, List<T> result) 399 { 400 /*if (debug) { 401 System.out.print("[" + level + "] qb bbox: " + this.bbox() + " "); 402 }*/ 403 if (!this.bbox().intersects(search_bbox)) 404 /*if (debug) { 405 out("miss " + Long.toHexString(this.quad)); 406 //QuadTiling.tile2xy(this.quad); 407 }*/ 408 return; 409 else if (bbox().bounds(search_bbox)) { 410 search_cache = this; 411 } 412 413 if (this.hasContent()) { 414 search_contents(search_bbox, result); 415 } 416 417 /*if (debug) { 418 out("hit " + this.quads()); 419 out("[" + level + "] not leaf, moving down"); 420 }*/ 421 422 //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked 423 424 if (nw != null) { 425 nw.search(search_bbox, result); 426 } 427 if (ne != null) { 428 ne.search(search_bbox, result); 429 } 430 if (se != null) { 431 se.search(search_bbox, result); 432 } 433 if (sw != null) { 434 sw.search(search_bbox, result); 435 } 436 } 437 public String quads() 438 { 439 return Long.toHexString(quad); 440 } 441 int index_of(QBLevel find_this) 442 { 443 QBLevel[] children = getChildren(); 444 for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) { 445 if (children[i] == find_this) 446 return i; 447 } 448 return -1; 449 } 450 double width() { 451 return bbox.width(); 452 } 453 454 double height() { 455 return bbox.height(); 456 } 457 458 public BBox bbox() { 459 return bbox; 460 } 461 /* 462 * This gives the coordinate of the bottom-left 463 * corner of the box 464 */ 465 LatLon coor() 466 { 467 return QuadTiling.tile2LatLon(this.quad); 468 } 469 void remove_from_parent() 470 { 471 if (parent == null) 472 return; 473 474 if (!canRemove()) { 475 abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren())); 476 } 477 478 if (parent.nw == this) { 479 parent.nw = null; 480 } else if (parent.ne == this) { 481 parent.ne = null; 482 } else if (parent.sw == this) { 483 parent.sw = null; 484 } else if (parent.se == this) { 485 parent.se = null; 486 } 487 488 if (parent.canRemove()) { 489 parent.remove_from_parent(); 490 } 491 } 492 boolean canRemove() 493 { 494 if (content != null && content.size() > 0) 495 return false; 496 if (this.hasChildren()) 497 return false; 498 return true; 499 } 500 } 501 502 private QBLevel root; 503 private QBLevel search_cache; 504 private int size; 505 506 public QuadBuckets() 507 { 508 clear(); 509 } 510 public void clear() { 511 root = new QBLevel(); 512 search_cache = null; 513 size = 0; 514 /*if (debug) { 515 out("QuadBuckets() cleared: " + this); 516 out("root: " + root + " level: " + root.level + " bbox: " + root.bbox()); 517 }*/ 518 } 519 public boolean add(T n) { 520 root.add(n); 521 size++; 522 return true; 523 } 524 525 public boolean retainAll(Collection<?> objects) 526 { 527 for (T o : this) { 528 if (objects.contains(o)) { 529 continue; 530 } 531 if (!this.remove(o)) 532 return false; 533 } 534 return true; 535 } 536 public boolean removeAll(Collection<?> objects) 537 { 538 boolean changed = false; 539 for (Object o : objects) { 540 changed = changed | remove(o); 541 } 542 return changed; 543 } 544 public boolean addAll(Collection<? extends T> objects) 545 { 546 boolean changed = false; 547 for (T o : objects) { 548 changed = changed | this.add(o); 549 } 550 return changed; 551 } 552 public boolean containsAll(Collection<?> objects) 553 { 554 for (Object o : objects) { 555 if (!this.contains(o)) 556 return false; 557 } 558 return true; 559 } 560 public boolean remove(Object o) { 561 @SuppressWarnings("unchecked") T t = (T) o; 562 search_cache = null; // Search cache might point to one of removed buckets 563 QBLevel bucket = root.findBucket(t.getBBox()); 564 if (bucket.remove_content(t)) { 565 size--; 566 return true; 567 } else 568 return false; 569 } 570 public boolean contains(Object o) { 571 @SuppressWarnings("unchecked") T t = (T) o; 572 QBLevel bucket = root.findBucket(t.getBBox()); 573 return bucket != null && bucket.content != null && bucket.content.contains(t); 574 } 575 576 public ArrayList<T> toArrayList() 577 { 578 ArrayList<T> a = new ArrayList<T>(); 579 for (T n : this) { 580 a.add(n); 581 } 582 /*if (debug) { 583 out("returning array list with size: " + a.size()); 584 }*/ 585 return a; 586 } 587 public Object[] toArray() 588 { 589 return this.toArrayList().toArray(); 590 } 591 public <A> A[] toArray(A[] template) 592 { 593 return this.toArrayList().toArray(template); 594 } 595 class QuadBucketIterator implements Iterator<T> 596 { 597 QBLevel current_node; 598 int content_index; 599 int iterated_over; 600 QBLevel next_content_node(QBLevel q) 601 { 602 if (q == null) 603 return null; 604 QBLevel orig = q; 605 QBLevel next; 606 next = q.nextContentNode(); 607 //if (consistency_testing && (orig == next)) 608 if (orig == next) { 609 abort("got same leaf back leaf: " + q.isLeaf()); 610 } 611 return next; 612 } 613 public QuadBucketIterator(QuadBuckets<T> qb) 614 { 615 /*if (debug) { 616 out(this + " is a new iterator qb: " + qb + " size: " + qb.size()); 617 }*/ 618 if (!qb.root.hasChildren() || qb.root.hasContent()) { 619 current_node = qb.root; 620 } else { 621 current_node = next_content_node(qb.root); 622 } 623 /*if (debug) { 624 out("\titerator first leaf: " + current_node); 625 }*/ 626 iterated_over = 0; 627 } 628 public boolean hasNext() 629 { 630 if (this.peek() == null) 631 /*if (debug) { 632 out(this + " no hasNext(), but iterated over so far: " + iterated_over); 633 }*/ 634 return false; 635 return true; 636 } 637 T peek() 638 { 639 if (current_node == null) 640 /*if (debug) { 641 out("null current leaf, nowhere to go"); 642 }*/ 643 return null; 644 while((current_node.content == null) || 645 (content_index >= current_node.content.size())) { 646 /*if (debug) { 647 out("moving to next leaf"); 648 }*/ 649 content_index = 0; 650 current_node = next_content_node(current_node); 651 if (current_node == null) { 652 break; 653 } 654 } 655 if (current_node == null || current_node.content == null) 656 /*if (debug) { 657 out("late nowhere to go " + current_node); 658 }*/ 659 return null; 660 return current_node.content.get(content_index); 661 } 662 public T next() 663 { 664 T ret = peek(); 665 content_index++; 666 /*if (debug) { 667 out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node); 668 }*/ 669 iterated_over++; 670 if (ret == null) { 671 /*if (debug) { 672 out(this + " no next node, but iterated over so far: " + iterated_over); 673 }*/ 674 } 675 return ret; 676 } 677 public void remove() 678 { 679 // two uses 680 // 1. Back up to the thing we just returned 681 // 2. move the index back since we removed 682 // an element 683 content_index--; 684 T object = peek(); 685 current_node.remove_content(object); 686 } 687 } 688 public Iterator<T> iterator() 689 { 690 return new QuadBucketIterator(this); 691 } 692 public int size() { 693 return size; 694 } 695 696 public boolean isEmpty() 697 { 698 if (this.size() == 0) 699 return true; 700 return false; 701 } 702 public List<T> search(BBox search_bbox) { 703 /*if (debug) { 704 out("qb root search at " + search_bbox); 705 out("root bbox: " + root.bbox()); 706 }*/ 707 List<T> ret = new ArrayList<T>(); 708 // Doing this cuts down search cost on a real-life data 709 // set by about 25% 710 boolean cache_searches = true; 711 if (cache_searches) { 712 if (search_cache == null) { 713 search_cache = root; 714 } 715 // Walk back up the tree when the last 716 // search spot can not cover the current 717 // search 718 while (search_cache != null && !search_cache.bbox().bounds(search_bbox)) { 719 /*if (debug) { 720 out("bbox: " + search_bbox); 721 out("search_cache: " + search_cache + " level: " + search_cache.level); 722 out("search_cache.bbox(): " + search_cache.bbox()); 723 }*/ 724 search_cache = search_cache.parent; 725 /*if (debug) { 726 out("new search_cache: " + search_cache); 727 }*/ 728 } 729 730 if (search_cache == null) { 731 search_cache = root; 732 out("bbox: " + search_bbox + " is out of the world"); 733 } 734 } else { 735 search_cache = root; 736 } 737 738 // Save parent because search_cache might change during search call 739 QBLevel tmp = search_cache.parent; 740 741 search_cache.search(search_bbox, ret); 742 743 // A way that spans this bucket may be stored in one 744 // of the nodes which is a parent of the search cache 745 while (tmp != null) { 746 tmp.search_contents(search_bbox, ret); 747 tmp = tmp.parent; 748 } 749 /*if (debug) { 750 out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size()); 751 }*/ 752 return ret; 753 } 754 755 public void printTree() { 756 printTreeRecursive(root, 0); 757 } 758 759 private void printTreeRecursive(QBLevel level, int indent) { 760 if (level == null) { 761 printIndented(indent, "<empty child>"); 762 return; 763 } 764 printIndented(indent, level); 765 if (level.hasContent()) { 766 for (T o:level.content) { 767 printIndented(indent, o); 768 } 769 } 770 for (QBLevel child:level.getChildren()) { 771 printTreeRecursive(child, indent + 2); 772 } 773 } 774 775 private void printIndented(int indent, Object msg) { 776 for (int i=0; i<indent; i++) { 777 System.out.print(' '); 778 } 779 System.out.println(msg); 780 } 781 }