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

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

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