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 *
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
176     * member 'i', but has not been popped yet.
177     * Return null if there is no such member left.
178     */
179    public Integer popAdjacent(Integer way) {
180        if (lastOnewayNode != null) return popBackwardOnewayPart(way);
181        if (firstOneway != null) return popForwardOnewayPart(way);
182
183        if (map.ways.containsKey(way)) {
184            for (Node n : map.ways.get(way)) {
185                Integer i = deleteAndGetAdjacentNode(map, n);
186                if (i != null) return i;
187
188                Integer j = deleteAndGetAdjacentNode(onewayMap, n);
189                if (j != null) {
190                    firstOneway = j;
191                    return j;
192                }
193            }
194        }
195
196        firstOneway = way;
197        return popForwardOnewayPart(way);
198    }
199
200    private Integer popForwardOnewayPart(Integer way) {
201        if (onewayMap.ways.containsKey(way)) {
202            for (Node n : onewayMap.ways.get(way)) {
203                Integer i = findAdjacentWay(onewayMap, n);
204                if (i == null) {
205                    continue;
206                }
207
208                lastOnewayNode = processBackwardIfEndOfLoopReached(i);
209                if (lastOnewayNode != null)
210                    return popBackwardOnewayPart(firstOneway);
211
212                deleteWayNode(onewayMap, i, n);
213                return i;
214            }
215        }
216
217        firstOneway = null;
218        return null;
219    }
220
221    private Node processBackwardIfEndOfLoopReached(Integer way) { //find if we didn't reach end of the loop (and process backward part)
222        if (onewayReverseMap.ways.containsKey(way)) {
223            for (Node n : onewayReverseMap.ways.get(way)) {
224                if ((map.nodes.containsKey(n))
225                        || (onewayMap.nodes.containsKey(n) && onewayMap.nodes.get(n).size() > 1))
226                    return n;
227                if (firstCircular != null && firstCircular == n)
228                    return firstCircular;
229            }
230        }
231        return null;
232    }
233
234    private Integer popBackwardOnewayPart(int way) {
235        if (lastOnewayNode != null) {
236            Set<Node> nodes = new TreeSet<>();
237            if (onewayReverseMap.ways.containsKey(way)) {
238                nodes.addAll(onewayReverseMap.ways.get(way));
239            }
240            if (map.ways.containsKey(way)) {
241                nodes.addAll(map.ways.get(way));
242            }
243            for (Node n : nodes) {
244                if (n == lastOnewayNode) { //if oneway part ends
245                    firstOneway = null;
246                    lastOnewayNode = null;
247                    Integer j = deleteAndGetAdjacentNode(map, n);
248                    if (j != null) return j;
249
250                    Integer k = deleteAndGetAdjacentNode(onewayMap, n);
251                    if (k != null) {
252                        firstOneway = k;
253                        return k;
254                    }
255                }
256
257                Integer j = deleteAndGetAdjacentNode(onewayReverseMap, n);
258                if (j != null) return j;
259            }
260        }
261
262        firstOneway = null;
263        lastOnewayNode = null;
264
265        return null;
266    }
267
268    /**
269     * find next node in nw NodeWays structure, if the node is found delete and return it
270     * @param nw nodes and ways
271     * @param n node
272     * @return node next to n
273     */
274    private Integer deleteAndGetAdjacentNode(NodesWays nw, Node n) {
275        Integer j = findAdjacentWay(nw, n);
276        if (j == null) return null;
277        deleteWayNode(nw, j, n);
278        return j;
279    }
280
281    private Integer findAdjacentWay(NodesWays nw, Node n) {
282        Set<Integer> adj = nw.nodes.get(n);
283        if (adj == null || adj.isEmpty()) return null;
284        return adj.iterator().next();
285    }
286
287    private void deleteWayNode(NodesWays nw, Integer way, Node n) {
288        if (nw.oneWay) {
289            doneOneway(way);
290        } else {
291            done(way);
292        }
293        nw.ways.get(way).remove(n);
294    }
295
296    /**
297     * Returns some remaining member or null if
298     * every sortable member has been processed.
299     */
300    public Integer pop() {
301        if (!remaining.isEmpty()) {
302            Integer i = remaining.iterator().next();
303            done(i);
304            return i;
305        }
306
307        if (remainingOneway.isEmpty()) return null;
308        for (Integer i :remainingOneway.keySet()) { //find oneway, which is connected to more than one way (is between two oneway loops)
309            for (Node n : onewayReverseMap.ways.get(i)) {
310                if (onewayReverseMap.nodes.containsKey(n) && onewayReverseMap.nodes.get(n).size() > 1) {
311                    doneOneway(i);
312                    firstCircular = n;
313                    return i;
314                }
315            }
316        }
317
318        Integer i = remainingOneway.keySet().iterator().next();
319        doneOneway(i);
320        return i;
321    }
322
323    /**
324     * This relation member has been processed.
325     * Remove references in the map.nodes.
326     */
327    private void doneOneway(Integer i) {
328        Set<Node> nodesForward = remainingOneway.get(i);
329        for (Node n : nodesForward) {
330            if (onewayMap.nodes.containsKey(n)) {
331                onewayMap.nodes.get(n).remove(i);
332            }
333            if (onewayReverseMap.nodes.containsKey(n)) {
334                onewayReverseMap.nodes.get(n).remove(i);
335            }
336        }
337        remainingOneway.remove(i);
338    }
339
340    private void done(Integer i) {
341        remaining.remove(i);
342        Set<Node> nodes = map.ways.get(i);
343        for (Node n : nodes) {
344            boolean result = map.nodes.get(n).remove(i);
345            if (!result) throw new AssertionError();
346        }
347    }
348
349    public List<Integer> getNotSortableMembers() {
350        return notSortable;
351    }
352}