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