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