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

Last change on this file since 10463 was 10463, checked in by Don-vip, 8 years ago

sonar - squid:S1166 - Exception handlers should preserve the original exceptions
  • Property svn:eol-style set to native
File size: 21.7 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.LinkedHashMap;
14import java.util.LinkedHashSet;
15import java.util.LinkedList;
16import java.util.List;
17import java.util.Map;
18import java.util.Objects;
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.data.osm.DataSet;
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;
42import org.openstreetmap.josm.tools.UserCancelException;
43
44/**
45 * Combines multiple ways into one.
46 * @since 213
47 */
48public class CombineWayAction extends JosmAction {
49
50 private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true);
51
52 /**
53 * Constructs a new {@code CombineWayAction}.
54 */
55 public CombineWayAction() {
56 super(tr("Combine Way"), "combineway", tr("Combine several ways into one."),
57 Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.DIRECT), true);
58 putValue("help", ht("/Action/CombineWay"));
59 }
60
61 protected static boolean confirmChangeDirectionOfWays() {
62 ExtendedDialog ed = new ExtendedDialog(Main.parent,
63 tr("Change directions?"),
64 new String[] {tr("Reverse and Combine"), tr("Cancel")});
65 ed.setButtonIcons(new String[] {"wayflip", "cancel"});
66 ed.setContent(tr("The ways can not be combined in their current directions. "
67 + "Do you want to reverse some of them?"));
68 ed.toggleEnable("combineway-reverse");
69 ed.showDialog();
70 return ed.getValue() == 1;
71 }
72
73 protected static void warnCombiningImpossible() {
74 String msg = tr("Could not combine ways<br>"
75 + "(They could not be merged into a single string of nodes)");
76 new Notification(msg)
77 .setIcon(JOptionPane.INFORMATION_MESSAGE)
78 .show();
79 return;
80 }
81
82 protected static Way getTargetWay(Collection<Way> combinedWays) {
83 // init with an arbitrary way
84 Way targetWay = combinedWays.iterator().next();
85
86 // look for the first way already existing on
87 // the server
88 for (Way w : combinedWays) {
89 targetWay = w;
90 if (!w.isNew()) {
91 break;
92 }
93 }
94 return targetWay;
95 }
96
97 /**
98 * Combine multiple ways into one.
99 * @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}
Note: See TracBrowser for help on using the repository browser.