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