[josm-dev] [PATCH 21/24] ReverseLookup
Dave Hansen
dave at sr71.net
Sat May 3 20:15:10 BST 2008
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);
+ }
+}
+
_
More information about the josm-dev
mailing list