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> makeIncompleteData_byPrimId; 041 042 protected final ConflictCollection purgedConflicts = new ConflictCollection(); 043 044 final protected 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 */ 054 public PurgeCommand(OsmDataLayer layer, Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) { 055 super(layer); 056 this.ds = layer.data; 057 /** 058 * The topological sort is to avoid missing way nodes and missing 059 * relation members when adding primitives back to the dataset on undo. 060 * 061 * The same should hold for normal execution, but at time of writing 062 * there seem to be no such consistency checks when removing primitives. 063 * (It is done in a save manner, anyway.) 064 */ 065 this.toPurge = topoSort(toPurge); 066 saveIncomplete(makeIncomplete); 067 } 068 069 protected void saveIncomplete(Collection<OsmPrimitive> makeIncomplete) { 070 makeIncompleteData = new Storage<PrimitiveData>(new Storage.PrimitiveIdHash()); 071 makeIncompleteData_byPrimId = makeIncompleteData.foreignKey(new Storage.PrimitiveIdHash()); 072 073 for (OsmPrimitive osm : makeIncomplete) { 074 makeIncompleteData.add(osm.save()); 075 } 076 } 077 078 @Override 079 public boolean executeCommand() { 080 ds.beginUpdate(); 081 try { 082 purgedConflicts.get().clear(); 083 /** 084 * Loop from back to front to keep referential integrity. 085 */ 086 for (int i=toPurge.size()-1; i>=0; --i) { 087 OsmPrimitive osm = toPurge.get(i); 088 if (makeIncompleteData_byPrimId.containsKey(osm)) { 089 // we could simply set the incomplete flag 090 // but that would not free memory in case the 091 // user clears undo/redo buffer after purge 092 PrimitiveData empty; 093 switch(osm.getType()) { 094 case NODE: empty = new NodeData(); break; 095 case WAY: empty = new WayData(); break; 096 case RELATION: empty = new RelationData(); break; 097 default: throw new AssertionError(); 098 } 099 empty.setId(osm.getUniqueId()); 100 empty.setIncomplete(true); 101 osm.load(empty); 102 } else { 103 ds.removePrimitive(osm); 104 Conflict<?> conflict = getLayer().getConflicts().getConflictForMy(osm); 105 if (conflict != null) { 106 purgedConflicts.add(conflict); 107 getLayer().getConflicts().remove(conflict); 108 } 109 } 110 } 111 } finally { 112 ds.endUpdate(); 113 } 114 return true; 115 } 116 117 @Override 118 public void undoCommand() { 119 if (ds == null) 120 return; 121 122 for (OsmPrimitive osm : toPurge) { 123 PrimitiveData data = makeIncompleteData_byPrimId.get(osm); 124 if (data != null) { 125 if (ds.getPrimitiveById(osm) != osm) 126 throw new AssertionError(String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm)); 127 osm.load(data); 128 } else { 129 if (ds.getPrimitiveById(osm) != null) 130 throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm)); 131 ds.addPrimitive(osm); 132 } 133 } 134 135 for (Conflict<?> conflict : purgedConflicts) { 136 getLayer().getConflicts().add(conflict); 137 } 138 } 139 140 /** 141 * Sorts a collection of primitives such that for each object 142 * its referrers come later in the sorted collection. 143 */ 144 public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) { 145 Set<OsmPrimitive> in = new HashSet<OsmPrimitive>(sel); 146 147 List<OsmPrimitive> out = new ArrayList<OsmPrimitive>(in.size()); 148 149 // Nodes not deleted in the first pass 150 Set<OsmPrimitive> remainingNodes = new HashSet<OsmPrimitive>(in.size()); 151 152 /** 153 * First add nodes that have no way referrer. 154 */ 155 outer: 156 for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) { 157 OsmPrimitive u = it.next(); 158 if (u instanceof Node) { 159 Node n = (Node) u; 160 for (OsmPrimitive ref : n.getReferrers()) { 161 if (ref instanceof Way && in.contains(ref)) { 162 it.remove(); 163 remainingNodes.add(n); 164 continue outer; 165 } 166 } 167 it.remove(); 168 out.add(n); 169 } 170 } 171 172 /** 173 * Then add all ways, each preceded by its (remaining) nodes. 174 */ 175 for (Iterator<OsmPrimitive> it = in.iterator(); it.hasNext();) { 176 OsmPrimitive u = it.next(); 177 if (u instanceof Way) { 178 Way w = (Way) u; 179 it.remove(); 180 for (Node n : w.getNodes()) { 181 if (remainingNodes.contains(n)) { 182 remainingNodes.remove(n); 183 out.add(n); 184 } 185 } 186 out.add(w); 187 } 188 } 189 190 if (!remainingNodes.isEmpty()) 191 throw new AssertionError("topo sort algorithm failed (nodes remaining)"); 192 193 /** 194 * Rest are relations. Do topological sorting on a DAG where each 195 * arrow points from child to parent. (Because it is faster to 196 * loop over getReferrers() than getMembers().) 197 */ 198 @SuppressWarnings({ "unchecked", "rawtypes" }) 199 Set<Relation> inR = (Set) in; 200 Set<Relation> childlessR = new HashSet<Relation>(); 201 List<Relation> outR = new ArrayList<Relation>(inR.size()); 202 203 HashMap<Relation, Integer> numChilds = new HashMap<Relation, Integer>(); 204 205 // calculate initial number of childs 206 for (Relation r : inR) { 207 numChilds.put(r, 0); 208 } 209 for (Relation r : inR) { 210 for (OsmPrimitive parent : r.getReferrers()) { 211 if (!(parent instanceof Relation)) 212 throw new AssertionError(); 213 Integer i = numChilds.get(parent); 214 if (i != null) { 215 numChilds.put((Relation)parent, i+1); 216 } 217 } 218 } 219 for (Relation r : inR) { 220 if (numChilds.get(r).equals(0)) { 221 childlessR.add(r); 222 } 223 } 224 225 while (!childlessR.isEmpty()) { 226 // Identify one childless Relation and 227 // let it virtually die. This makes other 228 // 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("data", "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 } 272}