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