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