Changeset 6178 in josm for trunk/src/org/openstreetmap


Ignore:
Timestamp:
2013-08-23T02:25:15+02:00 (11 years ago)
Author:
Don-vip
Message:

fix #9002 - QuadBuckets improvements (patch by shinigami)

Location:
trunk/src/org/openstreetmap/josm/data
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/org/openstreetmap/josm/data/coor/LatLon.java

    r6173 r6178  
    3636    public static final int    MAX_SERVER_DIGITS = 7;
    3737
     38    /**
     39     * The (0,0) coordinates.
     40     * @since 6178
     41     */
     42    public static final LatLon ZERO = new LatLon(0, 0);
     43   
    3844    private static DecimalFormat cDmsMinuteFormatter = new DecimalFormat("00");
    3945    private static DecimalFormat cDmsSecondFormatter = new DecimalFormat("00.0");

  • trunk/src/org/openstreetmap/josm/data/osm/BBox.java

    r6171 r6178  
    22package org.openstreetmap.josm.data.osm;
    33
    4 import java.util.ArrayList;
    54import java.util.Arrays;
    6 import java.util.List;
    75
    86import org.openstreetmap.josm.data.Bounds;

  • trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java

    r6171 r6178  
    22package org.openstreetmap.josm.data.osm;
    33
    4 import java.lang.reflect.Array;
    54import java.util.ArrayList;
    65import java.util.Arrays;
    … …  
    2019 *
    2120 */
    22 public class QuadBuckets<T extends OsmPrimitive> implements Collection<T>
    23 {
     21public class QuadBuckets<T extends OsmPrimitive> implements Collection<T> {
    2422    private static final boolean consistency_testing = false;
    2523    private static final int NW_INDEX = 1;
    … …  
    3331
    3432    public static final int MAX_OBJECTS_PER_LEVEL = 16;
    35    
    36     class QBLevel
    37     {
    38         final int level;
     33
     34    static class QBLevel<T extends OsmPrimitive> {
     35        private final int level;
     36        private final int index;
    3937        private final BBox bbox;
    40         final long quad;
    41         final QBLevel parent;
     38        private final long quad;
     39        private final QBLevel<T> parent;
    4240        private boolean isLeaf = true;
    4341
    44         public List<T> content;
    45         public QBLevel nw, ne, sw, se;
    46 
    47         private QBLevel getChild(int index) {
     42        private List<T> content;
     43        // child order by index is sw, nw, se, ne
     44        private QBLevel<T> nw, ne, sw, se;
     45        private boolean hasChild;
     46
     47        private final QuadBuckets<T> buckets;
     48
     49        private QBLevel<T> getChild(int index) {
    4850            switch (index) {
    4951            case NE_INDEX:
    5052                if (ne == null) {
    51                     ne = new QBLevel(this, index);
     53                    ne = new QBLevel<T>(this, index, buckets);
     54                    hasChild = true;
    5255                }
    5356                return ne;
    5457            case NW_INDEX:
    5558                if (nw == null) {
    56                     nw = new QBLevel(this, index);
     59                    nw = new QBLevel<T>(this, index, buckets);
     60                    hasChild = true;
    5761                }
    5862                return nw;
    5963            case SE_INDEX:
    6064                if (se == null) {
    61                     se = new QBLevel(this, index);
     65                    se = new QBLevel<T>(this, index, buckets);
     66                    hasChild = true;
    6267                }
    6368                return se;
    6469            case SW_INDEX:
    6570                if (sw == null) {
    66                     sw = new QBLevel(this, index);
     71                    sw = new QBLevel<T>(this, index, buckets);
     72                    hasChild = true;
    6773                }
    6874                return sw;
    … …  
    7278        }
    7379
    74         private QBLevel[] getChildren() {
    75             // This is ugly and hackish.  But, it seems to work,
    76             // and using an ArrayList here seems to cost us
    77             // a significant performance penalty -- 50% in my
    78             // testing.  Child access is one of the single
    79             // hottest code paths in this entire class.
    80             @SuppressWarnings("unchecked")
    81             QBLevel[] result = (QBLevel[]) Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL);
    82             result[NW_INDEX] = nw;
    83             result[NE_INDEX] = ne;
    84             result[SW_INDEX] = sw;
    85             result[SE_INDEX] = se;
    86             return result;
     80        @SuppressWarnings("unchecked")
     81        private QBLevel<T>[] getChildren() {
     82            return new QBLevel[] {sw, nw, se, ne};
    8783        }
    8884
    8985        @Override
    90         public String toString()  {
    91             return super.toString()+ "["+level+"]: " + bbox();
    92         }
    93        
     86        public String toString() {
     87            return super.toString() + "[" + level + "]: " + bbox();
     88        }
     89
    9490        /**
    9591         * Constructor for root node
    9692         */
    97         public QBLevel() {
     93        public QBLevel(final QuadBuckets<T> buckets) {
    9894            level = 0;
     95            index = 0;
    9996            quad = 0;
    10097            parent = null;
    10198            bbox = new BBox(-180, 90, 180, -90);
    102         }
    103 
    104         public QBLevel(QBLevel parent, int parent_index) {
     99            this.buckets = buckets;
     100        }
     101
     102        public QBLevel(QBLevel<T> parent, int parent_index, final QuadBuckets<T> buckets) {
    105103            this.parent = parent;
    106104            this.level = parent.level + 1;
     105            this.index = parent_index;
     106            this.buckets = buckets;
     107
    107108            int shift = (QuadTiling.NR_LEVELS - level) * 2;
    108109            long mult = 1;
    … …  
    110111            if (shift >= 30) {
    111112                shift -= 30;
    112                 mult = 1<<30;
     113                mult = 1 << 30;
    113114            }
    114115            long this_quadpart = mult * (parent_index << shift);
    … …  
    125126        }
    126127
    127         QBLevel findBucket(BBox bbox) {
     128        QBLevel<T> findBucket(BBox bbox) {
    128129            if (!hasChildren())
    129130                return this;
    … …  
    164165            content = null;
    165166
    166             for (T o: tmpcontent) {
     167            for (T o : tmpcontent) {
    167168                int index = o.getBBox().getIndex(level);
    168169                if (index == -1) {
    … …  
    184185            return ret;
    185186        }
    186        
    187         boolean matches(T o, BBox search_bbox) {
    188             // This can be optimized when o is a node
     187
     188        boolean matches(final T o, final BBox search_bbox) {
     189            if (o instanceof Node){
     190                final LatLon latLon = ((Node)o).getCoor();
     191                // node without coords -> bbox[0,0,0,0]
     192                return search_bbox.bounds(latLon != null ? latLon : LatLon.ZERO);
     193            }
    189194            return o.getBBox().intersects(search_bbox);
    190195        }
    191        
     196
    192197        private void search_contents(BBox search_bbox, List<T> result) {
    193198            /*
    … …  
    204209            }
    205210        }
    206        
     211
    207212        /*
    208213         * This is stupid. I tried to have a QBLeaf and QBBranch
    209          * class decending from a QBLevel. It's more than twice
     214         * class descending from a QBLevel. It's more than twice
    210215         * as slow. So, this throws OO out the window, but it
    211216         * is fast. Runtime type determination must be slow.
    … …  
    214219            return isLeaf;
    215220        }
    216        
     221
    217222        boolean hasChildren() {
    218             return nw != null || ne != null || sw != null || se != null;
    219         }
    220 
    221         QBLevel next_sibling() {
    222             boolean found_me = false;
    223             if (parent == null)
    224                 return null;
    225             for (QBLevel sibling : parent.getChildren()) {
    226                 if (sibling == null) {
    227                     continue;
    228                 }
    229                 // We're looking for the *next* child after us.
    230                 if (sibling == this) {
    231                     found_me = true;
    232                     continue;
    233                 }
    234                 if (found_me)
    235                     return sibling;
    236             }
    237             return null;
    238         }
    239        
     223            return hasChild;
     224        }
     225
     226        QBLevel<T> next_sibling() {
     227            return (parent == null) ? null : parent.firstSiblingOf(this);
     228        }
     229
    240230        boolean hasContent() {
    241231            return content != null;
    242232        }
    243        
    244         QBLevel nextSibling() {
    245             QBLevel next = this;
    246             QBLevel sibling = next.next_sibling();
     233
     234        QBLevel<T> nextSibling() {
     235            QBLevel<T> next = this;
     236            QBLevel<T> sibling = next.next_sibling();
    247237            // Walk back up the tree to find the
    248238            // next sibling node.  It may be either
    … …  
    258248            return next;
    259249        }
    260        
    261         QBLevel firstChild() {
    262             QBLevel ret = null;
    263             for (QBLevel child : getChildren()) {
    264                 if (child == null) {
    265                     continue;
    266                 }
    267                 ret = child;
    268                 break;
    269             }
    270             return ret;
    271         }
    272        
    273         QBLevel nextNode() {
     250
     251        QBLevel<T> firstChild() {
     252            if (sw != null)
     253                return sw;
     254            if (nw != null)
     255                return nw;
     256            if (se != null)
     257                return se;
     258            return ne;
     259        }
     260
     261        QBLevel<T> firstSiblingOf(final QBLevel<T> child) {
     262            switch (child.index) {
     263            case SW_INDEX:
     264                if (nw != null)
     265                    return nw;
     266            case NW_INDEX:
     267                if (se != null)
     268                    return se;
     269            case SE_INDEX:
     270                return ne;
     271            }
     272            return null;
     273        }
     274
     275        QBLevel<T> nextNode() {
    274276            if (!this.hasChildren())
    275277                return this.nextSibling();
    276278            return this.firstChild();
    277279        }
    278        
    279         QBLevel nextContentNode() {
    280             QBLevel next = this.nextNode();
     280
     281        QBLevel<T> nextContentNode() {
     282            QBLevel<T> next = this.nextNode();
    281283            if (next == null)
    282284                return next;
    … …  
    290292                if (!matches(o, this.bbox())) {
    291293                    o.getBBox().getIndex(level);
    292                     o.getBBox().getIndex(level-1);
     294                    o.getBBox().getIndex(level - 1);
    293295                    int nr = 0;
    294296                    abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
    … …  
    309311                return;
    310312            else if (bbox().bounds(search_bbox)) {
    311                 search_cache = this;
     313                buckets.search_cache = this;
    312314            }
    313315
    … …  
    331333            }
    332334        }
    333        
     335
    334336        public String quads() {
    335337            return Long.toHexString(quad);
    336338        }
    337        
    338         int index_of(QBLevel find_this) {
    339             QBLevel[] children = getChildren();
     339
     340        int index_of(QBLevel<T> find_this) {
     341            QBLevel<T>[] children = getChildren();
    340342            for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) {
    341343                if (children[i] == find_this)
    … …  
    344346            return -1;
    345347        }
    346        
     348
    347349        double width() {
    348350            return bbox.width();
    … …  
    356358            return bbox;
    357359        }
    358        
     360
    359361        /*
    360362         * This gives the coordinate of the bottom-left
    … …  
    364366            return QuadTiling.tile2LatLon(this.quad);
    365367        }
    366        
     368
    367369        void remove_from_parent() {
    368370            if (parent == null)
    … …  
    387389            }
    388390        }
    389        
     391
    390392        boolean canRemove() {
    391393            if (content != null && !content.isEmpty())
    … …  
    397399    }
    398400
    399     private QBLevel root;
    400     private QBLevel search_cache;
     401    private QBLevel<T> root;
     402    private QBLevel<T> search_cache;
    401403    private int size;
    402404
    … …  
    407409        clear();
    408410    }
    409    
    410     @Override
    411     public void clear()  {
    412         root = new QBLevel();
     411
     412    @Override
     413    public void clear() {
     414        root = new QBLevel<T>(this);
    413415        search_cache = null;
    414416        size = 0;
    415417    }
    416    
     418
    417419    @Override
    418420    public boolean add(T n) {
    … …  
    433435        return true;
    434436    }
    435    
     437
    436438    @Override
    437439    public boolean removeAll(Collection<?> objects) {
    … …  
    442444        return changed;
    443445    }
    444    
     446
    445447    @Override
    446448    public boolean addAll(Collection<? extends T> objects) {
    … …  
    451453        return changed;
    452454    }
    453    
     455
    454456    @Override
    455457    public boolean containsAll(Collection<?> objects) {
    … …  
    460462        return true;
    461463    }
    462    
     464
    463465    @Override
    464466    public boolean remove(Object o) {
    465         @SuppressWarnings("unchecked") T t = (T) o;
     467        @SuppressWarnings("unchecked")
     468        T t = (T) o;
    466469        search_cache = null; // Search cache might point to one of removed buckets
    467         QBLevel bucket = root.findBucket(t.getBBox());
     470        QBLevel<T> bucket = root.findBucket(t.getBBox());
    468471        if (bucket.remove_content(t)) {
    469472            size--;
    … …  
    472475            return false;
    473476    }
    474    
     477
    475478    @Override
    476479    public boolean contains(Object o) {
    477         @SuppressWarnings("unchecked") T t = (T) o;
    478         QBLevel bucket = root.findBucket(t.getBBox());
     480        @SuppressWarnings("unchecked")
     481        T t = (T) o;
     482        QBLevel<T> bucket = root.findBucket(t.getBBox());
    479483        return bucket != null && bucket.content != null && bucket.content.contains(t);
    480484    }
    … …  
    487491        return a;
    488492    }
    489    
     493
    490494    @Override
    491495    public Object[] toArray() {
    492496        return this.toArrayList().toArray();
    493497    }
    494    
     498
    495499    @Override
    496500    public <A> A[] toArray(A[] template) {
    497501        return this.toArrayList().toArray(template);
    498502    }
    499    
    500     class QuadBucketIterator implements Iterator<T>
    501     {
    502         QBLevel current_node;
     503
     504    class QuadBucketIterator implements Iterator<T> {
     505        QBLevel<T> current_node;
    503506        int content_index;
    504507        int iterated_over;
    505         QBLevel next_content_node(QBLevel q) {
     508
     509        QBLevel<T> next_content_node(QBLevel<T> q) {
    506510            if (q == null)
    507511                return null;
    508             QBLevel orig = q;
    509             QBLevel next;
     512            QBLevel<T> orig = q;
     513            QBLevel<T> next;
    510514            next = q.nextContentNode();
    511515            //if (consistency_testing && (orig == next))
    … …  
    515519            return next;
    516520        }
    517        
     521
    518522        public QuadBucketIterator(QuadBuckets<T> qb) {
    519523            if (!qb.root.hasChildren() || qb.root.hasContent()) {
    … …  
    524528            iterated_over = 0;
    525529        }
    526        
     530
    527531        @Override
    528532        public boolean hasNext() {
    … …  
    531535            return true;
    532536        }
    533        
     537
    534538        T peek() {
    535539            if (current_node == null)
    536540                return null;
    537             while((current_node.content == null) ||
    538                     (content_index >= current_node.content.size())) {
     541            while ((current_node.content == null) || (content_index >= current_node.content.size())) {
    539542                content_index = 0;
    540543                current_node = next_content_node(current_node);
    … …  
    547550            return current_node.content.get(content_index);
    548551        }
    549        
     552
    550553        @Override
    551554        public T next() {
    … …  
    555558            return ret;
    556559        }
    557        
     560
    558561        @Override
    559562        public void remove() {
    … …  
    567570        }
    568571    }
    569    
     572
    570573    @Override
    571574    public Iterator<T> iterator() {
    … …  
    584587        return false;
    585588    }
    586    
     589
    587590    public List<T> search(BBox search_bbox) {
    588591        List<T> ret = new ArrayList<T>();
    … …  
    607610
    608611        // Save parent because search_cache might change during search call
    609         QBLevel tmp = search_cache.parent;
     612        QBLevel<T> tmp = search_cache.parent;
    610613
    611614        search_cache.search(search_bbox, ret);
    … …  
    624627    }
    625628
    626     private void printTreeRecursive(QBLevel level, int indent) {
     629    private void printTreeRecursive(QBLevel<T> level, int indent) {
    627630        if (level == null) {
    628631            printIndented(indent, "<empty child>");
    … …  
    631634        printIndented(indent, level);
    632635        if (level.hasContent()) {
    633             for (T o:level.content) {
     636            for (T o : level.content) {
    634637                printIndented(indent, o);
    635638            }
    636639        }
    637         for (QBLevel child:level.getChildren()) {
     640        for (QBLevel<T> child : level.getChildren()) {
    638641            printTreeRecursive(child, indent + 2);
    639642        }
    … …  
    641644
    642645    private void printIndented(int indent, Object msg) {
    643         for (int i=0; i<indent; i++) {
     646        for (int i = 0; i < indent; i++) {
    644647            System.out.print(' ');
    645648        }
Note: See TracChangeset for help on using the changeset viewer.