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 Objects.equals(role, relMember.role) && 068 type == relMember.type && 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 = new TestError(this, Severity.ERROR, tr("Duplicated relations"), DUPLICATE_RELATION, duplicated); 206 errors.add(testError); 207 } 208 } 209 relations = null; 210 for (Set<OsmPrimitive> duplicated : relationsNoKeys.values()) { 211 if (duplicated.size() > 1) { 212 TestError testError = new TestError(this, Severity.WARNING, tr("Relations with same members"), SAME_RELATION, duplicated); 213 errors.add(testError); 214 } 215 } 216 relationsNoKeys = null; 217 } 218 219 @Override 220 public void visit(Relation r) { 221 if (!r.isUsable() || r.hasIncompleteMembers()) 222 return; 223 List<RelationMember> rMembers = r.getMembers(); 224 Map<String, String> rkeys = r.getKeys(); 225 for (String key : ignoreKeys) { 226 rkeys.remove(key); 227 } 228 RelationPair rKey = new RelationPair(rMembers, rkeys); 229 relations.put(rKey, r); 230 relationsNoKeys.put(rMembers, r); 231 } 232 233 /** 234 * Fix the error by removing all but one instance of duplicate relations 235 * @param testError The error to fix, must be of type {@link #DUPLICATE_RELATION} 236 */ 237 @Override 238 public Command fixError(TestError testError) { 239 if (testError.getCode() == SAME_RELATION) return null; 240 Collection<? extends OsmPrimitive> sel = testError.getPrimitives(); 241 Set<Relation> relFix = new HashSet<>(); 242 243 for (OsmPrimitive osm : sel) { 244 if (osm instanceof Relation && !osm.isDeleted()) { 245 relFix.add((Relation) osm); 246 } 247 } 248 249 if (relFix.size() < 2) 250 return null; 251 252 long idToKeep = 0; 253 Relation relationToKeep = relFix.iterator().next(); 254 // Find the relation that is member of one or more relations. (If any) 255 Relation relationWithRelations = null; 256 List<Relation> relRef = null; 257 for (Relation w : relFix) { 258 List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class); 259 if (!rel.isEmpty()) { 260 if (relationWithRelations != null) 261 throw new AssertionError("Cannot fix duplicate relations: More than one relation is member of another relation."); 262 relationWithRelations = w; 263 relRef = rel; 264 } 265 // Only one relation will be kept - the one with lowest positive ID, if such exist 266 // or one "at random" if no such exists. Rest of the relations will be deleted 267 if (!w.isNew() && (idToKeep == 0 || w.getId() < idToKeep)) { 268 idToKeep = w.getId(); 269 relationToKeep = w; 270 } 271 } 272 273 Collection<Command> commands = new LinkedList<>(); 274 275 // Fix relations. 276 if (relationWithRelations != null && relationToKeep != relationWithRelations) { 277 for (Relation rel : relRef) { 278 Relation newRel = new Relation(rel); 279 for (int i = 0; i < newRel.getMembers().size(); ++i) { 280 RelationMember m = newRel.getMember(i); 281 if (relationWithRelations.equals(m.getMember())) { 282 newRel.setMember(i, new RelationMember(m.getRole(), relationToKeep)); 283 } 284 } 285 commands.add(new ChangeCommand(rel, newRel)); 286 } 287 } 288 289 //Delete all relations in the list 290 relFix.remove(relationToKeep); 291 commands.add(new DeleteCommand(relFix)); 292 return new SequenceCommand(tr("Delete duplicate relations"), commands); 293 } 294 295 @Override 296 public boolean isFixable(TestError testError) { 297 if (!(testError.getTester() instanceof DuplicateRelation) 298 || testError.getCode() == SAME_RELATION) return false; 299 300 // We fix it only if there is no more than one relation that is relation member. 301 Collection<? extends OsmPrimitive> sel = testError.getPrimitives(); 302 Set<Relation> relations = new HashSet<>(); 303 304 for (OsmPrimitive osm : sel) { 305 if (osm instanceof Relation) { 306 relations.add((Relation) osm); 307 } 308 } 309 310 if (relations.size() < 2) 311 return false; 312 313 int relationsWithRelations = 0; 314 for (Relation w : relations) { 315 List<Relation> rel = OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class); 316 if (!rel.isEmpty()) { 317 ++relationsWithRelations; 318 } 319 } 320 return relationsWithRelations <= 1; 321 } 322}