001// License: GPL. See LICENSE file for details. 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 /** The map of potential duplicates. 102 * 103 * If there is exactly one node for a given pos, the map includes a pair <pos, Node>. 104 * If there are multiple nodes for a given pos, the map includes a pair 105 * <pos, NodesByEqualTagsMap> 106 */ 107 private Storage<Object> potentialDuplicates; 108 109 /** 110 * Constructor 111 */ 112 public DuplicateNode() { 113 super(tr("Duplicated nodes"), 114 tr("This test checks that there are no nodes at the very same location.")); 115 } 116 117 @Override 118 public void startTest(ProgressMonitor monitor) { 119 super.startTest(monitor); 120 potentialDuplicates = new Storage<>(new NodeHash()); 121 } 122 123 124 @SuppressWarnings("unchecked") 125 @Override 126 public void endTest() { 127 for (Object v: potentialDuplicates) { 128 if (v instanceof Node) { 129 // just one node at this position. Nothing to report as error 130 continue; 131 } 132 133 // multiple nodes at the same position -> check if all nodes have a distinct elevation 134 List<Node> nodes = (List<Node>) v; 135 Set<String> eles = new HashSet<>(); 136 for (Node n : nodes) { 137 String ele = n.get("ele"); 138 if (ele != null) { 139 eles.add(ele); 140 } 141 } 142 if (eles.size() == nodes.size()) { 143 // All nodes at this position have a distinct elevation. 144 // This is normal in some particular cases (for example, geodesic points in France) 145 // Do not report this as an error 146 continue; 147 } 148 149 // report errors 150 errors.addAll(buildTestErrors(this, nodes)); 151 } 152 super.endTest(); 153 potentialDuplicates = null; 154 } 155 156 /** 157 * Returns the list of "duplicate nodes" errors for the given selection of node and parent test 158 * @param parentTest The parent test of returned errors 159 * @param nodes The nodes selction to look into 160 * @return the list of "duplicate nodes" errors 161 */ 162 public List<TestError> buildTestErrors(Test parentTest, List<Node> nodes) { 163 List<TestError> errors = new ArrayList<>(); 164 165 MultiMap<Map<String,String>, OsmPrimitive> mm = new MultiMap<>(); 166 for (Node n: nodes) { 167 mm.put(n.getKeys(), n); 168 } 169 170 Map<String,Boolean> typeMap=new HashMap<>(); 171 String[] types = {"none", "highway", "railway", "waterway", "boundary", "power", "natural", "landuse", "building"}; 172 173 174 // check whether we have multiple nodes at the same position with 175 // the same tag set 176 // 177 for (Iterator<Map<String,String>> it = mm.keySet().iterator(); it.hasNext();) { 178 Map<String,String> tagSet = it.next(); 179 if (mm.get(tagSet).size() > 1) { 180 181 for (String type: types) { 182 typeMap.put(type, false); 183 } 184 185 for (OsmPrimitive p : mm.get(tagSet)) { 186 if (p.getType()==OsmPrimitiveType.NODE) { 187 Node n = (Node) p; 188 List<OsmPrimitive> lp=n.getReferrers(); 189 for (OsmPrimitive sp: lp) { 190 if (sp.getType()==OsmPrimitiveType.WAY) { 191 boolean typed = false; 192 Way w=(Way) sp; 193 Map<String, String> keys = w.getKeys(); 194 for (String type: typeMap.keySet()) { 195 if (keys.containsKey(type)) { 196 typeMap.put(type, true); 197 typed=true; 198 } 199 } 200 if (!typed) { 201 typeMap.put("none", true); 202 } 203 } 204 } 205 206 } 207 } 208 209 int nbType=0; 210 for (Entry<String, Boolean> entry: typeMap.entrySet()) { 211 if (entry.getValue()) { 212 nbType++; 213 } 214 } 215 216 if (nbType>1) { 217 String msg = marktr("Mixed type duplicated nodes"); 218 errors.add(new TestError( 219 parentTest, 220 Severity.WARNING, 221 tr("Duplicated nodes"), 222 tr(msg), 223 msg, 224 DUPLICATE_NODE_MIXED, 225 mm.get(tagSet) 226 )); 227 } else if (typeMap.get("highway")) { 228 String msg = marktr("Highway duplicated nodes"); 229 errors.add(new TestError( 230 parentTest, 231 Severity.ERROR, 232 tr("Duplicated nodes"), 233 tr(msg), 234 msg, 235 DUPLICATE_NODE_HIGHWAY, 236 mm.get(tagSet) 237 )); 238 } else if (typeMap.get("railway")) { 239 String msg = marktr("Railway duplicated nodes"); 240 errors.add(new TestError( 241 parentTest, 242 Severity.ERROR, 243 tr("Duplicated nodes"), 244 tr(msg), 245 msg, 246 DUPLICATE_NODE_RAILWAY, 247 mm.get(tagSet) 248 )); 249 } else if (typeMap.get("waterway")) { 250 String msg = marktr("Waterway duplicated nodes"); 251 errors.add(new TestError( 252 parentTest, 253 Severity.ERROR, 254 tr("Duplicated nodes"), 255 tr(msg), 256 msg, 257 DUPLICATE_NODE_WATERWAY, 258 mm.get(tagSet) 259 )); 260 } else if (typeMap.get("boundary")) { 261 String msg = marktr("Boundary duplicated nodes"); 262 errors.add(new TestError( 263 parentTest, 264 Severity.ERROR, 265 tr("Duplicated nodes"), 266 tr(msg), 267 msg, 268 DUPLICATE_NODE_BOUNDARY, 269 mm.get(tagSet) 270 )); 271 } else if (typeMap.get("power")) { 272 String msg = marktr("Power duplicated nodes"); 273 errors.add(new TestError( 274 parentTest, 275 Severity.ERROR, 276 tr("Duplicated nodes"), 277 tr(msg), 278 msg, 279 DUPLICATE_NODE_POWER, 280 mm.get(tagSet) 281 )); 282 } else if (typeMap.get("natural")) { 283 String msg = marktr("Natural duplicated nodes"); 284 errors.add(new TestError( 285 parentTest, 286 Severity.ERROR, 287 tr("Duplicated nodes"), 288 tr(msg), 289 msg, 290 DUPLICATE_NODE_NATURAL, 291 mm.get(tagSet) 292 )); 293 } else if (typeMap.get("building")) { 294 String msg = marktr("Building duplicated nodes"); 295 errors.add(new TestError( 296 parentTest, 297 Severity.ERROR, 298 tr("Duplicated nodes"), 299 tr(msg), 300 msg, 301 DUPLICATE_NODE_BUILDING, 302 mm.get(tagSet) 303 )); 304 } else if (typeMap.get("landuse")) { 305 String msg = marktr("Landuse duplicated nodes"); 306 errors.add(new TestError( 307 parentTest, 308 Severity.ERROR, 309 tr("Duplicated nodes"), 310 tr(msg), 311 msg, 312 DUPLICATE_NODE_LANDUSE, 313 mm.get(tagSet) 314 )); 315 } else { 316 String msg = marktr("Other duplicated nodes"); 317 errors.add(new TestError( 318 parentTest, 319 Severity.WARNING, 320 tr("Duplicated nodes"), 321 tr(msg), 322 msg, 323 DUPLICATE_NODE_OTHER, 324 mm.get(tagSet) 325 )); 326 327 } 328 it.remove(); 329 } 330 } 331 332 // check whether we have multiple nodes at the same position with 333 // differing tag sets 334 // 335 if (!mm.isEmpty()) { 336 List<OsmPrimitive> duplicates = new ArrayList<>(); 337 for (Set<OsmPrimitive> l: mm.values()) { 338 duplicates.addAll(l); 339 } 340 if (duplicates.size() > 1) { 341 errors.add(new TestError( 342 parentTest, 343 Severity.WARNING, 344 tr("Nodes at same position"), 345 DUPLICATE_NODE, 346 duplicates 347 )); 348 } 349 } 350 return errors; 351 } 352 353 @SuppressWarnings("unchecked") 354 @Override 355 public void visit(Node n) { 356 if (n.isUsable()) { 357 if (potentialDuplicates.get(n) == null) { 358 // in most cases there is just one node at a given position. We 359 // avoid to create an extra object and add remember the node 360 // itself at this position 361 potentialDuplicates.put(n); 362 } else if (potentialDuplicates.get(n) instanceof Node) { 363 // we have an additional node at the same position. Create an extra 364 // object to keep track of the nodes at this position. 365 // 366 Node n1 = (Node)potentialDuplicates.get(n); 367 List<Node> nodes = new ArrayList<>(2); 368 nodes.add(n1); 369 nodes.add(n); 370 potentialDuplicates.put(nodes); 371 } else if (potentialDuplicates.get(n) instanceof List<?>) { 372 // we have multiple nodes at the same position. 373 // 374 List<Node> nodes = (List<Node>)potentialDuplicates.get(n); 375 nodes.add(n); 376 } 377 } 378 } 379 380 /** 381 * Merge the nodes into one. 382 * Copied from UtilsPlugin.MergePointsAction 383 */ 384 @Override 385 public Command fixError(TestError testError) { 386 if (!isFixable(testError)) return null; 387 Collection<OsmPrimitive> sel = new LinkedList<>(testError.getPrimitives()); 388 LinkedHashSet<Node> nodes = new LinkedHashSet<>(OsmPrimitive.getFilteredList(sel, Node.class)); 389 390 // Filter nodes that have already been deleted (see #5764 and #5773) 391 for (Iterator<Node> it = nodes.iterator(); it.hasNext();) { 392 if (it.next().isDeleted()) { 393 it.remove(); 394 } 395 } 396 397 // Merge only if at least 2 nodes remain 398 if (nodes.size() >= 2) { 399 // Use first existing node or first node if all nodes are new 400 Node target = null; 401 for (Node n: nodes) { 402 if (!n.isNew()) { 403 target = n; 404 break; 405 } 406 } 407 if (target == null) { 408 target = nodes.iterator().next(); 409 } 410 411 if (DeleteCommand.checkAndConfirmOutlyingDelete(nodes, Collections.singleton(target))) 412 return MergeNodesAction.mergeNodes(Main.main.getEditLayer(), nodes, target); 413 } 414 415 return null;// undoRedo handling done in mergeNodes 416 } 417 418 @Override 419 public boolean isFixable(TestError testError) { 420 if (!(testError.getTester() instanceof DuplicateNode)) return false; 421 // never merge nodes with different tags. 422 if (testError.getCode() == DUPLICATE_NODE) return false; 423 // everything else is ok to merge 424 return true; 425 } 426}