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