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

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

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