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.NONE;
005
006import java.util.ArrayList;
007import java.util.List;
008import java.util.Map;
009import java.util.Set;
010import java.util.TreeMap;
011import java.util.TreeSet;
012
013import org.openstreetmap.josm.data.osm.INode;
014import org.openstreetmap.josm.data.osm.IPrimitive;
015import org.openstreetmap.josm.data.osm.IRelationMember;
016import org.openstreetmap.josm.data.osm.IWay;
017import org.openstreetmap.josm.tools.Utils;
018
019/**
020 * Auxiliary class for relation sorting.
021 *
022 * Constructs two mappings: One that maps each way to its nodes and the inverse mapping that
023 * maps each node to all ways that have this node.
024 * After construction both maps are consistent, but later on objects that are no longer needed
025 * are removed from the value sets.
026 * However the corresponding keys are not deleted even if they map to an empty set.
027 * Note that normal ways have 2 nodes (beginning and end) but roundabouts can have less or more
028 * (that are shared by other members).
029 *
030 * @author Christiaan Welvaart <cjw@time4t.net>
031 * @param <T> The type of {@link IRelationMember}
032 * @since 1785, xxx (generics)
033 */
034public class RelationNodeMap<T extends IRelationMember<? extends IPrimitive>> {
035
036    private static final String ROLE_BACKWARD = "backward";
037
038    private static class NodesWays {
039        public final Map<INode, Set<Integer>> nodes = new TreeMap<>();
040        public final Map<Integer, Set<INode>> ways = new TreeMap<>();
041        public final boolean oneWay;
042
043        NodesWays(boolean oneWay) {
044            this.oneWay = oneWay;
045        }
046    }
047
048    /*
049     * the maps. (Need TreeMap for efficiency.)
050     */
051    private final NodesWays map = new NodesWays(false);
052    /*
053     * Maps for oneways (forward/backward roles)
054     */
055
056    private final NodesWays onewayMap = new NodesWays(true);
057    private final NodesWays onewayReverseMap = new NodesWays(true);
058    /*
059     * Used to keep track of what members are done.
060     */
061    private final Set<Integer> remaining = new TreeSet<>();
062    private final Map<Integer, Set<INode>> remainingOneway = new TreeMap<>();
063
064    /**
065     * All members that are incomplete or not a way
066     */
067    private final List<Integer> notSortable = new ArrayList<>();
068
069    /**
070     * Gets the start node of the member, respecting the direction role.
071     * @param m The relation member.
072     * @return <code>null</code> if the member is no way, the node otherwise.
073     * @since 17862 (generics)
074     */
075    public static INode firstOnewayNode(IRelationMember<?> m) {
076        if (!m.isWay()) return null;
077        if (ROLE_BACKWARD.equals(m.getRole())) {
078            return m.getWay().lastNode();
079        }
080        return m.getWay().firstNode();
081    }
082
083    /**
084     * Gets the end node of the member, respecting the direction role.
085     * @param m The relation member.
086     * @return <code>null</code> if the member is no way, the node otherwise.
087     */
088    public static INode lastOnewayNode(IRelationMember<?> m) {
089        if (!m.isWay()) return null;
090        if (ROLE_BACKWARD.equals(m.getRole())) {
091            return m.getWay().firstNode();
092        }
093        return m.getWay().lastNode();
094    }
095
096    RelationNodeMap(List<T> members) {
097        for (int i = 0; i < members.size(); ++i) {
098            T m = members.get(i);
099            if (m.getMember().isIncomplete() || !m.isWay() || m.getWay().getNodesCount() < 2) {
100                notSortable.add(i);
101                continue;
102            }
103
104            IWay<?> w = m.getWay();
105            if (RelationSortUtils.roundaboutType(w) != NONE) {
106                for (INode nd : w.getNodes()) {
107                    addPair(nd, i);
108                }
109            } else if (RelationSortUtils.isOneway(m)) {
110                addNodeWayMap(firstOnewayNode(m), i);
111                addWayNodeMap(lastOnewayNode(m), i);
112                addNodeWayMapReverse(lastOnewayNode(m), i);
113                addWayNodeMapReverse(firstOnewayNode(m), i);
114                addRemainingForward(firstOnewayNode(m), i);
115                addRemainingForward(lastOnewayNode(m), i);
116            } else {
117                addPair(w.firstNode(), i);
118                addPair(w.lastNode(), i);
119            }
120        }
121
122        remaining.addAll(map.ways.keySet());
123    }
124
125    private void addPair(INode n, int i) {
126        map.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i);
127        map.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n);
128    }
129
130    private void addNodeWayMap(INode n, int i) {
131        onewayMap.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i);
132    }
133
134    private void addWayNodeMap(INode n, int i) {
135        onewayMap.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n);
136    }
137
138    private void addNodeWayMapReverse(INode n, int i) {
139        onewayReverseMap.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i);
140    }
141
142    private void addWayNodeMapReverse(INode n, int i) {
143        onewayReverseMap.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n);
144    }
145
146    private void addRemainingForward(INode n, int i) {
147        remainingOneway.computeIfAbsent(i, k -> new TreeSet<>()).add(n);
148    }
149
150    private Integer firstOneway;
151    private INode lastOnewayNode;
152    private INode firstCircular;
153
154    /**
155     * Return a relation member that is linked to the member 'i', but has not been popped yet.
156     * Return null if there is no such member left.
157     * @param way way key
158     * @return a relation member that is linked to the member 'i', but has not been popped yet
159     */
160    public Integer popAdjacent(Integer way) {
161        if (lastOnewayNode != null) return popBackwardOnewayPart(way);
162        if (firstOneway != null) return popForwardOnewayPart(way);
163
164        if (map.ways.containsKey(way)) {
165            for (INode n : map.ways.get(way)) {
166                Integer i = deleteAndGetAdjacentNode(map, n);
167                if (i != null) return i;
168
169                Integer j = deleteAndGetAdjacentNode(onewayMap, n);
170                if (j != null) {
171                    firstOneway = j;
172                    return j;
173                }
174            }
175        }
176
177        firstOneway = way;
178        return popForwardOnewayPart(way);
179    }
180
181    private Integer popForwardOnewayPart(Integer way) {
182        if (onewayMap.ways.containsKey(way)) {
183            INode exitNode = onewayMap.ways.get(way).iterator().next();
184
185            if (checkIfEndOfLoopReached(exitNode)) {
186                lastOnewayNode = exitNode;
187                return popBackwardOnewayPart(firstOneway);
188            }
189
190            Integer i = deleteAndGetAdjacentNode(onewayMap, exitNode);
191            if (i != null) return i;
192
193            // When our forward route ends in a dead end try to start
194            // the backward route anyway from the split point
195            // (firstOneWay), to support routes with split a split start
196            // or end.
197            lastOnewayNode = exitNode;
198            return popBackwardOnewayPart(firstOneway);
199        }
200
201        firstOneway = null;
202        return null;
203    }
204
205    // Check if the given node can be the end of the loop (i.e. it has
206    // an outgoing bidirectional or multiple outgoing oneways, or we
207    // looped back to our first circular node)
208    private boolean checkIfEndOfLoopReached(INode n) {
209        return map.nodes.containsKey(n)
210                || (onewayMap.nodes.containsKey(n) && (onewayMap.nodes.get(n).size() > 1))
211                || ((firstCircular != null) && (firstCircular == n));
212    }
213
214    private Integer popBackwardOnewayPart(int way) {
215        if (lastOnewayNode != null) {
216            Set<INode> nodes = new TreeSet<>();
217            if (onewayReverseMap.ways.containsKey(way)) {
218                nodes.addAll(onewayReverseMap.ways.get(way));
219            }
220            if (map.ways.containsKey(way)) {
221                nodes.addAll(map.ways.get(way));
222            }
223            for (INode n : nodes) {
224                if (n == lastOnewayNode) { //if oneway part ends
225                    firstOneway = null;
226                    lastOnewayNode = null;
227                    Integer j = deleteAndGetAdjacentNode(map, n);
228                    if (j != null) return j;
229
230                    Integer k = deleteAndGetAdjacentNode(onewayMap, n);
231                    if (k != null) {
232                        firstOneway = k;
233                        return k;
234                    }
235                }
236
237                Integer j = deleteAndGetAdjacentNode(onewayReverseMap, n);
238                if (j != null) return j;
239            }
240        }
241
242        firstOneway = null;
243        lastOnewayNode = null;
244
245        return null;
246    }
247
248    /**
249     * find next node in nw NodeWays structure, if the node is found delete and return it
250     * @param nw nodes and ways
251     * @param n node
252     * @return node next to n
253     */
254    private Integer deleteAndGetAdjacentNode(NodesWays nw, INode n) {
255        Integer j = findAdjacentWay(nw, n);
256        if (j == null) return null;
257        deleteWayNode(nw, j, n);
258        return j;
259    }
260
261    private static Integer findAdjacentWay(NodesWays nw, INode n) {
262        Set<Integer> adj = nw.nodes.get(n);
263        if (Utils.isEmpty(adj)) return null;
264        return adj.iterator().next();
265    }
266
267    private void deleteWayNode(NodesWays nw, Integer way, INode n) {
268        if (nw.oneWay) {
269            doneOneway(way);
270        } else {
271            done(way);
272            // For bidirectional ways, remove the entry node, so
273            // subsequent lookups will only return the other node(s) as
274            // valid exit nodes.
275            nw.ways.get(way).remove(n);
276        }
277    }
278
279    /**
280     * Returns some remaining member or null if every sortable member has been processed.
281     * @return member key
282     */
283    public Integer pop() {
284        if (!remaining.isEmpty()) {
285            Integer i = remaining.iterator().next();
286            done(i);
287            return i;
288        }
289
290        if (remainingOneway.isEmpty()) return null;
291        for (Integer i : remainingOneway.keySet()) { //find oneway, which is connected to more than one way (is between two oneway loops)
292            for (INode n : onewayReverseMap.ways.get(i)) {
293                if (onewayReverseMap.nodes.containsKey(n) && onewayReverseMap.nodes.get(n).size() > 1) {
294                    doneOneway(i);
295                    firstCircular = n;
296                    return i;
297                }
298            }
299        }
300
301        Integer i = remainingOneway.keySet().iterator().next();
302        doneOneway(i);
303        return i;
304    }
305
306    /**
307     * This relation member has been processed.
308     * Remove references in the map.nodes.
309     * @param i member key
310     */
311    private void doneOneway(Integer i) {
312        Set<INode> nodesForward = remainingOneway.get(i);
313        for (INode n : nodesForward) {
314            if (onewayMap.nodes.containsKey(n)) {
315                onewayMap.nodes.get(n).remove(i);
316            }
317            if (onewayReverseMap.nodes.containsKey(n)) {
318                onewayReverseMap.nodes.get(n).remove(i);
319            }
320        }
321        remainingOneway.remove(i);
322    }
323
324    private void done(Integer i) {
325        remaining.remove(i);
326        Set<INode> nodes = map.ways.get(i);
327        for (INode n : nodes) {
328            boolean result = map.nodes.get(n).remove(i);
329            if (!result) throw new AssertionError();
330        }
331    }
332
333    public List<Integer> getNotSortableMembers() {
334        return notSortable;
335    }
336}