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    }