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;
006import static org.openstreetmap.josm.tools.I18n.trn;
007
008import java.awt.event.ActionEvent;
009import java.awt.event.KeyEvent;
010import java.util.ArrayList;
011import java.util.Collection;
012import java.util.Collections;
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.data.osm.Node;
030import org.openstreetmap.josm.data.osm.OsmPrimitive;
031import org.openstreetmap.josm.data.osm.TagCollection;
032import org.openstreetmap.josm.data.osm.Way;
033import org.openstreetmap.josm.data.preferences.BooleanProperty;
034import org.openstreetmap.josm.gui.ExtendedDialog;
035import org.openstreetmap.josm.gui.Notification;
036import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
037import org.openstreetmap.josm.gui.util.GuiHelper;
038import org.openstreetmap.josm.tools.Pair;
039import org.openstreetmap.josm.tools.Shortcut;
040import org.openstreetmap.josm.tools.UserCancelException;
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", "cancel"});
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.toggleEnable("combineway-reverse");
067        ed.showDialog();
068        return ed.getValue() == 1;
069    }
070
071    protected static void warnCombiningImpossible() {
072        String msg = tr("Could not combine ways<br>"
073                + "(They could not be merged into a single string of nodes)");
074        new Notification(msg)
075                .setIcon(JOptionPane.INFORMATION_MESSAGE)
076                .show();
077        return;
078    }
079
080    protected static Way getTargetWay(Collection<Way> combinedWays) {
081        // init with an arbitrary way
082        Way targetWay = combinedWays.iterator().next();
083
084        // look for the first way already existing on
085        // the server
086        for (Way w : combinedWays) {
087            targetWay = w;
088            if (!w.isNew()) {
089                break;
090            }
091        }
092        return targetWay;
093    }
094
095    /**
096     * Combine multiple ways into one.
097     * @param ways the way to combine to one way
098     * @return null if ways cannot be combined. Otherwise returns the combined ways and the commands to combine
099     * @throws UserCancelException if the user cancelled a dialog.
100     */
101    public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException {
102
103        // prepare and clean the list of ways to combine
104        //
105        if (ways == null || ways.isEmpty())
106            return null;
107        ways.remove(null); // just in case -  remove all null ways from the collection
108
109        // remove duplicates, preserving order
110        ways = new LinkedHashSet<>(ways);
111
112        // try to build a new way which includes all the combined ways
113        //
114        NodeGraph graph = NodeGraph.createNearlyUndirectedGraphFromNodeWays(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<>();
126        List<Way> unreversedWays = new LinkedList<>();
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<>(ways);
156                unreversedTagWays.removeAll(reversedWays);
157                ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
158                List<Way> reversedTagWays = new ArrayList<>(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        List<Command> cmds = new LinkedList<>();
184        List<Way> deletedWays = new LinkedList<>(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 Command sequenceCommand = new SequenceCommand(/* for correct i18n of plural forms - see #9110 */
191                trn("Combine {0} way", "Combine {0} ways", ways.size(), ways.size()), cmds);
192
193        return new Pair<>(targetWay, sequenceCommand);
194    }
195
196    @Override
197    public void actionPerformed(ActionEvent event) {
198        if (getCurrentDataSet() == null)
199            return;
200        Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
201        Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
202        if (selectedWays.size() < 2) {
203            new Notification(
204                    tr("Please select at least two ways to combine."))
205                    .setIcon(JOptionPane.INFORMATION_MESSAGE)
206                    .setDuration(Notification.TIME_SHORT)
207                    .show();
208            return;
209        }
210        // combine and update gui
211        Pair<Way, Command> combineResult;
212        try {
213            combineResult = combineWaysWorker(selectedWays);
214        } catch (UserCancelException ex) {
215            return;
216        }
217
218        if (combineResult == null)
219            return;
220        final Way selectedWay = combineResult.a;
221        Main.main.undoRedo.add(combineResult.b);
222        if (selectedWay != null) {
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        }
251        setEnabled(numWays >= 2);
252    }
253
254    /**
255     * A pair of nodes.
256     */
257    public static class NodePair {
258        private final Node a;
259        private final Node b;
260
261        /**
262         * Constructs a new {@code NodePair}.
263         * @param a The first node
264         * @param b The second node
265         */
266        public NodePair(Node a, Node b) {
267            this.a = a;
268            this.b = b;
269        }
270
271        /**
272         * Constructs a new {@code NodePair}.
273         * @param pair An existing {@code Pair} of nodes
274         */
275        public NodePair(Pair<Node, Node> pair) {
276            this(pair.a, pair.b);
277        }
278
279        /**
280         * Constructs a new {@code NodePair}.
281         * @param other An existing {@code NodePair}
282         */
283        public NodePair(NodePair other) {
284            this(other.a, other.b);
285        }
286
287        /**
288         * Replies the first node.
289         * @return The first node
290         */
291        public Node getA() {
292            return a;
293        }
294
295        /**
296         * Replies the second node
297         * @return The second node
298         */
299        public Node getB() {
300            return b;
301        }
302
303        public boolean isAdjacentToA(NodePair other) {
304            return other.getA() == a || other.getB() == a;
305        }
306
307        public boolean isAdjacentToB(NodePair other) {
308            return other.getA() == b || other.getB() == b;
309        }
310
311        public boolean isSuccessorOf(NodePair other) {
312            return other.getB() == a;
313        }
314
315        public boolean isPredecessorOf(NodePair other) {
316            return b == other.getA();
317        }
318
319        public NodePair swap() {
320            return new NodePair(b, a);
321        }
322
323        @Override
324        public String toString() {
325            return new StringBuilder()
326            .append('[')
327            .append(a.getId())
328            .append(',')
329            .append(b.getId())
330            .append(']')
331            .toString();
332        }
333
334        /**
335         * Determines if this pair contains the given node.
336         * @param n The node to look for
337         * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
338         */
339        public boolean contains(Node n) {
340            return a == n || b == n;
341        }
342
343        @Override
344        public int hashCode() {
345            final int prime = 31;
346            int result = 1;
347            result = prime * result + ((a == null) ? 0 : a.hashCode());
348            result = prime * result + ((b == null) ? 0 : b.hashCode());
349            return result;
350        }
351
352        @Override
353        public boolean equals(Object obj) {
354            if (this == obj)
355                return true;
356            if (obj == null)
357                return false;
358            if (getClass() != obj.getClass())
359                return false;
360            NodePair other = (NodePair) obj;
361            if (a == null) {
362                if (other.a != null)
363                    return false;
364            } else if (!a.equals(other.a))
365                return false;
366            if (b == null) {
367                if (other.b != null)
368                    return false;
369            } else if (!b.equals(other.b))
370                return false;
371            return true;
372        }
373    }
374
375    public static class NodeGraph {
376        public static List<NodePair> buildNodePairs(Way way, boolean directed) {
377            List<NodePair> pairs = new ArrayList<>();
378            for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) {
379                pairs.add(new NodePair(pair));
380                if (!directed) {
381                    pairs.add(new NodePair(pair).swap());
382                }
383            }
384            return pairs;
385        }
386
387        public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
388            List<NodePair> pairs = new ArrayList<>();
389            for (Way w: ways) {
390                pairs.addAll(buildNodePairs(w, directed));
391            }
392            return pairs;
393        }
394
395        public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
396            List<NodePair> cleaned = new ArrayList<>();
397            for (NodePair p: pairs) {
398                if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
399                    cleaned.add(p);
400                }
401            }
402            return cleaned;
403        }
404
405        public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
406            NodeGraph graph = new NodeGraph();
407            for (NodePair pair: pairs) {
408                graph.add(pair);
409            }
410            return graph;
411        }
412
413        public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
414            NodeGraph graph = new NodeGraph();
415            for (Way w: ways) {
416                graph.add(buildNodePairs(w, true /* directed */));
417            }
418            return graph;
419        }
420
421        /**
422         * Create an undirected graph from the given node pairs.
423         * @param pairs Node pairs to build the graph from
424         * @return node graph structure
425         */
426        public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
427            NodeGraph graph = new NodeGraph();
428            for (NodePair pair: pairs) {
429                graph.add(pair);
430                graph.add(pair.swap());
431            }
432            return graph;
433        }
434
435        /**
436         * Create an undirected graph from the given ways, but prevent reversing of all
437         * non-new ways by fix one direction.
438         * @param ways Ways to build the graph from
439         * @return node graph structure
440         * @since 8181
441         */
442        public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
443            NodeGraph graph = new NodeGraph();
444            for (Way w: ways) {
445                graph.add(buildNodePairs(w, false /* undirected */));
446            }
447            return graph;
448        }
449
450        public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
451            boolean dir = true;
452            NodeGraph graph = new NodeGraph();
453            for (Way w: ways) {
454                if (!w.isNew()) {
455                    /* let the first non-new way give the direction (see #5880) */
456                    graph.add(buildNodePairs(w, dir));
457                    dir = false;
458                } else {
459                    graph.add(buildNodePairs(w, false /* undirected */));
460                }
461            }
462            return graph;
463        }
464
465        private final Set<NodePair> edges;
466        private int numUndirectedEges;
467        private Map<Node, List<NodePair>> successors;
468        private Map<Node, List<NodePair>> predecessors;
469
470        protected void rememberSuccessor(NodePair pair) {
471            if (successors.containsKey(pair.getA())) {
472                if (!successors.get(pair.getA()).contains(pair)) {
473                    successors.get(pair.getA()).add(pair);
474                }
475            } else {
476                List<NodePair> l = new ArrayList<>();
477                l.add(pair);
478                successors.put(pair.getA(), l);
479            }
480        }
481
482        protected void rememberPredecessors(NodePair pair) {
483            if (predecessors.containsKey(pair.getB())) {
484                if (!predecessors.get(pair.getB()).contains(pair)) {
485                    predecessors.get(pair.getB()).add(pair);
486                }
487            } else {
488                List<NodePair> l = new ArrayList<>();
489                l.add(pair);
490                predecessors.put(pair.getB(), l);
491            }
492        }
493
494        protected boolean isTerminalNode(Node n) {
495            if (successors.get(n) == null) return false;
496            if (successors.get(n).size() != 1) return false;
497            if (predecessors.get(n) == null) return true;
498            if (predecessors.get(n).size() == 1) {
499                NodePair p1 = successors.get(n).get(0);
500                NodePair p2 = predecessors.get(n).get(0);
501                return p1.equals(p2.swap());
502            }
503            return false;
504        }
505
506        protected void prepare() {
507            Set<NodePair> undirectedEdges = new LinkedHashSet<>();
508            successors = new LinkedHashMap<>();
509            predecessors = new LinkedHashMap<>();
510
511            for (NodePair pair: edges) {
512                if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
513                    undirectedEdges.add(pair);
514                }
515                rememberSuccessor(pair);
516                rememberPredecessors(pair);
517            }
518            numUndirectedEges = undirectedEdges.size();
519        }
520
521        /**
522         * Constructs a new {@code NodeGraph}.
523         */
524        public NodeGraph() {
525            edges = new LinkedHashSet<>();
526        }
527
528        public void add(NodePair pair) {
529            if (!edges.contains(pair)) {
530                edges.add(pair);
531            }
532        }
533
534        public void add(List<NodePair> pairs) {
535            for (NodePair pair: pairs) {
536                add(pair);
537            }
538        }
539
540        protected Set<Node> getTerminalNodes() {
541            Set<Node> ret = new LinkedHashSet<>();
542            for (Node n: getNodes()) {
543                if (isTerminalNode(n)) {
544                    ret.add(n);
545                }
546            }
547            return ret;
548        }
549
550        protected List<NodePair> getOutboundPairs(NodePair pair) {
551            return getOutboundPairs(pair.getB());
552        }
553
554        protected List<NodePair> getOutboundPairs(Node node) {
555            List<NodePair> l = successors.get(node);
556            if (l == null)
557                return Collections.emptyList();
558            return l;
559        }
560
561        protected Set<Node> getNodes() {
562            Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
563            for (NodePair pair: edges) {
564                nodes.add(pair.getA());
565                nodes.add(pair.getB());
566            }
567            return nodes;
568        }
569
570        protected boolean isSpanningWay(Stack<NodePair> way) {
571            return numUndirectedEges == way.size();
572        }
573
574        protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
575            List<Node> ret = new LinkedList<>();
576            for (NodePair pair: path) {
577                ret.add(pair.getA());
578            }
579            ret.add(path.peek().getB());
580            return ret;
581        }
582
583        /**
584         * Tries to find a spanning path starting from node <code>startNode</code>.
585         *
586         * Traverses the path in depth-first order.
587         *
588         * @param startNode the start node
589         * @return the spanning path; null, if no path is found
590         */
591        protected List<Node> buildSpanningPath(Node startNode) {
592            if (startNode == null)
593                return null;
594            Stack<NodePair> path = new Stack<>();
595            Stack<NodePair> nextPairs  = new Stack<>();
596            nextPairs.addAll(getOutboundPairs(startNode));
597            while (!nextPairs.isEmpty()) {
598                NodePair cur = nextPairs.pop();
599                if (!path.contains(cur) && !path.contains(cur.swap())) {
600                    while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
601                        path.pop();
602                    }
603                    path.push(cur);
604                    if (isSpanningWay(path)) return buildPathFromNodePairs(path);
605                    nextPairs.addAll(getOutboundPairs(path.peek()));
606                }
607            }
608            return null;
609        }
610
611        /**
612         * Tries to find a path through the graph which visits each edge (i.e.
613         * the segment of a way) exactly once.
614         *
615         * @return the path; null, if no path was found
616         */
617        public List<Node> buildSpanningPath() {
618            prepare();
619            // try to find a path from each "terminal node", i.e. from a
620            // node which is connected by exactly one undirected edges (or
621            // two directed edges in opposite direction) to the graph. A
622            // graph built up from way segments is likely to include such
623            // nodes, unless all ways are closed.
624            // In the worst case this loops over all nodes which is very slow for large ways.
625            //
626            Set<Node> nodes = getTerminalNodes();
627            nodes = nodes.isEmpty() ? getNodes() : nodes;
628            for (Node n: nodes) {
629                List<Node> path = buildSpanningPath(n);
630                if (path != null)
631                    return path;
632            }
633            return null;
634        }
635    }
636}