source: josm/trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java@ 8240

Last change on this file since 8240 was 8182, checked in by stoecker, 9 years ago

see #5880 - copy and paste error
  • Property svn:eol-style set to native
File size: 22.9 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.actions;
3
4import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
5import static org.openstreetmap.josm.tools.I18n.tr;
6import static org.openstreetmap.josm.tools.I18n.trn;
7
8import java.awt.event.ActionEvent;
9import java.awt.event.KeyEvent;
10import java.util.ArrayList;
11import java.util.Collection;
12import java.util.Collections;
13import java.util.HashSet;
14import java.util.LinkedHashMap;
15import java.util.LinkedHashSet;
16import java.util.LinkedList;
17import java.util.List;
18import java.util.Map;
19import java.util.Set;
20import java.util.Stack;
21
22import javax.swing.JOptionPane;
23
24import org.openstreetmap.josm.Main;
25import org.openstreetmap.josm.command.ChangeCommand;
26import org.openstreetmap.josm.command.Command;
27import org.openstreetmap.josm.command.DeleteCommand;
28import org.openstreetmap.josm.command.SequenceCommand;
29import org.openstreetmap.josm.corrector.ReverseWayTagCorrector;
30import org.openstreetmap.josm.corrector.UserCancelException;
31import org.openstreetmap.josm.data.osm.Node;
32import org.openstreetmap.josm.data.osm.OsmPrimitive;
33import org.openstreetmap.josm.data.osm.TagCollection;
34import org.openstreetmap.josm.data.osm.Way;
35import org.openstreetmap.josm.data.preferences.BooleanProperty;
36import org.openstreetmap.josm.gui.ExtendedDialog;
37import org.openstreetmap.josm.gui.Notification;
38import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
39import org.openstreetmap.josm.gui.util.GuiHelper;
40import org.openstreetmap.josm.tools.Pair;
41import org.openstreetmap.josm.tools.Shortcut;
42
43/**
44 * Combines multiple ways into one.
45 * @since 213
46 */
47public class CombineWayAction extends JosmAction {
48
49 private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true);
50
51 /**
52 * Constructs a new {@code CombineWayAction}.
53 */
54 public CombineWayAction() {
55 super(tr("Combine Way"), "combineway", tr("Combine several ways into one."),
56 Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.DIRECT), true);
57 putValue("help", ht("/Action/CombineWay"));
58 }
59
60 protected static boolean confirmChangeDirectionOfWays() {
61 ExtendedDialog ed = new ExtendedDialog(Main.parent,
62 tr("Change directions?"),
63 new String[] {tr("Reverse and Combine"), tr("Cancel")});
64 ed.setButtonIcons(new String[] {"wayflip", "cancel"});
65 ed.setContent(tr("The ways can not be combined in their current directions. "
66 + "Do you want to reverse some of them?"));
67 ed.toggleEnable("combineway-reverse");
68 ed.showDialog();
69 return ed.getValue() == 1;
70 }
71
72 protected static void warnCombiningImpossible() {
73 String msg = tr("Could not combine ways<br>"
74 + "(They could not be merged into a single string of nodes)");
75 new Notification(msg)
76 .setIcon(JOptionPane.INFORMATION_MESSAGE)
77 .show();
78 return;
79 }
80
81 protected static Way getTargetWay(Collection<Way> combinedWays) {
82 // init with an arbitrary way
83 Way targetWay = combinedWays.iterator().next();
84
85 // look for the first way already existing on
86 // the server
87 for (Way w : combinedWays) {
88 targetWay = w;
89 if (!w.isNew()) {
90 break;
91 }
92 }
93 return targetWay;
94 }
95
96 /**
97 * Combine multiple ways into one.
98 * @param ways the way to combine to one way
99 * @return null if ways cannot be combined. Otherwise returns the combined
100 * ways and the commands to combine
101 * @throws UserCancelException
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
115 // ways
116 //
117 NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
118 List<Node> path = graph.buildSpanningPath();
119 if (path == null) {
120 warnCombiningImpossible();
121 return null;
122 }
123 // check whether any ways have been reversed in the process
124 // and build the collection of tags used by the ways to combine
125 //
126 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
127
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 Collection<Command> changePropertyCommands = null;
163 for (Way w : reversedWays) {
164 Way wnew = new Way(w);
165 reversedTagWays.add(wnew);
166 changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
167 }
168 if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
169 for (Command c : changePropertyCommands) {
170 c.executeCommand();
171 }
172 }
173 wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
174 wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
175 }
176 }
177
178 // create the new way and apply the new node list
179 //
180 Way targetWay = getTargetWay(ways);
181 Way modifiedTargetWay = new Way(targetWay);
182 modifiedTargetWay.setNodes(path);
183
184 List<Command> resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay));
185
186 LinkedList<Command> cmds = new LinkedList<>();
187 LinkedList<Way> deletedWays = new LinkedList<>(ways);
188 deletedWays.remove(targetWay);
189
190 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
191 cmds.addAll(resolution);
192 cmds.add(new DeleteCommand(deletedWays));
193 final SequenceCommand sequenceCommand = new SequenceCommand(/* for correct i18n of plural forms - see #9110 */
194 trn("Combine {0} way", "Combine {0} ways", ways.size(), ways.size()), cmds);
195
196 return new Pair<Way, Command>(targetWay, sequenceCommand);
197 }
198
199 @Override
200 public void actionPerformed(ActionEvent event) {
201 if (getCurrentDataSet() == null)
202 return;
203 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
204 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
205 if (selectedWays.size() < 2) {
206 new Notification(
207 tr("Please select at least two ways to combine."))
208 .setIcon(JOptionPane.INFORMATION_MESSAGE)
209 .setDuration(Notification.TIME_SHORT)
210 .show();
211 return;
212 }
213 // combine and update gui
214 Pair<Way, Command> combineResult;
215 try {
216 combineResult = combineWaysWorker(selectedWays);
217 } catch (UserCancelException ex) {
218 return;
219 }
220
221 if (combineResult == null)
222 return;
223 final Way selectedWay = combineResult.a;
224 Main.main.undoRedo.add(combineResult.b);
225 if(selectedWay != null)
226 {
227 Runnable guiTask = new Runnable() {
228 @Override
229 public void run() {
230 getCurrentDataSet().setSelected(selectedWay);
231 }
232 };
233 GuiHelper.runInEDT(guiTask);
234 }
235 }
236
237 @Override
238 protected void updateEnabledState() {
239 if (getCurrentDataSet() == null) {
240 setEnabled(false);
241 return;
242 }
243 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
244 updateEnabledState(selection);
245 }
246
247 @Override
248 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
249 int numWays = 0;
250 for (OsmPrimitive osm : selection)
251 if (osm instanceof Way) {
252 numWays++;
253 }
254 setEnabled(numWays >= 2);
255 }
256
257 /**
258 * A pair of nodes.
259 */
260 public static class NodePair {
261 private final Node a;
262 private final Node b;
263
264 /**
265 * Constructs a new {@code NodePair}.
266 * @param a The first node
267 * @param b The second node
268 */
269 public NodePair(Node a, Node b) {
270 this.a = a;
271 this.b = b;
272 }
273
274 /**
275 * Constructs a new {@code NodePair}.
276 * @param pair An existing {@code Pair} of nodes
277 */
278 public NodePair(Pair<Node,Node> pair) {
279 this(pair.a, pair.b);
280 }
281
282 /**
283 * Constructs a new {@code NodePair}.
284 * @param other An existing {@code NodePair}
285 */
286 public NodePair(NodePair other) {
287 this(other.a, other.b);
288 }
289
290 /**
291 * Replies the first node.
292 * @return The first node
293 */
294 public Node getA() {
295 return a;
296 }
297
298 /**
299 * Replies the second node
300 * @return The second node
301 */
302 public Node getB() {
303 return b;
304 }
305
306 public boolean isAdjacentToA(NodePair other) {
307 return other.getA() == a || other.getB() == a;
308 }
309
310 public boolean isAdjacentToB(NodePair other) {
311 return other.getA() == b || other.getB() == b;
312 }
313
314 public boolean isSuccessorOf(NodePair other) {
315 return other.getB() == a;
316 }
317
318 public boolean isPredecessorOf(NodePair other) {
319 return b == other.getA();
320 }
321
322 public NodePair swap() {
323 return new NodePair(b,a);
324 }
325
326 @Override
327 public String toString() {
328 return new StringBuilder()
329 .append("[")
330 .append(a.getId())
331 .append(",")
332 .append(b.getId())
333 .append("]")
334 .toString();
335 }
336
337 /**
338 * Determines if this pair contains the given node.
339 * @param n The node to look for
340 * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
341 */
342 public boolean contains(Node n) {
343 return a == n || b == n;
344 }
345
346 @Override
347 public int hashCode() {
348 final int prime = 31;
349 int result = 1;
350 result = prime * result + ((a == null) ? 0 : a.hashCode());
351 result = prime * result + ((b == null) ? 0 : b.hashCode());
352 return result;
353 }
354
355 @Override
356 public boolean equals(Object obj) {
357 if (this == obj)
358 return true;
359 if (obj == null)
360 return false;
361 if (getClass() != obj.getClass())
362 return false;
363 NodePair other = (NodePair) obj;
364 if (a == null) {
365 if (other.a != null)
366 return false;
367 } else if (!a.equals(other.a))
368 return false;
369 if (b == null) {
370 if (other.b != null)
371 return false;
372 } else if (!b.equals(other.b))
373 return false;
374 return true;
375 }
376 }
377
378 public static class NodeGraph {
379 public static List<NodePair> buildNodePairs(Way way, boolean directed) {
380 List<NodePair> pairs = new ArrayList<>();
381 for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
382 pairs.add(new NodePair(pair));
383 if (!directed) {
384 pairs.add(new NodePair(pair).swap());
385 }
386 }
387 return pairs;
388 }
389
390 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
391 List<NodePair> pairs = new ArrayList<>();
392 for (Way w: ways) {
393 pairs.addAll(buildNodePairs(w, directed));
394 }
395 return pairs;
396 }
397
398 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
399 List<NodePair> cleaned = new ArrayList<>();
400 for(NodePair p: pairs) {
401 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
402 cleaned.add(p);
403 }
404 }
405 return cleaned;
406 }
407
408 public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
409 NodeGraph graph = new NodeGraph();
410 for (NodePair pair: pairs) {
411 graph.add(pair);
412 }
413 return graph;
414 }
415
416 public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
417 NodeGraph graph = new NodeGraph();
418 for (Way w: ways) {
419 graph.add(buildNodePairs(w, true /* directed */));
420 }
421 return graph;
422 }
423
424 /**
425 * Create an undirected graph from the given ways.
426 * @param ways Ways to build the graph from
427 * @return node graph structure
428 */
429 public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
430 NodeGraph graph = new NodeGraph();
431 for (NodePair pair: pairs) {
432 graph.add(pair);
433 graph.add(pair.swap());
434 }
435 return graph;
436 }
437
438 /**
439 * Create an undirected graph from the given ways, but prevent reversing of all
440 * non-new ways by fix one direction.
441 * @param ways Ways to build the graph from
442 * @return node graph structure
443 * @since 8181
444 */
445 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
446 NodeGraph graph = new NodeGraph();
447 for (Way w: ways) {
448 graph.add(buildNodePairs(w, false /* undirected */));
449 }
450 return graph;
451 }
452
453 public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
454 boolean dir = true;
455 NodeGraph graph = new NodeGraph();
456 for (Way w: ways) {
457 if(!w.isNew()) {
458 /* let the first non-new way give the direction (see #5880) */
459 graph.add(buildNodePairs(w, dir));
460 dir = false;
461 } else {
462 graph.add(buildNodePairs(w, false /* undirected */));
463 }
464 }
465 return graph;
466 }
467
468 private Set<NodePair> edges;
469 private int numUndirectedEges = 0;
470 private Map<Node, List<NodePair>> successors;
471 private Map<Node, List<NodePair>> predecessors;
472
473 protected void rememberSuccessor(NodePair pair) {
474 if (successors.containsKey(pair.getA())) {
475 if (!successors.get(pair.getA()).contains(pair)) {
476 successors.get(pair.getA()).add(pair);
477 }
478 } else {
479 List<NodePair> l = new ArrayList<>();
480 l.add(pair);
481 successors.put(pair.getA(), l);
482 }
483 }
484
485 protected void rememberPredecessors(NodePair pair) {
486 if (predecessors.containsKey(pair.getB())) {
487 if (!predecessors.get(pair.getB()).contains(pair)) {
488 predecessors.get(pair.getB()).add(pair);
489 }
490 } else {
491 List<NodePair> l = new ArrayList<>();
492 l.add(pair);
493 predecessors.put(pair.getB(), l);
494 }
495 }
496
497 protected boolean isTerminalNode(Node n) {
498 if (successors.get(n) == null) return false;
499 if (successors.get(n).size() != 1) return false;
500 if (predecessors.get(n) == null) return true;
501 if (predecessors.get(n).size() == 1) {
502 NodePair p1 = successors.get(n).iterator().next();
503 NodePair p2 = predecessors.get(n).iterator().next();
504 return p1.equals(p2.swap());
505 }
506 return false;
507 }
508
509 protected void prepare() {
510 Set<NodePair> undirectedEdges = new LinkedHashSet<>();
511 successors = new LinkedHashMap<>();
512 predecessors = new LinkedHashMap<>();
513
514 for (NodePair pair: edges) {
515 if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
516 undirectedEdges.add(pair);
517 }
518 rememberSuccessor(pair);
519 rememberPredecessors(pair);
520 }
521 numUndirectedEges = undirectedEdges.size();
522 }
523
524 /**
525 * Constructs a new {@code NodeGraph}.
526 */
527 public NodeGraph() {
528 edges = new LinkedHashSet<>();
529 }
530
531 public void add(NodePair pair) {
532 if (!edges.contains(pair)) {
533 edges.add(pair);
534 }
535 }
536
537 public void add(List<NodePair> pairs) {
538 for (NodePair pair: pairs) {
539 add(pair);
540 }
541 }
542
543 protected Node getStartNode() {
544 Set<Node> nodes = getNodes();
545 for (Node n: nodes) {
546 if (successors.get(n) != null && successors.get(n).size() ==1)
547 return n;
548 }
549 return null;
550 }
551
552 protected Set<Node> getTerminalNodes() {
553 Set<Node> ret = new LinkedHashSet<>();
554 for (Node n: getNodes()) {
555 if (isTerminalNode(n)) {
556 ret.add(n);
557 }
558 }
559 return ret;
560 }
561
562 protected Set<Node> getNodes(Stack<NodePair> pairs) {
563 HashSet<Node> nodes = new LinkedHashSet<>(2*pairs.size());
564 for (NodePair pair: pairs) {
565 nodes.add(pair.getA());
566 nodes.add(pair.getB());
567 }
568 return nodes;
569 }
570
571 protected List<NodePair> getOutboundPairs(NodePair pair) {
572 return getOutboundPairs(pair.getB());
573 }
574
575 protected List<NodePair> getOutboundPairs(Node node) {
576 List<NodePair> l = successors.get(node);
577 if (l == null)
578 return Collections.emptyList();
579 return l;
580 }
581
582 protected Set<Node> getNodes() {
583 Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
584 for (NodePair pair: edges) {
585 nodes.add(pair.getA());
586 nodes.add(pair.getB());
587 }
588 return nodes;
589 }
590
591 protected boolean isSpanningWay(Stack<NodePair> way) {
592 return numUndirectedEges == way.size();
593 }
594
595 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
596 LinkedList<Node> ret = new LinkedList<>();
597 for (NodePair pair: path) {
598 ret.add(pair.getA());
599 }
600 ret.add(path.peek().getB());
601 return ret;
602 }
603
604 /**
605 * Tries to find a spanning path starting from node <code>startNode</code>.
606 *
607 * Traverses the path in depth-first order.
608 *
609 * @param startNode the start node
610 * @return the spanning path; null, if no path is found
611 */
612 protected List<Node> buildSpanningPath(Node startNode) {
613 if (startNode == null)
614 return null;
615 Stack<NodePair> path = new Stack<>();
616 Stack<NodePair> nextPairs = new Stack<>();
617 nextPairs.addAll(getOutboundPairs(startNode));
618 while(!nextPairs.isEmpty()) {
619 NodePair cur= nextPairs.pop();
620 if (! path.contains(cur) && ! path.contains(cur.swap())) {
621 while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
622 path.pop();
623 }
624 path.push(cur);
625 if (isSpanningWay(path)) return buildPathFromNodePairs(path);
626 nextPairs.addAll(getOutboundPairs(path.peek()));
627 }
628 }
629 return null;
630 }
631
632 /**
633 * Tries to find a path through the graph which visits each edge (i.e.
634 * the segment of a way) exactly once.
635 *
636 * @return the path; null, if no path was found
637 */
638 public List<Node> buildSpanningPath() {
639 prepare();
640 // try to find a path from each "terminal node", i.e. from a
641 // node which is connected by exactly one undirected edges (or
642 // two directed edges in opposite direction) to the graph. A
643 // graph built up from way segments is likely to include such
644 // nodes, unless all ways are closed.
645 // In the worst case this loops over all nodes which is
646 // very slow for large ways.
647 //
648 Set<Node> nodes = getTerminalNodes();
649 nodes = nodes.isEmpty() ? getNodes() : nodes;
650 for (Node n: nodes) {
651 List<Node> path = buildSpanningPath(n);
652 if (path != null)
653 return path;
654 }
655 return null;
656 }
657 }
658}
Note: See TracBrowser for help on using the repository browser.