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.BACKWARD; 005import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.FORWARD; 006import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.NONE; 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.stream.Collectors; 011 012import org.openstreetmap.josm.data.osm.Node; 013import org.openstreetmap.josm.data.osm.Relation; 014import org.openstreetmap.josm.data.osm.RelationMember; 015import org.openstreetmap.josm.data.osm.Way; 016import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction; 017import org.openstreetmap.josm.tools.StreamUtils; 018import org.openstreetmap.josm.tools.bugreport.BugReport; 019 020/** 021 * This class calculates the {@link WayConnectionType} for a given list of members 022 */ 023public class WayConnectionTypeCalculator { 024 025 private static final int UNCONNECTED = Integer.MIN_VALUE; 026 027 private List<RelationMember> members; 028 029 /** 030 * refresh the cache of member WayConnectionTypes 031 * @param members relation members 032 * @return way connections 033 */ 034 public List<WayConnectionType> updateLinks(List<RelationMember> members) { 035 return updateLinks(null, members); 036 } 037 038 /** 039 * refresh the cache of member WayConnectionTypes 040 * @param r relation. Can be null, for plugins compatibility, but really shouldn't 041 * @param members relation members 042 * @return way connections 043 * @since 15696 044 */ 045 public List<WayConnectionType> updateLinks(Relation r, List<RelationMember> members) { 046 this.members = members; 047 final List<WayConnectionType> con = members.stream() 048 .map(ignore -> (WayConnectionType) null) 049 .collect(Collectors.toList()); 050 051 firstGroupIdx = 0; 052 053 lastForwardWay = UNCONNECTED; 054 lastBackwardWay = UNCONNECTED; 055 onewayBeginning = false; 056 WayConnectionType lastWct = null; 057 058 for (int i = 0; i < members.size(); ++i) { 059 try { 060 lastWct = updateLinksFor(r, con, lastWct, i); 061 } catch (RuntimeException e) { 062 int index = i; 063 throw BugReport.intercept(e).put("i", i).put("member", () -> members.get(index)).put("con", con) 064 .put("members", members).put("lastWct", lastWct).put("firstGroupIdx", firstGroupIdx); 065 } 066 } 067 if (!isSuperRoute(r)) { 068 makeLoopIfNeeded(con, members.size() - 1); 069 } 070 071 return con; 072 } 073 074 private WayConnectionType updateLinksFor(Relation r, List<WayConnectionType> con, WayConnectionType lastWct, int i) { 075 final RelationMember m = members.get(i); 076 if (isSuperRoute(r)) { 077 final WayConnectionType wct; 078 if (i == 0) { 079 wct = new WayConnectionType(false); 080 } else if (!members.get(i).isRelation() || !members.get(i - 1).isRelation()) { 081 wct = new WayConnectionType(true); 082 } else { 083 final List<RelationMember> previousMembers = members.get(i - 1).getRelation().getMembers(); 084 final Way previousLastWay = StreamUtils.reversedStream(previousMembers) 085 .filter(x -> x.isWay() && !x.hasRole()) 086 .map(RelationMember::getWay) 087 .findFirst().orElse(null); 088 final Way currentFirstWay = m.getRelation().getMembers().stream() 089 .filter(x -> x.isWay() && !x.hasRole()) 090 .map(RelationMember::getWay) 091 .findFirst().orElse(null); 092 final boolean isConnected = isConnected(previousLastWay, currentFirstWay); 093 wct = new WayConnectionType(false); 094 lastWct.linkNext = wct.linkPrev = isConnected; 095 } 096 con.set(i, wct); 097 return wct; 098 } else if (isNoHandleableWay(m)) { 099 if (i > 0) { 100 makeLoopIfNeeded(con, i-1); 101 } 102 con.set(i, new WayConnectionType()); 103 firstGroupIdx = i; 104 } else { 105 WayConnectionType wct = computeNextWayConnection(r, con, lastWct, i, m); 106 107 if (!wct.linkPrev) { 108 if (i > 0) { 109 makeLoopIfNeeded(con, i-1); 110 } 111 firstGroupIdx = i; 112 } 113 return wct; 114 } 115 return lastWct; 116 } 117 118 private static boolean isNoHandleableWay(final RelationMember m) { 119 return !m.isWay() || m.getWay() == null || m.getWay().isIncomplete(); 120 } 121 122 private WayConnectionType computeNextWayConnection(Relation r, List<WayConnectionType> con, WayConnectionType lastWct, int i, 123 final RelationMember m) { 124 WayConnectionType wct = new WayConnectionType(false); 125 wct.linkPrev = i > 0 && con.get(i-1) != null && con.get(i-1).isValid(); 126 wct.direction = NONE; 127 wct.ignoreOneway = isOnewayIgnored(r); 128 129 if (!wct.ignoreOneway && RelationSortUtils.isOneway(m)) { 130 handleOneway(lastWct, i, wct); 131 } 132 133 if (wct.linkPrev) { 134 if (lastBackwardWay != UNCONNECTED && lastForwardWay != UNCONNECTED) { 135 determineOnewayConnectionType(con, m, i, wct); 136 if (!wct.linkPrev) { 137 firstGroupIdx = i; 138 } 139 } 140 141 if (lastWct != null && !RelationSortUtils.isOneway(m)) { 142 wct.direction = determineDirection(i-1, lastWct.direction, i); 143 wct.linkPrev = wct.direction != NONE; 144 } 145 } 146 147 if (!wct.linkPrev) { 148 wct.direction = determineDirectionOfFirst(i, m, false); 149 if (RelationSortUtils.isOneway(m)) { 150 wct.isOnewayLoopForwardPart = true; 151 lastForwardWay = i; 152 } 153 } 154 155 wct.linkNext = false; 156 if (lastWct != null) { 157 lastWct.linkNext = wct.linkPrev; 158 } 159 160 if (!wct.ignoreOneway) { 161 handleOnewayFollows(lastWct, i, m, wct); 162 } 163 con.set(i, wct); 164 return wct; 165 } 166 167 private boolean isSuperRoute(Relation r) { 168 return r != null && r.hasTag("type", "superroute"); 169 } 170 171 private static boolean isOnewayIgnored(Relation r) { 172 return r != null && r.hasTag("type", "boundary", "multipolygon"); 173 } 174 175 protected void handleOnewayFollows(WayConnectionType lastWct, int i, final RelationMember m, 176 WayConnectionType wct) { 177 if (lastWct != null && i > 0 && m.getMember() instanceof Way && members.get(i - 1).getMember() instanceof Way 178 && (m.getWay().isOneway() != 0 || members.get(i - 1).getWay().isOneway() != 0)) { 179 Way way = m.getWay(); 180 Way previousWay = members.get(i - 1).getWay(); 181 if (way.isOneway() != 0 && previousWay.isOneway() != 0 && 182 (way.firstNode(true) != previousWay.lastNode(true) && 183 way.lastNode(true) != previousWay.firstNode(true))) { 184 wct.onewayFollowsPrevious = false; 185 lastWct.onewayFollowsNext = false; 186 } else if (way.isOneway() != 0 && previousWay.isOneway() == 0 && 187 previousWay.isFirstLastNode(way.lastNode(true))) { 188 wct.onewayFollowsPrevious = false; 189 } 190 } 191 } 192 193 private void handleOneway(WayConnectionType lastWct, int i, WayConnectionType wct) { 194 if (lastWct != null && lastWct.isOnewayTail) { 195 wct.isOnewayHead = true; 196 } 197 if (lastBackwardWay == UNCONNECTED && lastForwardWay == UNCONNECTED) { //Beginning of new oneway 198 wct.isOnewayHead = true; 199 lastForwardWay = i-1; 200 lastBackwardWay = i-1; 201 onewayBeginning = true; 202 } 203 } 204 205 private int firstGroupIdx; 206 private void makeLoopIfNeeded(final List<WayConnectionType> con, final int i) { 207 boolean loop = false; 208 if (i == firstGroupIdx) { //is primitive loop 209 loop = determineDirection(i, FORWARD, i) == FORWARD; 210 } else if (i >= 0) { 211 loop = determineDirection(i, con.get(i).direction, firstGroupIdx) == con.get(firstGroupIdx).direction; 212 } 213 if (loop) { 214 for (int j = firstGroupIdx; j <= i; ++j) { 215 con.get(j).isLoop = true; 216 } 217 } 218 } 219 220 private Direction determineDirectionOfFirst(final int i, final RelationMember m, boolean reversed) { 221 Direction result = RelationSortUtils.roundaboutType(m); 222 if (result != NONE) 223 return result; 224 225 if (RelationSortUtils.isOneway(m)) { 226 if (RelationSortUtils.isBackward(m) != reversed) return BACKWARD; 227 else return FORWARD; 228 } else { /** guess the direction and see if it fits with the next member */ 229 if (determineDirection(i, FORWARD, i+1) != NONE) return FORWARD; 230 if (determineDirection(i, BACKWARD, i+1) != NONE) return BACKWARD; 231 } 232 return NONE; 233 } 234 235 private int lastForwardWay; 236 private int lastBackwardWay; 237 private boolean onewayBeginning; 238 239 private void determineOnewayConnectionType(final List<WayConnectionType> con, 240 RelationMember m, int i, final WayConnectionType wct) { 241 Direction dirFW = determineDirection(lastForwardWay, con.get(lastForwardWay).direction, i); 242 Direction dirBW; 243 if (onewayBeginning) { 244 if (lastBackwardWay < 0) { 245 dirBW = determineDirection(firstGroupIdx, reverse(con.get(firstGroupIdx).direction), i, true); 246 } else { 247 dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true); 248 } 249 250 // Support split-start routes. When the current way does 251 // not fit as forward or backward and we have no backward 252 // ways yet (onewayBeginning) and the most recent oneway 253 // head starts a new segment (!linkPrev), instead of 254 // disconnecting the current way, make it the start of the 255 // backward route. To render properly, unset isOnewayHead on 256 // the most recent head (since the current backward way does 257 // no longer start there). 258 if (dirFW == NONE && dirBW == NONE && RelationSortUtils.isOneway(m) && !wct.isOnewayHead) { 259 WayConnectionType prevHead = null; 260 for (int j = i - 1; j >= 0; --j) { 261 if (con.get(j).isOnewayHead) { 262 prevHead = con.get(j); 263 break; 264 } 265 } 266 267 if (prevHead != null && !prevHead.linkPrev) { 268 dirBW = determineDirectionOfFirst(i, m, true); 269 prevHead.isOnewayHead = false; 270 } 271 } 272 273 if (dirBW != NONE) { 274 onewayBeginning = false; 275 } 276 } else { 277 dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true); 278 } 279 280 if (RelationSortUtils.isOneway(m)) { 281 if (dirBW != NONE) { 282 wct.direction = dirBW; 283 lastBackwardWay = i; 284 wct.isOnewayLoopBackwardPart = true; 285 } 286 if (dirFW != NONE) { 287 wct.direction = dirFW; 288 lastForwardWay = i; 289 wct.isOnewayLoopForwardPart = true; 290 } 291 // Not connected to previous 292 if (dirFW == NONE && dirBW == NONE) { 293 wct.linkPrev = false; 294 wct.isOnewayHead = true; 295 lastForwardWay = i-1; 296 lastBackwardWay = i-1; 297 onewayBeginning = true; 298 } 299 300 if (dirFW != NONE && dirBW != NONE) { //End of oneway loop 301 if (i+1 < members.size() && determineDirection(i, dirFW, i+1) != NONE) { 302 wct.isOnewayLoopBackwardPart = false; 303 wct.direction = dirFW; 304 } else { 305 wct.isOnewayLoopForwardPart = false; 306 wct.direction = dirBW; 307 } 308 309 wct.isOnewayTail = true; 310 } 311 312 } else { 313 lastForwardWay = UNCONNECTED; 314 lastBackwardWay = UNCONNECTED; 315 if (dirFW == NONE || dirBW == NONE) { 316 wct.linkPrev = false; 317 } 318 } 319 } 320 321 private static Direction reverse(final Direction dir) { 322 if (dir == FORWARD) return BACKWARD; 323 if (dir == BACKWARD) return FORWARD; 324 return dir; 325 } 326 327 private Direction determineDirection(int refI, Direction refDirection, int k) { 328 return determineDirection(refI, refDirection, k, false); 329 } 330 331 /** 332 * Determines the direction of way {@code k} with respect to the way {@code ref_i}. 333 * The way {@code ref_i} is assumed to have the direction {@code ref_direction} and to be the predecessor of {@code k}. 334 * 335 * If both ways are not linked in any way, NONE is returned. 336 * 337 * Else the direction is given as follows: 338 * Let the relation be a route of oneway streets, and someone travels them in the given order. 339 * Direction is FORWARD if it is legal and BACKWARD if it is illegal to do so for the given way. 340 * @param refI way key 341 * @param refDirection direction of ref_i 342 * @param k successor of ref_i 343 * @param reversed if {@code true} determine reverse direction 344 * @return direction of way {@code k} 345 */ 346 private Direction determineDirection(int refI, final Direction refDirection, int k, boolean reversed) { 347 if (members == null || refI < 0 || k < 0 || refI >= members.size() || k >= members.size() || refDirection == NONE) 348 return NONE; 349 350 final RelationMember mRef = members.get(refI); 351 final RelationMember m = members.get(k); 352 Way wayRef = null; 353 Way way = null; 354 355 if (mRef.isWay()) { 356 wayRef = mRef.getWay(); 357 } 358 if (m.isWay()) { 359 way = m.getWay(); 360 } 361 362 if (wayRef == null || way == null) 363 return NONE; 364 365 /** the list of nodes the way k can dock to */ 366 List<Node> refNodes = new ArrayList<>(); 367 368 switch (refDirection) { 369 case FORWARD: 370 refNodes.add(wayRef.lastNode()); 371 break; 372 case BACKWARD: 373 refNodes.add(wayRef.firstNode()); 374 break; 375 case ROUNDABOUT_LEFT: 376 case ROUNDABOUT_RIGHT: 377 refNodes = wayRef.getNodes(); 378 break; 379 default: // Do nothing 380 } 381 382 for (Node n : refNodes) { 383 if (n == null) { 384 continue; 385 } 386 if (RelationSortUtils.roundaboutType(members.get(k)) != NONE) { 387 for (Node nn : way.getNodes()) { 388 if (n == nn) 389 return RelationSortUtils.roundaboutType(members.get(k)); 390 } 391 } else if (RelationSortUtils.isOneway(m)) { 392 if (n == RelationNodeMap.firstOnewayNode(m) && !reversed) { 393 if (RelationSortUtils.isBackward(m)) 394 return BACKWARD; 395 else 396 return FORWARD; 397 } 398 if (reversed && n == RelationNodeMap.lastOnewayNode(m)) { 399 if (RelationSortUtils.isBackward(m)) 400 return FORWARD; 401 else 402 return BACKWARD; 403 } 404 } else { 405 if (n == way.firstNode()) 406 return FORWARD; 407 if (n == way.lastNode()) 408 return BACKWARD; 409 } 410 } 411 return NONE; 412 } 413 414 /** 415 * Free resources. 416 */ 417 public void clear() { 418 members = null; 419 } 420 421 private boolean isConnected(Way way1, Way way2) { 422 return way1 != null && way2 != null && way1.isUsable() && way2.isUsable() 423 && (way1.isFirstLastNode(way2.firstNode()) || way1.isFirstLastNode(way2.lastNode())); 424 } 425}