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; 006 007import java.awt.event.ActionEvent; 008import java.awt.event.KeyEvent; 009import java.util.ArrayList; 010import java.util.Collection; 011import java.util.Collections; 012import java.util.HashSet; 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.corrector.UserCancelException; 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; 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.png", "cancel.png"}); 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.showDialog(); 067 return ed.getValue() == 1; 068 } 069 070 protected static void warnCombiningImpossible() { 071 String msg = tr("Could not combine ways<br>" 072 + "(They could not be merged into a single string of nodes)"); 073 new Notification(msg) 074 .setIcon(JOptionPane.INFORMATION_MESSAGE) 075 .show(); 076 return; 077 } 078 079 protected static Way getTargetWay(Collection<Way> combinedWays) { 080 // init with an arbitrary way 081 Way targetWay = combinedWays.iterator().next(); 082 083 // look for the first way already existing on 084 // the server 085 for (Way w : combinedWays) { 086 targetWay = w; 087 if (!w.isNew()) { 088 break; 089 } 090 } 091 return targetWay; 092 } 093 094 /** 095 * @param ways 096 * @return null if ways cannot be combined. Otherwise returns the combined 097 * ways and the commands to combine 098 * @throws UserCancelException 099 */ 100 public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException { 101 102 // prepare and clean the list of ways to combine 103 // 104 if (ways == null || ways.isEmpty()) 105 return null; 106 ways.remove(null); // just in case - remove all null ways from the collection 107 108 // remove duplicates, preserving order 109 ways = new LinkedHashSet<Way>(ways); 110 111 // try to build a new way which includes all the combined 112 // ways 113 // 114 NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(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<Way>(); 126 List<Way> unreversedWays = new LinkedList<Way>(); 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<Way>(ways); 156 unreversedTagWays.removeAll(reversedWays); 157 ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector(); 158 List<Way> reversedTagWays = new ArrayList<Way>(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 LinkedList<Command> cmds = new LinkedList<Command>(); 184 LinkedList<Way> deletedWays = new LinkedList<Way>(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(tr("Combine {0} ways", ways.size()), cmds); 191 192 return new Pair<Way, Command>(targetWay, sequenceCommand); 193 } 194 195 @Override 196 public void actionPerformed(ActionEvent event) { 197 if (getCurrentDataSet() == null) 198 return; 199 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected(); 200 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class); 201 if (selectedWays.size() < 2) { 202 new Notification( 203 tr("Please select at least two ways to combine.")) 204 .setIcon(JOptionPane.INFORMATION_MESSAGE) 205 .setDuration(Notification.TIME_SHORT) 206 .show(); 207 return; 208 } 209 // combine and update gui 210 Pair<Way, Command> combineResult; 211 try { 212 combineResult = combineWaysWorker(selectedWays); 213 } catch (UserCancelException ex) { 214 return; 215 } 216 217 if (combineResult == null) 218 return; 219 final Way selectedWay = combineResult.a; 220 Main.main.undoRedo.add(combineResult.b); 221 if(selectedWay != null) 222 { 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 setEnabled(numWays >= 2); 251 } 252 253 /** 254 * A pair of nodes. 255 */ 256 static public class NodePair { 257 private final Node a; 258 private final Node b; 259 260 /** 261 * Constructs a new {@code NodePair}. 262 * @param a The first node 263 * @param b The second node 264 */ 265 public NodePair(Node a, Node b) { 266 this.a = a; 267 this.b = b; 268 } 269 270 /** 271 * Constructs a new {@code NodePair}. 272 * @param pair An existing {@code Pair} of nodes 273 */ 274 public NodePair(Pair<Node,Node> pair) { 275 this(pair.a, pair.b); 276 } 277 278 /** 279 * Constructs a new {@code NodePair}. 280 * @param other An existing {@code NodePair} 281 */ 282 public NodePair(NodePair other) { 283 this(other.a, other.b); 284 } 285 286 /** 287 * Replies the first node. 288 * @return The first node 289 */ 290 public Node getA() { 291 return a; 292 } 293 294 /** 295 * Replies the second node 296 * @return The second node 297 */ 298 public Node getB() { 299 return b; 300 } 301 302 public boolean isAdjacentToA(NodePair other) { 303 return other.getA() == a || other.getB() == a; 304 } 305 306 public boolean isAdjacentToB(NodePair other) { 307 return other.getA() == b || other.getB() == b; 308 } 309 310 public boolean isSuccessorOf(NodePair other) { 311 return other.getB() == a; 312 } 313 314 public boolean isPredecessorOf(NodePair other) { 315 return b == other.getA(); 316 } 317 318 public NodePair swap() { 319 return new NodePair(b,a); 320 } 321 322 @Override 323 public String toString() { 324 return new StringBuilder() 325 .append("[") 326 .append(a.getId()) 327 .append(",") 328 .append(b.getId()) 329 .append("]") 330 .toString(); 331 } 332 333 /** 334 * Determines if this pair contains the given node. 335 * @param n The node to look for 336 * @return {@code true} if {@code n} is in the pair, {@code false} otherwise 337 */ 338 public boolean contains(Node n) { 339 return a == n || b == n; 340 } 341 342 @Override 343 public int hashCode() { 344 final int prime = 31; 345 int result = 1; 346 result = prime * result + ((a == null) ? 0 : a.hashCode()); 347 result = prime * result + ((b == null) ? 0 : b.hashCode()); 348 return result; 349 } 350 351 @Override 352 public boolean equals(Object obj) { 353 if (this == obj) 354 return true; 355 if (obj == null) 356 return false; 357 if (getClass() != obj.getClass()) 358 return false; 359 NodePair other = (NodePair) obj; 360 if (a == null) { 361 if (other.a != null) 362 return false; 363 } else if (!a.equals(other.a)) 364 return false; 365 if (b == null) { 366 if (other.b != null) 367 return false; 368 } else if (!b.equals(other.b)) 369 return false; 370 return true; 371 } 372 } 373 374 static public class NodeGraph { 375 static public List<NodePair> buildNodePairs(Way way, boolean directed) { 376 List<NodePair> pairs = new ArrayList<NodePair>(); 377 for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) { 378 pairs.add(new NodePair(pair)); 379 if (!directed) { 380 pairs.add(new NodePair(pair).swap()); 381 } 382 } 383 return pairs; 384 } 385 386 static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) { 387 List<NodePair> pairs = new ArrayList<NodePair>(); 388 for (Way w: ways) { 389 pairs.addAll(buildNodePairs(w, directed)); 390 } 391 return pairs; 392 } 393 394 static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) { 395 List<NodePair> cleaned = new ArrayList<NodePair>(); 396 for(NodePair p: pairs) { 397 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) { 398 cleaned.add(p); 399 } 400 } 401 return cleaned; 402 } 403 404 static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) { 405 NodeGraph graph = new NodeGraph(); 406 for (NodePair pair: pairs) { 407 graph.add(pair); 408 } 409 return graph; 410 } 411 412 static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) { 413 NodeGraph graph = new NodeGraph(); 414 for (Way w: ways) { 415 graph.add(buildNodePairs(w, true /* directed */)); 416 } 417 return graph; 418 } 419 420 static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) { 421 NodeGraph graph = new NodeGraph(); 422 for (NodePair pair: pairs) { 423 graph.add(pair); 424 graph.add(pair.swap()); 425 } 426 return graph; 427 } 428 429 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) { 430 NodeGraph graph = new NodeGraph(); 431 for (Way w: ways) { 432 graph.add(buildNodePairs(w, false /* undirected */)); 433 } 434 return graph; 435 } 436 437 private Set<NodePair> edges; 438 private int numUndirectedEges = 0; 439 private Map<Node, List<NodePair>> successors; 440 private Map<Node, List<NodePair>> predecessors; 441 442 protected void rememberSuccessor(NodePair pair) { 443 if (successors.containsKey(pair.getA())) { 444 if (!successors.get(pair.getA()).contains(pair)) { 445 successors.get(pair.getA()).add(pair); 446 } 447 } else { 448 List<NodePair> l = new ArrayList<NodePair>(); 449 l.add(pair); 450 successors.put(pair.getA(), l); 451 } 452 } 453 454 protected void rememberPredecessors(NodePair pair) { 455 if (predecessors.containsKey(pair.getB())) { 456 if (!predecessors.get(pair.getB()).contains(pair)) { 457 predecessors.get(pair.getB()).add(pair); 458 } 459 } else { 460 List<NodePair> l = new ArrayList<NodePair>(); 461 l.add(pair); 462 predecessors.put(pair.getB(), l); 463 } 464 } 465 466 protected boolean isTerminalNode(Node n) { 467 if (successors.get(n) == null) return false; 468 if (successors.get(n).size() != 1) return false; 469 if (predecessors.get(n) == null) return true; 470 if (predecessors.get(n).size() == 1) { 471 NodePair p1 = successors.get(n).iterator().next(); 472 NodePair p2 = predecessors.get(n).iterator().next(); 473 return p1.equals(p2.swap()); 474 } 475 return false; 476 } 477 478 protected void prepare() { 479 Set<NodePair> undirectedEdges = new LinkedHashSet<NodePair>(); 480 successors = new LinkedHashMap<Node, List<NodePair>>(); 481 predecessors = new LinkedHashMap<Node, List<NodePair>>(); 482 483 for (NodePair pair: edges) { 484 if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) { 485 undirectedEdges.add(pair); 486 } 487 rememberSuccessor(pair); 488 rememberPredecessors(pair); 489 } 490 numUndirectedEges = undirectedEdges.size(); 491 } 492 493 /** 494 * Constructs a new {@code NodeGraph}. 495 */ 496 public NodeGraph() { 497 edges = new LinkedHashSet<NodePair>(); 498 } 499 500 public void add(NodePair pair) { 501 if (!edges.contains(pair)) { 502 edges.add(pair); 503 } 504 } 505 506 public void add(List<NodePair> pairs) { 507 for (NodePair pair: pairs) { 508 add(pair); 509 } 510 } 511 512 protected Node getStartNode() { 513 Set<Node> nodes = getNodes(); 514 for (Node n: nodes) { 515 if (successors.get(n) != null && successors.get(n).size() ==1) 516 return n; 517 } 518 return null; 519 } 520 521 protected Set<Node> getTerminalNodes() { 522 Set<Node> ret = new LinkedHashSet<Node>(); 523 for (Node n: getNodes()) { 524 if (isTerminalNode(n)) { 525 ret.add(n); 526 } 527 } 528 return ret; 529 } 530 531 protected Set<Node> getNodes(Stack<NodePair> pairs) { 532 HashSet<Node> nodes = new LinkedHashSet<Node>(2*pairs.size()); 533 for (NodePair pair: pairs) { 534 nodes.add(pair.getA()); 535 nodes.add(pair.getB()); 536 } 537 return nodes; 538 } 539 540 protected List<NodePair> getOutboundPairs(NodePair pair) { 541 return getOutboundPairs(pair.getB()); 542 } 543 544 protected List<NodePair> getOutboundPairs(Node node) { 545 List<NodePair> l = successors.get(node); 546 if (l == null) 547 return Collections.emptyList(); 548 return l; 549 } 550 551 protected Set<Node> getNodes() { 552 Set<Node> nodes = new LinkedHashSet<Node>(2 * edges.size()); 553 for (NodePair pair: edges) { 554 nodes.add(pair.getA()); 555 nodes.add(pair.getB()); 556 } 557 return nodes; 558 } 559 560 protected boolean isSpanningWay(Stack<NodePair> way) { 561 return numUndirectedEges == way.size(); 562 } 563 564 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) { 565 LinkedList<Node> ret = new LinkedList<Node>(); 566 for (NodePair pair: path) { 567 ret.add(pair.getA()); 568 } 569 ret.add(path.peek().getB()); 570 return ret; 571 } 572 573 /** 574 * Tries to find a spanning path starting from node <code>startNode</code>. 575 * 576 * Traverses the path in depth-first order. 577 * 578 * @param startNode the start node 579 * @return the spanning path; null, if no path is found 580 */ 581 protected List<Node> buildSpanningPath(Node startNode) { 582 if (startNode == null) 583 return null; 584 Stack<NodePair> path = new Stack<NodePair>(); 585 Stack<NodePair> nextPairs = new Stack<NodePair>(); 586 nextPairs.addAll(getOutboundPairs(startNode)); 587 while(!nextPairs.isEmpty()) { 588 NodePair cur= nextPairs.pop(); 589 if (! path.contains(cur) && ! path.contains(cur.swap())) { 590 while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) { 591 path.pop(); 592 } 593 path.push(cur); 594 if (isSpanningWay(path)) return buildPathFromNodePairs(path); 595 nextPairs.addAll(getOutboundPairs(path.peek())); 596 } 597 } 598 return null; 599 } 600 601 /** 602 * Tries to find a path through the graph which visits each edge (i.e. 603 * the segment of a way) exactly one. 604 * 605 * @return the path; null, if no path was found 606 */ 607 public List<Node> buildSpanningPath() { 608 prepare(); 609 // try to find a path from each "terminal node", i.e. from a 610 // node which is connected by exactly one undirected edges (or 611 // two directed edges in opposite direction) to the graph. A 612 // graph built up from way segments is likely to include such 613 // nodes, unless all ways are closed. 614 // In the worst case this loops over all nodes which is 615 // very slow for large ways. 616 // 617 Set<Node> nodes = getTerminalNodes(); 618 nodes = nodes.isEmpty() ? getNodes() : nodes; 619 for (Node n: nodes) { 620 List<Node> path = buildSpanningPath(n); 621 if (path != null) 622 return path; 623 } 624 return null; 625 } 626 } 627}