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