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