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