001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.gui.dialogs.relation.sort;
003
004import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.BACKWARD;
005import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.FORWARD;
006import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.NONE;
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.openstreetmap.josm.data.osm.Node;
012import org.openstreetmap.josm.data.osm.RelationMember;
013import org.openstreetmap.josm.data.osm.Way;
014import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction;
015import org.openstreetmap.josm.tools.JosmRuntimeException;
016import org.openstreetmap.josm.tools.bugreport.BugReport;
017
018/**
019 * This class calculates the {@link WayConnectionType} for a given list of members
020 */
021public class WayConnectionTypeCalculator {
022
023    private static final int UNCONNECTED = Integer.MIN_VALUE;
024
025    private List<RelationMember> members;
026
027    /**
028     * refresh the cache of member WayConnectionTypes
029     * @param members relation members
030     * @return way connections
031     */
032    public List<WayConnectionType> updateLinks(List<RelationMember> members) {
033        this.members = members;
034        final List<WayConnectionType> con = new ArrayList<>();
035
036        for (int i = 0; i < members.size(); ++i) {
037            con.add(null);
038        }
039
040        firstGroupIdx = 0;
041
042        lastForwardWay = UNCONNECTED;
043        lastBackwardWay = UNCONNECTED;
044        onewayBeginning = false;
045        WayConnectionType lastWct = null;
046
047        for (int i = 0; i < members.size(); ++i) {
048            try {
049                lastWct = updateLinksFor(con, lastWct, i);
050            } catch (JosmRuntimeException | IllegalArgumentException | IllegalStateException e) {
051                int index = i;
052                throw BugReport.intercept(e).put("i", i).put("member", () -> members.get(index)).put("con", con);
053            }
054        }
055        makeLoopIfNeeded(con, members.size()-1);
056
057        return con;
058    }
059
060    private WayConnectionType updateLinksFor(final List<WayConnectionType> con, WayConnectionType lastWct, int i) {
061        final RelationMember m = members.get(i);
062        if (isNoHandleableWay(m)) {
063            if (i > 0) {
064                makeLoopIfNeeded(con, i-1);
065            }
066            con.set(i, new WayConnectionType());
067            firstGroupIdx = i;
068        } else {
069            WayConnectionType wct = computeNextWayConnection(con, lastWct, i, m);
070
071            if (!wct.linkPrev) {
072                if (i > 0) {
073                    makeLoopIfNeeded(con, i-1);
074                }
075                firstGroupIdx = i;
076            }
077            return wct;
078        }
079        return lastWct;
080    }
081
082    private static boolean isNoHandleableWay(final RelationMember m) {
083        return !m.isWay() || m.getWay() == null || m.getWay().isIncomplete();
084    }
085
086    private WayConnectionType computeNextWayConnection(final List<WayConnectionType> con, WayConnectionType lastWct, int i,
087            final RelationMember m) {
088        WayConnectionType wct = new WayConnectionType(false);
089        wct.linkPrev = i > 0 && con.get(i-1) != null && con.get(i-1).isValid();
090        wct.direction = NONE;
091
092        if (RelationSortUtils.isOneway(m)) {
093            handleOneway(lastWct, i, wct);
094        }
095
096        if (wct.linkPrev) {
097            if (lastBackwardWay != UNCONNECTED && lastForwardWay != UNCONNECTED) {
098                determineOnewayConnectionType(con, m, i, wct);
099                if (!wct.linkPrev) {
100                    firstGroupIdx = i;
101                }
102            }
103
104            if (lastWct != null && !RelationSortUtils.isOneway(m)) {
105                wct.direction = determineDirection(i-1, lastWct.direction, i);
106                wct.linkPrev = wct.direction != NONE;
107            }
108        }
109
110        if (!wct.linkPrev) {
111            wct.direction = determineDirectionOfFirst(i, m);
112            if (RelationSortUtils.isOneway(m)) {
113                wct.isOnewayLoopForwardPart = true;
114                lastForwardWay = i;
115            }
116        }
117
118        wct.linkNext = false;
119        if (lastWct != null) {
120            lastWct.linkNext = wct.linkPrev;
121        }
122
123        if (lastWct != null && i > 0 && m.getMember() instanceof Way && members.get(i - 1).getMember() instanceof Way
124                && (m.getWay().isOneway() != 0 || members.get(i - 1).getWay().isOneway() != 0)) {
125            Way way = m.getWay();
126            Way previousWay = members.get(i - 1).getWay();
127            if (way.isOneway() != 0 && previousWay.isOneway() != 0 &&
128                    (way.firstNode(true) != previousWay.lastNode(true) &&
129                        way.lastNode(true) != previousWay.firstNode(true))) {
130                wct.onewayFollowsPrevious = false;
131                lastWct.onewayFollowsNext = false;
132            } else if (way.isOneway() != 0 && previousWay.isOneway() == 0 &&
133                    previousWay.isFirstLastNode(way.lastNode(true))) {
134                wct.onewayFollowsPrevious = false;
135            }
136        }
137        con.set(i, wct);
138        return wct;
139    }
140
141    private void handleOneway(WayConnectionType lastWct, int i, WayConnectionType wct) {
142        if (lastWct != null && lastWct.isOnewayTail) {
143            wct.isOnewayHead = true;
144        }
145        if (lastBackwardWay == UNCONNECTED && lastForwardWay == UNCONNECTED) { //Beginning of new oneway
146            wct.isOnewayHead = true;
147            lastForwardWay = i-1;
148            lastBackwardWay = i-1;
149            onewayBeginning = true;
150        }
151    }
152
153    private int firstGroupIdx;
154    private void makeLoopIfNeeded(final List<WayConnectionType> con, final int i) {
155        boolean loop = false;
156        if (i == firstGroupIdx) { //is primitive loop
157            loop = determineDirection(i, FORWARD, i) == FORWARD;
158        } else if (i >= 0) {
159            loop = determineDirection(i, con.get(i).direction, firstGroupIdx) == con.get(firstGroupIdx).direction;
160        }
161        if (loop) {
162            for (int j = firstGroupIdx; j <= i; ++j) {
163                con.get(j).isLoop = true;
164            }
165        }
166    }
167
168    private Direction determineDirectionOfFirst(final int i, final RelationMember m) {
169        Direction result = RelationSortUtils.roundaboutType(m);
170        if (result != NONE)
171            return result;
172
173        if (RelationSortUtils.isOneway(m)) {
174            if (RelationSortUtils.isBackward(m)) return BACKWARD;
175            else return FORWARD;
176        } else { /** guess the direction and see if it fits with the next member */
177            if (determineDirection(i, FORWARD, i+1) != NONE) return FORWARD;
178            if (determineDirection(i, BACKWARD, i+1) != NONE) return BACKWARD;
179        }
180        return NONE;
181    }
182
183    private int lastForwardWay;
184    private int lastBackwardWay;
185    private boolean onewayBeginning;
186
187    private void determineOnewayConnectionType(final List<WayConnectionType> con,
188            RelationMember m, int i, final WayConnectionType wct) {
189        Direction dirFW = determineDirection(lastForwardWay, con.get(lastForwardWay).direction, i);
190        Direction dirBW;
191        if (onewayBeginning) {
192            if (lastBackwardWay < 0) {
193                dirBW = determineDirection(firstGroupIdx, reverse(con.get(firstGroupIdx).direction), i, true);
194            } else {
195                dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
196            }
197
198            if (dirBW != NONE) {
199                onewayBeginning = false;
200            }
201        } else {
202            dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
203        }
204
205        if (RelationSortUtils.isOneway(m)) {
206            if (dirBW != NONE) {
207                wct.direction = dirBW;
208                lastBackwardWay = i;
209                wct.isOnewayLoopBackwardPart = true;
210            }
211            if (dirFW != NONE) {
212                wct.direction = dirFW;
213                lastForwardWay = i;
214                wct.isOnewayLoopForwardPart = true;
215            }
216            // Not connected to previous
217            if (dirFW == NONE && dirBW == NONE) {
218                wct.linkPrev = false;
219                if (RelationSortUtils.isOneway(m)) {
220                    wct.isOnewayHead = true;
221                    lastForwardWay = i-1;
222                    lastBackwardWay = i-1;
223                } else {
224                    lastForwardWay = UNCONNECTED;
225                    lastBackwardWay = UNCONNECTED;
226                }
227                onewayBeginning = true;
228            }
229
230            if (dirFW != NONE && dirBW != NONE) { //End of oneway loop
231                if (i+1 < members.size() && determineDirection(i, dirFW, i+1) != NONE) {
232                    wct.isOnewayLoopBackwardPart = false;
233                    wct.direction = dirFW;
234                } else {
235                    wct.isOnewayLoopForwardPart = false;
236                    wct.direction = dirBW;
237                }
238
239                wct.isOnewayTail = true;
240            }
241
242        } else {
243            lastForwardWay = UNCONNECTED;
244            lastBackwardWay = UNCONNECTED;
245            if (dirFW == NONE || dirBW == NONE) {
246                wct.linkPrev = false;
247            }
248        }
249    }
250
251    private static Direction reverse(final Direction dir) {
252        if (dir == FORWARD) return BACKWARD;
253        if (dir == BACKWARD) return FORWARD;
254        return dir;
255    }
256
257    private Direction determineDirection(int refI, Direction refDirection, int k) {
258        return determineDirection(refI, refDirection, k, false);
259    }
260
261    /**
262     * Determines the direction of way {@code k} with respect to the way {@code ref_i}.
263     * The way {@code ref_i} is assumed to have the direction {@code ref_direction} and to be the predecessor of {@code k}.
264     *
265     * If both ways are not linked in any way, NONE is returned.
266     *
267     * Else the direction is given as follows:
268     * Let the relation be a route of oneway streets, and someone travels them in the given order.
269     * Direction is FORWARD if it is legal and BACKWARD if it is illegal to do so for the given way.
270     * @param refI way key
271     * @param refDirection direction of ref_i
272     * @param k successor of ref_i
273     * @param reversed if {@code true} determine reverse direction
274     * @return direction of way {@code k}
275     */
276    private Direction determineDirection(int refI, final Direction refDirection, int k, boolean reversed) {
277        if (members == null || refI < 0 || k < 0 || refI >= members.size() || k >= members.size() || refDirection == NONE)
278            return NONE;
279
280        final RelationMember mRef = members.get(refI);
281        final RelationMember m = members.get(k);
282        Way wayRef = null;
283        Way way = null;
284
285        if (mRef.isWay()) {
286            wayRef = mRef.getWay();
287        }
288        if (m.isWay()) {
289            way = m.getWay();
290        }
291
292        if (wayRef == null || way == null)
293            return NONE;
294
295        /** the list of nodes the way k can dock to */
296        List<Node> refNodes = new ArrayList<>();
297
298        switch (refDirection) {
299        case FORWARD:
300            refNodes.add(wayRef.lastNode());
301            break;
302        case BACKWARD:
303            refNodes.add(wayRef.firstNode());
304            break;
305        case ROUNDABOUT_LEFT:
306        case ROUNDABOUT_RIGHT:
307            refNodes = wayRef.getNodes();
308            break;
309        default: // Do nothing
310        }
311
312        for (Node n : refNodes) {
313            if (n == null) {
314                continue;
315            }
316            if (RelationSortUtils.roundaboutType(members.get(k)) != NONE) {
317                for (Node nn : way.getNodes()) {
318                    if (n == nn)
319                        return RelationSortUtils.roundaboutType(members.get(k));
320                }
321            } else if (RelationSortUtils.isOneway(m)) {
322                if (n == RelationNodeMap.firstOnewayNode(m) && !reversed) {
323                    if (RelationSortUtils.isBackward(m))
324                        return BACKWARD;
325                    else
326                        return FORWARD;
327                }
328                if (reversed && n == RelationNodeMap.lastOnewayNode(m)) {
329                    if (RelationSortUtils.isBackward(m))
330                        return FORWARD;
331                    else
332                        return BACKWARD;
333                }
334            } else {
335                if (n == way.firstNode())
336                    return FORWARD;
337                if (n == way.lastNode())
338                    return BACKWARD;
339            }
340        }
341        return NONE;
342    }
343
344
345    /**
346     * Free resources.
347     */
348    public void clear() {
349        members = null;
350    }
351}