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