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