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

Last change on this file since 3530 was 3530, checked in by stoecker, 15 years ago

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