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