001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.command;
003    
004    import static org.openstreetmap.josm.tools.I18n.trn;
005    
006    import java.util.ArrayList;
007    import java.util.Collection;
008    import java.util.HashMap;
009    import java.util.HashSet;
010    import java.util.Iterator;
011    import java.util.List;
012    import java.util.Map;
013    import java.util.Set;
014    
015    import javax.swing.Icon;
016    
017    import org.openstreetmap.josm.data.osm.DataSet;
018    import org.openstreetmap.josm.data.osm.Hash;
019    import org.openstreetmap.josm.data.osm.Node;
020    import org.openstreetmap.josm.data.osm.NodeData;
021    import org.openstreetmap.josm.data.osm.OsmPrimitive;
022    import org.openstreetmap.josm.data.osm.PrimitiveData;
023    import org.openstreetmap.josm.data.osm.PrimitiveId;
024    import org.openstreetmap.josm.data.osm.Relation;
025    import org.openstreetmap.josm.data.osm.RelationData;
026    import org.openstreetmap.josm.data.osm.Storage;
027    import org.openstreetmap.josm.data.osm.Way;
028    import org.openstreetmap.josm.data.osm.WayData;
029    import org.openstreetmap.josm.gui.layer.OsmDataLayer;
030    import org.openstreetmap.josm.tools.ImageProvider;
031    
032    /**
033     * Command, to purge a list of primitives.
034     */
035    public class PurgeCommand extends Command {
036        protected List<OsmPrimitive> toPurge;
037        protected Storage<PrimitiveData> makeIncompleteData;
038    
039        protected Map<PrimitiveId, PrimitiveData> makeIncompleteData_byPrimId;
040    
041        final protected DataSet ds;
042    
043        /**
044         * This command relies on a number of consistency conditions:
045         *  - makeIncomplete must be a subset of toPurge.
046         *  - Each primitive, that is in toPurge but not in makeIncomplete, must
047         *      have all its referrers in toPurge.
048         *  - Each element of makeIncomplete must not be new and must have only
049         *      referrers that are either a relation or included in toPurge.
050         */
051        public PurgeCommand(OsmDataLayer layer, Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) {
052            super(layer);
053            this.ds = layer.data;
054            /**
055             * The topological sort is to avoid missing way nodes and missing
056             * relation members when adding primitives back to the dataset on undo.
057             *
058             * The same should hold for normal execution, but at time of writing
059             * there seem to be no such consistency checks when removing primitives.
060             * (It is done in a save manner, anyway.)
061             */
062            this.toPurge = topoSort(toPurge);
063            saveIncomplete(makeIncomplete);
064        }
065    
066        protected void saveIncomplete(Collection<OsmPrimitive> makeIncomplete) {
067            makeIncompleteData = new Storage<PrimitiveData>(new Hash<PrimitiveData,PrimitiveData>() {
068                public int getHashCode(PrimitiveData k) {
069                    return (int) k.getUniqueId();
070                }
071    
072                public boolean equals(PrimitiveData k, PrimitiveData t) {
073                    return k.getUniqueId() == t.getUniqueId() && k.getType() == t.getType();
074                }
075            });
076            makeIncompleteData_byPrimId = makeIncompleteData.foreignKey(new Hash<PrimitiveId, PrimitiveData>() {
077                public int getHashCode(PrimitiveId k) {
078                    return (int) k.getUniqueId();
079                }
080    
081                public boolean equals(PrimitiveId k, PrimitiveData t) {
082                    return k.getUniqueId() == t.getUniqueId() && k.getType() == t.getType();
083                }
084            });
085    
086            for (OsmPrimitive osm : makeIncomplete) {
087                makeIncompleteData.add(osm.save());
088            }
089        }
090    
091        @Override
092        public boolean executeCommand() {
093            ds.beginUpdate();
094            try {
095                /**
096                 * Loop from back to front to keep referential integrity.
097                 */
098                for (int i=toPurge.size()-1; i>=0; --i) {
099                    OsmPrimitive osm = toPurge.get(i);
100                    if (makeIncompleteData_byPrimId.containsKey(osm)) {
101                        // we could simply set the incomplete flag
102                        // but that would not free memory in case the
103                        // user clears undo/redo buffer after purge
104                        PrimitiveData empty;
105                        switch(osm.getType()) {
106                        case NODE: empty = new NodeData(); break;
107                        case WAY: empty = new WayData(); break;
108                        case RELATION: empty = new RelationData(); break;
109                        default: throw new AssertionError();
110                        }
111                        empty.setId(osm.getUniqueId());
112                        empty.setIncomplete(true);
113                        osm.load(empty);
114                    } else {
115                        ds.removePrimitive(osm);
116                    }
117                }
118            } finally {
119                ds.endUpdate();
120            }
121            return true;
122        }
123    
124        @Override
125        public void undoCommand() {
126            if (ds == null)
127                return;
128    
129            for (OsmPrimitive osm : toPurge) {
130                PrimitiveData data = makeIncompleteData_byPrimId.get(osm);
131                if (data != null) {
132                    if (ds.getPrimitiveById(osm) != osm)
133                        throw new AssertionError(String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm));
134                    osm.load(data);
135                } else {
136                    if (ds.getPrimitiveById(osm) != null)
137                        throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm));
138                    ds.addPrimitive(osm);
139                }
140            }
141        }
142    
143        /**
144         * Sorts a collection of primitives such that for each object
145         * its referrers come later in the sorted collection.
146         */
147        public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) {
148            Set<OsmPrimitive> in = new HashSet<OsmPrimitive>(sel);
149    
150            List<OsmPrimitive> out = new ArrayList<OsmPrimitive>(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                                continue outer;
163                            }
164                        }
165                        it.remove();
166                        out.add(n);
167                    }
168                }
169    
170            /**
171             * Then add all ways, each preceded by its (remaining) nodes.
172             */
173            top:
174                while (!in.isEmpty()) {
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 (in.contains(n)) {
182                                    in.remove(n);
183                                    out.add(n);
184                                }
185                            }
186                            out.add(w);
187                            continue top;
188                        }
189                    }
190                    break; // no more ways left
191                }
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            Set<Relation> inR = (Set) in;
199            Set<Relation> childlessR = new HashSet<Relation>();
200            List<Relation> outR = new ArrayList<Relation>(inR.size());
201    
202            HashMap<Relation, Integer> numChilds = new HashMap<Relation, Integer>();
203    
204            // calculate initial number of childs
205            for (Relation r : inR) {
206                numChilds.put(r, 0);
207            }
208            for (Relation r : inR) {
209                for (OsmPrimitive parent : r.getReferrers()) {
210                    if (!(parent instanceof Relation))
211                        throw new AssertionError();
212                    Integer i = numChilds.get(parent);
213                    if (i != null) {
214                        numChilds.put((Relation)parent, i+1);
215                    }
216                }
217            }
218            for (Relation r : inR) {
219                if (numChilds.get(r).equals(0)) {
220                    childlessR.add(r);
221                }
222            }
223    
224            while (!childlessR.isEmpty()) {
225                // Identify one childless Relation and
226                // let it virtually die. This makes other
227                // relations childless.
228                Iterator<Relation> it  = childlessR.iterator();
229                Relation next = it.next();
230                it.remove();
231                outR.add(next);
232    
233                for (OsmPrimitive parentPrim : next.getReferrers()) {
234                    Relation parent = (Relation) parentPrim;
235                    Integer i = numChilds.get(parent);
236                    if (i != null) {
237                        numChilds.put(parent, i-1);
238                        if (i-1 == 0) {
239                            childlessR.add(parent);
240                        }
241                    }
242                }
243            }
244    
245            if (outR.size() != inR.size())
246                throw new AssertionError("topo sort algorithm failed");
247    
248            out.addAll(outR);
249    
250            return out;
251        }
252    
253        @Override
254        public String getDescriptionText() {
255            return trn("Purged {0} object", "Purged {0} objects", toPurge.size(), toPurge.size());
256        }
257    
258        @Override
259        public Icon getDescriptionIcon() {
260            return ImageProvider.get("data", "purge");
261        }
262    
263        @Override
264        public Collection<? extends OsmPrimitive> getParticipatingPrimitives() {
265            return toPurge;
266        }
267    
268        @Override
269        public void fillModifiedData(Collection<OsmPrimitive> modified, Collection<OsmPrimitive> deleted, Collection<OsmPrimitive> added) {
270        }
271    }