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

Last change on this file since 10759 was 10647, checked in by Don-vip, 8 years ago

see #11390 - use functional comparators
  • Property svn:eol-style set to native
File size: 11.7 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;
14
15import org.openstreetmap.josm.actions.upload.CyclicUploadDependencyException;
16import org.openstreetmap.josm.data.conflict.Conflict;
17import org.openstreetmap.josm.data.conflict.ConflictCollection;
18import org.openstreetmap.josm.data.osm.DataSet;
19import org.openstreetmap.josm.data.osm.IPrimitive;
20import org.openstreetmap.josm.data.osm.Node;
21import org.openstreetmap.josm.data.osm.OsmPrimitive;
22import org.openstreetmap.josm.data.osm.OsmPrimitiveComparator;
23import org.openstreetmap.josm.data.osm.PrimitiveId;
24import org.openstreetmap.josm.data.osm.Relation;
25import org.openstreetmap.josm.data.osm.RelationMember;
26import org.openstreetmap.josm.data.osm.Way;
27import org.openstreetmap.josm.tools.Utils;
28
29/**
30 * Represents a collection of {@link OsmPrimitive}s which should be uploaded to the API.
31 * The collection is derived from the modified primitives of an {@link DataSet} and it provides methods
32 * for sorting the objects in upload order.
33 * @since 2025
34 */
35public class APIDataSet {
36 private List<OsmPrimitive> toAdd;
37 private List<OsmPrimitive> toUpdate;
38 private List<OsmPrimitive> toDelete;
39
40 /**
41 * creates a new empty data set
42 */
43 public APIDataSet() {
44 toAdd = new LinkedList<>();
45 toUpdate = new LinkedList<>();
46 toDelete = new LinkedList<>();
47 }
48
49 /**
50 * initializes the API data set with the modified primitives in <code>ds</code>
51 *
52 * @param ds the data set. Ignored, if null.
53 */
54 public void init(DataSet ds) {
55 if (ds == null) return;
56 init(ds.allPrimitives());
57 }
58
59 public final void init(Collection<OsmPrimitive> primitives) {
60 toAdd.clear();
61 toUpdate.clear();
62 toDelete.clear();
63
64 for (OsmPrimitive osm :primitives) {
65 if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
66 toAdd.add(osm);
67 } else if (osm.isModified() && !osm.isDeleted()) {
68 toUpdate.add(osm);
69 } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
70 toDelete.add(osm);
71 }
72 }
73 OsmPrimitiveComparator c = new OsmPrimitiveComparator(false, true);
74 toDelete.sort(c);
75 toAdd.sort(c);
76 toUpdate.sort(c);
77 }
78
79 /**
80 * initializes the API data set with the modified primitives in <code>ds</code>
81 *
82 * @param ds the data set. Ignored, if null.
83 */
84 public APIDataSet(DataSet ds) {
85 this();
86 init(ds);
87 }
88
89 /**
90 * Replies true if one of the primitives to be updated or to be deleted
91 * participates in the conflict <code>conflict</code>
92 *
93 * @param conflict the conflict
94 * @return true if one of the primitives to be updated or to be deleted
95 * participates in the conflict <code>conflict</code>
96 */
97 public boolean participatesInConflict(Conflict<?> conflict) {
98 if (conflict == null) return false;
99 for (OsmPrimitive p: toUpdate) {
100 if (conflict.isParticipating(p)) return true;
101 }
102 for (OsmPrimitive p: toDelete) {
103 if (conflict.isParticipating(p)) return true;
104 }
105 return false;
106 }
107
108 /**
109 * Replies true if one of the primitives to be updated or to be deleted
110 * participates in at least one conflict in <code>conflicts</code>
111 *
112 * @param conflicts the collection of conflicts
113 * @return true if one of the primitives to be updated or to be deleted
114 * participates in at least one conflict in <code>conflicts</code>
115 */
116 public boolean participatesInConflict(ConflictCollection conflicts) {
117 if (conflicts == null || conflicts.isEmpty()) return false;
118 Set<PrimitiveId> idsParticipatingInConflicts = new HashSet<>();
119 for (OsmPrimitive p: conflicts.getMyConflictParties()) {
120 idsParticipatingInConflicts.add(p.getPrimitiveId());
121 }
122 for (OsmPrimitive p: conflicts.getTheirConflictParties()) {
123 idsParticipatingInConflicts.add(p.getPrimitiveId());
124 }
125 for (OsmPrimitive p: toUpdate) {
126 if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
127 }
128 for (OsmPrimitive p: toDelete) {
129 if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
130 }
131 return false;
132 }
133
134 /**
135 * initializes the API data set with the primitives in <code>primitives</code>
136 *
137 * @param primitives the collection of primitives
138 */
139 public APIDataSet(Collection<OsmPrimitive> primitives) {
140 this();
141 init(primitives);
142 }
143
144 /**
145 * Replies true if there are no primitives to upload
146 *
147 * @return true if there are no primitives to upload
148 */
149 public boolean isEmpty() {
150 return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty();
151 }
152
153 /**
154 * Replies the primitives which should be added to the OSM database
155 *
156 * @return the primitives which should be added to the OSM database
157 */
158 public List<OsmPrimitive> getPrimitivesToAdd() {
159 return toAdd;
160 }
161
162 /**
163 * Replies the primitives which should be updated in the OSM database
164 *
165 * @return the primitives which should be updated in the OSM database
166 */
167 public List<OsmPrimitive> getPrimitivesToUpdate() {
168 return toUpdate;
169 }
170
171 /**
172 * Replies the primitives which should be deleted in the OSM database
173 *
174 * @return the primitives which should be deleted in the OSM database
175 */
176 public List<OsmPrimitive> getPrimitivesToDelete() {
177 return toDelete;
178 }
179
180 /**
181 * Replies all primitives
182 *
183 * @return all primitives
184 */
185 public List<OsmPrimitive> getPrimitives() {
186 List<OsmPrimitive> ret = new LinkedList<>();
187 ret.addAll(toAdd);
188 ret.addAll(toUpdate);
189 ret.addAll(toDelete);
190 return ret;
191 }
192
193 /**
194 * Replies the number of objects to upload
195 *
196 * @return the number of objects to upload
197 */
198 public int getSize() {
199 return toAdd.size() + toUpdate.size() + toDelete.size();
200 }
201
202 public void removeProcessed(Collection<IPrimitive> processed) {
203 if (processed == null) return;
204 toAdd.removeAll(processed);
205 toUpdate.removeAll(processed);
206 toDelete.removeAll(processed);
207 }
208
209 /**
210 * Adjusts the upload order for new relations. Child relations are uploaded first,
211 * parent relations second.
212 *
213 * This method detects cyclic dependencies in new relation. Relations with cyclic
214 * dependencies can't be uploaded.
215 *
216 * @throws CyclicUploadDependencyException if a cyclic dependency is detected
217 */
218 public void adjustRelationUploadOrder() throws CyclicUploadDependencyException {
219 List<OsmPrimitive> newToAdd = new LinkedList<>();
220 newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
221 newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
222
223 List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class));
224 List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
225 newToAdd.addAll(noProblemRelations);
226 relationsToAdd.removeAll(noProblemRelations);
227
228 RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
229 newToAdd.addAll(graph.computeUploadOrder());
230 toAdd = newToAdd;
231
232 List<OsmPrimitive> newToDelete = new LinkedList<>();
233 graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
234 newToDelete.addAll(graph.computeUploadOrder());
235 newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
236 newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
237 toDelete = newToDelete;
238 }
239
240 /**
241 * Replies the subset of relations in <code>relations</code> which are not referring to any
242 * new relation
243 *
244 * @param relations a list of relations
245 * @return the subset of relations in <code>relations</code> which are not referring to any
246 * new relation
247 */
248 protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
249 List<Relation> ret = new LinkedList<>();
250 for (Relation relation: relations) {
251 boolean refersToNewRelation = false;
252 for (RelationMember m : relation.getMembers()) {
253 if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
254 refersToNewRelation = true;
255 break;
256 }
257 }
258 if (!refersToNewRelation) {
259 ret.add(relation);
260 }
261 }
262 return ret;
263 }
264
265 /**
266 * Utility class to sort a collection of new relations with their dependencies
267 * topologically.
268 *
269 */
270 private static class RelationUploadDependencyGraph {
271 private final Map<Relation, Set<Relation>> children = new HashMap<>();
272 private Collection<Relation> relations;
273 private Set<Relation> visited = new HashSet<>();
274 private List<Relation> uploadOrder;
275 private final boolean newOrUndeleted;
276
277 RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
278 this.newOrUndeleted = newOrUndeleted;
279 build(relations);
280 }
281
282 public final void build(Collection<Relation> relations) {
283 this.relations = new HashSet<>();
284 for (Relation relation: relations) {
285 if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
286 continue;
287 }
288 this.relations.add(relation);
289 for (RelationMember m: relation.getMembers()) {
290 if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
291 addDependency(relation, (Relation) m.getMember());
292 }
293 }
294 }
295 }
296
297 public Set<Relation> getChildren(Relation relation) {
298 Set<Relation> p = children.get(relation);
299 if (p == null) {
300 p = new HashSet<>();
301 children.put(relation, p);
302 }
303 return p;
304 }
305
306 public void addDependency(Relation relation, Relation child) {
307 getChildren(relation).add(child);
308 }
309
310 protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException {
311 if (path.contains(current)) {
312 path.push(current);
313 throw new CyclicUploadDependencyException(path);
314 }
315 if (!visited.contains(current)) {
316 path.push(current);
317 visited.add(current);
318 for (Relation dependent : getChildren(current)) {
319 visit(path, dependent);
320 }
321 uploadOrder.add(current);
322 path.pop();
323 }
324 }
325
326 public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
327 visited = new HashSet<>();
328 uploadOrder = new LinkedList<>();
329 Stack<Relation> path = new Stack<>();
330 for (Relation relation: relations) {
331 visit(path, relation);
332 }
333 List<Relation> ret = new ArrayList<>(relations);
334 ret.sort(Comparator.comparingInt(uploadOrder::indexOf));
335 return ret;
336 }
337 }
338}
Note: See TracBrowser for help on using the repository browser.