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

Last change on this file since 2273 was 2273, checked in by jttt, 15 years ago

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