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