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