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