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