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}