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.data.coor.LatLon; 024import org.openstreetmap.josm.data.osm.Hash; 025import org.openstreetmap.josm.data.osm.Node; 026import org.openstreetmap.josm.data.osm.OsmPrimitive; 027import org.openstreetmap.josm.data.osm.OsmPrimitiveType; 028import org.openstreetmap.josm.data.osm.Storage; 029import org.openstreetmap.josm.data.osm.Way; 030import org.openstreetmap.josm.data.validation.Severity; 031import org.openstreetmap.josm.data.validation.Test; 032import org.openstreetmap.josm.data.validation.TestError; 033import org.openstreetmap.josm.gui.progress.ProgressMonitor; 034import org.openstreetmap.josm.tools.MultiMap; 035 036/** 037 * Tests if there are duplicate nodes 038 * 039 * @author frsantos 040 */ 041public class DuplicateNode extends Test { 042 043 private static class NodeHash implements Hash<Object, Object> { 044 045 private final 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 static final int DUPLICATE_NODE = 1; 089 protected static final int DUPLICATE_NODE_MIXED = 2; 090 protected static final int DUPLICATE_NODE_OTHER = 3; 091 protected static final int DUPLICATE_NODE_BUILDING = 10; 092 protected static final int DUPLICATE_NODE_BOUNDARY = 11; 093 protected static final int DUPLICATE_NODE_HIGHWAY = 12; 094 protected static final int DUPLICATE_NODE_LANDUSE = 13; 095 protected static final int DUPLICATE_NODE_NATURAL = 14; 096 protected static final int DUPLICATE_NODE_POWER = 15; 097 protected static final int DUPLICATE_NODE_RAILWAY = 16; 098 protected static final int DUPLICATE_NODE_WATERWAY = 17; 099 100 private static final String[] TYPES = { 101 "none", "highway", "railway", "waterway", "boundary", "power", "natural", "landuse", "building"}; 102 103 /** The map of potential duplicates. 104 * 105 * If there is exactly one node for a given pos, the map includes a pair <pos, Node>. 106 * If there are multiple nodes for a given pos, the map includes a pair 107 * <pos, NodesByEqualTagsMap> 108 */ 109 private Storage<Object> potentialDuplicates; 110 111 /** 112 * Constructor 113 */ 114 public DuplicateNode() { 115 super(tr("Duplicated nodes"), 116 tr("This test checks that there are no nodes at the very same location.")); 117 } 118 119 @Override 120 public void startTest(ProgressMonitor monitor) { 121 super.startTest(monitor); 122 potentialDuplicates = new Storage<>(new NodeHash()); 123 } 124 125 @SuppressWarnings("unchecked") 126 @Override 127 public void endTest() { 128 for (Object v: potentialDuplicates) { 129 if (v instanceof Node) { 130 // just one node at this position. Nothing to report as error 131 continue; 132 } 133 134 // multiple nodes at the same position -> check if all nodes have a distinct elevation 135 List<Node> nodes = (List<Node>) v; 136 Set<String> eles = new HashSet<>(); 137 for (Node n : nodes) { 138 String ele = n.get("ele"); 139 if (ele != null) { 140 eles.add(ele); 141 } 142 } 143 if (eles.size() == nodes.size()) { 144 // All nodes at this position have a distinct elevation. 145 // This is normal in some particular cases (for example, geodesic points in France) 146 // Do not report this as an error 147 continue; 148 } 149 150 // report errors 151 errors.addAll(buildTestErrors(this, nodes)); 152 } 153 super.endTest(); 154 potentialDuplicates = null; 155 } 156 157 /** 158 * Returns the list of "duplicate nodes" errors for the given selection of node and parent test 159 * @param parentTest The parent test of returned errors 160 * @param nodes The nodes selction to look into 161 * @return the list of "duplicate nodes" errors 162 */ 163 public List<TestError> buildTestErrors(Test parentTest, List<Node> nodes) { 164 List<TestError> errors = new ArrayList<>(); 165 166 MultiMap<Map<String, String>, OsmPrimitive> mm = new MultiMap<>(); 167 for (Node n: nodes) { 168 mm.put(n.getKeys(), n); 169 } 170 171 Map<String, Boolean> typeMap = new HashMap<>(); 172 173 // check whether we have multiple nodes at the same position with the same tag set 174 for (Iterator<Map<String, String>> it = mm.keySet().iterator(); it.hasNext();) { 175 Set<OsmPrimitive> primitives = mm.get(it.next()); 176 if (primitives.size() > 1) { 177 178 for (String type: TYPES) { 179 typeMap.put(type, Boolean.FALSE); 180 } 181 182 for (OsmPrimitive p : primitives) { 183 if (p.getType() == OsmPrimitiveType.NODE) { 184 Node n = (Node) p; 185 List<OsmPrimitive> lp = n.getReferrers(); 186 for (OsmPrimitive sp: lp) { 187 if (sp.getType() == OsmPrimitiveType.WAY) { 188 boolean typed = false; 189 Way w = (Way) sp; 190 Map<String, String> keys = w.getKeys(); 191 for (String type: typeMap.keySet()) { 192 if (keys.containsKey(type)) { 193 typeMap.put(type, Boolean.TRUE); 194 typed = true; 195 } 196 } 197 if (!typed) { 198 typeMap.put("none", Boolean.TRUE); 199 } 200 } 201 } 202 } 203 } 204 205 long nbType = typeMap.entrySet().stream().filter(Entry::getValue).count(); 206 207 if (nbType > 1) { 208 errors.add(TestError.builder(parentTest, Severity.WARNING, DUPLICATE_NODE_MIXED) 209 .message(marktr("Mixed type duplicated nodes")) 210 .primitives(primitives) 211 .build()); 212 } else if (typeMap.get("highway")) { 213 errors.add(TestError.builder(parentTest, Severity.ERROR, DUPLICATE_NODE_HIGHWAY) 214 .message(marktr("Highway duplicated nodes")) 215 .primitives(primitives) 216 .build()); 217 } else if (typeMap.get("railway")) { 218 errors.add(TestError.builder(parentTest, Severity.ERROR, DUPLICATE_NODE_RAILWAY) 219 .message(marktr("Railway duplicated nodes")) 220 .primitives(primitives) 221 .build()); 222 } else if (typeMap.get("waterway")) { 223 errors.add(TestError.builder(parentTest, Severity.ERROR, DUPLICATE_NODE_WATERWAY) 224 .message(marktr("Waterway duplicated nodes")) 225 .primitives(primitives) 226 .build()); 227 } else if (typeMap.get("boundary")) { 228 errors.add(TestError.builder(parentTest, Severity.ERROR, DUPLICATE_NODE_BOUNDARY) 229 .message(marktr("Boundary duplicated nodes")) 230 .primitives(primitives) 231 .build()); 232 } else if (typeMap.get("power")) { 233 errors.add(TestError.builder(parentTest, Severity.ERROR, DUPLICATE_NODE_POWER) 234 .message(marktr("Power duplicated nodes")) 235 .primitives(primitives) 236 .build()); 237 } else if (typeMap.get("natural")) { 238 errors.add(TestError.builder(parentTest, Severity.ERROR, DUPLICATE_NODE_NATURAL) 239 .message(marktr("Natural duplicated nodes")) 240 .primitives(primitives) 241 .build()); 242 } else if (typeMap.get("building")) { 243 errors.add(TestError.builder(parentTest, Severity.ERROR, DUPLICATE_NODE_BUILDING) 244 .message(marktr("Building duplicated nodes")) 245 .primitives(primitives) 246 .build()); 247 } else if (typeMap.get("landuse")) { 248 errors.add(TestError.builder(parentTest, Severity.ERROR, DUPLICATE_NODE_LANDUSE) 249 .message(marktr("Landuse duplicated nodes")) 250 .primitives(primitives) 251 .build()); 252 } else { 253 errors.add(TestError.builder(parentTest, Severity.WARNING, DUPLICATE_NODE_OTHER) 254 .message(marktr("Other duplicated nodes")) 255 .primitives(primitives) 256 .build()); 257 } 258 it.remove(); 259 } 260 } 261 262 // check whether we have multiple nodes at the same position with differing tag sets 263 if (!mm.isEmpty()) { 264 List<OsmPrimitive> duplicates = new ArrayList<>(); 265 for (Set<OsmPrimitive> l: mm.values()) { 266 duplicates.addAll(l); 267 } 268 if (duplicates.size() > 1) { 269 errors.add(TestError.builder(parentTest, Severity.WARNING, DUPLICATE_NODE) 270 .message(tr("Nodes at same position")) 271 .primitives(duplicates) 272 .build()); 273 } 274 } 275 return errors; 276 } 277 278 @SuppressWarnings("unchecked") 279 @Override 280 public void visit(Node n) { 281 if (n.isUsable()) { 282 if (potentialDuplicates.get(n) == null) { 283 // in most cases there is just one node at a given position. We 284 // avoid to create an extra object and add remember the node 285 // itself at this position 286 potentialDuplicates.put(n); 287 } else if (potentialDuplicates.get(n) instanceof Node) { 288 // we have an additional node at the same position. Create an extra 289 // object to keep track of the nodes at this position. 290 // 291 Node n1 = (Node) potentialDuplicates.get(n); 292 List<Node> nodes = new ArrayList<>(2); 293 nodes.add(n1); 294 nodes.add(n); 295 potentialDuplicates.put(nodes); 296 } else if (potentialDuplicates.get(n) instanceof List<?>) { 297 // we have multiple nodes at the same position. 298 // 299 List<Node> nodes = (List<Node>) potentialDuplicates.get(n); 300 nodes.add(n); 301 } 302 } 303 } 304 305 /** 306 * Merge the nodes into one. 307 * Copied from UtilsPlugin.MergePointsAction 308 */ 309 @Override 310 public Command fixError(TestError testError) { 311 if (!isFixable(testError)) return null; 312 // Diamond operator does not work with Java 9 here 313 @SuppressWarnings("unused") 314 Collection<OsmPrimitive> sel = new LinkedList<OsmPrimitive>(testError.getPrimitives()); 315 Set<Node> nodes = new LinkedHashSet<>(OsmPrimitive.getFilteredList(sel, Node.class)); 316 317 // Filter nodes that have already been deleted (see #5764 and #5773) 318 for (Iterator<Node> it = nodes.iterator(); it.hasNext();) { 319 if (it.next().isDeleted()) { 320 it.remove(); 321 } 322 } 323 324 // Merge only if at least 2 nodes remain 325 if (nodes.size() >= 2) { 326 // Use first existing node or first node if all nodes are new 327 Node target = null; 328 for (Node n: nodes) { 329 if (!n.isNew()) { 330 target = n; 331 break; 332 } 333 } 334 if (target == null) { 335 target = nodes.iterator().next(); 336 } 337 338 if (Command.checkOutlyingOrIncompleteOperation(nodes, Collections.singleton(target)) == Command.IS_OK) 339 return MergeNodesAction.mergeNodes(Main.getLayerManager().getEditLayer(), nodes, target); 340 } 341 342 return null; // undoRedo handling done in mergeNodes 343 } 344 345 @Override 346 public boolean isFixable(TestError testError) { 347 if (!(testError.getTester() instanceof DuplicateNode)) return false; 348 // never merge nodes with different tags. 349 if (testError.getCode() == DUPLICATE_NODE) return false; 350 // cannot merge nodes outside download area 351 final Iterator<? extends OsmPrimitive> it = testError.getPrimitives().iterator(); 352 if (!it.hasNext() || it.next().isOutsideDownloadArea()) return false; 353 // everything else is ok to merge 354 return true; 355 } 356}