Index: trunk/src/org/openstreetmap/josm/data/osm/DataSet.java
===================================================================
--- trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 12056)
+++ trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 12057)
@@ -22,5 +22,4 @@
 import java.util.function.Function;
 import java.util.function.Predicate;
-import java.util.stream.Collectors;
 import java.util.stream.Stream;
 
@@ -575,6 +574,6 @@
             if (primitive == null)
                 return;
+            clearSelection(primitiveId);
             super.removePrimitive(primitive);
-            clearSelection(primitiveId);
             allPrimitives.remove(primitive);
             primitive.setDataset(null);
@@ -1246,16 +1245,17 @@
         beginUpdate();
         try {
-            cleanupDeleted(Stream.concat(
-                    getNodes().stream(), Stream.concat(getNodes().stream(), getNodes().stream())));
+            Collection<OsmPrimitive> toCleanUp = getPrimitives(primitive -> primitive.isDeleted() && (!primitive.isVisible() || primitive.isNew()));
+            if (!toCleanUp.isEmpty()) {
+                clearSelection(toCleanUp.stream().map(OsmPrimitive::getPrimitiveId));
+                for (OsmPrimitive primitive : toCleanUp) {
+                    allPrimitives.remove(primitive);
+                    removePrimitive(primitive);
+                    primitive.setDataset(null);
+                }
+                firePrimitivesRemoved(toCleanUp, false);
+            }
         } finally {
             endUpdate();
         }
-    }
-
-    private void cleanupDeleted(Stream<? extends OsmPrimitive> it) {
-        it.filter(primitive -> primitive.isDeleted() && (!primitive.isVisible() || primitive.isNew()))
-                .collect(Collectors.toList())
-                .forEach(primitive -> this.removePrimitive(primitive.getPrimitiveId()));
-
     }