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.Objects; 014import java.util.Set; 015 016import javax.swing.Icon; 017 018import org.openstreetmap.josm.data.conflict.Conflict; 019import org.openstreetmap.josm.data.conflict.ConflictCollection; 020import org.openstreetmap.josm.data.osm.DataSet; 021import org.openstreetmap.josm.data.osm.Node; 022import org.openstreetmap.josm.data.osm.NodeData; 023import org.openstreetmap.josm.data.osm.OsmPrimitive; 024import org.openstreetmap.josm.data.osm.PrimitiveData; 025import org.openstreetmap.josm.data.osm.PrimitiveId; 026import org.openstreetmap.josm.data.osm.Relation; 027import org.openstreetmap.josm.data.osm.RelationData; 028import org.openstreetmap.josm.data.osm.RelationMember; 029import org.openstreetmap.josm.data.osm.Storage; 030import org.openstreetmap.josm.data.osm.Way; 031import org.openstreetmap.josm.data.osm.WayData; 032import org.openstreetmap.josm.spi.preferences.Config; 033import org.openstreetmap.josm.tools.ImageProvider; 034 035/** 036 * Command, to purge a list of primitives. 037 */ 038public class PurgeCommand extends Command { 039 protected List<OsmPrimitive> toPurge; 040 protected Storage<PrimitiveData> makeIncompleteData; 041 042 protected Map<PrimitiveId, PrimitiveData> makeIncompleteDataByPrimId; 043 044 protected final ConflictCollection purgedConflicts = new ConflictCollection(); 045 046 /** 047 * Constructs a new {@code PurgeCommand} (does not handle conflicts). 048 * This command relies on a number of consistency conditions: 049 * - makeIncomplete must be a subset of toPurge. 050 * - Each primitive, that is in toPurge but not in makeIncomplete, must have all its referrers in toPurge. 051 * - Each element of makeIncomplete must not be new and must have only referrers that are either a relation or included in toPurge. 052 * @param data OSM data set 053 * @param toPurge primitives to purge 054 * @param makeIncomplete primitives to make incomplete 055 * @since 11240 056 */ 057 public PurgeCommand(DataSet data, Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) { 058 super(data); 059 init(toPurge, makeIncomplete); 060 } 061 062 private void init(Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) { 063 /** 064 * The topological sort is to avoid missing way nodes and missing 065 * relation members when adding primitives back to the dataset on undo. 066 * 067 * The same should hold for normal execution, but at time of writing 068 * there seem to be no such consistency checks when removing primitives. 069 * (It is done in a save manner, anyway.) 070 */ 071 this.toPurge = topoSort(toPurge); 072 saveIncomplete(makeIncomplete); 073 } 074 075 protected final void saveIncomplete(Collection<OsmPrimitive> makeIncomplete) { 076 makeIncompleteData = new Storage<>(new Storage.PrimitiveIdHash()); 077 makeIncompleteDataByPrimId = makeIncompleteData.foreignKey(new Storage.PrimitiveIdHash()); 078 079 for (OsmPrimitive osm : makeIncomplete) { 080 makeIncompleteData.add(osm.save()); 081 } 082 } 083 084 @Override 085 public boolean executeCommand() { 086 getAffectedDataSet().beginUpdate(); 087 try { 088 purgedConflicts.get().clear(); 089 // unselect primitives in advance to not fire a selection change for every one of them 090 getAffectedDataSet().clearSelection(toPurge); 091 // Loop from back to front to keep referential integrity. 092 for (int i = toPurge.size()-1; i >= 0; --i) { 093 OsmPrimitive osm = toPurge.get(i); 094 if (makeIncompleteDataByPrimId.containsKey(osm)) { 095 // we could simply set the incomplete flag 096 // but that would not free memory in case the 097 // user clears undo/redo buffer after purge 098 PrimitiveData empty; 099 switch(osm.getType()) { 100 case NODE: empty = new NodeData(); break; 101 case WAY: empty = new WayData(); break; 102 case RELATION: empty = new RelationData(); break; 103 default: throw new AssertionError(); 104 } 105 empty.setId(osm.getUniqueId()); 106 empty.setIncomplete(true); 107 osm.load(empty); 108 } else { 109 getAffectedDataSet().removePrimitive(osm); 110 Conflict<?> conflict = getAffectedDataSet().getConflicts().getConflictForMy(osm); 111 if (conflict != null) { 112 purgedConflicts.add(conflict); 113 getAffectedDataSet().getConflicts().remove(conflict); 114 } 115 } 116 } 117 getAffectedDataSet().clearMappaintCache(); 118 } finally { 119 getAffectedDataSet().endUpdate(); 120 } 121 return true; 122 } 123 124 @Override 125 public void undoCommand() { 126 if (getAffectedDataSet() == null) 127 return; 128 129 getAffectedDataSet().beginUpdate(); 130 try { 131 for (OsmPrimitive osm : toPurge) { 132 PrimitiveData data = makeIncompleteDataByPrimId.get(osm); 133 if (data != null) { 134 if (getAffectedDataSet().getPrimitiveById(osm) != osm) 135 throw new AssertionError( 136 String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm)); 137 osm.load(data); 138 } else { 139 if (getAffectedDataSet().getPrimitiveById(osm) != null) 140 throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm)); 141 getAffectedDataSet().addPrimitive(osm); 142 } 143 } 144 145 for (Conflict<?> conflict : purgedConflicts) { 146 getAffectedDataSet().getConflicts().add(conflict); 147 } 148 getAffectedDataSet().clearMappaintCache(); 149 } finally { 150 getAffectedDataSet().endUpdate(); 151 } 152 } 153 154 /** 155 * Sorts a collection of primitives such that for each object 156 * its referrers come later in the sorted collection. 157 * @param sel collection of primitives to sort 158 * @return sorted list 159 */ 160 public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) { 161 Set<OsmPrimitive> in = new HashSet<>(sel); 162 List<OsmPrimitive> out = new ArrayList<>(in.size()); 163 Set<Relation> inR = new HashSet<>(); 164 165 // Nodes not deleted in the first pass 166 Set<OsmPrimitive> remainingNodes = new HashSet<>(in.size()); 167 168 /** 169 * First add nodes that have no way referrer. 170 */ 171 outer: 172 for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) { 173 OsmPrimitive u = it.next(); 174 if (u instanceof Node) { 175 Node n = (Node) u; 176 for (OsmPrimitive ref : n.getReferrers()) { 177 if (ref instanceof Way && in.contains(ref)) { 178 it.remove(); 179 remainingNodes.add(n); 180 continue outer; 181 } 182 } 183 it.remove(); 184 out.add(n); 185 } 186 } 187 188 /** 189 * Then add all ways, each preceded by its (remaining) nodes. 190 */ 191 for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) { 192 OsmPrimitive u = it.next(); 193 if (u instanceof Way) { 194 Way w = (Way) u; 195 it.remove(); 196 for (Node n : w.getNodes()) { 197 if (remainingNodes.contains(n)) { 198 remainingNodes.remove(n); 199 out.add(n); 200 } 201 } 202 out.add(w); 203 } else if (u instanceof Relation) { 204 inR.add((Relation) u); 205 } 206 } 207 208 if (!remainingNodes.isEmpty()) 209 throw new AssertionError("topo sort algorithm failed (nodes remaining)"); 210 211 // Do topological sorting on a DAG where each arrow points from child to parent. 212 // (Because it is faster to loop over getReferrers() than getMembers().) 213 214 Map<Relation, Integer> numChilds = new HashMap<>(); 215 216 // calculate initial number of childs 217 for (Relation r : inR) { 218 numChilds.put(r, 0); 219 } 220 for (Relation r : inR) { 221 for (OsmPrimitive parent : r.getReferrers()) { 222 if (!(parent instanceof Relation)) 223 throw new AssertionError(); 224 Integer i = numChilds.get(parent); 225 if (i != null) { 226 numChilds.put((Relation) parent, i+1); 227 } 228 } 229 } 230 Set<Relation> childlessR = new HashSet<>(); 231 for (Relation r : inR) { 232 if (numChilds.get(r).equals(0)) { 233 childlessR.add(r); 234 } 235 } 236 237 List<Relation> outR = new ArrayList<>(inR.size()); 238 while (!childlessR.isEmpty()) { 239 // Identify one childless Relation and let it virtually die. This makes other relations childless. 240 Iterator<Relation> it = childlessR.iterator(); 241 Relation next = it.next(); 242 it.remove(); 243 outR.add(next); 244 245 for (OsmPrimitive parentPrim : next.getReferrers()) { 246 Relation parent = (Relation) parentPrim; 247 Integer i = numChilds.get(parent); 248 if (i != null) { 249 numChilds.put(parent, i-1); 250 if (i-1 == 0) { 251 childlessR.add(parent); 252 } 253 } 254 } 255 } 256 257 if (outR.size() != inR.size()) 258 throw new AssertionError("topo sort algorithm failed"); 259 260 out.addAll(outR); 261 262 return out; 263 } 264 265 @Override 266 public String getDescriptionText() { 267 return trn("Purged {0} object", "Purged {0} objects", toPurge.size(), toPurge.size()); 268 } 269 270 @Override 271 public Icon getDescriptionIcon() { 272 return ImageProvider.get("data", "purge"); 273 } 274 275 @Override 276 public Collection<? extends OsmPrimitive> getParticipatingPrimitives() { 277 return toPurge; 278 } 279 280 @Override 281 public void fillModifiedData(Collection<OsmPrimitive> modified, Collection<OsmPrimitive> deleted, Collection<OsmPrimitive> added) { 282 // Do nothing 283 } 284 285 @Override 286 public int hashCode() { 287 return Objects.hash(super.hashCode(), toPurge, makeIncompleteData, makeIncompleteDataByPrimId, purgedConflicts, getAffectedDataSet()); 288 } 289 290 @Override 291 public boolean equals(Object obj) { 292 if (this == obj) return true; 293 if (obj == null || getClass() != obj.getClass()) return false; 294 if (!super.equals(obj)) return false; 295 PurgeCommand that = (PurgeCommand) obj; 296 return Objects.equals(toPurge, that.toPurge) && 297 Objects.equals(makeIncompleteData, that.makeIncompleteData) && 298 Objects.equals(makeIncompleteDataByPrimId, that.makeIncompleteDataByPrimId) && 299 Objects.equals(purgedConflicts, that.purgedConflicts); 300 } 301 302 /** 303 * Creates a new {@code PurgeCommand} to purge selected OSM primitives. 304 * @param sel selected OSM primitives 305 * @param toPurgeAdditionally optional list that will be filled with primitives to be purged that have not been in the selection 306 * @return command to purge selected OSM primitives 307 * @since 12718 308 */ 309 public static PurgeCommand build(Collection<OsmPrimitive> sel, List<OsmPrimitive> toPurgeAdditionally) { 310 Set<OsmPrimitive> toPurge = new HashSet<>(sel); 311 // finally, contains all objects that are purged 312 Set<OsmPrimitive> toPurgeChecked = new HashSet<>(); 313 314 // Add referrer, unless the object to purge is not new and the parent is a relation 315 Set<OsmPrimitive> toPurgeRecursive = new HashSet<>(); 316 while (!toPurge.isEmpty()) { 317 318 for (OsmPrimitive osm: toPurge) { 319 for (OsmPrimitive parent: osm.getReferrers()) { 320 if (toPurge.contains(parent) || toPurgeChecked.contains(parent) || toPurgeRecursive.contains(parent)) { 321 continue; 322 } 323 if (parent instanceof Way || (parent instanceof Relation && osm.isNew())) { 324 if (toPurgeAdditionally != null) { 325 toPurgeAdditionally.add(parent); 326 } 327 toPurgeRecursive.add(parent); 328 } 329 } 330 toPurgeChecked.add(osm); 331 } 332 toPurge = toPurgeRecursive; 333 toPurgeRecursive = new HashSet<>(); 334 } 335 336 // Subset of toPurgeChecked. Marks primitives that remain in the dataset, but incomplete. 337 Set<OsmPrimitive> makeIncomplete = new HashSet<>(); 338 339 // Find the objects that will be incomplete after purging. 340 // At this point, all parents of new to-be-purged primitives are 341 // also to-be-purged and 342 // all parents of not-new to-be-purged primitives are either 343 // to-be-purged or of type relation. 344 TOP: 345 for (OsmPrimitive child : toPurgeChecked) { 346 if (child.isNew()) { 347 continue; 348 } 349 for (OsmPrimitive parent : child.getReferrers()) { 350 if (parent instanceof Relation && !toPurgeChecked.contains(parent)) { 351 makeIncomplete.add(child); 352 continue TOP; 353 } 354 } 355 } 356 357 // Add untagged way nodes. Do not add nodes that have other referrers not yet to-be-purged. 358 if (Config.getPref().getBoolean("purge.add_untagged_waynodes", true)) { 359 Set<OsmPrimitive> wayNodes = new HashSet<>(); 360 for (OsmPrimitive osm : toPurgeChecked) { 361 if (osm instanceof Way) { 362 Way w = (Way) osm; 363 NODE: 364 for (Node n : w.getNodes()) { 365 if (n.isTagged() || toPurgeChecked.contains(n)) { 366 continue; 367 } 368 for (OsmPrimitive ref : n.getReferrers()) { 369 if (ref != w && !toPurgeChecked.contains(ref)) { 370 continue NODE; 371 } 372 } 373 wayNodes.add(n); 374 } 375 } 376 } 377 toPurgeChecked.addAll(wayNodes); 378 if (toPurgeAdditionally != null) { 379 toPurgeAdditionally.addAll(wayNodes); 380 } 381 } 382 383 if (Config.getPref().getBoolean("purge.add_relations_with_only_incomplete_members", true)) { 384 Set<Relation> relSet = new HashSet<>(); 385 for (OsmPrimitive osm : toPurgeChecked) { 386 for (OsmPrimitive parent : osm.getReferrers()) { 387 if (parent instanceof Relation 388 && !(toPurgeChecked.contains(parent)) 389 && hasOnlyIncompleteMembers((Relation) parent, toPurgeChecked, relSet)) { 390 relSet.add((Relation) parent); 391 } 392 } 393 } 394 395 // Add higher level relations (list gets extended while looping over it) 396 List<Relation> relLst = new ArrayList<>(relSet); 397 for (int i = 0; i < relLst.size(); ++i) { // foreach loop not applicable since list gets extended while looping over it 398 for (OsmPrimitive parent : relLst.get(i).getReferrers()) { 399 if (!(toPurgeChecked.contains(parent)) 400 && hasOnlyIncompleteMembers((Relation) parent, toPurgeChecked, relLst)) { 401 relLst.add((Relation) parent); 402 } 403 } 404 } 405 relSet = new HashSet<>(relLst); 406 toPurgeChecked.addAll(relSet); 407 if (toPurgeAdditionally != null) { 408 toPurgeAdditionally.addAll(relSet); 409 } 410 } 411 412 return new PurgeCommand(toPurgeChecked.iterator().next().getDataSet(), toPurgeChecked, makeIncomplete); 413 } 414 415 private static boolean hasOnlyIncompleteMembers( 416 Relation r, Collection<OsmPrimitive> toPurge, Collection<? extends OsmPrimitive> moreToPurge) { 417 for (RelationMember m : r.getMembers()) { 418 if (!m.getMember().isIncomplete() && !toPurge.contains(m.getMember()) && !moreToPurge.contains(m.getMember())) 419 return false; 420 } 421 return true; 422 } 423}