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