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> makeIncompleteData_byPrimId;
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        makeIncompleteData_byPrimId = 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 (makeIncompleteData_byPrimId.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 = makeIncompleteData_byPrimId.get(osm);
124            if (data != null) {
125                if (ds.getPrimitiveById(osm) != osm)
126                    throw new AssertionError(String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm));
127                osm.load(data);
128            } else {
129                if (ds.getPrimitiveById(osm) != null)
130                    throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm));
131                ds.addPrimitive(osm);
132            }
133        }
134
135        for (Conflict<?> conflict : purgedConflicts) {
136            getLayer().getConflicts().add(conflict);
137        }
138    }
139
140    /**
141     * Sorts a collection of primitives such that for each object
142     * its referrers come later in the sorted collection.
143     */
144    public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) {
145        Set<OsmPrimitive> in = new HashSet<>(sel);
146
147        List<OsmPrimitive> out = new ArrayList<>(in.size());
148
149        // Nodes not deleted in the first pass
150        Set<OsmPrimitive> remainingNodes = new HashSet<>(in.size());
151
152        /**
153         *  First add nodes that have no way referrer.
154         */
155        outer:
156            for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
157                OsmPrimitive u = it.next();
158                if (u instanceof Node) {
159                    Node n = (Node) u;
160                    for (OsmPrimitive ref : n.getReferrers()) {
161                        if (ref instanceof Way && in.contains(ref)) {
162                            it.remove();
163                            remainingNodes.add(n);
164                            continue outer;
165                        }
166                    }
167                    it.remove();
168                    out.add(n);
169                }
170            }
171
172        /**
173         * Then add all ways, each preceded by its (remaining) nodes.
174         */
175        for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) {
176            OsmPrimitive u = it.next();
177            if (u instanceof Way) {
178                Way w = (Way) u;
179                it.remove();
180                for (Node n : w.getNodes()) {
181                    if (remainingNodes.contains(n)) {
182                        remainingNodes.remove(n);
183                        out.add(n);
184                    }
185                }
186                out.add(w);
187            }
188        }
189
190        if (!remainingNodes.isEmpty())
191            throw new AssertionError("topo sort algorithm failed (nodes remaining)");
192
193        /**
194          * Rest are relations. Do topological sorting on a DAG where each
195          * arrow points from child to parent. (Because it is faster to
196          * loop over getReferrers() than getMembers().)
197          */
198        @SuppressWarnings({ "unchecked", "rawtypes" })
199        Set<Relation> inR = (Set) in;
200        Set<Relation> childlessR = new HashSet<>();
201        List<Relation> outR = new ArrayList<>(inR.size());
202
203        HashMap<Relation, Integer> numChilds = new HashMap<>();
204
205        // calculate initial number of childs
206        for (Relation r : inR) {
207            numChilds.put(r, 0);
208        }
209        for (Relation r : inR) {
210            for (OsmPrimitive parent : r.getReferrers()) {
211                if (!(parent instanceof Relation))
212                    throw new AssertionError();
213                Integer i = numChilds.get(parent);
214                if (i != null) {
215                    numChilds.put((Relation)parent, i+1);
216                }
217            }
218        }
219        for (Relation r : inR) {
220            if (numChilds.get(r).equals(0)) {
221                childlessR.add(r);
222            }
223        }
224
225        while (!childlessR.isEmpty()) {
226            // Identify one childless Relation and
227            // let it virtually die. This makes other
228            // relations childless.
229            Iterator<Relation> it  = childlessR.iterator();
230            Relation next = it.next();
231            it.remove();
232            outR.add(next);
233
234            for (OsmPrimitive parentPrim : next.getReferrers()) {
235                Relation parent = (Relation) parentPrim;
236                Integer i = numChilds.get(parent);
237                if (i != null) {
238                    numChilds.put(parent, i-1);
239                    if (i-1 == 0) {
240                        childlessR.add(parent);
241                    }
242                }
243            }
244        }
245
246        if (outR.size() != inR.size())
247            throw new AssertionError("topo sort algorithm failed");
248
249        out.addAll(outR);
250
251        return out;
252    }
253
254    @Override
255    public String getDescriptionText() {
256        return trn("Purged {0} object", "Purged {0} objects", toPurge.size(), toPurge.size());
257    }
258
259    @Override
260    public Icon getDescriptionIcon() {
261        return ImageProvider.get("data", "purge");
262    }
263
264    @Override
265    public Collection<? extends OsmPrimitive> getParticipatingPrimitives() {
266        return toPurge;
267    }
268
269    @Override
270    public void fillModifiedData(Collection<OsmPrimitive> modified, Collection<OsmPrimitive> deleted, Collection<OsmPrimitive> added) {
271    }
272}