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