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