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

Last change on this file since 2325 was 2323, checked in by Gubaer, 15 years ago

Added explicit help topics
See also current list of help topics with links to source files and to help pages
  • 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.help.HelpUtil.ht;
6import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.completeTagCollectionForEditing;
7import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.normalizeTagCollectionBeforeEditing;
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.Map;
20import java.util.Set;
21import java.util.Stack;
22
23import javax.swing.JOptionPane;
24import javax.swing.SwingUtilities;
25
26import org.openstreetmap.josm.Main;
27import org.openstreetmap.josm.command.ChangeCommand;
28import org.openstreetmap.josm.command.Command;
29import org.openstreetmap.josm.command.DeleteCommand;
30import org.openstreetmap.josm.command.SequenceCommand;
31import org.openstreetmap.josm.data.osm.DataSet;
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.RelationMember;
36import org.openstreetmap.josm.data.osm.TagCollection;
37import org.openstreetmap.josm.data.osm.Way;
38import org.openstreetmap.josm.gui.ExtendedDialog;
39import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
40import org.openstreetmap.josm.tools.Pair;
41import org.openstreetmap.josm.tools.Shortcut;
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 public void combineWays(Collection<Way> ways) {
94
95 // prepare and clean the list of ways to combine
96 //
97 if (ways == null || ways.isEmpty())
98 return;
99 ways.remove(null); // just in case - remove all null ways from the collection
100 ways = new HashSet<Way>(ways); // remove duplicates
101
102 // build the list of relations referring to the ways to combine
103 //
104 WayReferringRelations referringRelations = new WayReferringRelations(ways);
105 referringRelations.build(getCurrentDataSet());
106
107 // build the collection of tags used by the ways to combine
108 //
109 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
110
111 // try to build a new way which includes all the combined
112 // ways
113 //
114 NodeGraph graph = NodeGraph.createDirectedGraphFromWays(ways);
115 List<Node> path = graph.buildSpanningPath();
116 if (path == null) {
117 graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
118 path = graph.buildSpanningPath();
119 if (path != null) {
120 if (!confirmChangeDirectionOfWays())
121 return;
122 } else {
123 warnCombiningImpossible();
124 return;
125 }
126 }
127
128 // create the new way and apply the new node list
129 //
130 Way targetWay = getTargetWay(ways);
131 Way modifiedTargetWay = new Way(targetWay);
132 modifiedTargetWay.setNodes(path);
133
134 TagCollection completeWayTags = new TagCollection(wayTags);
135 combineTigerTags(completeWayTags);
136 normalizeTagCollectionBeforeEditing(completeWayTags, ways);
137 TagCollection tagsToEdit = new TagCollection(completeWayTags);
138 completeTagCollectionForEditing(tagsToEdit);
139
140 CombinePrimitiveResolverDialog dialog = CombinePrimitiveResolverDialog.getInstance();
141 dialog.getTagConflictResolverModel().populate(tagsToEdit, completeWayTags.getKeysWithMultipleValues());
142 dialog.setTargetPrimitive(targetWay);
143 dialog.getRelationMemberConflictResolverModel().populate(
144 referringRelations.getRelations(),
145 referringRelations.getWays()
146 );
147 dialog.prepareDefaultDecisions();
148
149 // resolve tag conflicts if necessary
150 //
151 if (!completeWayTags.isApplicableToPrimitive() || !referringRelations.getRelations().isEmpty()) {
152 dialog.setVisible(true);
153 if (dialog.isCancelled())
154 return;
155 }
156
157 LinkedList<Command> cmds = new LinkedList<Command>();
158 LinkedList<Way> deletedWays = new LinkedList<Way>(ways);
159 deletedWays.remove(targetWay);
160
161 cmds.add(new DeleteCommand(deletedWays));
162 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
163 cmds.addAll(dialog.buildResolutionCommands());
164 final SequenceCommand sequenceCommand = new SequenceCommand(tr("Combine {0} ways", ways.size()), cmds);
165
166 // update gui
167 final Way selectedWay = targetWay;
168 Runnable guiTask = new Runnable() {
169 public void run() {
170 Main.main.undoRedo.add(sequenceCommand);
171 getCurrentDataSet().setSelected(selectedWay);
172 }
173 };
174 if (SwingUtilities.isEventDispatchThread()) {
175 guiTask.run();
176 } else {
177 SwingUtilities.invokeLater(guiTask);
178 }
179 }
180
181 public void actionPerformed(ActionEvent event) {
182 if (getCurrentDataSet() == null)
183 return;
184 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
185 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
186 if (selectedWays.size() < 2) {
187 JOptionPane.showMessageDialog(
188 Main.parent,
189 tr("Please select at least two ways to combine."),
190 tr("Information"),
191 JOptionPane.INFORMATION_MESSAGE
192 );
193 return;
194 }
195 combineWays(selectedWays);
196 }
197
198 @Override
199 protected void updateEnabledState() {
200 if (getCurrentDataSet() == null) {
201 setEnabled(false);
202 return;
203 }
204 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
205 updateEnabledState(selection);
206 }
207
208 @Override
209 protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
210 int numWays = 0;
211 for (OsmPrimitive osm : selection)
212 if (osm instanceof Way) {
213 numWays++;
214 }
215 setEnabled(numWays >= 2);
216 }
217
218 /**
219 * This is a collection of relations referring to at least one out of a set of
220 * ways.
221 *
222 *
223 */
224 static private class WayReferringRelations {
225 /**
226 * the map references between relations and ways. The key is a ways, the value is a
227 * set of relations referring to that way.
228 */
229 private Map<Way, Set<Relation>> wayRelationMap;
230
231 /**
232 *
233 * @param ways a collection of ways
234 */
235 public WayReferringRelations(Collection<Way> ways) {
236 wayRelationMap = new HashMap<Way, Set<Relation>>();
237 if (ways == null) return;
238 ways.remove(null); // just in case - remove null values
239 for (Way way: ways) {
240 if (!wayRelationMap.containsKey(way)) {
241 wayRelationMap.put(way, new HashSet<Relation>());
242 }
243 }
244 }
245
246 /**
247 * build the sets of referring relations from the relations in the dataset <code>ds</code>
248 *
249 * @param ds the data set
250 */
251 public void build(DataSet ds) {
252 for (Relation r: ds.relations) {
253 if (!r.isUsable()) {
254 continue;
255 }
256 Set<Way> referringWays = OsmPrimitive.getFilteredSet(r.getMemberPrimitives(), Way.class);
257 for (Way w : wayRelationMap.keySet()) {
258 if (referringWays.contains(w)) {
259 wayRelationMap.get(w).add(r);
260 }
261 }
262 }
263 }
264
265 /**
266 * Replies the ways
267 * @return the ways
268 */
269 public Set<Way> getWays() {
270 return wayRelationMap.keySet();
271 }
272
273 /**
274 * Replies the set of referring relations
275 *
276 * @return the set of referring relations
277 */
278 public Set<Relation> getRelations() {
279 HashSet<Relation> ret = new HashSet<Relation>();
280 for (Way w: wayRelationMap.keySet()) {
281 ret.addAll(wayRelationMap.get(w));
282 }
283 return ret;
284 }
285
286 /**
287 * Replies the set of referring relations for a specific way
288 *
289 * @return the set of referring relations
290 */
291 public Set<Relation> getRelations(Way way) {
292 return wayRelationMap.get(way);
293 }
294
295 protected Command buildRelationUpdateCommand(Relation relation, Collection<Way> ways, Way targetWay) {
296 List<RelationMember> newMembers = new ArrayList<RelationMember>();
297 for (RelationMember rm : relation.getMembers()) {
298 if (ways.contains(rm.getMember())) {
299 RelationMember newMember = new RelationMember(rm.getRole(),targetWay);
300 newMembers.add(newMember);
301 } else {
302 newMembers.add(rm);
303 }
304 }
305 Relation newRelation = new Relation(relation);
306 newRelation.setMembers(newMembers);
307 return new ChangeCommand(relation, newRelation);
308 }
309
310 public List<Command> buildRelationUpdateCommands(Way targetWay) {
311 Collection<Way> toRemove = getWays();
312 toRemove.remove(targetWay);
313 ArrayList<Command> cmds = new ArrayList<Command>();
314 for (Relation r : getRelations()) {
315 Command cmd = buildRelationUpdateCommand(r, toRemove, targetWay);
316 cmds.add(cmd);
317 }
318 return cmds;
319 }
320 }
321
322 static public class NodePair {
323 private Node a;
324 private Node b;
325 public NodePair(Node a, Node b) {
326 this.a =a;
327 this.b = b;
328 }
329
330 public NodePair(Pair<Node,Node> pair) {
331 this.a = pair.a;
332 this.b = pair.b;
333 }
334
335 public NodePair(NodePair other) {
336 this.a = other.a;
337 this.b = other.b;
338 }
339
340 public Node getA() {
341 return a;
342 }
343
344 public Node getB() {
345 return b;
346 }
347
348 public boolean isAdjacentToA(NodePair other) {
349 return other.getA() == a || other.getB() == a;
350 }
351
352 public boolean isAdjacentToB(NodePair other) {
353 return other.getA() == b || other.getB() == b;
354 }
355
356 public boolean isSuccessorOf(NodePair other) {
357 return other.getB() == a;
358 }
359
360 public boolean isPredecessorOf(NodePair other) {
361 return b == other.getA();
362 }
363
364 public NodePair swap() {
365 return new NodePair(b,a);
366 }
367
368 @Override
369 public String toString() {
370 return new StringBuilder()
371 .append("[")
372 .append(a.getId())
373 .append(",")
374 .append(b.getId())
375 .append("]")
376 .toString();
377 }
378
379 public boolean contains(Node n) {
380 return a == n || b == n;
381 }
382
383 @Override
384 public int hashCode() {
385 final int prime = 31;
386 int result = 1;
387 result = prime * result + ((a == null) ? 0 : a.hashCode());
388 result = prime * result + ((b == null) ? 0 : b.hashCode());
389 return result;
390 }
391 @Override
392 public boolean equals(Object obj) {
393 if (this == obj)
394 return true;
395 if (obj == null)
396 return false;
397 if (getClass() != obj.getClass())
398 return false;
399 NodePair other = (NodePair) obj;
400 if (a == null) {
401 if (other.a != null)
402 return false;
403 } else if (!a.equals(other.a))
404 return false;
405 if (b == null) {
406 if (other.b != null)
407 return false;
408 } else if (!b.equals(other.b))
409 return false;
410 return true;
411 }
412 }
413
414
415 static public class NodeGraph {
416 static public List<NodePair> buildNodePairs(Way way, boolean directed) {
417 ArrayList<NodePair> pairs = new ArrayList<NodePair>();
418 for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
419 pairs.add(new NodePair(pair));
420 if (!directed) {
421 pairs.add(new NodePair(pair).swap());
422 }
423 }
424 return pairs;
425 }
426
427 static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
428 ArrayList<NodePair> pairs = new ArrayList<NodePair>();
429 for (Way w: ways) {
430 pairs.addAll(buildNodePairs(w, directed));
431 }
432 return pairs;
433 }
434
435 static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
436 ArrayList<NodePair> cleaned = new ArrayList<NodePair>();
437 for(NodePair p: pairs) {
438 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
439 cleaned.add(p);
440 }
441 }
442 return cleaned;
443 }
444
445 static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
446 NodeGraph graph = new NodeGraph();
447 for (NodePair pair: pairs) {
448 graph.add(pair);
449 }
450 return graph;
451 }
452
453 static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
454 NodeGraph graph = new NodeGraph();
455 for (Way w: ways) {
456 graph.add(buildNodePairs(w, true /* directed */));
457 }
458 return graph;
459 }
460
461 static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
462 NodeGraph graph = new NodeGraph();
463 for (NodePair pair: pairs) {
464 graph.add(pair);
465 graph.add(pair.swap());
466 }
467 return graph;
468 }
469
470 static public NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
471 NodeGraph graph = new NodeGraph();
472 for (Way w: ways) {
473 graph.add(buildNodePairs(w, false /* undirected */));
474 }
475 return graph;
476 }
477
478 private Set<NodePair> edges;
479 private int numUndirectedEges = 0;
480 private HashMap<Node, List<NodePair>> successors;
481 private HashMap<Node, List<NodePair>> predecessors;
482
483
484 protected void rememberSuccessor(NodePair pair) {
485 if (successors.containsKey(pair.getA())) {
486 if (!successors.get(pair.getA()).contains(pair)) {
487 successors.get(pair.getA()).add(pair);
488 }
489 } else {
490 ArrayList<NodePair> l = new ArrayList<NodePair>();
491 l.add(pair);
492 successors.put(pair.getA(), l);
493 }
494 }
495
496 protected void rememberPredecessors(NodePair pair) {
497 if (predecessors.containsKey(pair.getB())) {
498 if (!predecessors.get(pair.getB()).contains(pair)) {
499 predecessors.get(pair.getB()).add(pair);
500 }
501 } else {
502 ArrayList<NodePair> l = new ArrayList<NodePair>();
503 l.add(pair);
504 predecessors.put(pair.getB(), l);
505 }
506 }
507
508 protected boolean isTerminalNode(Node n) {
509 if (successors.get(n) == null) return false;
510 if (successors.get(n).size() != 1) return false;
511 if (predecessors.get(n) == null) return true;
512 if (predecessors.get(n).size() == 1) {
513 NodePair p1 = successors.get(n).iterator().next();
514 NodePair p2 = predecessors.get(n).iterator().next();
515 return p1.equals(p2.swap());
516 }
517 return false;
518 }
519
520 protected void prepare() {
521 Set<NodePair> undirectedEdges = new HashSet<NodePair>();
522 successors = new HashMap<Node, List<NodePair>>();
523 predecessors = new HashMap<Node, List<NodePair>>();
524
525 for (NodePair pair: edges) {
526 if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
527 undirectedEdges.add(pair);
528 }
529 rememberSuccessor(pair);
530 rememberPredecessors(pair);
531 }
532 numUndirectedEges = undirectedEdges.size();
533 }
534
535 public NodeGraph() {
536 edges = new HashSet<NodePair>();
537 }
538
539 public void add(NodePair pair) {
540 if (!edges.contains(pair)) {
541 edges.add(pair);
542 }
543 }
544
545 public void add(List<NodePair> pairs) {
546 for (NodePair pair: pairs) {
547 add(pair);
548 }
549 }
550
551 protected Node getStartNode() {
552 Set<Node> nodes = getNodes();
553 for (Node n: nodes) {
554 if (successors.get(n) != null && successors.get(n).size() ==1)
555 return n;
556 }
557 return null;
558 }
559
560 protected Set<Node> getTerminalNodes() {
561 Set<Node> ret = new HashSet<Node>();
562 for (Node n: getNodes()) {
563 if (isTerminalNode(n)) {
564 ret.add(n);
565 }
566 }
567 return ret;
568 }
569
570 protected Set<Node> getNodes(Stack<NodePair> pairs) {
571 HashSet<Node> nodes = new HashSet<Node>();
572 for (NodePair pair: pairs) {
573 nodes.add(pair.getA());
574 nodes.add(pair.getB());
575 }
576 return nodes;
577 }
578
579 protected List<NodePair> getOutboundPairs(NodePair pair) {
580 return getOutboundPairs(pair.getB());
581 }
582
583 protected List<NodePair> getOutboundPairs(Node node) {
584 List<NodePair> l = successors.get(node);
585 return l == null ? Collections.EMPTY_LIST : l;
586 }
587
588 protected Set<Node> getNodes() {
589 Set<Node> nodes = new HashSet<Node>();
590 for (NodePair pair: edges) {
591 nodes.add(pair.getA());
592 nodes.add(pair.getB());
593 }
594 return nodes;
595 }
596
597 protected boolean isSpanningWay(Stack<NodePair> way) {
598 return numUndirectedEges == way.size();
599 }
600
601 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
602 LinkedList<Node> ret = new LinkedList<Node>();
603 for (NodePair pair: path) {
604 ret.add(pair.getA());
605 }
606 ret.add(path.peek().getB());
607 return ret;
608 }
609
610 /**
611 * Tries to find a spanning path starting from node <code>startNode</code>.
612 *
613 * Traverses the path in depth-first order.
614 *
615 * @param startNode the start node
616 * @return the spanning path; null, if no path is found
617 */
618 protected List<Node> buildSpanningPath(Node startNode) {
619 if (startNode == null)
620 return null;
621 Stack<NodePair> path = new Stack<NodePair>();
622 Stack<NodePair> nextPairs = new Stack<NodePair>();
623 nextPairs.addAll(getOutboundPairs(startNode));
624 while(!nextPairs.isEmpty()) {
625 NodePair cur= nextPairs.pop();
626 if (! path.contains(cur) && ! path.contains(cur.swap())) {
627 while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
628 path.pop();
629 }
630 path.push(cur);
631 if (isSpanningWay(path)) return buildPathFromNodePairs(path);
632 nextPairs.addAll(getOutboundPairs(path.peek()));
633 }
634 }
635 return null;
636 }
637
638 /**
639 * Tries to find a path through the graph which visits each edge (i.e.
640 * the segment of a way) exactly one.
641 *
642 * @return the path; null, if no path was found
643 */
644 public List<Node> buildSpanningPath() {
645 prepare();
646 // try to find a path from each "terminal node", i.e. from a
647 // node which is connected by exactly one undirected edges (or
648 // two directed edges in opposite direction) to the graph. A
649 // graph built up from way segments is likely to include such
650 // nodes, unless all ways are closed.
651 // In the worst case this loops over all nodes which is
652 // very slow for large ways.
653 //
654 Set<Node> nodes = getTerminalNodes();
655 nodes = nodes.isEmpty() ? getNodes() : nodes;
656 for (Node n: nodes) {
657 List<Node> path = buildSpanningPath(n);
658 if (path != null)
659 return path;
660 }
661 return null;
662 }
663 }
664}
Note: See TracBrowser for help on using the repository browser.