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

Last change on this file since 11535 was 11389, checked in by Don-vip, 7 years ago

findbugs - DLS_DEAD_LOCAL_STORE
  • Property svn:eol-style set to native
File size: 21.4 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 }
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 ways and the commands to combine
100 * @throws UserCancelException if the user cancelled a dialog.
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 ways
114 //
115 NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(ways);
116 List<Node> path = graph.buildSpanningPath();
117 if (path == null) {
118 warnCombiningImpossible();
119 return null;
120 }
121 // check whether any ways have been reversed in the process
122 // and build the collection of tags used by the ways to combine
123 //
124 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
125
126 final List<Command> reverseWayTagCommands = new LinkedList<>();
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 = null;
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 for (Way w : reversedWays) {
162 Way wnew = new Way(w);
163 reversedTagWays.add(wnew);
164 reverseWayTagCommands.addAll(reverseWayTagCorrector.execute(w, wnew));
165 }
166 if (!reverseWayTagCommands.isEmpty()) {
167 // commands need to be executed for CombinePrimitiveResolverDialog
168 Main.main.undoRedo.add(new SequenceCommand(tr("Reverse Ways"), reverseWayTagCommands));
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 final List<Command> resolution;
182 try {
183 resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay));
184 } finally {
185 if (!reverseWayTagCommands.isEmpty()) {
186 // undo reverseWayTagCorrector and merge into SequenceCommand below
187 Main.main.undoRedo.undo();
188 }
189 }
190
191 List<Command> cmds = new LinkedList<>();
192 List<Way> deletedWays = new LinkedList<>(ways);
193 deletedWays.remove(targetWay);
194
195 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
196 cmds.addAll(reverseWayTagCommands);
197 cmds.addAll(resolution);
198 cmds.add(new DeleteCommand(deletedWays));
199 final Command sequenceCommand = new SequenceCommand(/* for correct i18n of plural forms - see #9110 */
200 trn("Combine {0} way", "Combine {0} ways", ways.size(), ways.size()), cmds);
201
202 return new Pair<>(targetWay, sequenceCommand);
203 }
204
205 @Override
206 public void actionPerformed(ActionEvent event) {
207 final DataSet ds = getLayerManager().getEditDataSet();
208 if (ds == null)
209 return;
210 Collection<OsmPrimitive> selection = ds.getSelected();
211 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
212 if (selectedWays.size() < 2) {
213 new Notification(
214 tr("Please select at least two ways to combine."))
215 .setIcon(JOptionPane.INFORMATION_MESSAGE)
216 .setDuration(Notification.TIME_SHORT)
217 .show();
218 return;
219 }
220 // combine and update gui
221 Pair<Way, Command> combineResult;
222 try {
223 combineResult = combineWaysWorker(selectedWays);
224 } catch (UserCancelException ex) {
225 Main.trace(ex);
226 return;
227 }
228
229 if (combineResult == null)
230 return;
231 final Way selectedWay = combineResult.a;
232 Main.main.undoRedo.add(combineResult.b);
233 if (selectedWay != null) {
234 GuiHelper.runInEDT(() -> ds.setSelected(selectedWay));
235 }
236 }
237
238 @Override
239 protected void updateEnabledState() {
240 updateEnabledStateOnCurrentSelection();
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 }
251 setEnabled(numWays >= 2);
252 }
253
254 /**
255 * A pair of nodes.
256 */
257 public static class NodePair {
258 private final Node a;
259 private final Node b;
260
261 /**
262 * Constructs a new {@code NodePair}.
263 * @param a The first node
264 * @param b The second node
265 */
266 public NodePair(Node a, Node b) {
267 this.a = a;
268 this.b = b;
269 }
270
271 /**
272 * Constructs a new {@code NodePair}.
273 * @param pair An existing {@code Pair} of nodes
274 */
275 public NodePair(Pair<Node, Node> pair) {
276 this(pair.a, pair.b);
277 }
278
279 /**
280 * Replies the first node.
281 * @return The first node
282 */
283 public Node getA() {
284 return a;
285 }
286
287 /**
288 * Replies the second node
289 * @return The second node
290 */
291 public Node getB() {
292 return b;
293 }
294
295 public boolean isSuccessorOf(NodePair other) {
296 return other.getB() == a;
297 }
298
299 public boolean isPredecessorOf(NodePair other) {
300 return b == other.getA();
301 }
302
303 public NodePair swap() {
304 return new NodePair(b, a);
305 }
306
307 @Override
308 public String toString() {
309 return new StringBuilder()
310 .append('[')
311 .append(a.getId())
312 .append(',')
313 .append(b.getId())
314 .append(']')
315 .toString();
316 }
317
318 /**
319 * Determines if this pair contains the given node.
320 * @param n The node to look for
321 * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
322 */
323 public boolean contains(Node n) {
324 return a == n || b == n;
325 }
326
327 @Override
328 public int hashCode() {
329 return Objects.hash(a, b);
330 }
331
332 @Override
333 public boolean equals(Object obj) {
334 if (this == obj) return true;
335 if (obj == null || getClass() != obj.getClass()) return false;
336 NodePair nodePair = (NodePair) obj;
337 return Objects.equals(a, nodePair.a) &&
338 Objects.equals(b, nodePair.b);
339 }
340 }
341
342 public static class NodeGraph {
343 public static List<NodePair> buildNodePairs(Way way, boolean directed) {
344 List<NodePair> pairs = new ArrayList<>();
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 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
355 List<NodePair> pairs = new ArrayList<>();
356 for (Way w: ways) {
357 pairs.addAll(buildNodePairs(w, directed));
358 }
359 return pairs;
360 }
361
362 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
363 List<NodePair> cleaned = new ArrayList<>();
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 public static 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 public static 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 /**
389 * Create an undirected graph from the given node pairs.
390 * @param pairs Node pairs to build the graph from
391 * @return node graph structure
392 */
393 public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
394 NodeGraph graph = new NodeGraph();
395 for (NodePair pair: pairs) {
396 graph.add(pair);
397 graph.add(pair.swap());
398 }
399 return graph;
400 }
401
402 /**
403 * Create an undirected graph from the given ways, but prevent reversing of all
404 * non-new ways by fix one direction.
405 * @param ways Ways to build the graph from
406 * @return node graph structure
407 * @since 8181
408 */
409 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
410 NodeGraph graph = new NodeGraph();
411 for (Way w: ways) {
412 graph.add(buildNodePairs(w, false /* undirected */));
413 }
414 return graph;
415 }
416
417 public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
418 boolean dir = true;
419 NodeGraph graph = new NodeGraph();
420 for (Way w: ways) {
421 if (!w.isNew()) {
422 /* let the first non-new way give the direction (see #5880) */
423 graph.add(buildNodePairs(w, dir));
424 dir = false;
425 } else {
426 graph.add(buildNodePairs(w, false /* undirected */));
427 }
428 }
429 return graph;
430 }
431
432 private final Set<NodePair> edges;
433 private int numUndirectedEges;
434 private final Map<Node, List<NodePair>> successors = new LinkedHashMap<>();
435 private final Map<Node, List<NodePair>> predecessors = new LinkedHashMap<>();
436
437 protected void rememberSuccessor(NodePair pair) {
438 if (successors.containsKey(pair.getA())) {
439 if (!successors.get(pair.getA()).contains(pair)) {
440 successors.get(pair.getA()).add(pair);
441 }
442 } else {
443 List<NodePair> l = new ArrayList<>();
444 l.add(pair);
445 successors.put(pair.getA(), l);
446 }
447 }
448
449 protected void rememberPredecessors(NodePair pair) {
450 if (predecessors.containsKey(pair.getB())) {
451 if (!predecessors.get(pair.getB()).contains(pair)) {
452 predecessors.get(pair.getB()).add(pair);
453 }
454 } else {
455 List<NodePair> l = new ArrayList<>();
456 l.add(pair);
457 predecessors.put(pair.getB(), l);
458 }
459 }
460
461 protected boolean isTerminalNode(Node n) {
462 if (successors.get(n) == null) return false;
463 if (successors.get(n).size() != 1) return false;
464 if (predecessors.get(n) == null) return true;
465 if (predecessors.get(n).size() == 1) {
466 NodePair p1 = successors.get(n).get(0);
467 NodePair p2 = predecessors.get(n).get(0);
468 return p1.equals(p2.swap());
469 }
470 return false;
471 }
472
473 protected void prepare() {
474 Set<NodePair> undirectedEdges = new LinkedHashSet<>();
475 successors.clear();
476 predecessors.clear();
477
478 for (NodePair pair: edges) {
479 if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
480 undirectedEdges.add(pair);
481 }
482 rememberSuccessor(pair);
483 rememberPredecessors(pair);
484 }
485 numUndirectedEges = undirectedEdges.size();
486 }
487
488 /**
489 * Constructs a new {@code NodeGraph}.
490 */
491 public NodeGraph() {
492 edges = new LinkedHashSet<>();
493 }
494
495 public void add(NodePair pair) {
496 if (!edges.contains(pair)) {
497 edges.add(pair);
498 }
499 }
500
501 public void add(List<NodePair> pairs) {
502 for (NodePair pair: pairs) {
503 add(pair);
504 }
505 }
506
507 protected Set<Node> getTerminalNodes() {
508 Set<Node> ret = new LinkedHashSet<>();
509 for (Node n: getNodes()) {
510 if (isTerminalNode(n)) {
511 ret.add(n);
512 }
513 }
514 return ret;
515 }
516
517 protected List<NodePair> getOutboundPairs(NodePair pair) {
518 return getOutboundPairs(pair.getB());
519 }
520
521 protected List<NodePair> getOutboundPairs(Node node) {
522 List<NodePair> l = successors.get(node);
523 if (l == null)
524 return Collections.emptyList();
525 return l;
526 }
527
528 protected Set<Node> getNodes() {
529 Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
530 for (NodePair pair: edges) {
531 nodes.add(pair.getA());
532 nodes.add(pair.getB());
533 }
534 return nodes;
535 }
536
537 protected boolean isSpanningWay(Stack<NodePair> way) {
538 return numUndirectedEges == way.size();
539 }
540
541 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
542 List<Node> ret = new LinkedList<>();
543 for (NodePair pair: path) {
544 ret.add(pair.getA());
545 }
546 ret.add(path.peek().getB());
547 return ret;
548 }
549
550 /**
551 * Tries to find a spanning path starting from node <code>startNode</code>.
552 *
553 * Traverses the path in depth-first order.
554 *
555 * @param startNode the start node
556 * @return the spanning path; null, if no path is found
557 */
558 protected List<Node> buildSpanningPath(Node startNode) {
559 if (startNode == null)
560 return null;
561 Stack<NodePair> path = new Stack<>();
562 Stack<NodePair> nextPairs = new Stack<>();
563 nextPairs.addAll(getOutboundPairs(startNode));
564 while (!nextPairs.isEmpty()) {
565 NodePair cur = nextPairs.pop();
566 if (!path.contains(cur) && !path.contains(cur.swap())) {
567 while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
568 path.pop();
569 }
570 path.push(cur);
571 if (isSpanningWay(path)) return buildPathFromNodePairs(path);
572 nextPairs.addAll(getOutboundPairs(path.peek()));
573 }
574 }
575 return null;
576 }
577
578 /**
579 * Tries to find a path through the graph which visits each edge (i.e.
580 * the segment of a way) exactly once.
581 *
582 * @return the path; null, if no path was found
583 */
584 public List<Node> buildSpanningPath() {
585 prepare();
586 // try to find a path from each "terminal node", i.e. from a
587 // node which is connected by exactly one undirected edges (or
588 // two directed edges in opposite direction) to the graph. A
589 // graph built up from way segments is likely to include such
590 // nodes, unless all ways are closed.
591 // In the worst case this loops over all nodes which is very slow for large ways.
592 //
593 Set<Node> nodes = getTerminalNodes();
594 nodes = nodes.isEmpty() ? getNodes() : nodes;
595 for (Node n: nodes) {
596 List<Node> path = buildSpanningPath(n);
597 if (path != null)
598 return path;
599 }
600 return null;
601 }
602 }
603}
Note: See TracBrowser for help on using the repository browser.