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