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}