Index: trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java (revision 6170) +++ trunk/src/org/openstreetmap/josm/data/coor/QuadTiling.java (revision 6171) @@ -9,12 +9,11 @@ public static final int TILES_PER_LEVEL_SHIFT = 2; // Has to be 2. Other parts of QuadBuckets code rely on it public static final int TILES_PER_LEVEL = 1<> total_shift)); } - static public int index(LatLon coor, int level) { - // The nodes that don't return coordinates will all get - // stuck in a single tile. Hopefully there are not too - // many of them + + /** + * Returns quad tiling index for given coordinates and level. + * + * @param coor coordinates + * @param level level + * + * @return quad tiling index for given coordinates and level. + * @since 2263 + */ + public static int index(LatLon coor, int level) { + // The nodes that don't return coordinates will all get stuck in a single tile. + // Hopefully there are not too many of them if (coor == null) return 0; - long x = lon2x(coor.lon()); - long y = lat2y(coor.lat()); + return index(coor.lat(), coor.lon(), level); + } + + /** + * Returns quad tiling index for given coordinates and level. + * + * @param lat latitude + * @param lon longitude + * @param level level + * + * @return quad tiling index for given coordinates and level. + * @since 6171 + */ + public static int index(final double lat, final double lon, final int level) { + long x = lon2x(lon); + long y = lat2y(lat); int shift = NR_LEVELS-level-1; return (int)((x >> shift & 1) * 2 + (y >> shift & 1)); Index: trunk/src/org/openstreetmap/josm/data/osm/BBox.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/osm/BBox.java (revision 6170) +++ trunk/src/org/openstreetmap/josm/data/osm/BBox.java (revision 6171) @@ -8,4 +8,5 @@ import org.openstreetmap.josm.data.Bounds; import org.openstreetmap.josm.data.coor.LatLon; +import org.openstreetmap.josm.data.coor.QuadTiling; import org.openstreetmap.josm.tools.Utils; @@ -152,20 +153,4 @@ } - /** - * Returns a list of all 4 corners of the bbox rectangle. - */ - public List points() { - LatLon p1 = new LatLon(ymin, xmin); - LatLon p2 = new LatLon(ymin, xmax); - LatLon p3 = new LatLon(ymax, xmin); - LatLon p4 = new LatLon(ymax, xmax); - List ret = new ArrayList(4); - ret.add(p1); - ret.add(p2); - ret.add(p3); - ret.add(p4); - return ret; - } - public LatLon getTopLeft() { return new LatLon(ymax, xmin); @@ -178,4 +163,23 @@ public LatLon getCenter() { return new LatLon(ymin + (ymax-ymin)/2.0, xmin + (xmax-xmin)/2.0); + } + + int getIndex(final int level) { + + int idx1 = QuadTiling.index(ymin, xmin, level); + + final int idx2 = QuadTiling.index(ymin, xmax, level); + if (idx1 == -1) idx1 = idx2; + else if (idx1 != idx2) return -1; + + final int idx3 = QuadTiling.index(ymax, xmin, level); + if (idx1 == -1) idx1 = idx3; + else if (idx1 != idx3) return -1; + + final int idx4 = QuadTiling.index(ymax, xmax, level); + if (idx1 == -1) idx1 = idx4; + else if (idx1 != idx4) return -1; + + return idx1; } Index: trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java =================================================================== --- trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (revision 6170) +++ trunk/src/org/openstreetmap/josm/data/osm/QuadBuckets.java (revision 6171) @@ -9,4 +9,5 @@ import java.util.List; +import org.openstreetmap.josm.Main; import org.openstreetmap.josm.data.coor.LatLon; import org.openstreetmap.josm.data.coor.QuadTiling; @@ -21,5 +22,4 @@ public class QuadBuckets implements Collection { - //private static boolean debug = false; private static final boolean consistency_testing = false; private static final int NW_INDEX = 1; @@ -28,34 +28,10 @@ private static final int SW_INDEX = 0; - static void abort(String s) - { + static void abort(String s) { throw new AssertionError(s); } - static void out(String s) - { - System.out.println(s); - } - // periodic output - long last_out = -1; - void pout(String s) - { - long now = System.currentTimeMillis(); - if (now - last_out < 300) - return; - last_out = now; - System.out.print(s + "\r"); - } - void pout(String s, int i, int total) - { - long now = System.currentTimeMillis(); - if ((now - last_out < 300) && - ((i+1) < total)) - return; - last_out = now; - // cast to float to keep the output size down - System.out.print(s + " " + (float)((i+1)*100.0/total) + "% done \r"); - } public static final int MAX_OBJECTS_PER_LEVEL = 16; + class QBLevel { @@ -115,4 +91,5 @@ return super.toString()+ "["+level+"]: " + bbox(); } + /** * Constructor for root node @@ -130,6 +107,5 @@ int shift = (QuadTiling.NR_LEVELS - level) * 2; long mult = 1; - // Java blows the big one. It seems to wrap when - // you shift by > 31 + // Java blows the big one. It seems to wrap when you shift by > 31 if (shift >= 30) { shift -= 30; @@ -139,10 +115,4 @@ this.quad = parent.quad | this_quadpart; this.bbox = calculateBBox(); // calculateBBox reference quad - /*if (debug) { - out("new level["+this.level+"] bbox["+parent_index+"]: " + this.bbox() - + " coor: " + this.coor() - + " quadpart: " + Long.toHexString(this_quadpart) - + " quad: " + Long.toHexString(this.quad)); - }*/ } @@ -159,5 +129,5 @@ return this; else { - int index = get_index(bbox, level); + int index = bbox.getIndex(level); if (index == -1) return this; @@ -166,6 +136,5 @@ } - boolean remove_content(T o) - { + boolean remove_content(T o) { // If two threads try to remove item at the same time from different buckets of this QBLevel, // it might happen that one thread removes bucket but don't remove parent because it still sees @@ -184,29 +153,5 @@ return ret; } - // Get the correct index for the given primitive - // at the given level. If the primitive can not - // fit into a single quad at this level, return -1 - int get_index(BBox bbox, int level) { - int index = -1; - for (LatLon c : bbox.points()) { - /*if (debug) { - out("getting index for point: " + c); - }*/ - if (index == -1) { - index = QuadTiling.index(c, level); - /*if (debug) { - out("set initial index to: " + index); - }*/ - continue; - } - int another_index = QuadTiling.index(c, level); - /*if (debug) { - out("other point index: " + another_index); - }*/ - if (another_index != index) - return -1; - } - return index; - } + /* * There is a race between this and qb.nextContentNode(). @@ -216,14 +161,9 @@ */ void __split() { - /*if (debug) { - out("splitting "+this.bbox()+" level "+level+" with " - + content.size() + " entries (my dimensions: " - + this.bbox().width()+", "+this.bbox().height()+")"); - }*/ List tmpcontent = content; content = null; for (T o: tmpcontent) { - int index = get_index(o.getBBox(), level); + int index = o.getBBox().getIndex(level); if (index == -1) { __add_content(o); @@ -235,29 +175,20 @@ } - boolean __add_content(T o) - { + boolean __add_content(T o) { boolean ret = false; - // The split_lock will keep two concurrent - // calls from overwriting content + // The split_lock will keep two concurrent calls from overwriting content if (content == null) { content = new ArrayList(); } ret = content.add(o); - /*if (debug && !this.isLeaf()) { - pout("added "+o.getClass().getName()+" to non-leaf with size: " + content.size()); - }*/ return ret; } - boolean matches(T o, BBox search_bbox) - { + + boolean matches(T o, BBox search_bbox) { // This can be optimized when o is a node - //return search_bbox.bounds(coor)); return o.getBBox().intersects(search_bbox); } - private void search_contents(BBox search_bbox, List result) - { - /*if (debug) { - out("searching contents (size: " + content == null?"":content.size() + ") for " + search_bbox); - }*/ + + private void search_contents(BBox search_bbox, List result) { /* * It is possible that this was created in a split @@ -272,59 +203,44 @@ } } - /*if (debug) { - out("done searching quad " + Long.toHexString(this.quad)); - }*/ - } + } + /* - * This is stupid. I tried to have a QBLeaf and QBBranch - * class decending 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. + * This is stupid. I tried to have a QBLeaf and QBBranch + * class decending 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. */ boolean isLeaf() { return isLeaf; } + boolean hasChildren() { return nw != null || ne != null || sw != null || se != null; } - QBLevel next_sibling() - { + QBLevel next_sibling() { boolean found_me = false; if (parent == null) return null; - int __nr = 0; for (QBLevel sibling : parent.getChildren()) { - __nr++; - int nr = __nr-1; if (sibling == null) { - /*if (debug) { - out("[" + this.level + "] null child nr: " + nr); - }*/ continue; } - // We're looking for the *next* child - // after us. + // We're looking for the *next* child after us. if (sibling == this) { - /*if (debug) { - out("[" + this.level + "] I was child nr: " + nr); - }*/ found_me = true; continue; } if (found_me) - /*if (debug) { - out("[" + this.level + "] next sibling was child nr: " + nr); - }*/ return sibling; } return null; } - boolean hasContent() - { + + boolean hasContent() { return content != null; } - QBLevel nextSibling() - { + + QBLevel nextSibling() { QBLevel next = this; QBLevel sibling = next.next_sibling(); @@ -333,7 +249,4 @@ // a leaf or branch. while (sibling == null) { - /*if (debug) { - out("no siblings at level["+next.level+"], moving to parent"); - }*/ next = next.parent; if (next == null) { @@ -345,6 +258,6 @@ return next; } - QBLevel firstChild() - { + + QBLevel firstChild() { QBLevel ret = null; for (QBLevel child : getChildren()) { @@ -357,12 +270,12 @@ return ret; } - QBLevel nextNode() - { + + QBLevel nextNode() { if (!this.hasChildren()) return this.nextSibling(); return this.firstChild(); } - QBLevel nextContentNode() - { + + QBLevel nextContentNode() { QBLevel next = this.nextNode(); if (next == null) @@ -376,12 +289,7 @@ if (consistency_testing) { if (!matches(o, this.bbox())) { - /*out("-----------------------------"); - debug = true;*/ - get_index(o.getBBox(), level); - get_index(o.getBBox(), level-1); + o.getBBox().getIndex(level); + o.getBBox().getIndex(level-1); int nr = 0; - /*for (QBLevel sibling : parent.getChildren()) { - out("sibling["+ (nr++) +"]: " + sibling.bbox() + " this: " + (this==sibling)); - }*/ abort("\nobject " + o + " does not belong in node at level: " + level + " bbox: " + this.bbox()); } @@ -397,14 +305,6 @@ } - private void search(BBox search_bbox, List result) - { - /*if (debug) { - System.out.print("[" + level + "] qb bbox: " + this.bbox() + " "); - }*/ + private void search(BBox search_bbox, List result) { if (!this.bbox().intersects(search_bbox)) - /*if (debug) { - out("miss " + Long.toHexString(this.quad)); - //QuadTiling.tile2xy(this.quad); - }*/ return; else if (bbox().bounds(search_bbox)) { @@ -416,9 +316,4 @@ } - /*if (debug) { - out("hit " + this.quads()); - out("[" + level + "] not leaf, moving down"); - }*/ - //TODO Coincidence vector should be calculated here and only buckets that match search_bbox should be checked @@ -436,10 +331,10 @@ } } - public String quads() - { + + public String quads() { return Long.toHexString(quad); } - int index_of(QBLevel find_this) - { + + int index_of(QBLevel find_this) { QBLevel[] children = getChildren(); for (int i = 0; i < QuadTiling.TILES_PER_LEVEL; i++) { @@ -449,4 +344,5 @@ return -1; } + double width() { return bbox.width(); @@ -460,14 +356,14 @@ return bbox; } + /* * This gives the coordinate of the bottom-left * corner of the box */ - LatLon coor() - { + LatLon coor() { return QuadTiling.tile2LatLon(this.quad); } - void remove_from_parent() - { + + void remove_from_parent() { if (parent == null) return; @@ -491,6 +387,6 @@ } } - boolean canRemove() - { + + boolean canRemove() { if (content != null && !content.isEmpty()) return false; @@ -505,8 +401,11 @@ private int size; - public QuadBuckets() - { + /** + * Constructs a new {@code QuadBuckets}. + */ + public QuadBuckets() { clear(); } + @Override public void clear() { @@ -514,9 +413,6 @@ search_cache = null; size = 0; - /*if (debug) { - out("QuadBuckets() cleared: " + this); - out("root: " + root + " level: " + root.level + " bbox: " + root.bbox()); - }*/ - } + } + @Override public boolean add(T n) { @@ -527,6 +423,5 @@ @Override - public boolean retainAll(Collection objects) - { + public boolean retainAll(Collection objects) { for (T o : this) { if (objects.contains(o)) { @@ -538,7 +433,7 @@ return true; } - @Override - public boolean removeAll(Collection objects) - { + + @Override + public boolean removeAll(Collection objects) { boolean changed = false; for (Object o : objects) { @@ -547,7 +442,7 @@ return changed; } - @Override - public boolean addAll(Collection objects) - { + + @Override + public boolean addAll(Collection objects) { boolean changed = false; for (T o : objects) { @@ -556,7 +451,7 @@ return changed; } - @Override - public boolean containsAll(Collection objects) - { + + @Override + public boolean containsAll(Collection objects) { for (Object o : objects) { if (!this.contains(o)) @@ -565,4 +460,5 @@ return true; } + @Override public boolean remove(Object o) { @@ -576,4 +472,5 @@ return false; } + @Override public boolean contains(Object o) { @@ -583,25 +480,22 @@ } - public ArrayList toArrayList() - { + public ArrayList toArrayList() { ArrayList a = new ArrayList(); for (T n : this) { a.add(n); } - /*if (debug) { - out("returning array list with size: " + a.size()); - }*/ return a; } - @Override - public Object[] toArray() - { + + @Override + public Object[] toArray() { return this.toArrayList().toArray(); } - @Override - public A[] toArray(A[] template) - { + + @Override + public A[] toArray(A[] template) { return this.toArrayList().toArray(template); } + class QuadBucketIterator implements Iterator { @@ -609,6 +503,5 @@ int content_index; int iterated_over; - QBLevel next_content_node(QBLevel q) - { + QBLevel next_content_node(QBLevel q) { if (q == null) return null; @@ -622,9 +515,6 @@ return next; } - public QuadBucketIterator(QuadBuckets qb) - { - /*if (debug) { - out(this + " is a new iterator qb: " + qb + " size: " + qb.size()); - }*/ + + public QuadBucketIterator(QuadBuckets qb) { if (!qb.root.hasChildren() || qb.root.hasContent()) { current_node = qb.root; @@ -632,31 +522,19 @@ current_node = next_content_node(qb.root); } - /*if (debug) { - out("\titerator first leaf: " + current_node); - }*/ iterated_over = 0; } + @Override - public boolean hasNext() - { + public boolean hasNext() { if (this.peek() == null) - /*if (debug) { - out(this + " no hasNext(), but iterated over so far: " + iterated_over); - }*/ return false; return true; } - T peek() - { + + T peek() { if (current_node == null) - /*if (debug) { - out("null current leaf, nowhere to go"); - }*/ return null; while((current_node.content == null) || (content_index >= current_node.content.size())) { - /*if (debug) { - out("moving to next leaf"); - }*/ content_index = 0; current_node = next_content_node(current_node); @@ -666,29 +544,18 @@ } if (current_node == null || current_node.content == null) - /*if (debug) { - out("late nowhere to go " + current_node); - }*/ return null; return current_node.content.get(content_index); } + @Override - public T next() - { + public T next() { T ret = peek(); content_index++; - /*if (debug) { - out("iteration["+iterated_over+"] " + content_index + " leaf: " + current_node); - }*/ iterated_over++; - if (ret == null) { - /*if (debug) { - out(this + " no next node, but iterated over so far: " + iterated_over); - }*/ - } return ret; } + @Override - public void remove() - { + public void remove() { // two uses // 1. Back up to the thing we just returned @@ -700,9 +567,10 @@ } } - @Override - public Iterator iterator() - { + + @Override + public Iterator iterator() { return new QuadBucketIterator(this); } + @Override public int size() { @@ -711,18 +579,13 @@ @Override - public boolean isEmpty() - { + public boolean isEmpty() { if (this.size() == 0) return true; return false; } + public List search(BBox search_bbox) { - /*if (debug) { - out("qb root search at " + search_bbox); - out("root bbox: " + root.bbox()); - }*/ List ret = new ArrayList(); - // Doing this cuts down search cost on a real-life data - // set by about 25% + // Doing this cuts down search cost on a real-life data set by about 25% boolean cache_searches = true; if (cache_searches) { @@ -730,22 +593,12 @@ search_cache = root; } - // Walk back up the tree when the last - // search spot can not cover the current - // search + // Walk back up the tree when the last search spot can not cover the current search while (search_cache != null && !search_cache.bbox().bounds(search_bbox)) { - /*if (debug) { - out("bbox: " + search_bbox); - out("search_cache: " + search_cache + " level: " + search_cache.level); - out("search_cache.bbox(): " + search_cache.bbox()); - }*/ search_cache = search_cache.parent; - /*if (debug) { - out("new search_cache: " + search_cache); - }*/ } if (search_cache == null) { search_cache = root; - out("bbox: " + search_bbox + " is out of the world"); + Main.info("bbox: " + search_bbox + " is out of the world"); } } else { @@ -764,7 +617,4 @@ tmp = tmp.parent; } - /*if (debug) { - out("search of QuadBuckets for " + search_bbox + " ret len: " + ret.size()); - }*/ return ret; }