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