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        con.set(i, wct);
123        return wct;
124    }
125
126    private void handleOneway(WayConnectionType lastWct, int i, WayConnectionType wct) {
127        if (lastWct != null && lastWct.isOnewayTail) {
128            wct.isOnewayHead = true;
129        }
130        if (lastBackwardWay == UNCONNECTED && lastForwardWay == UNCONNECTED) { //Beginning of new oneway
131            wct.isOnewayHead = true;
132            lastForwardWay = i-1;
133            lastBackwardWay = i-1;
134            onewayBeginning = true;
135        }
136    }
137
138    private int firstGroupIdx;
139    private void makeLoopIfNeeded(final List<WayConnectionType> con, final int i) {
140        boolean loop = false;
141        if (i == firstGroupIdx) { //is primitive loop
142            loop = determineDirection(i, FORWARD, i) == FORWARD;
143        } else if (i >= 0) {
144            loop = determineDirection(i, con.get(i).direction, firstGroupIdx) == con.get(firstGroupIdx).direction;
145        }
146        if (loop) {
147            for (int j = firstGroupIdx; j <= i; ++j) {
148                con.get(j).isLoop = true;
149            }
150        }
151    }
152
153    private Direction determineDirectionOfFirst(final int i, final RelationMember m) {
154        Direction result = RelationSortUtils.roundaboutType(m);
155        if (result != NONE)
156            return result;
157
158        if (RelationSortUtils.isOneway(m)) {
159            if (RelationSortUtils.isBackward(m)) return BACKWARD;
160            else return FORWARD;
161        } else { /** guess the direction and see if it fits with the next member */
162            if (determineDirection(i, FORWARD, i+1) != NONE) return FORWARD;
163            if (determineDirection(i, BACKWARD, i+1) != NONE) return BACKWARD;
164        }
165        return NONE;
166    }
167
168    private int lastForwardWay;
169    private int lastBackwardWay;
170    private boolean onewayBeginning;
171
172    private void determineOnewayConnectionType(final List<WayConnectionType> con,
173            RelationMember m, int i, final WayConnectionType wct) {
174        Direction dirFW = determineDirection(lastForwardWay, con.get(lastForwardWay).direction, i);
175        Direction dirBW;
176        if (onewayBeginning) {
177            if (lastBackwardWay < 0) {
178                dirBW = determineDirection(firstGroupIdx, reverse(con.get(firstGroupIdx).direction), i, true);
179            } else {
180                dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
181            }
182
183            if (dirBW != NONE) {
184                onewayBeginning = false;
185            }
186        } else {
187            dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
188        }
189
190        if (RelationSortUtils.isOneway(m)) {
191            if (dirBW != NONE) {
192                wct.direction = dirBW;
193                lastBackwardWay = i;
194                wct.isOnewayLoopBackwardPart = true;
195            }
196            if (dirFW != NONE) {
197                wct.direction = dirFW;
198                lastForwardWay = i;
199                wct.isOnewayLoopForwardPart = true;
200            }
201            // Not connected to previous
202            if (dirFW == NONE && dirBW == NONE) {
203                wct.linkPrev = false;
204                if (RelationSortUtils.isOneway(m)) {
205                    wct.isOnewayHead = true;
206                    lastForwardWay = i-1;
207                    lastBackwardWay = i-1;
208                } else {
209                    lastForwardWay = UNCONNECTED;
210                    lastBackwardWay = UNCONNECTED;
211                }
212                onewayBeginning = true;
213            }
214
215            if (dirFW != NONE && dirBW != NONE) { //End of oneway loop
216                if (i+1 < members.size() && determineDirection(i, dirFW, i+1) != NONE) {
217                    wct.isOnewayLoopBackwardPart = false;
218                    wct.direction = dirFW;
219                } else {
220                    wct.isOnewayLoopForwardPart = false;
221                    wct.direction = dirBW;
222                }
223
224                wct.isOnewayTail = true;
225            }
226
227        } else {
228            lastForwardWay = UNCONNECTED;
229            lastBackwardWay = UNCONNECTED;
230            if (dirFW == NONE || dirBW == NONE) {
231                wct.linkPrev = false;
232            }
233        }
234    }
235
236    private static Direction reverse(final Direction dir) {
237        if (dir == FORWARD) return BACKWARD;
238        if (dir == BACKWARD) return FORWARD;
239        return dir;
240    }
241
242    private Direction determineDirection(int refI, Direction refDirection, int k) {
243        return determineDirection(refI, refDirection, k, false);
244    }
245
246    /**
247     * Determines the direction of way {@code k} with respect to the way {@code ref_i}.
248     * The way {@code ref_i} is assumed to have the direction {@code ref_direction} and to be the predecessor of {@code k}.
249     *
250     * If both ways are not linked in any way, NONE is returned.
251     *
252     * Else the direction is given as follows:
253     * Let the relation be a route of oneway streets, and someone travels them in the given order.
254     * Direction is FORWARD if it is legal and BACKWARD if it is illegal to do so for the given way.
255     * @param refI way key
256     * @param refDirection direction of ref_i
257     * @param k successor of ref_i
258     * @param reversed if {@code true} determine reverse direction
259     * @return direction of way {@code k}
260     */
261    private Direction determineDirection(int refI, final Direction refDirection, int k, boolean reversed) {
262        if (members == null || refI < 0 || k < 0 || refI >= members.size() || k >= members.size() || refDirection == NONE)
263            return NONE;
264
265        final RelationMember mRef = members.get(refI);
266        final RelationMember m = members.get(k);
267        Way wayRef = null;
268        Way way = null;
269
270        if (mRef.isWay()) {
271            wayRef = mRef.getWay();
272        }
273        if (m.isWay()) {
274            way = m.getWay();
275        }
276
277        if (wayRef == null || way == null)
278            return NONE;
279
280        /** the list of nodes the way k can dock to */
281        List<Node> refNodes = new ArrayList<>();
282
283        switch (refDirection) {
284        case FORWARD:
285            refNodes.add(wayRef.lastNode());
286            break;
287        case BACKWARD:
288            refNodes.add(wayRef.firstNode());
289            break;
290        case ROUNDABOUT_LEFT:
291        case ROUNDABOUT_RIGHT:
292            refNodes = wayRef.getNodes();
293            break;
294        default: // Do nothing
295        }
296
297        for (Node n : refNodes) {
298            if (n == null) {
299                continue;
300            }
301            if (RelationSortUtils.roundaboutType(members.get(k)) != NONE) {
302                for (Node nn : way.getNodes()) {
303                    if (n == nn)
304                        return RelationSortUtils.roundaboutType(members.get(k));
305                }
306            } else if (RelationSortUtils.isOneway(m)) {
307                if (n == RelationNodeMap.firstOnewayNode(m) && !reversed) {
308                    if (RelationSortUtils.isBackward(m))
309                        return BACKWARD;
310                    else
311                        return FORWARD;
312                }
313                if (reversed && n == RelationNodeMap.lastOnewayNode(m)) {
314                    if (RelationSortUtils.isBackward(m))
315                        return FORWARD;
316                    else
317                        return BACKWARD;
318                }
319            } else {
320                if (n == way.firstNode())
321                    return FORWARD;
322                if (n == way.lastNode())
323                    return BACKWARD;
324            }
325        }
326        return NONE;
327    }
328
329
330    /**
331     * Free resources.
332     */
333    public void clear() {
334        members = null;
335    }
336}