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        map.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i);
111        map.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n);
112    }
113
114    private void addNodeWayMap(Node n, int i) {
115        onewayMap.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i);
116    }
117
118    private void addWayNodeMap(Node n, int i) {
119        onewayMap.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n);
120    }
121
122    private void addNodeWayMapReverse(Node n, int i) {
123        onewayReverseMap.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i);
124    }
125
126    private void addWayNodeMapReverse(Node n, int i) {
127        onewayReverseMap.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n);
128    }
129
130    private void addRemainingForward(Node n, int i) {
131        remainingOneway.computeIfAbsent(i, k -> new TreeSet<>()).add(n);
132    }
133
134    private Integer firstOneway;
135    private Node lastOnewayNode;
136    private Node firstCircular;
137
138    /**
139     * Return a relation member that is linked to the member 'i', but has not been popped yet.
140     * Return null if there is no such member left.
141     * @param way way key
142     * @return a relation member that is linked to the member 'i', but has not been popped yet
143     */
144    public Integer popAdjacent(Integer way) {
145        if (lastOnewayNode != null) return popBackwardOnewayPart(way);
146        if (firstOneway != null) return popForwardOnewayPart(way);
147
148        if (map.ways.containsKey(way)) {
149            for (Node n : map.ways.get(way)) {
150                Integer i = deleteAndGetAdjacentNode(map, n);
151                if (i != null) return i;
152
153                Integer j = deleteAndGetAdjacentNode(onewayMap, n);
154                if (j != null) {
155                    firstOneway = j;
156                    return j;
157                }
158            }
159        }
160
161        firstOneway = way;
162        return popForwardOnewayPart(way);
163    }
164
165    private Integer popForwardOnewayPart(Integer way) {
166        if (onewayMap.ways.containsKey(way)) {
167            for (Node n : onewayMap.ways.get(way)) {
168                Integer i = findAdjacentWay(onewayMap, n);
169                if (i == null) {
170                    continue;
171                }
172
173                lastOnewayNode = processBackwardIfEndOfLoopReached(i);
174                if (lastOnewayNode != null)
175                    return popBackwardOnewayPart(firstOneway);
176
177                deleteWayNode(onewayMap, i, n);
178                return i;
179            }
180        }
181
182        firstOneway = null;
183        return null;
184    }
185
186    private Node processBackwardIfEndOfLoopReached(Integer way) { //find if we didn't reach end of the loop (and process backward part)
187        if (onewayReverseMap.ways.containsKey(way)) {
188            for (Node n : onewayReverseMap.ways.get(way)) {
189                if ((map.nodes.containsKey(n))
190                        || (onewayMap.nodes.containsKey(n) && onewayMap.nodes.get(n).size() > 1))
191                    return n;
192                if (firstCircular != null && firstCircular == n)
193                    return firstCircular;
194            }
195        }
196        return null;
197    }
198
199    private Integer popBackwardOnewayPart(int way) {
200        if (lastOnewayNode != null) {
201            Set<Node> nodes = new TreeSet<>();
202            if (onewayReverseMap.ways.containsKey(way)) {
203                nodes.addAll(onewayReverseMap.ways.get(way));
204            }
205            if (map.ways.containsKey(way)) {
206                nodes.addAll(map.ways.get(way));
207            }
208            for (Node n : nodes) {
209                if (n == lastOnewayNode) { //if oneway part ends
210                    firstOneway = null;
211                    lastOnewayNode = null;
212                    Integer j = deleteAndGetAdjacentNode(map, n);
213                    if (j != null) return j;
214
215                    Integer k = deleteAndGetAdjacentNode(onewayMap, n);
216                    if (k != null) {
217                        firstOneway = k;
218                        return k;
219                    }
220                }
221
222                Integer j = deleteAndGetAdjacentNode(onewayReverseMap, n);
223                if (j != null) return j;
224            }
225        }
226
227        firstOneway = null;
228        lastOnewayNode = null;
229
230        return null;
231    }
232
233    /**
234     * find next node in nw NodeWays structure, if the node is found delete and return it
235     * @param nw nodes and ways
236     * @param n node
237     * @return node next to n
238     */
239    private Integer deleteAndGetAdjacentNode(NodesWays nw, Node n) {
240        Integer j = findAdjacentWay(nw, n);
241        if (j == null) return null;
242        deleteWayNode(nw, j, n);
243        return j;
244    }
245
246    private static Integer findAdjacentWay(NodesWays nw, Node n) {
247        Set<Integer> adj = nw.nodes.get(n);
248        if (adj == null || adj.isEmpty()) return null;
249        return adj.iterator().next();
250    }
251
252    private void deleteWayNode(NodesWays nw, Integer way, Node n) {
253        if (nw.oneWay) {
254            doneOneway(way);
255        } else {
256            done(way);
257        }
258        nw.ways.get(way).remove(n);
259    }
260
261    /**
262     * Returns some remaining member or null if every sortable member has been processed.
263     * @return member key
264     */
265    public Integer pop() {
266        if (!remaining.isEmpty()) {
267            Integer i = remaining.iterator().next();
268            done(i);
269            return i;
270        }
271
272        if (remainingOneway.isEmpty()) return null;
273        for (Integer i : remainingOneway.keySet()) { //find oneway, which is connected to more than one way (is between two oneway loops)
274            for (Node n : onewayReverseMap.ways.get(i)) {
275                if (onewayReverseMap.nodes.containsKey(n) && onewayReverseMap.nodes.get(n).size() > 1) {
276                    doneOneway(i);
277                    firstCircular = n;
278                    return i;
279                }
280            }
281        }
282
283        Integer i = remainingOneway.keySet().iterator().next();
284        doneOneway(i);
285        return i;
286    }
287
288    /**
289     * This relation member has been processed.
290     * Remove references in the map.nodes.
291     * @param i member key
292     */
293    private void doneOneway(Integer i) {
294        Set<Node> nodesForward = remainingOneway.get(i);
295        for (Node n : nodesForward) {
296            if (onewayMap.nodes.containsKey(n)) {
297                onewayMap.nodes.get(n).remove(i);
298            }
299            if (onewayReverseMap.nodes.containsKey(n)) {
300                onewayReverseMap.nodes.get(n).remove(i);
301            }
302        }
303        remainingOneway.remove(i);
304    }
305
306    private void done(Integer i) {
307        remaining.remove(i);
308        Set<Node> nodes = map.ways.get(i);
309        for (Node n : nodes) {
310            boolean result = map.nodes.get(n).remove(i);
311            if (!result) throw new AssertionError();
312        }
313    }
314
315    public List<Integer> getNotSortableMembers() {
316        return notSortable;
317    }
318}