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.LinkedList;
015import java.util.List;
016import java.util.Objects;
017import java.util.Optional;
018import java.util.Set;
019import java.util.stream.Collectors;
020
021import javax.swing.JOptionPane;
022
023import org.openstreetmap.josm.command.ChangeCommand;
024import org.openstreetmap.josm.command.ChangeNodesCommand;
025import org.openstreetmap.josm.command.Command;
026import org.openstreetmap.josm.command.DeleteCommand;
027import org.openstreetmap.josm.command.SequenceCommand;
028import org.openstreetmap.josm.data.UndoRedoHandler;
029import org.openstreetmap.josm.data.coor.EastNorth;
030import org.openstreetmap.josm.data.coor.LatLon;
031import org.openstreetmap.josm.data.osm.DefaultNameFormatter;
032import org.openstreetmap.josm.data.osm.Node;
033import org.openstreetmap.josm.data.osm.OsmPrimitive;
034import org.openstreetmap.josm.data.osm.OsmUtils;
035import org.openstreetmap.josm.data.osm.TagCollection;
036import org.openstreetmap.josm.data.osm.Way;
037import org.openstreetmap.josm.gui.HelpAwareOptionPane;
038import org.openstreetmap.josm.gui.HelpAwareOptionPane.ButtonSpec;
039import org.openstreetmap.josm.gui.MainApplication;
040import org.openstreetmap.josm.gui.MapView;
041import org.openstreetmap.josm.gui.Notification;
042import org.openstreetmap.josm.gui.conflict.tags.CombinePrimitiveResolverDialog;
043import org.openstreetmap.josm.gui.layer.OsmDataLayer;
044import org.openstreetmap.josm.spi.preferences.Config;
045import org.openstreetmap.josm.tools.CheckParameterUtil;
046import org.openstreetmap.josm.tools.ImageProvider;
047import org.openstreetmap.josm.tools.Logging;
048import org.openstreetmap.josm.tools.Shortcut;
049import org.openstreetmap.josm.tools.UserCancelException;
050
051/**
052 * Merges a collection of nodes into one node.
053 *
054 * The "surviving" node will be the one with the lowest positive id.
055 * (I.e. it was uploaded to the server and is the oldest one.)
056 *
057 * However we use the location of the node that was selected *last*.
058 * The "surviving" node will be moved to that location if it is
059 * different from the last selected node.
060 *
061 * @since 422
062 */
063public class MergeNodesAction extends JosmAction {
064
065    /**
066     * Constructs a new {@code MergeNodesAction}.
067     */
068    public MergeNodesAction() {
069        super(tr("Merge Nodes"), "mergenodes", tr("Merge nodes into the oldest one."),
070                Shortcut.registerShortcut("tools:mergenodes", tr("Tools: {0}", tr("Merge Nodes")), KeyEvent.VK_M, Shortcut.DIRECT), true);
071        setHelpId(ht("/Action/MergeNodes"));
072    }
073
074    @Override
075    public void actionPerformed(ActionEvent event) {
076        if (!isEnabled())
077            return;
078        final List<Node> selectedNodes = getLayerManager().getEditDataSet().getSelectedNodes().stream()
079                .filter(n -> !n.isDeleted() && !n.isIncomplete())
080                .collect(Collectors.toList());
081
082        if (selectedNodes.size() == 1) {
083            MapView mapView = MainApplication.getMap().mapView;
084            List<Node> nearestNodes = mapView.getNearestNodes(
085                    mapView.getPoint(selectedNodes.get(0)), selectedNodes, OsmPrimitive::isUsable);
086            if (nearestNodes.isEmpty()) {
087                new Notification(
088                        tr("Please select at least two nodes to merge or one node that is close to another node."))
089                        .setIcon(JOptionPane.WARNING_MESSAGE)
090                        .show();
091                return;
092            }
093            selectedNodes.addAll(nearestNodes);
094        }
095
096        Node targetNode = selectTargetNode(selectedNodes);
097        if (targetNode != null) {
098            Node targetLocationNode = selectTargetLocationNode(selectedNodes);
099            Command cmd = mergeNodes(selectedNodes, targetNode, targetLocationNode);
100            if (cmd != null) {
101                UndoRedoHandler.getInstance().add(cmd);
102                getLayerManager().getEditLayer().data.setSelected(targetNode);
103            }
104        }
105    }
106
107    /**
108     * Select the location of the target node after merge.
109     *
110     * @param candidates the collection of candidate nodes
111     * @return the coordinates of this node are later used for the target node
112     */
113    public static Node selectTargetLocationNode(List<Node> candidates) {
114        int size = candidates.size();
115        if (size == 0)
116            throw new IllegalArgumentException("empty list");
117        if (size == 1) // to avoid division by 0 in mode 2
118            return candidates.get(0);
119
120        switch (Config.getPref().getInt("merge-nodes.mode", 0)) {
121        case 0:
122            return candidates.get(size - 1);
123        case 1:
124            double east1 = 0;
125            double north1 = 0;
126            for (final Node n : candidates) {
127                EastNorth en = n.getEastNorth();
128                east1 += en.east();
129                north1 += en.north();
130            }
131
132            return new Node(new EastNorth(east1 / size, north1 / size));
133        case 2:
134            final double[] weights = new double[size];
135
136            for (int i = 0; i < size; i++) {
137                final LatLon c1 = candidates.get(i).getCoor();
138                for (int j = i + 1; j < size; j++) {
139                    final LatLon c2 = candidates.get(j).getCoor();
140                    final double d = c1.distance(c2);
141                    weights[i] += d;
142                    weights[j] += d;
143                }
144            }
145
146            double east2 = 0;
147            double north2 = 0;
148            double weight = 0;
149            for (int i = 0; i < size; i++) {
150                final EastNorth en = candidates.get(i).getEastNorth();
151                final double w = weights[i];
152                east2 += en.east() * w;
153                north2 += en.north() * w;
154                weight += w;
155            }
156
157            if (weight == 0) // to avoid division by 0
158                return candidates.get(0);
159
160            return new Node(new EastNorth(east2 / weight, north2 / weight));
161        default:
162            throw new IllegalStateException("unacceptable merge-nodes.mode");
163        }
164    }
165
166    /**
167     * Find which node to merge into (i.e. which one will be left)
168     *
169     * @param candidates the collection of candidate nodes
170     * @return the selected target node
171     */
172    public static Node selectTargetNode(Collection<Node> candidates) {
173        Node oldestNode = null;
174        Node targetNode = null;
175        Node lastNode = null;
176        for (Node n : candidates) {
177            if (!n.isNew()) {
178                // Among existing nodes, try to keep the oldest used one
179                if (!n.getReferrers().isEmpty()) {
180                    if (targetNode == null || n.getId() < targetNode.getId()) {
181                        targetNode = n;
182                    }
183                } else if (oldestNode == null || n.getId() < oldestNode.getId()) {
184                    oldestNode = n;
185                }
186            }
187            lastNode = n;
188        }
189        return Optional.ofNullable(targetNode).orElse(oldestNode != null ? oldestNode : lastNode);
190    }
191
192    /**
193     * Fixes the parent ways referring to one of the nodes.
194     *
195     * Replies null, if the ways could not be fixed, i.e. because a way would have to be deleted
196     * which is referred to by a relation.
197     *
198     * @param nodesToDelete the collection of nodes to be deleted
199     * @param targetNode the target node the other nodes are merged to
200     * @return a list of commands; null, if the ways could not be fixed
201     */
202    protected static List<Command> fixParentWays(Collection<Node> nodesToDelete, Node targetNode) {
203        List<Command> cmds = new ArrayList<>();
204        Set<Way> waysToDelete = new HashSet<>();
205
206        for (Way w: (Iterable<Way>) nodesToDelete.stream().flatMap(p -> p.referrers(Way.class))::iterator) {
207            List<Node> newNodes = new ArrayList<>(w.getNodesCount());
208            for (Node n: w.getNodes()) {
209                if (!nodesToDelete.contains(n) && !n.equals(targetNode)) {
210                    newNodes.add(n);
211                } else if (newNodes.isEmpty() || !newNodes.get(newNodes.size()-1).equals(targetNode)) {
212                    // make sure we collapse a sequence of deleted nodes
213                    // to exactly one occurrence of the merged target node
214                    newNodes.add(targetNode);
215                }
216                // else: drop the node
217            }
218            if (newNodes.size() < 2) {
219                if (w.getReferrers().isEmpty()) {
220                    waysToDelete.add(w);
221                } else {
222                    ButtonSpec[] options = {
223                            new ButtonSpec(
224                                    tr("Abort Merging"),
225                                    new ImageProvider("cancel"),
226                                    tr("Click to abort merging nodes"),
227                                    null /* no special help topic */
228                            )
229                    };
230                    HelpAwareOptionPane.showOptionDialog(
231                            MainApplication.getMainFrame(),
232                            tr("Cannot merge nodes: Would have to delete way {0} which is still used by {1}",
233                                DefaultNameFormatter.getInstance().formatAsHtmlUnorderedList(w),
234                                DefaultNameFormatter.getInstance().formatAsHtmlUnorderedList(w.getReferrers(), 20)),
235                            tr("Warning"),
236                            JOptionPane.WARNING_MESSAGE,
237                            null, /* no icon */
238                            options,
239                            options[0],
240                            ht("/Action/MergeNodes#WaysToDeleteStillInUse")
241                    );
242                    return null;
243                }
244            } else if (newNodes.size() < 2 && w.getReferrers().isEmpty()) {
245                waysToDelete.add(w);
246            } else {
247                cmds.add(new ChangeNodesCommand(w, newNodes));
248            }
249        }
250        if (!waysToDelete.isEmpty()) {
251            cmds.add(new DeleteCommand(waysToDelete));
252        }
253        return cmds;
254    }
255
256    /**
257     * Merges the nodes in {@code nodes} at the specified node's location. Uses the dataset
258     * managed by {@code layer} as reference.
259     * @param layer layer the reference data layer. Must not be null
260     * @param nodes the collection of nodes. Ignored if null
261     * @param targetLocationNode this node's location will be used for the target node
262     * @throws IllegalArgumentException if {@code layer} is null
263     */
264    public static void doMergeNodes(OsmDataLayer layer, Collection<Node> nodes, Node targetLocationNode) {
265        if (nodes == null) {
266            return;
267        }
268        Set<Node> allNodes = new HashSet<>(nodes);
269        allNodes.add(targetLocationNode);
270        Node target;
271        if (nodes.contains(targetLocationNode) && !targetLocationNode.isNew()) {
272            target = targetLocationNode; // keep existing targetLocationNode as target to avoid unnecessary changes (see #2447)
273        } else {
274            target = selectTargetNode(allNodes);
275        }
276
277        if (target != null) {
278            Command cmd = mergeNodes(nodes, target, targetLocationNode);
279            if (cmd != null) {
280                UndoRedoHandler.getInstance().add(cmd);
281                layer.data.setSelected(target);
282            }
283        }
284    }
285
286    /**
287     * Merges the nodes in {@code nodes} at the specified node's location.
288     *
289     * @param nodes the collection of nodes. Ignored if null.
290     * @param targetLocationNode this node's location will be used for the targetNode.
291     * @return The command necessary to run in order to perform action, or {@code null} if there is nothing to do
292     * @throws IllegalArgumentException if {@code layer} is null
293     * @since 12689
294     */
295    public static Command mergeNodes(Collection<Node> nodes, Node targetLocationNode) {
296        if (nodes == null) {
297            return null;
298        }
299        Set<Node> allNodes = new HashSet<>(nodes);
300        allNodes.add(targetLocationNode);
301        Node targetNode = selectTargetNode(allNodes);
302        if (targetNode == null) {
303            return null;
304        }
305        return mergeNodes(nodes, targetNode, targetLocationNode);
306    }
307
308    /**
309     * Merges the nodes in <code>nodes</code> onto one of the nodes.
310     *
311     * @param nodes the collection of nodes. Ignored if null.
312     * @param targetNode the target node the collection of nodes is merged to. Must not be null.
313     * @param targetLocationNode this node's location will be used for the targetNode.
314     * @return The command necessary to run in order to perform action, or {@code null} if there is nothing to do
315     * @throws IllegalArgumentException if layer is null
316     */
317    public static Command mergeNodes(Collection<Node> nodes, Node targetNode, Node targetLocationNode) {
318        CheckParameterUtil.ensureParameterNotNull(targetNode, "targetNode");
319        if (nodes == null) {
320            return null;
321        }
322
323        try {
324            TagCollection nodeTags = TagCollection.unionOfAllPrimitives(nodes);
325
326            // the nodes we will have to delete
327            //
328            Collection<Node> nodesToDelete = new HashSet<>(nodes);
329            nodesToDelete.remove(targetNode);
330
331            // fix the ways referring to at least one of the merged nodes
332            //
333            List<Command> wayFixCommands = fixParentWays(nodesToDelete, targetNode);
334            if (wayFixCommands == null) {
335                return null;
336            }
337            List<Command> cmds = new LinkedList<>(wayFixCommands);
338
339            // build the commands
340            //
341            if (!targetNode.equals(targetLocationNode)) {
342                LatLon targetLocationCoor = targetLocationNode.getCoor();
343                if (!Objects.equals(targetNode.getCoor(), targetLocationCoor)) {
344                    Node newTargetNode = new Node(targetNode);
345                    newTargetNode.setCoor(targetLocationCoor);
346                    cmds.add(new ChangeCommand(targetNode, newTargetNode));
347                }
348            }
349            cmds.addAll(CombinePrimitiveResolverDialog.launchIfNecessary(nodeTags, nodes, Collections.singleton(targetNode)));
350            if (!nodesToDelete.isEmpty()) {
351                cmds.add(new DeleteCommand(nodesToDelete));
352            }
353            if (cmds.size() == 1)
354                return cmds.get(0);
355            return cmds.isEmpty() ? null : new SequenceCommand(/* for correct i18n of plural forms - see #9110 */
356                    trn("Merge {0} node", "Merge {0} nodes", nodes.size(), nodes.size()), cmds);
357        } catch (UserCancelException ex) {
358            Logging.trace(ex);
359            return null;
360        }
361    }
362
363    @Override
364    protected void updateEnabledState() {
365        updateEnabledStateOnCurrentSelection();
366    }
367
368    @Override
369    protected void updateEnabledState(Collection<? extends OsmPrimitive> selection) {
370        setEnabled(OsmUtils.isOsmCollectionEditable(selection) && selection.stream().allMatch(osm -> osm instanceof Node));
371    }
372}