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.Node; 022import org.openstreetmap.josm.data.osm.OsmPrimitive; 023import org.openstreetmap.josm.data.osm.Relation; 024import org.openstreetmap.josm.data.osm.RelationMember; 025import org.openstreetmap.josm.data.osm.Way; 026import org.openstreetmap.josm.data.validation.Severity; 027import org.openstreetmap.josm.data.validation.Test; 028import org.openstreetmap.josm.data.validation.TestError; 029import org.openstreetmap.josm.gui.progress.ProgressMonitor; 030import org.openstreetmap.josm.tools.MultiMap; 031 032/** 033 * Tests if there are duplicate ways 034 */ 035public class DuplicateWay extends Test { 036 037 /** 038 * Class to store a way reduced to coordinates and keys. Essentially this is used to call the 039 * <code>equals{}</code> function. 040 */ 041 private static class WayPair { 042 private final List<LatLon> coor; 043 private final Map<String, String> keys; 044 045 WayPair(List<LatLon> coor, Map<String, String> keys) { 046 this.coor = coor; 047 this.keys = keys; 048 } 049 050 @Override 051 public int hashCode() { 052 return Objects.hash(coor, keys); 053 } 054 055 @Override 056 public boolean equals(Object obj) { 057 if (this == obj) return true; 058 if (obj == null || getClass() != obj.getClass()) return false; 059 WayPair wayPair = (WayPair) obj; 060 return Objects.equals(coor, wayPair.coor) && 061 Objects.equals(keys, wayPair.keys); 062 } 063 } 064 065 /** 066 * Class to store a way reduced to coordinates. Essentially this is used to call the 067 * <code>equals{}</code> function. 068 */ 069 private static class WayPairNoTags { 070 private final List<LatLon> coor; 071 072 WayPairNoTags(List<LatLon> coor) { 073 this.coor = coor; 074 } 075 076 @Override 077 public int hashCode() { 078 return Objects.hash(coor); 079 } 080 081 @Override 082 public boolean equals(Object obj) { 083 if (this == obj) return true; 084 if (obj == null || getClass() != obj.getClass()) return false; 085 WayPairNoTags that = (WayPairNoTags) obj; 086 return Objects.equals(coor, that.coor); 087 } 088 } 089 090 /** Test identification for exactly identical ways (coordinates and tags). */ 091 protected static final int DUPLICATE_WAY = 1401; 092 /** Test identification for identical ways (coordinates only). */ 093 protected static final int SAME_WAY = 1402; 094 095 /** Bag of all ways */ 096 private MultiMap<WayPair, OsmPrimitive> ways; 097 098 /** Bag of all ways, regardless of tags */ 099 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}