Core reverse lookup code for caching the results of reverse-lookup operations.
--- core-dave/src/org/openstreetmap/josm/command/AddNodeToWayCommand.java | 4 core-dave/src/org/openstreetmap/josm/command/ReplaceNodeInWayCommand.java | 20 core-dave/src/org/openstreetmap/josm/data/osm/DataSet.java | 3 core-dave/src/org/openstreetmap/josm/gui/layer/OsmDataLayer.java | 6 core-dave/src/org/openstreetmap/josm/tools/ReverseLookup.java | 236 ++++++++++ 5 files changed, 257 insertions(+), 12 deletions(-) diff -puN src/org/openstreetmap/josm/command/AddNodeToWayCommand.java~reverselookup src/org/openstreetmap/josm/command/AddNodeToWayCommand.java --- core/src/org/openstreetmap/josm/command/AddNodeToWayCommand.java~reverselookup 2008-05-03 12:08:45.000000000 -0700 +++ core-dave/src/org/openstreetmap/josm/command/AddNodeToWayCommand.java 2008-05-03 12:08:45.000000000 -0700 @@ -47,7 +47,7 @@ public class AddNodeToWayCommand extends way.addNode(node); } else way.addNodeNr(location, node); - //Main.ds.rl.addWayToNodeMap(node, way); + ds.rl.addWayToNodeMap(node, way); way.modified = true; return true; } @@ -56,7 +56,7 @@ public class AddNodeToWayCommand extends Node removed = way.removeNode(location); if (removed != node) Main.debug("removed wrong node"); - //Main.ds.rl.removeWayFromNodeMap(removed, way); + ds.rl.removeWayFromNodeMap(removed, way); way.modified = this.getOrig(way).modified; } diff -puN src/org/openstreetmap/josm/command/ReplaceNodeInWayCommand.java~reverselookup src/org/openstreetmap/josm/command/ReplaceNodeInWayCommand.java --- core/src/org/openstreetmap/josm/command/ReplaceNodeInWayCommand.java~reverselookup 2008-05-03 12:08:45.000000000 -0700 +++ core-dave/src/org/openstreetmap/josm/command/ReplaceNodeInWayCommand.java 2008-05-03 12:08:45.000000000 -0700 @@ -48,16 +48,16 @@ public class ReplaceNodeInWayCommand ext @Override public boolean executeCommand() { super.executeCommand(); - ///ds.rl.check(node); - ///ds.rl.check(newNode); + ds.rl.check(node); + ds.rl.check(newNode); if (replace_at != -1) replaced_at = way.replaceNode(node, newNode, replace_at); else replaced_at = way.replaceNode(node, newNode); - ///ds.rl.removeWayFromNodeMap_nocheck(node, way); - ///ds.rl.addWayToNodeMap_nocheck(newNode, way); - ///ds.rl.check(node); - ///ds.rl.check(newNode); + ds.rl.removeWayFromNodeMap_nocheck(node, way); + ds.rl.addWayToNodeMap_nocheck(newNode, way); + ds.rl.check(node); + ds.rl.check(newNode); if (replaced_at < 0) { String location = ""; if (replace_at != -1) @@ -72,10 +72,10 @@ public class ReplaceNodeInWayCommand ext @Override public void undoCommand() { way.replaceNode(newNode, node, replaced_at); - ///ds.rl.removeWayFromNodeMap_nocheck(newNode, way); - ///ds.rl.addWayToNodeMap_nocheck(node, way); - ///ds.rl.check(node); - ///ds.rl.check(newNode); + ds.rl.removeWayFromNodeMap_nocheck(newNode, way); + ds.rl.addWayToNodeMap_nocheck(node, way); + ds.rl.check(node); + ds.rl.check(newNode); Way orig_way = (Way)this.getOrig(way); Main.debug("ReplaceNodeInWay() orig_way: " + orig_way); way.modified = orig_way.modified; diff -puN src/org/openstreetmap/josm/data/osm/DataSet.java~reverselookup src/org/openstreetmap/josm/data/osm/DataSet.java --- core/src/org/openstreetmap/josm/data/osm/DataSet.java~reverselookup 2008-05-03 12:08:45.000000000 -0700 +++ core-dave/src/org/openstreetmap/josm/data/osm/DataSet.java 2008-05-03 12:08:45.000000000 -0700 @@ -9,6 +9,7 @@ import java.util.LinkedList; import java.util.List; import org.openstreetmap.josm.data.SelectionChangedListener; +import org.openstreetmap.josm.tools.ReverseLookup; /** * DataSet is the data behind the application. It can consists of only a few @@ -202,4 +203,6 @@ public class DataSet implements Cloneabl ds.dataSources.add(new DataSource(source.bounds, source.origin)); return ds; } + + public ReverseLookup rl = new ReverseLookup(this); } diff -puN src/org/openstreetmap/josm/gui/layer/OsmDataLayer.java~reverselookup src/org/openstreetmap/josm/gui/layer/OsmDataLayer.java --- core/src/org/openstreetmap/josm/gui/layer/OsmDataLayer.java~reverselookup 2008-05-03 12:08:45.000000000 -0700 +++ core-dave/src/org/openstreetmap/josm/gui/layer/OsmDataLayer.java 2008-05-03 12:08:45.000000000 -0700 @@ -189,6 +189,11 @@ public class OsmDataLayer extends Layer } @Override public void mergeFrom(final Layer from) { + // Since the ReverseLookup is layer-private, it gets really + // hard to keep it consistent here since things are goign + // between layers, so just disabled it. + data.rl.disable(); + ((OsmDataLayer)from).data.rl.disable(); final MergeVisitor visitor = new MergeVisitor(data,((OsmDataLayer)from).data); for (final OsmPrimitive osm : ((OsmDataLayer)from).data.allPrimitives()) osm.visit(visitor); @@ -206,6 +211,7 @@ public class OsmDataLayer extends Layer JOptionPane.showMessageDialog(Main.parent,tr("There were conflicts during import.")); if (!dlg.isVisible()) dlg.action.actionPerformed(new ActionEvent(this, 0, "")); + data.rl.enable(); } @Override public boolean isMergable(final Layer other) { diff -puN src/org/openstreetmap/josm/tools/ReverseLookup.java~reverselookup src/org/openstreetmap/josm/tools/ReverseLookup.java --- core/src/org/openstreetmap/josm/tools/ReverseLookup.java~reverselookup 2008-05-03 12:08:45.000000000 -0700 +++ core-dave/src/org/openstreetmap/josm/tools/ReverseLookup.java 2008-05-03 12:08:45.000000000 -0700 @@ -0,0 +1,236 @@ +// License: GPL. Copyright 2007 by Immanuel Scholz and others +package org.openstreetmap.josm.tools; + +import java.util.*; + +import org.openstreetmap.josm.Main; +import org.openstreetmap.josm.data.osm.visitor.CollectBackReferencesVisitor; +import org.openstreetmap.josm.data.osm.*; + + +public class ReverseLookup { + private HashMap<Node,List<Way>> waysUsingNodeCache = null; + private int misses = 0; + private int hits = 0; + private DataSet ds; + + static boolean debug = false; + static int nr = 0; + int thisnr; + public ReverseLookup(DataSet set) + { + this.ds = set; + thisnr = nr++; + } + public List<Way> slowWaysUsingNode(Node n) + { + List<Way> ways = new ArrayList<Way>(); + CollectBackReferencesVisitor v = new CollectBackReferencesVisitor(ds, false); + n.visit(v); + for (OsmPrimitive ref : v.data) { + if (ref instanceof Way) + ways.add((Way)ref); + } + return ways; + } + + static String pref() { + String p = Main.pref.get("reverse-lookup"); + // for debugging // p = "never"; + if (p.length() == 0) + p = "cache"; + return p; + } + boolean enabled = true; + + static boolean pref_disabled() { + return pref().equals("never"); + } + static boolean pref_always() { + return pref().equals("always"); + } + static boolean pref_can_cache() { + if (pref_always()) + return true; + return pref().equals("cache"); + } + boolean can_cache() { + if (!enabled) + return false; + return pref_can_cache(); + } + boolean always() { + if (!enabled) + return false; + return pref_always(); + } + boolean disabled() { + if (!enabled) + return true; + return pref_disabled(); + } + public void disable() { + enabled = false; + waysUsingNodeCache = null; + } + public void enable() { + enabled = true; + } + private void enable_cache() + { + if (waysUsingNodeCache == null) + waysUsingNodeCache = new HashMap<Node,List<Way>>(); + } + private List<Way> fastWaysUsingNode(Node n) + { + //Main.debug(this.thisnr + " fastWaysUsingNode("+n.hashCode()+")"); + boolean debugme = false; + if (debugme) { + int i=0; + List<Way> wl; + for (Node ntmp : waysUsingNodeCache.keySet()) { + wl = waysUsingNodeCache.get(ntmp); + Main.debug("key nr: " + i + ": " + ntmp.hashCode() + + " wl: " + wl + "ntmp == n : " + (n == ntmp)); + i++; + } + } + + if (disabled()) { + //Main.debug("disabled, skipping out of fastWaysUsingNode()"); + return null; + } + List<Way> ways = waysUsingNodeCache.get(n); + if ((hits+misses+1)%10000 == 0) + Main.debug("fastWaysUsingNode("+pref()+":"+pref_always()+") hits: " + hits + " misses: " + misses); + if (ways == null) { + //Main.debug("missed"); + misses++; + return null; + } + //Main.debug("hit"); + hits++; + return ways; + } + + public void check(Node n) + { + if (true) + return; + if (disabled()) + return; + List<Way> ways = fastWaysUsingNode(n); + int cs = ways.size(); + int ss = slowWaysUsingNode(n).size(); + if (cs == ss) + return; + + Main.debug("waysUsingNodeCreate("+n.id+") cached nr != slow nr: "+cs+"/"+ss); + for (Way w : ways) { + System.out.print("cached way: " + w.id + " ["); + for (Node nn : w.nodes) + System.out.print(nn.id + ", "); + Main.debug("]"); + } + for (Way w : slowWaysUsingNode(n)) { + System.out.print("slow way: " + w.id + " ["); + for (Node nn : w.nodes) + System.out.print(nn.id + ", "); + Main.debug("]"); + } + throw new ArithmeticException(); + } + + private List<Way> waysUsingNodeCreate(Node n) + { + if (can_cache()) + enable_cache(); + List<Way> ways = fastWaysUsingNode(n); + if (ways != null) + return ways; + //Main.debug("waysUsingNodeCreate("+n.hashCode()+") first touch, always: " + always()); + // This is the first call for this particular node + // so don't even bother with the slow path, and assume + // this is a new node touching no ways, yet. + if (always()) + ways = new ArrayList<Way>(); + else + ways = slowWaysUsingNode(n); + + if (can_cache()) { + //Main.debug("about to put this: " + ways + " in place of this: " + + // waysUsingNodeCache.get(n)); + waysUsingNodeCache.put(n, ways); + } + return ways; + } + public List<Way> waysUsingNode(Node n) + { + List<Way> ways = waysUsingNodeCreate(n); + return Collections.unmodifiableList(ways); + } + + public static HashSet<Relation> relationsUsingWays(List<Way> selectedWays) { + HashSet<Relation> relationsUsingWays = new HashSet<Relation>(); + for (Relation r : Main.ds.relations) { + if (r.deleted || r.incomplete) + continue; + for (RelationMember rm : r.members) { + if (!(rm.member instanceof Way)) + continue; + for(Way w : selectedWays) { + if (rm.member != w) + continue; + relationsUsingWays.add(r); + } + } + } + return relationsUsingWays; + } + public void addWayToNodeMap(Collection<Node> nodes, Way w) + { + for (Node n : nodes) + addWayToNodeMap(n, w); + for (Node n : nodes) + check(n); + } + public void removeWayFromNodeMap(Collection<Node> nodes, Way w) + { + for (Node n : nodes) + removeWayFromNodeMap_nocheck(n, w); + for (Node n : nodes) + check(n); + } + public void addWayToNodeMap_nocheck(Node n, Way w) + { + List<Way> ways = waysUsingNodeCreate(n); + if (can_cache() && !ways.contains(w)) { + ways.add(w); + //Main.debug("addWaysToNodeMap("+n.hashCode() + ", " +w.hashCode()+") ways size:" + ways.size()); + } + } + public void removeWayFromNodeMap_nocheck(Node n, Way w) + { + List<Way> ways = waysUsingNodeCreate(n); + if (can_cache()) { + //in.debug("removeWaysFromNodeMap("+n.hashCode() + ", " +w.hashCode()+") ways size:" + ways.size()); + ways.remove(w); + } + } + public void addWayToNodeMap(Node n, Way w) + { + addWayToNodeMap_nocheck(n, w); + check(n); + } + public void removeWayFromNodeMap(Node n, Way w) + { + removeWayFromNodeMap_nocheck(n, w); + check(n); + } + public void removeWay(Way w) + { + for (Node n : w.nodes) + removeWayFromNodeMap(n, w); + } +} + _ _______________________________________________ josm-dev mailing list josm-dev@openstreetmap.org http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/josm-dev