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