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

Last change on this file since 13388 was 13173, checked in by Don-vip, 6 years ago

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