001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.command;
003
004import static org.openstreetmap.josm.tools.I18n.trn;
005
006import java.util.ArrayList;
007import java.util.Collection;
008import java.util.HashMap;
009import java.util.HashSet;
010import java.util.Iterator;
011import java.util.List;
012import java.util.Map;
013import java.util.Objects;
014import java.util.Set;
015
016import javax.swing.Icon;
017
018import org.openstreetmap.josm.data.conflict.Conflict;
019import org.openstreetmap.josm.data.conflict.ConflictCollection;
020import org.openstreetmap.josm.data.osm.DataSet;
021import org.openstreetmap.josm.data.osm.Node;
022import org.openstreetmap.josm.data.osm.NodeData;
023import org.openstreetmap.josm.data.osm.OsmPrimitive;
024import org.openstreetmap.josm.data.osm.PrimitiveData;
025import org.openstreetmap.josm.data.osm.PrimitiveId;
026import org.openstreetmap.josm.data.osm.Relation;
027import org.openstreetmap.josm.data.osm.RelationData;
028import org.openstreetmap.josm.data.osm.Storage;
029import org.openstreetmap.josm.data.osm.Way;
030import org.openstreetmap.josm.data.osm.WayData;
031import org.openstreetmap.josm.gui.layer.OsmDataLayer;
032import org.openstreetmap.josm.tools.ImageProvider;
033
034/**
035 * Command, to purge a list of primitives.
036 */
037public class PurgeCommand extends Command {
038    protected List<OsmPrimitive> toPurge;
039    protected Storage<PrimitiveData> makeIncompleteData;
040
041    protected Map<PrimitiveId, PrimitiveData> makeIncompleteDataByPrimId;
042
043    protected final ConflictCollection purgedConflicts = new ConflictCollection();
044
045    /**
046     * Constructs a new {@code PurgeCommand} (handles conflicts).
047     * This command relies on a number of consistency conditions:
048     *  - makeIncomplete must be a subset of toPurge.
049     *  - Each primitive, that is in toPurge but not in makeIncomplete, must have all its referrers in toPurge.
050     *  - Each element of makeIncomplete must not be new and must have only referrers that are either a relation or included in toPurge.
051     * @param layer OSM data layer
052     * @param toPurge primitives to purge
053     * @param makeIncomplete primitives to make incomplete
054     */
055    public PurgeCommand(OsmDataLayer layer, Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) {
056        super(layer);
057        init(toPurge, makeIncomplete);
058    }
059
060    /**
061     * Constructs a new {@code PurgeCommand} (does not handle conflicts).
062     * This command relies on a number of consistency conditions:
063     *  - makeIncomplete must be a subset of toPurge.
064     *  - Each primitive, that is in toPurge but not in makeIncomplete, must have all its referrers in toPurge.
065     *  - Each element of makeIncomplete must not be new and must have only referrers that are either a relation or included in toPurge.
066     * @param data OSM data set
067     * @param toPurge primitives to purge
068     * @param makeIncomplete primitives to make incomplete
069     * @since 11240
070     */
071    public PurgeCommand(DataSet data, Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) {
072        super(data);
073        init(toPurge, makeIncomplete);
074    }
075
076    private void init(Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) {
077        /**
078         * The topological sort is to avoid missing way nodes and missing
079         * relation members when adding primitives back to the dataset on undo.
080         *
081         * The same should hold for normal execution, but at time of writing
082         * there seem to be no such consistency checks when removing primitives.
083         * (It is done in a save manner, anyway.)
084         */
085        this.toPurge = topoSort(toPurge);
086        saveIncomplete(makeIncomplete);
087    }
088
089    protected final void saveIncomplete(Collection<OsmPrimitive> makeIncomplete) {
090        makeIncompleteData = new Storage<>(new Storage.PrimitiveIdHash());
091        makeIncompleteDataByPrimId = makeIncompleteData.foreignKey(new Storage.PrimitiveIdHash());
092
093        for (OsmPrimitive osm : makeIncomplete) {
094            makeIncompleteData.add(osm.save());
095        }
096    }
097
098    @Override
099    public boolean executeCommand() {
100        getAffectedDataSet().beginUpdate();
101        try {
102            purgedConflicts.get().clear();
103            /**
104             * Loop from back to front to keep referential integrity.
105             */
106            for (int i = toPurge.size()-1; i >= 0; --i) {
107                OsmPrimitive osm = toPurge.get(i);
108                if (makeIncompleteDataByPrimId.containsKey(osm)) {
109                    // we could simply set the incomplete flag
110                    // but that would not free memory in case the
111                    // user clears undo/redo buffer after purge
112                    PrimitiveData empty;
113                    switch(osm.getType()) {
114                    case NODE: empty = new NodeData(); break;
115                    case WAY: empty = new WayData(); break;
116                    case RELATION: empty = new RelationData(); break;
117                    default: throw new AssertionError();
118                    }
119                    empty.setId(osm.getUniqueId());
120                    empty.setIncomplete(true);
121                    osm.load(empty);
122                } else {
123                    getAffectedDataSet().removePrimitive(osm);
124                    if (getLayer() != null) {
125                        Conflict<?> conflict = getLayer().getConflicts().getConflictForMy(osm);
126                        if (conflict != null) {
127                            purgedConflicts.add(conflict);
128                            getLayer().getConflicts().remove(conflict);
129                        }
130                    }
131                }
132            }
133        } finally {
134            getAffectedDataSet().endUpdate();
135        }
136        return true;
137    }
138
139    @Override
140    public void undoCommand() {
141        if (getAffectedDataSet() == null)
142            return;
143
144        for (OsmPrimitive osm : toPurge) {
145            PrimitiveData data = makeIncompleteDataByPrimId.get(osm);
146            if (data != null) {
147                if (getAffectedDataSet().getPrimitiveById(osm) != osm)
148                    throw new AssertionError(
149                            String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm));
150                osm.load(data);
151            } else {
152                if (getAffectedDataSet().getPrimitiveById(osm) != null)
153                    throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm));
154                getAffectedDataSet().addPrimitive(osm);
155            }
156        }
157
158        for (Conflict<?> conflict : purgedConflicts) {
159            getLayer().getConflicts().add(conflict);
160        }
161    }
162
163    /**
164     * Sorts a collection of primitives such that for each object
165     * its referrers come later in the sorted collection.
166     * @param sel collection of primitives to sort
167     * @return sorted list
168     */
169    public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) {
170        Set<OsmPrimitive> in = new HashSet<>(sel);
171
172        List<OsmPrimitive> out = new ArrayList<>(in.size());
173
174        // Nodes not deleted in the first pass
175        Set<OsmPrimitive> remainingNodes = new HashSet<>(in.size());
176
177        /**
178         *  First add nodes that have no way referrer.
179         */
180        outer:
181            for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
182                OsmPrimitive u = it.next();
183                if (u instanceof Node) {
184                    Node n = (Node) u;
185                    for (OsmPrimitive ref : n.getReferrers()) {
186                        if (ref instanceof Way && in.contains(ref)) {
187                            it.remove();
188                            remainingNodes.add(n);
189                            continue outer;
190                        }
191                    }
192                    it.remove();
193                    out.add(n);
194                }
195            }
196
197        /**
198         * Then add all ways, each preceded by its (remaining) nodes.
199         */
200        for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
201            OsmPrimitive u = it.next();
202            if (u instanceof Way) {
203                Way w = (Way) u;
204                it.remove();
205                for (Node n : w.getNodes()) {
206                    if (remainingNodes.contains(n)) {
207                        remainingNodes.remove(n);
208                        out.add(n);
209                    }
210                }
211                out.add(w);
212            }
213        }
214
215        if (!remainingNodes.isEmpty())
216            throw new AssertionError("topo sort algorithm failed (nodes remaining)");
217
218        /**
219          * Rest are relations. Do topological sorting on a DAG where each
220          * arrow points from child to parent. (Because it is faster to
221          * loop over getReferrers() than getMembers().)
222          */
223        @SuppressWarnings({ "unchecked", "rawtypes" })
224        Set<Relation> inR = (Set) in;
225
226        Map<Relation, Integer> numChilds = new HashMap<>();
227
228        // calculate initial number of childs
229        for (Relation r : inR) {
230            numChilds.put(r, 0);
231        }
232        for (Relation r : inR) {
233            for (OsmPrimitive parent : r.getReferrers()) {
234                if (!(parent instanceof Relation))
235                    throw new AssertionError();
236                Integer i = numChilds.get(parent);
237                if (i != null) {
238                    numChilds.put((Relation) parent, i+1);
239                }
240            }
241        }
242        Set<Relation> childlessR = new HashSet<>();
243        for (Relation r : inR) {
244            if (numChilds.get(r).equals(0)) {
245                childlessR.add(r);
246            }
247        }
248
249        List<Relation> outR = new ArrayList<>(inR.size());
250        while (!childlessR.isEmpty()) {
251            // Identify one childless Relation and let it virtually die. This makes other relations childless.
252            Iterator<Relation> it = childlessR.iterator();
253            Relation next = it.next();
254            it.remove();
255            outR.add(next);
256
257            for (OsmPrimitive parentPrim : next.getReferrers()) {
258                Relation parent = (Relation) parentPrim;
259                Integer i = numChilds.get(parent);
260                if (i != null) {
261                    numChilds.put(parent, i-1);
262                    if (i-1 == 0) {
263                        childlessR.add(parent);
264                    }
265                }
266            }
267        }
268
269        if (outR.size() != inR.size())
270            throw new AssertionError("topo sort algorithm failed");
271
272        out.addAll(outR);
273
274        return out;
275    }
276
277    @Override
278    public String getDescriptionText() {
279        return trn("Purged {0} object", "Purged {0} objects", toPurge.size(), toPurge.size());
280    }
281
282    @Override
283    public Icon getDescriptionIcon() {
284        return ImageProvider.get("data", "purge");
285    }
286
287    @Override
288    public Collection<? extends OsmPrimitive> getParticipatingPrimitives() {
289        return toPurge;
290    }
291
292    @Override
293    public void fillModifiedData(Collection<OsmPrimitive> modified, Collection<OsmPrimitive> deleted, Collection<OsmPrimitive> added) {
294        // Do nothing
295    }
296
297    @Override
298    public int hashCode() {
299        return Objects.hash(super.hashCode(), toPurge, makeIncompleteData, makeIncompleteDataByPrimId, purgedConflicts, getAffectedDataSet());
300    }
301
302    @Override
303    public boolean equals(Object obj) {
304        if (this == obj) return true;
305        if (obj == null || getClass() != obj.getClass()) return false;
306        if (!super.equals(obj)) return false;
307        PurgeCommand that = (PurgeCommand) obj;
308        return Objects.equals(toPurge, that.toPurge) &&
309                Objects.equals(makeIncompleteData, that.makeIncompleteData) &&
310                Objects.equals(makeIncompleteDataByPrimId, that.makeIncompleteDataByPrimId) &&
311                Objects.equals(purgedConflicts, that.purgedConflicts);
312    }
313}