001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data;
003
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Comparator;
007import java.util.HashMap;
008import java.util.HashSet;
009import java.util.LinkedList;
010import java.util.List;
011import java.util.Map;
012import java.util.Set;
013import java.util.Stack;
014import java.util.stream.Collectors;
015import java.util.stream.Stream;
016
017import org.openstreetmap.josm.data.conflict.ConflictCollection;
018import org.openstreetmap.josm.data.osm.CyclicUploadDependencyException;
019import org.openstreetmap.josm.data.osm.DataSet;
020import org.openstreetmap.josm.data.osm.IPrimitive;
021import org.openstreetmap.josm.data.osm.Node;
022import org.openstreetmap.josm.data.osm.OsmPrimitive;
023import org.openstreetmap.josm.data.osm.OsmPrimitiveComparator;
024import org.openstreetmap.josm.data.osm.PrimitiveId;
025import org.openstreetmap.josm.data.osm.Relation;
026import org.openstreetmap.josm.data.osm.RelationMember;
027import org.openstreetmap.josm.data.osm.Way;
028import org.openstreetmap.josm.tools.Logging;
029import org.openstreetmap.josm.tools.Utils;
030
031/**
032 * Represents a collection of {@link OsmPrimitive}s which should be uploaded to the API.
033 * The collection is derived from the modified primitives of an {@link DataSet} and it provides methods
034 * for sorting the objects in upload order.
035 * @since 2025
036 */
037public class APIDataSet {
038    private List<OsmPrimitive> toAdd;
039    private final List<OsmPrimitive> toUpdate;
040    private List<OsmPrimitive> toDelete;
041
042    /**
043     * The type of operation we can perform with OSM API on a primitive.
044     * @since 13161
045     */
046    public enum APIOperation {
047        /** Add a new primitive */
048        ADD,
049        /** Update an existing primitive */
050        UPDATE,
051        /** Delete an existing primitive */
052        DELETE;
053
054        /**
055         * Determines the API operation to perform on a primitive.
056         * @param osm OSM primitive
057         * @return the API operation to perform on {@code osm}
058         */
059        public static APIOperation of(OsmPrimitive osm) {
060            if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
061                return ADD;
062            } else if (osm.isModified() && !osm.isDeleted()) {
063                return UPDATE;
064            } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
065                return DELETE;
066            }
067            return null;
068        }
069    }
070
071    /**
072     * creates a new empty data set
073     */
074    public APIDataSet() {
075        toAdd = new LinkedList<>();
076        toUpdate = new LinkedList<>();
077        toDelete = new LinkedList<>();
078    }
079
080    /**
081     * initializes the API data set with the modified primitives in <code>ds</code>
082     *
083     * @param ds the data set. Ignored, if null.
084     */
085    public void init(DataSet ds) {
086        if (ds == null) return;
087        init(ds.allPrimitives());
088    }
089
090    /**
091     * Initializes the API data set with the modified primitives, ignores unmodified primitives.
092     *
093     * @param primitives the primitives
094     */
095    public final void init(Collection<OsmPrimitive> primitives) {
096        toAdd.clear();
097        toUpdate.clear();
098        toDelete.clear();
099
100        for (OsmPrimitive osm :primitives) {
101            APIOperation op = APIOperation.of(osm);
102            if (op != null) {
103                switch (op) {
104                    case ADD: toAdd.add(osm); break;
105                    case UPDATE: toUpdate.add(osm); break;
106                    case DELETE: toDelete.add(osm); break;
107                    default: Logging.trace("Ignored primitive {0} -> {1}", osm, op);
108                }
109            }
110        }
111        final Comparator<OsmPrimitive> orderingNodesWaysRelations = OsmPrimitiveComparator.orderingNodesWaysRelations();
112        final Comparator<OsmPrimitive> byUniqueId = OsmPrimitiveComparator.comparingUniqueId();
113        toAdd.sort(orderingNodesWaysRelations.thenComparing(byUniqueId));
114        toUpdate.sort(orderingNodesWaysRelations.thenComparing(byUniqueId));
115        toDelete.sort(orderingNodesWaysRelations.reversed().thenComparing(byUniqueId));
116    }
117
118    /**
119     * initializes the API data set with the modified primitives in <code>ds</code>
120     *
121     * @param ds the data set. Ignored, if null.
122     */
123    public APIDataSet(DataSet ds) {
124        this();
125        init(ds);
126    }
127
128    /**
129     * Replies true if one of the primitives to be updated or to be deleted
130     * participates in at least one conflict in <code>conflicts</code>
131     *
132     * @param conflicts the collection of conflicts
133     * @return true if one of the primitives to be updated or to be deleted
134     * participates in at least one conflict in <code>conflicts</code>
135     */
136    public boolean participatesInConflict(ConflictCollection conflicts) {
137        if (conflicts == null || conflicts.isEmpty()) return false;
138        Set<PrimitiveId> idsParticipatingInConflicts = conflicts.get().stream()
139                .flatMap(c -> Stream.of(c.getMy(), c.getTheir()))
140                .map(OsmPrimitive::getPrimitiveId)
141                .collect(Collectors.toSet());
142        return Stream.of(toUpdate, toDelete)
143                .flatMap(Collection::stream)
144                .map(OsmPrimitive::getPrimitiveId)
145                .anyMatch(idsParticipatingInConflicts::contains);
146    }
147
148    /**
149     * initializes the API data set with the primitives in <code>primitives</code>
150     *
151     * @param primitives the collection of primitives
152     */
153    public APIDataSet(Collection<OsmPrimitive> primitives) {
154        this();
155        init(primitives);
156    }
157
158    /**
159     * Replies true if there are no primitives to upload
160     *
161     * @return true if there are no primitives to upload
162     */
163    public boolean isEmpty() {
164        return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty();
165    }
166
167    /**
168     * Replies the primitives which should be added to the OSM database
169     *
170     * @return the primitives which should be added to the OSM database
171     */
172    public List<OsmPrimitive> getPrimitivesToAdd() {
173        return toAdd;
174    }
175
176    /**
177     * Replies the primitives which should be updated in the OSM database
178     *
179     * @return the primitives which should be updated in the OSM database
180     */
181    public List<OsmPrimitive> getPrimitivesToUpdate() {
182        return toUpdate;
183    }
184
185    /**
186     * Replies the primitives which should be deleted in the OSM database
187     *
188     * @return the primitives which should be deleted in the OSM database
189     */
190    public List<OsmPrimitive> getPrimitivesToDelete() {
191        return toDelete;
192    }
193
194    /**
195     * Replies all primitives
196     *
197     * @return all primitives
198     */
199    public List<OsmPrimitive> getPrimitives() {
200        List<OsmPrimitive> ret = new LinkedList<>();
201        ret.addAll(toAdd);
202        ret.addAll(toUpdate);
203        ret.addAll(toDelete);
204        return ret;
205    }
206
207    /**
208     * Replies the number of objects to upload
209     *
210     * @return the number of objects to upload
211     */
212    public int getSize() {
213        return toAdd.size() + toUpdate.size() + toDelete.size();
214    }
215
216    /**
217     * Removes the given primitives from this {@link APIDataSet}
218     * @param processed The primitives to remove
219     */
220    public void removeProcessed(Collection<IPrimitive> processed) {
221        if (processed == null) return;
222        toAdd.removeAll(processed);
223        toUpdate.removeAll(processed);
224        toDelete.removeAll(processed);
225    }
226
227    /**
228     * Adjusts the upload order for new relations. Child relations are uploaded first,
229     * parent relations second.
230     *
231     * This method detects cyclic dependencies in new relation. Relations with cyclic
232     * dependencies can't be uploaded.
233     *
234     * @throws CyclicUploadDependencyException if a cyclic dependency is detected
235     */
236    public void adjustRelationUploadOrder() throws CyclicUploadDependencyException {
237        List<OsmPrimitive> newToAdd = new LinkedList<>();
238        newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
239        newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
240
241        List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class));
242        List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
243        newToAdd.addAll(noProblemRelations);
244        relationsToAdd.removeAll(noProblemRelations);
245
246        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
247        newToAdd.addAll(graph.computeUploadOrder(false));
248        toAdd = newToAdd;
249
250        List<OsmPrimitive> newToDelete = new LinkedList<>();
251        graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
252        newToDelete.addAll(graph.computeUploadOrder(true));
253        newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
254        newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
255        toDelete = newToDelete;
256    }
257
258    /**
259     * Replies the subset of relations in <code>relations</code> which are not referring to any
260     * new relation
261     *
262     * @param relations a list of relations
263     * @return the subset of relations in <code>relations</code> which are not referring to any
264     * new relation
265     */
266    protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
267        List<Relation> ret = new LinkedList<>();
268        for (Relation relation: relations) {
269            boolean refersToNewRelation = relation.getMembers().stream()
270                    .anyMatch(m -> m.isRelation() && m.getMember().isNewOrUndeleted());
271            if (!refersToNewRelation) {
272                ret.add(relation);
273            }
274        }
275        return ret;
276    }
277
278    /**
279     * Utility class to sort a collection of new relations with their dependencies
280     * topologically.
281     *
282     */
283    private static class RelationUploadDependencyGraph {
284        private final Map<Relation, Set<Relation>> children = new HashMap<>();
285        private Collection<Relation> relations;
286        private Set<Relation> visited = new HashSet<>();
287        private List<Relation> uploadOrder;
288        private final boolean newOrUndeleted;
289
290        RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
291            this.newOrUndeleted = newOrUndeleted;
292            build(relations);
293        }
294
295        public final void build(Collection<Relation> relations) {
296            this.relations = new HashSet<>();
297            for (Relation relation: relations) {
298                if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
299                    continue;
300                }
301                this.relations.add(relation);
302                for (RelationMember m: relation.getMembers()) {
303                    if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
304                        addDependency(relation, (Relation) m.getMember());
305                    }
306                }
307            }
308        }
309
310        public Set<Relation> getChildren(Relation relation) {
311            return children.computeIfAbsent(relation, k -> new HashSet<>());
312        }
313
314        public void addDependency(Relation relation, Relation child) {
315            getChildren(relation).add(child);
316        }
317
318        protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException {
319            if (path.contains(current)) {
320                path.push(current);
321                throw new CyclicUploadDependencyException(path);
322            }
323            if (!visited.contains(current)) {
324                path.push(current);
325                visited.add(current);
326                for (Relation dependent : getChildren(current)) {
327                    visit(path, dependent);
328                }
329                uploadOrder.add(current);
330                path.pop();
331            }
332        }
333
334        public List<Relation> computeUploadOrder(boolean reverse) throws CyclicUploadDependencyException {
335            visited = new HashSet<>();
336            uploadOrder = new LinkedList<>();
337            Stack<Relation> path = new Stack<>();
338            for (Relation relation: relations) {
339                visit(path, relation);
340            }
341            List<Relation> ret = new ArrayList<>(relations);
342            Comparator<? super Relation> cmpr = Comparator.comparingInt(uploadOrder::indexOf);
343            if (reverse) {
344                cmpr = cmpr.reversed();
345            }
346            ret.sort(cmpr);
347            return ret;
348        }
349    }
350}