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