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