source: josm/trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java @ 5241

Revision 4869, 24.5 KB checked in by jttt, 4 months ago (diff)

Use final were appropriate
  • Property svn:eol-style set to native
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data.osm;
3
4import java.lang.reflect.Array;
5import java.util.ArrayList;
6import java.util.Arrays;
7import java.util.Collection;
8import java.util.Iterator;
9import java.util.List;
10
11import org.openstreetmap.josm.data.coor.LatLon;
12import org.openstreetmap.josm.data.coor.QuadTiling;
13
14/**
15 * Note: bbox of primitives added to QuadBuckets has to stay the same. In case of coordinate change, primitive must
16 * be removed and readded.
17 *
18 * This class is (no longer) thread safe.
19 *
20 */
21public class QuadBuckets<T extends OsmPrimitive> implements Collection<T>
22{
23    //private static boolean debug = false;
24    private static final boolean consistency_testing = false;
25    private static final int NW_INDEX = 1;
26    private static final int NE_INDEX = 3;
27    private static final int SE_INDEX = 2;
28    private static final int SW_INDEX = 0;
29
30    static void abort(String s)
31    {
32        throw new AssertionError(s);
33    }
34    static void out(String s)
35    {
36        System.out.println(s);
37    }
38    // periodic output
39    long last_out = -1;
40    void pout(String s)
41    {
42        long now = System.currentTimeMillis();
43        if (now - last_out < 300)
44            return;
45        last_out = now;
46        System.out.print(s + "\r");
47    }
48    void pout(String s, int i, int total)
49    {
50        long now = System.currentTimeMillis();
51        if ((now - last_out < 300) &&
52                ((i+1) < total))
53            return;
54        last_out = now;
55        // cast to float to keep the output size down
56        System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done    \r");
57    }
58
59    public static final int MAX_OBJECTS_PER_LEVEL = 16;
60    class QBLevel
61    {
62        final int level;
63        private final BBox bbox;
64        final long quad;
65        final QBLevel parent;
66        private boolean isLeaf = true;
67
68        public List<T> content;
69        public QBLevel nw, ne, sw, se;
70
71        private QBLevel getChild(int index) {
72            switch (index) {
73            case NE_INDEX:
74                if (ne == null) {
75                    ne = new QBLevel(this, index);
76                }
77                return ne;
78            case NW_INDEX:
79                if (nw == null) {
80                    nw = new QBLevel(this, index);
81                }
82                return nw;
83            case SE_INDEX:
84                if (se == null) {
85                    se = new QBLevel(this, index);
86                }
87                return se;
88            case SW_INDEX:
89                if (sw == null) {
90                    sw = new QBLevel(this, index);
91                }
92                return sw;
93            default:
94                return null;
95            }
96        }
97
98        private QBLevel[] getChildren() {
99            // 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}
Note: See TracBrowser for help on using the repository browser.