source: josm/trunk/src/org/openstreetmap/josm/actions/CombineWayAction.java @ 4920

Revision 4892, 22.5 KB checked in by stoecker, 10 days ago (diff)

remove deprecation
  • Property svn:eol-style set to native
Line 
1// License: GPL. Copyright 2007 by Immanuel Scholz and others
2package org.openstreetmap.josm.actions;
3
4import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.combineTigerTags;
5import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.completeTagCollectionForEditing;
6import static org.openstreetmap.josm.gui.conflict.tags.TagConflictResolutionUtil.normalizeTagCollectionBeforeEditing;
7import static org.openstreetmap.josm.gui.help.HelpUtil.ht;
8import static org.openstreetmap.josm.tools.I18n.tr;
9
10import java.awt.event.ActionEvent;
11import java.awt.event.KeyEvent;
12import java.util.ArrayList;
13import java.util.Collection;
14import java.util.Collections;
15import java.util.HashMap;
16import java.util.HashSet;
17import java.util.LinkedHashMap;
18import java.util.LinkedHashSet;
19import java.util.LinkedList;
20import java.util.List;
21import java.util.Set;
22import java.util.Stack;
23
24import javax.swing.JOptionPane;
25import javax.swing.SwingUtilities;
26
27import org.openstreetmap.josm.Main;
28import org.openstreetmap.josm.command.ChangeCommand;
29import org.openstreetmap.josm.command.Command;
30import org.openstreetmap.josm.command.DeleteCommand;
31import org.openstreetmap.josm.command.SequenceCommand;
32import org.openstreetmap.josm.corrector.ReverseWayTagCorrector;
33import org.openstreetmap.josm.corrector.UserCancelException;
34import org.openstreetmap.josm.data.osm.Node;
35import org.openstreetmap.josm.data.osm.OsmPrimitive;
36import org.openstreetmap.josm.data.osm.Relation;
37import org.openstreetmap.josm.data.osm.TagCollection;
38import org.openstreetmap.josm.data.osm.Way;
39import org.openstreetmap.josm.data.preferences.BooleanProperty;
40import org.openstreetmap.josm.gui.ExtendedDialog;
41import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
42import org.openstreetmap.josm.tools.Pair;
43import org.openstreetmap.josm.tools.Shortcut;
44
45/**
46 * Combines multiple ways into one.
47 *
48 */
49public class CombineWayAction extends JosmAction {
50
51    private static final BooleanProperty PROP_REVERSE_WAY = new BooleanProperty("tag-correction.reverse-way", true);
52
53    public CombineWayAction() {
54        super(tr("Combine Way"), "combineway", tr("Combine several ways into one."),
55                Shortcut.registerShortcut("tools:combineway", tr("Tool: {0}", tr("Combine Way")), KeyEvent.VK_C, Shortcut.GROUP_EDIT), true);
56        putValue("help", ht("/Action/CombineWay"));
57    }
58
59    protected static boolean confirmChangeDirectionOfWays() {
60        ExtendedDialog ed = new ExtendedDialog(Main.parent,
61                tr("Change directions?"),
62                new String[] {tr("Reverse and Combine"), tr("Cancel")});
63        ed.setButtonIcons(new String[] {"wayflip.png", "cancel.png"});
64        ed.setContent(tr("The ways can not be combined in their current directions.  "
65                + "Do you want to reverse some of them?"));
66        ed.showDialog();
67        return ed.getValue() == 1;
68    }
69
70    protected static void warnCombiningImpossible() {
71        String msg = tr("Could not combine ways "
72                + "(They could not be merged into a single string of nodes)");
73        JOptionPane.showMessageDialog(
74                Main.parent,
75                msg,
76                tr("Information"),
77                JOptionPane.INFORMATION_MESSAGE
78        );
79        return;
80    }
81
82    protected static Way getTargetWay(Collection<Way> combinedWays) {
83        // init with an arbitrary way
84        Way targetWay = combinedWays.iterator().next();
85
86        // look for the first way already existing on
87        // the server
88        for (Way w : combinedWays) {
89            targetWay = w;
90            if (!w.isNew()) {
91                break;
92            }
93        }
94        return targetWay;
95    }
96
97    /**
98     * Replies the set of referring relations
99     *
100     * @return the set of referring relations
101     */
102    public static Set<Relation> getParentRelations(Collection<Way> ways) {
103        HashSet<Relation> ret = new HashSet<Relation>();
104        for (Way w: ways) {
105            ret.addAll(OsmPrimitive.getFilteredList(w.getReferrers(), Relation.class));
106        }
107        return ret;
108    }
109
110    /**
111     * @param ways
112     * @return null if ways cannot be combined. Otherwise returns the combined
113     *              ways and the commands to combine
114     * @throws UserCancelException
115     */
116    public static Pair<Way, Command> combineWaysWorker(Collection<Way> ways) throws UserCancelException {
117
118        // prepare and clean the list of ways to combine
119        //
120        if (ways == null || ways.isEmpty())
121            return null;
122        ways.remove(null); // just in case -  remove all null ways from the collection
123
124        // remove duplicates, preserving order
125        ways = new LinkedHashSet<Way>(ways);
126
127        // try to build a new way which includes all the combined
128        // ways
129        //
130        NodeGraph graph = NodeGraph.createUndirectedGraphFromNodeWays(ways);
131        List<Node> path = graph.buildSpanningPath();
132        if (path == null) {
133            warnCombiningImpossible();
134            return null;
135        }
136        // check whether any ways have been reversed in the process
137        // and build the collection of tags used by the ways to combine
138        //
139        TagCollection wayTags = TagCollection.unionOfAllPrimitives(ways);
140
141        List<Way> reversedWays = new LinkedList<Way>();
142        List<Way> unreversedWays = new LinkedList<Way>();
143        for (Way w: ways) {
144            if ((path.indexOf(w.getNode(0)) + 1) == path.lastIndexOf(w.getNode(1))) {
145                unreversedWays.add(w);
146            } else {
147                reversedWays.add(w);
148            }
149        }
150        // reverse path if all ways have been reversed
151        if (unreversedWays.isEmpty()) {
152            Collections.reverse(path);
153            unreversedWays = reversedWays;
154            reversedWays = null;
155        }
156        if ((reversedWays != null) && !reversedWays.isEmpty()) {
157            if (!confirmChangeDirectionOfWays()) return null;
158            // filter out ways that have no direction-dependent tags
159            unreversedWays = ReverseWayTagCorrector.irreversibleWays(unreversedWays);
160            reversedWays = ReverseWayTagCorrector.irreversibleWays(reversedWays);
161            // reverse path if there are more reversed than unreversed ways with direction-dependent tags
162            if (reversedWays.size() > unreversedWays.size()) {
163                Collections.reverse(path);
164                List<Way> tempWays = unreversedWays;
165                unreversedWays = reversedWays;
166                reversedWays = tempWays;
167            }
168            // if there are still reversed ways with direction-dependent tags, reverse their tags
169            if (!reversedWays.isEmpty() && PROP_REVERSE_WAY.get()) {
170                List<Way> unreversedTagWays = new ArrayList<Way>(ways);
171                unreversedTagWays.removeAll(reversedWays);
172                ReverseWayTagCorrector reverseWayTagCorrector = new ReverseWayTagCorrector();
173                List<Way> reversedTagWays = new ArrayList<Way>();
174                Collection<Command> changePropertyCommands =  null;
175                for (Way w : reversedWays) {
176                    Way wnew = new Way(w);
177                    reversedTagWays.add(wnew);
178                    changePropertyCommands = reverseWayTagCorrector.execute(w, wnew);
179                }
180                if ((changePropertyCommands != null) && !changePropertyCommands.isEmpty()) {
181                    for (Command c : changePropertyCommands) {
182                        c.executeCommand();
183                    }
184                }
185                wayTags = TagCollection.unionOfAllPrimitives(reversedTagWays);
186                wayTags.add(TagCollection.unionOfAllPrimitives(unreversedTagWays));
187            }
188        }
189
190        // create the new way and apply the new node list
191        //
192        Way targetWay = getTargetWay(ways);
193        Way modifiedTargetWay = new Way(targetWay);
194        modifiedTargetWay.setNodes(path);
195
196        TagCollection completeWayTags = new TagCollection(wayTags);
197        combineTigerTags(completeWayTags);
198        normalizeTagCollectionBeforeEditing(completeWayTags, ways);
199        TagCollection tagsToEdit = new TagCollection(completeWayTags);
200        completeTagCollectionForEditing(tagsToEdit);
201
202        CombinePrimitiveResolverDialog dialog = CombinePrimitiveResolverDialog.getInstance();
203        dialog.getTagConflictResolverModel().populate(tagsToEdit, completeWayTags.getKeysWithMultipleValues());
204        dialog.setTargetPrimitive(targetWay);
205        Set<Relation> parentRelations = getParentRelations(ways);
206        dialog.getRelationMemberConflictResolverModel().populate(
207                parentRelations,
208                ways
209        );
210        dialog.prepareDefaultDecisions();
211
212        // resolve tag conflicts if necessary
213        //
214        if (!completeWayTags.isApplicableToPrimitive() || !parentRelations.isEmpty()) {
215            dialog.setVisible(true);
216            if (dialog.isCanceled())
217                throw new UserCancelException();
218        }
219
220        LinkedList<Command> cmds = new LinkedList<Command>();
221        LinkedList<Way> deletedWays = new LinkedList<Way>(ways);
222        deletedWays.remove(targetWay);
223
224        cmds.add(new ChangeCommand(targetWay, modifiedTargetWay));
225        cmds.addAll(dialog.buildResolutionCommands());
226        cmds.add(new DeleteCommand(deletedWays));
227        final SequenceCommand sequenceCommand = new SequenceCommand(tr("Combine {0} ways", ways.size()), cmds);
228
229        return new Pair<Way, Command>(targetWay, sequenceCommand);
230    }
231
232    public void actionPerformed(ActionEvent event) {
233        if (getCurrentDataSet() == null)
234            return;
235        Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
236        Set<Way> selectedWays = OsmPrimitive.getFilteredSet(selection, Way.class);
237        if (selectedWays.size() < 2) {
238            JOptionPane.showMessageDialog(
239                    Main.parent,
240                    tr("Please select at least two ways to combine."),
241                    tr("Information"),
242                    JOptionPane.INFORMATION_MESSAGE
243            );
244            return;
245        }
246        // combine and update gui
247        Pair<Way, Command> combineResult;
248        try {
249            combineResult = combineWaysWorker(selectedWays);
250        } catch (UserCancelException ex) {
251            return;
252        }
253
254        if (combineResult == null)
255            return;
256        final Way selectedWay = combineResult.a;
257        Main.main.undoRedo.add(combineResult.b);
258        if(selectedWay != null)
259        {
260            Runnable guiTask = new Runnable() {
261                public void run() {
262                    getCurrentDataSet().setSelected(selectedWay);
263                }
264            };
265            if (SwingUtilities.isEventDispatchThread()) {
266                guiTask.run();
267            } else {
268                SwingUtilities.invokeLater(guiTask);
269            }
270        }
271    }
272
273    @Override
274    protected void updateEnabledState() {
275        if (getCurrentDataSet() == null) {
276            setEnabled(false);
277            return;
278        }
279        Collection<OsmPrimitive> selection = getCurrentDataSet().getSelected();
280        updateEnabledState(selection);
281    }
282
283    @Override
284    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
285        int numWays = 0;
286        for (OsmPrimitive osm : selection)
287            if (osm instanceof Way) {
288                numWays++;
289            }
290        setEnabled(numWays >= 2);
291    }
292
293    static public class NodePair {
294        private Node a;
295        private Node b;
296        public NodePair(Node a, Node b) {
297            this.a =a;
298            this.b = b;
299        }
300
301        public NodePair(Pair<Node,Node> pair) {
302            this.a = pair.a;
303            this.b = pair.b;
304        }
305
306        public NodePair(NodePair other) {
307            this.a = other.a;
308            this.b = other.b;
309        }
310
311        public Node getA() {
312            return a;
313        }
314
315        public Node getB() {
316            return b;
317        }
318
319        public boolean isAdjacentToA(NodePair other) {
320            return other.getA() == a || other.getB() == a;
321        }
322
323        public boolean isAdjacentToB(NodePair other) {
324            return other.getA() == b || other.getB() == b;
325        }
326
327        public boolean isSuccessorOf(NodePair other) {
328            return other.getB() == a;
329        }
330
331        public boolean isPredecessorOf(NodePair other) {
332            return b == other.getA();
333        }
334
335        public NodePair swap() {
336            return new NodePair(b,a);
337        }
338
339        @Override
340        public String toString() {
341            return new StringBuilder()
342            .append("[")
343            .append(a.getId())
344            .append(",")
345            .append(b.getId())
346            .append("]")
347            .toString();
348        }
349
350        public boolean contains(Node n) {
351            return a == n || b == n;
352        }
353
354        @Override
355        public int hashCode() {
356            final int prime = 31;
357            int result = 1;
358            result = prime * result + ((a == null) ? 0 : a.hashCode());
359            result = prime * result + ((b == null) ? 0 : b.hashCode());
360            return result;
361        }
362        @Override
363        public boolean equals(Object obj) {
364            if (this == obj)
365                return true;
366            if (obj == null)
367                return false;
368            if (getClass() != obj.getClass())
369                return false;
370            NodePair other = (NodePair) obj;
371            if (a == null) {
372                if (other.a != null)
373                    return false;
374            } else if (!a.equals(other.a))
375                return false;
376            if (b == null) {
377                if (other.b != null)
378                    return false;
379            } else if (!b.equals(other.b))
380                return false;
381            return true;
382        }
383    }
384
385    static public class NodeGraph {
386        static public List<NodePair> buildNodePairs(Way way, boolean directed) {
387            ArrayList<NodePair> pairs = new ArrayList<NodePair>();
388            for (Pair<Node,Node> pair: way.getNodePairs(false /* don't sort */)) {
389                pairs.add(new NodePair(pair));
390                if (!directed) {
391                    pairs.add(new NodePair(pair).swap());
392                }
393            }
394            return pairs;
395        }
396
397        static public List<NodePair> buildNodePairs(List<Way> ways, boolean directed) {
398            ArrayList<NodePair> pairs = new ArrayList<NodePair>();
399            for (Way w: ways) {
400                pairs.addAll(buildNodePairs(w, directed));
401            }
402            return pairs;
403        }
404
405        static public List<NodePair> eliminateDuplicateNodePairs(List<NodePair> pairs) {
406            ArrayList<NodePair> cleaned = new ArrayList<NodePair>();
407            for(NodePair p: pairs) {
408                if (!cleaned.contains(p) && !cleaned.contains(p.swap())) {
409                    cleaned.add(p);
410                }
411            }
412            return cleaned;
413        }
414
415        static public NodeGraph createDirectedGraphFromNodePairs(List<NodePair> pairs) {
416            NodeGraph graph = new NodeGraph();
417            for (NodePair pair: pairs) {
418                graph.add(pair);
419            }
420            return graph;
421        }
422
423        static public NodeGraph createDirectedGraphFromWays(Collection<Way> ways) {
424            NodeGraph graph = new NodeGraph();
425            for (Way w: ways) {
426                graph.add(buildNodePairs(w, true /* directed */));
427            }
428            return graph;
429        }
430
431        static public NodeGraph createUndirectedGraphFromNodeList(List<NodePair> pairs) {
432            NodeGraph graph = new NodeGraph();
433            for (NodePair pair: pairs) {
434                graph.add(pair);
435                graph.add(pair.swap());
436            }
437            return graph;
438        }
439
440        static public NodeGraph createUndirectedGraphFromNodeWays(Collection<Way> ways) {
441            NodeGraph graph = new NodeGraph();
442            for (Way w: ways) {
443                graph.add(buildNodePairs(w, false /* undirected */));
444            }
445            return graph;
446        }
447
448        private Set<NodePair> edges;
449        private int numUndirectedEges = 0;
450        private HashMap<Node, List<NodePair>> successors;
451        private HashMap<Node, List<NodePair>> predecessors;
452
453        protected void rememberSuccessor(NodePair pair) {
454            if (successors.containsKey(pair.getA())) {
455                if (!successors.get(pair.getA()).contains(pair)) {
456                    successors.get(pair.getA()).add(pair);
457                }
458            } else {
459                ArrayList<NodePair> l = new ArrayList<NodePair>();
460                l.add(pair);
461                successors.put(pair.getA(), l);
462            }
463        }
464
465        protected void rememberPredecessors(NodePair pair) {
466            if (predecessors.containsKey(pair.getB())) {
467                if (!predecessors.get(pair.getB()).contains(pair)) {
468                    predecessors.get(pair.getB()).add(pair);
469                }
470            } else {
471                ArrayList<NodePair> l = new ArrayList<NodePair>();
472                l.add(pair);
473                predecessors.put(pair.getB(), l);
474            }
475        }
476
477        protected boolean isTerminalNode(Node n) {
478            if (successors.get(n) == null) return false;
479            if (successors.get(n).size() != 1) return false;
480            if (predecessors.get(n) == null) return true;
481            if (predecessors.get(n).size() == 1) {
482                NodePair p1 = successors.get(n).iterator().next();
483                NodePair p2 = predecessors.get(n).iterator().next();
484                return p1.equals(p2.swap());
485            }
486            return false;
487        }
488
489        protected void prepare() {
490            Set<NodePair> undirectedEdges = new LinkedHashSet<NodePair>();
491            successors = new LinkedHashMap<Node, List<NodePair>>();
492            predecessors = new LinkedHashMap<Node, List<NodePair>>();
493
494            for (NodePair pair: edges) {
495                if (!undirectedEdges.contains(pair) && ! undirectedEdges.contains(pair.swap())) {
496                    undirectedEdges.add(pair);
497                }
498                rememberSuccessor(pair);
499                rememberPredecessors(pair);
500            }
501            numUndirectedEges = undirectedEdges.size();
502        }
503
504        public NodeGraph() {
505            edges = new LinkedHashSet<NodePair>();
506        }
507
508        public void add(NodePair pair) {
509            if (!edges.contains(pair)) {
510                edges.add(pair);
511            }
512        }
513
514        public void add(List<NodePair> pairs) {
515            for (NodePair pair: pairs) {
516                add(pair);
517            }
518        }
519
520        protected Node getStartNode() {
521            Set<Node> nodes = getNodes();
522            for (Node n: nodes) {
523                if (successors.get(n) != null && successors.get(n).size() ==1)
524                    return n;
525            }
526            return null;
527        }
528
529        protected Set<Node> getTerminalNodes() {
530            Set<Node> ret = new LinkedHashSet<Node>();
531            for (Node n: getNodes()) {
532                if (isTerminalNode(n)) {
533                    ret.add(n);
534                }
535            }
536            return ret;
537        }
538
539        protected Set<Node> getNodes(Stack<NodePair> pairs) {
540            HashSet<Node> nodes = new LinkedHashSet<Node>();
541            for (NodePair pair: pairs) {
542                nodes.add(pair.getA());
543                nodes.add(pair.getB());
544            }
545            return nodes;
546        }
547
548        protected List<NodePair> getOutboundPairs(NodePair pair) {
549            return getOutboundPairs(pair.getB());
550        }
551
552        protected List<NodePair> getOutboundPairs(Node node) {
553            List<NodePair> l = successors.get(node);
554            if (l == null)
555                return Collections.emptyList();
556            return l;
557        }
558
559        protected Set<Node> getNodes() {
560            Set<Node> nodes = new LinkedHashSet<Node>();
561            for (NodePair pair: edges) {
562                nodes.add(pair.getA());
563                nodes.add(pair.getB());
564            }
565            return nodes;
566        }
567
568        protected boolean isSpanningWay(Stack<NodePair> way) {
569            return numUndirectedEges == way.size();
570        }
571
572        protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
573            LinkedList<Node> ret = new LinkedList<Node>();
574            for (NodePair pair: path) {
575                ret.add(pair.getA());
576            }
577            ret.add(path.peek().getB());
578            return ret;
579        }
580
581        /**
582         * Tries to find a spanning path starting from node <code>startNode</code>.
583         *
584         * Traverses the path in depth-first order.
585         *
586         * @param startNode the start node
587         * @return the spanning path; null, if no path is found
588         */
589        protected List<Node> buildSpanningPath(Node startNode) {
590            if (startNode == null)
591                return null;
592            Stack<NodePair> path = new Stack<NodePair>();
593            Stack<NodePair> nextPairs  = new Stack<NodePair>();
594            nextPairs.addAll(getOutboundPairs(startNode));
595            while(!nextPairs.isEmpty()) {
596                NodePair cur= nextPairs.pop();
597                if (! path.contains(cur) && ! path.contains(cur.swap())) {
598                    while(!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
599                        path.pop();
600                    }
601                    path.push(cur);
602                    if (isSpanningWay(path)) return buildPathFromNodePairs(path);
603                    nextPairs.addAll(getOutboundPairs(path.peek()));
604                }
605            }
606            return null;
607        }
608
609        /**
610         * Tries to find a path through the graph which visits each edge (i.e.
611         * the segment of a way) exactly one.
612         *
613         * @return the path; null, if no path was found
614         */
615        public List<Node> buildSpanningPath() {
616            prepare();
617            // try to find a path from each "terminal node", i.e. from a
618            // node which is connected by exactly one undirected edges (or
619            // two directed edges in opposite direction) to the graph. A
620            // graph built up from way segments is likely to include such
621            // nodes, unless all ways are closed.
622            // In the worst case this loops over all nodes which is
623            // very slow for large ways.
624            //
625            Set<Node> nodes = getTerminalNodes();
626            nodes = nodes.isEmpty() ? getNodes() : nodes;
627            for (Node n: nodes) {
628                List<Node> path = buildSpanningPath(n);
629                if (path != null)
630                    return path;
631            }
632            return null;
633        }
634    }
635}
Note: See TracBrowser for help on using the repository browser.