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