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