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}