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