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.Iterator;
012    import java.util.LinkedHashSet;
013    import java.util.LinkedList;
014    import java.util.List;
015    import java.util.Map;
016    import java.util.Set;
017    
018    import org.openstreetmap.josm.Main;
019    import org.openstreetmap.josm.actions.MergeNodesAction;
020    import org.openstreetmap.josm.command.Command;
021    import org.openstreetmap.josm.command.DeleteCommand;
022    import org.openstreetmap.josm.data.coor.LatLon;
023    import org.openstreetmap.josm.data.osm.Hash;
024    import org.openstreetmap.josm.data.osm.Node;
025    import org.openstreetmap.josm.data.osm.OsmPrimitive;
026    import org.openstreetmap.josm.data.osm.OsmPrimitiveType;
027    import org.openstreetmap.josm.data.osm.Storage;
028    import org.openstreetmap.josm.data.osm.Way;
029    import org.openstreetmap.josm.data.validation.Severity;
030    import org.openstreetmap.josm.data.validation.Test;
031    import org.openstreetmap.josm.data.validation.TestError;
032    import org.openstreetmap.josm.gui.progress.ProgressMonitor;
033    import org.openstreetmap.josm.tools.MultiMap;
034    
035    /**
036     * Tests if there are duplicate nodes
037     *
038     * @author frsantos
039     */
040    public class DuplicateNode extends Test {
041    
042        private static class NodeHash implements Hash<Object, Object> {
043    
044            double precision = Main.pref.getDouble("validator.duplicatenodes.precision", 0.);
045    
046            private LatLon roundCoord(LatLon coor) {
047                return new LatLon(
048                        Math.round(coor.lat() / precision) * precision,
049                        Math.round(coor.lon() / precision) * precision
050                        );
051            }
052    
053            @SuppressWarnings("unchecked")
054            private LatLon getLatLon(Object o) {
055                if (o instanceof Node) {
056                    LatLon coor = ((Node) o).getCoor();
057                    if (coor == null)
058                        return null;
059                    if (precision==0)
060                        return coor.getRoundedToOsmPrecision();
061                    return roundCoord(coor);
062                } else if (o instanceof List<?>) {
063                    LatLon coor = ((List<Node>) o).get(0).getCoor();
064                    if (coor == null)
065                        return null;
066                    if (precision==0)
067                        return coor.getRoundedToOsmPrecision();
068                    return roundCoord(coor);
069                } else
070                    throw new AssertionError();
071            }
072    
073            @Override
074            public boolean equals(Object k, Object t) {
075                LatLon coorK = getLatLon(k);
076                LatLon coorT = getLatLon(t);
077                return coorK == coorT || (coorK != null && coorT != null && coorK.equals(coorT));
078            }
079    
080            @Override
081            public int getHashCode(Object k) {
082                LatLon coorK = getLatLon(k);
083                return coorK == null ? 0 : coorK.hashCode();
084            }
085        }
086    
087        protected final static int DUPLICATE_NODE = 1;
088        protected final static int DUPLICATE_NODE_MIXED = 2;
089        protected final static int DUPLICATE_NODE_OTHER = 3;
090        protected final static int DUPLICATE_NODE_UNCLOSED = 4;
091        protected final static int DUPLICATE_NODE_BUILDING = 10;
092        protected final static int DUPLICATE_NODE_BOUNDARY = 11;
093        protected final static int DUPLICATE_NODE_HIGHWAY = 12;
094        protected final static int DUPLICATE_NODE_LANDUSE = 13;
095        protected final static int DUPLICATE_NODE_NATURAL = 14;
096        protected final static int DUPLICATE_NODE_POWER = 15;
097        protected final static int DUPLICATE_NODE_RAILWAY = 16;
098        protected final static int DUPLICATE_NODE_WATERWAY = 17;
099    
100        /** The map of potential duplicates.
101         *
102         * If there is exactly one node for a given pos, the map includes a pair <pos, Node>.
103         * If there are multiple nodes for a given pos, the map includes a pair
104         * <pos, NodesByEqualTagsMap>
105         */
106        Storage<Object> potentialDuplicates;
107    
108        /**
109         * Constructor
110         */
111        public DuplicateNode() {
112            super(tr("Duplicated nodes"),
113                    tr("This test checks that there are no nodes at the very same location."));
114        }
115    
116        @Override
117        public void startTest(ProgressMonitor monitor) {
118            super.startTest(monitor);
119            potentialDuplicates = new Storage<Object>(new NodeHash());
120        }
121    
122    
123        @SuppressWarnings("unchecked")
124        @Override
125        public void endTest() {
126            for (Object v: potentialDuplicates) {
127                if (v instanceof Node) {
128                    // just one node at this position. Nothing to report as
129                    // error
130                    continue;
131                }
132    
133                // multiple nodes at the same position -> report errors
134                //
135                List<Node> nodes = (List<Node>) v;
136                errors.addAll(buildTestErrors(this, nodes));
137            }
138            super.endTest();
139            potentialDuplicates = null;
140        }
141    
142        public List<TestError> buildTestErrors(Test parentTest, List<Node> nodes) {
143            List<TestError> errors = new ArrayList<TestError>();
144    
145            MultiMap<Map<String,String>, OsmPrimitive> mm = new MultiMap<Map<String,String>, OsmPrimitive>();
146            for (Node n: nodes) {
147                mm.put(n.getKeys(), n);
148            }
149    
150            Map<String,Boolean> typeMap=new HashMap<String,Boolean>();
151            String[] types = {"none", "highway", "railway", "waterway", "boundary", "power", "natural", "landuse", "building"};
152    
153    
154            // check whether we have multiple nodes at the same position with
155            // the same tag set
156            //
157            for (Iterator<Map<String,String>> it = mm.keySet().iterator(); it.hasNext();) {
158                Map<String,String> tagSet = it.next();
159                if (mm.get(tagSet).size() > 1) {
160    
161                    boolean oneWayClosed = false;
162    
163                    for (String type: types) {
164                        typeMap.put(type, false);
165                    }
166    
167                    for (OsmPrimitive p : mm.get(tagSet)) {
168                        if (p.getType()==OsmPrimitiveType.NODE) {
169                            Node n = (Node) p;
170                            List<OsmPrimitive> lp=n.getReferrers();
171                            for (OsmPrimitive sp: lp) {
172                                if (sp.getType()==OsmPrimitiveType.WAY) {
173                                    boolean typed = false;
174                                    Way w=(Way) sp;
175                                    oneWayClosed = oneWayClosed || w.isClosed();
176                                    Map<String, String> keys = w.getKeys();
177                                    for (String type: typeMap.keySet()) {
178                                        if (keys.containsKey(type)) {
179                                            typeMap.put(type, true);
180                                            typed=true;
181                                        }
182                                    }
183                                    if (!typed) {
184                                        typeMap.put("none", true);
185                                    }
186                                }
187                            }
188    
189                        }
190                    }
191    
192                    int nbType=0;
193                    for (String type: typeMap.keySet()) {
194                        if (typeMap.get(type)) {
195                            nbType++;
196                        }
197                    }
198    
199                    if (!oneWayClosed) {
200                        String msg = marktr("Duplicate nodes in two un-closed ways");
201                        errors.add(new TestError(
202                                parentTest,
203                                Severity.WARNING,
204                                tr("Duplicated nodes"),
205                                tr(msg),
206                                msg,
207                                DUPLICATE_NODE_UNCLOSED,
208                                mm.get(tagSet)
209                                ));
210                    } else if (nbType>1) {
211                        String msg = marktr("Mixed type duplicated nodes");
212                        errors.add(new TestError(
213                                parentTest,
214                                Severity.WARNING,
215                                tr("Duplicated nodes"),
216                                tr(msg),
217                                msg,
218                                DUPLICATE_NODE_MIXED,
219                                mm.get(tagSet)
220                                ));
221                    } else if (typeMap.get("highway")) {
222                        String msg = marktr("Highway duplicated nodes");
223                        errors.add(new TestError(
224                                parentTest,
225                                Severity.ERROR,
226                                tr("Duplicated nodes"),
227                                tr(msg),
228                                msg,
229                                DUPLICATE_NODE_HIGHWAY,
230                                mm.get(tagSet)
231                                ));
232                    } else if (typeMap.get("railway")) {
233                        String msg = marktr("Railway duplicated nodes");
234                        errors.add(new TestError(
235                                parentTest,
236                                Severity.ERROR,
237                                tr("Duplicated nodes"),
238                                tr(msg),
239                                msg,
240                                DUPLICATE_NODE_RAILWAY,
241                                mm.get(tagSet)
242                                ));
243                    } else if (typeMap.get("waterway")) {
244                        String msg = marktr("Waterway duplicated nodes");
245                        errors.add(new TestError(
246                                parentTest,
247                                Severity.ERROR,
248                                tr("Duplicated nodes"),
249                                tr(msg),
250                                msg,
251                                DUPLICATE_NODE_WATERWAY,
252                                mm.get(tagSet)
253                                ));
254                    } else if (typeMap.get("boundary")) {
255                        String msg = marktr("Boundary duplicated nodes");
256                        errors.add(new TestError(
257                                parentTest,
258                                Severity.ERROR,
259                                tr("Duplicated nodes"),
260                                tr(msg),
261                                msg,
262                                DUPLICATE_NODE_BOUNDARY,
263                                mm.get(tagSet)
264                                ));
265                    } else if (typeMap.get("power")) {
266                        String msg = marktr("Power duplicated nodes");
267                        errors.add(new TestError(
268                                parentTest,
269                                Severity.ERROR,
270                                tr("Duplicated nodes"),
271                                tr(msg),
272                                msg,
273                                DUPLICATE_NODE_POWER,
274                                mm.get(tagSet)
275                                ));
276                    } else if (typeMap.get("natural")) {
277                        String msg = marktr("Natural duplicated nodes");
278                        errors.add(new TestError(
279                                parentTest,
280                                Severity.ERROR,
281                                tr("Duplicated nodes"),
282                                tr(msg),
283                                msg,
284                                DUPLICATE_NODE_NATURAL,
285                                mm.get(tagSet)
286                                ));
287                    } else if (typeMap.get("building")) {
288                        String msg = marktr("Building duplicated nodes");
289                        errors.add(new TestError(
290                                parentTest,
291                                Severity.ERROR,
292                                tr("Duplicated nodes"),
293                                tr(msg),
294                                msg,
295                                DUPLICATE_NODE_BUILDING,
296                                mm.get(tagSet)
297                                ));
298                    } else if (typeMap.get("landuse")) {
299                        String msg = marktr("Landuse duplicated nodes");
300                        errors.add(new TestError(
301                                parentTest,
302                                Severity.ERROR,
303                                tr("Duplicated nodes"),
304                                tr(msg),
305                                msg,
306                                DUPLICATE_NODE_LANDUSE,
307                                mm.get(tagSet)
308                                ));
309                    } else {
310                        String msg = marktr("Other duplicated nodes");
311                        errors.add(new TestError(
312                                parentTest,
313                                Severity.WARNING,
314                                tr("Duplicated nodes"),
315                                tr(msg),
316                                msg,
317                                DUPLICATE_NODE_OTHER,
318                                mm.get(tagSet)
319                                ));
320    
321                    }
322                    it.remove();
323                }
324            }
325    
326            // check whether we have multiple nodes at the same position with
327            // differing tag sets
328            //
329            if (!mm.isEmpty()) {
330                List<OsmPrimitive> duplicates = new ArrayList<OsmPrimitive>();
331                for (Set<OsmPrimitive> l: mm.values()) {
332                    duplicates.addAll(l);
333                }
334                if (duplicates.size() > 1) {
335                    errors.add(new TestError(
336                            parentTest,
337                            Severity.WARNING,
338                            tr("Nodes at same position"),
339                            DUPLICATE_NODE,
340                            duplicates
341                            ));
342                }
343            }
344            return errors;
345        }
346    
347        @SuppressWarnings("unchecked")
348        @Override
349        public void visit(Node n) {
350            if (n.isUsable()) {
351                if (potentialDuplicates.get(n) == null) {
352                    // in most cases there is just one node at a given position. We
353                    // avoid to create an extra object and add remember the node
354                    // itself at this position
355                    potentialDuplicates.put(n);
356                } else if (potentialDuplicates.get(n) instanceof Node) {
357                    // we have an additional node at the same position. Create an extra
358                    // object to keep track of the nodes at this position.
359                    //
360                    Node n1 = (Node)potentialDuplicates.get(n);
361                    List<Node> nodes = new ArrayList<Node>(2);
362                    nodes.add(n1);
363                    nodes.add(n);
364                    potentialDuplicates.put(nodes);
365                } else if (potentialDuplicates.get(n) instanceof List<?>) {
366                    // we have multiple nodes at the same position.
367                    //
368                    List<Node> nodes = (List<Node>)potentialDuplicates.get(n);
369                    nodes.add(n);
370                }
371            }
372        }
373    
374        /**
375         * Merge the nodes into one.
376         * Copied from UtilsPlugin.MergePointsAction
377         */
378        @Override
379        public Command fixError(TestError testError) {
380            if (!isFixable(testError)) return null;
381            Collection<OsmPrimitive> sel = new LinkedList<OsmPrimitive>(testError.getPrimitives());
382            LinkedHashSet<Node> nodes = new LinkedHashSet<Node>(OsmPrimitive.getFilteredList(sel, Node.class));
383    
384            // Filter nodes that have already been deleted (see #5764 and #5773)
385            for (Iterator<Node> it = nodes.iterator(); it.hasNext();) {
386                if (it.next().isDeleted()) {
387                    it.remove();
388                }
389            }
390    
391            // Merge only if at least 2 nodes remain
392            if (nodes.size() >= 2) {
393                // Use first existing node or first node if all nodes are new
394                Node target = null;
395                for (Node n: nodes) {
396                    if (!n.isNew()) {
397                        target = n;
398                        break;
399                    }
400                }
401                if (target == null) {
402                    target = nodes.iterator().next();
403                }
404        
405                if (DeleteCommand.checkAndConfirmOutlyingDelete(Main.main.getCurrentDataSet().getDataSourceArea(), nodes, Collections.singleton(target)))
406                    return MergeNodesAction.mergeNodes(Main.main.getEditLayer(), nodes, target);
407            }
408    
409            return null;// undoRedo handling done in mergeNodes
410        }
411    
412        @Override
413        public boolean isFixable(TestError testError) {
414            if (!(testError.getTester() instanceof DuplicateNode)) return false;
415            // never merge nodes with different tags.
416            if (testError.getCode() == DUPLICATE_NODE) return false;
417            // never merge nodes from two different non-closed geometries
418            if (testError.getCode() == DUPLICATE_NODE_UNCLOSED) return false;
419            // everything else is ok to merge
420            return true;
421        }
422    }