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