001// License: GPL. For details, see LICENSE file. 002package org.openstreetmap.josm.actions; 003 004import static org.openstreetmap.josm.gui.help.HelpUtil.ht; 005import static org.openstreetmap.josm.tools.I18n.tr; 006import static org.openstreetmap.josm.tools.I18n.trn; 007 008import java.awt.event.ActionEvent; 009import java.awt.event.KeyEvent; 010import java.util.ArrayList; 011import java.util.Collection; 012import java.util.Collections; 013import java.util.LinkedHashMap; 014import java.util.LinkedHashSet; 015import java.util.LinkedList; 016import java.util.List; 017import java.util.Map; 018import java.util.Objects; 019import java.util.Set; 020import java.util.Stack; 021 022import javax.swing.JOptionPane; 023 024import org.openstreetmap.josm.Main; 025import org.openstreetmap.josm.command.ChangeCommand; 026import org.openstreetmap.josm.command.Command; 027import org.openstreetmap.josm.command.DeleteCommand; 028import org.openstreetmap.josm.command.SequenceCommand; 029import org.openstreetmap.josm.corrector.ReverseWayTagCorrector; 030import org.openstreetmap.josm.data.osm.Node; 031import org.openstreetmap.josm.data.osm.OsmPrimitive; 032import org.openstreetmap.josm.data.osm.TagCollection; 033import org.openstreetmap.josm.data.osm.Way; 034import org.openstreetmap.josm.data.preferences.BooleanProperty; 035import org.openstreetmap.josm.gui.ExtendedDialog; 036import org.openstreetmap.josm.gui.Notification; 037import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog; 038import org.openstreetmap.josm.gui.util.GuiHelper; 039import org.openstreetmap.josm.tools.Pair; 040import org.openstreetmap.josm.tools.Shortcut; 041import org.openstreetmap.josm.tools.UserCancelException; 042 043/** 044 * Combines multiple ways into one. 045 * @since 213 046 */ 047public class CombineWayAction extends JosmAction { 048 049 private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true); 050 051 /** 052 * Constructs a new {@code CombineWayAction}. 053 */ 054 public CombineWayAction() { 055 super(tr("Combine Way"), "combineway", tr("Combine several ways into one."), 056 Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.DIRECT), true); 057 putValue("help", ht("/Action/CombineWay")); 058 } 059 060 protected static boolean confirmChangeDirectionOfWays() { 061 ExtendedDialog ed = new ExtendedDialog(Main.parent, 062 tr("Change directions?"), 063 new String[] {tr("Reverse and Combine"), tr("Cancel")}); 064 ed.setButtonIcons(new String[] {"wayflip", "cancel"}); 065 ed.setContent(tr("The ways can not be combined in their current directions. " 066 + "Do you want to reverse some of them?")); 067 ed.toggleEnable("combineway-reverse"); 068 ed.showDialog(); 069 return ed.getValue() == 1; 070 } 071 072 protected static void warnCombiningImpossible() { 073 String msg = tr("Could not combine ways<br>" 074 + "(They could not be merged into a single string of nodes)"); 075 new Notification(msg) 076 .setIcon(JOptionPane.INFORMATION_MESSAGE) 077 .show(); 078 return; 079 } 080 081 protected static Way getTargetWay(Collection<Way> combinedWays) { 082 // init with an arbitrary way 083 Way targetWay = combinedWays.iterator().next(); 084 085 // look for the first way already existing on 086 // the server 087 for (Way w : combinedWays) { 088 targetWay = w; 089 if (!w.isNew()) { 090 break; 091 } 092 } 093 return targetWay; 094 } 095 096 /** 097 * Combine multiple ways into one. 098 * @param ways the way to combine to one way 099 * @return null if ways cannot be combined. Otherwise returns the combined ways and the commands to combine 100 * @throws UserCancelException if the user cancelled a dialog. 101 */ 102 public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException { 103 104 // prepare and clean the list of ways to combine 105 // 106 if (ways == null || ways.isEmpty()) 107 return null; 108 ways.remove(null); // just in case - remove all null ways from the collection 109 110 // remove duplicates, preserving order 111 ways = new LinkedHashSet<>(ways); 112 113 // try to build a new way which includes all the combined ways 114 // 115 NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways); 116 List<Node> path = graph.buildSpanningPath(); 117 if (path == null) { 118 warnCombiningImpossible(); 119 return null; 120 } 121 // check whether any ways have been reversed in the process 122 // and build the collection of tags used by the ways to combine 123 // 124 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways); 125 126 final List<Command> reverseWayTagCommands = new LinkedList<>(); 127 List<Way> reversedWays = new LinkedList<>(); 128 List<Way> unreversedWays = new LinkedList<>(); 129 for (Way w: ways) { 130 // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971) 131 if (w.getNodesCount() < 2 || (path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) { 132 unreversedWays.add(w); 133 } else { 134 reversedWays.add(w); 135 } 136 } 137 // reverse path if all ways have been reversed 138 if (unreversedWays.isEmpty()) { 139 Collections.reverse(path); 140 unreversedWays = reversedWays; 141 reversedWays = null; 142 } 143 if ((reversedWays != null) && !reversedWays.isEmpty()) { 144 if (!confirmChangeDirectionOfWays()) return null; 145 // filter out ways that have no direction-dependent tags 146 unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays); 147 reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays); 148 // reverse path if there are more reversed than unreversed ways with direction-dependent tags 149 if (reversedWays.size() > unreversedWays.size()) { 150 Collections.reverse(path); 151 List<Way> tempWays = unreversedWays; 152 unreversedWays = reversedWays; 153 reversedWays = tempWays; 154 } 155 // if there are still reversed ways with direction-dependent tags, reverse their tags 156 if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) { 157 List<Way> unreversedTagWays = new ArrayList<>(ways); 158 unreversedTagWays.removeAll(reversedWays); 159 ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector(); 160 List<Way> reversedTagWays = new ArrayList<>(reversedWays.size()); 161 for (Way w : reversedWays) { 162 Way wnew = new Way(w); 163 reversedTagWays.add(wnew); 164 reverseWayTagCommands.addAll(reverseWayTagCorrector.execute(w, wnew)); 165 } 166 if (!reverseWayTagCommands.isEmpty()) { 167 // commands need to be executed for CombinePrimitiveResolverDialog 168 Main.main.undoRedo.add(new SequenceCommand(tr("Reverse Ways"), reverseWayTagCommands)); 169 } 170 wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays); 171 wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays)); 172 } 173 } 174 175 // create the new way and apply the new node list 176 // 177 Way targetWay = getTargetWay(ways); 178 Way modifiedTargetWay = new Way(targetWay); 179 modifiedTargetWay.setNodes(path); 180 181 final List<Command> resolution; 182 try { 183 resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay)); 184 } finally { 185 if (!reverseWayTagCommands.isEmpty()) { 186 // undo reverseWayTagCorrector and merge into SequenceCommand below 187 Main.main.undoRedo.undo(); 188 } 189 } 190 191 List<Command> cmds = new LinkedList<>(); 192 List<Way> deletedWays = new LinkedList<>(ways); 193 deletedWays.remove(targetWay); 194 195 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay)); 196 cmds.addAll(reverseWayTagCommands); 197 cmds.addAll(resolution); 198 cmds.add(new DeleteCommand(deletedWays)); 199 final Command sequenceCommand = new SequenceCommand(/* for correct i18n of plural forms - see #9110 */ 200 trn("Combine {0} way", "Combine {0} ways", ways.size(), ways.size()), cmds); 201 202 return new Pair<>(targetWay, sequenceCommand); 203 } 204 205 @Override 206 public void actionPerformed(ActionEvent event) { 207 if (getCurrentDataSet() == null) 208 return; 209 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected(); 210 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class); 211 if (selectedWays.size() < 2) { 212 new Notification( 213 tr("Please select at least two ways to combine.")) 214 .setIcon(JOptionPane.INFORMATION_MESSAGE) 215 .setDuration(Notification.TIME_SHORT) 216 .show(); 217 return; 218 } 219 // combine and update gui 220 Pair<Way, Command> combineResult; 221 try { 222 combineResult = combineWaysWorker(selectedWays); 223 } catch (UserCancelException ex) { 224 return; 225 } 226 227 if (combineResult == null) 228 return; 229 final Way selectedWay = combineResult.a; 230 Main.main.undoRedo.add(combineResult.b); 231 if (selectedWay != null) { 232 Runnable guiTask = new Runnable() { 233 @Override 234 public void run() { 235 getCurrentDataSet().setSelected(selectedWay); 236 } 237 }; 238 GuiHelper.runInEDT(guiTask); 239 } 240 } 241 242 @Override 243 protected void updateEnabledState() { 244 if (getCurrentDataSet() == null) { 245 setEnabled(false); 246 return; 247 } 248 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected(); 249 updateEnabledState(selection); 250 } 251 252 @Override 253 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) { 254 int numWays = 0; 255 for (OsmPrimitive osm : selection) { 256 if (osm instanceof Way) { 257 numWays++; 258 } 259 } 260 setEnabled(numWays >= 2); 261 } 262 263 /** 264 * A pair of nodes. 265 */ 266 public static class NodePair { 267 private final Node a; 268 private final Node b; 269 270 /** 271 * Constructs a new {@code NodePair}. 272 * @param a The first node 273 * @param b The second node 274 */ 275 public NodePair(Node a, Node b) { 276 this.a = a; 277 this.b = b; 278 } 279 280 /** 281 * Constructs a new {@code NodePair}. 282 * @param pair An existing {@code Pair} of nodes 283 */ 284 public NodePair(Pair<Node, Node> pair) { 285 this(pair.a, pair.b); 286 } 287 288 /** 289 * Constructs a new {@code NodePair}. 290 * @param other An existing {@code NodePair} 291 */ 292 public NodePair(NodePair other) { 293 this(other.a, other.b); 294 } 295 296 /** 297 * Replies the first node. 298 * @return The first node 299 */ 300 public Node getA() { 301 return a; 302 } 303 304 /** 305 * Replies the second node 306 * @return The second node 307 */ 308 public Node getB() { 309 return b; 310 } 311 312 public boolean isAdjacentToA(NodePair other) { 313 return other.getA() == a || other.getB() == a; 314 } 315 316 public boolean isAdjacentToB(NodePair other) { 317 return other.getA() == b || other.getB() == b; 318 } 319 320 public boolean isSuccessorOf(NodePair other) { 321 return other.getB() == a; 322 } 323 324 public boolean isPredecessorOf(NodePair other) { 325 return b == other.getA(); 326 } 327 328 public NodePair swap() { 329 return new NodePair(b, a); 330 } 331 332 @Override 333 public String toString() { 334 return new StringBuilder() 335 .append('[') 336 .append(a.getId()) 337 .append(',') 338 .append(b.getId()) 339 .append(']') 340 .toString(); 341 } 342 343 /** 344 * Determines if this pair contains the given node. 345 * @param n The node to look for 346 * @return {@code true} if {@code n} is in the pair, {@code false} otherwise 347 */ 348 public boolean contains(Node n) { 349 return a == n || b == n; 350 } 351 352 @Override 353 public int hashCode() { 354 return Objects.hash(a, b); 355 } 356 357 @Override 358 public boolean equals(Object obj) { 359 if (this == obj) return true; 360 if (obj == null || getClass() != obj.getClass()) return false; 361 NodePair nodePair = (NodePair) obj; 362 return Objects.equals(a, nodePair.a) && 363 Objects.equals(b, nodePair.b); 364 } 365 } 366 367 public static class NodeGraph { 368 public static List<NodePair> buildNodePairs(Way way, boolean directed) { 369 List<NodePair> pairs = new ArrayList<>(); 370 for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) { 371 pairs.add(new NodePair(pair)); 372 if (!directed) { 373 pairs.add(new NodePair(pair).swap()); 374 } 375 } 376 return pairs; 377 } 378 379 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) { 380 List<NodePair> pairs = new ArrayList<>(); 381 for (Way w: ways) { 382 pairs.addAll(buildNodePairs(w, directed)); 383 } 384 return pairs; 385 } 386 387 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) { 388 List<NodePair> cleaned = new ArrayList<>(); 389 for (NodePair p: pairs) { 390 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) { 391 cleaned.add(p); 392 } 393 } 394 return cleaned; 395 } 396 397 public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) { 398 NodeGraph graph = new NodeGraph(); 399 for (NodePair pair: pairs) { 400 graph.add(pair); 401 } 402 return graph; 403 } 404 405 public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) { 406 NodeGraph graph = new NodeGraph(); 407 for (Way w: ways) { 408 graph.add(buildNodePairs(w, true /* directed */)); 409 } 410 return graph; 411 } 412 413 /** 414 * Create an undirected graph from the given node pairs. 415 * @param pairs Node pairs to build the graph from 416 * @return node graph structure 417 */ 418 public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) { 419 NodeGraph graph = new NodeGraph(); 420 for (NodePair pair: pairs) { 421 graph.add(pair); 422 graph.add(pair.swap()); 423 } 424 return graph; 425 } 426 427 /** 428 * Create an undirected graph from the given ways, but prevent reversing of all 429 * non-new ways by fix one direction. 430 * @param ways Ways to build the graph from 431 * @return node graph structure 432 * @since 8181 433 */ 434 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) { 435 NodeGraph graph = new NodeGraph(); 436 for (Way w: ways) { 437 graph.add(buildNodePairs(w, false /* undirected */)); 438 } 439 return graph; 440 } 441 442 public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) { 443 boolean dir = true; 444 NodeGraph graph = new NodeGraph(); 445 for (Way w: ways) { 446 if (!w.isNew()) { 447 /* let the first non-new way give the direction (see #5880) */ 448 graph.add(buildNodePairs(w, dir)); 449 dir = false; 450 } else { 451 graph.add(buildNodePairs(w, false /* undirected */)); 452 } 453 } 454 return graph; 455 } 456 457 private final Set<NodePair> edges; 458 private int numUndirectedEges; 459 private Map<Node, List<NodePair>> successors; 460 private Map<Node, List<NodePair>> predecessors; 461 462 protected void rememberSuccessor(NodePair pair) { 463 if (successors.containsKey(pair.getA())) { 464 if (!successors.get(pair.getA()).contains(pair)) { 465 successors.get(pair.getA()).add(pair); 466 } 467 } else { 468 List<NodePair> l = new ArrayList<>(); 469 l.add(pair); 470 successors.put(pair.getA(), l); 471 } 472 } 473 474 protected void rememberPredecessors(NodePair pair) { 475 if (predecessors.containsKey(pair.getB())) { 476 if (!predecessors.get(pair.getB()).contains(pair)) { 477 predecessors.get(pair.getB()).add(pair); 478 } 479 } else { 480 List<NodePair> l = new ArrayList<>(); 481 l.add(pair); 482 predecessors.put(pair.getB(), l); 483 } 484 } 485 486 protected boolean isTerminalNode(Node n) { 487 if (successors.get(n) == null) return false; 488 if (successors.get(n).size() != 1) return false; 489 if (predecessors.get(n) == null) return true; 490 if (predecessors.get(n).size() == 1) { 491 NodePair p1 = successors.get(n).get(0); 492 NodePair p2 = predecessors.get(n).get(0); 493 return p1.equals(p2.swap()); 494 } 495 return false; 496 } 497 498 protected void prepare() { 499 Set<NodePair> undirectedEdges = new LinkedHashSet<>(); 500 successors = new LinkedHashMap<>(); 501 predecessors = new LinkedHashMap<>(); 502 503 for (NodePair pair: edges) { 504 if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) { 505 undirectedEdges.add(pair); 506 } 507 rememberSuccessor(pair); 508 rememberPredecessors(pair); 509 } 510 numUndirectedEges = undirectedEdges.size(); 511 } 512 513 /** 514 * Constructs a new {@code NodeGraph}. 515 */ 516 public NodeGraph() { 517 edges = new LinkedHashSet<>(); 518 } 519 520 public void add(NodePair pair) { 521 if (!edges.contains(pair)) { 522 edges.add(pair); 523 } 524 } 525 526 public void add(List<NodePair> pairs) { 527 for (NodePair pair: pairs) { 528 add(pair); 529 } 530 } 531 532 protected Set<Node> getTerminalNodes() { 533 Set<Node> ret = new LinkedHashSet<>(); 534 for (Node n: getNodes()) { 535 if (isTerminalNode(n)) { 536 ret.add(n); 537 } 538 } 539 return ret; 540 } 541 542 protected List<NodePair> getOutboundPairs(NodePair pair) { 543 return getOutboundPairs(pair.getB()); 544 } 545 546 protected List<NodePair> getOutboundPairs(Node node) { 547 List<NodePair> l = successors.get(node); 548 if (l == null) 549 return Collections.emptyList(); 550 return l; 551 } 552 553 protected Set<Node> getNodes() { 554 Set<Node> nodes = new LinkedHashSet<>(2 * edges.size()); 555 for (NodePair pair: edges) { 556 nodes.add(pair.getA()); 557 nodes.add(pair.getB()); 558 } 559 return nodes; 560 } 561 562 protected boolean isSpanningWay(Stack<NodePair> way) { 563 return numUndirectedEges == way.size(); 564 } 565 566 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) { 567 List<Node> ret = new LinkedList<>(); 568 for (NodePair pair: path) { 569 ret.add(pair.getA()); 570 } 571 ret.add(path.peek().getB()); 572 return ret; 573 } 574 575 /** 576 * Tries to find a spanning path starting from node <code>startNode</code>. 577 * 578 * Traverses the path in depth-first order. 579 * 580 * @param startNode the start node 581 * @return the spanning path; null, if no path is found 582 */ 583 protected List<Node> buildSpanningPath(Node startNode) { 584 if (startNode == null) 585 return null; 586 Stack<NodePair> path = new Stack<>(); 587 Stack<NodePair> nextPairs = new Stack<>(); 588 nextPairs.addAll(getOutboundPairs(startNode)); 589 while (!nextPairs.isEmpty()) { 590 NodePair cur = nextPairs.pop(); 591 if (!path.contains(cur) && !path.contains(cur.swap())) { 592 while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) { 593 path.pop(); 594 } 595 path.push(cur); 596 if (isSpanningWay(path)) return buildPathFromNodePairs(path); 597 nextPairs.addAll(getOutboundPairs(path.peek())); 598 } 599 } 600 return null; 601 } 602 603 /** 604 * Tries to find a path through the graph which visits each edge (i.e. 605 * the segment of a way) exactly once. 606 * 607 * @return the path; null, if no path was found 608 */ 609 public List<Node> buildSpanningPath() { 610 prepare(); 611 // try to find a path from each "terminal node", i.e. from a 612 // node which is connected by exactly one undirected edges (or 613 // two directed edges in opposite direction) to the graph. A 614 // graph built up from way segments is likely to include such 615 // nodes, unless all ways are closed. 616 // In the worst case this loops over all nodes which is very slow for large ways. 617 // 618 Set<Node> nodes = getTerminalNodes(); 619 nodes = nodes.isEmpty() ? getNodes() : nodes; 620 for (Node n: nodes) { 621 List<Node> path = buildSpanningPath(n); 622 if (path != null) 623 return path; 624 } 625 return null; 626 } 627 } 628}