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

Last change on this file since 4996 was 4982, checked in by stoecker, 12 years ago

see #7226 - patch by akks (fixed a bit) - fix shortcut deprecations
  • Property svn:eol-style set to native
File size: 22.5 KB
Line 
1// License: GPL. Copyright 2007 by Immanuel Scholz and others
2package org.openstreetmap.josm.actions;
3
4import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.combineTigerTags;
5import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.completeTagCollectionForEditing;
6import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.normalizeTagCollectionBeforeEditing;
7import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
8import static org.openstreetmap.josm.tools.I18n.tr;
9
10import java.awt.event.ActionEvent;
11import java.awt.event.KeyEvent;
12import java.util.ArrayList;
13import java.util.Collection;
14import java.util.Collections;
15import java.util.HashMap;
16import java.util.HashSet;
17import java.util.LinkedHashMap;
18import java.util.LinkedHashSet;
19import java.util.LinkedList;
20import java.util.List;
21import java.util.Set;
22import java.util.Stack;
23
24import javax.swing.JOptionPane;
25import javax.swing.SwingUtilities;
26
27import org.openstreetmap.josm.Main;
28import org.openstreetmap.josm.command.ChangeCommand;
29import org.openstreetmap.josm.command.Command;
30import org.openstreetmap.josm.command.DeleteCommand;
31import org.openstreetmap.josm.command.SequenceCommand;
32import org.openstreetmap.josm.corrector.ReverseWayTagCorrector;
33import org.openstreetmap.josm.corrector.UserCancelException;
34import org.openstreetmap.josm.data.osm.Node;
35import org.openstreetmap.josm.data.osm.OsmPrimitive;
36import org.openstreetmap.josm.data.osm.Relation;
37import org.openstreetmap.josm.data.osm.TagCollection;
38import org.openstreetmap.josm.data.osm.Way;
39import org.openstreetmap.josm.data.preferences.BooleanProperty;
40import org.openstreetmap.josm.gui.ExtendedDialog;
41import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
42import org.openstreetmap.josm.tools.Pair;
43import org.openstreetmap.josm.tools.Shortcut;
44
45/**
46 * Combines multiple ways into one.
47 *
48 */
49public class CombineWayAction extends JosmAction {
50
51 private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true);
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.png", "cancel.png"});
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.showDialog();
67 return ed.getValue() == 1;
68 }
69
70 protected static void warnCombiningImpossible() {
71 String msg = tr("Could not combine ways "
72 + "(They could not be merged into a single string of nodes)");
73 JOptionPane.showMessageDialog(
74 Main.parent,
75 msg,
76 tr("Information"),
77 JOptionPane.INFORMATION_MESSAGE
78 );
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 * Replies the set of referring relations
99 *
100 * @return the set of referring relations
101 */
102 public static Set<Relation> getParentRelations(Collection<Way> ways) {
103 HashSet<Relation> ret = new HashSet<Relation>();
104 for (Way w: ways) {
105 ret.addAll(OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class));
106 }
107 return ret;
108 }
109
110 /**
111 * @param ways
112 * @return null if ways cannot be combined. Otherwise returns the combined
113 * ways and the commands to combine
114 * @throws UserCancelException
115 */
116 public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException {
117
118 // prepare and clean the list of ways to combine
119 //
120 if (ways == null || ways.isEmpty())
121 return null;
122 ways.remove(null); // just in case - remove all null ways from the collection
123
124 // remove duplicates, preserving order
125 ways = new LinkedHashSet<Way>(ways);
126
127 // try to build a new way which includes all the combined
128 // ways
129 //
130 NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
131 List<Node> path = graph.buildSpanningPath();
132 if (path == null) {
133 warnCombiningImpossible();
134 return null;
135 }
136 // check whether any ways have been reversed in the process
137 // and build the collection of tags used by the ways to combine
138 //
139 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
140
141 List<Way> reversedWays = new LinkedList<Way>();
142 List<Way> unreversedWays = new LinkedList<Way>();
143 for (Way w: ways) {
144 if ((path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
145 unreversedWays.add(w);
146 } else {
147 reversedWays.add(w);
148 }
149 }
150 // reverse path if all ways have been reversed
151 if (unreversedWays.isEmpty()) {
152 Collections.reverse(path);
153 unreversedWays = reversedWays;
154 reversedWays = null;
155 }
156 if ((reversedWays != null) && !reversedWays.isEmpty()) {
157 if (!confirmChangeDirectionOfWays()) return null;
158 // filter out ways that have no direction-dependent tags
159 unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays);
160 reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays);
161 // reverse path if there are more reversed than unreversed ways with direction-dependent tags
162 if (reversedWays.size() > unreversedWays.size()) {
163 Collections.reverse(path);
164 List<Way> tempWays = unreversedWays;
165 unreversedWays = reversedWays;
166 reversedWays = tempWays;
167 }
168 // if there are still reversed ways with direction-dependent tags, reverse their tags
169 if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
170 List<Way> unreversedTagWays = new ArrayList<Way>(ways);
171 unreversedTagWays.removeAll(reversedWays);
172 ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
173 List<Way> reversedTagWays = new ArrayList<Way>();
174 Collection<Command> changePropertyCommands = null;
175 for (Way w : reversedWays) {
176 Way wnew = new Way(w);
177 reversedTagWays.add(wnew);
178 changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
179 }
180 if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
181 for (Command c : changePropertyCommands) {
182 c.executeCommand();
183 }
184 }
185 wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
186 wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
187 }
188 }
189
190 // create the new way and apply the new node list
191 //
192 Way targetWay = getTargetWay(ways);
193 Way modifiedTargetWay = new Way(targetWay);
194 modifiedTargetWay.setNodes(path);
195
196 TagCollection completeWayTags = new TagCollection(wayTags);
197 combineTigerTags(completeWayTags);
198 normalizeTagCollectionBeforeEditing(completeWayTags, ways);
199 TagCollection tagsToEdit = new TagCollection(completeWayTags);
200 completeTagCollectionForEditing(tagsToEdit);
201
202 CombinePrimitiveResolverDialog dialog = CombinePrimitiveResolverDialog.getInstance();
203 dialog.getTagConflictResolverModel().populate(tagsToEdit, completeWayTags.getKeysWithMultipleValues());
204 dialog.setTargetPrimitive(targetWay);
205 Set<Relation> parentRelations = getParentRelations(ways);
206 dialog.getRelationMemberConflictResolverModel().populate(
207 parentRelations,
208 ways
209 );
210 dialog.prepareDefaultDecisions();
211
212 // resolve tag conflicts if necessary
213 //
214 if (!completeWayTags.isApplicableToPrimitive() || !parentRelations.isEmpty()) {
215 dialog.setVisible(true);
216 if (dialog.isCanceled())
217 throw new UserCancelException();
218 }
219
220 LinkedList<Command> cmds = new LinkedList<Command>();
221 LinkedList<Way> deletedWays = new LinkedList<Way>(ways);
222 deletedWays.remove(targetWay);
223
224 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
225 cmds.addAll(dialog.buildResolutionCommands());
226 cmds.add(new DeleteCommand(deletedWays));
227 final SequenceCommand sequenceCommand = new SequenceCommand(tr("Combine {0} ways", ways.size()), cmds);
228
229 return new Pair<Way, Command>(targetWay, sequenceCommand);
230 }
231
232 public void actionPerformed(ActionEvent event) {
233 if (getCurrentDataSet() == null)
234 return;
235 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
236 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
237 if (selectedWays.size() < 2) {
238 JOptionPane.showMessageDialog(
239 Main.parent,
240 tr("Please select at least two ways to combine."),
241 tr("Information"),
242 JOptionPane.INFORMATION_MESSAGE
243 );
244 return;
245 }
246 // combine and update gui
247 Pair<Way, Command> combineResult;
248 try {
249 combineResult = combineWaysWorker(selectedWays);
250 } catch (UserCancelException ex) {
251 return;
252 }
253
254 if (combineResult == null)
255 return;
256 final Way selectedWay = combineResult.a;
257 Main.main.undoRedo.add(combineResult.b);
258 if(selectedWay != null)
259 {
260 Runnable guiTask = new Runnable() {
261 public void run() {
262 getCurrentDataSet().setSelected(selectedWay);
263 }
264 };
265 if (SwingUtilities.isEventDispatchThread()) {
266 guiTask.run();
267 } else {
268 SwingUtilities.invokeLater(guiTask);
269 }
270 }
271 }
272
273 @Override
274 protected void updateEnabledState() {
275 if (getCurrentDataSet() == null) {
276 setEnabled(false);
277 return;
278 }
279 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
280 updateEnabledState(selection);
281 }
282
283 @Override
284 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
285 int numWays = 0;
286 for (OsmPrimitive osm : selection)
287 if (osm instanceof Way) {
288 numWays++;
289 }
290 setEnabled(numWays >= 2);
291 }
292
293 static public class NodePair {
294 private Node a;
295 private Node b;
296 public NodePair(Node a, Node b) {
297 this.a =a;
298 this.b = b;
299 }
300
301 public NodePair(Pair<Node,Node> pair) {
302 this.a = pair.a;
303 this.b = pair.b;
304 }
305
306 public NodePair(NodePair other) {
307 this.a = other.a;
308 this.b = other.b;
309 }
310
311 public Node getA() {
312 return a;
313 }
314
315 public Node getB() {
316 return b;
317 }
318
319 public boolean isAdjacentToA(NodePair other) {
320 return other.getA() == a || other.getB() == a;
321 }
322
323 public boolean isAdjacentToB(NodePair other) {
324 return other.getA() == b || other.getB() == b;
325 }
326
327 public boolean isSuccessorOf(NodePair other) {
328 return other.getB() == a;
329 }
330
331 public boolean isPredecessorOf(NodePair other) {
332 return b == other.getA();
333 }
334
335 public NodePair swap() {
336 return new NodePair(b,a);
337 }
338
339 @Override
340 public String toString() {
341 return new StringBuilder()
342 .append("[")
343 .append(a.getId())
344 .append(",")
345 .append(b.getId())
346 .append("]")
347 .toString();
348 }
349
350 public boolean contains(Node n) {
351 return a == n || b == n;
352 }
353
354 @Override
355 public int hashCode() {
356 final int prime = 31;
357 int result = 1;
358 result = prime * result + ((a == null) ? 0 : a.hashCode());
359 result = prime * result + ((b == null) ? 0 : b.hashCode());
360 return result;
361 }
362 @Override
363 public boolean equals(Object obj) {
364 if (this == obj)
365 return true;
366 if (obj == null)
367 return false;
368 if (getClass() != obj.getClass())
369 return false;
370 NodePair other = (NodePair) obj;
371 if (a == null) {
372 if (other.a != null)
373 return false;
374 } else if (!a.equals(other.a))
375 return false;
376 if (b == null) {
377 if (other.b != null)
378 return false;
379 } else if (!b.equals(other.b))
380 return false;
381 return true;
382 }
383 }
384
385 static public class NodeGraph {
386 static public List<NodePair> buildNodePairs(Way way, boolean directed) {
387 ArrayList<NodePair> pairs = new ArrayList<NodePair>();
388 for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
389 pairs.add(new NodePair(pair));
390 if (!directed) {
391 pairs.add(new NodePair(pair).swap());
392 }
393 }
394 return pairs;
395 }
396
397 static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
398 ArrayList<NodePair> pairs = new ArrayList<NodePair>();
399 for (Way w: ways) {
400 pairs.addAll(buildNodePairs(w, directed));
401 }
402 return pairs;
403 }
404
405 static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
406 ArrayList<NodePair> cleaned = new ArrayList<NodePair>();
407 for(NodePair p: pairs) {
408 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
409 cleaned.add(p);
410 }
411 }
412 return cleaned;
413 }
414
415 static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
416 NodeGraph graph = new NodeGraph();
417 for (NodePair pair: pairs) {
418 graph.add(pair);
419 }
420 return graph;
421 }
422
423 static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
424 NodeGraph graph = new NodeGraph();
425 for (Way w: ways) {
426 graph.add(buildNodePairs(w, true /* directed */));
427 }
428 return graph;
429 }
430
431 static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
432 NodeGraph graph = new NodeGraph();
433 for (NodePair pair: pairs) {
434 graph.add(pair);
435 graph.add(pair.swap());
436 }
437 return graph;
438 }
439
440 static public NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
441 NodeGraph graph = new NodeGraph();
442 for (Way w: ways) {
443 graph.add(buildNodePairs(w, false /* undirected */));
444 }
445 return graph;
446 }
447
448 private Set<NodePair> edges;
449 private int numUndirectedEges = 0;
450 private HashMap<Node, List<NodePair>> successors;
451 private HashMap<Node, List<NodePair>> predecessors;
452
453 protected void rememberSuccessor(NodePair pair) {
454 if (successors.containsKey(pair.getA())) {
455 if (!successors.get(pair.getA()).contains(pair)) {
456 successors.get(pair.getA()).add(pair);
457 }
458 } else {
459 ArrayList<NodePair> l = new ArrayList<NodePair>();
460 l.add(pair);
461 successors.put(pair.getA(), l);
462 }
463 }
464
465 protected void rememberPredecessors(NodePair pair) {
466 if (predecessors.containsKey(pair.getB())) {
467 if (!predecessors.get(pair.getB()).contains(pair)) {
468 predecessors.get(pair.getB()).add(pair);
469 }
470 } else {
471 ArrayList<NodePair> l = new ArrayList<NodePair>();
472 l.add(pair);
473 predecessors.put(pair.getB(), l);
474 }
475 }
476
477 protected boolean isTerminalNode(Node n) {
478 if (successors.get(n) == null) return false;
479 if (successors.get(n).size() != 1) return false;
480 if (predecessors.get(n) == null) return true;
481 if (predecessors.get(n).size() == 1) {
482 NodePair p1 = successors.get(n).iterator().next();
483 NodePair p2 = predecessors.get(n).iterator().next();
484 return p1.equals(p2.swap());
485 }
486 return false;
487 }
488
489 protected void prepare() {
490 Set<NodePair> undirectedEdges = new LinkedHashSet<NodePair>();
491 successors = new LinkedHashMap<Node, List<NodePair>>();
492 predecessors = new LinkedHashMap<Node, List<NodePair>>();
493
494 for (NodePair pair: edges) {
495 if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
496 undirectedEdges.add(pair);
497 }
498 rememberSuccessor(pair);
499 rememberPredecessors(pair);
500 }
501 numUndirectedEges = undirectedEdges.size();
502 }
503
504 public NodeGraph() {
505 edges = new LinkedHashSet<NodePair>();
506 }
507
508 public void add(NodePair pair) {
509 if (!edges.contains(pair)) {
510 edges.add(pair);
511 }
512 }
513
514 public void add(List<NodePair> pairs) {
515 for (NodePair pair: pairs) {
516 add(pair);
517 }
518 }
519
520 protected Node getStartNode() {
521 Set<Node> nodes = getNodes();
522 for (Node n: nodes) {
523 if (successors.get(n) != null && successors.get(n).size() ==1)
524 return n;
525 }
526 return null;
527 }
528
529 protected Set<Node> getTerminalNodes() {
530 Set<Node> ret = new LinkedHashSet<Node>();
531 for (Node n: getNodes()) {
532 if (isTerminalNode(n)) {
533 ret.add(n);
534 }
535 }
536 return ret;
537 }
538
539 protected Set<Node> getNodes(Stack<NodePair> pairs) {
540 HashSet<Node> nodes = new LinkedHashSet<Node>();
541 for (NodePair pair: pairs) {
542 nodes.add(pair.getA());
543 nodes.add(pair.getB());
544 }
545 return nodes;
546 }
547
548 protected List<NodePair> getOutboundPairs(NodePair pair) {
549 return getOutboundPairs(pair.getB());
550 }
551
552 protected List<NodePair> getOutboundPairs(Node node) {
553 List<NodePair> l = successors.get(node);
554 if (l == null)
555 return Collections.emptyList();
556 return l;
557 }
558
559 protected Set<Node> getNodes() {
560 Set<Node> nodes = new LinkedHashSet<Node>();
561 for (NodePair pair: edges) {
562 nodes.add(pair.getA());
563 nodes.add(pair.getB());
564 }
565 return nodes;
566 }
567
568 protected boolean isSpanningWay(Stack<NodePair> way) {
569 return numUndirectedEges == way.size();
570 }
571
572 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
573 LinkedList<Node> ret = new LinkedList<Node>();
574 for (NodePair pair: path) {
575 ret.add(pair.getA());
576 }
577 ret.add(path.peek().getB());
578 return ret;
579 }
580
581 /**
582 * Tries to find a spanning path starting from node <code>startNode</code>.
583 *
584 * Traverses the path in depth-first order.
585 *
586 * @param startNode the start node
587 * @return the spanning path; null, if no path is found
588 */
589 protected List<Node> buildSpanningPath(Node startNode) {
590 if (startNode == null)
591 return null;
592 Stack<NodePair> path = new Stack<NodePair>();
593 Stack<NodePair> nextPairs = new Stack<NodePair>();
594 nextPairs.addAll(getOutboundPairs(startNode));
595 while(!nextPairs.isEmpty()) {
596 NodePair cur= nextPairs.pop();
597 if (! path.contains(cur) && ! path.contains(cur.swap())) {
598 while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
599 path.pop();
600 }
601 path.push(cur);
602 if (isSpanningWay(path)) return buildPathFromNodePairs(path);
603 nextPairs.addAll(getOutboundPairs(path.peek()));
604 }
605 }
606 return null;
607 }
608
609 /**
610 * Tries to find a path through the graph which visits each edge (i.e.
611 * the segment of a way) exactly one.
612 *
613 * @return the path; null, if no path was found
614 */
615 public List<Node> buildSpanningPath() {
616 prepare();
617 // try to find a path from each "terminal node", i.e. from a
618 // node which is connected by exactly one undirected edges (or
619 // two directed edges in opposite direction) to the graph. A
620 // graph built up from way segments is likely to include such
621 // nodes, unless all ways are closed.
622 // In the worst case this loops over all nodes which is
623 // very slow for large ways.
624 //
625 Set<Node> nodes = getTerminalNodes();
626 nodes = nodes.isEmpty() ? getNodes() : nodes;
627 for (Node n: nodes) {
628 List<Node> path = buildSpanningPath(n);
629 if (path != null)
630 return path;
631 }
632 return null;
633 }
634 }
635}
Note: See TracBrowser for help on using the repository browser.