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<>();
047        toUpdate = new LinkedList<>();
048        toDelete = new LinkedList<>();
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 final 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(false, true);
079        Collections.sort(toDelete, c);
080        Collections.sort(toAdd, c);
081        Collections.sort(toUpdate, c);
082    }
083
084    /**
085     * initializes the API data set with the modified primitives in <code>ds</code>
086     *
087     * @param ds the data set. Ignored, if null.
088     */
089    public APIDataSet(DataSet ds) {
090        this();
091        init(ds);
092    }
093
094    /**
095     * Replies true if one of the primitives to be updated or to be deleted
096     * participates in the conflict <code>conflict</code>
097     *
098     * @param conflict the conflict
099     * @return true if one of the primitives to be updated or to be deleted
100     * participates in the conflict <code>conflict</code>
101     */
102    public boolean participatesInConflict(Conflict<?> conflict) {
103        if (conflict == null) return false;
104        for (OsmPrimitive p: toUpdate) {
105            if (conflict.isParticipating(p)) return true;
106        }
107        for (OsmPrimitive p: toDelete) {
108            if (conflict.isParticipating(p)) return true;
109        }
110        return false;
111    }
112
113    /**
114     * Replies 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     * @param conflicts the collection of conflicts
118     * @return true if one of the primitives to be updated or to be deleted
119     * participates in at least one conflict in <code>conflicts</code>
120     */
121    public boolean participatesInConflict(ConflictCollection conflicts) {
122        if (conflicts == null || conflicts.isEmpty()) return false;
123        Set<PrimitiveId> idsParticipatingInConflicts = new HashSet<>();
124        for (OsmPrimitive p: conflicts.getMyConflictParties()) {
125            idsParticipatingInConflicts.add(p.getPrimitiveId());
126        }
127        for (OsmPrimitive p: conflicts.getTheirConflictParties()) {
128            idsParticipatingInConflicts.add(p.getPrimitiveId());
129        }
130        for (OsmPrimitive p: toUpdate) {
131            if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
132        }
133        for (OsmPrimitive p: toDelete) {
134            if (idsParticipatingInConflicts.contains(p.getPrimitiveId())) return true;
135        }
136        return false;
137    }
138
139    /**
140     * initializes the API data set with the primitives in <code>primitives</code>
141     *
142     * @param primitives the collection of primitives
143     */
144    public APIDataSet(Collection<OsmPrimitive> primitives) {
145        this();
146        init(primitives);
147    }
148
149    /**
150     * Replies true if there are no primitives to upload
151     *
152     * @return true if there are no primitives to upload
153     */
154    public boolean isEmpty() {
155        return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty();
156    }
157
158    /**
159     * Replies the primitives which should be added to the OSM database
160     *
161     * @return the primitives which should be added to the OSM database
162     */
163    public List<OsmPrimitive> getPrimitivesToAdd() {
164        return toAdd;
165    }
166
167    /**
168     * Replies the primitives which should be updated in the OSM database
169     *
170     * @return the primitives which should be updated in the OSM database
171     */
172    public List<OsmPrimitive> getPrimitivesToUpdate() {
173        return toUpdate;
174    }
175
176    /**
177     * Replies the primitives which should be deleted in the OSM database
178     *
179     * @return the primitives which should be deleted in the OSM database
180     */
181    public List<OsmPrimitive> getPrimitivesToDelete() {
182        return toDelete;
183    }
184
185    /**
186     * Replies all primitives
187     *
188     * @return all primitives
189     */
190    public List<OsmPrimitive> getPrimitives() {
191        LinkedList<OsmPrimitive> ret = new LinkedList<>();
192        ret.addAll(toAdd);
193        ret.addAll(toUpdate);
194        ret.addAll(toDelete);
195        return ret;
196    }
197
198    /**
199     * Replies the number of objects to upload
200     *
201     * @return the number of objects to upload
202     */
203    public int getSize() {
204        return toAdd.size() + toUpdate.size() + toDelete.size();
205    }
206
207    public void removeProcessed(Collection<IPrimitive> processed) {
208        if (processed == null) return;
209        toAdd.removeAll(processed);
210        toUpdate.removeAll(processed);
211        toDelete.removeAll(processed);
212    }
213
214    /**
215     * Adjusts the upload order for new relations. Child relations are uploaded first,
216     * parent relations second.
217     *
218     * This method detects cyclic dependencies in new relation. Relations with cyclic
219     * dependencies can't be uploaded.
220     *
221     * @throws CyclicUploadDependencyException thrown, if a cyclic dependency is detected
222     */
223    public void adjustRelationUploadOrder() throws CyclicUploadDependencyException{
224        LinkedList<OsmPrimitive> newToAdd = new LinkedList<>();
225        newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
226        newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
227
228        List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class));
229        List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
230        newToAdd.addAll(noProblemRelations);
231        relationsToAdd.removeAll(noProblemRelations);
232
233        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
234        newToAdd.addAll(graph.computeUploadOrder());
235        toAdd = newToAdd;
236
237        LinkedList<OsmPrimitive> newToDelete = new LinkedList<>();
238        graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
239        newToDelete.addAll(graph.computeUploadOrder());
240        newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
241        newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
242        toDelete = newToDelete;
243    }
244
245    /**
246     * Replies the subset of relations in <code>relations</code> which are not referring to any
247     * new relation
248     *
249     * @param relations a list of relations
250     * @return the subset of relations in <code>relations</code> which are not referring to any
251     * new relation
252     */
253    protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
254        List<Relation> ret = new LinkedList<>();
255        for (Relation relation: relations) {
256            boolean refersToNewRelation = false;
257            for (RelationMember m : relation.getMembers()) {
258                if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
259                    refersToNewRelation = true;
260                    break;
261                }
262            }
263            if (!refersToNewRelation) {
264                ret.add(relation);
265            }
266        }
267        return ret;
268    }
269
270    /**
271     * Utility class to sort a collection of new relations with their dependencies
272     * topologically.
273     *
274     */
275    private static class RelationUploadDependencyGraph {
276        private Map<Relation, Set<Relation>> children = new HashMap<>();
277        private Collection<Relation> relations;
278        private Set<Relation> visited = new HashSet<>();
279        private List<Relation> uploadOrder;
280        private final boolean newOrUndeleted;
281
282        public RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
283            this.newOrUndeleted = newOrUndeleted;
284            build(relations);
285        }
286
287        public final void build(Collection<Relation> relations) {
288            this.relations = new HashSet<>();
289            for(Relation relation: relations) {
290                if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
291                    continue;
292                }
293                this.relations.add(relation);
294                for (RelationMember m: relation.getMembers()) {
295                    if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
296                        addDependency(relation, (Relation)m.getMember());
297                    }
298                }
299            }
300        }
301
302        public Set<Relation> getChildren(Relation relation) {
303            Set<Relation> p = children.get(relation);
304            if (p == null) {
305                p = new HashSet<>();
306                children.put(relation, p);
307            }
308            return p;
309        }
310
311        public void addDependency(Relation relation, Relation child) {
312            getChildren(relation).add(child);
313        }
314
315        protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException{
316            if (path.contains(current)) {
317                path.push(current);
318                throw new CyclicUploadDependencyException(path);
319            }
320            if (!visited.contains(current)) {
321                path.push(current);
322                visited.add(current);
323                for (Relation dependent : getChildren(current)) {
324                    visit(path,dependent);
325                }
326                uploadOrder.add(current);
327                path.pop();
328            }
329        }
330
331        public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
332            visited = new HashSet<>();
333            uploadOrder = new LinkedList<>();
334            Stack<Relation> path = new Stack<>();
335            for (Relation relation: relations) {
336                visit(path, relation);
337            }
338            List<Relation> ret = new ArrayList<>(relations);
339            Collections.sort(
340                    ret,
341                    new Comparator<Relation>() {
342                        @Override
343                        public int compare(Relation o1, Relation o2) {
344                            return Integer.valueOf(uploadOrder.indexOf(o1)).compareTo(uploadOrder.indexOf(o2));
345                        }
346                    }
347                    );
348            return ret;
349        }
350    }
351}