source: josm/trunk/src/org/openstreetmap/josm/data/validation/tests/DuplicateWay.java@ 6104

Last change on this file since 6104 was 6104, checked in by Don-vip, 11 years ago

see #8902 - Small performance enhancements / coding style (patch by shinigami):

  • while -> foreach
  • for -> for each

plus:

  • cleanup of FileDrop class to make it more integrated into JOSM core + remove warnings
  • Property svn:eol-style set to native
File size: 11.4 KB
Line 
1// License: GPL. See LICENSE file for details.
2package org.openstreetmap.josm.data.validation.tests;
3
4import static org.openstreetmap.josm.tools.I18n.tr;
5
6import java.util.ArrayList;
7import java.util.Collection;
8import java.util.Collections;
9import java.util.HashSet;
10import java.util.LinkedList;
11import java.util.List;
12import java.util.Map;
13import java.util.Set;
14
15import org.openstreetmap.josm.command.ChangeCommand;
16import org.openstreetmap.josm.command.Command;
17import org.openstreetmap.josm.command.DeleteCommand;
18import org.openstreetmap.josm.command.SequenceCommand;
19import org.openstreetmap.josm.data.coor.LatLon;
20import org.openstreetmap.josm.data.osm.Node;
21import org.openstreetmap.josm.data.osm.OsmPrimitive;
22import org.openstreetmap.josm.data.osm.Relation;
23import org.openstreetmap.josm.data.osm.RelationMember;
24import org.openstreetmap.josm.data.osm.Way;
25import org.openstreetmap.josm.data.validation.Severity;
26import org.openstreetmap.josm.data.validation.Test;
27import org.openstreetmap.josm.data.validation.TestError;
28import org.openstreetmap.josm.gui.progress.ProgressMonitor;
29import org.openstreetmap.josm.tools.MultiMap;
30
31/**
32 * Tests if there are duplicate ways
33 */
34public class DuplicateWay extends Test
35{
36
37 /**
38 * Class to store a way reduced to coordinates and keys. Essentially this is used to call the
39 * <code>equals{}</code> function.
40 */
41 private static class WayPair {
42 public List<LatLon> coor;
43 public Map<String, String> keys;
44 public WayPair(List<LatLon> _coor, Map<String, String> _keys) {
45 coor=_coor;
46 keys=_keys;
47 }
48
49 @Override
50 public int hashCode() {
51 return coor.hashCode() + keys.hashCode();
52 }
53
54 @Override
55 public boolean equals(Object obj) {
56 if (!(obj instanceof WayPair))
57 return false;
58 WayPair wp = (WayPair) obj;
59 return wp.coor.equals(coor) && wp.keys.equals(keys);
60 }
61 }
62
63 /**
64 * Class to store a way reduced to coordinates. Essentially this is used to call the
65 * <code>equals{}</code> function.
66 */
67 private static class WayPairNoTags {
68 public List<LatLon> coor;
69 public WayPairNoTags(List<LatLon> _coor) {
70 coor=_coor;
71 }
72 @Override
73 public int hashCode() {
74 return coor.hashCode();
75 }
76 @Override
77 public boolean equals(Object obj) {
78 if (!(obj instanceof WayPairNoTags)) return false;
79 WayPairNoTags wp = (WayPairNoTags) obj;
80 return wp.coor.equals(coor);
81 }
82 }
83
84 /** Test identification for exactly identical ways (coordinates and tags). */
85 protected static final int DUPLICATE_WAY = 1401;
86 /** Test identification for identical ways (coordinates only). */
87 protected static final int SAME_WAY = 1402;
88
89 /** Bag of all ways */
90 private MultiMap<WayPair, OsmPrimitive> ways;
91
92 /** Bag of all ways, regardless of tags */
93 private MultiMap<WayPairNoTags, OsmPrimitive> waysNoTags;
94
95 /** Set of known hashcodes for list of coordinates **/
96 private Set<Integer> knownHashCodes;
97
98 /**
99 * 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<WayPair, OsmPrimitive>(1000);
110 waysNoTags = new MultiMap<WayPairNoTags, OsmPrimitive>(1000);
111 knownHashCodes = new HashSet<Integer>(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<Node>(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<LatLon>(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<LatLon>(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<Way>();
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()) {
245 if (idToKeep == 0 || w.getId() < idToKeep) {
246 idToKeep = w.getId();
247 wayToKeep = w;
248 }
249 }
250 }
251
252 // Find the way that is member of one or more relations. (If any)
253 Way wayWithRelations = null;
254 List<Relation> relations = null;
255 for (Way w : ways) {
256 List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class);
257 if (!rel.isEmpty()) {
258 if (wayWithRelations != null)
259 throw new AssertionError("Cannot fix duplicate Ways: More than one way is relation member.");
260 wayWithRelations = w;
261 relations = rel;
262 }
263 }
264
265 Collection<Command> commands = new LinkedList<Command>();
266
267 // Fix relations.
268 if (wayWithRelations != null && wayToKeep != wayWithRelations) {
269 for (Relation rel : relations) {
270 Relation newRel = new Relation(rel);
271 for (int i = 0; i < newRel.getMembers().size(); ++i) {
272 RelationMember m = newRel.getMember(i);
273 if (wayWithRelations.equals(m.getMember())) {
274 newRel.setMember(i, new RelationMember(m.getRole(), wayToKeep));
275 }
276 }
277 commands.add(new ChangeCommand(rel, newRel));
278 }
279 }
280
281 //Delete all ways in the list
282 //Note: nodes are not deleted, these can be detected and deleted at next pass
283 ways.remove(wayToKeep);
284 commands.add(new DeleteCommand(ways));
285 return new SequenceCommand(tr("Delete duplicate ways"), commands);
286 }
287
288 @Override
289 public boolean isFixable(TestError testError) {
290 if (!(testError.getTester() instanceof DuplicateWay))
291 return false;
292
293 //Do not automatically fix same ways with different tags
294 if (testError.getCode()!=DUPLICATE_WAY) return false;
295
296 // We fix it only if there is no more than one way that is relation member.
297 Collection<? extends OsmPrimitive> sel = testError.getPrimitives();
298 HashSet<Way> ways = new HashSet<Way>();
299
300 for (OsmPrimitive osm : sel) {
301 if (osm instanceof Way) {
302 ways.add((Way)osm);
303 }
304 }
305
306 if (ways.size() < 2)
307 return false;
308
309 int waysWithRelations = 0;
310 for (Way w : ways) {
311 List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class);
312 if (!rel.isEmpty()) {
313 ++waysWithRelations;
314 }
315 }
316 return (waysWithRelations <= 1);
317 }
318}
Note: See TracBrowser for help on using the repository browser.