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