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 }