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