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 }