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