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 = NONE;
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 ref_i, Direction ref_direction, int k) {
215        return determineDirection(ref_i, ref_direction, 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 ref_i way key
228     * @param ref_direction 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 ref_i, final Direction ref_direction, int k, boolean reversed) {
234        if (ref_i < 0 || k < 0 || ref_i >= members.size() || k >= members.size())
235            return NONE;
236        if (ref_direction == NONE)
237            return NONE;
238
239        final RelationMember m_ref = members.get(ref_i);
240        final RelationMember m = members.get(k);
241        Way way_ref = null;
242        Way way = null;
243
244        if (m_ref.isWay()) {
245            way_ref = m_ref.getWay();
246        }
247        if (m.isWay()) {
248            way = m.getWay();
249        }
250
251        if (way_ref == null || way == null)
252            return NONE;
253
254        /** the list of nodes the way k can dock to */
255        List<Node> refNodes = new ArrayList<>();
256
257        switch (ref_direction) {
258        case FORWARD:
259            refNodes.add(way_ref.lastNode());
260            break;
261        case BACKWARD:
262            refNodes.add(way_ref.firstNode());
263            break;
264        case ROUNDABOUT_LEFT:
265        case ROUNDABOUT_RIGHT:
266            refNodes = way_ref.getNodes();
267            break;
268        }
269
270        for (Node n : refNodes) {
271            if (n == null) {
272                continue;
273            }
274            if (RelationSortUtils.roundaboutType(members.get(k)) != NONE) {
275                for (Node nn : way.getNodes()) {
276                    if (n == nn)
277                        return RelationSortUtils.roundaboutType(members.get(k));
278                }
279            } else if (RelationSortUtils.isOneway(m)) {
280                if (n == RelationNodeMap.firstOnewayNode(m) && !reversed) {
281                    if (RelationSortUtils.isBackward(m))
282                        return BACKWARD;
283                    else
284                        return FORWARD;
285                }
286                if (n == RelationNodeMap.lastOnewayNode(m) && reversed) {
287                    if (RelationSortUtils.isBackward(m))
288                        return FORWARD;
289                    else
290                        return BACKWARD;
291                }
292            } else {
293                if (n == way.firstNode())
294                    return FORWARD;
295                if (n == way.lastNode())
296                    return BACKWARD;
297            }
298        }
299        return NONE;
300    }
301}