[josm-dev] QuadBuckets in Dataset

[Dave Hansen]

On Sat, 2009-10-31 at 17:08 +0100, Jiri Klement wrote:
> > I'd just like to note that as a JOSM user I appreciated QuadBuckets
> > since I could run the Validator on large datasets for the first time
> > without JOSM taking forever (& having to be killed).
> 
> I've noticed that validator plugin is using QuadBuckets, but in my
> opinion UnconnectedWays test will miss some cases in case they're
> caused by moved nodes, because MoveCommand doesn't reindex
> QuadBuckets. Or am I missing something?

One suggestion was to use the UndoRedoHandler code to catch
modifications and reindex the primitives.  How about something like
this?

Index: src/org/openstreetmap/josm/data/UndoRedoHandler.java
===================================================================
--- src/org/openstreetmap/josm/data/UndoRedoHandler.java	(revision 2355)
+++ src/org/openstreetmap/josm/data/UndoRedoHandler.java	(working copy)
@@ -3,11 +3,13 @@
 
 import java.util.Iterator;
 import java.util.LinkedList;
+import java.util.HashSet;
 import java.util.Stack;
 
 import org.openstreetmap.josm.Main;
 import org.openstreetmap.josm.command.Command;
 import org.openstreetmap.josm.data.osm.DataSet;
+import org.openstreetmap.josm.data.osm.OsmPrimitive;
 import org.openstreetmap.josm.gui.layer.Layer;
 import org.openstreetmap.josm.gui.layer.OsmDataLayer;
 import org.openstreetmap.josm.gui.layer.Layer.LayerChangeListener;
@@ -38,16 +40,32 @@
     public void addNoRedraw(final Command c) {
         c.executeCommand();
         commands.add(c);
+        recordModified(c);
         redoCommands.clear();
     }
 
-    public void afterAdd() {
+    HashSet<OsmPrimitive> modifiedPrimitives = new HashSet<OsmPrimitive>();
+    void recordModified(Command c)
+    {
+        LinkedList<OsmPrimitive> deleted = new LinkedList<OsmPrimitive>();
+        LinkedList<OsmPrimitive> added = new LinkedList<OsmPrimitive>();
+        LinkedList<OsmPrimitive> modified = new LinkedList<OsmPrimitive>();
+        c.fillModifiedData(modified, deleted, added);
+        modifiedPrimitives.addAll(modified);
+    }
+    public void sendNotifications()
+    {
         if (Main.map != null && Main.map.mapView.getActiveLayer() instanceof OsmDataLayer) {
             OsmDataLayer data = (OsmDataLayer)Main.map.mapView.getActiveLayer();
             data.fireDataChange();
         }
+        Main.main.getCurrentDataSet().notifyPrimitiveChange(modifiedPrimitives);
+        modifiedPrimitives.clear();
         fireCommandsChanged();
+    }
 
+    public void afterAdd() {
+        sendNotifications();
         // the command may have changed the selection so tell the listeners about the current situation
         Main.main.getCurrentDataSet().fireSelectionChanged();
     }
@@ -69,11 +87,8 @@
         final Command c = commands.removeLast();
         c.undoCommand();
         redoCommands.push(c);
-        if (Main.map != null && Main.map.mapView.getActiveLayer() instanceof OsmDataLayer) {
-            OsmDataLayer data = (OsmDataLayer)Main.map.mapView.getActiveLayer();
-            data.fireDataChange();
-        }
-        fireCommandsChanged();
+        recordModified(c);
+        sendNotifications();
         Main.main.getCurrentDataSet().setSelected();
     }
 
@@ -86,12 +101,9 @@
             return;
         final Command c = redoCommands.pop();
         c.executeCommand();
+        recordModified(c);
         commands.add(c);
-        if (Main.map != null && Main.map.mapView.getActiveLayer() instanceof OsmDataLayer) {
-            OsmDataLayer data = (OsmDataLayer)Main.map.mapView.getActiveLayer();
-            data.fireDataChange();
-        }
-        fireCommandsChanged();
+        sendNotifications();
     }
 
     public void fireCommandsChanged() {
Index: src/org/openstreetmap/josm/data/osm/DataSet.java
===================================================================
--- src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 2355)
+++ src/org/openstreetmap/josm/data/osm/DataSet.java	(working copy)
@@ -645,4 +645,62 @@
         }
         return ret;
     }
+
+    List<Way> waysUsingNode(Node n)
+    {
+        List<Way> possible_ways = ways.search(n.getCoor(), 0.0);
+        List<Way> result = new ArrayList<Way>();
+        for (Way w : possible_ways) {
+            if (!w.containsNode(n))
+                continue;
+            result.add(w);
+        }
+        return result;
+    }
+
+    void reIndex(Way w)
+    {
+        ways.remove(w);
+        ways.add(w);
+    }
+
+    void reIndex(Node n)
+    {
+        nodes.remove(n);
+        nodes.add(n);
+    }
+
+    void reIndexPrimitives(Collection<OsmPrimitive> modified)
+    {
+        for (OsmPrimitive o : modified) {
+            if (o instanceof Way)
+                reIndex((Way)o);
+            if (o instanceof Node)
+                reIndex((Node)o);
+        }
+    }
+
+    /*
+     * When nodes and ways get modified, their spatial properties may
+     * change.  This means that their locations in the spatially-indexed
+     * QuadBuckets structures may change.  When this happens, delete
+     * and reinsert them.
+     */
+    public void notifyPrimitiveChange(Collection<OsmPrimitive> modified)
+    {
+        /*
+         * Make sure to reindex all the ways first.  This will
+         * make sure that waysUsingNode() can find the ways
+         * if they got changed.
+         */
+        reIndexPrimitives(modified);
+        HashSet<OsmPrimitive> waysTouchedByNodes = new HashSet<OsmPrimitive>();
+        for (OsmPrimitive o : modified) {
+            if (!(o instanceof Node))
+                continue;
+            Node n = (Node)o;
+            modified.addAll(waysUsingNode(n));
+        }
+        reIndexPrimitives(waysTouchedByNodes);
+    }
 }


-- Dave