001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.command;
003
004import static org.openstreetmap.josm.tools.I18n.tr;
005import static org.openstreetmap.josm.tools.I18n.trn;
006
007import java.util.ArrayList;
008import java.util.Arrays;
009import java.util.Collection;
010import java.util.Collections;
011import java.util.HashSet;
012import java.util.Iterator;
013import java.util.LinkedList;
014import java.util.List;
015import java.util.Objects;
016import java.util.Optional;
017import java.util.Set;
018import java.util.function.Consumer;
019
020import org.openstreetmap.josm.data.osm.DefaultNameFormatter;
021import org.openstreetmap.josm.data.osm.Node;
022import org.openstreetmap.josm.data.osm.OsmPrimitive;
023import org.openstreetmap.josm.data.osm.PrimitiveId;
024import org.openstreetmap.josm.data.osm.Relation;
025import org.openstreetmap.josm.data.osm.RelationMember;
026import org.openstreetmap.josm.data.osm.Way;
027import org.openstreetmap.josm.spi.preferences.Config;
028import org.openstreetmap.josm.tools.CheckParameterUtil;
029import org.openstreetmap.josm.tools.Logging;
030
031/**
032 * Splits a way into multiple ways (all identical except for their node list).
033 *
034 * Ways are just split at the selected nodes.  The nodes remain in their
035 * original order.  Selected nodes at the end of a way are ignored.
036 *
037 * @since 12828 ({@code SplitWayAction} converted to a {@link Command})
038 */
039public class SplitWayCommand extends SequenceCommand {
040
041    private static volatile Consumer<String> warningNotifier = Logging::warn;
042
043    /**
044     * Sets the global warning notifier.
045     * @param notifier warning notifier in charge of displaying warning message, if any. Must not be null
046     */
047    public static void setWarningNotifier(Consumer<String> notifier) {
048        warningNotifier = Objects.requireNonNull(notifier);
049    }
050
051    private final List<? extends PrimitiveId> newSelection;
052    private final Way originalWay;
053    private final List<Way> newWays;
054
055    /**
056     * Create a new {@code SplitWayCommand}.
057     * @param name The description text
058     * @param commandList The sequence of commands that should be executed.
059     * @param newSelection The new list of selected primitives ids (which is saved for later retrieval with {@link #getNewSelection})
060     * @param originalWay The original way being split (which is saved for later retrieval with {@link #getOriginalWay})
061     * @param newWays The resulting new ways (which is saved for later retrieval with {@link #getOriginalWay})
062     */
063    public SplitWayCommand(String name, Collection<Command> commandList,
064            List<? extends PrimitiveId> newSelection, Way originalWay, List<Way> newWays) {
065        super(name, commandList);
066        this.newSelection = newSelection;
067        this.originalWay = originalWay;
068        this.newWays = newWays;
069    }
070
071    /**
072     * Replies the new list of selected primitives ids
073     * @return The new list of selected primitives ids
074     */
075    public List<? extends PrimitiveId> getNewSelection() {
076        return newSelection;
077    }
078
079    /**
080     * Replies the original way being split
081     * @return The original way being split
082     */
083    public Way getOriginalWay() {
084        return originalWay;
085    }
086
087    /**
088     * Replies the resulting new ways
089     * @return The resulting new ways
090     */
091    public List<Way> getNewWays() {
092        return newWays;
093    }
094
095    /**
096     * Determines which way chunk should reuse the old id and its history
097     */
098    @FunctionalInterface
099    public interface Strategy {
100
101        /**
102         * Determines which way chunk should reuse the old id and its history.
103         *
104         * @param wayChunks the way chunks
105         * @return the way to keep
106         */
107        Way determineWayToKeep(Iterable<Way> wayChunks);
108
109        /**
110         * Returns a strategy which selects the way chunk with the highest node count to keep.
111         * @return strategy which selects the way chunk with the highest node count to keep
112         */
113        static Strategy keepLongestChunk() {
114            return wayChunks -> {
115                    Way wayToKeep = null;
116                    for (Way i : wayChunks) {
117                        if (wayToKeep == null || i.getNodesCount() > wayToKeep.getNodesCount()) {
118                            wayToKeep = i;
119                        }
120                    }
121                    return wayToKeep;
122                };
123        }
124
125        /**
126         * Returns a strategy which selects the first way chunk.
127         * @return strategy which selects the first way chunk
128         */
129        static Strategy keepFirstChunk() {
130            return wayChunks -> wayChunks.iterator().next();
131        }
132    }
133
134    /**
135     * Splits the nodes of {@code wayToSplit} into a list of node sequences
136     * which are separated at the nodes in {@code splitPoints}.
137     *
138     * This method displays warning messages if {@code wayToSplit} and/or
139     * {@code splitPoints} aren't consistent.
140     *
141     * Returns null, if building the split chunks fails.
142     *
143     * @param wayToSplit the way to split. Must not be null.
144     * @param splitPoints the nodes where the way is split. Must not be null.
145     * @return the list of chunks
146     */
147    public static List<List<Node>> buildSplitChunks(Way wayToSplit, List<Node> splitPoints) {
148        CheckParameterUtil.ensureParameterNotNull(wayToSplit, "wayToSplit");
149        CheckParameterUtil.ensureParameterNotNull(splitPoints, "splitPoints");
150
151        Set<Node> nodeSet = new HashSet<>(splitPoints);
152        List<List<Node>> wayChunks = new LinkedList<>();
153        List<Node> currentWayChunk = new ArrayList<>();
154        wayChunks.add(currentWayChunk);
155
156        Iterator<Node> it = wayToSplit.getNodes().iterator();
157        while (it.hasNext()) {
158            Node currentNode = it.next();
159            boolean atEndOfWay = currentWayChunk.isEmpty() || !it.hasNext();
160            currentWayChunk.add(currentNode);
161            if (nodeSet.contains(currentNode) && !atEndOfWay) {
162                currentWayChunk = new ArrayList<>();
163                currentWayChunk.add(currentNode);
164                wayChunks.add(currentWayChunk);
165            }
166        }
167
168        // Handle circular ways specially.
169        // If you split at a circular way at two nodes, you just want to split
170        // it at these points, not also at the former endpoint.
171        // So if the last node is the same first node, join the last and the
172        // first way chunk.
173        List<Node> lastWayChunk = wayChunks.get(wayChunks.size() - 1);
174        if (wayChunks.size() >= 2
175                && wayChunks.get(0).get(0) == lastWayChunk.get(lastWayChunk.size() - 1)
176                && !nodeSet.contains(wayChunks.get(0).get(0))) {
177            if (wayChunks.size() == 2) {
178                warningNotifier.accept(tr("You must select two or more nodes to split a circular way."));
179                return null;
180            }
181            lastWayChunk.remove(lastWayChunk.size() - 1);
182            lastWayChunk.addAll(wayChunks.get(0));
183            wayChunks.remove(wayChunks.size() - 1);
184            wayChunks.set(0, lastWayChunk);
185        }
186
187        if (wayChunks.size() < 2) {
188            if (wayChunks.get(0).get(0) == wayChunks.get(0).get(wayChunks.get(0).size() - 1)) {
189                warningNotifier.accept(
190                        tr("You must select two or more nodes to split a circular way."));
191            } else {
192                warningNotifier.accept(
193                        tr("The way cannot be split at the selected nodes. (Hint: Select nodes in the middle of the way.)"));
194            }
195            return null;
196        }
197        return wayChunks;
198    }
199
200    /**
201     * Creates new way objects for the way chunks and transfers the keys from the original way.
202     * @param way the original way whose  keys are transferred
203     * @param wayChunks the way chunks
204     * @return the new way objects
205     */
206    public static List<Way> createNewWaysFromChunks(Way way, Iterable<List<Node>> wayChunks) {
207        final List<Way> newWays = new ArrayList<>();
208        for (List<Node> wayChunk : wayChunks) {
209            Way wayToAdd = new Way();
210            wayToAdd.setKeys(way.getKeys());
211            wayToAdd.setNodes(wayChunk);
212            newWays.add(wayToAdd);
213        }
214        return newWays;
215    }
216
217    /**
218     * Splits the way {@code way} into chunks of {@code wayChunks} and replies
219     * the result of this process in an instance of {@link SplitWayCommand}.
220     *
221     * Note that changes are not applied to the data yet. You have to
222     * submit the command first, i.e. {@code UndoRedoHandler.getInstance().add(result)}.
223     *
224     * @param way the way to split. Must not be null.
225     * @param wayChunks the list of way chunks into the way is split. Must not be null.
226     * @param selection The list of currently selected primitives
227     * @return the result from the split operation
228     */
229    public static SplitWayCommand splitWay(Way way, List<List<Node>> wayChunks, Collection<? extends OsmPrimitive> selection) {
230        return splitWay(way, wayChunks, selection, Strategy.keepLongestChunk());
231    }
232
233    /**
234     * Splits the way {@code way} into chunks of {@code wayChunks} and replies
235     * the result of this process in an instance of {@link SplitWayCommand}.
236     * The {@link SplitWayCommand.Strategy} is used to determine which
237     * way chunk should reuse the old id and its history.
238     *
239     * Note that changes are not applied to the data yet. You have to
240     * submit the command first, i.e. {@code UndoRedoHandler.getInstance().add(result)}.
241     *
242     * @param way the way to split. Must not be null.
243     * @param wayChunks the list of way chunks into the way is split. Must not be null.
244     * @param selection The list of currently selected primitives
245     * @param splitStrategy The strategy used to determine which way chunk should reuse the old id and its history
246     * @return the result from the split operation
247     */
248    public static SplitWayCommand splitWay(Way way, List<List<Node>> wayChunks,
249            Collection<? extends OsmPrimitive> selection, Strategy splitStrategy) {
250        // build a list of commands, and also a new selection list
251        final List<OsmPrimitive> newSelection = new ArrayList<>(selection.size() + wayChunks.size());
252        newSelection.addAll(selection);
253
254        // Create all potential new ways
255        final List<Way> newWays = createNewWaysFromChunks(way, wayChunks);
256
257        // Determine which part reuses the existing way
258        final Way wayToKeep = splitStrategy.determineWayToKeep(newWays);
259
260        return wayToKeep != null ? doSplitWay(way, wayToKeep, newWays, newSelection) : null;
261    }
262
263    /**
264     * Effectively constructs the {@link SplitWayCommand}.
265     * This method is only public for {@code SplitWayAction}.
266     *
267     * @param way the way to split. Must not be null.
268     * @param wayToKeep way chunk which should reuse the old id and its history
269     * @param newWays potential new ways
270     * @param newSelection new selection list to update (optional: can be null)
271     * @return the {@code SplitWayCommand}
272     */
273    public static SplitWayCommand doSplitWay(Way way, Way wayToKeep, List<Way> newWays, List<OsmPrimitive> newSelection) {
274
275        Collection<Command> commandList = new ArrayList<>(newWays.size());
276        Collection<String> nowarnroles = Config.getPref().getList("way.split.roles.nowarn",
277                Arrays.asList("outer", "inner", "forward", "backward", "north", "south", "east", "west"));
278
279        // Change the original way
280        final Way changedWay = new Way(way);
281        changedWay.setNodes(wayToKeep.getNodes());
282        commandList.add(new ChangeCommand(way, changedWay));
283        if (/*!isMapModeDraw &&*/ newSelection != null && !newSelection.contains(way)) {
284            newSelection.add(way);
285        }
286        final int indexOfWayToKeep = newWays.indexOf(wayToKeep);
287        newWays.remove(wayToKeep);
288
289        if (/*!isMapModeDraw &&*/ newSelection != null) {
290            newSelection.addAll(newWays);
291        }
292        for (Way wayToAdd : newWays) {
293            commandList.add(new AddCommand(way.getDataSet(), wayToAdd));
294        }
295
296        boolean warnmerole = false;
297        boolean warnme = false;
298        // now copy all relations to new way also
299
300        for (Relation r : OsmPrimitive.getParentRelations(Collections.singleton(way))) {
301            if (!r.isUsable()) {
302                continue;
303            }
304            Relation c = null;
305            String type = Optional.ofNullable(r.get("type")).orElse("");
306
307            int ic = 0;
308            int ir = 0;
309            List<RelationMember> relationMembers = r.getMembers();
310            for (RelationMember rm: relationMembers) {
311                if (rm.isWay() && rm.getMember() == way) {
312                    boolean insert = true;
313                    if ("restriction".equals(type) || "destination_sign".equals(type)) {
314                        /* this code assumes the restriction is correct. No real error checking done */
315                        String role = rm.getRole();
316                        if ("from".equals(role) || "to".equals(role)) {
317                            OsmPrimitive via = findVia(r, type);
318                            List<Node> nodes = new ArrayList<>();
319                            if (via != null) {
320                                if (via instanceof Node) {
321                                    nodes.add((Node) via);
322                                } else if (via instanceof Way) {
323                                    nodes.add(((Way) via).lastNode());
324                                    nodes.add(((Way) via).firstNode());
325                                }
326                            }
327                            Way res = null;
328                            for (Node n : nodes) {
329                                if (changedWay.isFirstLastNode(n)) {
330                                    res = way;
331                                }
332                            }
333                            if (res == null) {
334                                for (Way wayToAdd : newWays) {
335                                    for (Node n : nodes) {
336                                        if (wayToAdd.isFirstLastNode(n)) {
337                                            res = wayToAdd;
338                                        }
339                                    }
340                                }
341                                if (res != null) {
342                                    if (c == null) {
343                                        c = new Relation(r);
344                                    }
345                                    c.addMember(new RelationMember(role, res));
346                                    c.removeMembersFor(way);
347                                    insert = false;
348                                }
349                            } else {
350                                insert = false;
351                            }
352                        } else if (!"via".equals(role)) {
353                            warnme = true;
354                        }
355                    } else if (!("route".equals(type)) && !("multipolygon".equals(type))) {
356                        warnme = true;
357                    }
358                    if (c == null) {
359                        c = new Relation(r);
360                    }
361
362                    if (insert) {
363                        if (rm.hasRole() && !nowarnroles.contains(rm.getRole())) {
364                            warnmerole = true;
365                        }
366
367                        Boolean backwards = null;
368                        int k = 1;
369                        while (ir - k >= 0 || ir + k < relationMembers.size()) {
370                            if ((ir - k >= 0) && relationMembers.get(ir - k).isWay()) {
371                                Way w = relationMembers.get(ir - k).getWay();
372                                if ((w.lastNode() == way.firstNode()) || w.firstNode() == way.firstNode()) {
373                                    backwards = Boolean.FALSE;
374                                } else if ((w.firstNode() == way.lastNode()) || w.lastNode() == way.lastNode()) {
375                                    backwards = Boolean.TRUE;
376                                }
377                                break;
378                            }
379                            if ((ir + k < relationMembers.size()) && relationMembers.get(ir + k).isWay()) {
380                                Way w = relationMembers.get(ir + k).getWay();
381                                if ((w.lastNode() == way.firstNode()) || w.firstNode() == way.firstNode()) {
382                                    backwards = Boolean.TRUE;
383                                } else if ((w.firstNode() == way.lastNode()) || w.lastNode() == way.lastNode()) {
384                                    backwards = Boolean.FALSE;
385                                }
386                                break;
387                            }
388                            k++;
389                        }
390
391                        int j = ic;
392                        final List<Way> waysToAddBefore = newWays.subList(0, indexOfWayToKeep);
393                        for (Way wayToAdd : waysToAddBefore) {
394                            RelationMember em = new RelationMember(rm.getRole(), wayToAdd);
395                            j++;
396                            if (Boolean.TRUE.equals(backwards)) {
397                                c.addMember(ic + 1, em);
398                            } else {
399                                c.addMember(j - 1, em);
400                            }
401                        }
402                        final List<Way> waysToAddAfter = newWays.subList(indexOfWayToKeep, newWays.size());
403                        for (Way wayToAdd : waysToAddAfter) {
404                            RelationMember em = new RelationMember(rm.getRole(), wayToAdd);
405                            j++;
406                            if (Boolean.TRUE.equals(backwards)) {
407                                c.addMember(ic, em);
408                            } else {
409                                c.addMember(j, em);
410                            }
411                        }
412                        ic = j;
413                    }
414                }
415                ic++;
416                ir++;
417            }
418
419            if (c != null) {
420                commandList.add(new ChangeCommand(r.getDataSet(), r, c));
421            }
422        }
423        if (warnmerole) {
424            warningNotifier.accept(
425                    tr("A role based relation membership was copied to all new ways.<br>You should verify this and correct it when necessary."));
426        } else if (warnme) {
427            warningNotifier.accept(
428                    tr("A relation membership was copied to all new ways.<br>You should verify this and correct it when necessary."));
429        }
430
431        return new SplitWayCommand(
432                    /* for correct i18n of plural forms - see #9110 */
433                    trn("Split way {0} into {1} part", "Split way {0} into {1} parts", newWays.size() + 1,
434                            way.getDisplayName(DefaultNameFormatter.getInstance()), newWays.size() + 1),
435                    commandList,
436                    newSelection,
437                    way,
438                    newWays
439            );
440    }
441
442    static OsmPrimitive findVia(Relation r, String type) {
443        if (type != null) {
444            switch (type) {
445            case "restriction":
446                return findRelationMember(r, "via").orElse(null);
447            case "destination_sign":
448                // Prefer intersection over sign, see #12347
449                return findRelationMember(r, "intersection").orElse(findRelationMember(r, "sign").orElse(null));
450            default:
451                return null;
452            }
453        }
454        return null;
455    }
456
457    static Optional<OsmPrimitive> findRelationMember(Relation r, String role) {
458        return r.getMembers().stream().filter(rmv -> role.equals(rmv.getRole()))
459                .map(RelationMember::getMember).findAny();
460    }
461
462    /**
463     * Splits the way {@code way} at the nodes in {@code atNodes} and replies
464     * the result of this process in an instance of {@link SplitWayCommand}.
465     *
466     * Note that changes are not applied to the data yet. You have to
467     * submit the command first, i.e. {@code UndoRedoHandler.getInstance().add(result)}.
468     *
469     * Replies null if the way couldn't be split at the given nodes.
470     *
471     * @param way the way to split. Must not be null.
472     * @param atNodes the list of nodes where the way is split. Must not be null.
473     * @param selection The list of currently selected primitives
474     * @return the result from the split operation
475     */
476    public static SplitWayCommand split(Way way, List<Node> atNodes, Collection<? extends OsmPrimitive> selection) {
477        List<List<Node>> chunks = buildSplitChunks(way, atNodes);
478        return chunks != null ? splitWay(way, chunks, selection) : null;
479    }
480}