001 // License: GPL. For details, see LICENSE file. 002 package org.openstreetmap.josm.command; 003 004 import static org.openstreetmap.josm.tools.I18n.trn; 005 006 import java.util.ArrayList; 007 import java.util.Collection; 008 import java.util.HashMap; 009 import java.util.HashSet; 010 import java.util.Iterator; 011 import java.util.List; 012 import java.util.Map; 013 import java.util.Set; 014 015 import javax.swing.Icon; 016 017 import org.openstreetmap.josm.data.osm.DataSet; 018 import org.openstreetmap.josm.data.osm.Hash; 019 import org.openstreetmap.josm.data.osm.Node; 020 import org.openstreetmap.josm.data.osm.NodeData; 021 import org.openstreetmap.josm.data.osm.OsmPrimitive; 022 import org.openstreetmap.josm.data.osm.PrimitiveData; 023 import org.openstreetmap.josm.data.osm.PrimitiveId; 024 import org.openstreetmap.josm.data.osm.Relation; 025 import org.openstreetmap.josm.data.osm.RelationData; 026 import org.openstreetmap.josm.data.osm.Storage; 027 import org.openstreetmap.josm.data.osm.Way; 028 import org.openstreetmap.josm.data.osm.WayData; 029 import org.openstreetmap.josm.gui.layer.OsmDataLayer; 030 import org.openstreetmap.josm.tools.ImageProvider; 031 032 /** 033 * Command, to purge a list of primitives. 034 */ 035 public class PurgeCommand extends Command { 036 protected List<OsmPrimitive> toPurge; 037 protected Storage<PrimitiveData> makeIncompleteData; 038 039 protected Map<PrimitiveId, PrimitiveData> makeIncompleteData_byPrimId; 040 041 final protected DataSet ds; 042 043 /** 044 * This command relies on a number of consistency conditions: 045 * - makeIncomplete must be a subset of toPurge. 046 * - Each primitive, that is in toPurge but not in makeIncomplete, must 047 * have all its referrers in toPurge. 048 * - Each element of makeIncomplete must not be new and must have only 049 * referrers that are either a relation or included in toPurge. 050 */ 051 public PurgeCommand(OsmDataLayer layer, Collection<OsmPrimitive> toPurge, Collection<OsmPrimitive> makeIncomplete) { 052 super(layer); 053 this.ds = layer.data; 054 /** 055 * The topological sort is to avoid missing way nodes and missing 056 * relation members when adding primitives back to the dataset on undo. 057 * 058 * The same should hold for normal execution, but at time of writing 059 * there seem to be no such consistency checks when removing primitives. 060 * (It is done in a save manner, anyway.) 061 */ 062 this.toPurge = topoSort(toPurge); 063 saveIncomplete(makeIncomplete); 064 } 065 066 protected void saveIncomplete(Collection<OsmPrimitive> makeIncomplete) { 067 makeIncompleteData = new Storage<PrimitiveData>(new Hash<PrimitiveData,PrimitiveData>() { 068 public int getHashCode(PrimitiveData k) { 069 return (int) k.getUniqueId(); 070 } 071 072 public boolean equals(PrimitiveData k, PrimitiveData t) { 073 return k.getUniqueId() == t.getUniqueId() && k.getType() == t.getType(); 074 } 075 }); 076 makeIncompleteData_byPrimId = makeIncompleteData.foreignKey(new Hash<PrimitiveId, PrimitiveData>() { 077 public int getHashCode(PrimitiveId k) { 078 return (int) k.getUniqueId(); 079 } 080 081 public boolean equals(PrimitiveId k, PrimitiveData t) { 082 return k.getUniqueId() == t.getUniqueId() && k.getType() == t.getType(); 083 } 084 }); 085 086 for (OsmPrimitive osm : makeIncomplete) { 087 makeIncompleteData.add(osm.save()); 088 } 089 } 090 091 @Override 092 public boolean executeCommand() { 093 ds.beginUpdate(); 094 try { 095 /** 096 * Loop from back to front to keep referential integrity. 097 */ 098 for (int i=toPurge.size()-1; i>=0; --i) { 099 OsmPrimitive osm = toPurge.get(i); 100 if (makeIncompleteData_byPrimId.containsKey(osm)) { 101 // we could simply set the incomplete flag 102 // but that would not free memory in case the 103 // user clears undo/redo buffer after purge 104 PrimitiveData empty; 105 switch(osm.getType()) { 106 case NODE: empty = new NodeData(); break; 107 case WAY: empty = new WayData(); break; 108 case RELATION: empty = new RelationData(); break; 109 default: throw new AssertionError(); 110 } 111 empty.setId(osm.getUniqueId()); 112 empty.setIncomplete(true); 113 osm.load(empty); 114 } else { 115 ds.removePrimitive(osm); 116 } 117 } 118 } finally { 119 ds.endUpdate(); 120 } 121 return true; 122 } 123 124 @Override 125 public void undoCommand() { 126 if (ds == null) 127 return; 128 129 for (OsmPrimitive osm : toPurge) { 130 PrimitiveData data = makeIncompleteData_byPrimId.get(osm); 131 if (data != null) { 132 if (ds.getPrimitiveById(osm) != osm) 133 throw new AssertionError(String.format("Primitive %s has been made incomplete when purging, but it cannot be found on undo.", osm)); 134 osm.load(data); 135 } else { 136 if (ds.getPrimitiveById(osm) != null) 137 throw new AssertionError(String.format("Primitive %s was removed when purging, but is still there on undo", osm)); 138 ds.addPrimitive(osm); 139 } 140 } 141 } 142 143 /** 144 * Sorts a collection of primitives such that for each object 145 * its referrers come later in the sorted collection. 146 */ 147 public static List<OsmPrimitive> topoSort(Collection<OsmPrimitive> sel) { 148 Set<OsmPrimitive> in = new HashSet<OsmPrimitive>(sel); 149 150 List<OsmPrimitive> out = new ArrayList<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 continue outer; 163 } 164 } 165 it.remove(); 166 out.add(n); 167 } 168 } 169 170 /** 171 * Then add all ways, each preceded by its (remaining) nodes. 172 */ 173 top: 174 while (!in.isEmpty()) { 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 (in.contains(n)) { 182 in.remove(n); 183 out.add(n); 184 } 185 } 186 out.add(w); 187 continue top; 188 } 189 } 190 break; // no more ways left 191 } 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 Set<Relation> inR = (Set) in; 199 Set<Relation> childlessR = new HashSet<Relation>(); 200 List<Relation> outR = new ArrayList<Relation>(inR.size()); 201 202 HashMap<Relation, Integer> numChilds = new HashMap<Relation, Integer>(); 203 204 // calculate initial number of childs 205 for (Relation r : inR) { 206 numChilds.put(r, 0); 207 } 208 for (Relation r : inR) { 209 for (OsmPrimitive parent : r.getReferrers()) { 210 if (!(parent instanceof Relation)) 211 throw new AssertionError(); 212 Integer i = numChilds.get(parent); 213 if (i != null) { 214 numChilds.put((Relation)parent, i+1); 215 } 216 } 217 } 218 for (Relation r : inR) { 219 if (numChilds.get(r).equals(0)) { 220 childlessR.add(r); 221 } 222 } 223 224 while (!childlessR.isEmpty()) { 225 // Identify one childless Relation and 226 // let it virtually die. This makes other 227 // relations childless. 228 Iterator<Relation> it = childlessR.iterator(); 229 Relation next = it.next(); 230 it.remove(); 231 outR.add(next); 232 233 for (OsmPrimitive parentPrim : next.getReferrers()) { 234 Relation parent = (Relation) parentPrim; 235 Integer i = numChilds.get(parent); 236 if (i != null) { 237 numChilds.put(parent, i-1); 238 if (i-1 == 0) { 239 childlessR.add(parent); 240 } 241 } 242 } 243 } 244 245 if (outR.size() != inR.size()) 246 throw new AssertionError("topo sort algorithm failed"); 247 248 out.addAll(outR); 249 250 return out; 251 } 252 253 @Override 254 public String getDescriptionText() { 255 return trn("Purged {0} object", "Purged {0} objects", toPurge.size(), toPurge.size()); 256 } 257 258 @Override 259 public Icon getDescriptionIcon() { 260 return ImageProvider.get("data", "purge"); 261 } 262 263 @Override 264 public Collection<? extends OsmPrimitive> getParticipatingPrimitives() { 265 return toPurge; 266 } 267 268 @Override 269 public void fillModifiedData(Collection<OsmPrimitive> modified, Collection<OsmPrimitive> deleted, Collection<OsmPrimitive> added) { 270 } 271 }