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.Main;
013import org.openstreetmap.josm.data.coor.LatLon;
014import org.openstreetmap.josm.data.coor.QuadTiling;
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 OsmPrimitive> 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 OsmPrimitive> 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            case NW_INDEX:
244                if (se != null)
245                    return se;
246            case SE_INDEX:
247                return ne;
248            }
249            return null;
250        }
251
252        QBLevel<T> nextNode() {
253            if (!this.hasChildren())
254                return this.nextSibling();
255            return this.firstChild();
256        }
257
258        QBLevel<T> nextContentNode() {
259            QBLevel<T> next = this.nextNode();
260            if (next == null)
261                return next;
262            if (next.hasContent())
263                return next;
264            return next.nextContentNode();
265        }
266
267        void doAdd(T o) {
268            if (consistency_testing) {
269                if (o instanceof Node && !matches(o, this)) {
270                    o.getBBox().getIndex(level);
271                    o.getBBox().getIndex(level - 1);
272                    abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + super.toString());
273                }
274            }
275            doAddContent(o);
276            if (isLeaf() && content.size() > MAX_OBJECTS_PER_NODE && level < QuadTiling.NR_LEVELS) {
277                doSplit();
278            }
279        }
280
281        void add(T o) {
282            findBucket(o.getBBox()).doAdd(o);
283        }
284
285        private void search(QuadBuckets<T> buckets, BBox searchBbox, List<T> result) {
286            if (!this.intersects(searchBbox))
287                return;
288            else if (this.bounds(searchBbox)) {
289                buckets.searchCache = this;
290            }
291
292            if (this.hasContent()) {
293                searchContents(searchBbox, result);
294            }
295
296            //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
297
298            if (nw != null) {
299                nw.search(buckets, searchBbox, result);
300            }
301            if (ne != null) {
302                ne.search(buckets, searchBbox, result);
303            }
304            if (se != null) {
305                se.search(buckets, searchBbox, result);
306            }
307            if (sw != null) {
308                sw.search(buckets, searchBbox, result);
309            }
310        }
311
312        public String quads() {
313            return Long.toHexString(quad);
314        }
315
316        int indexOf(QBLevel<T> findThis) {
317            QBLevel<T>[] children = getChildren();
318            for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
319                if (children[i] == findThis) {
320                    return i;
321                }
322            }
323            return -1;
324        }
325
326        void removeFromParent() {
327            if (parent == null)
328                return;
329
330            if (!canRemove()) {
331                abort("attempt to remove non-empty child: " + this.content + ' ' + Arrays.toString(this.getChildren()));
332            }
333
334            if (parent.nw == this) {
335                parent.nw = null;
336            } else if (parent.ne == this) {
337                parent.ne = null;
338            } else if (parent.sw == this) {
339                parent.sw = null;
340            } else if (parent.se == this) {
341                parent.se = null;
342            }
343
344            if (parent.canRemove()) {
345                parent.removeFromParent();
346            }
347        }
348
349        boolean canRemove() {
350            return (content == null || content.isEmpty()) && !this.hasChildren();
351        }
352    }
353
354    private QBLevel<T> root;
355    private QBLevel<T> searchCache;
356    private int size;
357    private Collection<T> invalidBBoxPrimitives;
358
359    /**
360     * Constructs a new {@code QuadBuckets}.
361     */
362    public QuadBuckets() {
363        clear();
364    }
365
366    @Override
367    public final void clear() {
368        root = new QBLevel<>();
369        invalidBBoxPrimitives = new LinkedHashSet<>();
370        searchCache = null;
371        size = 0;
372    }
373
374    @Override
375    public boolean add(T n) {
376        if (n.getBBox().isValid()) {
377            root.add(n);
378        } else {
379            invalidBBoxPrimitives.add(n);
380        }
381        size++;
382        return true;
383    }
384
385    @Override
386    public boolean retainAll(Collection<?> objects) {
387        for (T o : this) {
388            if (objects.contains(o)) {
389                continue;
390            }
391            if (!this.remove(o)) {
392                return false;
393            }
394        }
395        return true;
396    }
397
398    @Override
399    public boolean removeAll(Collection<?> objects) {
400        boolean changed = false;
401        for (Object o : objects) {
402            changed = changed | remove(o);
403        }
404        return changed;
405    }
406
407    @Override
408    public boolean addAll(Collection<? extends T> objects) {
409        boolean changed = false;
410        for (T o : objects) {
411            changed = changed | this.add(o);
412        }
413        return changed;
414    }
415
416    @Override
417    public boolean containsAll(Collection<?> objects) {
418        for (Object o : objects) {
419            if (!this.contains(o)) {
420                return false;
421            }
422        }
423        return true;
424    }
425
426    @Override
427    public boolean remove(Object o) {
428        @SuppressWarnings("unchecked")
429        T t = (T) o;
430        searchCache = null; // Search cache might point to one of removed buckets
431        QBLevel<T> bucket = root.findBucket(t.getBBox());
432        boolean removed = bucket.removeContent(t);
433        if (!removed) {
434            removed = invalidBBoxPrimitives.remove(o);
435        }
436        if (removed) {
437            size--;
438        }
439        return removed;
440    }
441
442    @Override
443    public boolean contains(Object o) {
444        @SuppressWarnings("unchecked")
445        T t = (T) o;
446        if (!t.getBBox().isValid()) {
447            return invalidBBoxPrimitives.contains(o);
448        }
449        QBLevel<T> bucket = root.findBucket(t.getBBox());
450        return bucket != null && bucket.content != null && bucket.content.contains(t);
451    }
452
453    /**
454     * Converts to list.
455     * @return elements as list
456     */
457    public List<T> toList() {
458        List<T> a = new ArrayList<>();
459        for (T n : this) {
460            a.add(n);
461        }
462        return a;
463    }
464
465    @Override
466    public Object[] toArray() {
467        return this.toList().toArray();
468    }
469
470    @Override
471    public <A> A[] toArray(A[] template) {
472        return this.toList().toArray(template);
473    }
474
475    class QuadBucketIterator implements Iterator<T> {
476        private QBLevel<T> currentNode;
477        private int contentIndex;
478        private final Iterator<T> invalidBBoxIterator = invalidBBoxPrimitives.iterator();
479        boolean fromInvalidBBoxPrimitives;
480        QuadBuckets<T> qb;
481
482        final QBLevel<T> nextContentNode(QBLevel<T> q) {
483            if (q == null)
484                return null;
485            QBLevel<T> orig = q;
486            QBLevel<T> next;
487            next = q.nextContentNode();
488            if (orig == next) {
489                abort("got same leaf back leaf: " + q.isLeaf());
490            }
491            return next;
492        }
493
494        QuadBucketIterator(QuadBuckets<T> qb) {
495            if (!qb.root.hasChildren() || qb.root.hasContent()) {
496                currentNode = qb.root;
497            } else {
498                currentNode = nextContentNode(qb.root);
499            }
500            this.qb = qb;
501        }
502
503        @Override
504        public boolean hasNext() {
505            if (this.peek() == null) {
506                fromInvalidBBoxPrimitives = true;
507                return invalidBBoxIterator.hasNext();
508            }
509            return true;
510        }
511
512        T peek() {
513            if (currentNode == null)
514                return null;
515            while ((currentNode.content == null) || (contentIndex >= currentNode.content.size())) {
516                contentIndex = 0;
517                currentNode = nextContentNode(currentNode);
518                if (currentNode == null) {
519                    break;
520                }
521            }
522            if (currentNode == null || currentNode.content == null)
523                return null;
524            return currentNode.content.get(contentIndex);
525        }
526
527        @Override
528        public T next() {
529            if (fromInvalidBBoxPrimitives) {
530                return invalidBBoxIterator.next();
531            }
532            T ret = peek();
533            if (ret == null)
534                throw new NoSuchElementException();
535            contentIndex++;
536            return ret;
537        }
538
539        @Override
540        public void remove() {
541            if (fromInvalidBBoxPrimitives) {
542                invalidBBoxIterator.remove();
543                qb.size--;
544            } else {
545                // two uses
546                // 1. Back up to the thing we just returned
547                // 2. move the index back since we removed
548                //    an element
549                contentIndex--;
550                T object = peek();
551                if (currentNode.removeContent(object))
552                    qb.size--;
553
554            }
555        }
556    }
557
558    @Override
559    public Iterator<T> iterator() {
560        return new QuadBucketIterator(this);
561    }
562
563    @Override
564    public int size() {
565        return size;
566    }
567
568    @Override
569    public boolean isEmpty() {
570        return size == 0;
571    }
572
573    /**
574     * Search the tree for objects in the bbox (or crossing the bbox if they are ways)
575     * @param searchBbox the bbox
576     * @return List of primitives within the bbox (or crossing the bbox if they are ways). Can be empty, but not null.
577     */
578    public List<T> search(BBox searchBbox) {
579        List<T> ret = new ArrayList<>();
580        if (!searchBbox.isValid()) {
581            return ret;
582        }
583
584        // Doing this cuts down search cost on a real-life data set by about 25%
585        if (searchCache == null) {
586            searchCache = root;
587        }
588        // Walk back up the tree when the last search spot can not cover the current search
589        while (searchCache != null && !searchCache.bounds(searchBbox)) {
590            searchCache = searchCache.parent;
591        }
592
593        if (searchCache == null) {
594            searchCache = root;
595            Main.info("bbox: " + searchBbox + " is out of the world");
596        }
597
598        // Save parent because searchCache might change during search call
599        QBLevel<T> tmp = searchCache.parent;
600
601        searchCache.search(this, searchBbox, ret);
602
603        // A way that spans this bucket may be stored in one
604        // of the nodes which is a parent of the search cache
605        while (tmp != null) {
606            tmp.searchContents(searchBbox, ret);
607            tmp = tmp.parent;
608        }
609        return ret;
610    }
611}