001    // License: GPL. For details, see LICENSE file.
002    package org.openstreetmap.josm.data;
003    
004    import java.util.ArrayList;
005    import java.util.Collection;
006    import java.util.Collections;
007    import java.util.Comparator;
008    import java.util.HashMap;
009    import java.util.HashSet;
010    import java.util.LinkedList;
011    import java.util.List;
012    import java.util.Set;
013    import java.util.Stack;
014    
015    import org.openstreetmap.josm.actions.upload.CyclicUploadDependencyException;
016    import org.openstreetmap.josm.data.conflict.Conflict;
017    import org.openstreetmap.josm.data.conflict.ConflictCollection;
018    import org.openstreetmap.josm.data.osm.DataSet;
019    import org.openstreetmap.josm.data.osm.IPrimitive;
020    import org.openstreetmap.josm.data.osm.Node;
021    import org.openstreetmap.josm.data.osm.OsmPrimitive;
022    import org.openstreetmap.josm.data.osm.OsmPrimitiveComparator;
023    import org.openstreetmap.josm.data.osm.PrimitiveId;
024    import org.openstreetmap.josm.data.osm.Relation;
025    import org.openstreetmap.josm.data.osm.RelationMember;
026    import org.openstreetmap.josm.data.osm.Way;
027    import org.openstreetmap.josm.tools.Utils;
028    
029    /**
030     * Represents a collection of {@link OsmPrimitive}s which should be uploaded to the
031     * API.
032     * The collection is derived from the modified primitives of an {@link DataSet} and it provides methods
033     * for sorting the objects in upload order.
034     *
035     */
036    public class APIDataSet {
037        private LinkedList<OsmPrimitive> toAdd;
038        private LinkedList<OsmPrimitive> toUpdate;
039        private LinkedList<OsmPrimitive> toDelete;
040    
041        /**
042         * creates a new empty data set
043         */
044        public APIDataSet() {
045            toAdd = new LinkedList<OsmPrimitive>();
046            toUpdate = new LinkedList<OsmPrimitive>();
047            toDelete = new LinkedList<OsmPrimitive>();
048        }
049    
050        /**
051         * initializes the API data set with the modified primitives in <code>ds</code>
052         *
053         * @param ds the data set. Ignored, if null.
054         */
055        public void init(DataSet ds) {
056            if (ds == null) return;
057            toAdd.clear();
058            toUpdate.clear();
059            toDelete.clear();
060    
061            for (OsmPrimitive osm :ds.allPrimitives()) {
062                if (osm.get("josm/ignore") != null) {
063                    continue;
064                }
065                if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
066                    toAdd.add(osm);
067                } else if (osm.isModified() && !osm.isDeleted()) {
068                    toUpdate.add(osm);
069                } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
070                    toDelete.add(osm);
071                }
072            }
073            OsmPrimitiveComparator c = new OsmPrimitiveComparator();
074            c.relationsFirst = true;
075            Collections.sort(toDelete, c);
076            Collections.sort(toAdd, c);
077            Collections.sort(toUpdate, c);
078        }
079    
080        /**
081         * initializes the API data set with the modified primitives in <code>ds</code>
082         *
083         * @param ds the data set. Ignored, if null.
084         */
085        public APIDataSet(DataSet ds) {
086            this();
087            init(ds);
088        }
089    
090        /**
091         * Replies true if one of the primitives to be updated or to be deleted
092         * participates in the conflict <code>conflict</code>
093         *
094         * @param conflict the conflict
095         * @return true if one of the primitives to be updated or to be deleted
096         * participates in the conflict <code>conflict</code>
097         */
098        public boolean participatesInConflict(Conflict<?> conflict) {
099            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    }