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