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

Last change on this file since 2484 was 2381, checked in by jttt, 14 years ago

Change most occurrences of Dataset.nodes/ways/relations with getNodes()/../.. or addPrimitive
  • Property svn:eol-style set to native
File size: 22.6 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.getRelations()) {
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 if (l == null)
586 return Collections.emptyList();
587 return l;
588 }
589
590 protected Set<Node> getNodes() {
591 Set<Node> nodes = new HashSet<Node>();
592 for (NodePair pair: edges) {
593 nodes.add(pair.getA());
594 nodes.add(pair.getB());
595 }
596 return nodes;
597 }
598
599 protected boolean isSpanningWay(Stack<NodePair> way) {
600 return numUndirectedEges == way.size();
601 }
602
603 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
604 LinkedList<Node> ret = new LinkedList<Node>();
605 for (NodePair pair: path) {
606 ret.add(pair.getA());
607 }
608 ret.add(path.peek().getB());
609 return ret;
610 }
611
612 /**
613 * Tries to find a spanning path starting from node <code>startNode</code>.
614 *
615 * Traverses the path in depth-first order.
616 *
617 * @param startNode the start node
618 * @return the spanning path; null, if no path is found
619 */
620 protected List<Node> buildSpanningPath(Node startNode) {
621 if (startNode == null)
622 return null;
623 Stack<NodePair> path = new Stack<NodePair>();
624 Stack<NodePair> nextPairs = new Stack<NodePair>();
625 nextPairs.addAll(getOutboundPairs(startNode));
626 while(!nextPairs.isEmpty()) {
627 NodePair cur= nextPairs.pop();
628 if (! path.contains(cur) && ! path.contains(cur.swap())) {
629 while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
630 path.pop();
631 }
632 path.push(cur);
633 if (isSpanningWay(path)) return buildPathFromNodePairs(path);
634 nextPairs.addAll(getOutboundPairs(path.peek()));
635 }
636 }
637 return null;
638 }
639
640 /**
641 * Tries to find a path through the graph which visits each edge (i.e.
642 * the segment of a way) exactly one.
643 *
644 * @return the path; null, if no path was found
645 */
646 public List<Node> buildSpanningPath() {
647 prepare();
648 // try to find a path from each "terminal node", i.e. from a
649 // node which is connected by exactly one undirected edges (or
650 // two directed edges in opposite direction) to the graph. A
651 // graph built up from way segments is likely to include such
652 // nodes, unless all ways are closed.
653 // In the worst case this loops over all nodes which is
654 // very slow for large ways.
655 //
656 Set<Node> nodes = getTerminalNodes();
657 nodes = nodes.isEmpty() ? getNodes() : nodes;
658 for (Node n: nodes) {
659 List<Node> path = buildSpanningPath(n);
660 if (path != null)
661 return path;
662 }
663 return null;
664 }
665 }
666}
Note: See TracBrowser for help on using the repository browser.