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 }