Changeset 3150 in josm for trunk/src


Ignore:
Timestamp:
2010-03-21T09:56:49+01:00 (10 years ago)
Author:
jttt
Message:

Split QBLevel only once in QuadBuckets, simplified add operation

File:
1 edited

Legend:

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

    r3145 r3150  
    5151        System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done    \r");
    5252    }
    53     // 24 levels of buckets gives us bottom-level
    54     // buckets that are about 2 meters on a side.
    55     // That should do. :)
    56     public static int NR_LEVELS = 24;
    57     public static double WORLD_PARTS = (1 << NR_LEVELS);
    5853
    5954    public static int MAX_OBJECTS_PER_LEVEL = 16;
     
    8580            this.parent = parent;
    8681            this.level = parent.level + 1;
    87             int shift = (QuadBuckets.NR_LEVELS - level) * 2;
     82            int shift = (QuadTiling.NR_LEVELS - level) * 2;
    8883            long mult = 1;
    8984            // Java blows the big one.  It seems to wrap when
     
    110105            LatLon top_right = new LatLon(lat, lon);
    111106            return new BBox(bottom_left, top_right);
     107        }
     108
     109        QBLevel findBucket(BBox bbox) {
     110            if (isLeaf())
     111                return this;
     112            else {
     113                int index = get_index(bbox, level);
     114                if (index == -1)
     115                    return this;
     116                if (children[index] == null) {
     117                    children[index] = new QBLevel(this, index);
     118                }
     119                return children[index].findBucket(bbox);
     120            }
    112121        }
    113122
     
    142151        // at the given level.  If the primitive can not
    143152        // fit into a single quad at this level, return -1
    144         int get_index(T o, int level)
    145         {
    146             if (debug) {
    147                 out("getting index for " + o + " at level: " + level);
    148             }
     153        int get_index(BBox bbox, int level) {
    149154            int index = -1;
    150             for (LatLon c : o.getBBox().points()) {
     155            for (LatLon c : bbox.points()) {
    151156                if (debug) {
    152157                    out("getting index for point: " + c);
     
    163168                    out("other point index: " + another_index);
    164169                }
    165                 if (another_index != index) {
    166                     // This happens at level 0 sometimes when a way has no
    167                     // nodes present.
    168                     if (debug) {
    169                         out("primitive ("+o.getId()+") would have gone across two quads "
    170                                 + another_index + "/" + index + " at level: " + level + "    ");
    171                     }
     170                if (another_index != index)
    172171                    return -1;
    173                 }
    174172            }
    175173            return index;
     
    181179         * is a dead end.
    182180         */
    183         void __split()
    184         {
     181        void __split() {
    185182            if (debug) {
    186183                out("splitting "+this.bbox()+" level "+level+" with "
     
    194191            List<T> tmpcontent = content;
    195192            content = null;
    196             for (T o : tmpcontent) {
    197                 int new_index = get_index(o, level);
    198                 if (new_index == -1) {
    199                     this.__add_content(o);
    200                     //out("adding content to branch: " + this);
    201                     continue;
    202                 }
    203                 if (children == null) {
    204                     children = newChildren();
    205                 }
    206                 if (children[new_index] == null) {
    207                     children[new_index] = new QBLevel(this, new_index);
    208                 }
    209                 QBLevel child = children[new_index];
    210                 if (debug) {
    211                     out("putting "+o+"(q:"+Long.toHexString(QuadTiling.quadTile(o.getBBox().points().get(0)))+") into ["+new_index+"] " + child.bbox());
    212                 }
    213                 child.add(o);
    214             }
    215         }
    216         void split() {
    217             synchronized(split_lock) {
    218                 __split();
    219             }
    220         }
     193            children = newChildren();
     194            for (T o: tmpcontent) {
     195                add(o);
     196            }
     197            if (!hasChildren()) {
     198                // All items stay at this level (get_index == 1). Create at least first child to keep the contract
     199                // that at least one child always exists
     200                children[0] = new QBLevel(this, 0);
     201            }
     202        }
     203
    221204        boolean __add_content(T o)
    222205        {
     
    233216            return ret;
    234217        }
    235         void __add_to_leaf(T o)
    236         {
    237             __add_content(o);
    238             if (content.size() > MAX_OBJECTS_PER_LEVEL) {
    239                 if (debug) {
    240                     out("["+level+"] deciding to split");
    241                 }
    242                 if (level >= NR_LEVELS-1) {
    243                     if (debug) {
    244                         out("can not split, but too deep: " + level + " size: " + content.size());
    245                     }
    246                     return;
    247                 }
    248                 int before_size = -1;
    249                 if (consistency_testing) {
    250                     before_size = this.size();
    251                 }
    252                 this.split();
    253                 if (consistency_testing) {
    254                     int after_size = this.size();
    255                     if (before_size != after_size) {
    256                         abort("["+level+"] split done before: " + before_size + " after: " + after_size);
    257                     }
    258                 }
    259                 return;
    260             }
    261         }
    262 
    263218        boolean matches(T o, BBox search_bbox)
    264219        {
     
    461416            return ret;
    462417        }
    463         boolean add(T n)
    464         {
     418
     419        void doAdd(T o) {
    465420            if (consistency_testing) {
    466                 if (!matches(n, this.bbox())) {
     421                if (!matches(o, this.bbox())) {
    467422                    out("-----------------------------");
    468423                    debug = true;
    469                     get_index(n, level);
    470                     get_index(n, level-1);
     424                    get_index(o.getBBox(), level);
     425                    get_index(o.getBBox(), level-1);
    471426                    int nr = 0;
    472427                    for (QBLevel sibling : parent.children) {
    473428                        out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling));
    474429                    }
    475                     abort("\nobject " + n + " does not belong in node at level: " + level + " bbox: " + this.bbox());
     430                    abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox());
    476431                }
    477432            }
    478433            synchronized (split_lock) {
    479                 if (isLeaf()) {
    480                     __add_to_leaf(n);
    481                 } else {
    482                     __add_to_branch(n);
    483                 }
    484             }
    485             return true;
    486         }
    487         QBLevel __add_to_branch(T n)
    488         {
    489             int index = get_index(n, level);
    490             if (index == -1) {
    491                 if (debug) {
    492                     out("unable to get index for " + n + "at level: " + level + ", adding content to branch: " + this);
    493                 }
    494                 this.__add_content(n);
    495                 return this;
    496             }
    497             if (debug) {
    498                 out("[" + level + "]: " + n +
    499                         " index " + index + " levelquad:" + this.quads() + " level bbox:" + this.bbox());
    500                 out("   put in child["+index+"]");
    501             }
    502             if (children[index] == null) {
    503                 children[index] = new QBLevel(this, index);
    504             }
    505             children[index].add(n);
    506             return this;
    507         }
     434                __add_content(o);
     435                if (isLeaf() && content.size() > MAX_OBJECTS_PER_LEVEL && level < QuadTiling.NR_LEVELS) {
     436                    __split();
     437                }
     438            }
     439        }
     440
     441        void add(T o) {
     442            synchronized (split_lock) {
     443                findBucket(o.getBBox()).doAdd(o);
     444            }
     445        }
     446
    508447        private List<T> search(BBox search_bbox)
    509448        {
     
    667606    public boolean add(T n)
    668607    {
    669         if (debug) {
    670             out("QuadBuckets() add: " + n + " size now: " + this.size());
    671         }
    672         int before_size = -1;
    673         if (consistency_testing) {
    674             before_size = root.size();
    675         }
    676         boolean ret;
    677         // A way with no nodes will have an infinitely large
    678         // bounding box.  Just stash it in the root node.
    679         if (!n.isUsable()) {
    680             synchronized (split_lock) {
    681                 ret = root.__add_content(n);
    682             }
    683         } else {
    684             ret = root.add(n);
    685         }
    686         if (consistency_testing) {
    687             int end_size = root.size();
    688             if (ret) {
    689                 end_size--;
    690             }
    691             if (before_size != end_size) {
    692                 abort("size inconsistency before add: " + before_size + " after: " + end_size);
    693             }
    694         }
    695         if (debug) {
    696             out("QuadBuckets() add: " + n + " size after: " + this.size());
    697         }
    698         return ret;
    699     }
    700     public void reindex()
    701     {
    702         QBLevel newroot = new QBLevel();
    703         Iterator<T> i = this.iterator();
    704         while (i.hasNext()) {
    705             T o = i.next();
    706             newroot.add(o);
    707         }
    708         root = newroot;
     608
     609        root.add(n);
     610        return true;
    709611    }
    710612    public void unsupported()
Note: See TracChangeset for help on using the changeset viewer.