source: josm/trunk/src/org/openstreetmap/josm/data/APIDataSet.java @ 13018

Last change on this file since 13018 was 13018, checked in by bastiK, 16 months ago

fixed #15374 - problem deleting multilevel relations

  • Property svn:eol-style set to native
File size: 11.5 KB
Line 
1// License: GPL. For details, see LICENSE file.
2package org.openstreetmap.josm.data;
3
4import java.util.ArrayList;
5import java.util.Collection;
6import java.util.Comparator;
7import java.util.HashMap;
8import java.util.HashSet;
9import java.util.LinkedList;
10import java.util.List;
11import java.util.Map;
12import java.util.Set;
13import java.util.Stack;
14import java.util.stream.Collectors;
15import java.util.stream.Stream;
16
17import org.openstreetmap.josm.data.conflict.ConflictCollection;
18import org.openstreetmap.josm.data.osm.CyclicUploadDependencyException;
19import org.openstreetmap.josm.data.osm.DataSet;
20import org.openstreetmap.josm.data.osm.IPrimitive;
21import org.openstreetmap.josm.data.osm.Node;
22import org.openstreetmap.josm.data.osm.OsmPrimitive;
23import org.openstreetmap.josm.data.osm.OsmPrimitiveComparator;
24import org.openstreetmap.josm.data.osm.PrimitiveId;
25import org.openstreetmap.josm.data.osm.Relation;
26import org.openstreetmap.josm.data.osm.RelationMember;
27import org.openstreetmap.josm.data.osm.Way;
28import org.openstreetmap.josm.tools.Utils;
29
30/**
31 * Represents a collection of {@link OsmPrimitive}s which should be uploaded to the API.
32 * The collection is derived from the modified primitives of an {@link DataSet} and it provides methods
33 * for sorting the objects in upload order.
34 * @since 2025
35 */
36public class APIDataSet {
37    private List<OsmPrimitive> toAdd;
38    private List<OsmPrimitive> toUpdate;
39    private List<OsmPrimitive> toDelete;
40
41    /**
42     * creates a new empty data set
43     */
44    public APIDataSet() {
45        toAdd = new LinkedList<>();
46        toUpdate = new LinkedList<>();
47        toDelete = new LinkedList<>();
48    }
49
50    /**
51     * initializes the API data set with the modified primitives in <code>ds</code>
52     *
53     * @param ds the data set. Ignored, if null.
54     */
55    public void init(DataSet ds) {
56        if (ds == null) return;
57        init(ds.allPrimitives());
58    }
59
60    /**
61     * Initializes the API data set with the modified primitives, ignores unmodified primitives.
62     *
63     * @param primitives the primitives
64     */
65    public final void init(Collection<OsmPrimitive> primitives) {
66        toAdd.clear();
67        toUpdate.clear();
68        toDelete.clear();
69
70        for (OsmPrimitive osm :primitives) {
71            if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
72                toAdd.add(osm);
73            } else if (osm.isModified() && !osm.isDeleted()) {
74                toUpdate.add(osm);
75            } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
76                toDelete.add(osm);
77            }
78        }
79        final Comparator<OsmPrimitive> orderingNodesWaysRelations = OsmPrimitiveComparator.orderingNodesWaysRelations();
80        final Comparator<OsmPrimitive> byUniqueId = OsmPrimitiveComparator.comparingUniqueId();
81        toAdd.sort(orderingNodesWaysRelations.thenComparing(byUniqueId));
82        toUpdate.sort(orderingNodesWaysRelations.thenComparing(byUniqueId));
83        toDelete.sort(orderingNodesWaysRelations.reversed().thenComparing(byUniqueId));
84    }
85
86    /**
87     * initializes the API data set with the modified primitives in <code>ds</code>
88     *
89     * @param ds the data set. Ignored, if null.
90     */
91    public APIDataSet(DataSet ds) {
92        this();
93        init(ds);
94    }
95
96    /**
97     * Replies true if one of the primitives to be updated or to be deleted
98     * participates in at least one conflict in <code>conflicts</code>
99     *
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    /**
185     * Removes the given primitives from this {@link APIDataSet}
186     * @param processed The primitives to remove
187     */
188    public void removeProcessed(Collection<IPrimitive> processed) {
189        if (processed == null) return;
190        toAdd.removeAll(processed);
191        toUpdate.removeAll(processed);
192        toDelete.removeAll(processed);
193    }
194
195    /**
196     * Adjusts the upload order for new relations. Child relations are uploaded first,
197     * parent relations second.
198     *
199     * This method detects cyclic dependencies in new relation. Relations with cyclic
200     * dependencies can't be uploaded.
201     *
202     * @throws CyclicUploadDependencyException if a cyclic dependency is detected
203     */
204    public void adjustRelationUploadOrder() throws CyclicUploadDependencyException {
205        List<OsmPrimitive> newToAdd = new LinkedList<>();
206        newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
207        newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
208
209        List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class));
210        List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
211        newToAdd.addAll(noProblemRelations);
212        relationsToAdd.removeAll(noProblemRelations);
213
214        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
215        newToAdd.addAll(graph.computeUploadOrder(false));
216        toAdd = newToAdd;
217
218        List<OsmPrimitive> newToDelete = new LinkedList<>();
219        graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
220        newToDelete.addAll(graph.computeUploadOrder(true));
221        newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
222        newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
223        toDelete = newToDelete;
224    }
225
226    /**
227     * Replies the subset of relations in <code>relations</code> which are not referring to any
228     * new relation
229     *
230     * @param relations a list of relations
231     * @return the subset of relations in <code>relations</code> which are not referring to any
232     * new relation
233     */
234    protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
235        List<Relation> ret = new LinkedList<>();
236        for (Relation relation: relations) {
237            boolean refersToNewRelation = false;
238            for (RelationMember m : relation.getMembers()) {
239                if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
240                    refersToNewRelation = true;
241                    break;
242                }
243            }
244            if (!refersToNewRelation) {
245                ret.add(relation);
246            }
247        }
248        return ret;
249    }
250
251    /**
252     * Utility class to sort a collection of new relations with their dependencies
253     * topologically.
254     *
255     */
256    private static class RelationUploadDependencyGraph {
257        private final Map<Relation, Set<Relation>> children = new HashMap<>();
258        private Collection<Relation> relations;
259        private Set<Relation> visited = new HashSet<>();
260        private List<Relation> uploadOrder;
261        private final boolean newOrUndeleted;
262
263        RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
264            this.newOrUndeleted = newOrUndeleted;
265            build(relations);
266        }
267
268        public final void build(Collection<Relation> relations) {
269            this.relations = new HashSet<>();
270            for (Relation relation: relations) {
271                if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
272                    continue;
273                }
274                this.relations.add(relation);
275                for (RelationMember m: relation.getMembers()) {
276                    if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
277                        addDependency(relation, (Relation) m.getMember());
278                    }
279                }
280            }
281        }
282
283        public Set<Relation> getChildren(Relation relation) {
284            return children.computeIfAbsent(relation, k -> new HashSet<>());
285        }
286
287        public void addDependency(Relation relation, Relation child) {
288            getChildren(relation).add(child);
289        }
290
291        protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException {
292            if (path.contains(current)) {
293                path.push(current);
294                throw new CyclicUploadDependencyException(path);
295            }
296            if (!visited.contains(current)) {
297                path.push(current);
298                visited.add(current);
299                for (Relation dependent : getChildren(current)) {
300                    visit(path, dependent);
301                }
302                uploadOrder.add(current);
303                path.pop();
304            }
305        }
306
307        public List<Relation> computeUploadOrder(boolean reverse) throws CyclicUploadDependencyException {
308            visited = new HashSet<>();
309            uploadOrder = new LinkedList<>();
310            Stack<Relation> path = new Stack<>();
311            for (Relation relation: relations) {
312                visit(path, relation);
313            }
314            List<Relation> ret = new ArrayList<>(relations);
315            Comparator<? super Relation> cmpr = Comparator.comparingInt(uploadOrder::indexOf);
316            if (reverse) {
317                cmpr = cmpr.reversed();
318            }
319            ret.sort(cmpr);
320            return ret;
321        }
322    }
323}
Note: See TracBrowser for help on using the repository browser.