[3719] | 1 | // License: GPL. For details, see LICENSE file.
|
---|
[2165] | 2 | package org.openstreetmap.josm.data.osm;
|
---|
[2427] | 3 |
|
---|
[2165] | 4 | import java.util.ArrayList;
|
---|
[2420] | 5 | import java.util.Arrays;
|
---|
[2165] | 6 | import java.util.Collection;
|
---|
[2388] | 7 | import java.util.Iterator;
|
---|
| 8 | import java.util.List;
|
---|
[2165] | 9 |
|
---|
[6171] | 10 | import org.openstreetmap.josm.Main;
|
---|
[2388] | 11 | import org.openstreetmap.josm.data.coor.LatLon;
|
---|
[2165] | 12 | import org.openstreetmap.josm.data.coor.QuadTiling;
|
---|
| 13 |
|
---|
[3154] | 14 | /**
|
---|
| 15 | * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must
|
---|
| 16 | * be removed and readded.
|
---|
| 17 | *
|
---|
[3584] | 18 | * This class is (no longer) thread safe.
|
---|
| 19 | *
|
---|
[3154] | 20 | */
|
---|
[6178] | 21 | public class QuadBuckets<T extends OsmPrimitive> implements Collection<T> {
|
---|
[2896] | 22 | private static final boolean consistency_testing = false;
|
---|
[3476] | 23 | private static final int NW_INDEX = 1;
|
---|
| 24 | private static final int NE_INDEX = 3;
|
---|
| 25 | private static final int SE_INDEX = 2;
|
---|
| 26 | private static final int SW_INDEX = 0;
|
---|
[2165] | 27 |
|
---|
[6171] | 28 | static void abort(String s) {
|
---|
[2420] | 29 | throw new AssertionError(s);
|
---|
[2165] | 30 | }
|
---|
| 31 |
|
---|
[4869] | 32 | public static final int MAX_OBJECTS_PER_LEVEL = 16;
|
---|
[6178] | 33 |
|
---|
| 34 | static class QBLevel<T extends OsmPrimitive> {
|
---|
| 35 | private final int level;
|
---|
| 36 | private final int index;
|
---|
[3145] | 37 | private final BBox bbox;
|
---|
[6178] | 38 | private final long quad;
|
---|
| 39 | private final QBLevel<T> parent;
|
---|
[3476] | 40 | private boolean isLeaf = true;
|
---|
[2165] | 41 |
|
---|
[6178] | 42 | private List<T> content;
|
---|
| 43 | // child order by index is sw, nw, se, ne
|
---|
| 44 | private QBLevel<T> nw, ne, sw, se;
|
---|
[3476] | 45 |
|
---|
[6178] | 46 | private final QuadBuckets<T> buckets;
|
---|
| 47 |
|
---|
| 48 | private QBLevel<T> getChild(int index) {
|
---|
[3476] | 49 | switch (index) {
|
---|
| 50 | case NE_INDEX:
|
---|
| 51 | if (ne == null) {
|
---|
[6178] | 52 | ne = new QBLevel<T>(this, index, buckets);
|
---|
[3476] | 53 | }
|
---|
| 54 | return ne;
|
---|
| 55 | case NW_INDEX:
|
---|
| 56 | if (nw == null) {
|
---|
[6178] | 57 | nw = new QBLevel<T>(this, index, buckets);
|
---|
[3476] | 58 | }
|
---|
| 59 | return nw;
|
---|
| 60 | case SE_INDEX:
|
---|
| 61 | if (se == null) {
|
---|
[6178] | 62 | se = new QBLevel<T>(this, index, buckets);
|
---|
[3476] | 63 | }
|
---|
| 64 | return se;
|
---|
| 65 | case SW_INDEX:
|
---|
| 66 | if (sw == null) {
|
---|
[6178] | 67 | sw = new QBLevel<T>(this, index, buckets);
|
---|
[3476] | 68 | }
|
---|
| 69 | return sw;
|
---|
| 70 | default:
|
---|
| 71 | return null;
|
---|
| 72 | }
|
---|
| 73 | }
|
---|
| 74 |
|
---|
[6178] | 75 | @SuppressWarnings("unchecked")
|
---|
| 76 | private QBLevel<T>[] getChildren() {
|
---|
| 77 | return new QBLevel[] {sw, nw, se, ne};
|
---|
[3476] | 78 | }
|
---|
| 79 |
|
---|
[2388] | 80 | @Override
|
---|
[6178] | 81 | public String toString() {
|
---|
| 82 | return super.toString() + "[" + level + "]: " + bbox();
|
---|
[2263] | 83 | }
|
---|
[6178] | 84 |
|
---|
[3145] | 85 | /**
|
---|
| 86 | * Constructor for root node
|
---|
| 87 | */
|
---|
[6178] | 88 | public QBLevel(final QuadBuckets<T> buckets) {
|
---|
[3145] | 89 | level = 0;
|
---|
[6178] | 90 | index = 0;
|
---|
[3145] | 91 | quad = 0;
|
---|
| 92 | parent = null;
|
---|
| 93 | bbox = new BBox(-180, 90, 180, -90);
|
---|
[6178] | 94 | this.buckets = buckets;
|
---|
[2165] | 95 | }
|
---|
[3145] | 96 |
|
---|
[6178] | 97 | public QBLevel(QBLevel<T> parent, int parent_index, final QuadBuckets<T> buckets) {
|
---|
[3145] | 98 | this.parent = parent;
|
---|
| 99 | this.level = parent.level + 1;
|
---|
[6178] | 100 | this.index = parent_index;
|
---|
| 101 | this.buckets = buckets;
|
---|
| 102 |
|
---|
[3150] | 103 | int shift = (QuadTiling.NR_LEVELS - level) * 2;
|
---|
[3145] | 104 | long mult = 1;
|
---|
[6171] | 105 | // Java blows the big one. It seems to wrap when you shift by > 31
|
---|
[3145] | 106 | if (shift >= 30) {
|
---|
| 107 | shift -= 30;
|
---|
[6178] | 108 | mult = 1 << 30;
|
---|
[3145] | 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;
|
---|
[6203] | 119 | return new BBox(bottom_left.lon(), bottom_left.lat(), lon, lat);
|
---|
[3145] | 120 | }
|
---|
| 121 |
|
---|
[6178] | 122 | QBLevel<T> findBucket(BBox bbox) {
|
---|
[3603] | 123 | if (!hasChildren())
|
---|
[3150] | 124 | return this;
|
---|
| 125 | else {
|
---|
[6171] | 126 | int index = bbox.getIndex(level);
|
---|
[3150] | 127 | if (index == -1)
|
---|
| 128 | return this;
|
---|
[3476] | 129 | return getChild(index).findBucket(bbox);
|
---|
[3150] | 130 | }
|
---|
| 131 | }
|
---|
| 132 |
|
---|
[6171] | 133 | boolean remove_content(T o) {
|
---|
[3584] | 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);
|
---|
[6093] | 142 | if (this.content.isEmpty()) {
|
---|
[3584] | 143 | this.content = null;
|
---|
[2388] | 144 | }
|
---|
[3584] | 145 | if (this.canRemove()) {
|
---|
| 146 | this.remove_from_parent();
|
---|
| 147 | }
|
---|
| 148 | return ret;
|
---|
[2263] | 149 | }
|
---|
[6171] | 150 |
|
---|
[2440] | 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 | */
|
---|
[3150] | 157 | void __split() {
|
---|
[2263] | 158 | List<T> tmpcontent = content;
|
---|
[2165] | 159 | content = null;
|
---|
[3476] | 160 |
|
---|
[6178] | 161 | for (T o : tmpcontent) {
|
---|
[6171] | 162 | int index = o.getBBox().getIndex(level);
|
---|
[3476] | 163 | if (index == -1) {
|
---|
| 164 | __add_content(o);
|
---|
| 165 | } else {
|
---|
| 166 | getChild(index).doAdd(o);
|
---|
| 167 | }
|
---|
[2165] | 168 | }
|
---|
[3476] | 169 | isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1)
|
---|
[2440] | 170 | }
|
---|
[3150] | 171 |
|
---|
[6171] | 172 | boolean __add_content(T o) {
|
---|
[2263] | 173 | boolean ret = false;
|
---|
[6171] | 174 | // The split_lock will keep two concurrent calls from overwriting content
|
---|
[2388] | 175 | if (content == null) {
|
---|
[2380] | 176 | content = new ArrayList<T>();
|
---|
[2388] | 177 | }
|
---|
[2263] | 178 | ret = content.add(o);
|
---|
| 179 | return ret;
|
---|
| 180 | }
|
---|
[6178] | 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 | }
|
---|
[2427] | 188 | return o.getBBox().intersects(search_bbox);
|
---|
[2165] | 189 | }
|
---|
[6178] | 190 |
|
---|
[6171] | 191 | private void search_contents(BBox search_bbox, List<T> result) {
|
---|
[2165] | 192 | /*
|
---|
| 193 | * It is possible that this was created in a split
|
---|
| 194 | * but never got any content populated.
|
---|
| 195 | */
|
---|
| 196 | if (content == null)
|
---|
[3151] | 197 | return;
|
---|
| 198 |
|
---|
[2263] | 199 | for (T o : content) {
|
---|
[2388] | 200 | if (matches(o, search_bbox)) {
|
---|
[3151] | 201 | result.add(o);
|
---|
[2388] | 202 | }
|
---|
[2165] | 203 | }
|
---|
| 204 | }
|
---|
[6178] | 205 |
|
---|
[2165] | 206 | /*
|
---|
[6171] | 207 | * This is stupid. I tried to have a QBLeaf and QBBranch
|
---|
[6178] | 208 | * class descending from a QBLevel. It's more than twice
|
---|
[6171] | 209 | * as slow. So, this throws OO out the window, but it
|
---|
| 210 | * is fast. Runtime type determination must be slow.
|
---|
[2165] | 211 | */
|
---|
[3476] | 212 | boolean isLeaf() {
|
---|
| 213 | return isLeaf;
|
---|
[2165] | 214 | }
|
---|
[6178] | 215 |
|
---|
[3476] | 216 | boolean hasChildren() {
|
---|
[6181] | 217 | return nw != null || ne != null || sw != null || se != null;
|
---|
[3476] | 218 | }
|
---|
| 219 |
|
---|
[6178] | 220 | QBLevel<T> next_sibling() {
|
---|
| 221 | return (parent == null) ? null : parent.firstSiblingOf(this);
|
---|
[2165] | 222 | }
|
---|
[6178] | 223 |
|
---|
[6171] | 224 | boolean hasContent() {
|
---|
[2441] | 225 | return content != null;
|
---|
[2263] | 226 | }
|
---|
[6178] | 227 |
|
---|
| 228 | QBLevel<T> nextSibling() {
|
---|
| 229 | QBLevel<T> next = this;
|
---|
| 230 | QBLevel<T> sibling = next.next_sibling();
|
---|
[2423] | 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;
|
---|
[2427] | 238 | }
|
---|
[2423] | 239 | sibling = next.next_sibling();
|
---|
[2165] | 240 | }
|
---|
[2423] | 241 | next = sibling;
|
---|
| 242 | return next;
|
---|
| 243 | }
|
---|
[6178] | 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;
|
---|
[2440] | 265 | }
|
---|
[6178] | 266 | return null;
|
---|
[2440] | 267 | }
|
---|
[6178] | 268 |
|
---|
| 269 | QBLevel<T> nextNode() {
|
---|
[3603] | 270 | if (!this.hasChildren())
|
---|
[2449] | 271 | return this.nextSibling();
|
---|
| 272 | return this.firstChild();
|
---|
| 273 | }
|
---|
[6178] | 274 |
|
---|
| 275 | QBLevel<T> nextContentNode() {
|
---|
| 276 | QBLevel<T> next = this.nextNode();
|
---|
[2165] | 277 | if (next == null)
|
---|
[2449] | 278 | return next;
|
---|
| 279 | if (next.hasContent())
|
---|
| 280 | return next;
|
---|
| 281 | return next.nextContentNode();
|
---|
[2165] | 282 | }
|
---|
[3150] | 283 |
|
---|
| 284 | void doAdd(T o) {
|
---|
[2263] | 285 | if (consistency_testing) {
|
---|
[3150] | 286 | if (!matches(o, this.bbox())) {
|
---|
[6171] | 287 | o.getBBox().getIndex(level);
|
---|
[6178] | 288 | o.getBBox().getIndex(level - 1);
|
---|
[2442] | 289 | int nr = 0;
|
---|
[3150] | 290 | abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
|
---|
[2263] | 291 | }
|
---|
| 292 | }
|
---|
[3584] | 293 | __add_content(o);
|
---|
| 294 | if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) {
|
---|
| 295 | __split();
|
---|
[2388] | 296 | }
|
---|
[2165] | 297 | }
|
---|
[3150] | 298 |
|
---|
| 299 | void add(T o) {
|
---|
[3584] | 300 | findBucket(o.getBBox()).doAdd(o);
|
---|
[2165] | 301 | }
|
---|
[3150] | 302 |
|
---|
[6171] | 303 | private void search(BBox search_bbox, List<T> result) {
|
---|
[4869] | 304 | if (!this.bbox().intersects(search_bbox))
|
---|
[3151] | 305 | return;
|
---|
[4869] | 306 | else if (bbox().bounds(search_bbox)) {
|
---|
[6178] | 307 | buckets.search_cache = this;
|
---|
[2165] | 308 | }
|
---|
[3476] | 309 |
|
---|
[2388] | 310 | if (this.hasContent()) {
|
---|
[3151] | 311 | search_contents(search_bbox, result);
|
---|
[2388] | 312 | }
|
---|
[3151] | 313 |
|
---|
[3476] | 314 | //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
|
---|
| 315 |
|
---|
| 316 | if (nw != null) {
|
---|
| 317 | nw.search(search_bbox, result);
|
---|
[2165] | 318 | }
|
---|
[3476] | 319 | if (ne != null) {
|
---|
| 320 | ne.search(search_bbox, result);
|
---|
| 321 | }
|
---|
| 322 | if (se != null) {
|
---|
| 323 | se.search(search_bbox, result);
|
---|
| 324 | }
|
---|
| 325 | if (sw != null) {
|
---|
| 326 | sw.search(search_bbox, result);
|
---|
| 327 | }
|
---|
[2165] | 328 | }
|
---|
[6178] | 329 |
|
---|
[6171] | 330 | public String quads() {
|
---|
[2165] | 331 | return Long.toHexString(quad);
|
---|
| 332 | }
|
---|
[6178] | 333 |
|
---|
| 334 | int index_of(QBLevel<T> find_this) {
|
---|
| 335 | QBLevel<T>[] children = getChildren();
|
---|
[2165] | 336 | for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
|
---|
| 337 | if (children[i] == find_this)
|
---|
| 338 | return i;
|
---|
| 339 | }
|
---|
| 340 | return -1;
|
---|
| 341 | }
|
---|
[6178] | 342 |
|
---|
[3145] | 343 | double width() {
|
---|
| 344 | return bbox.width();
|
---|
[2165] | 345 | }
|
---|
[3145] | 346 |
|
---|
| 347 | double height() {
|
---|
| 348 | return bbox.height();
|
---|
[2165] | 349 | }
|
---|
[3145] | 350 |
|
---|
| 351 | public BBox bbox() {
|
---|
[2165] | 352 | return bbox;
|
---|
| 353 | }
|
---|
[6178] | 354 |
|
---|
[2165] | 355 | /*
|
---|
| 356 | * This gives the coordinate of the bottom-left
|
---|
| 357 | * corner of the box
|
---|
| 358 | */
|
---|
[6171] | 359 | LatLon coor() {
|
---|
[2165] | 360 | return QuadTiling.tile2LatLon(this.quad);
|
---|
| 361 | }
|
---|
[6178] | 362 |
|
---|
[6171] | 363 | void remove_from_parent() {
|
---|
[2423] | 364 | if (parent == null)
|
---|
| 365 | return;
|
---|
| 366 |
|
---|
[3476] | 367 | if (!canRemove()) {
|
---|
| 368 | abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren()));
|
---|
[2423] | 369 | }
|
---|
[3476] | 370 |
|
---|
| 371 | if (parent.nw == this) {
|
---|
| 372 | parent.nw = null;
|
---|
| 373 | } else if (parent.ne == this) {
|
---|
| 374 | parent.ne = null;
|
---|
| 375 | } else if (parent.sw == this) {
|
---|
| 376 | parent.sw = null;
|
---|
| 377 | } else if (parent.se == this) {
|
---|
| 378 | parent.se = null;
|
---|
[2911] | 379 | }
|
---|
[3476] | 380 |
|
---|
[2427] | 381 | if (parent.canRemove()) {
|
---|
[2423] | 382 | parent.remove_from_parent();
|
---|
[2427] | 383 | }
|
---|
[2423] | 384 | }
|
---|
[6178] | 385 |
|
---|
[6171] | 386 | boolean canRemove() {
|
---|
[6093] | 387 | if (content != null && !content.isEmpty())
|
---|
[2423] | 388 | return false;
|
---|
[2425] | 389 | if (this.hasChildren())
|
---|
| 390 | return false;
|
---|
[2423] | 391 | return true;
|
---|
| 392 | }
|
---|
[2165] | 393 | }
|
---|
| 394 |
|
---|
[6178] | 395 | private QBLevel<T> root;
|
---|
| 396 | private QBLevel<T> search_cache;
|
---|
[3157] | 397 | private int size;
|
---|
| 398 |
|
---|
[6171] | 399 | /**
|
---|
| 400 | * Constructs a new {@code QuadBuckets}.
|
---|
| 401 | */
|
---|
| 402 | public QuadBuckets() {
|
---|
[2165] | 403 | clear();
|
---|
| 404 | }
|
---|
[6178] | 405 |
|
---|
[6084] | 406 | @Override
|
---|
[6178] | 407 | public void clear() {
|
---|
| 408 | root = new QBLevel<T>(this);
|
---|
[3584] | 409 | search_cache = null;
|
---|
| 410 | size = 0;
|
---|
[2165] | 411 | }
|
---|
[6178] | 412 |
|
---|
[6084] | 413 | @Override
|
---|
[3157] | 414 | public boolean add(T n) {
|
---|
[3584] | 415 | root.add(n);
|
---|
| 416 | size++;
|
---|
| 417 | return true;
|
---|
[2165] | 418 | }
|
---|
[3584] | 419 |
|
---|
[6084] | 420 | @Override
|
---|
[6171] | 421 | public boolean retainAll(Collection<?> objects) {
|
---|
[2263] | 422 | for (T o : this) {
|
---|
[2388] | 423 | if (objects.contains(o)) {
|
---|
[2197] | 424 | continue;
|
---|
[2388] | 425 | }
|
---|
[2263] | 426 | if (!this.remove(o))
|
---|
[2197] | 427 | return false;
|
---|
| 428 | }
|
---|
| 429 | return true;
|
---|
[2165] | 430 | }
|
---|
[6178] | 431 |
|
---|
[6084] | 432 | @Override
|
---|
[6171] | 433 | public boolean removeAll(Collection<?> objects) {
|
---|
[2427] | 434 | boolean changed = false;
|
---|
[2263] | 435 | for (Object o : objects) {
|
---|
[2427] | 436 | changed = changed | remove(o);
|
---|
[2197] | 437 | }
|
---|
[2427] | 438 | return changed;
|
---|
[2165] | 439 | }
|
---|
[6178] | 440 |
|
---|
[6084] | 441 | @Override
|
---|
[6171] | 442 | public boolean addAll(Collection<? extends T> objects) {
|
---|
[2427] | 443 | boolean changed = false;
|
---|
[3154] | 444 | for (T o : objects) {
|
---|
| 445 | changed = changed | this.add(o);
|
---|
[2197] | 446 | }
|
---|
[2427] | 447 | return changed;
|
---|
[2165] | 448 | }
|
---|
[6178] | 449 |
|
---|
[6084] | 450 | @Override
|
---|
[6171] | 451 | public boolean containsAll(Collection<?> objects) {
|
---|
[2263] | 452 | for (Object o : objects) {
|
---|
| 453 | if (!this.contains(o))
|
---|
[2197] | 454 | return false;
|
---|
| 455 | }
|
---|
| 456 | return true;
|
---|
[2165] | 457 | }
|
---|
[6178] | 458 |
|
---|
[6084] | 459 | @Override
|
---|
[3157] | 460 | public boolean remove(Object o) {
|
---|
[6178] | 461 | @SuppressWarnings("unchecked")
|
---|
| 462 | T t = (T) o;
|
---|
[3584] | 463 | search_cache = null; // Search cache might point to one of removed buckets
|
---|
[6178] | 464 | QBLevel<T> bucket = root.findBucket(t.getBBox());
|
---|
[3584] | 465 | if (bucket.remove_content(t)) {
|
---|
| 466 | size--;
|
---|
| 467 | return true;
|
---|
| 468 | } else
|
---|
| 469 | return false;
|
---|
[2165] | 470 | }
|
---|
[6178] | 471 |
|
---|
[6084] | 472 | @Override
|
---|
[3154] | 473 | public boolean contains(Object o) {
|
---|
[6178] | 474 | @SuppressWarnings("unchecked")
|
---|
| 475 | T t = (T) o;
|
---|
| 476 | QBLevel<T> bucket = root.findBucket(t.getBBox());
|
---|
[3453] | 477 | return bucket != null && bucket.content != null && bucket.content.contains(t);
|
---|
[2165] | 478 | }
|
---|
[3154] | 479 |
|
---|
[6171] | 480 | public ArrayList<T> toArrayList() {
|
---|
[2263] | 481 | ArrayList<T> a = new ArrayList<T>();
|
---|
[2388] | 482 | for (T n : this) {
|
---|
[2165] | 483 | a.add(n);
|
---|
[2388] | 484 | }
|
---|
[2165] | 485 | return a;
|
---|
| 486 | }
|
---|
[6178] | 487 |
|
---|
[6084] | 488 | @Override
|
---|
[6171] | 489 | public Object[] toArray() {
|
---|
[2165] | 490 | return this.toArrayList().toArray();
|
---|
| 491 | }
|
---|
[6178] | 492 |
|
---|
[6084] | 493 | @Override
|
---|
[6171] | 494 | public <A> A[] toArray(A[] template) {
|
---|
[2165] | 495 | return this.toArrayList().toArray(template);
|
---|
| 496 | }
|
---|
[6178] | 497 |
|
---|
| 498 | class QuadBucketIterator implements Iterator<T> {
|
---|
| 499 | QBLevel<T> current_node;
|
---|
[2263] | 500 | int content_index;
|
---|
[2165] | 501 | int iterated_over;
|
---|
[6178] | 502 |
|
---|
| 503 | QBLevel<T> next_content_node(QBLevel<T> q) {
|
---|
[2165] | 504 | if (q == null)
|
---|
| 505 | return null;
|
---|
[6178] | 506 | QBLevel<T> orig = q;
|
---|
| 507 | QBLevel<T> next;
|
---|
[3584] | 508 | next = q.nextContentNode();
|
---|
[2263] | 509 | //if (consistency_testing && (orig == next))
|
---|
[2388] | 510 | if (orig == next) {
|
---|
[2165] | 511 | abort("got same leaf back leaf: " + q.isLeaf());
|
---|
[2388] | 512 | }
|
---|
[2165] | 513 | return next;
|
---|
| 514 | }
|
---|
[6178] | 515 |
|
---|
[6171] | 516 | public QuadBucketIterator(QuadBuckets<T> qb) {
|
---|
[3603] | 517 | if (!qb.root.hasChildren() || qb.root.hasContent()) {
|
---|
[2263] | 518 | current_node = qb.root;
|
---|
[2388] | 519 | } else {
|
---|
[2263] | 520 | current_node = next_content_node(qb.root);
|
---|
[2388] | 521 | }
|
---|
[2165] | 522 | iterated_over = 0;
|
---|
| 523 | }
|
---|
[6178] | 524 |
|
---|
[6084] | 525 | @Override
|
---|
[6171] | 526 | public boolean hasNext() {
|
---|
[4869] | 527 | if (this.peek() == null)
|
---|
[2165] | 528 | return false;
|
---|
| 529 | return true;
|
---|
| 530 | }
|
---|
[6178] | 531 |
|
---|
[6171] | 532 | T peek() {
|
---|
[4869] | 533 | if (current_node == null)
|
---|
[2165] | 534 | return null;
|
---|
[6178] | 535 | while ((current_node.content == null) || (content_index >= current_node.content.size())) {
|
---|
[2263] | 536 | content_index = 0;
|
---|
| 537 | current_node = next_content_node(current_node);
|
---|
[2388] | 538 | if (current_node == null) {
|
---|
[2165] | 539 | break;
|
---|
[2388] | 540 | }
|
---|
[2165] | 541 | }
|
---|
[4869] | 542 | if (current_node == null || current_node.content == null)
|
---|
[2165] | 543 | return null;
|
---|
[2263] | 544 | return current_node.content.get(content_index);
|
---|
[2165] | 545 | }
|
---|
[6178] | 546 |
|
---|
[6084] | 547 | @Override
|
---|
[6171] | 548 | public T next() {
|
---|
[2263] | 549 | T ret = peek();
|
---|
| 550 | content_index++;
|
---|
[2165] | 551 | iterated_over++;
|
---|
| 552 | return ret;
|
---|
| 553 | }
|
---|
[6178] | 554 |
|
---|
[6084] | 555 | @Override
|
---|
[6171] | 556 | public void remove() {
|
---|
[2197] | 557 | // two uses
|
---|
| 558 | // 1. Back up to the thing we just returned
|
---|
| 559 | // 2. move the index back since we removed
|
---|
| 560 | // an element
|
---|
[2263] | 561 | content_index--;
|
---|
[3000] | 562 | T object = peek();
|
---|
[2423] | 563 | current_node.remove_content(object);
|
---|
[2165] | 564 | }
|
---|
| 565 | }
|
---|
[6178] | 566 |
|
---|
[6084] | 567 | @Override
|
---|
[6171] | 568 | public Iterator<T> iterator() {
|
---|
[2165] | 569 | return new QuadBucketIterator(this);
|
---|
| 570 | }
|
---|
[6171] | 571 |
|
---|
[6084] | 572 | @Override
|
---|
[3157] | 573 | public int size() {
|
---|
[3584] | 574 | return size;
|
---|
[2165] | 575 | }
|
---|
[3157] | 576 |
|
---|
[6084] | 577 | @Override
|
---|
[6171] | 578 | public boolean isEmpty() {
|
---|
[2165] | 579 | if (this.size() == 0)
|
---|
| 580 | return true;
|
---|
| 581 | return false;
|
---|
| 582 | }
|
---|
[6178] | 583 |
|
---|
[3151] | 584 | public List<T> search(BBox search_bbox) {
|
---|
| 585 | List<T> ret = new ArrayList<T>();
|
---|
[6171] | 586 | // Doing this cuts down search cost on a real-life data set by about 25%
|
---|
[2165] | 587 | boolean cache_searches = true;
|
---|
| 588 | if (cache_searches) {
|
---|
[2388] | 589 | if (search_cache == null) {
|
---|
[2165] | 590 | search_cache = root;
|
---|
[2388] | 591 | }
|
---|
[6171] | 592 | // Walk back up the tree when the last search spot can not cover the current search
|
---|
[4178] | 593 | while (search_cache != null && !search_cache.bbox().bounds(search_bbox)) {
|
---|
[2165] | 594 | search_cache = search_cache.parent;
|
---|
| 595 | }
|
---|
[4178] | 596 |
|
---|
| 597 | if (search_cache == null) {
|
---|
| 598 | search_cache = root;
|
---|
[6171] | 599 | Main.info("bbox: " + search_bbox + " is out of the world");
|
---|
[4178] | 600 | }
|
---|
[2165] | 601 | } else {
|
---|
| 602 | search_cache = root;
|
---|
| 603 | }
|
---|
[2441] | 604 |
|
---|
| 605 | // Save parent because search_cache might change during search call
|
---|
[6178] | 606 | QBLevel<T> tmp = search_cache.parent;
|
---|
[2441] | 607 |
|
---|
[3151] | 608 | search_cache.search(search_bbox, ret);
|
---|
[2441] | 609 |
|
---|
[2263] | 610 | // A way that spans this bucket may be stored in one
|
---|
| 611 | // of the nodes which is a parent of the search cache
|
---|
| 612 | while (tmp != null) {
|
---|
[3151] | 613 | tmp.search_contents(search_bbox, ret);
|
---|
[2263] | 614 | tmp = tmp.parent;
|
---|
| 615 | }
|
---|
| 616 | return ret;
|
---|
[2165] | 617 | }
|
---|
[2441] | 618 |
|
---|
| 619 | public void printTree() {
|
---|
| 620 | printTreeRecursive(root, 0);
|
---|
| 621 | }
|
---|
| 622 |
|
---|
[6178] | 623 | private void printTreeRecursive(QBLevel<T> level, int indent) {
|
---|
[2441] | 624 | if (level == null) {
|
---|
| 625 | printIndented(indent, "<empty child>");
|
---|
| 626 | return;
|
---|
| 627 | }
|
---|
| 628 | printIndented(indent, level);
|
---|
| 629 | if (level.hasContent()) {
|
---|
[6178] | 630 | for (T o : level.content) {
|
---|
[2441] | 631 | printIndented(indent, o);
|
---|
| 632 | }
|
---|
| 633 | }
|
---|
[6178] | 634 | for (QBLevel<T> child : level.getChildren()) {
|
---|
[3476] | 635 | printTreeRecursive(child, indent + 2);
|
---|
[2441] | 636 | }
|
---|
| 637 | }
|
---|
| 638 |
|
---|
| 639 | private void printIndented(int indent, Object msg) {
|
---|
[6178] | 640 | for (int i = 0; i < indent; i++) {
|
---|
[2441] | 641 | System.out.print(' ');
|
---|
| 642 | }
|
---|
| 643 | System.out.println(msg);
|
---|
| 644 | }
|
---|
[2165] | 645 | }
|
---|