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 }