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