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