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