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.INode; 014import org.openstreetmap.josm.data.osm.IPrimitive; 015import org.openstreetmap.josm.data.osm.IRelationMember; 016import org.openstreetmap.josm.data.osm.IWay; 017import org.openstreetmap.josm.tools.Utils; 018 019/** 020 * Auxiliary class for relation sorting. 021 * 022 * Constructs two mappings: One that maps each way to its nodes and the inverse mapping that 023 * maps each node to all ways that have this node. 024 * After construction both maps are consistent, but later on objects that are no longer needed 025 * are removed from the value sets. 026 * However the corresponding keys are not deleted even if they map to an empty set. 027 * Note that normal ways have 2 nodes (beginning and end) but roundabouts can have less or more 028 * (that are shared by other members). 029 * 030 * @author Christiaan Welvaart <cjw@time4t.net> 031 * @param <T> The type of {@link IRelationMember} 032 * @since 1785, xxx (generics) 033 */ 034public class RelationNodeMap<T extends IRelationMember<? extends IPrimitive>> { 035 036 private static final String ROLE_BACKWARD = "backward"; 037 038 private static class NodesWays { 039 public final Map<INode, Set<Integer>> nodes = new TreeMap<>(); 040 public final Map<Integer, Set<INode>> ways = new TreeMap<>(); 041 public final boolean oneWay; 042 043 NodesWays(boolean oneWay) { 044 this.oneWay = oneWay; 045 } 046 } 047 048 /* 049 * the maps. (Need TreeMap for efficiency.) 050 */ 051 private final NodesWays map = new NodesWays(false); 052 /* 053 * Maps for oneways (forward/backward roles) 054 */ 055 056 private final NodesWays onewayMap = new NodesWays(true); 057 private final NodesWays onewayReverseMap = new NodesWays(true); 058 /* 059 * Used to keep track of what members are done. 060 */ 061 private final Set<Integer> remaining = new TreeSet<>(); 062 private final Map<Integer, Set<INode>> remainingOneway = new TreeMap<>(); 063 064 /** 065 * All members that are incomplete or not a way 066 */ 067 private final List<Integer> notSortable = new ArrayList<>(); 068 069 /** 070 * Gets the start node of the member, respecting the direction role. 071 * @param m The relation member. 072 * @return <code>null</code> if the member is no way, the node otherwise. 073 * @since 17862 (generics) 074 */ 075 public static INode firstOnewayNode(IRelationMember<?> m) { 076 if (!m.isWay()) return null; 077 if (ROLE_BACKWARD.equals(m.getRole())) { 078 return m.getWay().lastNode(); 079 } 080 return m.getWay().firstNode(); 081 } 082 083 /** 084 * Gets the end node of the member, respecting the direction role. 085 * @param m The relation member. 086 * @return <code>null</code> if the member is no way, the node otherwise. 087 */ 088 public static INode lastOnewayNode(IRelationMember<?> m) { 089 if (!m.isWay()) return null; 090 if (ROLE_BACKWARD.equals(m.getRole())) { 091 return m.getWay().firstNode(); 092 } 093 return m.getWay().lastNode(); 094 } 095 096 RelationNodeMap(List<T> members) { 097 for (int i = 0; i < members.size(); ++i) { 098 T m = members.get(i); 099 if (m.getMember().isIncomplete() || !m.isWay() || m.getWay().getNodesCount() < 2) { 100 notSortable.add(i); 101 continue; 102 } 103 104 IWay<?> w = m.getWay(); 105 if (RelationSortUtils.roundaboutType(w) != NONE) { 106 for (INode nd : w.getNodes()) { 107 addPair(nd, i); 108 } 109 } else if (RelationSortUtils.isOneway(m)) { 110 addNodeWayMap(firstOnewayNode(m), i); 111 addWayNodeMap(lastOnewayNode(m), i); 112 addNodeWayMapReverse(lastOnewayNode(m), i); 113 addWayNodeMapReverse(firstOnewayNode(m), i); 114 addRemainingForward(firstOnewayNode(m), i); 115 addRemainingForward(lastOnewayNode(m), i); 116 } else { 117 addPair(w.firstNode(), i); 118 addPair(w.lastNode(), i); 119 } 120 } 121 122 remaining.addAll(map.ways.keySet()); 123 } 124 125 private void addPair(INode n, int i) { 126 map.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i); 127 map.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n); 128 } 129 130 private void addNodeWayMap(INode n, int i) { 131 onewayMap.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i); 132 } 133 134 private void addWayNodeMap(INode n, int i) { 135 onewayMap.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n); 136 } 137 138 private void addNodeWayMapReverse(INode n, int i) { 139 onewayReverseMap.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i); 140 } 141 142 private void addWayNodeMapReverse(INode n, int i) { 143 onewayReverseMap.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n); 144 } 145 146 private void addRemainingForward(INode n, int i) { 147 remainingOneway.computeIfAbsent(i, k -> new TreeSet<>()).add(n); 148 } 149 150 private Integer firstOneway; 151 private INode lastOnewayNode; 152 private INode firstCircular; 153 154 /** 155 * Return a relation member that is linked to the member 'i', but has not been popped yet. 156 * Return null if there is no such member left. 157 * @param way way key 158 * @return a relation member that is linked to the member 'i', but has not been popped yet 159 */ 160 public Integer popAdjacent(Integer way) { 161 if (lastOnewayNode != null) return popBackwardOnewayPart(way); 162 if (firstOneway != null) return popForwardOnewayPart(way); 163 164 if (map.ways.containsKey(way)) { 165 for (INode n : map.ways.get(way)) { 166 Integer i = deleteAndGetAdjacentNode(map, n); 167 if (i != null) return i; 168 169 Integer j = deleteAndGetAdjacentNode(onewayMap, n); 170 if (j != null) { 171 firstOneway = j; 172 return j; 173 } 174 } 175 } 176 177 firstOneway = way; 178 return popForwardOnewayPart(way); 179 } 180 181 private Integer popForwardOnewayPart(Integer way) { 182 if (onewayMap.ways.containsKey(way)) { 183 INode exitNode = onewayMap.ways.get(way).iterator().next(); 184 185 if (checkIfEndOfLoopReached(exitNode)) { 186 lastOnewayNode = exitNode; 187 return popBackwardOnewayPart(firstOneway); 188 } 189 190 Integer i = deleteAndGetAdjacentNode(onewayMap, exitNode); 191 if (i != null) return i; 192 193 // When our forward route ends in a dead end try to start 194 // the backward route anyway from the split point 195 // (firstOneWay), to support routes with split a split start 196 // or end. 197 lastOnewayNode = exitNode; 198 return popBackwardOnewayPart(firstOneway); 199 } 200 201 firstOneway = null; 202 return null; 203 } 204 205 // Check if the given node can be the end of the loop (i.e. it has 206 // an outgoing bidirectional or multiple outgoing oneways, or we 207 // looped back to our first circular node) 208 private boolean checkIfEndOfLoopReached(INode n) { 209 return map.nodes.containsKey(n) 210 || (onewayMap.nodes.containsKey(n) && (onewayMap.nodes.get(n).size() > 1)) 211 || ((firstCircular != null) && (firstCircular == n)); 212 } 213 214 private Integer popBackwardOnewayPart(int way) { 215 if (lastOnewayNode != null) { 216 Set<INode> nodes = new TreeSet<>(); 217 if (onewayReverseMap.ways.containsKey(way)) { 218 nodes.addAll(onewayReverseMap.ways.get(way)); 219 } 220 if (map.ways.containsKey(way)) { 221 nodes.addAll(map.ways.get(way)); 222 } 223 for (INode n : nodes) { 224 if (n == lastOnewayNode) { //if oneway part ends 225 firstOneway = null; 226 lastOnewayNode = null; 227 Integer j = deleteAndGetAdjacentNode(map, n); 228 if (j != null) return j; 229 230 Integer k = deleteAndGetAdjacentNode(onewayMap, n); 231 if (k != null) { 232 firstOneway = k; 233 return k; 234 } 235 } 236 237 Integer j = deleteAndGetAdjacentNode(onewayReverseMap, n); 238 if (j != null) return j; 239 } 240 } 241 242 firstOneway = null; 243 lastOnewayNode = null; 244 245 return null; 246 } 247 248 /** 249 * find next node in nw NodeWays structure, if the node is found delete and return it 250 * @param nw nodes and ways 251 * @param n node 252 * @return node next to n 253 */ 254 private Integer deleteAndGetAdjacentNode(NodesWays nw, INode n) { 255 Integer j = findAdjacentWay(nw, n); 256 if (j == null) return null; 257 deleteWayNode(nw, j, n); 258 return j; 259 } 260 261 private static Integer findAdjacentWay(NodesWays nw, INode n) { 262 Set<Integer> adj = nw.nodes.get(n); 263 if (Utils.isEmpty(adj)) return null; 264 return adj.iterator().next(); 265 } 266 267 private void deleteWayNode(NodesWays nw, Integer way, INode n) { 268 if (nw.oneWay) { 269 doneOneway(way); 270 } else { 271 done(way); 272 // For bidirectional ways, remove the entry node, so 273 // subsequent lookups will only return the other node(s) as 274 // valid exit nodes. 275 nw.ways.get(way).remove(n); 276 } 277 } 278 279 /** 280 * Returns some remaining member or null if every sortable member has been processed. 281 * @return member key 282 */ 283 public Integer pop() { 284 if (!remaining.isEmpty()) { 285 Integer i = remaining.iterator().next(); 286 done(i); 287 return i; 288 } 289 290 if (remainingOneway.isEmpty()) return null; 291 for (Integer i : remainingOneway.keySet()) { //find oneway, which is connected to more than one way (is between two oneway loops) 292 for (INode n : onewayReverseMap.ways.get(i)) { 293 if (onewayReverseMap.nodes.containsKey(n) && onewayReverseMap.nodes.get(n).size() > 1) { 294 doneOneway(i); 295 firstCircular = n; 296 return i; 297 } 298 } 299 } 300 301 Integer i = remainingOneway.keySet().iterator().next(); 302 doneOneway(i); 303 return i; 304 } 305 306 /** 307 * This relation member has been processed. 308 * Remove references in the map.nodes. 309 * @param i member key 310 */ 311 private void doneOneway(Integer i) { 312 Set<INode> nodesForward = remainingOneway.get(i); 313 for (INode n : nodesForward) { 314 if (onewayMap.nodes.containsKey(n)) { 315 onewayMap.nodes.get(n).remove(i); 316 } 317 if (onewayReverseMap.nodes.containsKey(n)) { 318 onewayReverseMap.nodes.get(n).remove(i); 319 } 320 } 321 remainingOneway.remove(i); 322 } 323 324 private void done(Integer i) { 325 remaining.remove(i); 326 Set<INode> nodes = map.ways.get(i); 327 for (INode n : nodes) { 328 boolean result = map.nodes.get(n).remove(i); 329 if (!result) throw new AssertionError(); 330 } 331 } 332 333 public List<Integer> getNotSortableMembers() { 334 return notSortable; 335 } 336}