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