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

Last change on this file since 13466 was 13420, checked in by bastiK, 6 years ago

fixed #11607 - RangeViolatedError: the new range must be within a single subrange
  • Property svn:eol-style set to native
File size: 16.9 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;
15
16import javax.swing.Icon;
17
18import org.openstreetmap.josm.data.conflict.Conflict;
19import org.openstreetmap.josm.data.conflict.ConflictCollection;
20import org.openstreetmap.josm.data.osm.DataSet;
21import org.openstreetmap.josm.data.osm.Node;
22import org.openstreetmap.josm.data.osm.NodeData;
23import org.openstreetmap.josm.data.osm.OsmPrimitive;
24import org.openstreetmap.josm.data.osm.PrimitiveData;
25import org.openstreetmap.josm.data.osm.PrimitiveId;
26import org.openstreetmap.josm.data.osm.Relation;
27import org.openstreetmap.josm.data.osm.RelationData;
28import org.openstreetmap.josm.data.osm.RelationMember;
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().beginUpdate();
87 try {
88 purgedConflicts.get().clear();
89 // unselect primitives in advance to not fire a selection change for every one of them
90 getAffectedDataSet().clearSelection(toPurge);
91 // Loop from back to front to keep referential integrity.
92 for (int i = toPurge.size()-1; i >= 0; --i) {
93 OsmPrimitive osm = toPurge.get(i);
94 if (makeIncompleteDataByPrimId.containsKey(osm)) {
95 // we could simply set the incomplete flag
96 // but that would not free memory in case the
97 // user clears undo/redo buffer after purge
98 PrimitiveData empty;
99 switch(osm.getType()) {
100 case NODE: empty = new NodeData(); break;
101 case WAY: empty = new WayData(); break;
102 case RELATION: empty = new RelationData(); break;
103 default: throw new AssertionError();
104 }
105 empty.setId(osm.getUniqueId());
106 empty.setIncomplete(true);
107 osm.load(empty);
108 } else {
109 getAffectedDataSet().removePrimitive(osm);
110 Conflict<?> conflict = getAffectedDataSet().getConflicts().getConflictForMy(osm);
111 if (conflict != null) {
112 purgedConflicts.add(conflict);
113 getAffectedDataSet().getConflicts().remove(conflict);
114 }
115 }
116 }
117 getAffectedDataSet().clearMappaintCache();
118 } finally {
119 getAffectedDataSet().endUpdate();
120 }
121 return true;
122 }
123
124 @Override
125 public void undoCommand() {
126 if (getAffectedDataSet() == null)
127 return;
128
129 getAffectedDataSet().beginUpdate();
130 try {
131 for (OsmPrimitive osm : toPurge) {
132 PrimitiveData data = makeIncompleteDataByPrimId.get(osm);
133 if (data != null) {
134 if (getAffectedDataSet().getPrimitiveById(osm) != osm)
135 throw new AssertionError(
136 String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm));
137 osm.load(data);
138 } else {
139 if (getAffectedDataSet().getPrimitiveById(osm) != null)
140 throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm));
141 getAffectedDataSet().addPrimitive(osm);
142 }
143 }
144
145 for (Conflict<?> conflict : purgedConflicts) {
146 getAffectedDataSet().getConflicts().add(conflict);
147 }
148 getAffectedDataSet().clearMappaintCache();
149 } finally {
150 getAffectedDataSet().endUpdate();
151 }
152 }
153
154 /**
155 * Sorts a collection of primitives such that for each object
156 * its referrers come later in the sorted collection.
157 * @param sel collection of primitives to sort
158 * @return sorted list
159 */
160 public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) {
161 Set<OsmPrimitive> in = new HashSet<>(sel);
162
163 List<OsmPrimitive> out = new ArrayList<>(in.size());
164
165 // Nodes not deleted in the first pass
166 Set<OsmPrimitive> remainingNodes = new HashSet<>(in.size());
167
168 /**
169 * First add nodes that have no way referrer.
170 */
171 outer:
172 for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
173 OsmPrimitive u = it.next();
174 if (u instanceof Node) {
175 Node n = (Node) u;
176 for (OsmPrimitive ref : n.getReferrers()) {
177 if (ref instanceof Way && in.contains(ref)) {
178 it.remove();
179 remainingNodes.add(n);
180 continue outer;
181 }
182 }
183 it.remove();
184 out.add(n);
185 }
186 }
187
188 /**
189 * Then add all ways, each preceded by its (remaining) nodes.
190 */
191 for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
192 OsmPrimitive u = it.next();
193 if (u instanceof Way) {
194 Way w = (Way) u;
195 it.remove();
196 for (Node n : w.getNodes()) {
197 if (remainingNodes.contains(n)) {
198 remainingNodes.remove(n);
199 out.add(n);
200 }
201 }
202 out.add(w);
203 }
204 }
205
206 if (!remainingNodes.isEmpty())
207 throw new AssertionError("topo sort algorithm failed (nodes remaining)");
208
209 /**
210 * Rest are relations. Do topological sorting on a DAG where each
211 * arrow points from child to parent. (Because it is faster to
212 * loop over getReferrers() than getMembers().)
213 */
214 @SuppressWarnings({ "unchecked", "rawtypes" })
215 Set<Relation> inR = (Set) in;
216
217 Map<Relation, Integer> numChilds = new HashMap<>();
218
219 // calculate initial number of childs
220 for (Relation r : inR) {
221 numChilds.put(r, 0);
222 }
223 for (Relation r : inR) {
224 for (OsmPrimitive parent : r.getReferrers()) {
225 if (!(parent instanceof Relation))
226 throw new AssertionError();
227 Integer i = numChilds.get(parent);
228 if (i != null) {
229 numChilds.put((Relation) parent, i+1);
230 }
231 }
232 }
233 Set<Relation> childlessR = new HashSet<>();
234 for (Relation r : inR) {
235 if (numChilds.get(r).equals(0)) {
236 childlessR.add(r);
237 }
238 }
239
240 List<Relation> outR = new ArrayList<>(inR.size());
241 while (!childlessR.isEmpty()) {
242 // Identify one childless Relation and let it virtually die. This makes other relations childless.
243 Iterator<Relation> it = childlessR.iterator();
244 Relation next = it.next();
245 it.remove();
246 outR.add(next);
247
248 for (OsmPrimitive parentPrim : next.getReferrers()) {
249 Relation parent = (Relation) parentPrim;
250 Integer i = numChilds.get(parent);
251 if (i != null) {
252 numChilds.put(parent, i-1);
253 if (i-1 == 0) {
254 childlessR.add(parent);
255 }
256 }
257 }
258 }
259
260 if (outR.size() != inR.size())
261 throw new AssertionError("topo sort algorithm failed");
262
263 out.addAll(outR);
264
265 return out;
266 }
267
268 @Override
269 public String getDescriptionText() {
270 return trn("Purged {0} object", "Purged {0} objects", toPurge.size(), toPurge.size());
271 }
272
273 @Override
274 public Icon getDescriptionIcon() {
275 return ImageProvider.get("data", "purge");
276 }
277
278 @Override
279 public Collection<? extends OsmPrimitive> getParticipatingPrimitives() {
280 return toPurge;
281 }
282
283 @Override
284 public void fillModifiedData(Collection<OsmPrimitive> modified, Collection<OsmPrimitive> deleted, Collection<OsmPrimitive> added) {
285 // Do nothing
286 }
287
288 @Override
289 public int hashCode() {
290 return Objects.hash(super.hashCode(), toPurge, makeIncompleteData, makeIncompleteDataByPrimId, purgedConflicts, getAffectedDataSet());
291 }
292
293 @Override
294 public boolean equals(Object obj) {
295 if (this == obj) return true;
296 if (obj == null || getClass() != obj.getClass()) return false;
297 if (!super.equals(obj)) return false;
298 PurgeCommand that = (PurgeCommand) obj;
299 return Objects.equals(toPurge, that.toPurge) &&
300 Objects.equals(makeIncompleteData, that.makeIncompleteData) &&
301 Objects.equals(makeIncompleteDataByPrimId, that.makeIncompleteDataByPrimId) &&
302 Objects.equals(purgedConflicts, that.purgedConflicts);
303 }
304
305 /**
306 * Creates a new {@code PurgeCommand} to purge selected OSM primitives.
307 * @param sel selected OSM primitives
308 * @param toPurgeAdditionally optional list that will be filled with primitives to be purged that have not been in the selection
309 * @return command to purge selected OSM primitives
310 * @since 12718
311 */
312 public static PurgeCommand build(Collection<OsmPrimitive> sel, List<OsmPrimitive> toPurgeAdditionally) {
313 Set<OsmPrimitive> toPurge = new HashSet<>(sel);
314 // finally, contains all objects that are purged
315 Set<OsmPrimitive> toPurgeChecked = new HashSet<>();
316
317 // Add referrer, unless the object to purge is not new and the parent is a relation
318 Set<OsmPrimitive> toPurgeRecursive = new HashSet<>();
319 while (!toPurge.isEmpty()) {
320
321 for (OsmPrimitive osm: toPurge) {
322 for (OsmPrimitive parent: osm.getReferrers()) {
323 if (toPurge.contains(parent) || toPurgeChecked.contains(parent) || toPurgeRecursive.contains(parent)) {
324 continue;
325 }
326 if (parent instanceof Way || (parent instanceof Relation && osm.isNew())) {
327 if (toPurgeAdditionally != null) {
328 toPurgeAdditionally.add(parent);
329 }
330 toPurgeRecursive.add(parent);
331 }
332 }
333 toPurgeChecked.add(osm);
334 }
335 toPurge = toPurgeRecursive;
336 toPurgeRecursive = new HashSet<>();
337 }
338
339 // Subset of toPurgeChecked. Marks primitives that remain in the dataset, but incomplete.
340 Set<OsmPrimitive> makeIncomplete = new HashSet<>();
341
342 // Find the objects that will be incomplete after purging.
343 // At this point, all parents of new to-be-purged primitives are
344 // also to-be-purged and
345 // all parents of not-new to-be-purged primitives are either
346 // to-be-purged or of type relation.
347 TOP:
348 for (OsmPrimitive child : toPurgeChecked) {
349 if (child.isNew()) {
350 continue;
351 }
352 for (OsmPrimitive parent : child.getReferrers()) {
353 if (parent instanceof Relation && !toPurgeChecked.contains(parent)) {
354 makeIncomplete.add(child);
355 continue TOP;
356 }
357 }
358 }
359
360 // Add untagged way nodes. Do not add nodes that have other referrers not yet to-be-purged.
361 if (Config.getPref().getBoolean("purge.add_untagged_waynodes", true)) {
362 Set<OsmPrimitive> wayNodes = new HashSet<>();
363 for (OsmPrimitive osm : toPurgeChecked) {
364 if (osm instanceof Way) {
365 Way w = (Way) osm;
366 NODE:
367 for (Node n : w.getNodes()) {
368 if (n.isTagged() || toPurgeChecked.contains(n)) {
369 continue;
370 }
371 for (OsmPrimitive ref : n.getReferrers()) {
372 if (ref != w && !toPurgeChecked.contains(ref)) {
373 continue NODE;
374 }
375 }
376 wayNodes.add(n);
377 }
378 }
379 }
380 toPurgeChecked.addAll(wayNodes);
381 if (toPurgeAdditionally != null) {
382 toPurgeAdditionally.addAll(wayNodes);
383 }
384 }
385
386 if (Config.getPref().getBoolean("purge.add_relations_with_only_incomplete_members", true)) {
387 Set<Relation> relSet = new HashSet<>();
388 for (OsmPrimitive osm : toPurgeChecked) {
389 for (OsmPrimitive parent : osm.getReferrers()) {
390 if (parent instanceof Relation
391 && !(toPurgeChecked.contains(parent))
392 && hasOnlyIncompleteMembers((Relation) parent, toPurgeChecked, relSet)) {
393 relSet.add((Relation) parent);
394 }
395 }
396 }
397
398 // Add higher level relations (list gets extended while looping over it)
399 List<Relation> relLst = new ArrayList<>(relSet);
400 for (int i = 0; i < relLst.size(); ++i) { // foreach loop not applicable since list gets extended while looping over it
401 for (OsmPrimitive parent : relLst.get(i).getReferrers()) {
402 if (!(toPurgeChecked.contains(parent))
403 && hasOnlyIncompleteMembers((Relation) parent, toPurgeChecked, relLst)) {
404 relLst.add((Relation) parent);
405 }
406 }
407 }
408 relSet = new HashSet<>(relLst);
409 toPurgeChecked.addAll(relSet);
410 if (toPurgeAdditionally != null) {
411 toPurgeAdditionally.addAll(relSet);
412 }
413 }
414
415 return new PurgeCommand(toPurgeChecked.iterator().next().getDataSet(), toPurgeChecked, makeIncomplete);
416 }
417
418 private static boolean hasOnlyIncompleteMembers(
419 Relation r, Collection<OsmPrimitive> toPurge, Collection<? extends OsmPrimitive> moreToPurge) {
420 for (RelationMember m : r.getMembers()) {
421 if (!m.getMember().isIncomplete() && !toPurge.contains(m.getMember()) && !moreToPurge.contains(m.getMember()))
422 return false;
423 }
424 return true;
425 }
426}
Note: See TracBrowser for help on using the repository browser.