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