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