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