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

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

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