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.ChangeMembersCommand; 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 /** Set of member objects of the relation */ 113 private final Set<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 HashSet<>(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 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.OTHER, SAME_RELATION) 217 .message(tr("Relations with same members")) 218 .primitives(duplicated) 219 .build(); 220 errors.add(testError); 221 } 222 } 223 relationsNoKeys = null; 224 super.endTest(); 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 || "destination_sign".equals(r.get("type")) || 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 (!isFixable(testError)) return null; 249 250 Set<Relation> relFix = testError.primitives(Relation.class) 251 .filter(r -> !r.isDeleted() || r.getDataSet() == null || r.getDataSet().getPrimitiveById(r) == null) 252 .collect(Collectors.toSet()); 253 254 if (relFix.size() < 2) 255 return null; 256 257 long idToKeep = 0; 258 Relation relationToKeep = relFix.iterator().next(); 259 // Find the relation that is member of one or more relations. (If any) 260 Relation relationWithRelations = null; 261 Collection<Relation> relRef = null; 262 for (Relation r : relFix) { 263 Collection<Relation> rel = r.referrers(Relation.class).collect(Collectors.toList()); 264 if (!rel.isEmpty()) { 265 if (relationWithRelations != null) 266 throw new AssertionError("Cannot fix duplicate relations: More than one relation is member of another relation."); 267 relationWithRelations = r; 268 relRef = rel; 269 } 270 // Only one relation will be kept - the one with lowest positive ID, if such exist 271 // or one "at random" if no such exists. Rest of the relations will be deleted 272 if (!r.isNew() && (idToKeep == 0 || r.getId() < idToKeep)) { 273 idToKeep = r.getId(); 274 relationToKeep = r; 275 } 276 } 277 278 Collection<Command> commands = new LinkedList<>(); 279 280 // Fix relations. 281 if (relationWithRelations != null && relRef != null && relationToKeep != relationWithRelations) { 282 for (Relation rel : relRef) { 283 List<RelationMember> members = new ArrayList<>(rel.getMembers()); 284 for (int i = 0; i < rel.getMembers().size(); ++i) { 285 RelationMember m = rel.getMember(i); 286 if (relationWithRelations.equals(m.getMember())) { 287 members.set(i, new RelationMember(m.getRole(), relationToKeep)); 288 } 289 } 290 commands.add(new ChangeMembersCommand(rel, members)); 291 } 292 } 293 294 // Delete all relations in the list 295 relFix.remove(relationToKeep); 296 commands.add(new DeleteCommand(relFix)); 297 return new SequenceCommand(tr("Delete duplicate relations"), commands); 298 } 299 300 @Override 301 public boolean isFixable(TestError testError) { 302 if (!(testError.getTester() instanceof DuplicateRelation) 303 || testError.getCode() == SAME_RELATION) return false; 304 305 // We fix it only if there is no more than one relation that is relation member. 306 Set<Relation> rels = testError.primitives(Relation.class) 307 .collect(Collectors.toSet()); 308 309 if (rels.size() < 2) 310 return false; 311 312 // count relations with relations 313 return rels.stream() 314 .filter(x -> x.referrers(Relation.class).anyMatch(y -> true)) 315 .limit(2) 316 .count() <= 1; 317 } 318}