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

Last change on this file since 2564 was 2564, checked in by Gubaer, 14 years ago

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