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