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