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.Arrays;
008import java.util.Collection;
009import java.util.Collections;
010import java.util.Comparator;
011import java.util.HashMap;
012import java.util.HashSet;
013import java.util.List;
014import java.util.Map;
015import java.util.Set;
016import java.util.TreeSet;
017
018import org.openstreetmap.josm.data.osm.Node;
019import org.openstreetmap.josm.data.osm.OsmPrimitive;
020import org.openstreetmap.josm.data.osm.OsmUtils;
021import org.openstreetmap.josm.data.osm.Relation;
022import org.openstreetmap.josm.data.osm.Way;
023import org.openstreetmap.josm.data.osm.WaySegment;
024import org.openstreetmap.josm.data.preferences.CollectionProperty;
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;
030import org.openstreetmap.josm.tools.Pair;
031import org.openstreetmap.josm.tools.Predicates;
032import org.openstreetmap.josm.tools.Utils;
033
034/**
035 * Tests if there are overlapping ways.
036 *
037 * @author frsantos
038 */
039public class OverlappingWays extends Test {
040
041    /** Bag of all way segments */
042    private MultiMap<Pair<Node,Node>, WaySegment> nodePairs;
043
044    protected static final int OVERLAPPING_HIGHWAY = 101;
045    protected static final int OVERLAPPING_RAILWAY = 102;
046    protected static final int OVERLAPPING_WAY = 103;
047    protected static final int OVERLAPPING_HIGHWAY_AREA = 111;
048    protected static final int OVERLAPPING_RAILWAY_AREA = 112;
049    protected static final int OVERLAPPING_WAY_AREA = 113;
050    protected static final int OVERLAPPING_AREA = 120;
051    protected static final int DUPLICATE_WAY_SEGMENT = 121;
052
053    protected static final CollectionProperty IGNORED_KEYS = new CollectionProperty(
054            "overlapping-ways.ignored-keys", Arrays.asList("barrier", "building", "historic:building"));
055
056    /** Constructor */
057    public OverlappingWays() {
058        super(tr("Overlapping ways"),
059                tr("This test checks that a connection between two nodes "
060                        + "is not used by more than one way."));
061    }
062
063    @Override
064    public void startTest(ProgressMonitor monitor)  {
065        super.startTest(monitor);
066        nodePairs = new MultiMap<>(1000);
067    }
068
069    private boolean parentMultipolygonConcernsArea(OsmPrimitive p) {
070        for (Relation r : OsmPrimitive.getFilteredList(p.getReferrers(), Relation.class)) {
071            if (r.concernsArea() ) {
072                return true;
073            }
074        }
075        return false;
076    }
077
078    @Override
079    public void endTest() {
080        Map<List<Way>, Set<WaySegment>> seenWays = new HashMap<>(500);
081
082        Collection<TestError> preliminaryErrors = new ArrayList<>();
083        for (Set<WaySegment> duplicated : nodePairs.values()) {
084            int ways = duplicated.size();
085
086            if (ways > 1) {
087                List<OsmPrimitive> prims = new ArrayList<>();
088                List<Way> currentWays = new ArrayList<>();
089                Collection<WaySegment> highlight;
090                int highway = 0;
091                int railway = 0;
092                int area = 0;
093
094                for (WaySegment ws : duplicated) {
095                    if (ws.way.get("highway") != null) {
096                        highway++;
097                    } else if (ws.way.get("railway") != null) {
098                        railway++;
099                    }
100                    Boolean ar = OsmUtils.getOsmBoolean(ws.way.get("area"));
101                    if (ar != null && ar) {
102                        area++;
103                    }
104                    if (ws.way.concernsArea() || parentMultipolygonConcernsArea(ws.way)) {
105                        area++;
106                        ways--;
107                    }
108
109                    prims.add(ws.way);
110                    currentWays.add(ws.way);
111                }
112                /* These ways not seen before
113                 * If two or more of the overlapping ways are
114                 * highways or railways mark a separate error
115                 */
116                if ((highlight = seenWays.get(currentWays)) == null) {
117                    String errortype;
118                    int type;
119
120                    if (area > 0) {
121                        if (ways == 0 || duplicated.size() == area) {
122                            errortype = tr("Areas share segment");
123                            type = OVERLAPPING_AREA;
124                        } else if (highway == ways) {
125                            errortype = tr("Highways share segment with area");
126                            type = OVERLAPPING_HIGHWAY_AREA;
127                        } else if (railway == ways) {
128                            errortype = tr("Railways share segment with area");
129                            type = OVERLAPPING_RAILWAY_AREA;
130                        } else {
131                            errortype = tr("Ways share segment with area");
132                            type = OVERLAPPING_WAY_AREA;
133                        }
134                    }
135                    else if (highway == ways) {
136                        errortype = tr("Overlapping highways");
137                        type = OVERLAPPING_HIGHWAY;
138                    } else if (railway == ways) {
139                        errortype = tr("Overlapping railways");
140                        type = OVERLAPPING_RAILWAY;
141                    } else {
142                        errortype = tr("Overlapping ways");
143                        type = OVERLAPPING_WAY;
144                    }
145
146                    preliminaryErrors.add(new TestError(this,
147                            type < OVERLAPPING_HIGHWAY_AREA ? Severity.WARNING : Severity.OTHER,
148                                    errortype, type, prims, duplicated));
149                    seenWays.put(currentWays, duplicated);
150                } else { /* way seen, mark highlight layer only */
151                    for (WaySegment ws : duplicated) {
152                        highlight.add(ws);
153                    }
154                }
155            }
156        }
157
158        // see ticket #9598 - only report if at least 3 segments are shared, except for overlapping ways, i.e warnings (see #9820)
159        for (TestError error : preliminaryErrors) {
160            if (error.getSeverity().equals(Severity.WARNING) || error.getHighlighted().size() / error.getPrimitives().size() >= 3) {
161                boolean ignore = false;
162                for (String ignoredKey : IGNORED_KEYS.get()) {
163                    if (Utils.exists(error.getPrimitives(), Predicates.hasKey(ignoredKey))) {
164                        ignore = true;
165                        break;
166                    }
167                }
168                if (!ignore) {
169                    errors.add(error);
170                }
171            }
172        }
173
174        super.endTest();
175        nodePairs = null;
176    }
177
178    protected static Set<WaySegment> checkDuplicateWaySegment(Way w) {
179        // test for ticket #4959
180        Set<WaySegment> segments = new TreeSet<>(new Comparator<WaySegment>() {
181            @Override
182            public int compare(WaySegment o1, WaySegment o2) {
183                final List<Node> n1 = Arrays.asList(o1.getFirstNode(), o1.getSecondNode());
184                final List<Node> n2 = Arrays.asList(o2.getFirstNode(), o2.getSecondNode());
185                Collections.sort(n1);
186                Collections.sort(n2);
187                final int first = n1.get(0).compareTo(n2.get(0));
188                final int second = n1.get(1).compareTo(n2.get(1));
189                return first != 0 ? first : second;
190            }
191        });
192        final Set<WaySegment> duplicateWaySegments = new HashSet<>();
193
194        for (int i = 0; i < w.getNodesCount() - 1; i++) {
195            final WaySegment segment = new WaySegment(w, i);
196            final boolean wasInSet = !segments.add(segment);
197            if (wasInSet) {
198                duplicateWaySegments.add(segment);
199            }
200        }
201        if (duplicateWaySegments.size() > 1) {
202            return duplicateWaySegments;
203        } else {
204            return null;
205        }
206    }
207
208    @Override
209    public void visit(Way w) {
210
211        final Set<WaySegment> duplicateWaySegment = checkDuplicateWaySegment(w);
212        if (duplicateWaySegment != null) {
213            errors.add(new TestError(this, Severity.ERROR, tr("Way contains segment twice"),
214                    DUPLICATE_WAY_SEGMENT, Collections.singleton(w), duplicateWaySegment));
215            return;
216        }
217
218        Node lastN = null;
219        int i = -2;
220        for (Node n : w.getNodes()) {
221            i++;
222            if (lastN == null) {
223                lastN = n;
224                continue;
225            }
226            nodePairs.put(Pair.sort(new Pair<>(lastN, n)),
227                    new WaySegment(w, i));
228            lastN = n;
229        }
230    }
231}