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<WayConnectionType>();
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                    wct = 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    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    int lastForwardWay, lastBackwardWay;
139    boolean onewayBeginning;
140    private WayConnectionType determineOnewayConnectionType(final List<WayConnectionType> con,
141            RelationMember m, int i, final WayConnectionType wct) {
142        Direction dirFW = determineDirection(lastForwardWay, con.get(lastForwardWay).direction, i);
143        Direction dirBW = NONE;
144        if (onewayBeginning) {
145            if (lastBackwardWay < 0) {
146                dirBW = determineDirection(firstGroupIdx, reverse(con.get(firstGroupIdx).direction), i, true);
147            } else {
148                dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
149            }
150
151            if (dirBW != NONE) {
152                onewayBeginning = false;
153            }
154        } else {
155            dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
156        }
157
158        if (RelationSortUtils.isOneway(m)) {
159            if (dirBW != NONE){
160                wct.direction = dirBW;
161                lastBackwardWay = i;
162                wct.isOnewayLoopBackwardPart = true;
163            }
164            if (dirFW != NONE){
165                wct.direction = dirFW;
166                lastForwardWay = i;
167                wct.isOnewayLoopForwardPart = true;
168            }
169            // Not connected to previous
170            if (dirFW == NONE && dirBW == NONE) {
171                wct.linkPrev = false;
172                if (RelationSortUtils.isOneway(m)) {
173                    wct.isOnewayHead = true;
174                    lastForwardWay = i-1;
175                    lastBackwardWay = i-1;
176                } else {
177                    lastForwardWay = UNCONNECTED;
178                    lastBackwardWay = UNCONNECTED;
179                }
180                onewayBeginning = true;
181            }
182
183            if (dirFW != NONE && dirBW != NONE) { //End of oneway loop
184                if (i+1<members.size() && determineDirection(i, dirFW, i+1) != NONE) {
185                    wct.isOnewayLoopBackwardPart = false;
186                    wct.direction = dirFW;
187                } else {
188                    wct.isOnewayLoopForwardPart = false;
189                    wct.direction = dirBW;
190                }
191
192                wct.isOnewayTail = true;
193            }
194
195        } else {
196            lastForwardWay = UNCONNECTED;
197            lastBackwardWay = UNCONNECTED;
198            if (dirFW == NONE || dirBW == NONE) {
199                wct.linkPrev = false;
200            }
201        }
202        return wct;
203    }
204
205    private static Direction reverse(final Direction dir){
206        if (dir == FORWARD) return BACKWARD;
207        if (dir == BACKWARD) return FORWARD;
208        return dir;
209    }
210
211    private Direction determineDirection(int ref_i, Direction ref_direction, int k) {
212        return determineDirection(ref_i, ref_direction, k, false);
213    }
214    /**
215     * Determines the direction of way k with respect to the way ref_i.
216     * The way ref_i is assumed to have the direction ref_direction and
217     * to be the predecessor of k.
218     *
219     * If both ways are not linked in any way, NONE is returned.
220     *
221     * Else the direction is given as follows:
222     * Let the relation be a route of oneway streets, and someone travels them in the given order.
223     * Direction is FORWARD if it is legal and BACKWARD if it is illegal to do so for the given way.
224     *
225     **/
226    private Direction determineDirection(int ref_i, final Direction ref_direction, int k, boolean reversed) {
227        if (ref_i < 0 || k < 0 || ref_i >= members.size() || k >= members.size())
228            return NONE;
229        if (ref_direction == NONE)
230            return NONE;
231
232        final RelationMember m_ref = members.get(ref_i);
233        final RelationMember m = members.get(k);
234        Way way_ref = null;
235        Way way = null;
236
237        if (m_ref.isWay()) {
238            way_ref = m_ref.getWay();
239        }
240        if (m.isWay()) {
241            way = m.getWay();
242        }
243
244        if (way_ref == null || way == null)
245            return NONE;
246
247        /** the list of nodes the way k can dock to */
248        List<Node> refNodes= new ArrayList<Node>();
249
250        switch (ref_direction) {
251        case FORWARD:
252            refNodes.add(way_ref.lastNode());
253            break;
254        case BACKWARD:
255            refNodes.add(way_ref.firstNode());
256            break;
257        case ROUNDABOUT_LEFT:
258        case ROUNDABOUT_RIGHT:
259            refNodes = way_ref.getNodes();
260            break;
261        }
262
263        for (Node n : refNodes) {
264            if (n == null) {
265                continue;
266            }
267            if (RelationSortUtils.roundaboutType(members.get(k)) != NONE) {
268                for (Node nn : way.getNodes()) {
269                    if (n == nn)
270                        return RelationSortUtils.roundaboutType(members.get(k));
271                }
272            } else if (RelationSortUtils.isOneway(m)) {
273                if (n == RelationNodeMap.firstOnewayNode(m) && !reversed) {
274                    if (RelationSortUtils.isBackward(m))
275                        return BACKWARD;
276                    else
277                        return FORWARD;
278                }
279                if (n == RelationNodeMap.lastOnewayNode(m) && reversed) {
280                    if (RelationSortUtils.isBackward(m))
281                        return FORWARD;
282                    else
283                        return BACKWARD;
284                }
285            } else {
286                if (n == way.firstNode())
287                    return FORWARD;
288                if (n == way.lastNode())
289                    return BACKWARD;
290            }
291        }
292        return NONE;
293    }
294}