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

Last change on this file since 4100 was 4100, checked in by bastiK, 13 years ago

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