Index: /trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java =================================================================== --- /trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (revision 3475) +++ /trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (revision 3476) @@ -20,4 +20,8 @@ private static boolean debug = false; private static final boolean consistency_testing = false; + private static final int NW_INDEX = 1; + private static final int NE_INDEX = 3; + private static final int SE_INDEX = 2; + private static final int SW_INDEX = 0; /* * Functions prefixed with __ need locking before @@ -62,10 +66,52 @@ final long quad; final QBLevel parent; + private boolean isLeaf = true; public List content; - public QBLevel children[]; + public QBLevel nw, ne, sw, se; + + private QBLevel getChild(int index) { + switch (index) { + case NE_INDEX: + if (ne == null) { + ne = new QBLevel(this, index); + } + return ne; + case NW_INDEX: + if (nw == null) { + nw = new QBLevel(this, index); + } + return nw; + case SE_INDEX: + if (se == null) { + se = new QBLevel(this, index); + } + return se; + case SW_INDEX: + if (sw == null) { + sw = new QBLevel(this, index); + } + return sw; + default: + return null; + } + } + + private QBLevel[] getChildren() { + // This is ugly and hackish. But, it seems to work, + // and using an ArrayList here seems to cost us + // a significant performance penalty -- 50% in my + // testing. Child access is one of the single + // hottest code paths in this entire class. + QBLevel[] result = (QBLevel[]) Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL); + result[NW_INDEX] = nw; + result[NE_INDEX] = ne; + result[SW_INDEX] = sw; + result[SE_INDEX] = se; + return result; + } + @Override - public String toString() - { + public String toString() { return super.toString()+ "["+level+"]: " + bbox(); } @@ -117,8 +163,5 @@ if (index == -1) return this; - if (children[index] == null) { - children[index] = new QBLevel(this, index); - } - return children[index].findBucket(bbox); + return getChild(index).findBucket(bbox); } } @@ -144,13 +187,4 @@ } } - QBLevel[] newChildren() - { - // This is ugly and hackish. But, it seems to work, - // and using an ArrayList here seems to cost us - // a significant performance penalty -- 50% in my - // testing. Child access is one of the single - // hottest code paths in this entire class. - return (QBLevel[])Array.newInstance(this.getClass(), QuadTiling.TILES_PER_LEVEL); - } // Get the correct index for the given primitive // at the given level. If the primitive can not @@ -190,19 +224,16 @@ + this.bbox().width()+", "+this.bbox().height()+")"); } - // deferring allocation of children until use - // seems a bit faster - //for (int i = 0; i < TILES_PER_LEVEL; i++) - // children[i] = new QBLevel(this, i); List tmpcontent = content; content = null; - children = newChildren(); + for (T o: tmpcontent) { - add(o); - } - if (!hasChildren()) { - // All items stay at this level (get_index == -1). Create at least first child to keep the contract - // that at least one child always exists - children[0] = new QBLevel(this, 0); - } + int index = get_index(o.getBBox(), level); + if (index == -1) { + __add_content(o); + } else { + getChild(index).doAdd(o); + } + } + isLeaf = false; // It's not enough to check children because all items could end up in this level (index == -1) } @@ -254,10 +285,11 @@ * is fast. Runtime type determination must be slow. */ - boolean isLeaf() - { - if (children == null) - return true; - return false; - } + boolean isLeaf() { + return isLeaf; + } + boolean hasChildren() { + return nw != null || ne != null || sw != null || se != null; + } + QBLevel next_sibling() { @@ -265,8 +297,6 @@ if (parent == null) return null; - if (parent.children == null) - return null; int __nr = 0; - for (QBLevel sibling : parent.children) { + for (QBLevel sibling : parent.getChildren()) { __nr++; int nr = __nr-1; @@ -325,5 +355,5 @@ { QBLevel ret = null; - for (QBLevel child : this.children) { + for (QBLevel child : getChildren()) { if (child == null) { continue; @@ -358,5 +388,5 @@ get_index(o.getBBox(), level-1); int nr = 0; - for (QBLevel sibling : parent.children) { + for (QBLevel sibling : parent.getChildren()) { out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling)); } @@ -389,5 +419,8 @@ } return; - } + } else if (bbox().bounds(search_bbox)) { + search_cache = this; + } + if (this.hasContent()) { search_contents(search_bbox, result); @@ -403,26 +436,18 @@ out("[" + level + "] not leaf, moving down"); } - for (int i = 0; i < children.length; i++) { - QBLevel q = children[i]; - if (debug) { - out("child["+i+"]: " + q); - } - if (q == null) { - continue; - } - if (debug) { - System.out.print(i+": "); - } - q.search(search_bbox, result); - if (q.bbox().bounds(search_bbox)) { - search_cache = q; - // optimization: do not continue searching - // other tiles if this one wholly contained - // what we were looking for. - if (debug) { - out("break early"); - } - break; - } + + //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked + + if (nw != null) { + nw.search(search_bbox, result); + } + if (ne != null) { + ne.search(search_bbox, result); + } + if (se != null) { + se.search(search_bbox, result); + } + if (sw != null) { + sw.search(search_bbox, result); } } @@ -436,4 +461,5 @@ return -1; + QBLevel[] children = getChildren(); for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) { if (children[i] == find_this) @@ -461,15 +487,4 @@ return QuadTiling.tile2LatLon(this.quad); } - boolean hasChildren() - { - if (children == null) - return false; - - for (QBLevel child : children) { - if (child != null) - return true; - } - return false; - } void remove_from_parent() { @@ -477,22 +492,18 @@ return; - int nr_siblings = 0; - for (int i = 0; i < parent.children.length; i++) { - QBLevel sibling = parent.children[i]; - if (sibling != null) { - nr_siblings++; - } - if (sibling != this) { - continue; - } - if (!canRemove()) { - abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.children)); - } - parent.children[i] = null; - nr_siblings--; - } - if (nr_siblings == 0) { - parent.children = null; - } + if (!canRemove()) { + abort("attempt to remove non-empty child: " + this.content + " " + Arrays.toString(this.getChildren())); + } + + if (parent.nw == this) { + parent.nw = null; + } else if (parent.ne == this) { + parent.ne = null; + } else if (parent.sw == this) { + parent.sw = null; + } else if (parent.se == this) { + parent.se = null; + } + if (parent.canRemove()) { parent.remove_from_parent(); @@ -791,8 +802,6 @@ } } - if (level.children != null) { - for (QBLevel child:level.children) { - printTreeRecursive(child, indent + 2); - } + for (QBLevel child:level.getChildren()) { + printTreeRecursive(child, indent + 2); } } Index: /trunk/test/unit/org/openstreetmap/josm/data/osm/QuadBucketsTest.java =================================================================== --- /trunk/test/unit/org/openstreetmap/josm/data/osm/QuadBucketsTest.java (revision 3475) +++ /trunk/test/unit/org/openstreetmap/josm/data/osm/QuadBucketsTest.java (revision 3476) @@ -4,6 +4,10 @@ import java.io.FileInputStream; import java.util.ArrayList; +import java.util.Collection; +import java.util.Iterator; import java.util.List; +import org.fest.reflect.core.Reflection; +import org.fest.reflect.reference.TypeRef; import org.junit.Assert; import org.junit.Test; @@ -20,17 +24,35 @@ List allWays = new ArrayList(ds.getWays()); List allRelations = new ArrayList(ds.getRelations()); + + QuadBuckets nodes = Reflection.field("nodes").ofType(new TypeRef>() {}).in(ds).get(); + QuadBuckets ways = Reflection.field("ways").ofType(new TypeRef>() {}).in(ds).get(); + Collection relations = Reflection.field("relations").ofType(new TypeRef>() {}).in(ds).get(); + + int expectedCount = allNodes.size(); for (OsmPrimitive o: allNodes) { ds.removePrimitive(o); + checkIterator(nodes, --expectedCount); } + expectedCount = allWays.size(); for (OsmPrimitive o: allWays) { ds.removePrimitive(o); + checkIterator(ways, --expectedCount); } for (OsmPrimitive o: allRelations) { ds.removePrimitive(o); } + Assert.assertTrue(nodes.isEmpty()); + Assert.assertTrue(ways.isEmpty()); + Assert.assertTrue(relations.isEmpty()); + } - Assert.assertTrue(ds.getNodes().isEmpty()); - Assert.assertTrue(ds.getWays().isEmpty()); - Assert.assertTrue(ds.getRelations().isEmpty()); + private void checkIterator(Collection col, int expectedCount) { + int count = 0; + Iterator it = col.iterator(); + while (it.hasNext()) { + count++; + it.next(); + } + Assert.assertEquals(expectedCount, count); }