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

Last change on this file since 3775 was 3510, checked in by bastiK, 14 years ago

fix rework [3504] (see #5179)
  • Property svn:eol-style set to native
File size: 22.8 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.GROUP_EDIT), 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 @Deprecated
111 public static Way combineWays(Collection<Way> ways) {
112 Pair<Way, Command> combineResult;
113 try {
114 combineResult = combineWaysWorker(ways);
115 } catch (UserCancelException ex) {
116 return null;
117 }
118 Main.main.undoRedo.add(combineResult.b);
119 return combineResult.a;
120 }
121
122 /**
123 * @param ways
124 * @return null if ways cannot be combined. Otherwise returns the combined
125 * ways and the commands to combine
126 * @throws UserCancelException
127 */
128 public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException {
129
130 // prepare and clean the list of ways to combine
131 //
132 if (ways == null || ways.isEmpty())
133 return null;
134 ways.remove(null); // just in case - remove all null ways from the collection
135
136 // remove duplicates, preserving order
137 ways = new LinkedHashSet<Way>(ways);
138
139 // try to build a new way which includes all the combined
140 // ways
141 //
142 NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
143 List<Node> path = graph.buildSpanningPath();
144 if (path == null) {
145 warnCombiningImpossible();
146 return null;
147 }
148 // check whether any ways have been reversed in the process
149 // and build the collection of tags used by the ways to combine
150 //
151 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
152
153 List<Way> reversedWays = new LinkedList<Way>();
154 List<Way> unreversedWays = new LinkedList<Way>();
155 for (Way w: ways) {
156 if ((path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
157 unreversedWays.add(w);
158 } else {
159 reversedWays.add(w);
160 }
161 }
162 // reverse path if all ways have been reversed
163 if (unreversedWays.isEmpty()) {
164 Collections.reverse(path);
165 unreversedWays = reversedWays;
166 reversedWays = null;
167 }
168 if ((reversedWays != null) && !reversedWays.isEmpty()) {
169 if (!confirmChangeDirectionOfWays()) return null;
170 // filter out ways that have no direction-dependent tags
171 unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays);
172 reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays);
173 // reverse path if there are more reversed than unreversed ways with direction-dependent tags
174 if (reversedWays.size() > unreversedWays.size()) {
175 Collections.reverse(path);
176 List<Way> tempWays = unreversedWays;
177 unreversedWays = reversedWays;
178 reversedWays = tempWays;
179 }
180 // if there are still reversed ways with direction-dependent tags, reverse their tags
181 if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
182 List<Way> unreversedTagWays = new ArrayList<Way>(ways);
183 unreversedTagWays.removeAll(reversedWays);
184 ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
185 List<Way> reversedTagWays = new ArrayList<Way>();
186 Collection<Command> changePropertyCommands = null;
187 for (Way w : reversedWays) {
188 Way wnew = new Way(w);
189 reversedTagWays.add(wnew);
190 changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
191 }
192 if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
193 for (Command c : changePropertyCommands) {
194 c.executeCommand();
195 }
196 }
197 wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
198 wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
199 }
200 }
201
202 // create the new way and apply the new node list
203 //
204 Way targetWay = getTargetWay(ways);
205 Way modifiedTargetWay = new Way(targetWay);
206 modifiedTargetWay.setNodes(path);
207
208 TagCollection completeWayTags = new TagCollection(wayTags);
209 combineTigerTags(completeWayTags);
210 normalizeTagCollectionBeforeEditing(completeWayTags, ways);
211 TagCollection tagsToEdit = new TagCollection(completeWayTags);
212 completeTagCollectionForEditing(tagsToEdit);
213
214 CombinePrimitiveResolverDialog dialog = CombinePrimitiveResolverDialog.getInstance();
215 dialog.getTagConflictResolverModel().populate(tagsToEdit, completeWayTags.getKeysWithMultipleValues());
216 dialog.setTargetPrimitive(targetWay);
217 Set<Relation> parentRelations = getParentRelations(ways);
218 dialog.getRelationMemberConflictResolverModel().populate(
219 parentRelations,
220 ways
221 );
222 dialog.prepareDefaultDecisions();
223
224 // resolve tag conflicts if necessary
225 //
226 if (!completeWayTags.isApplicableToPrimitive() || !parentRelations.isEmpty()) {
227 dialog.setVisible(true);
228 if (dialog.isCancelled())
229 throw new UserCancelException();
230 }
231
232 LinkedList<Command> cmds = new LinkedList<Command>();
233 LinkedList<Way> deletedWays = new LinkedList<Way>(ways);
234 deletedWays.remove(targetWay);
235
236 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
237 cmds.addAll(dialog.buildResolutionCommands());
238 cmds.add(new DeleteCommand(deletedWays));
239 final SequenceCommand sequenceCommand = new SequenceCommand(tr("Combine {0} ways", ways.size()), cmds);
240
241 return new Pair<Way, Command>(targetWay, sequenceCommand);
242 }
243
244 public void actionPerformed(ActionEvent event) {
245 if (getCurrentDataSet() == null)
246 return;
247 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
248 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
249 if (selectedWays.size() < 2) {
250 JOptionPane.showMessageDialog(
251 Main.parent,
252 tr("Please select at least two ways to combine."),
253 tr("Information"),
254 JOptionPane.INFORMATION_MESSAGE
255 );
256 return;
257 }
258 // combine and update gui
259 Pair<Way, Command> combineResult;
260 try {
261 combineResult = combineWaysWorker(selectedWays);
262 } catch (UserCancelException ex) {
263 return;
264 }
265
266 if (combineResult == null)
267 return;
268 final Way selectedWay = combineResult.a;
269 Main.main.undoRedo.add(combineResult.b);
270 if(selectedWay != null)
271 {
272 Runnable guiTask = new Runnable() {
273 public void run() {
274 getCurrentDataSet().setSelected(selectedWay);
275 }
276 };
277 if (SwingUtilities.isEventDispatchThread()) {
278 guiTask.run();
279 } else {
280 SwingUtilities.invokeLater(guiTask);
281 }
282 }
283 }
284
285 @Override
286 protected void updateEnabledState() {
287 if (getCurrentDataSet() == null) {
288 setEnabled(false);
289 return;
290 }
291 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
292 updateEnabledState(selection);
293 }
294
295 @Override
296 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
297 int numWays = 0;
298 for (OsmPrimitive osm : selection)
299 if (osm instanceof Way) {
300 numWays++;
301 }
302 setEnabled(numWays >= 2);
303 }
304
305 static public class NodePair {
306 private Node a;
307 private Node b;
308 public NodePair(Node a, Node b) {
309 this.a =a;
310 this.b = b;
311 }
312
313 public NodePair(Pair<Node,Node> pair) {
314 this.a = pair.a;
315 this.b = pair.b;
316 }
317
318 public NodePair(NodePair other) {
319 this.a = other.a;
320 this.b = other.b;
321 }
322
323 public Node getA() {
324 return a;
325 }
326
327 public Node getB() {
328 return b;
329 }
330
331 public boolean isAdjacentToA(NodePair other) {
332 return other.getA() == a || other.getB() == a;
333 }
334
335 public boolean isAdjacentToB(NodePair other) {
336 return other.getA() == b || other.getB() == b;
337 }
338
339 public boolean isSuccessorOf(NodePair other) {
340 return other.getB() == a;
341 }
342
343 public boolean isPredecessorOf(NodePair other) {
344 return b == other.getA();
345 }
346
347 public NodePair swap() {
348 return new NodePair(b,a);
349 }
350
351 @Override
352 public String toString() {
353 return new StringBuilder()
354 .append("[")
355 .append(a.getId())
356 .append(",")
357 .append(b.getId())
358 .append("]")
359 .toString();
360 }
361
362 public boolean contains(Node n) {
363 return a == n || b == n;
364 }
365
366 @Override
367 public int hashCode() {
368 final int prime = 31;
369 int result = 1;
370 result = prime * result + ((a == null) ? 0 : a.hashCode());
371 result = prime * result + ((b == null) ? 0 : b.hashCode());
372 return result;
373 }
374 @Override
375 public boolean equals(Object obj) {
376 if (this == obj)
377 return true;
378 if (obj == null)
379 return false;
380 if (getClass() != obj.getClass())
381 return false;
382 NodePair other = (NodePair) obj;
383 if (a == null) {
384 if (other.a != null)
385 return false;
386 } else if (!a.equals(other.a))
387 return false;
388 if (b == null) {
389 if (other.b != null)
390 return false;
391 } else if (!b.equals(other.b))
392 return false;
393 return true;
394 }
395 }
396
397 static public class NodeGraph {
398 static public List<NodePair> buildNodePairs(Way way, boolean directed) {
399 ArrayList<NodePair> pairs = new ArrayList<NodePair>();
400 for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
401 pairs.add(new NodePair(pair));
402 if (!directed) {
403 pairs.add(new NodePair(pair).swap());
404 }
405 }
406 return pairs;
407 }
408
409 static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
410 ArrayList<NodePair> pairs = new ArrayList<NodePair>();
411 for (Way w: ways) {
412 pairs.addAll(buildNodePairs(w, directed));
413 }
414 return pairs;
415 }
416
417 static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
418 ArrayList<NodePair> cleaned = new ArrayList<NodePair>();
419 for(NodePair p: pairs) {
420 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
421 cleaned.add(p);
422 }
423 }
424 return cleaned;
425 }
426
427 static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
428 NodeGraph graph = new NodeGraph();
429 for (NodePair pair: pairs) {
430 graph.add(pair);
431 }
432 return graph;
433 }
434
435 static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
436 NodeGraph graph = new NodeGraph();
437 for (Way w: ways) {
438 graph.add(buildNodePairs(w, true /* directed */));
439 }
440 return graph;
441 }
442
443 static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
444 NodeGraph graph = new NodeGraph();
445 for (NodePair pair: pairs) {
446 graph.add(pair);
447 graph.add(pair.swap());
448 }
449 return graph;
450 }
451
452 static public NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
453 NodeGraph graph = new NodeGraph();
454 for (Way w: ways) {
455 graph.add(buildNodePairs(w, false /* undirected */));
456 }
457 return graph;
458 }
459
460 private Set<NodePair> edges;
461 private int numUndirectedEges = 0;
462 private HashMap<Node, List<NodePair>> successors;
463 private HashMap<Node, List<NodePair>> predecessors;
464
465 protected void rememberSuccessor(NodePair pair) {
466 if (successors.containsKey(pair.getA())) {
467 if (!successors.get(pair.getA()).contains(pair)) {
468 successors.get(pair.getA()).add(pair);
469 }
470 } else {
471 ArrayList<NodePair> l = new ArrayList<NodePair>();
472 l.add(pair);
473 successors.put(pair.getA(), l);
474 }
475 }
476
477 protected void rememberPredecessors(NodePair pair) {
478 if (predecessors.containsKey(pair.getB())) {
479 if (!predecessors.get(pair.getB()).contains(pair)) {
480 predecessors.get(pair.getB()).add(pair);
481 }
482 } else {
483 ArrayList<NodePair> l = new ArrayList<NodePair>();
484 l.add(pair);
485 predecessors.put(pair.getB(), l);
486 }
487 }
488
489 protected boolean isTerminalNode(Node n) {
490 if (successors.get(n) == null) return false;
491 if (successors.get(n).size() != 1) return false;
492 if (predecessors.get(n) == null) return true;
493 if (predecessors.get(n).size() == 1) {
494 NodePair p1 = successors.get(n).iterator().next();
495 NodePair p2 = predecessors.get(n).iterator().next();
496 return p1.equals(p2.swap());
497 }
498 return false;
499 }
500
501 protected void prepare() {
502 Set<NodePair> undirectedEdges = new LinkedHashSet<NodePair>();
503 successors = new LinkedHashMap<Node, List<NodePair>>();
504 predecessors = new LinkedHashMap<Node, List<NodePair>>();
505
506 for (NodePair pair: edges) {
507 if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
508 undirectedEdges.add(pair);
509 }
510 rememberSuccessor(pair);
511 rememberPredecessors(pair);
512 }
513 numUndirectedEges = undirectedEdges.size();
514 }
515
516 public NodeGraph() {
517 edges = new LinkedHashSet<NodePair>();
518 }
519
520 public void add(NodePair pair) {
521 if (!edges.contains(pair)) {
522 edges.add(pair);
523 }
524 }
525
526 public void add(List<NodePair> pairs) {
527 for (NodePair pair: pairs) {
528 add(pair);
529 }
530 }
531
532 protected Node getStartNode() {
533 Set<Node> nodes = getNodes();
534 for (Node n: nodes) {
535 if (successors.get(n) != null && successors.get(n).size() ==1)
536 return n;
537 }
538 return null;
539 }
540
541 protected Set<Node> getTerminalNodes() {
542 Set<Node> ret = new LinkedHashSet<Node>();
543 for (Node n: getNodes()) {
544 if (isTerminalNode(n)) {
545 ret.add(n);
546 }
547 }
548 return ret;
549 }
550
551 protected Set<Node> getNodes(Stack<NodePair> pairs) {
552 HashSet<Node> nodes = new LinkedHashSet<Node>();
553 for (NodePair pair: pairs) {
554 nodes.add(pair.getA());
555 nodes.add(pair.getB());
556 }
557 return nodes;
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<Node>();
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(Stack<NodePair> way) {
581 return numUndirectedEges == way.size();
582 }
583
584 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
585 LinkedList<Node> ret = new LinkedList<Node>();
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 Stack<NodePair> path = new Stack<NodePair>();
605 Stack<NodePair> nextPairs = new Stack<NodePair>();
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 one.
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
635 // very slow for large ways.
636 //
637 Set<Node> nodes = getTerminalNodes();
638 nodes = nodes.isEmpty() ? getNodes() : nodes;
639 for (Node n: nodes) {
640 List<Node> path = buildSpanningPath(n);
641 if (path != null)
642 return path;
643 }
644 return null;
645 }
646 }
647}
Note: See TracBrowser for help on using the repository browser.