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         * Constructs a new {@code NodePair}.
290         * @param other An existing {@code NodePair}
291         */
292        public NodePair(NodePair other) {
293            this(other.a, other.b);
294        }
295
296        /**
297         * Replies the first node.
298         * @return The first node
299         */
300        public Node getA() {
301            return a;
302        }
303
304        /**
305         * Replies the second node
306         * @return The second node
307         */
308        public Node getB() {
309            return b;
310        }
311
312        public boolean isAdjacentToA(NodePair other) {
313            return other.getA() == a || other.getB() == a;
314        }
315
316        public boolean isAdjacentToB(NodePair other) {
317            return other.getA() == b || other.getB() == b;
318        }
319
320        public boolean isSuccessorOf(NodePair other) {
321            return other.getB() == a;
322        }
323
324        public boolean isPredecessorOf(NodePair other) {
325            return b == other.getA();
326        }
327
328        public NodePair swap() {
329            return new NodePair(b, a);
330        }
331
332        @Override
333        public String toString() {
334            return new StringBuilder()
335            .append('[')
336            .append(a.getId())
337            .append(',')
338            .append(b.getId())
339            .append(']')
340            .toString();
341        }
342
343        /**
344         * Determines if this pair contains the given node.
345         * @param n The node to look for
346         * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
347         */
348        public boolean contains(Node n) {
349            return a == n || b == n;
350        }
351
352        @Override
353        public int hashCode() {
354            return Objects.hash(a, b);
355        }
356
357        @Override
358        public boolean equals(Object obj) {
359            if (this == obj) return true;
360            if (obj == null || getClass() != obj.getClass()) return false;
361            NodePair nodePair = (NodePair) obj;
362            return Objects.equals(a, nodePair.a) &&
363                    Objects.equals(b, nodePair.b);
364        }
365    }
366
367    public static class NodeGraph {
368        public static List<NodePair> buildNodePairs(Way way, boolean directed) {
369            List<NodePair> pairs = new ArrayList<>();
370            for (Pair<Node, Node> pair: way.getNodePairs(false /* don't sort */)) {
371                pairs.add(new NodePair(pair));
372                if (!directed) {
373                    pairs.add(new NodePair(pair).swap());
374                }
375            }
376            return pairs;
377        }
378
379        public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
380            List<NodePair> pairs = new ArrayList<>();
381            for (Way w: ways) {
382                pairs.addAll(buildNodePairs(w, directed));
383            }
384            return pairs;
385        }
386
387        public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
388            List<NodePair> cleaned = new ArrayList<>();
389            for (NodePair p: pairs) {
390                if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
391                    cleaned.add(p);
392                }
393            }
394            return cleaned;
395        }
396
397        public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
398            NodeGraph graph = new NodeGraph();
399            for (NodePair pair: pairs) {
400                graph.add(pair);
401            }
402            return graph;
403        }
404
405        public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
406            NodeGraph graph = new NodeGraph();
407            for (Way w: ways) {
408                graph.add(buildNodePairs(w, true /* directed */));
409            }
410            return graph;
411        }
412
413        /**
414         * Create an undirected graph from the given node pairs.
415         * @param pairs Node pairs to build the graph from
416         * @return node graph structure
417         */
418        public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
419            NodeGraph graph = new NodeGraph();
420            for (NodePair pair: pairs) {
421                graph.add(pair);
422                graph.add(pair.swap());
423            }
424            return graph;
425        }
426
427        /**
428         * Create an undirected graph from the given ways, but prevent reversing of all
429         * non-new ways by fix one direction.
430         * @param ways Ways to build the graph from
431         * @return node graph structure
432         * @since 8181
433         */
434        public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
435            NodeGraph graph = new NodeGraph();
436            for (Way w: ways) {
437                graph.add(buildNodePairs(w, false /* undirected */));
438            }
439            return graph;
440        }
441
442        public static NodeGraph createNearlyUndirectedGraphFromNodeWays(Collection<Way> ways) {
443            boolean dir = true;
444            NodeGraph graph = new NodeGraph();
445            for (Way w: ways) {
446                if (!w.isNew()) {
447                    /* let the first non-new way give the direction (see #5880) */
448                    graph.add(buildNodePairs(w, dir));
449                    dir = false;
450                } else {
451                    graph.add(buildNodePairs(w, false /* undirected */));
452                }
453            }
454            return graph;
455        }
456
457        private final Set<NodePair> edges;
458        private int numUndirectedEges;
459        private Map<Node, List<NodePair>> successors;
460        private Map<Node, List<NodePair>> predecessors;
461
462        protected void rememberSuccessor(NodePair pair) {
463            if (successors.containsKey(pair.getA())) {
464                if (!successors.get(pair.getA()).contains(pair)) {
465                    successors.get(pair.getA()).add(pair);
466                }
467            } else {
468                List<NodePair> l = new ArrayList<>();
469                l.add(pair);
470                successors.put(pair.getA(), l);
471            }
472        }
473
474        protected void rememberPredecessors(NodePair pair) {
475            if (predecessors.containsKey(pair.getB())) {
476                if (!predecessors.get(pair.getB()).contains(pair)) {
477                    predecessors.get(pair.getB()).add(pair);
478                }
479            } else {
480                List<NodePair> l = new ArrayList<>();
481                l.add(pair);
482                predecessors.put(pair.getB(), l);
483            }
484        }
485
486        protected boolean isTerminalNode(Node n) {
487            if (successors.get(n) == null) return false;
488            if (successors.get(n).size() != 1) return false;
489            if (predecessors.get(n) == null) return true;
490            if (predecessors.get(n).size() == 1) {
491                NodePair p1 = successors.get(n).get(0);
492                NodePair p2 = predecessors.get(n).get(0);
493                return p1.equals(p2.swap());
494            }
495            return false;
496        }
497
498        protected void prepare() {
499            Set<NodePair> undirectedEdges = new LinkedHashSet<>();
500            successors = new LinkedHashMap<>();
501            predecessors = new LinkedHashMap<>();
502
503            for (NodePair pair: edges) {
504                if (!undirectedEdges.contains(pair) && !undirectedEdges.contains(pair.swap())) {
505                    undirectedEdges.add(pair);
506                }
507                rememberSuccessor(pair);
508                rememberPredecessors(pair);
509            }
510            numUndirectedEges = undirectedEdges.size();
511        }
512
513        /**
514         * Constructs a new {@code NodeGraph}.
515         */
516        public NodeGraph() {
517            edges = new LinkedHashSet<>();
518        }
519
520        public void add(NodePair pair) {
521            if (!edges.contains(pair)) {
522                edges.add(pair);
523            }
524        }
525
526        public void add(List<NodePair> pairs) {
527            for (NodePair pair: pairs) {
528                add(pair);
529            }
530        }
531
532        protected Set<Node> getTerminalNodes() {
533            Set<Node> ret = new LinkedHashSet<>();
534            for (Node n: getNodes()) {
535                if (isTerminalNode(n)) {
536                    ret.add(n);
537                }
538            }
539            return ret;
540        }
541
542        protected List<NodePair> getOutboundPairs(NodePair pair) {
543            return getOutboundPairs(pair.getB());
544        }
545
546        protected List<NodePair> getOutboundPairs(Node node) {
547            List<NodePair> l = successors.get(node);
548            if (l == null)
549                return Collections.emptyList();
550            return l;
551        }
552
553        protected Set<Node> getNodes() {
554            Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
555            for (NodePair pair: edges) {
556                nodes.add(pair.getA());
557                nodes.add(pair.getB());
558            }
559            return nodes;
560        }
561
562        protected boolean isSpanningWay(Stack<NodePair> way) {
563            return numUndirectedEges == way.size();
564        }
565
566        protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
567            List<Node> ret = new LinkedList<>();
568            for (NodePair pair: path) {
569                ret.add(pair.getA());
570            }
571            ret.add(path.peek().getB());
572            return ret;
573        }
574
575        /**
576         * Tries to find a spanning path starting from node <code>startNode</code>.
577         *
578         * Traverses the path in depth-first order.
579         *
580         * @param startNode the start node
581         * @return the spanning path; null, if no path is found
582         */
583        protected List<Node> buildSpanningPath(Node startNode) {
584            if (startNode == null)
585                return null;
586            Stack<NodePair> path = new Stack<>();
587            Stack<NodePair> nextPairs  = new Stack<>();
588            nextPairs.addAll(getOutboundPairs(startNode));
589            while (!nextPairs.isEmpty()) {
590                NodePair cur = nextPairs.pop();
591                if (!path.contains(cur) && !path.contains(cur.swap())) {
592                    while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
593                        path.pop();
594                    }
595                    path.push(cur);
596                    if (isSpanningWay(path)) return buildPathFromNodePairs(path);
597                    nextPairs.addAll(getOutboundPairs(path.peek()));
598                }
599            }
600            return null;
601        }
602
603        /**
604         * Tries to find a path through the graph which visits each edge (i.e.
605         * the segment of a way) exactly once.
606         *
607         * @return the path; null, if no path was found
608         */
609        public List<Node> buildSpanningPath() {
610            prepare();
611            // try to find a path from each "terminal node", i.e. from a
612            // node which is connected by exactly one undirected edges (or
613            // two directed edges in opposite direction) to the graph. A
614            // graph built up from way segments is likely to include such
615            // nodes, unless all ways are closed.
616            // In the worst case this loops over all nodes which is very slow for large ways.
617            //
618            Set<Node> nodes = getTerminalNodes();
619            nodes = nodes.isEmpty() ? getNodes() : nodes;
620            for (Node n: nodes) {
621                List<Node> path = buildSpanningPath(n);
622                if (path != null)
623                    return path;
624            }
625            return null;
626        }
627    }
628}