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