001// License: GPL. For details, see LICENSE file.
002package org.openstreetmap.josm.data;
003
004import java.util.ArrayList;
005import java.util.Collection;
006import java.util.Collections;
007import java.util.Comparator;
008import java.util.HashMap;
009import java.util.HashSet;
010import java.util.LinkedList;
011import java.util.List;
012import java.util.Map;
013import java.util.Set;
014import java.util.Stack;
015
016import org.openstreetmap.josm.actions.upload.CyclicUploadDependencyException;
017import org.openstreetmap.josm.data.conflict.Conflict;
018import org.openstreetmap.josm.data.conflict.ConflictCollection;
019import org.openstreetmap.josm.data.osm.DataSet;
020import org.openstreetmap.josm.data.osm.IPrimitive;
021import org.openstreetmap.josm.data.osm.Node;
022import org.openstreetmap.josm.data.osm.OsmPrimitive;
023import org.openstreetmap.josm.data.osm.OsmPrimitiveComparator;
024import org.openstreetmap.josm.data.osm.PrimitiveId;
025import org.openstreetmap.josm.data.osm.Relation;
026import org.openstreetmap.josm.data.osm.RelationMember;
027import org.openstreetmap.josm.data.osm.Way;
028import org.openstreetmap.josm.tools.Utils;
029
030/**
031 * Represents a collection of {@link OsmPrimitive}s which should be uploaded to the
032 * API.
033 * The collection is derived from the modified primitives of an {@link DataSet} and it provides methods
034 * for sorting the objects in upload order.
035 *
036 */
037public class APIDataSet {
038    private List<OsmPrimitive> toAdd;
039    private List<OsmPrimitive> toUpdate;
040    private List<OsmPrimitive> toDelete;
041
042    /**
043     * creates a new empty data set
044     */
045    public APIDataSet() {
046        toAdd = new LinkedList<OsmPrimitive>();
047        toUpdate = new LinkedList<OsmPrimitive>();
048        toDelete = new LinkedList<OsmPrimitive>();
049    }
050
051    /**
052     * initializes the API data set with the modified primitives in <code>ds</code>
053     *
054     * @param ds the data set. Ignored, if null.
055     */
056    public void init(DataSet ds) {
057        if (ds == null) return;
058        init(ds.allPrimitives());
059    }
060
061    public void init(Collection<OsmPrimitive> primitives) {
062        toAdd.clear();
063        toUpdate.clear();
064        toDelete.clear();
065
066        for (OsmPrimitive osm :primitives) {
067            if (osm.get("josm/ignore") != null) {
068                continue;
069            }
070            if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
071                toAdd.add(osm);
072            } else if (osm.isModified() && !osm.isDeleted()) {
073                toUpdate.add(osm);
074            } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
075                toDelete.add(osm);
076            }
077        }
078        OsmPrimitiveComparator c = new OsmPrimitiveComparator();
079        c.relationsFirst = true;
080        Collections.sort(toDelete, c);
081        Collections.sort(toAdd, c);
082        Collections.sort(toUpdate, c);
083    }
084
085    /**
086     * initializes the API data set with the modified primitives in <code>ds</code>
087     *
088     * @param ds the data set. Ignored, if null.
089     */
090    public APIDataSet(DataSet ds) {
091        this();
092        init(ds);
093    }
094
095    /**
096     * Replies true if one of the primitives to be updated or to be deleted
097     * participates in the conflict <code>conflict</code>
098     *
099     * @param conflict the conflict
100     * @return true if one of the primitives to be updated or to be deleted
101     * participates in the conflict <code>conflict</code>
102     */
103    public boolean participatesInConflict(Conflict<?> conflict) {
104        if (conflict == null) return false;
105        for (OsmPrimitive p: toUpdate) {
106            if (conflict.isParticipating(p)) return true;
107        }
108        for (OsmPrimitive p: toDelete) {
109            if (conflict.isParticipating(p)) return true;
110        }
111        return false;
112    }
113
114    /**
115     * Replies true if one of the primitives to be updated or to be deleted
116     * participates in at least one conflict in <code>conflicts</code>
117     *
118     * @param conflicts the collection of conflicts
119     * @return true if one of the primitives to be updated or to be deleted
120     * participates in at least one conflict in <code>conflicts</code>
121     */
122    public boolean participatesInConflict(ConflictCollection conflicts) {
123        if (conflicts == null || conflicts.isEmpty()) return false;
124        Set<PrimitiveId> idsParticipatingInConflicts = new HashSet<PrimitiveId>();
125        for (OsmPrimitive p: conflicts.getMyConflictParties()) {
126            idsParticipatingInConflicts.add(p.getPrimitiveId());
127        }
128        for (OsmPrimitive p: conflicts.getTheirConflictParties()) {
129            idsParticipatingInConflicts.add(p.getPrimitiveId());
130        }
131        for (OsmPrimitive p: toUpdate) {
132            if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
133        }
134        for (OsmPrimitive p: toDelete) {
135            if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
136        }
137        return false;
138    }
139
140    /**
141     * initializes the API data set with the primitives in <code>primitives</code>
142     *
143     * @param primitives the collection of primitives
144     */
145    public APIDataSet(Collection<OsmPrimitive> primitives) {
146        this();
147        init(primitives);
148    }
149
150    /**
151     * Replies true if there are no primitives to upload
152     *
153     * @return true if there are no primitives to upload
154     */
155    public boolean isEmpty() {
156        return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty();
157    }
158
159    /**
160     * Replies the primitives which should be added to the OSM database
161     *
162     * @return the primitives which should be added to the OSM database
163     */
164    public List<OsmPrimitive> getPrimitivesToAdd() {
165        return toAdd;
166    }
167
168    /**
169     * Replies the primitives which should be updated in the OSM database
170     *
171     * @return the primitives which should be updated in the OSM database
172     */
173    public List<OsmPrimitive> getPrimitivesToUpdate() {
174        return toUpdate;
175    }
176
177    /**
178     * Replies the primitives which should be deleted in the OSM database
179     *
180     * @return the primitives which should be deleted in the OSM database
181     */
182    public List<OsmPrimitive> getPrimitivesToDelete() {
183        return toDelete;
184    }
185
186    /**
187     * Replies all primitives
188     *
189     * @return all primitives
190     */
191    public List<OsmPrimitive> getPrimitives() {
192        LinkedList<OsmPrimitive> ret = new LinkedList<OsmPrimitive>();
193        ret.addAll(toAdd);
194        ret.addAll(toUpdate);
195        ret.addAll(toDelete);
196        return ret;
197    }
198
199    /**
200     * Replies the number of objects to upload
201     *
202     * @return the number of objects to upload
203     */
204    public int getSize() {
205        return toAdd.size() + toUpdate.size() + toDelete.size();
206    }
207
208    public void removeProcessed(Collection<IPrimitive> processed) {
209        if (processed == null) return;
210        toAdd.removeAll(processed);
211        toUpdate.removeAll(processed);
212        toDelete.removeAll(processed);
213    }
214
215    /**
216     * Adjusts the upload order for new relations. Child relations are uploaded first,
217     * parent relations second.
218     *
219     * This method detects cyclic dependencies in new relation. Relations with cyclic
220     * dependencies can't be uploaded.
221     *
222     * @throws CyclicUploadDependencyException thrown, if a cyclic dependency is detected
223     */
224    public void adjustRelationUploadOrder() throws CyclicUploadDependencyException{
225        LinkedList<OsmPrimitive> newToAdd = new LinkedList<OsmPrimitive>();
226        newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
227        newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
228
229        List<Relation> relationsToAdd = new ArrayList<Relation>(Utils.filteredCollection(toAdd, Relation.class));
230        List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
231        newToAdd.addAll(noProblemRelations);
232        relationsToAdd.removeAll(noProblemRelations);
233
234        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd);
235        newToAdd.addAll(graph.computeUploadOrder());
236        toAdd = newToAdd;
237    }
238
239    /**
240     * Replies the subset of relations in <code>relations</code> which are not referring to any
241     * new relation
242     *
243     * @param relations a list of relations
244     * @return the subset of relations in <code>relations</code> which are not referring to any
245     * new relation
246     */
247    protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
248        List<Relation> ret = new LinkedList<Relation>();
249        for (Relation relation: relations) {
250            boolean refersToNewRelation = false;
251            for (RelationMember m : relation.getMembers()) {
252                if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
253                    refersToNewRelation = true;
254                    break;
255                }
256            }
257            if (!refersToNewRelation) {
258                ret.add(relation);
259            }
260        }
261        return ret;
262    }
263
264    /**
265     * Utility class to sort a collection of new relations with their dependencies
266     * topologically.
267     *
268     */
269    private static class RelationUploadDependencyGraph {
270        private Map<Relation, Set<Relation>> children;
271        private Collection<Relation> relations;
272        private Set<Relation> visited;
273        private List<Relation> uploadOrder;
274
275        public RelationUploadDependencyGraph() {
276            this.children = new HashMap<Relation, Set<Relation>>();
277            this.visited = new HashSet<Relation>();
278        }
279
280        public RelationUploadDependencyGraph(Collection<Relation> relations) {
281            this();
282            build(relations);
283        }
284
285        public void build(Collection<Relation> relations) {
286            this.relations = new HashSet<Relation>();
287            for(Relation relation: relations) {
288                if (!relation.isNewOrUndeleted() ) {
289                    continue;
290                }
291                this.relations.add(relation);
292                for (RelationMember m: relation.getMembers()) {
293                    if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
294                        addDependency(relation, (Relation)m.getMember());
295                    }
296                }
297            }
298        }
299
300        public Set<Relation> getChildren(Relation relation) {
301            Set<Relation> p = children.get(relation);
302            if (p == null) {
303                p = new HashSet<Relation>();
304                children.put(relation, p);
305            }
306            return p;
307        }
308
309        public void addDependency(Relation relation, Relation child) {
310            getChildren(relation).add(child);
311        }
312
313        protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException{
314            if (path.contains(current)) {
315                path.push(current);
316                throw new CyclicUploadDependencyException(path);
317            }
318            if (!visited.contains(current)) {
319                path.push(current);
320                visited.add(current);
321                for (Relation dependent : getChildren(current)) {
322                    visit(path,dependent);
323                }
324                uploadOrder.add(current);
325                path.pop();
326            }
327        }
328
329        public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
330            visited = new HashSet<Relation>();
331            uploadOrder = new LinkedList<Relation>();
332            Stack<Relation> path = new Stack<Relation>();
333            for (Relation relation: relations) {
334                visit(path, relation);
335            }
336            List<Relation> ret = new ArrayList<Relation>(relations);
337            Collections.sort(
338                    ret,
339                    new Comparator<Relation>() {
340                        @Override
341                        public int compare(Relation o1, Relation o2) {
342                            return Integer.valueOf(uploadOrder.indexOf(o1)).compareTo(uploadOrder.indexOf(o2));
343                        }
344                    }
345                    );
346            return ret;
347        }
348    }
349}