001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.actions;
003
004import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
005import static org.openstreetmap.josm.tools.I18n.tr;
006
007import java.awt.event.ActionEvent;
008import java.awt.event.KeyEvent;
009import java.util.ArrayList;
010import java.util.Collection;
011import java.util.Collections;
012import java.util.HashSet;
013import java.util.LinkedHashMap;
014import java.util.LinkedHashSet;
015import java.util.LinkedList;
016import java.util.List;
017import java.util.Map;
018import java.util.Set;
019import java.util.Stack;
020
021import javax.swing.JOptionPane;
022
023import org.openstreetmap.josm.Main;
024import org.openstreetmap.josm.command.ChangeCommand;
025import org.openstreetmap.josm.command.Command;
026import org.openstreetmap.josm.command.DeleteCommand;
027import org.openstreetmap.josm.command.SequenceCommand;
028import org.openstreetmap.josm.corrector.ReverseWayTagCorrector;
029import org.openstreetmap.josm.corrector.UserCancelException;
030import org.openstreetmap.josm.data.osm.Node;
031import org.openstreetmap.josm.data.osm.OsmPrimitive;
032import org.openstreetmap.josm.data.osm.TagCollection;
033import org.openstreetmap.josm.data.osm.Way;
034import org.openstreetmap.josm.data.preferences.BooleanProperty;
035import org.openstreetmap.josm.gui.ExtendedDialog;
036import org.openstreetmap.josm.gui.Notification;
037import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
038import org.openstreetmap.josm.gui.util.GuiHelper;
039import org.openstreetmap.josm.tools.Pair;
040import org.openstreetmap.josm.tools.Shortcut;
041
042/**
043 * Combines multiple ways into one.
044 * @since 213
045 */
046public class CombineWayAction extends JosmAction {
047
048    private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true);
049
050    /**
051     * Constructs a new {@code CombineWayAction}.
052     */
053    public CombineWayAction() {
054        super(tr("Combine Way"), "combineway", tr("Combine several ways into one."),
055                Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.DIRECT), true);
056        putValue("help", ht("/Action/CombineWay"));
057    }
058
059    protected static boolean confirmChangeDirectionOfWays() {
060        ExtendedDialog ed = new ExtendedDialog(Main.parent,
061                tr("Change directions?"),
062                new String[] {tr("Reverse and Combine"), tr("Cancel")});
063        ed.setButtonIcons(new String[] {"wayflip.png", "cancel.png"});
064        ed.setContent(tr("The ways can not be combined in their current directions.  "
065                + "Do you want to reverse some of them?"));
066        ed.showDialog();
067        return ed.getValue() == 1;
068    }
069
070    protected static void warnCombiningImpossible() {
071        String msg = tr("Could not combine ways<br>"
072                + "(They could not be merged into a single string of nodes)");
073        new Notification(msg)
074                .setIcon(JOptionPane.INFORMATION_MESSAGE)
075                .show();
076        return;
077    }
078
079    protected static Way getTargetWay(Collection<Way> combinedWays) {
080        // init with an arbitrary way
081        Way targetWay = combinedWays.iterator().next();
082
083        // look for the first way already existing on
084        // the server
085        for (Way w : combinedWays) {
086            targetWay = w;
087            if (!w.isNew()) {
088                break;
089            }
090        }
091        return targetWay;
092    }
093
094    /**
095     * @param ways
096     * @return null if ways cannot be combined. Otherwise returns the combined
097     *              ways and the commands to combine
098     * @throws UserCancelException
099     */
100    public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException {
101
102        // prepare and clean the list of ways to combine
103        //
104        if (ways == null || ways.isEmpty())
105            return null;
106        ways.remove(null); // just in case -  remove all null ways from the collection
107
108        // remove duplicates, preserving order
109        ways = new LinkedHashSet<Way>(ways);
110
111        // try to build a new way which includes all the combined
112        // ways
113        //
114        NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
115        List<Node> path = graph.buildSpanningPath();
116        if (path == null) {
117            warnCombiningImpossible();
118            return null;
119        }
120        // check whether any ways have been reversed in the process
121        // and build the collection of tags used by the ways to combine
122        //
123        TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
124
125        List<Way> reversedWays = new LinkedList<Way>();
126        List<Way> unreversedWays = new LinkedList<Way>();
127        for (Way w: ways) {
128            // Treat zero or one-node ways as unreversed as Combine action action is a good way to fix them (see #8971)
129            if (w.getNodesCount() < 2 || (path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
130                unreversedWays.add(w);
131            } else {
132                reversedWays.add(w);
133            }
134        }
135        // reverse path if all ways have been reversed
136        if (unreversedWays.isEmpty()) {
137            Collections.reverse(path);
138            unreversedWays = reversedWays;
139            reversedWays = null;
140        }
141        if ((reversedWays != null) && !reversedWays.isEmpty()) {
142            if (!confirmChangeDirectionOfWays()) return null;
143            // filter out ways that have no direction-dependent tags
144            unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays);
145            reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays);
146            // reverse path if there are more reversed than unreversed ways with direction-dependent tags
147            if (reversedWays.size() > unreversedWays.size()) {
148                Collections.reverse(path);
149                List<Way> tempWays = unreversedWays;
150                unreversedWays = reversedWays;
151                reversedWays = tempWays;
152            }
153            // if there are still reversed ways with direction-dependent tags, reverse their tags
154            if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
155                List<Way> unreversedTagWays = new ArrayList<Way>(ways);
156                unreversedTagWays.removeAll(reversedWays);
157                ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
158                List<Way> reversedTagWays = new ArrayList<Way>(reversedWays.size());
159                Collection<Command> changePropertyCommands =  null;
160                for (Way w : reversedWays) {
161                    Way wnew = new Way(w);
162                    reversedTagWays.add(wnew);
163                    changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
164                }
165                if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
166                    for (Command c : changePropertyCommands) {
167                        c.executeCommand();
168                    }
169                }
170                wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
171                wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
172            }
173        }
174
175        // create the new way and apply the new node list
176        //
177        Way targetWay = getTargetWay(ways);
178        Way modifiedTargetWay = new Way(targetWay);
179        modifiedTargetWay.setNodes(path);
180
181        List<Command> resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay));
182
183        LinkedList<Command> cmds = new LinkedList<Command>();
184        LinkedList<Way> deletedWays = new LinkedList<Way>(ways);
185        deletedWays.remove(targetWay);
186
187        cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
188        cmds.addAll(resolution);
189        cmds.add(new DeleteCommand(deletedWays));
190        final SequenceCommand sequenceCommand = new SequenceCommand(tr("Combine {0} ways", ways.size()), cmds);
191
192        return new Pair<Way, Command>(targetWay, sequenceCommand);
193    }
194
195    @Override
196    public void actionPerformed(ActionEvent event) {
197        if (getCurrentDataSet() == null)
198            return;
199        Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
200        Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
201        if (selectedWays.size() < 2) {
202            new Notification(
203                    tr("Please select at least two ways to combine."))
204                    .setIcon(JOptionPane.INFORMATION_MESSAGE)
205                    .setDuration(Notification.TIME_SHORT)
206                    .show();
207            return;
208        }
209        // combine and update gui
210        Pair<Way, Command> combineResult;
211        try {
212            combineResult = combineWaysWorker(selectedWays);
213        } catch (UserCancelException ex) {
214            return;
215        }
216
217        if (combineResult == null)
218            return;
219        final Way selectedWay = combineResult.a;
220        Main.main.undoRedo.add(combineResult.b);
221        if(selectedWay != null)
222        {
223            Runnable guiTask = new Runnable() {
224                @Override
225                public void run() {
226                    getCurrentDataSet().setSelected(selectedWay);
227                }
228            };
229            GuiHelper.runInEDT(guiTask);
230        }
231    }
232
233    @Override
234    protected void updateEnabledState() {
235        if (getCurrentDataSet() == null) {
236            setEnabled(false);
237            return;
238        }
239        Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
240        updateEnabledState(selection);
241    }
242
243    @Override
244    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
245        int numWays = 0;
246        for (OsmPrimitive osm : selection)
247            if (osm instanceof Way) {
248                numWays++;
249            }
250        setEnabled(numWays >= 2);
251    }
252
253    /**
254     * A pair of nodes.
255     */
256    static public class NodePair {
257        private final Node a;
258        private final Node b;
259        
260        /**
261         * Constructs a new {@code NodePair}.
262         * @param a The first node
263         * @param b The second node
264         */
265        public NodePair(Node a, Node b) {
266            this.a = a;
267            this.b = b;
268        }
269
270        /**
271         * Constructs a new {@code NodePair}.
272         * @param pair An existing {@code Pair} of nodes
273         */
274        public NodePair(Pair<Node,Node> pair) {
275            this(pair.a, pair.b);
276        }
277
278        /**
279         * Constructs a new {@code NodePair}.
280         * @param other An existing {@code NodePair}
281         */
282        public NodePair(NodePair other) {
283            this(other.a, other.b);
284        }
285
286        /**
287         * Replies the first node.
288         * @return The first node
289         */
290        public Node getA() {
291            return a;
292        }
293
294        /**
295         * Replies the second node
296         * @return The second node
297         */
298        public Node getB() {
299            return b;
300        }
301
302        public boolean isAdjacentToA(NodePair other) {
303            return other.getA() == a || other.getB() == a;
304        }
305
306        public boolean isAdjacentToB(NodePair other) {
307            return other.getA() == b || other.getB() == b;
308        }
309
310        public boolean isSuccessorOf(NodePair other) {
311            return other.getB() == a;
312        }
313
314        public boolean isPredecessorOf(NodePair other) {
315            return b == other.getA();
316        }
317
318        public NodePair swap() {
319            return new NodePair(b,a);
320        }
321
322        @Override
323        public String toString() {
324            return new StringBuilder()
325            .append("[")
326            .append(a.getId())
327            .append(",")
328            .append(b.getId())
329            .append("]")
330            .toString();
331        }
332
333        /**
334         * Determines if this pair contains the given node.
335         * @param n The node to look for
336         * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
337         */
338        public boolean contains(Node n) {
339            return a == n || b == n;
340        }
341
342        @Override
343        public int hashCode() {
344            final int prime = 31;
345            int result = 1;
346            result = prime * result + ((a == null) ? 0 : a.hashCode());
347            result = prime * result + ((b == null) ? 0 : b.hashCode());
348            return result;
349        }
350        
351        @Override
352        public boolean equals(Object obj) {
353            if (this == obj)
354                return true;
355            if (obj == null)
356                return false;
357            if (getClass() != obj.getClass())
358                return false;
359            NodePair other = (NodePair) obj;
360            if (a == null) {
361                if (other.a != null)
362                    return false;
363            } else if (!a.equals(other.a))
364                return false;
365            if (b == null) {
366                if (other.b != null)
367                    return false;
368            } else if (!b.equals(other.b))
369                return false;
370            return true;
371        }
372    }
373
374    static public class NodeGraph {
375        static public List<NodePair> buildNodePairs(Way way, boolean directed) {
376            List<NodePair> pairs = new ArrayList<NodePair>();
377            for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
378                pairs.add(new NodePair(pair));
379                if (!directed) {
380                    pairs.add(new NodePair(pair).swap());
381                }
382            }
383            return pairs;
384        }
385
386        static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
387            List<NodePair> pairs = new ArrayList<NodePair>();
388            for (Way w: ways) {
389                pairs.addAll(buildNodePairs(w, directed));
390            }
391            return pairs;
392        }
393
394        static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
395            List<NodePair> cleaned = new ArrayList<NodePair>();
396            for(NodePair p: pairs) {
397                if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
398                    cleaned.add(p);
399                }
400            }
401            return cleaned;
402        }
403
404        static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
405            NodeGraph graph = new NodeGraph();
406            for (NodePair pair: pairs) {
407                graph.add(pair);
408            }
409            return graph;
410        }
411
412        static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
413            NodeGraph graph = new NodeGraph();
414            for (Way w: ways) {
415                graph.add(buildNodePairs(w, true /* directed */));
416            }
417            return graph;
418        }
419
420        static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
421            NodeGraph graph = new NodeGraph();
422            for (NodePair pair: pairs) {
423                graph.add(pair);
424                graph.add(pair.swap());
425            }
426            return graph;
427        }
428
429        public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
430            NodeGraph graph = new NodeGraph();
431            for (Way w: ways) {
432                graph.add(buildNodePairs(w, false /* undirected */));
433            }
434            return graph;
435        }
436
437        private Set<NodePair> edges;
438        private int numUndirectedEges = 0;
439        private Map<Node, List<NodePair>> successors;
440        private Map<Node, List<NodePair>> predecessors;
441
442        protected void rememberSuccessor(NodePair pair) {
443            if (successors.containsKey(pair.getA())) {
444                if (!successors.get(pair.getA()).contains(pair)) {
445                    successors.get(pair.getA()).add(pair);
446                }
447            } else {
448                List<NodePair> l = new ArrayList<NodePair>();
449                l.add(pair);
450                successors.put(pair.getA(), l);
451            }
452        }
453
454        protected void rememberPredecessors(NodePair pair) {
455            if (predecessors.containsKey(pair.getB())) {
456                if (!predecessors.get(pair.getB()).contains(pair)) {
457                    predecessors.get(pair.getB()).add(pair);
458                }
459            } else {
460                List<NodePair> l = new ArrayList<NodePair>();
461                l.add(pair);
462                predecessors.put(pair.getB(), l);
463            }
464        }
465
466        protected boolean isTerminalNode(Node n) {
467            if (successors.get(n) == null) return false;
468            if (successors.get(n).size() != 1) return false;
469            if (predecessors.get(n) == null) return true;
470            if (predecessors.get(n).size() == 1) {
471                NodePair p1 = successors.get(n).iterator().next();
472                NodePair p2 = predecessors.get(n).iterator().next();
473                return p1.equals(p2.swap());
474            }
475            return false;
476        }
477
478        protected void prepare() {
479            Set<NodePair> undirectedEdges = new LinkedHashSet<NodePair>();
480            successors = new LinkedHashMap<Node, List<NodePair>>();
481            predecessors = new LinkedHashMap<Node, List<NodePair>>();
482
483            for (NodePair pair: edges) {
484                if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
485                    undirectedEdges.add(pair);
486                }
487                rememberSuccessor(pair);
488                rememberPredecessors(pair);
489            }
490            numUndirectedEges = undirectedEdges.size();
491        }
492
493        /**
494         * Constructs a new {@code NodeGraph}.
495         */
496        public NodeGraph() {
497            edges = new LinkedHashSet<NodePair>();
498        }
499
500        public void add(NodePair pair) {
501            if (!edges.contains(pair)) {
502                edges.add(pair);
503            }
504        }
505
506        public void add(List<NodePair> pairs) {
507            for (NodePair pair: pairs) {
508                add(pair);
509            }
510        }
511
512        protected Node getStartNode() {
513            Set<Node> nodes = getNodes();
514            for (Node n: nodes) {
515                if (successors.get(n) != null && successors.get(n).size() ==1)
516                    return n;
517            }
518            return null;
519        }
520
521        protected Set<Node> getTerminalNodes() {
522            Set<Node> ret = new LinkedHashSet<Node>();
523            for (Node n: getNodes()) {
524                if (isTerminalNode(n)) {
525                    ret.add(n);
526                }
527            }
528            return ret;
529        }
530
531        protected Set<Node> getNodes(Stack<NodePair> pairs) {
532            HashSet<Node> nodes = new LinkedHashSet<Node>(2*pairs.size());
533            for (NodePair pair: pairs) {
534                nodes.add(pair.getA());
535                nodes.add(pair.getB());
536            }
537            return nodes;
538        }
539
540        protected List<NodePair> getOutboundPairs(NodePair pair) {
541            return getOutboundPairs(pair.getB());
542        }
543
544        protected List<NodePair> getOutboundPairs(Node node) {
545            List<NodePair> l = successors.get(node);
546            if (l == null)
547                return Collections.emptyList();
548            return l;
549        }
550
551        protected Set<Node> getNodes() {
552            Set<Node> nodes = new LinkedHashSet<Node>(2 * edges.size());
553            for (NodePair pair: edges) {
554                nodes.add(pair.getA());
555                nodes.add(pair.getB());
556            }
557            return nodes;
558        }
559
560        protected boolean isSpanningWay(Stack<NodePair> way) {
561            return numUndirectedEges == way.size();
562        }
563
564        protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
565            LinkedList<Node> ret = new LinkedList<Node>();
566            for (NodePair pair: path) {
567                ret.add(pair.getA());
568            }
569            ret.add(path.peek().getB());
570            return ret;
571        }
572
573        /**
574         * Tries to find a spanning path starting from node <code>startNode</code>.
575         *
576         * Traverses the path in depth-first order.
577         *
578         * @param startNode the start node
579         * @return the spanning path; null, if no path is found
580         */
581        protected List<Node> buildSpanningPath(Node startNode) {
582            if (startNode == null)
583                return null;
584            Stack<NodePair> path = new Stack<NodePair>();
585            Stack<NodePair> nextPairs  = new Stack<NodePair>();
586            nextPairs.addAll(getOutboundPairs(startNode));
587            while(!nextPairs.isEmpty()) {
588                NodePair cur= nextPairs.pop();
589                if (! path.contains(cur) && ! path.contains(cur.swap())) {
590                    while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
591                        path.pop();
592                    }
593                    path.push(cur);
594                    if (isSpanningWay(path)) return buildPathFromNodePairs(path);
595                    nextPairs.addAll(getOutboundPairs(path.peek()));
596                }
597            }
598            return null;
599        }
600
601        /**
602         * Tries to find a path through the graph which visits each edge (i.e.
603         * the segment of a way) exactly one.
604         *
605         * @return the path; null, if no path was found
606         */
607        public List<Node> buildSpanningPath() {
608            prepare();
609            // try to find a path from each "terminal node", i.e. from a
610            // node which is connected by exactly one undirected edges (or
611            // two directed edges in opposite direction) to the graph. A
612            // graph built up from way segments is likely to include such
613            // nodes, unless all ways are closed.
614            // In the worst case this loops over all nodes which is
615            // very slow for large ways.
616            //
617            Set<Node> nodes = getTerminalNodes();
618            nodes = nodes.isEmpty() ? getNodes() : nodes;
619            for (Node n: nodes) {
620                List<Node> path = buildSpanningPath(n);
621                if (path != null)
622                    return path;
623            }
624            return null;
625        }
626    }
627}