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.HashSet;
014import java.util.LinkedHashMap;
015import java.util.LinkedHashSet;
016import java.util.LinkedList;
017import java.util.List;
018import java.util.Map;
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.corrector.UserCancelException;
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;
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     * @param ways
098     * @return null if ways cannot be combined. Otherwise returns the combined
099     *              ways and the commands to combine
100     * @throws UserCancelException
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
114        // ways
115        //
116        NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(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        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                Collection<Command> changePropertyCommands =  null;
162                for (Way w : reversedWays) {
163                    Way wnew = new Way(w);
164                    reversedTagWays.add(wnew);
165                    changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
166                }
167                if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
168                    for (Command c : changePropertyCommands) {
169                        c.executeCommand();
170                    }
171                }
172                wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
173                wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
174            }
175        }
176
177        // create the new way and apply the new node list
178        //
179        Way targetWay = getTargetWay(ways);
180        Way modifiedTargetWay = new Way(targetWay);
181        modifiedTargetWay.setNodes(path);
182
183        List<Command> resolution = CombinePrimitiveResolverDialog.launchIfNecessary(wayTags, ways, Collections.singleton(targetWay));
184
185        LinkedList<Command> cmds = new LinkedList<>();
186        LinkedList<Way> deletedWays = new LinkedList<>(ways);
187        deletedWays.remove(targetWay);
188
189        cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
190        cmds.addAll(resolution);
191        cmds.add(new DeleteCommand(deletedWays));
192        final SequenceCommand sequenceCommand = new SequenceCommand(/* for correct i18n of plural forms - see #9110 */
193                trn("Combine {0} way", "Combine {0} ways", ways.size(), ways.size()), cmds);
194
195        return new Pair<Way, Command>(targetWay, sequenceCommand);
196    }
197
198    @Override
199    public void actionPerformed(ActionEvent event) {
200        if (getCurrentDataSet() == null)
201            return;
202        Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
203        Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
204        if (selectedWays.size() < 2) {
205            new Notification(
206                    tr("Please select at least two ways to combine."))
207                    .setIcon(JOptionPane.INFORMATION_MESSAGE)
208                    .setDuration(Notification.TIME_SHORT)
209                    .show();
210            return;
211        }
212        // combine and update gui
213        Pair<Way, Command> combineResult;
214        try {
215            combineResult = combineWaysWorker(selectedWays);
216        } catch (UserCancelException ex) {
217            return;
218        }
219
220        if (combineResult == null)
221            return;
222        final Way selectedWay = combineResult.a;
223        Main.main.undoRedo.add(combineResult.b);
224        if(selectedWay != null)
225        {
226            Runnable guiTask = new Runnable() {
227                @Override
228                public void run() {
229                    getCurrentDataSet().setSelected(selectedWay);
230                }
231            };
232            GuiHelper.runInEDT(guiTask);
233        }
234    }
235
236    @Override
237    protected void updateEnabledState() {
238        if (getCurrentDataSet() == null) {
239            setEnabled(false);
240            return;
241        }
242        Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
243        updateEnabledState(selection);
244    }
245
246    @Override
247    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
248        int numWays = 0;
249        for (OsmPrimitive osm : selection)
250            if (osm instanceof Way) {
251                numWays++;
252            }
253        setEnabled(numWays >= 2);
254    }
255
256    /**
257     * A pair of nodes.
258     */
259    public static class NodePair {
260        private final Node a;
261        private final Node b;
262
263        /**
264         * Constructs a new {@code NodePair}.
265         * @param a The first node
266         * @param b The second node
267         */
268        public NodePair(Node a, Node b) {
269            this.a = a;
270            this.b = b;
271        }
272
273        /**
274         * Constructs a new {@code NodePair}.
275         * @param pair An existing {@code Pair} of nodes
276         */
277        public NodePair(Pair<Node,Node> pair) {
278            this(pair.a, pair.b);
279        }
280
281        /**
282         * Constructs a new {@code NodePair}.
283         * @param other An existing {@code NodePair}
284         */
285        public NodePair(NodePair other) {
286            this(other.a, other.b);
287        }
288
289        /**
290         * Replies the first node.
291         * @return The first node
292         */
293        public Node getA() {
294            return a;
295        }
296
297        /**
298         * Replies the second node
299         * @return The second node
300         */
301        public Node getB() {
302            return b;
303        }
304
305        public boolean isAdjacentToA(NodePair other) {
306            return other.getA() == a || other.getB() == a;
307        }
308
309        public boolean isAdjacentToB(NodePair other) {
310            return other.getA() == b || other.getB() == b;
311        }
312
313        public boolean isSuccessorOf(NodePair other) {
314            return other.getB() == a;
315        }
316
317        public boolean isPredecessorOf(NodePair other) {
318            return b == other.getA();
319        }
320
321        public NodePair swap() {
322            return new NodePair(b,a);
323        }
324
325        @Override
326        public String toString() {
327            return new StringBuilder()
328            .append("[")
329            .append(a.getId())
330            .append(",")
331            .append(b.getId())
332            .append("]")
333            .toString();
334        }
335
336        /**
337         * Determines if this pair contains the given node.
338         * @param n The node to look for
339         * @return {@code true} if {@code n} is in the pair, {@code false} otherwise
340         */
341        public boolean contains(Node n) {
342            return a == n || b == n;
343        }
344
345        @Override
346        public int hashCode() {
347            final int prime = 31;
348            int result = 1;
349            result = prime * result + ((a == null) ? 0 : a.hashCode());
350            result = prime * result + ((b == null) ? 0 : b.hashCode());
351            return result;
352        }
353
354        @Override
355        public boolean equals(Object obj) {
356            if (this == obj)
357                return true;
358            if (obj == null)
359                return false;
360            if (getClass() != obj.getClass())
361                return false;
362            NodePair other = (NodePair) obj;
363            if (a == null) {
364                if (other.a != null)
365                    return false;
366            } else if (!a.equals(other.a))
367                return false;
368            if (b == null) {
369                if (other.b != null)
370                    return false;
371            } else if (!b.equals(other.b))
372                return false;
373            return true;
374        }
375    }
376
377    public static class NodeGraph {
378        public static List<NodePair> buildNodePairs(Way way, boolean directed) {
379            List<NodePair> pairs = new ArrayList<>();
380            for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
381                pairs.add(new NodePair(pair));
382                if (!directed) {
383                    pairs.add(new NodePair(pair).swap());
384                }
385            }
386            return pairs;
387        }
388
389        public static List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
390            List<NodePair> pairs = new ArrayList<>();
391            for (Way w: ways) {
392                pairs.addAll(buildNodePairs(w, directed));
393            }
394            return pairs;
395        }
396
397        public static List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
398            List<NodePair> cleaned = new ArrayList<>();
399            for(NodePair p: pairs) {
400                if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
401                    cleaned.add(p);
402                }
403            }
404            return cleaned;
405        }
406
407        public static NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
408            NodeGraph graph = new NodeGraph();
409            for (NodePair pair: pairs) {
410                graph.add(pair);
411            }
412            return graph;
413        }
414
415        public static NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
416            NodeGraph graph = new NodeGraph();
417            for (Way w: ways) {
418                graph.add(buildNodePairs(w, true /* directed */));
419            }
420            return graph;
421        }
422
423        public static NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
424            NodeGraph graph = new NodeGraph();
425            for (NodePair pair: pairs) {
426                graph.add(pair);
427                graph.add(pair.swap());
428            }
429            return graph;
430        }
431
432        public static NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
433            NodeGraph graph = new NodeGraph();
434            for (Way w: ways) {
435                graph.add(buildNodePairs(w, false /* undirected */));
436            }
437            return graph;
438        }
439
440        private Set<NodePair> edges;
441        private int numUndirectedEges = 0;
442        private Map<Node, List<NodePair>> successors;
443        private Map<Node, List<NodePair>> predecessors;
444
445        protected void rememberSuccessor(NodePair pair) {
446            if (successors.containsKey(pair.getA())) {
447                if (!successors.get(pair.getA()).contains(pair)) {
448                    successors.get(pair.getA()).add(pair);
449                }
450            } else {
451                List<NodePair> l = new ArrayList<>();
452                l.add(pair);
453                successors.put(pair.getA(), l);
454            }
455        }
456
457        protected void rememberPredecessors(NodePair pair) {
458            if (predecessors.containsKey(pair.getB())) {
459                if (!predecessors.get(pair.getB()).contains(pair)) {
460                    predecessors.get(pair.getB()).add(pair);
461                }
462            } else {
463                List<NodePair> l = new ArrayList<>();
464                l.add(pair);
465                predecessors.put(pair.getB(), l);
466            }
467        }
468
469        protected boolean isTerminalNode(Node n) {
470            if (successors.get(n) == null) return false;
471            if (successors.get(n).size() != 1) return false;
472            if (predecessors.get(n) == null) return true;
473            if (predecessors.get(n).size() == 1) {
474                NodePair p1 = successors.get(n).iterator().next();
475                NodePair p2 = predecessors.get(n).iterator().next();
476                return p1.equals(p2.swap());
477            }
478            return false;
479        }
480
481        protected void prepare() {
482            Set<NodePair> undirectedEdges = new LinkedHashSet<>();
483            successors = new LinkedHashMap<>();
484            predecessors = new LinkedHashMap<>();
485
486            for (NodePair pair: edges) {
487                if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
488                    undirectedEdges.add(pair);
489                }
490                rememberSuccessor(pair);
491                rememberPredecessors(pair);
492            }
493            numUndirectedEges = undirectedEdges.size();
494        }
495
496        /**
497         * Constructs a new {@code NodeGraph}.
498         */
499        public NodeGraph() {
500            edges = new LinkedHashSet<>();
501        }
502
503        public void add(NodePair pair) {
504            if (!edges.contains(pair)) {
505                edges.add(pair);
506            }
507        }
508
509        public void add(List<NodePair> pairs) {
510            for (NodePair pair: pairs) {
511                add(pair);
512            }
513        }
514
515        protected Node getStartNode() {
516            Set<Node> nodes = getNodes();
517            for (Node n: nodes) {
518                if (successors.get(n) != null && successors.get(n).size() ==1)
519                    return n;
520            }
521            return null;
522        }
523
524        protected Set<Node> getTerminalNodes() {
525            Set<Node> ret = new LinkedHashSet<>();
526            for (Node n: getNodes()) {
527                if (isTerminalNode(n)) {
528                    ret.add(n);
529                }
530            }
531            return ret;
532        }
533
534        protected Set<Node> getNodes(Stack<NodePair> pairs) {
535            HashSet<Node> nodes = new LinkedHashSet<>(2*pairs.size());
536            for (NodePair pair: pairs) {
537                nodes.add(pair.getA());
538                nodes.add(pair.getB());
539            }
540            return nodes;
541        }
542
543        protected List<NodePair> getOutboundPairs(NodePair pair) {
544            return getOutboundPairs(pair.getB());
545        }
546
547        protected List<NodePair> getOutboundPairs(Node node) {
548            List<NodePair> l = successors.get(node);
549            if (l == null)
550                return Collections.emptyList();
551            return l;
552        }
553
554        protected Set<Node> getNodes() {
555            Set<Node> nodes = new LinkedHashSet<>(2 * edges.size());
556            for (NodePair pair: edges) {
557                nodes.add(pair.getA());
558                nodes.add(pair.getB());
559            }
560            return nodes;
561        }
562
563        protected boolean isSpanningWay(Stack<NodePair> way) {
564            return numUndirectedEges == way.size();
565        }
566
567        protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
568            LinkedList<Node> ret = new LinkedList<>();
569            for (NodePair pair: path) {
570                ret.add(pair.getA());
571            }
572            ret.add(path.peek().getB());
573            return ret;
574        }
575
576        /**
577         * Tries to find a spanning path starting from node <code>startNode</code>.
578         *
579         * Traverses the path in depth-first order.
580         *
581         * @param startNode the start node
582         * @return the spanning path; null, if no path is found
583         */
584        protected List<Node> buildSpanningPath(Node startNode) {
585            if (startNode == null)
586                return null;
587            Stack<NodePair> path = new Stack<>();
588            Stack<NodePair> nextPairs  = new Stack<>();
589            nextPairs.addAll(getOutboundPairs(startNode));
590            while(!nextPairs.isEmpty()) {
591                NodePair cur= nextPairs.pop();
592                if (! path.contains(cur) && ! path.contains(cur.swap())) {
593                    while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
594                        path.pop();
595                    }
596                    path.push(cur);
597                    if (isSpanningWay(path)) return buildPathFromNodePairs(path);
598                    nextPairs.addAll(getOutboundPairs(path.peek()));
599                }
600            }
601            return null;
602        }
603
604        /**
605         * Tries to find a path through the graph which visits each edge (i.e.
606         * the segment of a way) exactly one.
607         *
608         * @return the path; null, if no path was found
609         */
610        public List<Node> buildSpanningPath() {
611            prepare();
612            // try to find a path from each "terminal node", i.e. from a
613            // node which is connected by exactly one undirected edges (or
614            // two directed edges in opposite direction) to the graph. A
615            // graph built up from way segments is likely to include such
616            // nodes, unless all ways are closed.
617            // In the worst case this loops over all nodes which is
618            // very slow for large ways.
619            //
620            Set<Node> nodes = getTerminalNodes();
621            nodes = nodes.isEmpty() ? getNodes() : nodes;
622            for (Node n: nodes) {
623                List<Node> path = buildSpanningPath(n);
624                if (path != null)
625                    return path;
626            }
627            return null;
628        }
629    }
630}