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

Last change on this file since 4191 was 4191, checked in by stoecker, 13 years ago

remove old debug stuff
  • 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.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.Node;
20import org.openstreetmap.josm.data.osm.OsmPrimitive;
21import org.openstreetmap.josm.data.osm.OsmPrimitiveComparator;
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 OsmPrimitiveComparator c = new OsmPrimitiveComparator();
73 c.relationsFirst = true;
74 Collections.sort(toDelete, c);
75 Collections.sort(toAdd, c);
76 Collections.sort(toUpdate, 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<PrimitiveId>();
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 toAdd.clear();
142 toUpdate.clear();
143 toDelete.clear();
144 for (OsmPrimitive osm: primitives) {
145 if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
146 toAdd.addLast(osm);
147 } else if (osm.isModified() && !osm.isDeleted()) {
148 toUpdate.addLast(osm);
149 } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
150 toDelete.addFirst(osm);
151 }
152 }
153 OsmPrimitiveComparator c = new OsmPrimitiveComparator();
154 c.relationsFirst = true;
155 Collections.sort(toDelete, c);
156 Collections.sort(toAdd, c);
157 Collections.sort(toUpdate, c);
158 }
159
160 /**
161 * Replies true if there are no primitives to upload
162 *
163 * @return true if there are no primitives to upload
164 */
165 public boolean isEmpty() {
166 return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty();
167 }
168
169 /**
170 * Replies the primitives which should be added to the OSM database
171 *
172 * @return the primitives which should be added to the OSM database
173 */
174 public List<OsmPrimitive> getPrimitivesToAdd() {
175 return toAdd;
176 }
177
178 /**
179 * Replies the primitives which should be updated in the OSM database
180 *
181 * @return the primitives which should be updated in the OSM database
182 */
183 public List<OsmPrimitive> getPrimitivesToUpdate() {
184 return toUpdate;
185 }
186
187 /**
188 * Replies the primitives which should be deleted in the OSM database
189 *
190 * @return the primitives which should be deleted in the OSM database
191 */
192 public List<OsmPrimitive> getPrimitivesToDelete() {
193 return toDelete;
194 }
195
196 /**
197 * Replies all primitives
198 *
199 * @return all primitives
200 */
201 public List<OsmPrimitive> getPrimitives() {
202 LinkedList<OsmPrimitive> ret = new LinkedList<OsmPrimitive>();
203 ret.addAll(toAdd);
204 ret.addAll(toUpdate);
205 ret.addAll(toDelete);
206 return ret;
207 }
208
209 /**
210 * Replies the number of objects to upload
211 *
212 * @return the number of objects to upload
213 */
214 public int getSize() {
215 return toAdd.size() + toUpdate.size() + toDelete.size();
216 }
217
218 public void removeProcessed(Collection<OsmPrimitive> processed) {
219 if (processed == null) return;
220 toAdd.removeAll(processed);
221 toUpdate.removeAll(processed);
222 toDelete.removeAll(processed);
223 }
224
225 /**
226 * Adjusts the upload order for new relations. Child relations are uploaded first,
227 * parent relations second.
228 *
229 * This method detects cyclic dependencies in new relation. Relations with cyclic
230 * dependencies can't be uploaded.
231 *
232 * @throws CyclicUploadDependencyException thrown, if a cyclic dependency is detected
233 */
234 public void adjustRelationUploadOrder() throws CyclicUploadDependencyException{
235 LinkedList<OsmPrimitive> newToAdd = new LinkedList<OsmPrimitive>();
236 newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
237 newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
238
239 List<Relation> relationsToAdd = new ArrayList<Relation>(Utils.filteredCollection(toAdd, Relation.class));
240 List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
241 newToAdd.addAll(noProblemRelations);
242 relationsToAdd.removeAll(noProblemRelations);
243
244 RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd);
245 newToAdd.addAll(graph.computeUploadOrder());
246 toAdd = newToAdd;
247 }
248
249 /**
250 * Replies the subset of relations in <code>relations</code> which are not referring to any
251 * new relation
252 *
253 * @param relations a list of relations
254 * @return the subset of relations in <code>relations</code> which are not referring to any
255 * new relation
256 */
257 protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
258 List<Relation> ret = new LinkedList<Relation>();
259 for (Relation relation: relations) {
260 boolean refersToNewRelation = false;
261 for (RelationMember m : relation.getMembers()) {
262 if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
263 refersToNewRelation = true;
264 break;
265 }
266 }
267 if (!refersToNewRelation) {
268 ret.add(relation);
269 }
270 }
271 return ret;
272 }
273
274 /**
275 * Utility class to sort a collection of new relations with their dependencies
276 * topologically.
277 *
278 */
279 private class RelationUploadDependencyGraph {
280 private HashMap<Relation, Set<Relation>> children;
281 private Collection<Relation> relations;
282 private Set<Relation> visited;
283 private List<Relation> uploadOrder;
284
285 public RelationUploadDependencyGraph() {
286 this.children = new HashMap<Relation, Set<Relation>>();
287 this.visited = new HashSet<Relation>();
288 }
289
290 public RelationUploadDependencyGraph(Collection<Relation> relations) {
291 this();
292 build(relations);
293 }
294
295 public void build(Collection<Relation> relations) {
296 this.relations = new HashSet<Relation>();
297 for(Relation relation: relations) {
298 if (!relation.isNewOrUndeleted() ) {
299 continue;
300 }
301 this.relations.add(relation);
302 for (RelationMember m: relation.getMembers()) {
303 if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
304 addDependency(relation, (Relation)m.getMember());
305 }
306 }
307 }
308 }
309
310 public Set<Relation> getChildren(Relation relation) {
311 Set<Relation> p = children.get(relation);
312 if (p == null) {
313 p = new HashSet<Relation>();
314 children.put(relation, p);
315 }
316 return p;
317 }
318
319 public void addDependency(Relation relation, Relation child) {
320 getChildren(relation).add(child);
321 }
322
323 protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException{
324 if (path.contains(current)) {
325 path.push(current);
326 throw new CyclicUploadDependencyException(path);
327 }
328 if (!visited.contains(current)) {
329 path.push(current);
330 visited.add(current);
331 for (Relation dependent : getChildren(current)) {
332 visit(path,dependent);
333 }
334 uploadOrder.add(current);
335 path.pop();
336 }
337 }
338
339 public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
340 visited = new HashSet<Relation>();
341 uploadOrder = new LinkedList<Relation>();
342 Stack<Relation> path = new Stack<Relation>();
343 for (Relation relation: relations) {
344 visit(path, relation);
345 }
346 ArrayList<Relation> ret = new ArrayList<Relation>(relations);
347 Collections.sort(
348 ret,
349 new Comparator<Relation>() {
350 public int compare(Relation o1, Relation o2) {
351 return Integer.valueOf(uploadOrder.indexOf(o1)).compareTo(uploadOrder.indexOf(o2));
352 }
353 }
354 );
355 return ret;
356 }
357 }
358}
Note: See TracBrowser for help on using the repository browser.