source: josm/trunk/src/org/openstreetmap/josm/command/PurgeCommand.java@ 17534

Last change on this file since 17534 was 16800, checked in by Klumbumbus, 4 years ago

see #15240 - Change some png icons to svg:

  • dialogs/duplicatelayer, dialogs/layerlist, dialogs/layerlist/active, dialogs/layerlist/active-pressed, dialogs/mergedown, dialogs/reorderlayers, all derived from internal dialogs/activate icon, PD and CC0 licensed
  • help/internet ​https://commons.wikimedia.org/wiki/File:Gnome-emblem-web.svg, modified, from GNOME Project, LGPL licensed
  • purge ​https://commons.wikimedia.org/wiki/File:Edit-clear.svg, resized, from The Tango Desktop Project, PD and CC0 licensed
  • dialogs/geoimage/deletefromdisk, derived from internal dialogs/delete icon, PD and CC0 licensed
  • remove data/key, use dialogs/propertiesdialog instead (fits better, used in command stack panel only)
  • small changes/fixes to existing icons
  • Property svn:eol-style set to native
File size: 16.5 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.command;
3
4import static org.openstreetmap.josm.tools.I18n.trn;
5
6import java.util.ArrayList;
7import java.util.Collection;
8import java.util.HashMap;
9import java.util.HashSet;
10import java.util.Iterator;
11import java.util.List;
12import java.util.Map;
13import java.util.Objects;
14import java.util.Set;
15import java.util.stream.Collectors;
16
17import javax.swing.Icon;
18
19import org.openstreetmap.josm.data.conflict.Conflict;
20import org.openstreetmap.josm.data.conflict.ConflictCollection;
21import org.openstreetmap.josm.data.osm.DataSet;
22import org.openstreetmap.josm.data.osm.Node;
23import org.openstreetmap.josm.data.osm.NodeData;
24import org.openstreetmap.josm.data.osm.OsmPrimitive;
25import org.openstreetmap.josm.data.osm.PrimitiveData;
26import org.openstreetmap.josm.data.osm.PrimitiveId;
27import org.openstreetmap.josm.data.osm.Relation;
28import org.openstreetmap.josm.data.osm.RelationData;
29import org.openstreetmap.josm.data.osm.Storage;
30import org.openstreetmap.josm.data.osm.Way;
31import org.openstreetmap.josm.data.osm.WayData;
32import org.openstreetmap.josm.spi.preferences.Config;
33import org.openstreetmap.josm.tools.ImageProvider;
34
35/**
36 * Command, to purge a list of primitives.
37 */
38public class PurgeCommand extends Command {
39 protected List<OsmPrimitive> toPurge;
40 protected Storage<PrimitiveData> makeIncompleteData;
41
42 protected Map<PrimitiveId, PrimitiveData> makeIncompleteDataByPrimId;
43
44 protected final ConflictCollection purgedConflicts = new ConflictCollection();
45
46 /**
47 * Constructs a new {@code PurgeCommand} (does not handle conflicts).
48 * This command relies on a number of consistency conditions:
49 * - makeIncomplete must be a subset of toPurge.
50 * - Each primitive, that is in toPurge but not in makeIncomplete, must have all its referrers in toPurge.
51 * - Each element of makeIncomplete must not be new and must have only referrers that are either a relation or included in toPurge.
52 * @param data OSM data set
53 * @param toPurge primitives to purge
54 * @param makeIncomplete primitives to make incomplete
55 * @since 11240
56 */
57 public PurgeCommand(DataSet data, Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) {
58 super(data);
59 init(toPurge, makeIncomplete);
60 }
61
62 private void init(Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) {
63 /**
64 * The topological sort is to avoid missing way nodes and missing
65 * relation members when adding primitives back to the dataset on undo.
66 *
67 * The same should hold for normal execution, but at time of writing
68 * there seem to be no such consistency checks when removing primitives.
69 * (It is done in a save manner, anyway.)
70 */
71 this.toPurge = topoSort(toPurge);
72 saveIncomplete(makeIncomplete);
73 }
74
75 protected final void saveIncomplete(Collection<OsmPrimitive> makeIncomplete) {
76 makeIncompleteData = new Storage<>(new Storage.PrimitiveIdHash());
77 makeIncompleteDataByPrimId = makeIncompleteData.foreignKey(new Storage.PrimitiveIdHash());
78
79 for (OsmPrimitive osm : makeIncomplete) {
80 makeIncompleteData.add(osm.save());
81 }
82 }
83
84 @Override
85 public boolean executeCommand() {
86 getAffectedDataSet().update(() -> {
87 purgedConflicts.get().clear();
88 // unselect primitives in advance to not fire a selection change for every one of them
89 getAffectedDataSet().clearSelection(toPurge);
90 // Loop from back to front to keep referential integrity.
91 for (int i = toPurge.size()-1; i >= 0; --i) {
92 OsmPrimitive osm = toPurge.get(i);
93 if (makeIncompleteDataByPrimId.containsKey(osm)) {
94 // we could simply set the incomplete flag
95 // but that would not free memory in case the
96 // user clears undo/redo buffer after purge
97 PrimitiveData empty;
98 switch(osm.getType()) {
99 case NODE: empty = new NodeData(); break;
100 case WAY: empty = new WayData(); break;
101 case RELATION: empty = new RelationData(); break;
102 default: throw new AssertionError();
103 }
104 empty.setId(osm.getUniqueId());
105 empty.setIncomplete(true);
106 osm.load(empty);
107 } else {
108 getAffectedDataSet().removePrimitive(osm);
109 Conflict<?> conflict = getAffectedDataSet().getConflicts().getConflictForMy(osm);
110 if (conflict != null) {
111 purgedConflicts.add(conflict);
112 getAffectedDataSet().getConflicts().remove(conflict);
113 }
114 }
115 }
116 getAffectedDataSet().clearMappaintCache();
117 });
118 return true;
119 }
120
121 @Override
122 public void undoCommand() {
123 if (getAffectedDataSet() == null)
124 return;
125
126 getAffectedDataSet().update(() -> {
127 for (OsmPrimitive osm : toPurge) {
128 PrimitiveData data = makeIncompleteDataByPrimId.get(osm);
129 if (data != null) {
130 if (getAffectedDataSet().getPrimitiveById(osm) != osm)
131 throw new AssertionError(
132 String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm));
133 osm.load(data);
134 } else {
135 if (getAffectedDataSet().getPrimitiveById(osm) != null)
136 throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm));
137 getAffectedDataSet().addPrimitive(osm);
138 }
139 }
140
141 for (Conflict<?> conflict : purgedConflicts) {
142 getAffectedDataSet().getConflicts().add(conflict);
143 }
144 getAffectedDataSet().clearMappaintCache();
145 });
146 }
147
148 /**
149 * Sorts a collection of primitives such that for each object
150 * its referrers come later in the sorted collection.
151 * @param sel collection of primitives to sort
152 * @return sorted list
153 */
154 public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) {
155 Set<OsmPrimitive> in = new HashSet<>(sel);
156 List<OsmPrimitive> out = new ArrayList<>(in.size());
157 Set<Relation> inR = new HashSet<>();
158
159 // Nodes not deleted in the first pass
160 Set<OsmPrimitive> remainingNodes = new HashSet<>(in.size());
161
162 /**
163 * First add nodes that have no way referrer.
164 */
165 outer:
166 for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
167 OsmPrimitive u = it.next();
168 if (u instanceof Node) {
169 Node n = (Node) u;
170 for (OsmPrimitive ref : n.getReferrers()) {
171 if (ref instanceof Way && in.contains(ref)) {
172 it.remove();
173 remainingNodes.add(n);
174 continue outer;
175 }
176 }
177 it.remove();
178 out.add(n);
179 }
180 }
181
182 /**
183 * Then add all ways, each preceded by its (remaining) nodes.
184 */
185 for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
186 OsmPrimitive u = it.next();
187 if (u instanceof Way) {
188 Way w = (Way) u;
189 it.remove();
190 for (Node n : w.getNodes()) {
191 if (remainingNodes.contains(n)) {
192 remainingNodes.remove(n);
193 out.add(n);
194 }
195 }
196 out.add(w);
197 } else if (u instanceof Relation) {
198 inR.add((Relation) u);
199 }
200 }
201
202 if (!remainingNodes.isEmpty())
203 throw new AssertionError("topo sort algorithm failed (nodes remaining)");
204
205 // Do topological sorting on a DAG where each arrow points from child to parent.
206 // (Because it is faster to loop over getReferrers() than getMembers().)
207
208 Map<Relation, Integer> numChilds = new HashMap<>();
209
210 // calculate initial number of childs
211 for (Relation r : inR) {
212 numChilds.put(r, 0);
213 }
214 for (Relation r : inR) {
215 for (OsmPrimitive parent : r.getReferrers()) {
216 if (!(parent instanceof Relation))
217 throw new AssertionError();
218 Integer i = numChilds.get(parent);
219 if (i != null) {
220 numChilds.put((Relation) parent, i+1);
221 }
222 }
223 }
224 Set<Relation> childlessR = inR.stream().filter(r -> numChilds.get(r).equals(0)).collect(Collectors.toSet());
225
226 List<Relation> outR = new ArrayList<>(inR.size());
227 while (!childlessR.isEmpty()) {
228 // Identify one childless Relation and let it virtually die. This makes other relations childless.
229 Iterator<Relation> it = childlessR.iterator();
230 Relation next = it.next();
231 it.remove();
232 outR.add(next);
233
234 for (OsmPrimitive parentPrim : next.getReferrers()) {
235 Relation parent = (Relation) parentPrim;
236 Integer i = numChilds.get(parent);
237 if (i != null) {
238 numChilds.put(parent, i-1);
239 if (i-1 == 0) {
240 childlessR.add(parent);
241 }
242 }
243 }
244 }
245
246 if (outR.size() != inR.size())
247 throw new AssertionError("topo sort algorithm failed");
248
249 out.addAll(outR);
250
251 return out;
252 }
253
254 @Override
255 public String getDescriptionText() {
256 return trn("Purged {0} object", "Purged {0} objects", toPurge.size(), toPurge.size());
257 }
258
259 @Override
260 public Icon getDescriptionIcon() {
261 return ImageProvider.get("purge");
262 }
263
264 @Override
265 public Collection<? extends OsmPrimitive> getParticipatingPrimitives() {
266 return toPurge;
267 }
268
269 @Override
270 public void fillModifiedData(Collection<OsmPrimitive> modified, Collection<OsmPrimitive> deleted, Collection<OsmPrimitive> added) {
271 // Do nothing
272 }
273
274 @Override
275 public int hashCode() {
276 return Objects.hash(super.hashCode(), toPurge, makeIncompleteData, makeIncompleteDataByPrimId, purgedConflicts, getAffectedDataSet());
277 }
278
279 @Override
280 public boolean equals(Object obj) {
281 if (this == obj) return true;
282 if (obj == null || getClass() != obj.getClass()) return false;
283 if (!super.equals(obj)) return false;
284 PurgeCommand that = (PurgeCommand) obj;
285 return Objects.equals(toPurge, that.toPurge) &&
286 Objects.equals(makeIncompleteData, that.makeIncompleteData) &&
287 Objects.equals(makeIncompleteDataByPrimId, that.makeIncompleteDataByPrimId) &&
288 Objects.equals(purgedConflicts, that.purgedConflicts);
289 }
290
291 /**
292 * Creates a new {@code PurgeCommand} to purge selected OSM primitives.
293 * @param sel selected OSM primitives
294 * @param toPurgeAdditionally optional list that will be filled with primitives to be purged that have not been in the selection
295 * @return command to purge selected OSM primitives
296 * @since 12718
297 */
298 public static PurgeCommand build(Collection<OsmPrimitive> sel, List<OsmPrimitive> toPurgeAdditionally) {
299 Set<OsmPrimitive> toPurge = new HashSet<>(sel);
300 // finally, contains all objects that are purged
301 Set<OsmPrimitive> toPurgeChecked = new HashSet<>();
302
303 // Add referrer, unless the object to purge is not new and the parent is a relation
304 Set<OsmPrimitive> toPurgeRecursive = new HashSet<>();
305 while (!toPurge.isEmpty()) {
306
307 for (OsmPrimitive osm: toPurge) {
308 for (OsmPrimitive parent: osm.getReferrers()) {
309 if (toPurge.contains(parent) || toPurgeChecked.contains(parent) || toPurgeRecursive.contains(parent)) {
310 continue;
311 }
312 if (parent instanceof Way || (parent instanceof Relation && osm.isNew())) {
313 if (toPurgeAdditionally != null) {
314 toPurgeAdditionally.add(parent);
315 }
316 toPurgeRecursive.add(parent);
317 }
318 }
319 toPurgeChecked.add(osm);
320 }
321 toPurge = toPurgeRecursive;
322 toPurgeRecursive = new HashSet<>();
323 }
324
325 // Subset of toPurgeChecked. Marks primitives that remain in the dataset, but incomplete.
326 Set<OsmPrimitive> makeIncomplete = new HashSet<>();
327
328 // Find the objects that will be incomplete after purging.
329 // At this point, all parents of new to-be-purged primitives are
330 // also to-be-purged and
331 // all parents of not-new to-be-purged primitives are either
332 // to-be-purged or of type relation.
333 TOP:
334 for (OsmPrimitive child : toPurgeChecked) {
335 if (child.isNew()) {
336 continue;
337 }
338 for (OsmPrimitive parent : child.getReferrers()) {
339 if (parent instanceof Relation && !toPurgeChecked.contains(parent)) {
340 makeIncomplete.add(child);
341 continue TOP;
342 }
343 }
344 }
345
346 // Add untagged way nodes. Do not add nodes that have other referrers not yet to-be-purged.
347 if (Config.getPref().getBoolean("purge.add_untagged_waynodes", true)) {
348 Set<OsmPrimitive> wayNodes = new HashSet<>();
349 for (OsmPrimitive osm : toPurgeChecked) {
350 if (osm instanceof Way) {
351 Way w = (Way) osm;
352 NODE:
353 for (Node n : w.getNodes()) {
354 if (n.isTagged() || toPurgeChecked.contains(n)) {
355 continue;
356 }
357 for (OsmPrimitive ref : n.getReferrers()) {
358 if (ref != w && !toPurgeChecked.contains(ref)) {
359 continue NODE;
360 }
361 }
362 wayNodes.add(n);
363 }
364 }
365 }
366 toPurgeChecked.addAll(wayNodes);
367 if (toPurgeAdditionally != null) {
368 toPurgeAdditionally.addAll(wayNodes);
369 }
370 }
371
372 if (Config.getPref().getBoolean("purge.add_relations_with_only_incomplete_members", true)) {
373 Set<Relation> relSet = new HashSet<>();
374 for (OsmPrimitive osm : toPurgeChecked) {
375 for (OsmPrimitive parent : osm.getReferrers()) {
376 if (parent instanceof Relation
377 && !toPurgeChecked.contains(parent)
378 && hasOnlyIncompleteMembers((Relation) parent, toPurgeChecked, relSet)) {
379 relSet.add((Relation) parent);
380 }
381 }
382 }
383
384 // Add higher level relations (list gets extended while looping over it)
385 List<Relation> relLst = new ArrayList<>(relSet);
386 for (int i = 0; i < relLst.size(); ++i) { // foreach loop not applicable since list gets extended while looping over it
387 for (OsmPrimitive parent : relLst.get(i).getReferrers()) {
388 if (!toPurgeChecked.contains(parent)
389 && hasOnlyIncompleteMembers((Relation) parent, toPurgeChecked, relLst)) {
390 relLst.add((Relation) parent);
391 }
392 }
393 }
394 relSet = new HashSet<>(relLst);
395 toPurgeChecked.addAll(relSet);
396 if (toPurgeAdditionally != null) {
397 toPurgeAdditionally.addAll(relSet);
398 }
399 }
400
401 return new PurgeCommand(toPurgeChecked.iterator().next().getDataSet(), toPurgeChecked, makeIncomplete);
402 }
403
404 private static boolean hasOnlyIncompleteMembers(
405 Relation r, Collection<OsmPrimitive> toPurge, Collection<? extends OsmPrimitive> moreToPurge) {
406 return r.getMembers().stream()
407 .allMatch(m -> m.getMember().isIncomplete() || toPurge.contains(m.getMember()) || moreToPurge.contains(m.getMember()));
408 }
409}
Note: See TracBrowser for help on using the repository browser.