Changeset 5905 in josm for trunk/src/org/openstreetmap/josm/actions

Timestamp:

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

Author:

bastiK

Message:

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

File:

• trunk/src/org/openstreetmap/josm/actions/PurgeAction.java (modified) (1 diff)

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>();
         }