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.HashSet; 009import java.util.LinkedList; 010import java.util.List; 011import java.util.Map; 012import java.util.Objects; 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.AbstractPrimitive; 021import org.openstreetmap.josm.data.osm.Node; 022import org.openstreetmap.josm.data.osm.OsmPrimitive; 023import org.openstreetmap.josm.data.osm.OsmPrimitiveType; 024import org.openstreetmap.josm.data.osm.Relation; 025import org.openstreetmap.josm.data.osm.RelationMember; 026import org.openstreetmap.josm.data.osm.Way; 027import org.openstreetmap.josm.data.validation.Severity; 028import org.openstreetmap.josm.data.validation.Test; 029import org.openstreetmap.josm.data.validation.TestError; 030import org.openstreetmap.josm.gui.progress.ProgressMonitor; 031import org.openstreetmap.josm.tools.MultiMap; 032 033/** 034 * Tests if there are duplicate relations 035 */ 036public class DuplicateRelation extends Test { 037 038 /** 039 * Class to store one relation members and information about it 040 */ 041 public static class RelMember { 042 /** Role of the relation member */ 043 private final String role; 044 045 /** Type of the relation member */ 046 private final OsmPrimitiveType type; 047 048 /** Tags of the relation member */ 049 private Map<String, String> tags; 050 051 /** Coordinates of the relation member */ 052 private List<LatLon> coor; 053 054 /** ID of the relation member in case it is a {@link Relation} */ 055 private long relId; 056 057 @Override 058 public int hashCode() { 059 return Objects.hash(role, type, tags, coor, relId); 060 } 061 062 @Override 063 public boolean equals(Object obj) { 064 if (this == obj) return true; 065 if (obj == null || getClass() != obj.getClass()) return false; 066 RelMember relMember = (RelMember) obj; 067 return relId == relMember.relId && 068 type == relMember.type && 069 Objects.equals(role, relMember.role) && 070 Objects.equals(tags, relMember.tags) && 071 Objects.equals(coor, relMember.coor); 072 } 073 074 /** Extract and store relation information based on the relation member 075 * @param src The relation member to store information about 076 */ 077 public RelMember(RelationMember src) { 078 role = src.getRole(); 079 type = src.getType(); 080 relId = 0; 081 coor = new ArrayList<>(); 082 083 if (src.isNode()) { 084 Node r = src.getNode(); 085 tags = r.getKeys(); 086 coor = new ArrayList<>(1); 087 coor.add(r.getCoor()); 088 } 089 if (src.isWay()) { 090 Way r = src.getWay(); 091 tags = r.getKeys(); 092 List<Node> wNodes = r.getNodes(); 093 coor = new ArrayList<>(wNodes.size()); 094 for (Node wNode : wNodes) { 095 coor.add(wNode.getCoor()); 096 } 097 } 098 if (src.isRelation()) { 099 Relation r = src.getRelation(); 100 tags = r.getKeys(); 101 relId = r.getId(); 102 coor = new ArrayList<>(); 103 } 104 } 105 } 106 107 /** 108 * Class to store relation members 109 */ 110 private static class RelationMembers { 111 /** List of member objects of the relation */ 112 private final List<RelMember> members; 113 114 /** Store relation information 115 * @param members The list of relation members 116 */ 117 RelationMembers(List<RelationMember> members) { 118 this.members = new ArrayList<>(members.size()); 119 for (RelationMember member : members) { 120 this.members.add(new RelMember(member)); 121 } 122 } 123 124 @Override 125 public int hashCode() { 126 return Objects.hash(members); 127 } 128 129 @Override 130 public boolean equals(Object obj) { 131 if (this == obj) return true; 132 if (obj == null || getClass() != obj.getClass()) return false; 133 RelationMembers that = (RelationMembers) obj; 134 return Objects.equals(members, that.members); 135 } 136 } 137 138 /** 139 * Class to store relation data (keys are usually cleanup and may not be equal to original relation) 140 */ 141 private static class RelationPair { 142 /** Member objects of the relation */ 143 private final RelationMembers members; 144 /** Tags of the relation */ 145 private final Map<String, String> keys; 146 147 /** Store relation information 148 * @param members The list of relation members 149 * @param keys The set of tags of the relation 150 */ 151 RelationPair(List<RelationMember> members, Map<String, String> keys) { 152 this.members = new RelationMembers(members); 153 this.keys = keys; 154 } 155 156 @Override 157 public int hashCode() { 158 return Objects.hash(members, keys); 159 } 160 161 @Override 162 public boolean equals(Object obj) { 163 if (this == obj) return true; 164 if (obj == null || getClass() != obj.getClass()) return false; 165 RelationPair that = (RelationPair) obj; 166 return Objects.equals(members, that.members) && 167 Objects.equals(keys, that.keys); 168 } 169 } 170 171 /** Code number of completely duplicated relation error */ 172 protected static final int DUPLICATE_RELATION = 1901; 173 174 /** Code number of relation with same members error */ 175 protected static final int SAME_RELATION = 1902; 176 177 /** MultiMap of all relations */ 178 private MultiMap<RelationPair, OsmPrimitive> relations; 179 180 /** MultiMap of all relations, regardless of keys */ 181 private MultiMap<List<RelationMember>, OsmPrimitive> relationsNoKeys; 182 183 /** List of keys without useful information */ 184 private final Set<String> ignoreKeys = new HashSet<>(AbstractPrimitive.getUninterestingKeys()); 185 186 /** 187 * Default constructor 188 */ 189 public DuplicateRelation() { 190 super(tr("Duplicated relations"), 191 tr("This test checks that there are no relations with same tags and same members with same roles.")); 192 } 193 194 @Override 195 public void startTest(ProgressMonitor monitor) { 196 super.startTest(monitor); 197 relations = new MultiMap<>(1000); 198 relationsNoKeys = new MultiMap<>(1000); 199 } 200 201 @Override 202 public void endTest() { 203 super.endTest(); 204 for (Set<OsmPrimitive> duplicated : relations.values()) { 205 if (duplicated.size() > 1) { 206 TestError testError = TestError.builder(this, Severity.ERROR, DUPLICATE_RELATION) 207 .message(tr("Duplicated relations")) 208 .primitives(duplicated) 209 .build(); 210 errors.add(testError); 211 } 212 } 213 relations = null; 214 for (Set<OsmPrimitive> duplicated : relationsNoKeys.values()) { 215 if (duplicated.size() > 1) { 216 TestError testError = TestError.builder(this, Severity.WARNING, SAME_RELATION) 217 .message(tr("Relations with same members")) 218 .primitives(duplicated) 219 .build(); 220 errors.add(testError); 221 } 222 } 223 relationsNoKeys = null; 224 } 225 226 @Override 227 public void visit(Relation r) { 228 if (!r.isUsable() || r.hasIncompleteMembers() || "tmc".equals(r.get("type")) || "TMC".equals(r.get("type"))) 229 return; 230 List<RelationMember> rMembers = r.getMembers(); 231 Map<String, String> rkeys = r.getKeys(); 232 for (String key : ignoreKeys) { 233 rkeys.remove(key); 234 } 235 RelationPair rKey = new RelationPair(rMembers, rkeys); 236 relations.put(rKey, r); 237 relationsNoKeys.put(rMembers, r); 238 } 239 240 /** 241 * Fix the error by removing all but one instance of duplicate relations 242 * @param testError The error to fix, must be of type {@link #DUPLICATE_RELATION} 243 */ 244 @Override 245 public Command fixError(TestError testError) { 246 if (testError.getCode() == SAME_RELATION) return null; 247 Collection<? extends OsmPrimitive> sel = testError.getPrimitives(); 248 Set<Relation> relFix = new HashSet<>(); 249 250 for (OsmPrimitive osm : sel) { 251 if (osm instanceof Relation && !osm.isDeleted()) { 252 relFix.add((Relation) osm); 253 } 254 } 255 256 if (relFix.size() < 2) 257 return null; 258 259 long idToKeep = 0; 260 Relation relationToKeep = relFix.iterator().next(); 261 // Find the relation that is member of one or more relations. (If any) 262 Relation relationWithRelations = null; 263 List<Relation> relRef = null; 264 for (Relation w : relFix) { 265 List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class); 266 if (!rel.isEmpty()) { 267 if (relationWithRelations != null) 268 throw new AssertionError("Cannot fix duplicate relations: More than one relation is member of another relation."); 269 relationWithRelations = w; 270 relRef = rel; 271 } 272 // Only one relation will be kept - the one with lowest positive ID, if such exist 273 // or one "at random" if no such exists. Rest of the relations will be deleted 274 if (!w.isNew() && (idToKeep == 0 || w.getId() < idToKeep)) { 275 idToKeep = w.getId(); 276 relationToKeep = w; 277 } 278 } 279 280 Collection<Command> commands = new LinkedList<>(); 281 282 // Fix relations. 283 if (relationWithRelations != null && relRef != null && relationToKeep != relationWithRelations) { 284 for (Relation rel : relRef) { 285 Relation newRel = new Relation(rel); 286 for (int i = 0; i < newRel.getMembers().size(); ++i) { 287 RelationMember m = newRel.getMember(i); 288 if (relationWithRelations.equals(m.getMember())) { 289 newRel.setMember(i, new RelationMember(m.getRole(), relationToKeep)); 290 } 291 } 292 commands.add(new ChangeCommand(rel, newRel)); 293 } 294 } 295 296 // Delete all relations in the list 297 relFix.remove(relationToKeep); 298 commands.add(new DeleteCommand(relFix)); 299 return new SequenceCommand(tr("Delete duplicate relations"), commands); 300 } 301 302 @Override 303 public boolean isFixable(TestError testError) { 304 if (!(testError.getTester() instanceof DuplicateRelation) 305 || testError.getCode() == SAME_RELATION) return false; 306 307 // We fix it only if there is no more than one relation that is relation member. 308 Collection<? extends OsmPrimitive> sel = testError.getPrimitives(); 309 Set<Relation> rels = new HashSet<>(); 310 311 for (OsmPrimitive osm : sel) { 312 if (osm instanceof Relation) { 313 rels.add((Relation) osm); 314 } 315 } 316 317 if (rels.size() < 2) 318 return false; 319 320 int relationsWithRelations = 0; 321 for (Relation w : rels) { 322 List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class); 323 if (!rel.isEmpty()) { 324 ++relationsWithRelations; 325 } 326 } 327 return relationsWithRelations <= 1; 328 } 329}