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