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