001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.data.osm;
003    
004    import java.lang.reflect.Array;
005    import java.util.ArrayList;
006    import java.util.Arrays;
007    import java.util.Collection;
008    import java.util.Iterator;
009    import java.util.List;
010    
011    import org.openstreetmap.josm.data.coor.LatLon;
012    import 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     */
021    public class QuadBuckets<T extends OsmPrimitive> implements Collection<T>
022    {
023        //private static boolean debug = false;
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        {
032            throw new AssertionError(s);
033        }
034        static void out(String s)
035        {
036            System.out.println(s);
037        }
038        // periodic output
039        long last_out = -1;
040        void pout(String s)
041        {
042            long now = System.currentTimeMillis();
043            if (now - last_out < 300)
044                return;
045            last_out = now;
046            System.out.print(s + "\r");
047        }
048        void pout(String s, int i, int total)
049        {
050            long now = System.currentTimeMillis();
051            if ((now - last_out < 300) &&
052                    ((i+1) < total))
053                return;
054            last_out = now;
055            // cast to float to keep the output size down
056            System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done    \r");
057        }
058    
059        public static final int MAX_OBJECTS_PER_LEVEL = 16;
060        class QBLevel
061        {
062            final int level;
063            private final BBox bbox;
064            final long quad;
065            final QBLevel parent;
066            private boolean isLeaf = true;
067    
068            public List<T> content;
069            public QBLevel nw, ne, sw, se;
070    
071            private QBLevel getChild(int index) {
072                switch (index) {
073                case NE_INDEX:
074                    if (ne == null) {
075                        ne = new QBLevel(this, index);
076                    }
077                    return ne;
078                case NW_INDEX:
079                    if (nw == null) {
080                        nw = new QBLevel(this, index);
081                    }
082                    return nw;
083                case SE_INDEX:
084                    if (se == null) {
085                        se = new QBLevel(this, index);
086                    }
087                    return se;
088                case SW_INDEX:
089                    if (sw == null) {
090                        sw = new QBLevel(this, index);
091                    }
092                    return sw;
093                default:
094                    return null;
095                }
096            }
097    
098            private QBLevel[] getChildren() {
099                // This is ugly and hackish.  But, it seems to work,
100                // and using an ArrayList here seems to cost us
101                // a significant performance penalty -- 50% in my
102                // testing.  Child access is one of the single
103                // hottest code paths in this entire class.
104                QBLevel[] result = (QBLevel[]) Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL);
105                result[NW_INDEX] = nw;
106                result[NE_INDEX] = ne;
107                result[SW_INDEX] = sw;
108                result[SE_INDEX] = se;
109                return result;
110            }
111    
112            @Override
113            public String toString()  {
114                return super.toString()+ "["+level+"]: " + bbox();
115            }
116            /**
117             * Constructor for root node
118             */
119            public QBLevel() {
120                level = 0;
121                quad = 0;
122                parent = null;
123                bbox = new BBox(-180, 90, 180, -90);
124            }
125    
126            public QBLevel(QBLevel parent, int parent_index) {
127                this.parent = parent;
128                this.level = parent.level + 1;
129                int shift = (QuadTiling.NR_LEVELS - level) * 2;
130                long mult = 1;
131                // Java blows the big one.  It seems to wrap when
132                // you shift by > 31
133                if (shift >= 30) {
134                    shift -= 30;
135                    mult = 1<<30;
136                }
137                long this_quadpart = mult * (parent_index << shift);
138                this.quad = parent.quad | this_quadpart;
139                this.bbox = calculateBBox(); // calculateBBox reference quad
140                /*if (debug) {
141                    out("new level["+this.level+"] bbox["+parent_index+"]: " + this.bbox()
142                            + " coor: " + this.coor()
143                            + " quadpart: " + Long.toHexString(this_quadpart)
144                            + " quad: " + Long.toHexString(this.quad));
145                }*/
146            }
147    
148            private BBox calculateBBox() {
149                LatLon bottom_left = this.coor();
150                double lat = bottom_left.lat() + parent.height() / 2;
151                double lon = bottom_left.lon() + parent.width() / 2;
152                LatLon top_right = new LatLon(lat, lon);
153                return new BBox(bottom_left, top_right);
154            }
155    
156            QBLevel findBucket(BBox bbox) {
157                if (!hasChildren())
158                    return this;
159                else {
160                    int index = get_index(bbox, level);
161                    if (index == -1)
162                        return this;
163                    return getChild(index).findBucket(bbox);
164                }
165            }
166    
167            boolean remove_content(T o)
168            {
169                // If two threads try to remove item at the same time from different buckets of this QBLevel,
170                // it might happen that one thread removes bucket but don't remove parent because it still sees
171                // another bucket set. Second thread do the same. Due to thread memory caching, it's possible that
172                // changes made by threads will show up in children array too late, leading to QBLevel with all children
173                // set to null
174                if (content == null)
175                    return false;
176                boolean ret = this.content.remove(o);
177                if (this.content.size() == 0) {
178                    this.content = null;
179                }
180                if (this.canRemove()) {
181                    this.remove_from_parent();
182                }
183                return ret;
184            }
185            // Get the correct index for the given primitive
186            // at the given level.  If the primitive can not
187            // fit into a single quad at this level, return -1
188            int get_index(BBox bbox, int level) {
189                int index = -1;
190                for (LatLon c : bbox.points()) {
191                    /*if (debug) {
192                        out("getting index for point: " + c);
193                    }*/
194                    if (index == -1) {
195                        index = QuadTiling.index(c, level);
196                        /*if (debug) {
197                            out("set initial index to: " + index);
198                        }*/
199                        continue;
200                    }
201                    int another_index = QuadTiling.index(c, level);
202                    /*if (debug) {
203                        out("other point index: " + another_index);
204                    }*/
205                    if (another_index != index)
206                        return -1;
207                }
208                return index;
209            }
210            /*
211             * There is a race between this and qb.nextContentNode().
212             * If nextContentNode() runs into this bucket, it may
213             * attempt to null out 'children' because it thinks this
214             * is a dead end.
215             */
216            void __split() {
217                /*if (debug) {
218                    out("splitting "+this.bbox()+" level "+level+" with "
219                            + content.size() + " entries (my dimensions: "
220                            + this.bbox().width()+", "+this.bbox().height()+")");
221                }*/
222                List<T> tmpcontent = content;
223                content = null;
224    
225                for (T o: tmpcontent) {
226                    int index = get_index(o.getBBox(), level);
227                    if (index == -1) {
228                        __add_content(o);
229                    } else {
230                        getChild(index).doAdd(o);
231                    }
232                }
233                isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1)
234            }
235    
236            boolean __add_content(T o)
237            {
238                boolean ret = false;
239                // The split_lock will keep two concurrent
240                // calls from overwriting content
241                if (content == null) {
242                    content = new ArrayList<T>();
243                }
244                ret = content.add(o);
245                /*if (debug && !this.isLeaf()) {
246                    pout("added "+o.getClass().getName()+" to non-leaf with size: " + content.size());
247                }*/
248                return ret;
249            }
250            boolean matches(T o, BBox search_bbox)
251            {
252                // This can be optimized when o is a node
253                //return search_bbox.bounds(coor));
254                return o.getBBox().intersects(search_bbox);
255            }
256            private void search_contents(BBox search_bbox, List<T> result)
257            {
258                /*if (debug) {
259                    out("searching contents (size: " + content == null?"<null>":content.size() + ") for " + search_bbox);
260                }*/
261                /*
262                 * It is possible that this was created in a split
263                 * but never got any content populated.
264                 */
265                if (content == null)
266                    return;
267    
268                for (T o : content) {
269                    if (matches(o, search_bbox)) {
270                        result.add(o);
271                    }
272                }
273                /*if (debug) {
274                    out("done searching quad " + Long.toHexString(this.quad));
275                }*/
276            }
277            /*
278             * This is stupid.  I tried to have a QBLeaf and QBBranch
279             * class decending from a QBLevel.  It's more than twice
280             * as slow.  So, this throws OO out the window, but it
281             * is fast.  Runtime type determination must be slow.
282             */
283            boolean isLeaf() {
284                return isLeaf;
285            }
286            boolean hasChildren() {
287                return nw != null || ne != null || sw != null || se != null;
288            }
289    
290            QBLevel next_sibling()
291            {
292                boolean found_me = false;
293                if (parent == null)
294                    return null;
295                int __nr = 0;
296                for (QBLevel sibling : parent.getChildren()) {
297                    __nr++;
298                    int nr = __nr-1;
299                    if (sibling == null) {
300                        /*if (debug) {
301                            out("[" + this.level + "] null child nr: " + nr);
302                        }*/
303                        continue;
304                    }
305                    // We're looking for the *next* child
306                    // after us.
307                    if (sibling == this) {
308                        /*if (debug) {
309                            out("[" + this.level + "] I was child nr: " + nr);
310                        }*/
311                        found_me = true;
312                        continue;
313                    }
314                    if (found_me)
315                        /*if (debug) {
316                            out("[" + this.level + "] next sibling was child nr: " + nr);
317                        }*/
318                        return sibling;
319                }
320                return null;
321            }
322            boolean hasContent()
323            {
324                return content != null;
325            }
326            QBLevel nextSibling()
327            {
328                QBLevel next = this;
329                QBLevel sibling = next.next_sibling();
330                // Walk back up the tree to find the
331                // next sibling node.  It may be either
332                // a leaf or branch.
333                while (sibling == null) {
334                    /*if (debug) {
335                        out("no siblings at level["+next.level+"], moving to parent");
336                    }*/
337                    next = next.parent;
338                    if (next == null) {
339                        break;
340                    }
341                    sibling = next.next_sibling();
342                }
343                next = sibling;
344                return next;
345            }
346            QBLevel firstChild()
347            {
348                QBLevel ret = null;
349                for (QBLevel child : getChildren()) {
350                    if (child == null) {
351                        continue;
352                    }
353                    ret = child;
354                    break;
355                }
356                return ret;
357            }
358            QBLevel nextNode()
359            {
360                if (!this.hasChildren())
361                    return this.nextSibling();
362                return this.firstChild();
363            }
364            QBLevel nextContentNode()
365            {
366                QBLevel next = this.nextNode();
367                if (next == null)
368                    return next;
369                if (next.hasContent())
370                    return next;
371                return next.nextContentNode();
372            }
373    
374            void doAdd(T o) {
375                if (consistency_testing) {
376                    if (!matches(o, this.bbox())) {
377                        /*out("-----------------------------");
378                        debug = true;*/
379                        get_index(o.getBBox(), level);
380                        get_index(o.getBBox(), level-1);
381                        int nr = 0;
382                        /*for (QBLevel sibling : parent.getChildren()) {
383                            out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling));
384                        }*/
385                        abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
386                    }
387                }
388                __add_content(o);
389                if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) {
390                    __split();
391                }
392            }
393    
394            void add(T o) {
395                findBucket(o.getBBox()).doAdd(o);
396            }
397    
398            private void search(BBox search_bbox, List<T> result)
399            {
400                /*if (debug) {
401                    System.out.print("[" + level + "] qb bbox: " + this.bbox() + " ");
402                }*/
403                if (!this.bbox().intersects(search_bbox))
404                    /*if (debug) {
405                        out("miss " + Long.toHexString(this.quad));
406                        //QuadTiling.tile2xy(this.quad);
407                    }*/
408                    return;
409                else if (bbox().bounds(search_bbox)) {
410                    search_cache = this;
411                }
412    
413                if (this.hasContent()) {
414                    search_contents(search_bbox, result);
415                }
416    
417                /*if (debug) {
418                    out("hit " + this.quads());
419                    out("[" + level + "] not leaf, moving down");
420                }*/
421    
422                //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked
423    
424                if (nw != null) {
425                    nw.search(search_bbox, result);
426                }
427                if (ne != null) {
428                    ne.search(search_bbox, result);
429                }
430                if (se != null) {
431                    se.search(search_bbox, result);
432                }
433                if (sw != null) {
434                    sw.search(search_bbox, result);
435                }
436            }
437            public String quads()
438            {
439                return Long.toHexString(quad);
440            }
441            int index_of(QBLevel find_this)
442            {
443                QBLevel[] children = getChildren();
444                for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
445                    if (children[i] == find_this)
446                        return i;
447                }
448                return -1;
449            }
450            double width() {
451                return bbox.width();
452            }
453    
454            double height() {
455                return bbox.height();
456            }
457    
458            public BBox bbox() {
459                return bbox;
460            }
461            /*
462             * This gives the coordinate of the bottom-left
463             * corner of the box
464             */
465            LatLon coor()
466            {
467                return QuadTiling.tile2LatLon(this.quad);
468            }
469            void remove_from_parent()
470            {
471                if (parent == null)
472                    return;
473    
474                if (!canRemove()) {
475                    abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren()));
476                }
477    
478                if (parent.nw == this) {
479                    parent.nw = null;
480                } else if (parent.ne == this) {
481                    parent.ne = null;
482                } else if (parent.sw == this) {
483                    parent.sw = null;
484                } else if (parent.se == this) {
485                    parent.se = null;
486                }
487    
488                if (parent.canRemove()) {
489                    parent.remove_from_parent();
490                }
491            }
492            boolean canRemove()
493            {
494                if (content != null && content.size() > 0)
495                    return false;
496                if (this.hasChildren())
497                    return false;
498                return true;
499            }
500        }
501    
502        private QBLevel root;
503        private QBLevel search_cache;
504        private int size;
505    
506        public QuadBuckets()
507        {
508            clear();
509        }
510        public void clear()  {
511            root = new QBLevel();
512            search_cache = null;
513            size = 0;
514            /*if (debug) {
515                out("QuadBuckets() cleared: " + this);
516                out("root: " + root + " level: " + root.level + " bbox: " + root.bbox());
517            }*/
518        }
519        public boolean add(T n) {
520            root.add(n);
521            size++;
522            return true;
523        }
524    
525        public boolean retainAll(Collection<?> objects)
526        {
527            for (T o : this) {
528                if (objects.contains(o)) {
529                    continue;
530                }
531                if (!this.remove(o))
532                    return false;
533            }
534            return true;
535        }
536        public boolean removeAll(Collection<?> objects)
537        {
538            boolean changed = false;
539            for (Object o : objects) {
540                changed = changed | remove(o);
541            }
542            return changed;
543        }
544        public boolean addAll(Collection<? extends T> objects)
545        {
546            boolean changed = false;
547            for (T o : objects) {
548                changed = changed | this.add(o);
549            }
550            return changed;
551        }
552        public boolean containsAll(Collection<?> objects)
553        {
554            for (Object o : objects) {
555                if (!this.contains(o))
556                    return false;
557            }
558            return true;
559        }
560        public boolean remove(Object o) {
561            @SuppressWarnings("unchecked") T t = (T) o;
562            search_cache = null; // Search cache might point to one of removed buckets
563            QBLevel bucket = root.findBucket(t.getBBox());
564            if (bucket.remove_content(t)) {
565                size--;
566                return true;
567            } else
568                return false;
569        }
570        public boolean contains(Object o) {
571            @SuppressWarnings("unchecked") T t = (T) o;
572            QBLevel bucket = root.findBucket(t.getBBox());
573            return bucket != null && bucket.content != null && bucket.content.contains(t);
574        }
575    
576        public ArrayList<T> toArrayList()
577        {
578            ArrayList<T> a = new ArrayList<T>();
579            for (T n : this) {
580                a.add(n);
581            }
582            /*if (debug) {
583                out("returning array list with size: " + a.size());
584            }*/
585            return a;
586        }
587        public Object[] toArray()
588        {
589            return this.toArrayList().toArray();
590        }
591        public <A> A[] toArray(A[] template)
592        {
593            return this.toArrayList().toArray(template);
594        }
595        class QuadBucketIterator implements Iterator<T>
596        {
597            QBLevel current_node;
598            int content_index;
599            int iterated_over;
600            QBLevel next_content_node(QBLevel q)
601            {
602                if (q == null)
603                    return null;
604                QBLevel orig = q;
605                QBLevel next;
606                next = q.nextContentNode();
607                //if (consistency_testing && (orig == next))
608                if (orig == next) {
609                    abort("got same leaf back leaf: " + q.isLeaf());
610                }
611                return next;
612            }
613            public QuadBucketIterator(QuadBuckets<T> qb)
614            {
615                /*if (debug) {
616                    out(this + " is a new iterator qb: " + qb + " size: " + qb.size());
617                }*/
618                if (!qb.root.hasChildren() || qb.root.hasContent()) {
619                    current_node = qb.root;
620                } else {
621                    current_node = next_content_node(qb.root);
622                }
623                /*if (debug) {
624                    out("\titerator first leaf: " + current_node);
625                }*/
626                iterated_over = 0;
627            }
628            public boolean hasNext()
629            {
630                if (this.peek() == null)
631                    /*if (debug) {
632                        out(this + " no hasNext(), but iterated over so far: " + iterated_over);
633                    }*/
634                    return false;
635                return true;
636            }
637            T peek()
638            {
639                if (current_node == null)
640                    /*if (debug) {
641                        out("null current leaf, nowhere to go");
642                    }*/
643                    return null;
644                while((current_node.content == null) ||
645                        (content_index >= current_node.content.size())) {
646                    /*if (debug) {
647                        out("moving to next leaf");
648                    }*/
649                    content_index = 0;
650                    current_node = next_content_node(current_node);
651                    if (current_node == null) {
652                        break;
653                    }
654                }
655                if (current_node == null || current_node.content == null)
656                    /*if (debug) {
657                        out("late nowhere to go " + current_node);
658                    }*/
659                    return null;
660                return current_node.content.get(content_index);
661            }
662            public T next()
663            {
664                T ret = peek();
665                content_index++;
666                /*if (debug) {
667                    out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node);
668                }*/
669                iterated_over++;
670                if (ret == null) {
671                    /*if (debug) {
672                        out(this + " no next node, but iterated over so far: " + iterated_over);
673                    }*/
674                }
675                return ret;
676            }
677            public void remove()
678            {
679                // two uses
680                // 1. Back up to the thing we just returned
681                // 2. move the index back since we removed
682                //    an element
683                content_index--;
684                T object = peek();
685                current_node.remove_content(object);
686            }
687        }
688        public Iterator<T> iterator()
689        {
690            return new QuadBucketIterator(this);
691        }
692        public int size() {
693            return size;
694        }
695    
696        public boolean isEmpty()
697        {
698            if (this.size() == 0)
699                return true;
700            return false;
701        }
702        public List<T> search(BBox search_bbox) {
703            /*if (debug) {
704                out("qb root search at " + search_bbox);
705                out("root bbox: " + root.bbox());
706            }*/
707            List<T> ret = new ArrayList<T>();
708            // Doing this cuts down search cost on a real-life data
709            // set by about 25%
710            boolean cache_searches = true;
711            if (cache_searches) {
712                if (search_cache == null) {
713                    search_cache = root;
714                }
715                // Walk back up the tree when the last
716                // search spot can not cover the current
717                // search
718                while (search_cache != null && !search_cache.bbox().bounds(search_bbox)) {
719                    /*if (debug) {
720                        out("bbox: " + search_bbox);
721                        out("search_cache: " + search_cache + " level: " + search_cache.level);
722                        out("search_cache.bbox(): " + search_cache.bbox());
723                    }*/
724                    search_cache = search_cache.parent;
725                    /*if (debug) {
726                        out("new search_cache: " + search_cache);
727                    }*/
728                }
729    
730                if (search_cache == null) {
731                    search_cache = root;
732                    out("bbox: " + search_bbox + " is out of the world");
733                }
734            } else {
735                search_cache = root;
736            }
737    
738            // Save parent because search_cache might change during search call
739            QBLevel tmp = search_cache.parent;
740    
741            search_cache.search(search_bbox, ret);
742    
743            // A way that spans this bucket may be stored in one
744            // of the nodes which is a parent of the search cache
745            while (tmp != null) {
746                tmp.search_contents(search_bbox, ret);
747                tmp = tmp.parent;
748            }
749            /*if (debug) {
750                out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size());
751            }*/
752            return ret;
753        }
754    
755        public void printTree() {
756            printTreeRecursive(root, 0);
757        }
758    
759        private void printTreeRecursive(QBLevel level, int indent) {
760            if (level == null) {
761                printIndented(indent, "<empty child>");
762                return;
763            }
764            printIndented(indent, level);
765            if (level.hasContent()) {
766                for (T o:level.content) {
767                    printIndented(indent, o);
768                }
769            }
770            for (QBLevel child:level.getChildren()) {
771                printTreeRecursive(child, indent + 2);
772            }
773        }
774    
775        private void printIndented(int indent, Object msg) {
776            for (int i=0; i<indent; i++) {
777                System.out.print(' ');
778            }
779            System.out.println(msg);
780        }
781    }