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 map.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i); 111 map.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n); 112 } 113 114 private void addNodeWayMap(Node n, int i) { 115 onewayMap.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i); 116 } 117 118 private void addWayNodeMap(Node n, int i) { 119 onewayMap.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n); 120 } 121 122 private void addNodeWayMapReverse(Node n, int i) { 123 onewayReverseMap.nodes.computeIfAbsent(n, k -> new TreeSet<>()).add(i); 124 } 125 126 private void addWayNodeMapReverse(Node n, int i) { 127 onewayReverseMap.ways.computeIfAbsent(i, k -> new TreeSet<>()).add(n); 128 } 129 130 private void addRemainingForward(Node n, int i) { 131 remainingOneway.computeIfAbsent(i, k -> new TreeSet<>()).add(n); 132 } 133 134 private Integer firstOneway; 135 private Node lastOnewayNode; 136 private Node firstCircular; 137 138 /** 139 * Return a relation member that is linked to the member 'i', but has not been popped yet. 140 * Return null if there is no such member left. 141 * @param way way key 142 * @return a relation member that is linked to the member 'i', but has not been popped yet 143 */ 144 public Integer popAdjacent(Integer way) { 145 if (lastOnewayNode != null) return popBackwardOnewayPart(way); 146 if (firstOneway != null) return popForwardOnewayPart(way); 147 148 if (map.ways.containsKey(way)) { 149 for (Node n : map.ways.get(way)) { 150 Integer i = deleteAndGetAdjacentNode(map, n); 151 if (i != null) return i; 152 153 Integer j = deleteAndGetAdjacentNode(onewayMap, n); 154 if (j != null) { 155 firstOneway = j; 156 return j; 157 } 158 } 159 } 160 161 firstOneway = way; 162 return popForwardOnewayPart(way); 163 } 164 165 private Integer popForwardOnewayPart(Integer way) { 166 if (onewayMap.ways.containsKey(way)) { 167 for (Node n : onewayMap.ways.get(way)) { 168 Integer i = findAdjacentWay(onewayMap, n); 169 if (i == null) { 170 continue; 171 } 172 173 lastOnewayNode = processBackwardIfEndOfLoopReached(i); 174 if (lastOnewayNode != null) 175 return popBackwardOnewayPart(firstOneway); 176 177 deleteWayNode(onewayMap, i, n); 178 return i; 179 } 180 } 181 182 firstOneway = null; 183 return null; 184 } 185 186 private Node processBackwardIfEndOfLoopReached(Integer way) { //find if we didn't reach end of the loop (and process backward part) 187 if (onewayReverseMap.ways.containsKey(way)) { 188 for (Node n : onewayReverseMap.ways.get(way)) { 189 if ((map.nodes.containsKey(n)) 190 || (onewayMap.nodes.containsKey(n) && onewayMap.nodes.get(n).size() > 1)) 191 return n; 192 if (firstCircular != null && firstCircular == n) 193 return firstCircular; 194 } 195 } 196 return null; 197 } 198 199 private Integer popBackwardOnewayPart(int way) { 200 if (lastOnewayNode != null) { 201 Set<Node> nodes = new TreeSet<>(); 202 if (onewayReverseMap.ways.containsKey(way)) { 203 nodes.addAll(onewayReverseMap.ways.get(way)); 204 } 205 if (map.ways.containsKey(way)) { 206 nodes.addAll(map.ways.get(way)); 207 } 208 for (Node n : nodes) { 209 if (n == lastOnewayNode) { //if oneway part ends 210 firstOneway = null; 211 lastOnewayNode = null; 212 Integer j = deleteAndGetAdjacentNode(map, n); 213 if (j != null) return j; 214 215 Integer k = deleteAndGetAdjacentNode(onewayMap, n); 216 if (k != null) { 217 firstOneway = k; 218 return k; 219 } 220 } 221 222 Integer j = deleteAndGetAdjacentNode(onewayReverseMap, n); 223 if (j != null) return j; 224 } 225 } 226 227 firstOneway = null; 228 lastOnewayNode = null; 229 230 return null; 231 } 232 233 /** 234 * find next node in nw NodeWays structure, if the node is found delete and return it 235 * @param nw nodes and ways 236 * @param n node 237 * @return node next to n 238 */ 239 private Integer deleteAndGetAdjacentNode(NodesWays nw, Node n) { 240 Integer j = findAdjacentWay(nw, n); 241 if (j == null) return null; 242 deleteWayNode(nw, j, n); 243 return j; 244 } 245 246 private static Integer findAdjacentWay(NodesWays nw, Node n) { 247 Set<Integer> adj = nw.nodes.get(n); 248 if (adj == null || adj.isEmpty()) return null; 249 return adj.iterator().next(); 250 } 251 252 private void deleteWayNode(NodesWays nw, Integer way, Node n) { 253 if (nw.oneWay) { 254 doneOneway(way); 255 } else { 256 done(way); 257 } 258 nw.ways.get(way).remove(n); 259 } 260 261 /** 262 * Returns some remaining member or null if every sortable member has been processed. 263 * @return member key 264 */ 265 public Integer pop() { 266 if (!remaining.isEmpty()) { 267 Integer i = remaining.iterator().next(); 268 done(i); 269 return i; 270 } 271 272 if (remainingOneway.isEmpty()) return null; 273 for (Integer i : remainingOneway.keySet()) { //find oneway, which is connected to more than one way (is between two oneway loops) 274 for (Node n : onewayReverseMap.ways.get(i)) { 275 if (onewayReverseMap.nodes.containsKey(n) && onewayReverseMap.nodes.get(n).size() > 1) { 276 doneOneway(i); 277 firstCircular = n; 278 return i; 279 } 280 } 281 } 282 283 Integer i = remainingOneway.keySet().iterator().next(); 284 doneOneway(i); 285 return i; 286 } 287 288 /** 289 * This relation member has been processed. 290 * Remove references in the map.nodes. 291 * @param i member key 292 */ 293 private void doneOneway(Integer i) { 294 Set<Node> nodesForward = remainingOneway.get(i); 295 for (Node n : nodesForward) { 296 if (onewayMap.nodes.containsKey(n)) { 297 onewayMap.nodes.get(n).remove(i); 298 } 299 if (onewayReverseMap.nodes.containsKey(n)) { 300 onewayReverseMap.nodes.get(n).remove(i); 301 } 302 } 303 remainingOneway.remove(i); 304 } 305 306 private void done(Integer i) { 307 remaining.remove(i); 308 Set<Node> nodes = map.ways.get(i); 309 for (Node n : nodes) { 310 boolean result = map.nodes.get(n).remove(i); 311 if (!result) throw new AssertionError(); 312 } 313 } 314 315 public List<Integer> getNotSortableMembers() { 316 return notSortable; 317 } 318}