Index: trunk/src/org/openstreetmap/josm/data/coor/LatLon.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/coor/LatLon.java (revision 6177) +++ trunk/src/org/openstreetmap/josm/data/coor/LatLon.java (revision 6178) @@ -36,4 +36,10 @@ public static final int MAX_SERVER_DIGITS = 7; + /** + * The (0,0) coordinates. + * @since 6178 + */ + public static final LatLon ZERO = new LatLon(0, 0); + private static DecimalFormat cDmsMinuteFormatter = new DecimalFormat("00"); private static DecimalFormat cDmsSecondFormatter = new DecimalFormat("00.0"); Index: trunk/src/org/openstreetmap/josm/data/osm/BBox.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/osm/BBox.java (revision 6177) +++ trunk/src/org/openstreetmap/josm/data/osm/BBox.java (revision 6178) @@ -2,7 +2,5 @@ package org.openstreetmap.josm.data.osm; -import java.util.ArrayList; import java.util.Arrays; -import java.util.List; import org.openstreetmap.josm.data.Bounds; Index: trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (revision 6177) +++ trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (revision 6178) @@ -2,5 +2,4 @@ package org.openstreetmap.josm.data.osm; -import java.lang.reflect.Array; import java.util.ArrayList; import java.util.Arrays; @@ -20,6 +19,5 @@ * */ -public class QuadBuckets implements Collection -{ +public class QuadBuckets implements Collection { private static final boolean consistency_testing = false; private static final int NW_INDEX = 1; @@ -33,36 +31,44 @@ public static final int MAX_OBJECTS_PER_LEVEL = 16; - - class QBLevel - { - final int level; + + static class QBLevel { + private final int level; + private final int index; private final BBox bbox; - final long quad; - final QBLevel parent; + private final long quad; + private final QBLevel parent; private boolean isLeaf = true; - public List content; - public QBLevel nw, ne, sw, se; - - private QBLevel getChild(int index) { + private List content; + // child order by index is sw, nw, se, ne + private QBLevel nw, ne, sw, se; + private boolean hasChild; + + private final QuadBuckets buckets; + + private QBLevel getChild(int index) { switch (index) { case NE_INDEX: if (ne == null) { - ne = new QBLevel(this, index); + ne = new QBLevel(this, index, buckets); + hasChild = true; } return ne; case NW_INDEX: if (nw == null) { - nw = new QBLevel(this, index); + nw = new QBLevel(this, index, buckets); + hasChild = true; } return nw; case SE_INDEX: if (se == null) { - se = new QBLevel(this, index); + se = new QBLevel(this, index, buckets); + hasChild = true; } return se; case SW_INDEX: if (sw == null) { - sw = new QBLevel(this, index); + sw = new QBLevel(this, index, buckets); + hasChild = true; } return sw; @@ -72,37 +78,32 @@ } - 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. - @SuppressWarnings("unchecked") - 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; + @SuppressWarnings("unchecked") + private QBLevel[] getChildren() { + return new QBLevel[] {sw, nw, se, ne}; } @Override - public String toString() { - return super.toString()+ "["+level+"]: " + bbox(); - } - + public String toString() { + return super.toString() + "[" + level + "]: " + bbox(); + } + /** * Constructor for root node */ - public QBLevel() { + public QBLevel(final QuadBuckets buckets) { level = 0; + index = 0; quad = 0; parent = null; bbox = new BBox(-180, 90, 180, -90); - } - - public QBLevel(QBLevel parent, int parent_index) { + this.buckets = buckets; + } + + public QBLevel(QBLevel parent, int parent_index, final QuadBuckets buckets) { this.parent = parent; this.level = parent.level + 1; + this.index = parent_index; + this.buckets = buckets; + int shift = (QuadTiling.NR_LEVELS - level) * 2; long mult = 1; @@ -110,5 +111,5 @@ if (shift >= 30) { shift -= 30; - mult = 1<<30; + mult = 1 << 30; } long this_quadpart = mult * (parent_index << shift); @@ -125,5 +126,5 @@ } - QBLevel findBucket(BBox bbox) { + QBLevel findBucket(BBox bbox) { if (!hasChildren()) return this; @@ -164,5 +165,5 @@ content = null; - for (T o: tmpcontent) { + for (T o : tmpcontent) { int index = o.getBBox().getIndex(level); if (index == -1) { @@ -184,10 +185,14 @@ return ret; } - - boolean matches(T o, BBox search_bbox) { - // This can be optimized when o is a node + + boolean matches(final T o, final BBox search_bbox) { + if (o instanceof Node){ + final LatLon latLon = ((Node)o).getCoor(); + // node without coords -> bbox[0,0,0,0] + return search_bbox.bounds(latLon != null ? latLon : LatLon.ZERO); + } return o.getBBox().intersects(search_bbox); } - + private void search_contents(BBox search_bbox, List result) { /* @@ -204,8 +209,8 @@ } } - + /* * This is stupid. I tried to have a QBLeaf and QBBranch - * class decending from a QBLevel. It's more than twice + * class descending from a QBLevel. It's more than twice * as slow. So, this throws OO out the window, but it * is fast. Runtime type determination must be slow. @@ -214,35 +219,20 @@ return isLeaf; } - + boolean hasChildren() { - return nw != null || ne != null || sw != null || se != null; - } - - QBLevel next_sibling() { - boolean found_me = false; - if (parent == null) - return null; - for (QBLevel sibling : parent.getChildren()) { - if (sibling == null) { - continue; - } - // We're looking for the *next* child after us. - if (sibling == this) { - found_me = true; - continue; - } - if (found_me) - return sibling; - } - return null; - } - + return hasChild; + } + + QBLevel next_sibling() { + return (parent == null) ? null : parent.firstSiblingOf(this); + } + boolean hasContent() { return content != null; } - - QBLevel nextSibling() { - QBLevel next = this; - QBLevel sibling = next.next_sibling(); + + QBLevel nextSibling() { + QBLevel next = this; + QBLevel sibling = next.next_sibling(); // Walk back up the tree to find the // next sibling node. It may be either @@ -258,25 +248,37 @@ return next; } - - QBLevel firstChild() { - QBLevel ret = null; - for (QBLevel child : getChildren()) { - if (child == null) { - continue; - } - ret = child; - break; - } - return ret; - } - - QBLevel nextNode() { + + QBLevel firstChild() { + if (sw != null) + return sw; + if (nw != null) + return nw; + if (se != null) + return se; + return ne; + } + + QBLevel firstSiblingOf(final QBLevel child) { + switch (child.index) { + case SW_INDEX: + if (nw != null) + return nw; + case NW_INDEX: + if (se != null) + return se; + case SE_INDEX: + return ne; + } + return null; + } + + QBLevel nextNode() { if (!this.hasChildren()) return this.nextSibling(); return this.firstChild(); } - - QBLevel nextContentNode() { - QBLevel next = this.nextNode(); + + QBLevel nextContentNode() { + QBLevel next = this.nextNode(); if (next == null) return next; @@ -290,5 +292,5 @@ if (!matches(o, this.bbox())) { o.getBBox().getIndex(level); - o.getBBox().getIndex(level-1); + o.getBBox().getIndex(level - 1); int nr = 0; abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox()); @@ -309,5 +311,5 @@ return; else if (bbox().bounds(search_bbox)) { - search_cache = this; + buckets.search_cache = this; } @@ -331,11 +333,11 @@ } } - + public String quads() { return Long.toHexString(quad); } - - int index_of(QBLevel find_this) { - QBLevel[] children = getChildren(); + + int index_of(QBLevel find_this) { + QBLevel[] children = getChildren(); for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) { if (children[i] == find_this) @@ -344,5 +346,5 @@ return -1; } - + double width() { return bbox.width(); @@ -356,5 +358,5 @@ return bbox; } - + /* * This gives the coordinate of the bottom-left @@ -364,5 +366,5 @@ return QuadTiling.tile2LatLon(this.quad); } - + void remove_from_parent() { if (parent == null) @@ -387,5 +389,5 @@ } } - + boolean canRemove() { if (content != null && !content.isEmpty()) @@ -397,6 +399,6 @@ } - private QBLevel root; - private QBLevel search_cache; + private QBLevel root; + private QBLevel search_cache; private int size; @@ -407,12 +409,12 @@ clear(); } - - @Override - public void clear() { - root = new QBLevel(); + + @Override + public void clear() { + root = new QBLevel(this); search_cache = null; size = 0; } - + @Override public boolean add(T n) { @@ -433,5 +435,5 @@ return true; } - + @Override public boolean removeAll(Collection objects) { @@ -442,5 +444,5 @@ return changed; } - + @Override public boolean addAll(Collection objects) { @@ -451,5 +453,5 @@ return changed; } - + @Override public boolean containsAll(Collection objects) { @@ -460,10 +462,11 @@ return true; } - + @Override public boolean remove(Object o) { - @SuppressWarnings("unchecked") T t = (T) o; + @SuppressWarnings("unchecked") + T t = (T) o; search_cache = null; // Search cache might point to one of removed buckets - QBLevel bucket = root.findBucket(t.getBBox()); + QBLevel bucket = root.findBucket(t.getBBox()); if (bucket.remove_content(t)) { size--; @@ -472,9 +475,10 @@ return false; } - + @Override public boolean contains(Object o) { - @SuppressWarnings("unchecked") T t = (T) o; - QBLevel bucket = root.findBucket(t.getBBox()); + @SuppressWarnings("unchecked") + T t = (T) o; + QBLevel bucket = root.findBucket(t.getBBox()); return bucket != null && bucket.content != null && bucket.content.contains(t); } @@ -487,25 +491,25 @@ return a; } - + @Override public Object[] toArray() { return this.toArrayList().toArray(); } - + @Override public A[] toArray(A[] template) { return this.toArrayList().toArray(template); } - - class QuadBucketIterator implements Iterator - { - QBLevel current_node; + + class QuadBucketIterator implements Iterator { + QBLevel current_node; int content_index; int iterated_over; - QBLevel next_content_node(QBLevel q) { + + QBLevel next_content_node(QBLevel q) { if (q == null) return null; - QBLevel orig = q; - QBLevel next; + QBLevel orig = q; + QBLevel next; next = q.nextContentNode(); //if (consistency_testing && (orig == next)) @@ -515,5 +519,5 @@ return next; } - + public QuadBucketIterator(QuadBuckets qb) { if (!qb.root.hasChildren() || qb.root.hasContent()) { @@ -524,5 +528,5 @@ iterated_over = 0; } - + @Override public boolean hasNext() { @@ -531,10 +535,9 @@ return true; } - + T peek() { if (current_node == null) return null; - while((current_node.content == null) || - (content_index >= current_node.content.size())) { + while ((current_node.content == null) || (content_index >= current_node.content.size())) { content_index = 0; current_node = next_content_node(current_node); @@ -547,5 +550,5 @@ return current_node.content.get(content_index); } - + @Override public T next() { @@ -555,5 +558,5 @@ return ret; } - + @Override public void remove() { @@ -567,5 +570,5 @@ } } - + @Override public Iterator iterator() { @@ -584,5 +587,5 @@ return false; } - + public List search(BBox search_bbox) { List ret = new ArrayList(); @@ -607,5 +610,5 @@ // Save parent because search_cache might change during search call - QBLevel tmp = search_cache.parent; + QBLevel tmp = search_cache.parent; search_cache.search(search_bbox, ret); @@ -624,5 +627,5 @@ } - private void printTreeRecursive(QBLevel level, int indent) { + private void printTreeRecursive(QBLevel level, int indent) { if (level == null) { printIndented(indent, ""); @@ -631,9 +634,9 @@ printIndented(indent, level); if (level.hasContent()) { - for (T o:level.content) { + for (T o : level.content) { printIndented(indent, o); } } - for (QBLevel child:level.getChildren()) { + for (QBLevel child : level.getChildren()) { printTreeRecursive(child, indent + 2); } @@ -641,5 +644,5 @@ private void printIndented(int indent, Object msg) { - for (int i=0; i