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}