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 * @since 1785 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 member 'i', but has not been popped yet. 176 * Return null if there is no such member left. 177 * @param way way key 178 * @return a relation member that is linked to the member 'i', but has not been popped yet 179 */ 180 public Integer popAdjacent(Integer way) { 181 if (lastOnewayNode != null) return popBackwardOnewayPart(way); 182 if (firstOneway != null) return popForwardOnewayPart(way); 183 184 if (map.ways.containsKey(way)) { 185 for (Node n : map.ways.get(way)) { 186 Integer i = deleteAndGetAdjacentNode(map, n); 187 if (i != null) return i; 188 189 Integer j = deleteAndGetAdjacentNode(onewayMap, n); 190 if (j != null) { 191 firstOneway = j; 192 return j; 193 } 194 } 195 } 196 197 firstOneway = way; 198 return popForwardOnewayPart(way); 199 } 200 201 private Integer popForwardOnewayPart(Integer way) { 202 if (onewayMap.ways.containsKey(way)) { 203 for (Node n : onewayMap.ways.get(way)) { 204 Integer i = findAdjacentWay(onewayMap, n); 205 if (i == null) { 206 continue; 207 } 208 209 lastOnewayNode = processBackwardIfEndOfLoopReached(i); 210 if (lastOnewayNode != null) 211 return popBackwardOnewayPart(firstOneway); 212 213 deleteWayNode(onewayMap, i, n); 214 return i; 215 } 216 } 217 218 firstOneway = null; 219 return null; 220 } 221 222 private Node processBackwardIfEndOfLoopReached(Integer way) { //find if we didn't reach end of the loop (and process backward part) 223 if (onewayReverseMap.ways.containsKey(way)) { 224 for (Node n : onewayReverseMap.ways.get(way)) { 225 if ((map.nodes.containsKey(n)) 226 || (onewayMap.nodes.containsKey(n) && onewayMap.nodes.get(n).size() > 1)) 227 return n; 228 if (firstCircular != null && firstCircular == n) 229 return firstCircular; 230 } 231 } 232 return null; 233 } 234 235 private Integer popBackwardOnewayPart(int way) { 236 if (lastOnewayNode != null) { 237 Set<Node> nodes = new TreeSet<>(); 238 if (onewayReverseMap.ways.containsKey(way)) { 239 nodes.addAll(onewayReverseMap.ways.get(way)); 240 } 241 if (map.ways.containsKey(way)) { 242 nodes.addAll(map.ways.get(way)); 243 } 244 for (Node n : nodes) { 245 if (n == lastOnewayNode) { //if oneway part ends 246 firstOneway = null; 247 lastOnewayNode = null; 248 Integer j = deleteAndGetAdjacentNode(map, n); 249 if (j != null) return j; 250 251 Integer k = deleteAndGetAdjacentNode(onewayMap, n); 252 if (k != null) { 253 firstOneway = k; 254 return k; 255 } 256 } 257 258 Integer j = deleteAndGetAdjacentNode(onewayReverseMap, n); 259 if (j != null) return j; 260 } 261 } 262 263 firstOneway = null; 264 lastOnewayNode = null; 265 266 return null; 267 } 268 269 /** 270 * find next node in nw NodeWays structure, if the node is found delete and return it 271 * @param nw nodes and ways 272 * @param n node 273 * @return node next to n 274 */ 275 private Integer deleteAndGetAdjacentNode(NodesWays nw, Node n) { 276 Integer j = findAdjacentWay(nw, n); 277 if (j == null) return null; 278 deleteWayNode(nw, j, n); 279 return j; 280 } 281 282 private Integer findAdjacentWay(NodesWays nw, Node n) { 283 Set<Integer> adj = nw.nodes.get(n); 284 if (adj == null || adj.isEmpty()) return null; 285 return adj.iterator().next(); 286 } 287 288 private void deleteWayNode(NodesWays nw, Integer way, Node n) { 289 if (nw.oneWay) { 290 doneOneway(way); 291 } else { 292 done(way); 293 } 294 nw.ways.get(way).remove(n); 295 } 296 297 /** 298 * Returns some remaining member or null if every sortable member has been processed. 299 * @return member key 300 */ 301 public Integer pop() { 302 if (!remaining.isEmpty()) { 303 Integer i = remaining.iterator().next(); 304 done(i); 305 return i; 306 } 307 308 if (remainingOneway.isEmpty()) return null; 309 for (Integer i : remainingOneway.keySet()) { //find oneway, which is connected to more than one way (is between two oneway loops) 310 for (Node n : onewayReverseMap.ways.get(i)) { 311 if (onewayReverseMap.nodes.containsKey(n) && onewayReverseMap.nodes.get(n).size() > 1) { 312 doneOneway(i); 313 firstCircular = n; 314 return i; 315 } 316 } 317 } 318 319 Integer i = remainingOneway.keySet().iterator().next(); 320 doneOneway(i); 321 return i; 322 } 323 324 /** 325 * This relation member has been processed. 326 * Remove references in the map.nodes. 327 * @param i member key 328 */ 329 private void doneOneway(Integer i) { 330 Set<Node> nodesForward = remainingOneway.get(i); 331 for (Node n : nodesForward) { 332 if (onewayMap.nodes.containsKey(n)) { 333 onewayMap.nodes.get(n).remove(i); 334 } 335 if (onewayReverseMap.nodes.containsKey(n)) { 336 onewayReverseMap.nodes.get(n).remove(i); 337 } 338 } 339 remainingOneway.remove(i); 340 } 341 342 private void done(Integer i) { 343 remaining.remove(i); 344 Set<Node> nodes = map.ways.get(i); 345 for (Node n : nodes) { 346 boolean result = map.nodes.get(n).remove(i); 347 if (!result) throw new AssertionError(); 348 } 349 } 350 351 public List<Integer> getNotSortableMembers() { 352 return notSortable; 353 } 354}