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

Last change on this file since 4104 was 4104, checked in by bastiK, 15 years ago

see #6233 (patch by brycenesbitt) - Updated elements not sorted in upload dialog (Add/Delete are fine)
  • Property svn:eol-style set to native
File size: 15.3 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.Set;
13import java.util.Stack;
14import java.util.logging.Logger;
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.Node;
21import org.openstreetmap.josm.data.osm.OsmPrimitive;
22import org.openstreetmap.josm.data.osm.PrimitiveId;
23import org.openstreetmap.josm.data.osm.Relation;
24import org.openstreetmap.josm.data.osm.RelationMember;
25import org.openstreetmap.josm.data.osm.Way;
26import org.openstreetmap.josm.tools.Utils;
27
28/**
29 * Represents a collection of {@see OsmPrimitive}s which should be uploaded to the
30 * API.
31 * The collection is derived from the modified primitives of an {@see DataSet} and it provides methods
32 * for sorting the objects in upload order.
33 *
34 */
35public class APIDataSet {
36 private LinkedList<OsmPrimitive> toAdd;
37 private LinkedList<OsmPrimitive> toUpdate;
38 private LinkedList<OsmPrimitive> toDelete;
39
40 /**
41 * creates a new empty data set
42 */
43 public APIDataSet() {
44 toAdd = new LinkedList<OsmPrimitive>();
45 toUpdate = new LinkedList<OsmPrimitive>();
46 toDelete = new LinkedList<OsmPrimitive>();
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 toAdd.clear();
57 toUpdate.clear();
58 toDelete.clear();
59
60 for (OsmPrimitive osm :ds.allPrimitives()) {
61 if (osm.get("josm/ignore") != null) {
62 continue;
63 }
64 if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
65 toAdd.add(osm);
66 } else if (osm.isModified() && !osm.isDeleted()) {
67 toUpdate.add(osm);
68 } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
69 toDelete.add(osm);
70 }
71 }
72 sortDeleted();
73 sortNew();
74 sortUpdated();
75 }
76
77 /**
78 * Ensures that primitives are deleted in the following order: Relations, then Ways,
79 * then Nodes.
80 *
81 */
82 protected void sortDeleted() {
83 Collections.sort(
84 toDelete,
85 new Comparator<OsmPrimitive>() {
86 public int compare(OsmPrimitive o1, OsmPrimitive o2) {
87 if (o1 instanceof Node && o2 instanceof Node)
88 return 0;
89 else if (o1 instanceof Node)
90 return 1;
91 else if (o2 instanceof Node)
92 return -1;
93
94 if (o1 instanceof Way && o2 instanceof Way)
95 return 0;
96 else if (o1 instanceof Way && o2 instanceof Relation)
97 return 1;
98 else if (o2 instanceof Way && o1 instanceof Relation)
99 return -1;
100
101 return 0;
102 }
103 }
104 );
105 }
106
107 /**
108 * Ensures that primitives are added in the following order: Nodes, then Ways,
109 * then Relations.
110 *
111 */
112 protected void sortNew() {
113 Collections.sort(
114 toAdd,
115 new Comparator<OsmPrimitive>() {
116 public int compare(OsmPrimitive o1, OsmPrimitive o2) {
117 if (o1 instanceof Node && o2 instanceof Node)
118 return 0;
119 else if (o1 instanceof Node)
120 return -1;
121 else if (o2 instanceof Node)
122 return 1;
123
124 if (o1 instanceof Way && o2 instanceof Way)
125 return 0;
126 else if (o1 instanceof Way && o2 instanceof Relation)
127 return -1;
128 else if (o2 instanceof Way && o1 instanceof Relation)
129 return 1;
130
131 return 0;
132 }
133 }
134 );
135 }
136 /*
137 * Sort list of updated elements, so it looks neat in the confirmation dialog.
138 */
139 protected void sortUpdated() {
140 Collections.sort(
141 toUpdate,
142 new Comparator<OsmPrimitive>() {
143 public int compare(OsmPrimitive o1, OsmPrimitive o2) {
144 if (o1 instanceof Node && o2 instanceof Node)
145 return 0;
146 else if (o1 instanceof Node)
147 return -1;
148 else if (o2 instanceof Node)
149 return 1;
150
151 if (o1 instanceof Way && o2 instanceof Way)
152 return 0;
153 else if (o1 instanceof Way && o2 instanceof Relation)
154 return -1;
155 else if (o2 instanceof Way && o1 instanceof Relation)
156 return 1;
157
158 return 0;
159 }
160 }
161 );
162 }
163
164 /**
165 * initializes the API data set with the modified primitives in <code>ds</code>
166 *
167 * @param ds the data set. Ignored, if null.
168 */
169 public APIDataSet(DataSet ds) {
170 this();
171 init(ds);
172 }
173
174 /**
175 * Replies true if one of the primitives to be updated or to be deleted
176 * participates in the conflict <code>conflict</code>
177 *
178 * @param conflict the conflict
179 * @return true if one of the primitives to be updated or to be deleted
180 * participates in the conflict <code>conflict</code>
181 */
182 public boolean participatesInConflict(Conflict<?> conflict) {
183 if (conflict == null) return false;
184 for (OsmPrimitive p: toUpdate) {
185 if (conflict.isParticipating(p)) return true;
186 }
187 for (OsmPrimitive p: toDelete) {
188 if (conflict.isParticipating(p)) return true;
189 }
190 return false;
191 }
192
193 /**
194 * Replies true if one of the primitives to be updated or to be deleted
195 * participates in at least one conflict in <code>conflicts</code>
196 *
197 * @param conflicts the collection of conflicts
198 * @return true if one of the primitives to be updated or to be deleted
199 * participates in at least one conflict in <code>conflicts</code>
200 */
201 public boolean participatesInConflict(ConflictCollection conflicts) {
202 if (conflicts == null || conflicts.isEmpty()) return false;
203 Set<PrimitiveId> idsParticipatingInConflicts = new HashSet<PrimitiveId>();
204 for (OsmPrimitive p: conflicts.getMyConflictParties()) {
205 idsParticipatingInConflicts.add(p.getPrimitiveId());
206 }
207 for (OsmPrimitive p: conflicts.getTheirConflictParties()) {
208 idsParticipatingInConflicts.add(p.getPrimitiveId());
209 }
210 for (OsmPrimitive p: toUpdate) {
211 if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
212 }
213 for (OsmPrimitive p: toDelete) {
214 if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
215 }
216 return false;
217 }
218
219 /**
220 * initializes the API data set with the primitives in <code>primitives</code>
221 *
222 * @param primitives the collection of primitives
223 */
224 public APIDataSet(Collection<OsmPrimitive> primitives) {
225 this();
226 toAdd.clear();
227 toUpdate.clear();
228 toDelete.clear();
229 for (OsmPrimitive osm: primitives) {
230 if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
231 toAdd.addLast(osm);
232 } else if (osm.isModified() && !osm.isDeleted()) {
233 toUpdate.addLast(osm);
234 } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
235 toDelete.addFirst(osm);
236 }
237 }
238 sortNew();
239 sortDeleted();
240 }
241
242 /**
243 * Replies true if there are no primitives to upload
244 *
245 * @return true if there are no primitives to upload
246 */
247 public boolean isEmpty() {
248 return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty();
249 }
250
251 /**
252 * Replies the primitives which should be added to the OSM database
253 *
254 * @return the primitives which should be added to the OSM database
255 */
256 public List<OsmPrimitive> getPrimitivesToAdd() {
257 return toAdd;
258 }
259
260 /**
261 * Replies the primitives which should be updated in the OSM database
262 *
263 * @return the primitives which should be updated in the OSM database
264 */
265 public List<OsmPrimitive> getPrimitivesToUpdate() {
266 return toUpdate;
267 }
268
269 /**
270 * Replies the primitives which should be deleted in the OSM database
271 *
272 * @return the primitives which should be deleted in the OSM database
273 */
274 public List<OsmPrimitive> getPrimitivesToDelete() {
275 return toDelete;
276 }
277
278 /**
279 * Replies all primitives
280 *
281 * @return all primitives
282 */
283 public List<OsmPrimitive> getPrimitives() {
284 LinkedList<OsmPrimitive> ret = new LinkedList<OsmPrimitive>();
285 ret.addAll(toAdd);
286 ret.addAll(toUpdate);
287 ret.addAll(toDelete);
288 return ret;
289 }
290
291 /**
292 * Replies the number of objects to upload
293 *
294 * @return the number of objects to upload
295 */
296 public int getSize() {
297 return toAdd.size() + toUpdate.size() + toDelete.size();
298 }
299
300 public void removeProcessed(Collection<OsmPrimitive> processed) {
301 if (processed == null) return;
302 toAdd.removeAll(processed);
303 toUpdate.removeAll(processed);
304 toDelete.removeAll(processed);
305 }
306
307 /**
308 * Adjusts the upload order for new relations. Child relations are uploaded first,
309 * parent relations second.
310 *
311 * This method detects cyclic dependencies in new relation. Relations with cyclic
312 * dependencies can't be uploaded.
313 *
314 * @throws CyclicUploadDependencyException thrown, if a cyclic dependency is detected
315 */
316 public void adjustRelationUploadOrder() throws CyclicUploadDependencyException{
317 LinkedList<OsmPrimitive> newToAdd = new LinkedList<OsmPrimitive>();
318 newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
319 newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
320
321 List<Relation> relationsToAdd = new ArrayList<Relation>(Utils.filteredCollection(toAdd, Relation.class));
322 List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
323 newToAdd.addAll(noProblemRelations);
324 relationsToAdd.removeAll(noProblemRelations);
325
326 RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd);
327 newToAdd.addAll(graph.computeUploadOrder());
328 toAdd = newToAdd;
329 }
330
331 /**
332 * Replies the subset of relations in <code>relations</code> which are not referring to any
333 * new relation
334 *
335 * @param relations a list of relations
336 * @return the subset of relations in <code>relations</code> which are not referring to any
337 * new relation
338 */
339 protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
340 List<Relation> ret = new LinkedList<Relation>();
341 for (Relation relation: relations) {
342 boolean refersToNewRelation = false;
343 for (RelationMember m : relation.getMembers()) {
344 if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
345 refersToNewRelation = true;
346 break;
347 }
348 }
349 if (!refersToNewRelation) {
350 ret.add(relation);
351 }
352 }
353 return ret;
354 }
355
356 /**
357 * Utility class to sort a collection of new relations with their dependencies
358 * topologically.
359 *
360 */
361 private class RelationUploadDependencyGraph {
362 @SuppressWarnings("unused")
363 private final Logger logger = Logger.getLogger(RelationUploadDependencyGraph.class.getName());
364 private HashMap<Relation, Set<Relation>> children;
365 private Collection<Relation> relations;
366 private Set<Relation> visited;
367 private List<Relation> uploadOrder;
368
369 public RelationUploadDependencyGraph() {
370 this.children = new HashMap<Relation, Set<Relation>>();
371 this.visited = new HashSet<Relation>();
372 }
373
374 public RelationUploadDependencyGraph(Collection<Relation> relations) {
375 this();
376 build(relations);
377 }
378
379 public void build(Collection<Relation> relations) {
380 this.relations = new HashSet<Relation>();
381 for(Relation relation: relations) {
382 if (!relation.isNewOrUndeleted() ) {
383 continue;
384 }
385 this.relations.add(relation);
386 for (RelationMember m: relation.getMembers()) {
387 if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
388 addDependency(relation, (Relation)m.getMember());
389 }
390 }
391 }
392 }
393
394 public Set<Relation> getChildren(Relation relation) {
395 Set<Relation> p = children.get(relation);
396 if (p == null) {
397 p = new HashSet<Relation>();
398 children.put(relation, p);
399 }
400 return p;
401 }
402
403 public void addDependency(Relation relation, Relation child) {
404 getChildren(relation).add(child);
405 }
406
407 protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException{
408 if (path.contains(current)) {
409 path.push(current);
410 throw new CyclicUploadDependencyException(path);
411 }
412 if (!visited.contains(current)) {
413 path.push(current);
414 visited.add(current);
415 for (Relation dependent : getChildren(current)) {
416 visit(path,dependent);
417 }
418 uploadOrder.add(current);
419 path.pop();
420 }
421 }
422
423 public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
424 visited = new HashSet<Relation>();
425 uploadOrder = new LinkedList<Relation>();
426 Stack<Relation> path = new Stack<Relation>();
427 for (Relation relation: relations) {
428 visit(path, relation);
429 }
430 ArrayList<Relation> ret = new ArrayList<Relation>(relations);
431 Collections.sort(
432 ret,
433 new Comparator<Relation>() {
434 public int compare(Relation o1, Relation o2) {
435 return Integer.valueOf(uploadOrder.indexOf(o1)).compareTo(uploadOrder.indexOf(o2));
436 }
437 }
438 );
439 return ret;
440 }
441 }
442}
Note: See TracBrowser for help on using the repository browser.