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

Last change on this file since 6106 was 6106, checked in by Don-vip, 11 years ago

see #8902 - Small performance enhancements / coding style (patch by shinigami):

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