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