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

Last change on this file since 5436 was 5266, checked in by bastiK, 14 years ago

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