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