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.HashSet; 014import java.util.LinkedHashMap; 015import java.util.LinkedHashSet; 016import java.util.LinkedList; 017import java.util.List; 018import java.util.Map; 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.corrector.UserCancelException; 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; 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 * @param ways 098 * @return null if ways cannot be combined. Otherwise returns the combined 099 * ways and the commands to combine 100 * @throws UserCancelException 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 114 // ways 115 // 116 NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(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 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 Collection<Command> changePropertyCommands = null; 162 for (Way w : reversedWays) { 163 Way wnew = new Way(w); 164 reversedTagWays.add(wnew); 165 changePropertyCommands = reverseWayTagCorrector.execute(w, wnew); 166 } 167 if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) { 168 for (Command c : changePropertyCommands) { 169 c.executeCommand(); 170 } 171 } 172 wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays); 173 wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays)); 174 } 175 } 176 177 // create the new way and apply the new node list 178 // 179 Way targetWay = getTargetWay(ways); 180 Way modifiedTargetWay = new Way(targetWay); 181 modifiedTargetWay.setNodes(path); 182 183 List<Command> resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay)); 184 185 LinkedList<Command> cmds = new LinkedList<>(); 186 LinkedList<Way> deletedWays = new LinkedList<>(ways); 187 deletedWays.remove(targetWay); 188 189 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay)); 190 cmds.addAll(resolution); 191 cmds.add(new DeleteCommand(deletedWays)); 192 final SequenceCommand sequenceCommand = new SequenceCommand(/* for correct i18n of plural forms - see #9110 */ 193 trn("Combine {0} way", "Combine {0} ways", ways.size(), ways.size()), cmds); 194 195 return new Pair<Way, Command>(targetWay, sequenceCommand); 196 } 197 198 @Override 199 public void actionPerformed(ActionEvent event) { 200 if (getCurrentDataSet() == null) 201 return; 202 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected(); 203 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class); 204 if (selectedWays.size() < 2) { 205 new Notification( 206 tr("Please select at least two ways to combine.")) 207 .setIcon(JOptionPane.INFORMATION_MESSAGE) 208 .setDuration(Notification.TIME_SHORT) 209 .show(); 210 return; 211 } 212 // combine and update gui 213 Pair<Way, Command> combineResult; 214 try { 215 combineResult = combineWaysWorker(selectedWays); 216 } catch (UserCancelException ex) { 217 return; 218 } 219 220 if (combineResult == null) 221 return; 222 final Way selectedWay = combineResult.a; 223 Main.main.undoRedo.add(combineResult.b); 224 if(selectedWay != null) 225 { 226 Runnable guiTask = new Runnable() { 227 @Override 228 public void run() { 229 getCurrentDataSet().setSelected(selectedWay); 230 } 231 }; 232 GuiHelper.runInEDT(guiTask); 233 } 234 } 235 236 @Override 237 protected void updateEnabledState() { 238 if (getCurrentDataSet() == null) { 239 setEnabled(false); 240 return; 241 } 242 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected(); 243 updateEnabledState(selection); 244 } 245 246 @Override 247 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) { 248 int numWays = 0; 249 for (OsmPrimitive osm : selection) 250 if (osm instanceof Way) { 251 numWays++; 252 } 253 setEnabled(numWays >= 2); 254 } 255 256 /** 257 * A pair of nodes. 258 */ 259 public static class NodePair { 260 private final Node a; 261 private final Node b; 262 263 /** 264 * Constructs a new {@code NodePair}. 265 * @param a The first node 266 * @param b The second node 267 */ 268 public NodePair(Node a, Node b) { 269 this.a = a; 270 this.b = b; 271 } 272 273 /** 274 * Constructs a new {@code NodePair}. 275 * @param pair An existing {@code Pair} of nodes 276 */ 277 public NodePair(Pair<Node,Node> pair) { 278 this(pair.a, pair.b); 279 } 280 281 /** 282 * Constructs a new {@code NodePair}. 283 * @param other An existing {@code NodePair} 284 */ 285 public NodePair(NodePair other) { 286 this(other.a, other.b); 287 } 288 289 /** 290 * Replies the first node. 291 * @return The first node 292 */ 293 public Node getA() { 294 return a; 295 } 296 297 /** 298 * Replies the second node 299 * @return The second node 300 */ 301 public Node getB() { 302 return b; 303 } 304 305 public boolean isAdjacentToA(NodePair other) { 306 return other.getA() == a || other.getB() == a; 307 } 308 309 public boolean isAdjacentToB(NodePair other) { 310 return other.getA() == b || other.getB() == b; 311 } 312 313 public boolean isSuccessorOf(NodePair other) { 314 return other.getB() == a; 315 } 316 317 public boolean isPredecessorOf(NodePair other) { 318 return b == other.getA(); 319 } 320 321 public NodePair swap() { 322 return new NodePair(b,a); 323 } 324 325 @Override 326 public String toString() { 327 return new StringBuilder() 328 .append("[") 329 .append(a.getId()) 330 .append(",") 331 .append(b.getId()) 332 .append("]") 333 .toString(); 334 } 335 336 /** 337 * Determines if this pair contains the given node. 338 * @param n The node to look for 339 * @return {@code true} if {@code n} is in the pair, {@code false} otherwise 340 */ 341 public boolean contains(Node n) { 342 return a == n || b == n; 343 } 344 345 @Override 346 public int hashCode() { 347 final int prime = 31; 348 int result = 1; 349 result = prime * result + ((a == null) ? 0 : a.hashCode()); 350 result = prime * result + ((b == null) ? 0 : b.hashCode()); 351 return result; 352 } 353 354 @Override 355 public boolean equals(Object obj) { 356 if (this == obj) 357 return true; 358 if (obj == null) 359 return false; 360 if (getClass() != obj.getClass()) 361 return false; 362 NodePair other = (NodePair) obj; 363 if (a == null) { 364 if (other.a != null) 365 return false; 366 } else if (!a.equals(other.a)) 367 return false; 368 if (b == null) { 369 if (other.b != null) 370 return false; 371 } else if (!b.equals(other.b)) 372 return false; 373 return true; 374 } 375 } 376 377 public static class NodeGraph { 378 public static List<NodePair> buildNodePairs(Way way, boolean directed) { 379 List<NodePair> pairs = new ArrayList<>(); 380 for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) { 381 pairs.add(new NodePair(pair)); 382 if (!directed) { 383 pairs.add(new NodePair(pair).swap()); 384 } 385 } 386 return pairs; 387 } 388 389 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) { 390 List<NodePair> pairs = new ArrayList<>(); 391 for (Way w: ways) { 392 pairs.addAll(buildNodePairs(w, directed)); 393 } 394 return pairs; 395 } 396 397 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) { 398 List<NodePair> cleaned = new ArrayList<>(); 399 for(NodePair p: pairs) { 400 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) { 401 cleaned.add(p); 402 } 403 } 404 return cleaned; 405 } 406 407 public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) { 408 NodeGraph graph = new NodeGraph(); 409 for (NodePair pair: pairs) { 410 graph.add(pair); 411 } 412 return graph; 413 } 414 415 public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) { 416 NodeGraph graph = new NodeGraph(); 417 for (Way w: ways) { 418 graph.add(buildNodePairs(w, true /* directed */)); 419 } 420 return graph; 421 } 422 423 public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) { 424 NodeGraph graph = new NodeGraph(); 425 for (NodePair pair: pairs) { 426 graph.add(pair); 427 graph.add(pair.swap()); 428 } 429 return graph; 430 } 431 432 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) { 433 NodeGraph graph = new NodeGraph(); 434 for (Way w: ways) { 435 graph.add(buildNodePairs(w, false /* undirected */)); 436 } 437 return graph; 438 } 439 440 private Set<NodePair> edges; 441 private int numUndirectedEges = 0; 442 private Map<Node, List<NodePair>> successors; 443 private Map<Node, List<NodePair>> predecessors; 444 445 protected void rememberSuccessor(NodePair pair) { 446 if (successors.containsKey(pair.getA())) { 447 if (!successors.get(pair.getA()).contains(pair)) { 448 successors.get(pair.getA()).add(pair); 449 } 450 } else { 451 List<NodePair> l = new ArrayList<>(); 452 l.add(pair); 453 successors.put(pair.getA(), l); 454 } 455 } 456 457 protected void rememberPredecessors(NodePair pair) { 458 if (predecessors.containsKey(pair.getB())) { 459 if (!predecessors.get(pair.getB()).contains(pair)) { 460 predecessors.get(pair.getB()).add(pair); 461 } 462 } else { 463 List<NodePair> l = new ArrayList<>(); 464 l.add(pair); 465 predecessors.put(pair.getB(), l); 466 } 467 } 468 469 protected boolean isTerminalNode(Node n) { 470 if (successors.get(n) == null) return false; 471 if (successors.get(n).size() != 1) return false; 472 if (predecessors.get(n) == null) return true; 473 if (predecessors.get(n).size() == 1) { 474 NodePair p1 = successors.get(n).iterator().next(); 475 NodePair p2 = predecessors.get(n).iterator().next(); 476 return p1.equals(p2.swap()); 477 } 478 return false; 479 } 480 481 protected void prepare() { 482 Set<NodePair> undirectedEdges = new LinkedHashSet<>(); 483 successors = new LinkedHashMap<>(); 484 predecessors = new LinkedHashMap<>(); 485 486 for (NodePair pair: edges) { 487 if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) { 488 undirectedEdges.add(pair); 489 } 490 rememberSuccessor(pair); 491 rememberPredecessors(pair); 492 } 493 numUndirectedEges = undirectedEdges.size(); 494 } 495 496 /** 497 * Constructs a new {@code NodeGraph}. 498 */ 499 public NodeGraph() { 500 edges = new LinkedHashSet<>(); 501 } 502 503 public void add(NodePair pair) { 504 if (!edges.contains(pair)) { 505 edges.add(pair); 506 } 507 } 508 509 public void add(List<NodePair> pairs) { 510 for (NodePair pair: pairs) { 511 add(pair); 512 } 513 } 514 515 protected Node getStartNode() { 516 Set<Node> nodes = getNodes(); 517 for (Node n: nodes) { 518 if (successors.get(n) != null && successors.get(n).size() ==1) 519 return n; 520 } 521 return null; 522 } 523 524 protected Set<Node> getTerminalNodes() { 525 Set<Node> ret = new LinkedHashSet<>(); 526 for (Node n: getNodes()) { 527 if (isTerminalNode(n)) { 528 ret.add(n); 529 } 530 } 531 return ret; 532 } 533 534 protected Set<Node> getNodes(Stack<NodePair> pairs) { 535 HashSet<Node> nodes = new LinkedHashSet<>(2*pairs.size()); 536 for (NodePair pair: pairs) { 537 nodes.add(pair.getA()); 538 nodes.add(pair.getB()); 539 } 540 return nodes; 541 } 542 543 protected List<NodePair> getOutboundPairs(NodePair pair) { 544 return getOutboundPairs(pair.getB()); 545 } 546 547 protected List<NodePair> getOutboundPairs(Node node) { 548 List<NodePair> l = successors.get(node); 549 if (l == null) 550 return Collections.emptyList(); 551 return l; 552 } 553 554 protected Set<Node> getNodes() { 555 Set<Node> nodes = new LinkedHashSet<>(2 * edges.size()); 556 for (NodePair pair: edges) { 557 nodes.add(pair.getA()); 558 nodes.add(pair.getB()); 559 } 560 return nodes; 561 } 562 563 protected boolean isSpanningWay(Stack<NodePair> way) { 564 return numUndirectedEges == way.size(); 565 } 566 567 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) { 568 LinkedList<Node> ret = new LinkedList<>(); 569 for (NodePair pair: path) { 570 ret.add(pair.getA()); 571 } 572 ret.add(path.peek().getB()); 573 return ret; 574 } 575 576 /** 577 * Tries to find a spanning path starting from node <code>startNode</code>. 578 * 579 * Traverses the path in depth-first order. 580 * 581 * @param startNode the start node 582 * @return the spanning path; null, if no path is found 583 */ 584 protected List<Node> buildSpanningPath(Node startNode) { 585 if (startNode == null) 586 return null; 587 Stack<NodePair> path = new Stack<>(); 588 Stack<NodePair> nextPairs = new Stack<>(); 589 nextPairs.addAll(getOutboundPairs(startNode)); 590 while(!nextPairs.isEmpty()) { 591 NodePair cur= nextPairs.pop(); 592 if (! path.contains(cur) && ! path.contains(cur.swap())) { 593 while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) { 594 path.pop(); 595 } 596 path.push(cur); 597 if (isSpanningWay(path)) return buildPathFromNodePairs(path); 598 nextPairs.addAll(getOutboundPairs(path.peek())); 599 } 600 } 601 return null; 602 } 603 604 /** 605 * Tries to find a path through the graph which visits each edge (i.e. 606 * the segment of a way) exactly one. 607 * 608 * @return the path; null, if no path was found 609 */ 610 public List<Node> buildSpanningPath() { 611 prepare(); 612 // try to find a path from each "terminal node", i.e. from a 613 // node which is connected by exactly one undirected edges (or 614 // two directed edges in opposite direction) to the graph. A 615 // graph built up from way segments is likely to include such 616 // nodes, unless all ways are closed. 617 // In the worst case this loops over all nodes which is 618 // very slow for large ways. 619 // 620 Set<Node> nodes = getTerminalNodes(); 621 nodes = nodes.isEmpty() ? getNodes() : nodes; 622 for (Node n: nodes) { 623 List<Node> path = buildSpanningPath(n); 624 if (path != null) 625 return path; 626 } 627 return null; 628 } 629 } 630}