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

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

sonar - squid:S1149 - Synchronized classes Vector, Hashtable, Stack and StringBuffer should not be used
  • Property svn:eol-style set to native
File size: 22.5 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.ArrayDeque;
11import java.util.ArrayList;
12import java.util.Collection;
13import java.util.Collections;
14import java.util.Deque;
15import java.util.LinkedHashMap;
16import java.util.LinkedHashSet;
17import java.util.LinkedList;
18import java.util.List;
19import java.util.Map;
20import java.util.Set;
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 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 List<Way> reversedWays = new LinkedList<>();
127 List<Way> unreversedWays = new LinkedList<>();
128 for (Way w: ways) {
129 // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971)
130 if (w.getNodesCount() < 2 || (path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
131 unreversedWays.add(w);
132 } else {
133 reversedWays.add(w);
134 }
135 }
136 // reverse path if all ways have been reversed
137 if (unreversedWays.isEmpty()) {
138 Collections.reverse(path);
139 unreversedWays = reversedWays;
140 reversedWays = null;
141 }
142 if ((reversedWays != null) && !reversedWays.isEmpty()) {
143 if (!confirmChangeDirectionOfWays()) return null;
144 // filter out ways that have no direction-dependent tags
145 unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays);
146 reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays);
147 // reverse path if there are more reversed than unreversed ways with direction-dependent tags
148 if (reversedWays.size() > unreversedWays.size()) {
149 Collections.reverse(path);
150 List<Way> tempWays = unreversedWays;
151 unreversedWays = reversedWays;
152 reversedWays = tempWays;
153 }
154 // if there are still reversed ways with direction-dependent tags, reverse their tags
155 if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
156 List<Way> unreversedTagWays = new ArrayList<>(ways);
157 unreversedTagWays.removeAll(reversedWays);
158 ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
159 List<Way> reversedTagWays = new ArrayList<>(reversedWays.size());
160 Collection<Command> changePropertyCommands = null;
161 for (Way w : reversedWays) {
162 Way wnew = new Way(w);
163 reversedTagWays.add(wnew);
164 changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
165 }
166 if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
167 for (Command c : changePropertyCommands) {
168 c.executeCommand();
169 }
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 List<Command> resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay));
183
184 List<Command> cmds = new LinkedList<>();
185 List<Way> deletedWays = new LinkedList<>(ways);
186 deletedWays.remove(targetWay);
187
188 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
189 cmds.addAll(resolution);
190 cmds.add(new DeleteCommand(deletedWays));
191 final SequenceCommand sequenceCommand = new SequenceCommand(/* for correct i18n of plural forms - see #9110 */
192 trn("Combine {0} way", "Combine {0} ways", ways.size(), ways.size()), cmds);
193
194 return new Pair<Way, Command>(targetWay, sequenceCommand);
195 }
196
197 @Override
198 public void actionPerformed(ActionEvent event) {
199 if (getCurrentDataSet() == null)
200 return;
201 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
202 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
203 if (selectedWays.size() < 2) {
204 new Notification(
205 tr("Please select at least two ways to combine."))
206 .setIcon(JOptionPane.INFORMATION_MESSAGE)
207 .setDuration(Notification.TIME_SHORT)
208 .show();
209 return;
210 }
211 // combine and update gui
212 Pair<Way, Command> combineResult;
213 try {
214 combineResult = combineWaysWorker(selectedWays);
215 } catch (UserCancelException ex) {
216 return;
217 }
218
219 if (combineResult == null)
220 return;
221 final Way selectedWay = combineResult.a;
222 Main.main.undoRedo.add(combineResult.b);
223 if (selectedWay != null) {
224 Runnable guiTask = new Runnable() {
225 @Override
226 public void run() {
227 getCurrentDataSet().setSelected(selectedWay);
228 }
229 };
230 GuiHelper.runInEDT(guiTask);
231 }
232 }
233
234 @Override
235 protected void updateEnabledState() {
236 if (getCurrentDataSet() == null) {
237 setEnabled(false);
238 return;
239 }
240 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
241 updateEnabledState(selection);
242 }
243
244 @Override
245 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
246 int numWays = 0;
247 for (OsmPrimitive osm : selection) {
248 if (osm instanceof Way) {
249 numWays++;
250 }
251 }
252 setEnabled(numWays >= 2);
253 }
254
255 /**
256 * A pair of nodes.
257 */
258 public static class NodePair {
259 private final Node a;
260 private final Node b;
261
262 /**
263 * Constructs a new {@code NodePair}.
264 * @param a The first node
265 * @param b The second node
266 */
267 public NodePair(Node a, Node b) {
268 this.a = a;
269 this.b = b;
270 }
271
272 /**
273 * Constructs a new {@code NodePair}.
274 * @param pair An existing {@code Pair} of nodes
275 */
276 public NodePair(Pair<Node, Node> pair) {
277 this(pair.a, pair.b);
278 }
279
280 /**
281 * Constructs a new {@code NodePair}.
282 * @param other An existing {@code NodePair}
283 */
284 public NodePair(NodePair other) {
285 this(other.a, other.b);
286 }
287
288 /**
289 * Replies the first node.
290 * @return The first node
291 */
292 public Node getA() {
293 return a;
294 }
295
296 /**
297 * Replies the second node
298 * @return The second node
299 */
300 public Node getB() {
301 return b;
302 }
303
304 public boolean isAdjacentToA(NodePair other) {
305 return other.getA() == a || other.getB() == a;
306 }
307
308 public boolean isAdjacentToB(NodePair other) {
309 return other.getA() == b || other.getB() == b;
310 }
311
312 public boolean isSuccessorOf(NodePair other) {
313 return other.getB() == a;
314 }
315
316 public boolean isPredecessorOf(NodePair other) {
317 return b == other.getA();
318 }
319
320 public NodePair swap() {
321 return new NodePair(b, a);
322 }
323
324 @Override
325 public String toString() {
326 return new StringBuilder()
327 .append('[')
328 .append(a.getId())
329 .append(',')
330 .append(b.getId())
331 .append(']')
332 .toString();
333 }
334
335 /**
336 * Determines if this pair contains the given node.
337 * @param n The node to look for
338 * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
339 */
340 public boolean contains(Node n) {
341 return a == n || b == n;
342 }
343
344 @Override
345 public int hashCode() {
346 final int prime = 31;
347 int result = 1;
348 result = prime * result + ((a == null) ? 0 : a.hashCode());
349 result = prime * result + ((b == null) ? 0 : b.hashCode());
350 return result;
351 }
352
353 @Override
354 public boolean equals(Object obj) {
355 if (this == obj)
356 return true;
357 if (obj == null)
358 return false;
359 if (getClass() != obj.getClass())
360 return false;
361 NodePair other = (NodePair) obj;
362 if (a == null) {
363 if (other.a != null)
364 return false;
365 } else if (!a.equals(other.a))
366 return false;
367 if (b == null) {
368 if (other.b != null)
369 return false;
370 } else if (!b.equals(other.b))
371 return false;
372 return true;
373 }
374 }
375
376 public static class NodeGraph {
377 public static List<NodePair> buildNodePairs(Way way, boolean directed) {
378 List<NodePair> pairs = new ArrayList<>();
379 for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) {
380 pairs.add(new NodePair(pair));
381 if (!directed) {
382 pairs.add(new NodePair(pair).swap());
383 }
384 }
385 return pairs;
386 }
387
388 public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
389 List<NodePair> pairs = new ArrayList<>();
390 for (Way w: ways) {
391 pairs.addAll(buildNodePairs(w, directed));
392 }
393 return pairs;
394 }
395
396 public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
397 List<NodePair> cleaned = new ArrayList<>();
398 for (NodePair p: pairs) {
399 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
400 cleaned.add(p);
401 }
402 }
403 return cleaned;
404 }
405
406 public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
407 NodeGraph graph = new NodeGraph();
408 for (NodePair pair: pairs) {
409 graph.add(pair);
410 }
411 return graph;
412 }
413
414 public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
415 NodeGraph graph = new NodeGraph();
416 for (Way w: ways) {
417 graph.add(buildNodePairs(w, true /* directed */));
418 }
419 return graph;
420 }
421
422 /**
423 * Create an undirected graph from the given node pairs.
424 * @param pairs Node pairs to build the graph from
425 * @return node graph structure
426 */
427 public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
428 NodeGraph graph = new NodeGraph();
429 for (NodePair pair: pairs) {
430 graph.add(pair);
431 graph.add(pair.swap());
432 }
433 return graph;
434 }
435
436 /**
437 * Create an undirected graph from the given ways, but prevent reversing of all
438 * non-new ways by fix one direction.
439 * @param ways Ways to build the graph from
440 * @return node graph structure
441 * @since 8181
442 */
443 public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
444 NodeGraph graph = new NodeGraph();
445 for (Way w: ways) {
446 graph.add(buildNodePairs(w, false /* undirected */));
447 }
448 return graph;
449 }
450
451 public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
452 boolean dir = true;
453 NodeGraph graph = new NodeGraph();
454 for (Way w: ways) {
455 if (!w.isNew()) {
456 /* let the first non-new way give the direction (see #5880) */
457 graph.add(buildNodePairs(w, dir));
458 dir = false;
459 } else {
460 graph.add(buildNodePairs(w, false /* undirected */));
461 }
462 }
463 return graph;
464 }
465
466 private Set<NodePair> edges;
467 private int numUndirectedEges;
468 private Map<Node, List<NodePair>> successors;
469 private Map<Node, List<NodePair>> predecessors;
470
471 protected void rememberSuccessor(NodePair pair) {
472 if (successors.containsKey(pair.getA())) {
473 if (!successors.get(pair.getA()).contains(pair)) {
474 successors.get(pair.getA()).add(pair);
475 }
476 } else {
477 List<NodePair> l = new ArrayList<>();
478 l.add(pair);
479 successors.put(pair.getA(), l);
480 }
481 }
482
483 protected void rememberPredecessors(NodePair pair) {
484 if (predecessors.containsKey(pair.getB())) {
485 if (!predecessors.get(pair.getB()).contains(pair)) {
486 predecessors.get(pair.getB()).add(pair);
487 }
488 } else {
489 List<NodePair> l = new ArrayList<>();
490 l.add(pair);
491 predecessors.put(pair.getB(), l);
492 }
493 }
494
495 protected boolean isTerminalNode(Node n) {
496 if (successors.get(n) == null) return false;
497 if (successors.get(n).size() != 1) return false;
498 if (predecessors.get(n) == null) return true;
499 if (predecessors.get(n).size() == 1) {
500 NodePair p1 = successors.get(n).get(0);
501 NodePair p2 = predecessors.get(n).get(0);
502 return p1.equals(p2.swap());
503 }
504 return false;
505 }
506
507 protected void prepare() {
508 Set<NodePair> undirectedEdges = new LinkedHashSet<>();
509 successors = new LinkedHashMap<>();
510 predecessors = new LinkedHashMap<>();
511
512 for (NodePair pair: edges) {
513 if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
514 undirectedEdges.add(pair);
515 }
516 rememberSuccessor(pair);
517 rememberPredecessors(pair);
518 }
519 numUndirectedEges = undirectedEdges.size();
520 }
521
522 /**
523 * Constructs a new {@code NodeGraph}.
524 */
525 public NodeGraph() {
526 edges = new LinkedHashSet<>();
527 }
528
529 public void add(NodePair pair) {
530 if (!edges.contains(pair)) {
531 edges.add(pair);
532 }
533 }
534
535 public void add(List<NodePair> pairs) {
536 for (NodePair pair: pairs) {
537 add(pair);
538 }
539 }
540
541 protected Node getStartNode() {
542 Set<Node> nodes = getNodes();
543 for (Node n: nodes) {
544 if (successors.get(n) != null && successors.get(n).size() == 1)
545 return n;
546 }
547 return null;
548 }
549
550 protected Set<Node> getTerminalNodes() {
551 Set<Node> ret = new LinkedHashSet<>();
552 for (Node n: getNodes()) {
553 if (isTerminalNode(n)) {
554 ret.add(n);
555 }
556 }
557 return ret;
558 }
559
560 protected List<NodePair> getOutboundPairs(NodePair pair) {
561 return getOutboundPairs(pair.getB());
562 }
563
564 protected List<NodePair> getOutboundPairs(Node node) {
565 List<NodePair> l = successors.get(node);
566 if (l == null)
567 return Collections.emptyList();
568 return l;
569 }
570
571 protected Set<Node> getNodes() {
572 Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
573 for (NodePair pair: edges) {
574 nodes.add(pair.getA());
575 nodes.add(pair.getB());
576 }
577 return nodes;
578 }
579
580 protected boolean isSpanningWay(Deque<NodePair> way) {
581 return numUndirectedEges == way.size();
582 }
583
584 protected List<Node> buildPathFromNodePairs(Deque<NodePair> path) {
585 List<Node> ret = new LinkedList<>();
586 for (NodePair pair: path) {
587 ret.add(pair.getA());
588 }
589 ret.add(path.peek().getB());
590 return ret;
591 }
592
593 /**
594 * Tries to find a spanning path starting from node <code>startNode</code>.
595 *
596 * Traverses the path in depth-first order.
597 *
598 * @param startNode the start node
599 * @return the spanning path; null, if no path is found
600 */
601 protected List<Node> buildSpanningPath(Node startNode) {
602 if (startNode == null)
603 return null;
604 Deque<NodePair> path = new ArrayDeque<>();
605 Deque<NodePair> nextPairs = new ArrayDeque<>();
606 nextPairs.addAll(getOutboundPairs(startNode));
607 while (!nextPairs.isEmpty()) {
608 NodePair cur = nextPairs.pop();
609 if (!path.contains(cur) && !path.contains(cur.swap())) {
610 while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
611 path.pop();
612 }
613 path.push(cur);
614 if (isSpanningWay(path)) return buildPathFromNodePairs(path);
615 nextPairs.addAll(getOutboundPairs(path.peek()));
616 }
617 }
618 return null;
619 }
620
621 /**
622 * Tries to find a path through the graph which visits each edge (i.e.
623 * the segment of a way) exactly once.
624 *
625 * @return the path; null, if no path was found
626 */
627 public List<Node> buildSpanningPath() {
628 prepare();
629 // try to find a path from each "terminal node", i.e. from a
630 // node which is connected by exactly one undirected edges (or
631 // two directed edges in opposite direction) to the graph. A
632 // graph built up from way segments is likely to include such
633 // nodes, unless all ways are closed.
634 // In the worst case this loops over all nodes which is very slow for large ways.
635 //
636 Set<Node> nodes = getTerminalNodes();
637 nodes = nodes.isEmpty() ? getNodes() : nodes;
638 for (Node n: nodes) {
639 List<Node> path = buildSpanningPath(n);
640 if (path != null)
641 return path;
642 }
643 return null;
644 }
645 }
646}
Note: See TracBrowser for help on using the repository browser.