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