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