001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.data.validation.tests; 003 004import static org.openstreetmap.josm.tools.I18n.marktr; 005import static org.openstreetmap.josm.tools.I18n.tr; 006 007import java.util.ArrayList; 008import java.util.Collection; 009import java.util.Collections; 010import java.util.HashMap; 011import java.util.HashSet; 012import java.util.Iterator; 013import java.util.LinkedHashSet; 014import java.util.LinkedList; 015import java.util.List; 016import java.util.Map; 017import java.util.Map.Entry; 018import java.util.Set; 019 020import org.openstreetmap.josm.Main; 021import org.openstreetmap.josm.actions.MergeNodesAction; 022import org.openstreetmap.josm.command.Command; 023import org.openstreetmap.josm.command.DeleteCommand; 024import org.openstreetmap.josm.data.coor.LatLon; 025import org.openstreetmap.josm.data.osm.Hash; 026import org.openstreetmap.josm.data.osm.Node; 027import org.openstreetmap.josm.data.osm.OsmPrimitive; 028import org.openstreetmap.josm.data.osm.OsmPrimitiveType; 029import org.openstreetmap.josm.data.osm.Storage; 030import org.openstreetmap.josm.data.osm.Way; 031import org.openstreetmap.josm.data.validation.Severity; 032import org.openstreetmap.josm.data.validation.Test; 033import org.openstreetmap.josm.data.validation.TestError; 034import org.openstreetmap.josm.gui.progress.ProgressMonitor; 035import org.openstreetmap.josm.tools.MultiMap; 036 037/** 038 * Tests if there are duplicate nodes 039 * 040 * @author frsantos 041 */ 042public class DuplicateNode extends Test { 043 044 private static class NodeHash implements Hash<Object, Object> { 045 046 private double precision = Main.pref.getDouble("validator.duplicatenodes.precision", 0.); 047 048 private LatLon roundCoord(LatLon coor) { 049 return new LatLon( 050 Math.round(coor.lat() / precision) * precision, 051 Math.round(coor.lon() / precision) * precision 052 ); 053 } 054 055 @SuppressWarnings("unchecked") 056 private LatLon getLatLon(Object o) { 057 if (o instanceof Node) { 058 LatLon coor = ((Node) o).getCoor(); 059 if (coor == null) 060 return null; 061 if (precision == 0) 062 return coor.getRoundedToOsmPrecision(); 063 return roundCoord(coor); 064 } else if (o instanceof List<?>) { 065 LatLon coor = ((List<Node>) o).get(0).getCoor(); 066 if (coor == null) 067 return null; 068 if (precision == 0) 069 return coor.getRoundedToOsmPrecision(); 070 return roundCoord(coor); 071 } else 072 throw new AssertionError(); 073 } 074 075 @Override 076 public boolean equals(Object k, Object t) { 077 LatLon coorK = getLatLon(k); 078 LatLon coorT = getLatLon(t); 079 return coorK == coorT || (coorK != null && coorT != null && coorK.equals(coorT)); 080 } 081 082 @Override 083 public int getHashCode(Object k) { 084 LatLon coorK = getLatLon(k); 085 return coorK == null ? 0 : coorK.hashCode(); 086 } 087 } 088 089 protected static final int DUPLICATE_NODE = 1; 090 protected static final int DUPLICATE_NODE_MIXED = 2; 091 protected static final int DUPLICATE_NODE_OTHER = 3; 092 protected static final int DUPLICATE_NODE_BUILDING = 10; 093 protected static final int DUPLICATE_NODE_BOUNDARY = 11; 094 protected static final int DUPLICATE_NODE_HIGHWAY = 12; 095 protected static final int DUPLICATE_NODE_LANDUSE = 13; 096 protected static final int DUPLICATE_NODE_NATURAL = 14; 097 protected static final int DUPLICATE_NODE_POWER = 15; 098 protected static final int DUPLICATE_NODE_RAILWAY = 16; 099 protected static final int DUPLICATE_NODE_WATERWAY = 17; 100 101 private static final String[] TYPES = { 102 "none", "highway", "railway", "waterway", "boundary", "power", "natural", "landuse", "building"}; 103 104 /** The map of potential duplicates. 105 * 106 * If there is exactly one node for a given pos, the map includes a pair <pos, Node>. 107 * If there are multiple nodes for a given pos, the map includes a pair 108 * <pos, NodesByEqualTagsMap> 109 */ 110 private Storage<Object> potentialDuplicates; 111 112 /** 113 * Constructor 114 */ 115 public DuplicateNode() { 116 super(tr("Duplicated nodes"), 117 tr("This test checks that there are no nodes at the very same location.")); 118 } 119 120 @Override 121 public void startTest(ProgressMonitor monitor) { 122 super.startTest(monitor); 123 potentialDuplicates = new Storage<>(new NodeHash()); 124 } 125 126 @SuppressWarnings("unchecked") 127 @Override 128 public void endTest() { 129 for (Object v: potentialDuplicates) { 130 if (v instanceof Node) { 131 // just one node at this position. Nothing to report as error 132 continue; 133 } 134 135 // multiple nodes at the same position -> check if all nodes have a distinct elevation 136 List<Node> nodes = (List<Node>) v; 137 Set<String> eles = new HashSet<>(); 138 for (Node n : nodes) { 139 String ele = n.get("ele"); 140 if (ele != null) { 141 eles.add(ele); 142 } 143 } 144 if (eles.size() == nodes.size()) { 145 // All nodes at this position have a distinct elevation. 146 // This is normal in some particular cases (for example, geodesic points in France) 147 // Do not report this as an error 148 continue; 149 } 150 151 // report errors 152 errors.addAll(buildTestErrors(this, nodes)); 153 } 154 super.endTest(); 155 potentialDuplicates = null; 156 } 157 158 /** 159 * Returns the list of "duplicate nodes" errors for the given selection of node and parent test 160 * @param parentTest The parent test of returned errors 161 * @param nodes The nodes selction to look into 162 * @return the list of "duplicate nodes" errors 163 */ 164 public List<TestError> buildTestErrors(Test parentTest, List<Node> nodes) { 165 List<TestError> errors = new ArrayList<>(); 166 167 MultiMap<Map<String, String>, OsmPrimitive> mm = new MultiMap<>(); 168 for (Node n: nodes) { 169 mm.put(n.getKeys(), n); 170 } 171 172 Map<String, Boolean> typeMap = new HashMap<>(); 173 174 // check whether we have multiple nodes at the same position with the same tag set 175 for (Iterator<Map<String, String>> it = mm.keySet().iterator(); it.hasNext();) { 176 Map<String, String> tagSet = it.next(); 177 if (mm.get(tagSet).size() > 1) { 178 179 for (String type: TYPES) { 180 typeMap.put(type, Boolean.FALSE); 181 } 182 183 for (OsmPrimitive p : mm.get(tagSet)) { 184 if (p.getType() == OsmPrimitiveType.NODE) { 185 Node n = (Node) p; 186 List<OsmPrimitive> lp = n.getReferrers(); 187 for (OsmPrimitive sp: lp) { 188 if (sp.getType() == OsmPrimitiveType.WAY) { 189 boolean typed = false; 190 Way w = (Way) sp; 191 Map<String, String> keys = w.getKeys(); 192 for (String type: typeMap.keySet()) { 193 if (keys.containsKey(type)) { 194 typeMap.put(type, Boolean.TRUE); 195 typed = true; 196 } 197 } 198 if (!typed) { 199 typeMap.put("none", Boolean.TRUE); 200 } 201 } 202 } 203 } 204 } 205 206 int nbType = 0; 207 for (Entry<String, Boolean> entry: typeMap.entrySet()) { 208 if (entry.getValue()) { 209 nbType++; 210 } 211 } 212 213 if (nbType > 1) { 214 String msg = marktr("Mixed type duplicated nodes"); 215 errors.add(new TestError( 216 parentTest, 217 Severity.WARNING, 218 tr("Duplicated nodes"), 219 tr(msg), 220 msg, 221 DUPLICATE_NODE_MIXED, 222 mm.get(tagSet) 223 )); 224 } else if (typeMap.get("highway")) { 225 String msg = marktr("Highway duplicated nodes"); 226 errors.add(new TestError( 227 parentTest, 228 Severity.ERROR, 229 tr("Duplicated nodes"), 230 tr(msg), 231 msg, 232 DUPLICATE_NODE_HIGHWAY, 233 mm.get(tagSet) 234 )); 235 } else if (typeMap.get("railway")) { 236 String msg = marktr("Railway duplicated nodes"); 237 errors.add(new TestError( 238 parentTest, 239 Severity.ERROR, 240 tr("Duplicated nodes"), 241 tr(msg), 242 msg, 243 DUPLICATE_NODE_RAILWAY, 244 mm.get(tagSet) 245 )); 246 } else if (typeMap.get("waterway")) { 247 String msg = marktr("Waterway duplicated nodes"); 248 errors.add(new TestError( 249 parentTest, 250 Severity.ERROR, 251 tr("Duplicated nodes"), 252 tr(msg), 253 msg, 254 DUPLICATE_NODE_WATERWAY, 255 mm.get(tagSet) 256 )); 257 } else if (typeMap.get("boundary")) { 258 String msg = marktr("Boundary duplicated nodes"); 259 errors.add(new TestError( 260 parentTest, 261 Severity.ERROR, 262 tr("Duplicated nodes"), 263 tr(msg), 264 msg, 265 DUPLICATE_NODE_BOUNDARY, 266 mm.get(tagSet) 267 )); 268 } else if (typeMap.get("power")) { 269 String msg = marktr("Power duplicated nodes"); 270 errors.add(new TestError( 271 parentTest, 272 Severity.ERROR, 273 tr("Duplicated nodes"), 274 tr(msg), 275 msg, 276 DUPLICATE_NODE_POWER, 277 mm.get(tagSet) 278 )); 279 } else if (typeMap.get("natural")) { 280 String msg = marktr("Natural duplicated nodes"); 281 errors.add(new TestError( 282 parentTest, 283 Severity.ERROR, 284 tr("Duplicated nodes"), 285 tr(msg), 286 msg, 287 DUPLICATE_NODE_NATURAL, 288 mm.get(tagSet) 289 )); 290 } else if (typeMap.get("building")) { 291 String msg = marktr("Building duplicated nodes"); 292 errors.add(new TestError( 293 parentTest, 294 Severity.ERROR, 295 tr("Duplicated nodes"), 296 tr(msg), 297 msg, 298 DUPLICATE_NODE_BUILDING, 299 mm.get(tagSet) 300 )); 301 } else if (typeMap.get("landuse")) { 302 String msg = marktr("Landuse duplicated nodes"); 303 errors.add(new TestError( 304 parentTest, 305 Severity.ERROR, 306 tr("Duplicated nodes"), 307 tr(msg), 308 msg, 309 DUPLICATE_NODE_LANDUSE, 310 mm.get(tagSet) 311 )); 312 } else { 313 String msg = marktr("Other duplicated nodes"); 314 errors.add(new TestError( 315 parentTest, 316 Severity.WARNING, 317 tr("Duplicated nodes"), 318 tr(msg), 319 msg, 320 DUPLICATE_NODE_OTHER, 321 mm.get(tagSet) 322 )); 323 324 } 325 it.remove(); 326 } 327 } 328 329 // check whether we have multiple nodes at the same position with 330 // differing tag sets 331 // 332 if (!mm.isEmpty()) { 333 List<OsmPrimitive> duplicates = new ArrayList<>(); 334 for (Set<OsmPrimitive> l: mm.values()) { 335 duplicates.addAll(l); 336 } 337 if (duplicates.size() > 1) { 338 errors.add(new TestError( 339 parentTest, 340 Severity.WARNING, 341 tr("Nodes at same position"), 342 DUPLICATE_NODE, 343 duplicates 344 )); 345 } 346 } 347 return errors; 348 } 349 350 @SuppressWarnings("unchecked") 351 @Override 352 public void visit(Node n) { 353 if (n.isUsable()) { 354 if (potentialDuplicates.get(n) == null) { 355 // in most cases there is just one node at a given position. We 356 // avoid to create an extra object and add remember the node 357 // itself at this position 358 potentialDuplicates.put(n); 359 } else if (potentialDuplicates.get(n) instanceof Node) { 360 // we have an additional node at the same position. Create an extra 361 // object to keep track of the nodes at this position. 362 // 363 Node n1 = (Node) potentialDuplicates.get(n); 364 List<Node> nodes = new ArrayList<>(2); 365 nodes.add(n1); 366 nodes.add(n); 367 potentialDuplicates.put(nodes); 368 } else if (potentialDuplicates.get(n) instanceof List<?>) { 369 // we have multiple nodes at the same position. 370 // 371 List<Node> nodes = (List<Node>) potentialDuplicates.get(n); 372 nodes.add(n); 373 } 374 } 375 } 376 377 /** 378 * Merge the nodes into one. 379 * Copied from UtilsPlugin.MergePointsAction 380 */ 381 @Override 382 public Command fixError(TestError testError) { 383 if (!isFixable(testError)) return null; 384 Collection<OsmPrimitive> sel = new LinkedList<OsmPrimitive>(testError.getPrimitives()); 385 Set<Node> nodes = new LinkedHashSet<>(OsmPrimitive.getFilteredList(sel, Node.class)); 386 387 // Filter nodes that have already been deleted (see #5764 and #5773) 388 for (Iterator<Node> it = nodes.iterator(); it.hasNext();) { 389 if (it.next().isDeleted()) { 390 it.remove(); 391 } 392 } 393 394 // Merge only if at least 2 nodes remain 395 if (nodes.size() >= 2) { 396 // Use first existing node or first node if all nodes are new 397 Node target = null; 398 for (Node n: nodes) { 399 if (!n.isNew()) { 400 target = n; 401 break; 402 } 403 } 404 if (target == null) { 405 target = nodes.iterator().next(); 406 } 407 408 if (DeleteCommand.checkAndConfirmOutlyingDelete(nodes, Collections.singleton(target))) 409 return MergeNodesAction.mergeNodes(Main.main.getEditLayer(), nodes, target); 410 } 411 412 return null; // undoRedo handling done in mergeNodes 413 } 414 415 @Override 416 public boolean isFixable(TestError testError) { 417 if (!(testError.getTester() instanceof DuplicateNode)) return false; 418 // never merge nodes with different tags. 419 if (testError.getCode() == DUPLICATE_NODE) return false; 420 // everything else is ok to merge 421 return true; 422 } 423}