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