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