001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data.validation.tests;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005
006import java.util.ArrayList;
007import java.util.Collection;
008import java.util.Collections;
009import java.util.HashSet;
010import java.util.LinkedList;
011import java.util.List;
012import java.util.Map;
013import java.util.Objects;
014import java.util.Set;
015
016import org.openstreetmap.josm.command.ChangeCommand;
017import org.openstreetmap.josm.command.Command;
018import org.openstreetmap.josm.command.DeleteCommand;
019import org.openstreetmap.josm.command.SequenceCommand;
020import org.openstreetmap.josm.data.coor.LatLon;
021import org.openstreetmap.josm.data.osm.AbstractPrimitive;
022import org.openstreetmap.josm.data.osm.Node;
023import org.openstreetmap.josm.data.osm.OsmPrimitive;
024import org.openstreetmap.josm.data.osm.Relation;
025import org.openstreetmap.josm.data.osm.RelationMember;
026import org.openstreetmap.josm.data.osm.Way;
027import org.openstreetmap.josm.data.validation.Severity;
028import org.openstreetmap.josm.data.validation.Test;
029import org.openstreetmap.josm.data.validation.TestError;
030import org.openstreetmap.josm.gui.progress.ProgressMonitor;
031import org.openstreetmap.josm.tools.MultiMap;
032
033/**
034 * Tests if there are duplicate ways
035 */
036public class DuplicateWay extends Test {
037
038    /**
039      * Class to store a way reduced to coordinates and keys. Essentially this is used to call the
040      * <code>equals{}</code> function.
041      */
042    private static class WayPair {
043        private final List<LatLon> coor;
044        private final Map<String, String> keys;
045
046        WayPair(List<LatLon> coor, Map<String, String> keys) {
047            this.coor = coor;
048            this.keys = keys;
049        }
050
051        @Override
052        public int hashCode() {
053            return Objects.hash(coor, keys);
054        }
055
056        @Override
057        public boolean equals(Object obj) {
058            if (this == obj) return true;
059            if (obj == null || getClass() != obj.getClass()) return false;
060            WayPair wayPair = (WayPair) obj;
061            return Objects.equals(coor, wayPair.coor) &&
062                    Objects.equals(keys, wayPair.keys);
063        }
064    }
065
066    /**
067      * Class to store a way reduced to coordinates. Essentially this is used to call the
068      * <code>equals{}</code> function.
069      */
070    private static class WayPairNoTags {
071        private final List<LatLon> coor;
072
073        WayPairNoTags(List<LatLon> coor) {
074            this.coor = coor;
075        }
076
077        @Override
078        public int hashCode() {
079            return Objects.hash(coor);
080        }
081
082        @Override
083        public boolean equals(Object obj) {
084            if (this == obj) return true;
085            if (obj == null || getClass() != obj.getClass()) return false;
086            WayPairNoTags that = (WayPairNoTags) obj;
087            return Objects.equals(coor, that.coor);
088        }
089    }
090
091    /** Test identification for exactly identical ways (coordinates and tags). */
092    protected static final int DUPLICATE_WAY = 1401;
093    /** Test identification for identical ways (coordinates only). */
094    protected static final int SAME_WAY = 1402;
095
096    /** Bag of all ways */
097    private MultiMap<WayPair, OsmPrimitive> ways;
098
099    /** Bag of all ways, regardless of tags */
100    private MultiMap<WayPairNoTags, OsmPrimitive> waysNoTags;
101
102    /** Set of known hashcodes for list of coordinates **/
103    private Set<Integer> knownHashCodes;
104
105    /**
106     * Constructor
107     */
108    public DuplicateWay() {
109        super(tr("Duplicated ways"),
110                tr("This test checks that there are no ways with same node coordinates and optionally also same tags."));
111    }
112
113    @Override
114    public void startTest(ProgressMonitor monitor) {
115        super.startTest(monitor);
116        ways = new MultiMap<>(1000);
117        waysNoTags = new MultiMap<>(1000);
118        knownHashCodes = new HashSet<>(1000);
119    }
120
121    @Override
122    public void endTest() {
123        super.endTest();
124        for (Set<OsmPrimitive> duplicated : ways.values()) {
125            if (duplicated.size() > 1) {
126                TestError testError = TestError.builder(this, Severity.ERROR, DUPLICATE_WAY)
127                        .message(tr("Duplicated ways"))
128                        .primitives(duplicated)
129                        .build();
130                errors.add(testError);
131            }
132        }
133
134        for (Set<OsmPrimitive> sameway : waysNoTags.values()) {
135            if (sameway.size() > 1) {
136                //Report error only if at least some tags are different, as otherwise the error was already reported as duplicated ways
137                Map<String, String> tags0 = null;
138                boolean skip = true;
139
140                for (OsmPrimitive o : sameway) {
141                    if (tags0 == null) {
142                        tags0 = o.getKeys();
143                        removeUninterestingKeys(tags0);
144                    } else {
145                        Map<String, String> tagsCmp = o.getKeys();
146                        removeUninterestingKeys(tagsCmp);
147                        if (!tagsCmp.equals(tags0)) {
148                            skip = false;
149                            break;
150                        }
151                    }
152                }
153                if (skip) {
154                    continue;
155                }
156                TestError testError = TestError.builder(this, Severity.WARNING, SAME_WAY)
157                        .message(tr("Ways with same position"))
158                        .primitives(sameway)
159                        .build();
160                errors.add(testError);
161            }
162        }
163        ways = null;
164        waysNoTags = null;
165        knownHashCodes = null;
166    }
167
168    /**
169     * Remove uninteresting discardable keys to normalize the tags
170     * @param wkeys The tags of the way, obtained by {@code Way#getKeys}
171     */
172    public void removeUninterestingKeys(Map<String, String> wkeys) {
173        for (String key : AbstractPrimitive.getDiscardableKeys()) {
174            wkeys.remove(key);
175        }
176    }
177
178    @Override
179    public void visit(Way w) {
180        if (!w.isUsable())
181            return;
182        List<LatLon> wLat = getOrderedNodes(w);
183        // If this way has not direction-dependant keys, make sure the list is ordered the same for all ways (fix #8015)
184        if (!w.hasDirectionKeys()) {
185            int hash = wLat.hashCode();
186            if (!knownHashCodes.contains(hash)) {
187                List<LatLon> reversedwLat = new ArrayList<>(wLat);
188                Collections.reverse(reversedwLat);
189                int reverseHash = reversedwLat.hashCode();
190                if (!knownHashCodes.contains(reverseHash)) {
191                    // Neither hash or reversed hash is known, remember hash
192                    knownHashCodes.add(hash);
193                } else {
194                    // Reversed hash is known, use the reverse list then
195                    wLat = reversedwLat;
196                }
197            }
198        }
199        Map<String, String> wkeys = w.getKeys();
200        removeUninterestingKeys(wkeys);
201        WayPair wKey = new WayPair(wLat, wkeys);
202        ways.put(wKey, w);
203        WayPairNoTags wKeyN = new WayPairNoTags(wLat);
204        waysNoTags.put(wKeyN, w);
205    }
206
207    /**
208     * Replies the ordered list of nodes of way w such as it is easier to find duplicated ways.
209     * In case of a closed way, build the list of lat/lon starting from the node with the lowest id
210     * to ensure this list will produce the same hashcode as the list obtained from another closed
211     * way with the same nodes, in the same order, but that does not start from the same node (fix #8008)
212     * @param w way
213     * @return the ordered list of nodes of way w such as it is easier to find duplicated ways
214     * @since 7721
215     */
216    public static List<LatLon> getOrderedNodes(Way w) {
217        List<Node> wNodes = w.getNodes();                        // The original list of nodes for this way
218        List<Node> wNodesToUse = new ArrayList<>(wNodes.size()); // The list that will be considered for this test
219        if (w.isClosed()) {
220            int lowestIndex = 0;
221            long lowestNodeId = wNodes.get(0).getUniqueId();
222            for (int i = 1; i < wNodes.size(); i++) {
223                if (wNodes.get(i).getUniqueId() < lowestNodeId) {
224                    lowestNodeId = wNodes.get(i).getUniqueId();
225                    lowestIndex = i;
226                }
227            }
228            for (int i = lowestIndex; i < wNodes.size()-1; i++) {
229                wNodesToUse.add(wNodes.get(i));
230            }
231            for (int i = 0; i < lowestIndex; i++) {
232                wNodesToUse.add(wNodes.get(i));
233            }
234            wNodesToUse.add(wNodes.get(lowestIndex));
235        } else {
236            wNodesToUse.addAll(wNodes);
237        }
238        // Build the list of lat/lon
239        List<LatLon> wLat = new ArrayList<>(wNodesToUse.size());
240        for (Node node : wNodesToUse) {
241            wLat.add(node.getCoor());
242        }
243        return wLat;
244    }
245
246    /**
247     * Fix the error by removing all but one instance of duplicate ways
248     */
249    @Override
250    public Command fixError(TestError testError) {
251        Collection<? extends OsmPrimitive> sel = testError.getPrimitives();
252        Set<Way> wayz = new HashSet<>();
253
254        for (OsmPrimitive osm : sel) {
255            if (osm instanceof Way && !osm.isDeleted()) {
256                wayz.add((Way) osm);
257            }
258        }
259
260        if (wayz.size() < 2)
261            return null;
262
263        long idToKeep = 0;
264        Way wayToKeep = wayz.iterator().next();
265        // Find the way that is member of one or more relations. (If any)
266        Way wayWithRelations = null;
267        List<Relation> relations = null;
268        for (Way w : wayz) {
269            List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class);
270            if (!rel.isEmpty()) {
271                if (wayWithRelations != null)
272                    throw new AssertionError("Cannot fix duplicate Ways: More than one way is relation member.");
273                wayWithRelations = w;
274                relations = rel;
275            }
276            // Only one way will be kept - the one with lowest positive ID, if such exist
277            // or one "at random" if no such exists. Rest of the ways will be deleted
278            if (!w.isNew() && (idToKeep == 0 || w.getId() < idToKeep)) {
279                idToKeep = w.getId();
280                wayToKeep = w;
281            }
282        }
283
284        Collection<Command> commands = new LinkedList<>();
285
286        // Fix relations.
287        if (wayWithRelations != null && relations != null && wayToKeep != wayWithRelations) {
288            for (Relation rel : relations) {
289                Relation newRel = new Relation(rel);
290                for (int i = 0; i < newRel.getMembers().size(); ++i) {
291                    RelationMember m = newRel.getMember(i);
292                    if (wayWithRelations.equals(m.getMember())) {
293                        newRel.setMember(i, new RelationMember(m.getRole(), wayToKeep));
294                    }
295                }
296                commands.add(new ChangeCommand(rel, newRel));
297            }
298        }
299
300        // Delete all ways in the list
301        // Note: nodes are not deleted, these can be detected and deleted at next pass
302        wayz.remove(wayToKeep);
303        commands.add(new DeleteCommand(wayz));
304        return new SequenceCommand(tr("Delete duplicate ways"), commands);
305    }
306
307    @Override
308    public boolean isFixable(TestError testError) {
309        if (!(testError.getTester() instanceof DuplicateWay))
310            return false;
311
312        // Do not automatically fix same ways with different tags
313        if (testError.getCode() != DUPLICATE_WAY) return false;
314
315        // We fix it only if there is no more than one way that is relation member.
316        Collection<? extends OsmPrimitive> sel = testError.getPrimitives();
317        Set<Way> wayz = new HashSet<>();
318
319        for (OsmPrimitive osm : sel) {
320            if (osm instanceof Way) {
321                wayz.add((Way) osm);
322            }
323        }
324
325        if (wayz.size() < 2)
326            return false;
327
328        int waysWithRelations = 0;
329        for (Way w : wayz) {
330            List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class);
331            if (!rel.isEmpty()) {
332                ++waysWithRelations;
333            }
334        }
335        return waysWithRelations <= 1;
336    }
337}