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