001    // License: GPL. Copyright 2007 by Immanuel Scholz and others
002    package org.openstreetmap.josm.actions;
003    
004    import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
005    import static org.openstreetmap.josm.tools.I18n.tr;
006    
007    import java.awt.event.ActionEvent;
008    import java.awt.event.KeyEvent;
009    import java.util.ArrayList;
010    import java.util.Collection;
011    import java.util.Collections;
012    import java.util.HashMap;
013    import java.util.HashSet;
014    import java.util.LinkedHashMap;
015    import java.util.LinkedHashSet;
016    import java.util.LinkedList;
017    import java.util.List;
018    import java.util.Set;
019    import java.util.Stack;
020    
021    import javax.swing.JOptionPane;
022    
023    import org.openstreetmap.josm.Main;
024    import org.openstreetmap.josm.command.ChangeCommand;
025    import org.openstreetmap.josm.command.Command;
026    import org.openstreetmap.josm.command.DeleteCommand;
027    import org.openstreetmap.josm.command.SequenceCommand;
028    import org.openstreetmap.josm.corrector.ReverseWayTagCorrector;
029    import org.openstreetmap.josm.corrector.UserCancelException;
030    import org.openstreetmap.josm.data.osm.Node;
031    import org.openstreetmap.josm.data.osm.OsmPrimitive;
032    import org.openstreetmap.josm.data.osm.TagCollection;
033    import org.openstreetmap.josm.data.osm.Way;
034    import org.openstreetmap.josm.data.preferences.BooleanProperty;
035    import org.openstreetmap.josm.gui.ExtendedDialog;
036    import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
037    import org.openstreetmap.josm.gui.util.GuiHelper;
038    import org.openstreetmap.josm.tools.Pair;
039    import org.openstreetmap.josm.tools.Shortcut;
040    
041    /**
042     * Combines multiple ways into one.
043     *
044     */
045    public class CombineWayAction extends JosmAction {
046    
047        private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true);
048    
049        public CombineWayAction() {
050            super(tr("Combine Way"), "combineway", tr("Combine several ways into one."),
051                    Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.DIRECT), true);
052            putValue("help", ht("/Action/CombineWay"));
053        }
054    
055        protected static boolean confirmChangeDirectionOfWays() {
056            ExtendedDialog ed = new ExtendedDialog(Main.parent,
057                    tr("Change directions?"),
058                    new String[] {tr("Reverse and Combine"), tr("Cancel")});
059            ed.setButtonIcons(new String[] {"wayflip.png", "cancel.png"});
060            ed.setContent(tr("The ways can not be combined in their current directions.  "
061                    + "Do you want to reverse some of them?"));
062            ed.showDialog();
063            return ed.getValue() == 1;
064        }
065    
066        protected static void warnCombiningImpossible() {
067            String msg = tr("Could not combine ways "
068                    + "(They could not be merged into a single string of nodes)");
069            JOptionPane.showMessageDialog(
070                    Main.parent,
071                    msg,
072                    tr("Information"),
073                    JOptionPane.INFORMATION_MESSAGE
074            );
075            return;
076        }
077    
078        protected static Way getTargetWay(Collection<Way> combinedWays) {
079            // init with an arbitrary way
080            Way targetWay = combinedWays.iterator().next();
081    
082            // look for the first way already existing on
083            // the server
084            for (Way w : combinedWays) {
085                targetWay = w;
086                if (!w.isNew()) {
087                    break;
088                }
089            }
090            return targetWay;
091        }
092    
093        /**
094         * @param ways
095         * @return null if ways cannot be combined. Otherwise returns the combined
096         *              ways and the commands to combine
097         * @throws UserCancelException
098         */
099        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>();
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        public void actionPerformed(ActionEvent event) {
194            if (getCurrentDataSet() == null)
195                return;
196            Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
197            Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
198            if (selectedWays.size() < 2) {
199                JOptionPane.showMessageDialog(
200                        Main.parent,
201                        tr("Please select at least two ways to combine."),
202                        tr("Information"),
203                        JOptionPane.INFORMATION_MESSAGE
204                );
205                return;
206            }
207            // combine and update gui
208            Pair<Way, Command> combineResult;
209            try {
210                combineResult = combineWaysWorker(selectedWays);
211            } catch (UserCancelException ex) {
212                return;
213            }
214    
215            if (combineResult == null)
216                return;
217            final Way selectedWay = combineResult.a;
218            Main.main.undoRedo.add(combineResult.b);
219            if(selectedWay != null)
220            {
221                Runnable guiTask = new Runnable() {
222                    public void run() {
223                        getCurrentDataSet().setSelected(selectedWay);
224                    }
225                };
226                GuiHelper.runInEDT(guiTask);
227            }
228        }
229    
230        @Override
231        protected void updateEnabledState() {
232            if (getCurrentDataSet() == null) {
233                setEnabled(false);
234                return;
235            }
236            Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
237            updateEnabledState(selection);
238        }
239    
240        @Override
241        protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
242            int numWays = 0;
243            for (OsmPrimitive osm : selection)
244                if (osm instanceof Way) {
245                    numWays++;
246                }
247            setEnabled(numWays >= 2);
248        }
249    
250        static public class NodePair {
251            private Node a;
252            private Node b;
253            public NodePair(Node a, Node b) {
254                this.a =a;
255                this.b = b;
256            }
257    
258            public NodePair(Pair<Node,Node> pair) {
259                this.a = pair.a;
260                this.b = pair.b;
261            }
262    
263            public NodePair(NodePair other) {
264                this.a = other.a;
265                this.b = other.b;
266            }
267    
268            public Node getA() {
269                return a;
270            }
271    
272            public Node getB() {
273                return b;
274            }
275    
276            public boolean isAdjacentToA(NodePair other) {
277                return other.getA() == a || other.getB() == a;
278            }
279    
280            public boolean isAdjacentToB(NodePair other) {
281                return other.getA() == b || other.getB() == b;
282            }
283    
284            public boolean isSuccessorOf(NodePair other) {
285                return other.getB() == a;
286            }
287    
288            public boolean isPredecessorOf(NodePair other) {
289                return b == other.getA();
290            }
291    
292            public NodePair swap() {
293                return new NodePair(b,a);
294            }
295    
296            @Override
297            public String toString() {
298                return new StringBuilder()
299                .append("[")
300                .append(a.getId())
301                .append(",")
302                .append(b.getId())
303                .append("]")
304                .toString();
305            }
306    
307            public boolean contains(Node n) {
308                return a == n || b == n;
309            }
310    
311            @Override
312            public int hashCode() {
313                final int prime = 31;
314                int result = 1;
315                result = prime * result + ((a == null) ? 0 : a.hashCode());
316                result = prime * result + ((b == null) ? 0 : b.hashCode());
317                return result;
318            }
319            @Override
320            public boolean equals(Object obj) {
321                if (this == obj)
322                    return true;
323                if (obj == null)
324                    return false;
325                if (getClass() != obj.getClass())
326                    return false;
327                NodePair other = (NodePair) obj;
328                if (a == null) {
329                    if (other.a != null)
330                        return false;
331                } else if (!a.equals(other.a))
332                    return false;
333                if (b == null) {
334                    if (other.b != null)
335                        return false;
336                } else if (!b.equals(other.b))
337                    return false;
338                return true;
339            }
340        }
341    
342        static public class NodeGraph {
343            static public List<NodePair> buildNodePairs(Way way, boolean directed) {
344                ArrayList<NodePair> pairs = new ArrayList<NodePair>();
345                for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
346                    pairs.add(new NodePair(pair));
347                    if (!directed) {
348                        pairs.add(new NodePair(pair).swap());
349                    }
350                }
351                return pairs;
352            }
353    
354            static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
355                ArrayList<NodePair> pairs = new ArrayList<NodePair>();
356                for (Way w: ways) {
357                    pairs.addAll(buildNodePairs(w, directed));
358                }
359                return pairs;
360            }
361    
362            static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
363                ArrayList<NodePair> cleaned = new ArrayList<NodePair>();
364                for(NodePair p: pairs) {
365                    if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
366                        cleaned.add(p);
367                    }
368                }
369                return cleaned;
370            }
371    
372            static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
373                NodeGraph graph = new NodeGraph();
374                for (NodePair pair: pairs) {
375                    graph.add(pair);
376                }
377                return graph;
378            }
379    
380            static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
381                NodeGraph graph = new NodeGraph();
382                for (Way w: ways) {
383                    graph.add(buildNodePairs(w, true /* directed */));
384                }
385                return graph;
386            }
387    
388            static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
389                NodeGraph graph = new NodeGraph();
390                for (NodePair pair: pairs) {
391                    graph.add(pair);
392                    graph.add(pair.swap());
393                }
394                return graph;
395            }
396    
397            static public NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
398                NodeGraph graph = new NodeGraph();
399                for (Way w: ways) {
400                    graph.add(buildNodePairs(w, false /* undirected */));
401                }
402                return graph;
403            }
404    
405            private Set<NodePair> edges;
406            private int numUndirectedEges = 0;
407            private HashMap<Node, List<NodePair>> successors;
408            private HashMap<Node, List<NodePair>> predecessors;
409    
410            protected void rememberSuccessor(NodePair pair) {
411                if (successors.containsKey(pair.getA())) {
412                    if (!successors.get(pair.getA()).contains(pair)) {
413                        successors.get(pair.getA()).add(pair);
414                    }
415                } else {
416                    ArrayList<NodePair> l = new ArrayList<NodePair>();
417                    l.add(pair);
418                    successors.put(pair.getA(), l);
419                }
420            }
421    
422            protected void rememberPredecessors(NodePair pair) {
423                if (predecessors.containsKey(pair.getB())) {
424                    if (!predecessors.get(pair.getB()).contains(pair)) {
425                        predecessors.get(pair.getB()).add(pair);
426                    }
427                } else {
428                    ArrayList<NodePair> l = new ArrayList<NodePair>();
429                    l.add(pair);
430                    predecessors.put(pair.getB(), l);
431                }
432            }
433    
434            protected boolean isTerminalNode(Node n) {
435                if (successors.get(n) == null) return false;
436                if (successors.get(n).size() != 1) return false;
437                if (predecessors.get(n) == null) return true;
438                if (predecessors.get(n).size() == 1) {
439                    NodePair p1 = successors.get(n).iterator().next();
440                    NodePair p2 = predecessors.get(n).iterator().next();
441                    return p1.equals(p2.swap());
442                }
443                return false;
444            }
445    
446            protected void prepare() {
447                Set<NodePair> undirectedEdges = new LinkedHashSet<NodePair>();
448                successors = new LinkedHashMap<Node, List<NodePair>>();
449                predecessors = new LinkedHashMap<Node, List<NodePair>>();
450    
451                for (NodePair pair: edges) {
452                    if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
453                        undirectedEdges.add(pair);
454                    }
455                    rememberSuccessor(pair);
456                    rememberPredecessors(pair);
457                }
458                numUndirectedEges = undirectedEdges.size();
459            }
460    
461            public NodeGraph() {
462                edges = new LinkedHashSet<NodePair>();
463            }
464    
465            public void add(NodePair pair) {
466                if (!edges.contains(pair)) {
467                    edges.add(pair);
468                }
469            }
470    
471            public void add(List<NodePair> pairs) {
472                for (NodePair pair: pairs) {
473                    add(pair);
474                }
475            }
476    
477            protected Node getStartNode() {
478                Set<Node> nodes = getNodes();
479                for (Node n: nodes) {
480                    if (successors.get(n) != null && successors.get(n).size() ==1)
481                        return n;
482                }
483                return null;
484            }
485    
486            protected Set<Node> getTerminalNodes() {
487                Set<Node> ret = new LinkedHashSet<Node>();
488                for (Node n: getNodes()) {
489                    if (isTerminalNode(n)) {
490                        ret.add(n);
491                    }
492                }
493                return ret;
494            }
495    
496            protected Set<Node> getNodes(Stack<NodePair> pairs) {
497                HashSet<Node> nodes = new LinkedHashSet<Node>();
498                for (NodePair pair: pairs) {
499                    nodes.add(pair.getA());
500                    nodes.add(pair.getB());
501                }
502                return nodes;
503            }
504    
505            protected List<NodePair> getOutboundPairs(NodePair pair) {
506                return getOutboundPairs(pair.getB());
507            }
508    
509            protected List<NodePair> getOutboundPairs(Node node) {
510                List<NodePair> l = successors.get(node);
511                if (l == null)
512                    return Collections.emptyList();
513                return l;
514            }
515    
516            protected Set<Node> getNodes() {
517                Set<Node> nodes = new LinkedHashSet<Node>();
518                for (NodePair pair: edges) {
519                    nodes.add(pair.getA());
520                    nodes.add(pair.getB());
521                }
522                return nodes;
523            }
524    
525            protected boolean isSpanningWay(Stack<NodePair> way) {
526                return numUndirectedEges == way.size();
527            }
528    
529            protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
530                LinkedList<Node> ret = new LinkedList<Node>();
531                for (NodePair pair: path) {
532                    ret.add(pair.getA());
533                }
534                ret.add(path.peek().getB());
535                return ret;
536            }
537    
538            /**
539             * Tries to find a spanning path starting from node <code>startNode</code>.
540             *
541             * Traverses the path in depth-first order.
542             *
543             * @param startNode the start node
544             * @return the spanning path; null, if no path is found
545             */
546            protected List<Node> buildSpanningPath(Node startNode) {
547                if (startNode == null)
548                    return null;
549                Stack<NodePair> path = new Stack<NodePair>();
550                Stack<NodePair> nextPairs  = new Stack<NodePair>();
551                nextPairs.addAll(getOutboundPairs(startNode));
552                while(!nextPairs.isEmpty()) {
553                    NodePair cur= nextPairs.pop();
554                    if (! path.contains(cur) && ! path.contains(cur.swap())) {
555                        while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
556                            path.pop();
557                        }
558                        path.push(cur);
559                        if (isSpanningWay(path)) return buildPathFromNodePairs(path);
560                        nextPairs.addAll(getOutboundPairs(path.peek()));
561                    }
562                }
563                return null;
564            }
565    
566            /**
567             * Tries to find a path through the graph which visits each edge (i.e.
568             * the segment of a way) exactly one.
569             *
570             * @return the path; null, if no path was found
571             */
572            public List<Node> buildSpanningPath() {
573                prepare();
574                // try to find a path from each "terminal node", i.e. from a
575                // node which is connected by exactly one undirected edges (or
576                // two directed edges in opposite direction) to the graph. A
577                // graph built up from way segments is likely to include such
578                // nodes, unless all ways are closed.
579                // In the worst case this loops over all nodes which is
580                // very slow for large ways.
581                //
582                Set<Node> nodes = getTerminalNodes();
583                nodes = nodes.isEmpty() ? getNodes() : nodes;
584                for (Node n: nodes) {
585                    List<Node> path = buildSpanningPath(n);
586                    if (path != null)
587                        return path;
588                }
589                return null;
590            }
591        }
592    }