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

Last change on this file since 2136 was 2120, checked in by stoecker, 15 years ago

see #3475 - patch by Petr Dlouhý - code rework for display filtering
  • Property svn:eol-style set to native
File size: 21.4 KB
Line 
1// License: GPL. Copyright 2007 by Immanuel Scholz and others
2package org.openstreetmap.josm.actions;
3
4import static org.openstreetmap.josm.tools.I18n.tr;
5
6import java.awt.event.ActionEvent;
7import java.awt.event.KeyEvent;
8import java.util.ArrayList;
9import java.util.Collection;
10import java.util.HashMap;
11import java.util.HashSet;
12import java.util.LinkedList;
13import java.util.List;
14import java.util.Map;
15import java.util.Set;
16import java.util.Stack;
17
18import javax.swing.JOptionPane;
19import javax.swing.SwingUtilities;
20
21import org.openstreetmap.josm.Main;
22import org.openstreetmap.josm.command.ChangeCommand;
23import org.openstreetmap.josm.command.Command;
24import org.openstreetmap.josm.command.DeleteCommand;
25import org.openstreetmap.josm.command.SequenceCommand;
26import org.openstreetmap.josm.data.osm.DataSet;
27import org.openstreetmap.josm.data.osm.Node;
28import org.openstreetmap.josm.data.osm.OsmPrimitive;
29import org.openstreetmap.josm.data.osm.Relation;
30import org.openstreetmap.josm.data.osm.RelationMember;
31import org.openstreetmap.josm.data.osm.Tag;
32import org.openstreetmap.josm.data.osm.TagCollection;
33import org.openstreetmap.josm.data.osm.Way;
34import org.openstreetmap.josm.gui.ExtendedDialog;
35import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
36import org.openstreetmap.josm.tools.Pair;
37import org.openstreetmap.josm.tools.Shortcut;
38
39/**
40 * Combines multiple ways into one.
41 *
42 */
43public class CombineWayAction extends JosmAction {
44
45 public CombineWayAction() {
46 super(tr("Combine Way"), "combineway", tr("Combine several ways into one."),
47 Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.GROUP_EDIT), true);
48 }
49
50 protected Set<OsmPrimitive> intersect(Set<? extends OsmPrimitive> s1, Set<? extends OsmPrimitive> s2) {
51 HashSet<OsmPrimitive> ret = new HashSet<OsmPrimitive>(s1);
52 ret.retainAll(s2);
53 return ret;
54 }
55
56 protected boolean confirmCombiningWithConflictsInRelationMemberships() {
57 ExtendedDialog ed = new ExtendedDialog(Main.parent,
58 tr("Combine ways with different memberships?"),
59 new String[] {tr("Combine Anyway"), tr("Cancel")});
60 ed.setButtonIcons(new String[] {"combineway.png", "cancel.png"});
61 ed.setContent(tr("The selected ways have differing relation memberships. "
62 + "Do you still want to combine them?"));
63 ed.showDialog();
64
65 return ed.getValue() == 1;
66 }
67
68 protected boolean confirmChangeDirectionOfWays() {
69 ExtendedDialog ed = new ExtendedDialog(Main.parent,
70 tr("Change directions?"),
71 new String[] {tr("Reverse and Combine"), tr("Cancel")});
72 ed.setButtonIcons(new String[] {"wayflip.png", "cancel.png"});
73 ed.setContent(tr("The ways can not be combined in their current directions. "
74 + "Do you want to reverse some of them?"));
75 ed.showDialog();
76 return ed.getValue() == 1;
77 }
78
79 protected void warnCombiningImpossible() {
80 String msg = tr("Could not combine ways "
81 + "(They could not be merged into a single string of nodes)");
82 JOptionPane.showMessageDialog(
83 Main.parent,
84 msg, //FIXME: not sure whether this fits in a dialog
85 tr("Information"),
86 JOptionPane.INFORMATION_MESSAGE
87 );
88 return;
89 }
90
91 protected Way getTargetWay(Collection<Way> combinedWays) {
92 // init with an arbitrary way
93 Way targetWay = combinedWays.iterator().next();
94
95 // look for the first way already existing on
96 // the server
97 for (Way w : combinedWays) {
98 targetWay = w;
99 if (w.getId() != 0) {
100 break;
101 }
102 }
103 return targetWay;
104 }
105
106 protected static void completeTagCollectionWithMissingTags(TagCollection tc, Collection<? extends OsmPrimitive> merged) {
107 for (String key: tc.getKeys()) {
108 // make sure the empty value is in the tag set if a tag is not present
109 // on all merged nodes
110 //
111 for (OsmPrimitive p: merged) {
112 if (p.get(key) == null) {
113 tc.add(new Tag(key)); // add a tag with key and empty value
114 }
115 }
116 }
117 // remove irrelevant tags
118 //
119 tc.removeByKey("created_by");
120 }
121
122 protected static void completeTagCollectionForEditing(TagCollection tc) {
123 for (String key: tc.getKeys()) {
124 // make sure the empty value is in the tag set such that we can delete the tag
125 // in the conflict dialog if necessary
126 //
127 tc.add(new Tag(key,""));
128 }
129 }
130
131 public void combineWays(Collection<Way> ways) {
132
133 // prepare and clean the list of ways to combine
134 //
135 if (ways == null || ways.isEmpty())
136 return;
137 ways.remove(null); // just in case - remove all null ways from the collection
138 ways = new HashSet<Way>(ways); // remove duplicates
139
140 // build the list of relations referring to the ways to combine
141 //
142 WayReferringRelations referringRelations = new WayReferringRelations(ways);
143 referringRelations.build(getCurrentDataSet());
144
145 // build the collection of tags used by the ways to combine
146 //
147 TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
148
149
150 // try to build a new way out of the combination of ways
151 // which are combined
152 //
153 NodeGraph graph = NodeGraph.createDirectedGraphFromWays(ways);
154 List<Node> path = graph.buildSpanningPath();
155 if (path == null) {
156 graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
157 path = graph.buildSpanningPath();
158 if (path != null) {
159 if (!confirmChangeDirectionOfWays())
160 return;
161 } else {
162 warnCombiningImpossible();
163 return;
164 }
165 }
166
167 // create the new way and apply the new node list
168 //
169 Way targetWay = getTargetWay(ways);
170 Way modifiedTargetWay = new Way(targetWay);
171 modifiedTargetWay.setNodes(path);
172
173 TagCollection completeWayTags = new TagCollection(wayTags);
174 completeTagCollectionWithMissingTags(completeWayTags, ways);
175 TagCollection tagsToEdit = new TagCollection(completeWayTags);
176 completeTagCollectionForEditing(tagsToEdit);
177
178 CombinePrimitiveResolverDialog dialog = CombinePrimitiveResolverDialog.getInstance();
179 dialog.getTagConflictResolverModel().populate(tagsToEdit);
180 dialog.setTargetPrimitive(targetWay);
181 dialog.getRelationMemberConflictResolverModel().populate(
182 referringRelations.getRelations(),
183 referringRelations.getWays()
184 );
185 dialog.prepareDefaultDecisions();
186
187 // resolve tag conflicts if necessary
188 //
189 if (!completeWayTags.isApplicableToPrimitive() || !referringRelations.getRelations().isEmpty()) {
190 dialog.setVisible(true);
191 if (dialog.isCancelled())
192 return;
193 }
194
195 LinkedList<Command> cmds = new LinkedList<Command>();
196 LinkedList<Way> deletedWays = new LinkedList<Way>(ways);
197 deletedWays.remove(targetWay);
198
199 cmds.add(new DeleteCommand(deletedWays));
200 cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
201 cmds.addAll(dialog.buildResolutionCommands());
202 final SequenceCommand sequenceCommand = new SequenceCommand(tr("Combine {0} ways", ways.size()), cmds);
203
204 // update gui
205 final Way selectedWay = targetWay;
206 Runnable guiTask = new Runnable() {
207 public void run() {
208 Main.main.undoRedo.add(sequenceCommand);
209 getCurrentDataSet().setSelected(selectedWay);
210 }
211 };
212 if (SwingUtilities.isEventDispatchThread()) {
213 guiTask.run();
214 } else {
215 SwingUtilities.invokeLater(guiTask);
216 }
217 }
218
219
220 public void actionPerformed(ActionEvent event) {
221 if (getCurrentDataSet() == null)
222 return;
223 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
224 Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
225 if (selectedWays.size() < 2) {
226 JOptionPane.showMessageDialog(
227 Main.parent,
228 tr("Please select at least two ways to combine."),
229 tr("Information"),
230 JOptionPane.INFORMATION_MESSAGE
231 );
232 return;
233 }
234 combineWays(selectedWays);
235 }
236
237 @Override
238 protected void updateEnabledState() {
239 if (getCurrentDataSet() == null) {
240 setEnabled(false);
241 return;
242 }
243 Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
244 int numWays = 0;
245
246 for (OsmPrimitive osm : selection)
247 if (osm instanceof Way) {
248 numWays++;
249 }
250 setEnabled(numWays >= 2);
251 }
252
253 /**
254 * This is a collection of relations referring to at least one out of a set of
255 * ways.
256 *
257 *
258 */
259 static private class WayReferringRelations {
260 /**
261 * the map references between relations and ways. The key is a ways, the value is a
262 * set of relations referring to that way.
263 */
264 private Map<Way, Set<Relation>> wayRelationMap;
265
266 /**
267 *
268 * @param ways a collection of ways
269 */
270 public WayReferringRelations(Collection<Way> ways) {
271 wayRelationMap = new HashMap<Way, Set<Relation>>();
272 if (ways == null) return;
273 ways.remove(null); // just in case - remove null values
274 for (Way way: ways) {
275 if (!wayRelationMap.containsKey(way)) {
276 wayRelationMap.put(way, new HashSet<Relation>());
277 }
278 }
279 }
280
281 /**
282 * build the sets of referring relations from the relations in the dataset <code>ds</code>
283 *
284 * @param ds the data set
285 */
286 public void build(DataSet ds) {
287 for (Relation r: ds.relations) {
288 if (!r.isUsable()) {
289 continue;
290 }
291 Set<Way> referringWays = OsmPrimitive.getFilteredSet(r.getMemberPrimitives(), Way.class);
292 for (Way w : wayRelationMap.keySet()) {
293 if (referringWays.contains(w)) {
294 wayRelationMap.get(w).add(r);
295 }
296 }
297 }
298 }
299
300 /**
301 * Replies the ways
302 * @return the ways
303 */
304 public Set<Way> getWays() {
305 return wayRelationMap.keySet();
306 }
307
308 /**
309 * Replies the set of referring relations
310 *
311 * @return the set of referring relations
312 */
313 public Set<Relation> getRelations() {
314 HashSet<Relation> ret = new HashSet<Relation>();
315 for (Way w: wayRelationMap.keySet()) {
316 ret.addAll(wayRelationMap.get(w));
317 }
318 return ret;
319 }
320
321 /**
322 * Replies the set of referring relations for a specific way
323 *
324 * @return the set of referring relations
325 */
326 public Set<Relation> getRelations(Way way) {
327 return wayRelationMap.get(way);
328 }
329
330 protected Command buildRelationUpdateCommand(Relation relation, Collection<Way> ways, Way targetWay) {
331 List<RelationMember> newMembers = new ArrayList<RelationMember>();
332 for (RelationMember rm : relation.getMembers()) {
333 if (ways.contains(rm.getMember())) {
334 RelationMember newMember = new RelationMember(rm.getRole(),targetWay);
335 newMembers.add(newMember);
336 } else {
337 newMembers.add(rm);
338 }
339 }
340 Relation newRelation = new Relation(relation);
341 newRelation.setMembers(newMembers);
342 return new ChangeCommand(relation, newRelation);
343 }
344
345 public List<Command> buildRelationUpdateCommands(Way targetWay) {
346 Collection<Way> toRemove = getWays();
347 toRemove.remove(targetWay);
348 ArrayList<Command> cmds = new ArrayList<Command>();
349 for (Relation r : getRelations()) {
350 Command cmd = buildRelationUpdateCommand(r, toRemove, targetWay);
351 cmds.add(cmd);
352 }
353 return cmds;
354 }
355 }
356
357 static public class NodePair {
358 private Node a;
359 private Node b;
360 public NodePair(Node a, Node b) {
361 this.a =a;
362 this.b = b;
363 }
364
365 public NodePair(Pair<Node,Node> pair) {
366 this.a = pair.a;
367 this.b = pair.b;
368 }
369
370 public NodePair(NodePair other) {
371 this.a = other.a;
372 this.b = other.b;
373 }
374
375 public Node getA() {
376 return a;
377 }
378
379 public Node getB() {
380 return b;
381 }
382
383 public boolean isAdjacentToA(NodePair other) {
384 return other.getA() == a || other.getB() == a;
385 }
386
387 public boolean isAdjacentToB(NodePair other) {
388 return other.getA() == b || other.getB() == b;
389 }
390
391 public boolean isSuccessorOf(NodePair other) {
392 return other.getB() == a;
393 }
394
395 public boolean isPredecessorOf(NodePair other) {
396 return b == other.getA();
397 }
398
399 public NodePair swap() {
400 return new NodePair(b,a);
401 }
402
403 @Override
404 public String toString() {
405 return new StringBuilder()
406 .append("[")
407 .append(a.getId())
408 .append(",")
409 .append(b.getId())
410 .append("]")
411 .toString();
412 }
413
414 public boolean contains(Node n) {
415 return a == n || b == n;
416 }
417
418 @Override
419 public int hashCode() {
420 final int prime = 31;
421 int result = 1;
422 result = prime * result + ((a == null) ? 0 : a.hashCode());
423 result = prime * result + ((b == null) ? 0 : b.hashCode());
424 return result;
425 }
426 @Override
427 public boolean equals(Object obj) {
428 if (this == obj)
429 return true;
430 if (obj == null)
431 return false;
432 if (getClass() != obj.getClass())
433 return false;
434 NodePair other = (NodePair) obj;
435 if (a == null) {
436 if (other.a != null)
437 return false;
438 } else if (!a.equals(other.a))
439 return false;
440 if (b == null) {
441 if (other.b != null)
442 return false;
443 } else if (!b.equals(other.b))
444 return false;
445 return true;
446 }
447 }
448
449
450 static public class NodeGraph {
451 static public List<NodePair> buildNodePairs(Way way, boolean directed) {
452 ArrayList<NodePair> pairs = new ArrayList<NodePair>();
453 for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
454 pairs.add(new NodePair(pair));
455 if (!directed) {
456 pairs.add(new NodePair(pair).swap());
457 }
458 }
459 return pairs;
460 }
461
462 static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
463 ArrayList<NodePair> pairs = new ArrayList<NodePair>();
464 for (Way w: ways) {
465 pairs.addAll(buildNodePairs(w, directed));
466 }
467 return pairs;
468 }
469
470 static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
471 ArrayList<NodePair> cleaned = new ArrayList<NodePair>();
472 for(NodePair p: pairs) {
473 if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
474 cleaned.add(p);
475 }
476 }
477 return cleaned;
478 }
479
480 static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
481 NodeGraph graph = new NodeGraph();
482 for (NodePair pair: pairs) {
483 graph.add(pair);
484 }
485 return graph;
486 }
487
488 static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
489 NodeGraph graph = new NodeGraph();
490 for (Way w: ways) {
491 graph.add(buildNodePairs(w, true /* directed */));
492 }
493 return graph;
494 }
495
496 static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
497 NodeGraph graph = new NodeGraph();
498 for (NodePair pair: pairs) {
499 graph.add(pair);
500 graph.add(pair.swap());
501 }
502 return graph;
503 }
504
505 static public NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
506 NodeGraph graph = new NodeGraph();
507 for (Way w: ways) {
508 graph.add(buildNodePairs(w, false /* undirected */));
509 }
510 return graph;
511 }
512
513 private Set<NodePair> edges;
514 private int numUndirectedEges = 0;
515
516 protected void computeNumEdges() {
517 Set<NodePair> undirectedEdges = new HashSet<NodePair>();
518 for (NodePair pair: edges) {
519 if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
520 undirectedEdges.add(pair);
521 }
522 }
523 numUndirectedEges = undirectedEdges.size();
524 }
525
526 public NodeGraph() {
527 edges = new HashSet<NodePair>();
528 }
529
530 public void add(NodePair pair) {
531 if (!edges.contains(pair)) {
532 edges.add(pair);
533 }
534 }
535
536 public void add(List<NodePair> pairs) {
537 for (NodePair pair: pairs) {
538 add(pair);
539 }
540 }
541
542 protected Node getStartNode() {
543 return edges.iterator().next().getA();
544 }
545
546 protected Set<Node> getNodes(Stack<NodePair> pairs) {
547 HashSet<Node> nodes = new HashSet<Node>();
548 for (NodePair pair: pairs) {
549 nodes.add(pair.getA());
550 nodes.add(pair.getB());
551 }
552 return nodes;
553 }
554
555 protected List<NodePair> getOutboundPairs(NodePair pair) {
556 LinkedList<NodePair> outbound = new LinkedList<NodePair>();
557 for (NodePair candidate:edges) {
558 if (candidate.equals(pair)) {
559 continue;
560 }
561 if (candidate.isSuccessorOf(pair)) {
562 outbound.add(candidate);
563 }
564 }
565 return outbound;
566 }
567
568 protected List<NodePair> getOutboundPairs(Node node) {
569 LinkedList<NodePair> outbound = new LinkedList<NodePair>();
570 for (NodePair candidate:edges) {
571 if (candidate.getA() == node) {
572 outbound.add(candidate);
573 }
574 }
575 return outbound;
576 }
577
578 protected Set<Node> getNodes() {
579 Set<Node> nodes = new HashSet<Node>();
580 for (NodePair pair: edges) {
581 nodes.add(pair.getA());
582 nodes.add(pair.getB());
583 }
584 return nodes;
585 }
586
587 protected boolean isSpanningWay(Stack<NodePair> way) {
588 return numUndirectedEges == way.size();
589 }
590
591
592 protected boolean advance(Stack<NodePair> path) {
593 // found a spanning path ?
594 //
595 if (isSpanningWay(path))
596 return true;
597
598 // advance with one of the possible follow up nodes
599 //
600 Stack<NodePair> nextPairs = new Stack<NodePair>();
601 nextPairs.addAll(getOutboundPairs(path.peek()));
602 while(!nextPairs.isEmpty()) {
603 NodePair next = nextPairs.pop();
604 if (path.contains(next) || path.contains(next.swap())) {
605 continue;
606 }
607 path.push(next);
608 if (advance(path)) return true;
609 path.pop();
610 }
611 return false;
612 }
613
614 protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
615 LinkedList<Node> ret = new LinkedList<Node>();
616 for (NodePair pair: path) {
617 ret.add(pair.getA());
618 }
619 ret.add(path.peek().getB());
620 return ret;
621 }
622
623 protected List<Node> buildSpanningPath(Node startNode) {
624 if (startNode == null)
625 return null;
626 Stack<NodePair> path = new Stack<NodePair>();
627 // advance with one of the possible follow up nodes
628 //
629 Stack<NodePair> nextPairs = new Stack<NodePair>();
630 nextPairs.addAll(getOutboundPairs(startNode));
631 while(!nextPairs.isEmpty()) {
632 path.push(nextPairs.pop());
633 if (advance(path))
634 return buildPathFromNodePairs(path);
635 path.pop();
636 }
637 return null;
638 }
639
640 public List<Node> buildSpanningPath() {
641 computeNumEdges();
642 for (Node n : getNodes()) {
643 List<Node> path = buildSpanningPath(n);
644 if (path != null)
645 return path;
646 }
647 return null;
648 }
649 }
650}
Note: See TracBrowser for help on using the repository browser.