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