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<>();
075
076            if (src.isNode()) {
077                Node r = src.getNode();
078                tags = r.getKeys();
079                coor = new ArrayList<>(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<>(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<>();
096            }
097        }
098    }
099
100    /**
101     * Class to store relation members
102     */
103    private static 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<>(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<>(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<>(1000);
188        relations_nokeys = new MultiMap<>(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<>();
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<>();
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<>();
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}