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