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