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