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