1 | // License: GPL. For details, see LICENSE file.
|
---|
2 | package org.openstreetmap.josm.data.validation.tests;
|
---|
3 |
|
---|
4 | import static org.openstreetmap.josm.tools.I18n.tr;
|
---|
5 |
|
---|
6 | import java.util.ArrayList;
|
---|
7 | import java.util.Collection;
|
---|
8 | import java.util.Collections;
|
---|
9 | import java.util.HashSet;
|
---|
10 | import java.util.LinkedList;
|
---|
11 | import java.util.List;
|
---|
12 | import java.util.Map;
|
---|
13 | import java.util.Objects;
|
---|
14 | import java.util.Set;
|
---|
15 |
|
---|
16 | import org.openstreetmap.josm.command.ChangeCommand;
|
---|
17 | import org.openstreetmap.josm.command.Command;
|
---|
18 | import org.openstreetmap.josm.command.DeleteCommand;
|
---|
19 | import org.openstreetmap.josm.command.SequenceCommand;
|
---|
20 | import org.openstreetmap.josm.data.coor.LatLon;
|
---|
21 | import org.openstreetmap.josm.data.osm.Node;
|
---|
22 | import org.openstreetmap.josm.data.osm.OsmPrimitive;
|
---|
23 | import org.openstreetmap.josm.data.osm.Relation;
|
---|
24 | import org.openstreetmap.josm.data.osm.RelationMember;
|
---|
25 | import org.openstreetmap.josm.data.osm.Way;
|
---|
26 | import org.openstreetmap.josm.data.validation.Severity;
|
---|
27 | import org.openstreetmap.josm.data.validation.Test;
|
---|
28 | import org.openstreetmap.josm.data.validation.TestError;
|
---|
29 | import org.openstreetmap.josm.gui.progress.ProgressMonitor;
|
---|
30 | import org.openstreetmap.josm.tools.MultiMap;
|
---|
31 |
|
---|
32 | /**
|
---|
33 | * Tests if there are duplicate ways
|
---|
34 | */
|
---|
35 | public class DuplicateWay extends Test {
|
---|
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 | private final List<LatLon> coor;
|
---|
43 | private final Map<String, String> keys;
|
---|
44 |
|
---|
45 | WayPair(List<LatLon> coor, Map<String, String> keys) {
|
---|
46 | this.coor = coor;
|
---|
47 | this.keys = keys;
|
---|
48 | }
|
---|
49 |
|
---|
50 | @Override
|
---|
51 | public int hashCode() {
|
---|
52 | return Objects.hash(coor, keys);
|
---|
53 | }
|
---|
54 |
|
---|
55 | @Override
|
---|
56 | public boolean equals(Object obj) {
|
---|
57 | if (this == obj) return true;
|
---|
58 | if (obj == null || getClass() != obj.getClass()) return false;
|
---|
59 | WayPair wayPair = (WayPair) obj;
|
---|
60 | return Objects.equals(coor, wayPair.coor) &&
|
---|
61 | Objects.equals(keys, wayPair.keys);
|
---|
62 | }
|
---|
63 | }
|
---|
64 |
|
---|
65 | /**
|
---|
66 | * Class to store a way reduced to coordinates. Essentially this is used to call the
|
---|
67 | * <code>equals{}</code> function.
|
---|
68 | */
|
---|
69 | private static class WayPairNoTags {
|
---|
70 | private final List<LatLon> coor;
|
---|
71 |
|
---|
72 | WayPairNoTags(List<LatLon> coor) {
|
---|
73 | this.coor = coor;
|
---|
74 | }
|
---|
75 |
|
---|
76 | @Override
|
---|
77 | public int hashCode() {
|
---|
78 | return Objects.hash(coor);
|
---|
79 | }
|
---|
80 |
|
---|
81 | @Override
|
---|
82 | public boolean equals(Object obj) {
|
---|
83 | if (this == obj) return true;
|
---|
84 | if (obj == null || getClass() != obj.getClass()) return false;
|
---|
85 | WayPairNoTags that = (WayPairNoTags) obj;
|
---|
86 | return Objects.equals(coor, that.coor);
|
---|
87 | }
|
---|
88 | }
|
---|
89 |
|
---|
90 | /** Test identification for exactly identical ways (coordinates and tags). */
|
---|
91 | protected static final int DUPLICATE_WAY = 1401;
|
---|
92 | /** Test identification for identical ways (coordinates only). */
|
---|
93 | protected static final int SAME_WAY = 1402;
|
---|
94 |
|
---|
95 | /** Bag of all ways */
|
---|
96 | private MultiMap<WayPair, OsmPrimitive> ways;
|
---|
97 |
|
---|
98 | /** Bag of all ways, regardless of tags */
|
---|
99 | private MultiMap<WayPairNoTags, OsmPrimitive> waysNoTags;
|
---|
100 |
|
---|
101 | /** Set of known hashcodes for list of coordinates **/
|
---|
102 | private Set<Integer> knownHashCodes;
|
---|
103 |
|
---|
104 | /**
|
---|
105 | * Constructor
|
---|
106 | */
|
---|
107 | public DuplicateWay() {
|
---|
108 | super(tr("Duplicated ways"),
|
---|
109 | tr("This test checks that there are no ways with same node coordinates and optionally also same tags."));
|
---|
110 | }
|
---|
111 |
|
---|
112 | @Override
|
---|
113 | public void startTest(ProgressMonitor monitor) {
|
---|
114 | super.startTest(monitor);
|
---|
115 | ways = new MultiMap<>(1000);
|
---|
116 | waysNoTags = new MultiMap<>(1000);
|
---|
117 | knownHashCodes = new HashSet<>(1000);
|
---|
118 | }
|
---|
119 |
|
---|
120 | @Override
|
---|
121 | public void endTest() {
|
---|
122 | super.endTest();
|
---|
123 | for (Set<OsmPrimitive> duplicated : ways.values()) {
|
---|
124 | if (duplicated.size() > 1) {
|
---|
125 | TestError testError = TestError.builder(this, Severity.ERROR, DUPLICATE_WAY)
|
---|
126 | .message(tr("Duplicated ways"))
|
---|
127 | .primitives(duplicated)
|
---|
128 | .build();
|
---|
129 | errors.add(testError);
|
---|
130 | }
|
---|
131 | }
|
---|
132 |
|
---|
133 | for (Set<OsmPrimitive> sameway : waysNoTags.values()) {
|
---|
134 | if (sameway.size() > 1) {
|
---|
135 | //Report error only if at least some tags are different, as otherwise the error was already reported as duplicated ways
|
---|
136 | Map<String, String> tags0 = null;
|
---|
137 | boolean skip = true;
|
---|
138 |
|
---|
139 | for (OsmPrimitive o : sameway) {
|
---|
140 | if (tags0 == null) {
|
---|
141 | tags0 = o.getKeys();
|
---|
142 | removeUninterestingKeys(tags0);
|
---|
143 | } else {
|
---|
144 | Map<String, String> tagsCmp = o.getKeys();
|
---|
145 | removeUninterestingKeys(tagsCmp);
|
---|
146 | if (!tagsCmp.equals(tags0)) {
|
---|
147 | skip = false;
|
---|
148 | break;
|
---|
149 | }
|
---|
150 | }
|
---|
151 | }
|
---|
152 | if (skip) {
|
---|
153 | continue;
|
---|
154 | }
|
---|
155 | TestError testError = TestError.builder(this, Severity.WARNING, SAME_WAY)
|
---|
156 | .message(tr("Ways with same position"))
|
---|
157 | .primitives(sameway)
|
---|
158 | .build();
|
---|
159 | errors.add(testError);
|
---|
160 | }
|
---|
161 | }
|
---|
162 | ways = null;
|
---|
163 | waysNoTags = null;
|
---|
164 | knownHashCodes = null;
|
---|
165 | }
|
---|
166 |
|
---|
167 | /**
|
---|
168 | * Remove uninteresting discardable keys to normalize the tags
|
---|
169 | * @param wkeys The tags of the way, obtained by {@code Way#getKeys}
|
---|
170 | */
|
---|
171 | public void removeUninterestingKeys(Map<String, String> wkeys) {
|
---|
172 | for (String key : OsmPrimitive.getDiscardableKeys()) {
|
---|
173 | wkeys.remove(key);
|
---|
174 | }
|
---|
175 | }
|
---|
176 |
|
---|
177 | @Override
|
---|
178 | public void visit(Way w) {
|
---|
179 | if (!w.isUsable())
|
---|
180 | return;
|
---|
181 | List<LatLon> wLat = getOrderedNodes(w);
|
---|
182 | // If this way has not direction-dependant keys, make sure the list is ordered the same for all ways (fix #8015)
|
---|
183 | if (!w.hasDirectionKeys()) {
|
---|
184 | int hash = wLat.hashCode();
|
---|
185 | if (!knownHashCodes.contains(hash)) {
|
---|
186 | List<LatLon> reversedwLat = new ArrayList<>(wLat);
|
---|
187 | Collections.reverse(reversedwLat);
|
---|
188 | int reverseHash = reversedwLat.hashCode();
|
---|
189 | if (!knownHashCodes.contains(reverseHash)) {
|
---|
190 | // Neither hash or reversed hash is known, remember hash
|
---|
191 | knownHashCodes.add(hash);
|
---|
192 | } else {
|
---|
193 | // Reversed hash is known, use the reverse list then
|
---|
194 | wLat = reversedwLat;
|
---|
195 | }
|
---|
196 | }
|
---|
197 | }
|
---|
198 | Map<String, String> wkeys = w.getKeys();
|
---|
199 | removeUninterestingKeys(wkeys);
|
---|
200 | WayPair wKey = new WayPair(wLat, wkeys);
|
---|
201 | ways.put(wKey, w);
|
---|
202 | WayPairNoTags wKeyN = new WayPairNoTags(wLat);
|
---|
203 | waysNoTags.put(wKeyN, w);
|
---|
204 | }
|
---|
205 |
|
---|
206 | /**
|
---|
207 | * Replies the ordered list of nodes of way w such as it is easier to find duplicated ways.
|
---|
208 | * In case of a closed way, build the list of lat/lon starting from the node with the lowest id
|
---|
209 | * to ensure this list will produce the same hashcode as the list obtained from another closed
|
---|
210 | * way with the same nodes, in the same order, but that does not start from the same node (fix #8008)
|
---|
211 | * @param w way
|
---|
212 | * @return the ordered list of nodes of way w such as it is easier to find duplicated ways
|
---|
213 | * @since 7721
|
---|
214 | */
|
---|
215 | public static List<LatLon> getOrderedNodes(Way w) {
|
---|
216 | List<Node> wNodes = w.getNodes(); // The original list of nodes for this way
|
---|
217 | List<Node> wNodesToUse = new ArrayList<>(wNodes.size()); // The list that will be considered for this test
|
---|
218 | if (w.isClosed()) {
|
---|
219 | int lowestIndex = 0;
|
---|
220 | long lowestNodeId = wNodes.get(0).getUniqueId();
|
---|
221 | for (int i = 1; i < wNodes.size(); i++) {
|
---|
222 | if (wNodes.get(i).getUniqueId() < lowestNodeId) {
|
---|
223 | lowestNodeId = wNodes.get(i).getUniqueId();
|
---|
224 | lowestIndex = i;
|
---|
225 | }
|
---|
226 | }
|
---|
227 | for (int i = lowestIndex; i < wNodes.size()-1; i++) {
|
---|
228 | wNodesToUse.add(wNodes.get(i));
|
---|
229 | }
|
---|
230 | for (int i = 0; i < lowestIndex; i++) {
|
---|
231 | wNodesToUse.add(wNodes.get(i));
|
---|
232 | }
|
---|
233 | wNodesToUse.add(wNodes.get(lowestIndex));
|
---|
234 | } else {
|
---|
235 | wNodesToUse.addAll(wNodes);
|
---|
236 | }
|
---|
237 | // Build the list of lat/lon
|
---|
238 | List<LatLon> wLat = new ArrayList<>(wNodesToUse.size());
|
---|
239 | for (Node node : wNodesToUse) {
|
---|
240 | wLat.add(node.getCoor());
|
---|
241 | }
|
---|
242 | return wLat;
|
---|
243 | }
|
---|
244 |
|
---|
245 | /**
|
---|
246 | * Fix the error by removing all but one instance of duplicate ways
|
---|
247 | */
|
---|
248 | @Override
|
---|
249 | public Command fixError(TestError testError) {
|
---|
250 | Collection<? extends OsmPrimitive> sel = testError.getPrimitives();
|
---|
251 | Set<Way> wayz = new HashSet<>();
|
---|
252 |
|
---|
253 | for (OsmPrimitive osm : sel) {
|
---|
254 | if (osm instanceof Way && !osm.isDeleted()) {
|
---|
255 | wayz.add((Way) osm);
|
---|
256 | }
|
---|
257 | }
|
---|
258 |
|
---|
259 | if (wayz.size() < 2)
|
---|
260 | return null;
|
---|
261 |
|
---|
262 | long idToKeep = 0;
|
---|
263 | Way wayToKeep = wayz.iterator().next();
|
---|
264 | // Find the way that is member of one or more relations. (If any)
|
---|
265 | Way wayWithRelations = null;
|
---|
266 | List<Relation> relations = null;
|
---|
267 | for (Way w : wayz) {
|
---|
268 | List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class);
|
---|
269 | if (!rel.isEmpty()) {
|
---|
270 | if (wayWithRelations != null)
|
---|
271 | throw new AssertionError("Cannot fix duplicate Ways: More than one way is relation member.");
|
---|
272 | wayWithRelations = w;
|
---|
273 | relations = rel;
|
---|
274 | }
|
---|
275 | // Only one way will be kept - the one with lowest positive ID, if such exist
|
---|
276 | // or one "at random" if no such exists. Rest of the ways will be deleted
|
---|
277 | if (!w.isNew() && (idToKeep == 0 || w.getId() < idToKeep)) {
|
---|
278 | idToKeep = w.getId();
|
---|
279 | wayToKeep = w;
|
---|
280 | }
|
---|
281 | }
|
---|
282 |
|
---|
283 | Collection<Command> commands = new LinkedList<>();
|
---|
284 |
|
---|
285 | // Fix relations.
|
---|
286 | if (wayWithRelations != null && relations != null && wayToKeep != wayWithRelations) {
|
---|
287 | for (Relation rel : relations) {
|
---|
288 | Relation newRel = new Relation(rel);
|
---|
289 | for (int i = 0; i < newRel.getMembers().size(); ++i) {
|
---|
290 | RelationMember m = newRel.getMember(i);
|
---|
291 | if (wayWithRelations.equals(m.getMember())) {
|
---|
292 | newRel.setMember(i, new RelationMember(m.getRole(), wayToKeep));
|
---|
293 | }
|
---|
294 | }
|
---|
295 | commands.add(new ChangeCommand(rel, newRel));
|
---|
296 | }
|
---|
297 | }
|
---|
298 |
|
---|
299 | // Delete all ways in the list
|
---|
300 | // Note: nodes are not deleted, these can be detected and deleted at next pass
|
---|
301 | wayz.remove(wayToKeep);
|
---|
302 | commands.add(new DeleteCommand(wayz));
|
---|
303 | return new SequenceCommand(tr("Delete duplicate ways"), commands);
|
---|
304 | }
|
---|
305 |
|
---|
306 | @Override
|
---|
307 | public boolean isFixable(TestError testError) {
|
---|
308 | if (!(testError.getTester() instanceof DuplicateWay))
|
---|
309 | return false;
|
---|
310 |
|
---|
311 | // Do not automatically fix same ways with different tags
|
---|
312 | if (testError.getCode() != DUPLICATE_WAY) return false;
|
---|
313 |
|
---|
314 | // We fix it only if there is no more than one way that is relation member.
|
---|
315 | Collection<? extends OsmPrimitive> sel = testError.getPrimitives();
|
---|
316 | Set<Way> wayz = new HashSet<>();
|
---|
317 |
|
---|
318 | for (OsmPrimitive osm : sel) {
|
---|
319 | if (osm instanceof Way) {
|
---|
320 | wayz.add((Way) osm);
|
---|
321 | }
|
---|
322 | }
|
---|
323 |
|
---|
324 | if (wayz.size() < 2)
|
---|
325 | return false;
|
---|
326 |
|
---|
327 | int waysWithRelations = 0;
|
---|
328 | for (Way w : wayz) {
|
---|
329 | List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class);
|
---|
330 | if (!rel.isEmpty()) {
|
---|
331 | ++waysWithRelations;
|
---|
332 | }
|
---|
333 | }
|
---|
334 | return waysWithRelations <= 1;
|
---|
335 | }
|
---|
336 | }
|
---|