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