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