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 }