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

Last change on this file since 2876 was 2711, checked in by stoecker, 14 years ago

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