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