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

Last change on this file since 6854 was 6801, checked in by simon04, 10 years ago

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