Changeset 5905 in josm for trunk

Timestamp:

2013-04-28T12:01:13+02:00 (12 years ago)

Author:

bastiK

Message:

applied #8643 - Very slow Purge command - O(N^{2) (patch by bilbo)}

Location:

trunk/src/org/openstreetmap/josm

Files:

• actions/PurgeAction.java (modified) (1 diff)
• command/PurgeCommand.java (modified) (3 diffs)

trunk/src/org/openstreetmap/josm/actions/PurgeAction.java

@@ -98 +98 @@
         // Add referrer, unless the object to purge is not new
         // and the parent is a relation
+        HashSet<OsmPrimitive> toPurgeRecursive = new HashSet<OsmPrimitive>();
         while (!toPurge.isEmpty()) {
-            OsmPrimitive osm = toPurge.iterator().next();
-            for (OsmPrimitive parent: osm.getReferrers()) {
-                if (toPurge.contains(parent) || toPurgeChecked.contains(parent)) {
-                    continue;
-                }
-                if (parent instanceof Way || (parent instanceof Relation && osm.isNew())) {
-                    toPurgeAdditionally.add(parent);
-                    toPurge.add(parent);
-                }
-            }
-            toPurge.remove(osm);
-            toPurgeChecked.add(osm);
+
+            for (OsmPrimitive osm: toPurge) {
+                for (OsmPrimitive parent: osm.getReferrers()) {
+                    if (toPurge.contains(parent) || toPurgeChecked.contains(parent) || toPurgeRecursive.contains(parent)) {
+                        continue;
+                    }
+                    if (parent instanceof Way || (parent instanceof Relation && osm.isNew())) {
+                        toPurgeAdditionally.add(parent);
+                        toPurgeRecursive.add(parent);
+                    }
+                }
+                toPurgeChecked.add(osm);
+            }
+            toPurge = toPurgeRecursive;
+            toPurgeRecursive = new HashSet<OsmPrimitive>();
         }
 

trunk/src/org/openstreetmap/josm/command/PurgeCommand.java

@@ -133 +133 @@
         List<OsmPrimitive> out = new ArrayList<OsmPrimitive>(in.size());
 
+        // Nodes not deleted in the first pass
+        Set<OsmPrimitive> remainingNodes = new HashSet<OsmPrimitive>(in.size());
+
         /**
          *  First add nodes that have no way referrer.
@@ -143 +146 @@
                     for (OsmPrimitive ref : n.getReferrers()) {
                         if (ref instanceof Way && in.contains(ref)) {
+                            it.remove();
+                            remainingNodes.add(n);
                             continue outer;
                         }
@@ -154 +159 @@
          * Then add all ways, each preceded by its (remaining) nodes.
          */
-        top: while (!in.isEmpty()) {
-            for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
-                OsmPrimitive u = it.next();
-                if (u instanceof Way) {
-                    Way w = (Way) u;
-                    it.remove();
-                    for (Node n : w.getNodes()) {
-                        if (in.contains(n)) {
-                            in.remove(n);
-                            out.add(n);
-                        }
-                    }
-                    out.add(w);
-                    continue top;
-                }
-            }
-            break; // no more ways left
-        }
+        for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
+            OsmPrimitive u = it.next();
+            if (u instanceof Way) {
+                Way w = (Way) u;
+                it.remove();
+                for (Node n : w.getNodes()) {
+                    if (remainingNodes.contains(n)) {
+                        remainingNodes.remove(n);
+                        out.add(n);
+                    }
+                }
+                out.add(w);
+            }
+        }
+
+        if (!remainingNodes.isEmpty())
+            throw new AssertionError("topo sort algorithm failed (nodes remaining)");
 
         /**