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.Collections;
007import java.util.Comparator;
008import java.util.HashMap;
009import java.util.HashSet;
010import java.util.LinkedList;
011import java.util.List;
012import java.util.Map;
013import java.util.Set;
014import java.util.Stack;
015
016import org.openstreetmap.josm.actions.upload.CyclicUploadDependencyException;
017import org.openstreetmap.josm.data.conflict.Conflict;
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    public final void init(Collection<OsmPrimitive> primitives) {
061        toAdd.clear();
062        toUpdate.clear();
063        toDelete.clear();
064
065        for (OsmPrimitive osm :primitives) {
066            if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
067                toAdd.add(osm);
068            } else if (osm.isModified() && !osm.isDeleted()) {
069                toUpdate.add(osm);
070            } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
071                toDelete.add(osm);
072            }
073        }
074        OsmPrimitiveComparator c = new OsmPrimitiveComparator(false, true);
075        Collections.sort(toDelete, c);
076        Collections.sort(toAdd, c);
077        Collections.sort(toUpdate, c);
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 APIDataSet(DataSet ds) {
086        this();
087        init(ds);
088    }
089
090    /**
091     * Replies true if one of the primitives to be updated or to be deleted
092     * participates in the conflict <code>conflict</code>
093     *
094     * @param conflict the conflict
095     * @return true if one of the primitives to be updated or to be deleted
096     * participates in the conflict <code>conflict</code>
097     */
098    public boolean participatesInConflict(Conflict<?> conflict) {
099        if (conflict == null) return false;
100        for (OsmPrimitive p: toUpdate) {
101            if (conflict.isParticipating(p)) return true;
102        }
103        for (OsmPrimitive p: toDelete) {
104            if (conflict.isParticipating(p)) return true;
105        }
106        return false;
107    }
108
109    /**
110     * Replies true if one of the primitives to be updated or to be deleted
111     * participates in at least one conflict in <code>conflicts</code>
112     *
113     * @param conflicts the collection of conflicts
114     * @return true if one of the primitives to be updated or to be deleted
115     * participates in at least one conflict in <code>conflicts</code>
116     */
117    public boolean participatesInConflict(ConflictCollection conflicts) {
118        if (conflicts == null || conflicts.isEmpty()) return false;
119        Set<PrimitiveId> idsParticipatingInConflicts = new HashSet<>();
120        for (OsmPrimitive p: conflicts.getMyConflictParties()) {
121            idsParticipatingInConflicts.add(p.getPrimitiveId());
122        }
123        for (OsmPrimitive p: conflicts.getTheirConflictParties()) {
124            idsParticipatingInConflicts.add(p.getPrimitiveId());
125        }
126        for (OsmPrimitive p: toUpdate) {
127            if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
128        }
129        for (OsmPrimitive p: toDelete) {
130            if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
131        }
132        return false;
133    }
134
135    /**
136     * initializes the API data set with the primitives in <code>primitives</code>
137     *
138     * @param primitives the collection of primitives
139     */
140    public APIDataSet(Collection<OsmPrimitive> primitives) {
141        this();
142        init(primitives);
143    }
144
145    /**
146     * Replies true if there are no primitives to upload
147     *
148     * @return true if there are no primitives to upload
149     */
150    public boolean isEmpty() {
151        return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty();
152    }
153
154    /**
155     * Replies the primitives which should be added to the OSM database
156     *
157     * @return the primitives which should be added to the OSM database
158     */
159    public List<OsmPrimitive> getPrimitivesToAdd() {
160        return toAdd;
161    }
162
163    /**
164     * Replies the primitives which should be updated in the OSM database
165     *
166     * @return the primitives which should be updated in the OSM database
167     */
168    public List<OsmPrimitive> getPrimitivesToUpdate() {
169        return toUpdate;
170    }
171
172    /**
173     * Replies the primitives which should be deleted in the OSM database
174     *
175     * @return the primitives which should be deleted in the OSM database
176     */
177    public List<OsmPrimitive> getPrimitivesToDelete() {
178        return toDelete;
179    }
180
181    /**
182     * Replies all primitives
183     *
184     * @return all primitives
185     */
186    public List<OsmPrimitive> getPrimitives() {
187        LinkedList<OsmPrimitive> ret = new LinkedList<>();
188        ret.addAll(toAdd);
189        ret.addAll(toUpdate);
190        ret.addAll(toDelete);
191        return ret;
192    }
193
194    /**
195     * Replies the number of objects to upload
196     *
197     * @return the number of objects to upload
198     */
199    public int getSize() {
200        return toAdd.size() + toUpdate.size() + toDelete.size();
201    }
202
203    public void removeProcessed(Collection<IPrimitive> processed) {
204        if (processed == null) return;
205        toAdd.removeAll(processed);
206        toUpdate.removeAll(processed);
207        toDelete.removeAll(processed);
208    }
209
210    /**
211     * Adjusts the upload order for new relations. Child relations are uploaded first,
212     * parent relations second.
213     *
214     * This method detects cyclic dependencies in new relation. Relations with cyclic
215     * dependencies can't be uploaded.
216     *
217     * @throws CyclicUploadDependencyException thrown, if a cyclic dependency is detected
218     */
219    public void adjustRelationUploadOrder() throws CyclicUploadDependencyException{
220        LinkedList<OsmPrimitive> newToAdd = new LinkedList<>();
221        newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
222        newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
223
224        List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class));
225        List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
226        newToAdd.addAll(noProblemRelations);
227        relationsToAdd.removeAll(noProblemRelations);
228
229        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
230        newToAdd.addAll(graph.computeUploadOrder());
231        toAdd = newToAdd;
232
233        LinkedList<OsmPrimitive> newToDelete = new LinkedList<>();
234        graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
235        newToDelete.addAll(graph.computeUploadOrder());
236        newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
237        newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
238        toDelete = newToDelete;
239    }
240
241    /**
242     * Replies the subset of relations in <code>relations</code> which are not referring to any
243     * new relation
244     *
245     * @param relations a list of relations
246     * @return the subset of relations in <code>relations</code> which are not referring to any
247     * new relation
248     */
249    protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
250        List<Relation> ret = new LinkedList<>();
251        for (Relation relation: relations) {
252            boolean refersToNewRelation = false;
253            for (RelationMember m : relation.getMembers()) {
254                if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
255                    refersToNewRelation = true;
256                    break;
257                }
258            }
259            if (!refersToNewRelation) {
260                ret.add(relation);
261            }
262        }
263        return ret;
264    }
265
266    /**
267     * Utility class to sort a collection of new relations with their dependencies
268     * topologically.
269     *
270     */
271    private static class RelationUploadDependencyGraph {
272        private Map<Relation, Set<Relation>> children = new HashMap<>();
273        private Collection<Relation> relations;
274        private Set<Relation> visited = new HashSet<>();
275        private List<Relation> uploadOrder;
276        private final boolean newOrUndeleted;
277
278        public RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
279            this.newOrUndeleted = newOrUndeleted;
280            build(relations);
281        }
282
283        public final void build(Collection<Relation> relations) {
284            this.relations = new HashSet<>();
285            for(Relation relation: relations) {
286                if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
287                    continue;
288                }
289                this.relations.add(relation);
290                for (RelationMember m: relation.getMembers()) {
291                    if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
292                        addDependency(relation, (Relation)m.getMember());
293                    }
294                }
295            }
296        }
297
298        public Set<Relation> getChildren(Relation relation) {
299            Set<Relation> p = children.get(relation);
300            if (p == null) {
301                p = new HashSet<>();
302                children.put(relation, p);
303            }
304            return p;
305        }
306
307        public void addDependency(Relation relation, Relation child) {
308            getChildren(relation).add(child);
309        }
310
311        protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException{
312            if (path.contains(current)) {
313                path.push(current);
314                throw new CyclicUploadDependencyException(path);
315            }
316            if (!visited.contains(current)) {
317                path.push(current);
318                visited.add(current);
319                for (Relation dependent : getChildren(current)) {
320                    visit(path,dependent);
321                }
322                uploadOrder.add(current);
323                path.pop();
324            }
325        }
326
327        public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
328            visited = new HashSet<>();
329            uploadOrder = new LinkedList<>();
330            Stack<Relation> path = new Stack<>();
331            for (Relation relation: relations) {
332                visit(path, relation);
333            }
334            List<Relation> ret = new ArrayList<>(relations);
335            Collections.sort(
336                    ret,
337                    new Comparator<Relation>() {
338                        @Override
339                        public int compare(Relation o1, Relation o2) {
340                            return Integer.valueOf(uploadOrder.indexOf(o1)).compareTo(uploadOrder.indexOf(o2));
341                        }
342                    }
343                    );
344            return ret;
345        }
346    }
347}