source: josm/trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationNodeMap.java @ 14030

Last change on this file since 14030 was 14030, checked in by michael2402, 8 months ago

See #16388: Fix Checkstyle / Test issues.

  • Property svn:eol-style set to native
File size: 10.8 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.gui.dialogs.relation.sort;
3
4import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.NONE;
5
6import java.util.ArrayList;
7import java.util.List;
8import java.util.Map;
9import java.util.Set;
10import java.util.TreeMap;
11import java.util.TreeSet;
12
13import org.openstreetmap.josm.data.osm.Node;
14import org.openstreetmap.josm.data.osm.RelationMember;
15import org.openstreetmap.josm.data.osm.Way;
16
17/**
18 * Auxiliary class for relation sorting.
19 *
20 * Constructs two mappings: One that maps each way to its nodes and the inverse mapping that
21 * maps each node to all ways that have this node.
22 * After construction both maps are consistent, but later on objects that are no longer needed
23 * are removed from the value sets.
24 * However the corresponding keys are not deleted even if they map to an empty set.
25 * Note that normal ways have 2 nodes (beginning and end) but roundabouts can have less or more
26 * (that are shared by other members).
27 *
28 * @author Christiaan Welvaart <cjw@time4t.net>
29 * @since 1785
30 */
31public class RelationNodeMap {
32
33    private static final String ROLE_BACKWARD = "backward";
34
35    private static class NodesWays {
36        public final Map<Node, Set<Integer>> nodes = new TreeMap<>();
37        public final Map<Integer, Set<Node>> ways = new TreeMap<>();
38        public final boolean oneWay;
39
40        NodesWays(boolean oneWay) {
41            this.oneWay = oneWay;
42        }
43    }
44
45    /*
46     * the maps. (Need TreeMap for efficiency.)
47     */
48    private final NodesWays map = new NodesWays(false);
49    /*
50     * Maps for oneways (forward/backward roles)
51     */
52
53    private final NodesWays onewayMap = new NodesWays(true);
54    private final NodesWays onewayReverseMap = new NodesWays(true);
55    /*
56     * Used to keep track of what members are done.
57     */
58    private final Set<Integer> remaining = new TreeSet<>();
59    private final Map<Integer, Set<Node>> remainingOneway = new TreeMap<>();
60
61    /**
62     * All members that are incomplete or not a way
63     */
64    private final List<Integer> notSortable = new ArrayList<>();
65
66    /**
67     * Gets the start node of the member, respecting the direction role.
68     * @param m The relation member.
69     * @return <code>null</code> if the member is no way, the node otherwise.
70     */
71    public static Node firstOnewayNode(RelationMember m) {
72        if (!m.isWay()) return null;
73        if (ROLE_BACKWARD.equals(m.getRole())) {
74            return m.getWay().lastNode();
75        }
76        return m.getWay().firstNode();
77    }
78
79    /**
80     * Gets the end node of the member, respecting the direction role.
81     * @param m The relation member.
82     * @return <code>null</code> if the member is no way, the node otherwise.
83     */
84    public static Node lastOnewayNode(RelationMember m) {
85        if (!m.isWay()) return null;
86        if (ROLE_BACKWARD.equals(m.getRole())) {
87            return m.getWay().firstNode();
88        }
89        return m.getWay().lastNode();
90    }
91
92    RelationNodeMap(List<RelationMember> members) {
93        for (int i = 0; i < members.size(); ++i) {
94            RelationMember m = members.get(i);
95            if (m.getMember().isIncomplete() || !m.isWay() || m.getWay().getNodesCount() < 2) {
96                notSortable.add(i);
97                continue;
98            }
99
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}
Note: See TracBrowser for help on using the repository browser.