[josm-dev] [PATCH 03/26] ReverseLookup

Dave Hansen dave at sr71.net
Tue Apr 29 03:02:45 BST 2008


Core reverse lookup code for caching the results of reverse-lookup
operations.

---

 core-dave/src/org/openstreetmap/josm/data/osm/DataSet.java    |    3 
 core-dave/src/org/openstreetmap/josm/tools/ReverseLookup.java |  236 ++++++++++
 2 files changed, 239 insertions(+)

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-04-28 18:59:24.000000000 -0700
+++ core-dave/src/org/openstreetmap/josm/data/osm/DataSet.java	2008-04-28 18:59:24.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/tools/ReverseLookup.java~reverselookup src/org/openstreetmap/josm/tools/ReverseLookup.java
--- core/src/org/openstreetmap/josm/tools/ReverseLookup.java~reverselookup	2008-04-28 18:59:24.000000000 -0700
+++ core-dave/src/org/openstreetmap/josm/tools/ReverseLookup.java	2008-04-28 18:59:24.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