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

Last change on this file since 12718 was 12718, checked in by Don-vip, 3 months ago

see #13036 - see #15229 - see #15182 - make Commands depends only on a DataSet, not a Layer. This removes a lot of GUI dependencies

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