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 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 * @since 2025 035 */ 036public class APIDataSet { 037 private List<OsmPrimitive> toAdd; 038 private List<OsmPrimitive> toUpdate; 039 private List<OsmPrimitive> toDelete; 040 041 /** 042 * creates a new empty data set 043 */ 044 public APIDataSet() { 045 toAdd = new LinkedList<>(); 046 toUpdate = new LinkedList<>(); 047 toDelete = new LinkedList<>(); 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 init(ds.allPrimitives()); 058 } 059 060 public final void init(Collection<OsmPrimitive> primitives) { 061 toAdd.clear(); 062 toUpdate.clear(); 063 toDelete.clear(); 064 065 for (OsmPrimitive osm :primitives) { 066 if (osm.isNewOrUndeleted() && !osm.isDeleted()) { 067 toAdd.add(osm); 068 } else if (osm.isModified() && !osm.isDeleted()) { 069 toUpdate.add(osm); 070 } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) { 071 toDelete.add(osm); 072 } 073 } 074 OsmPrimitiveComparator c = new OsmPrimitiveComparator(false, 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<>(); 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 init(primitives); 143 } 144 145 /** 146 * Replies true if there are no primitives to upload 147 * 148 * @return true if there are no primitives to upload 149 */ 150 public boolean isEmpty() { 151 return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty(); 152 } 153 154 /** 155 * Replies the primitives which should be added to the OSM database 156 * 157 * @return the primitives which should be added to the OSM database 158 */ 159 public List<OsmPrimitive> getPrimitivesToAdd() { 160 return toAdd; 161 } 162 163 /** 164 * Replies the primitives which should be updated in the OSM database 165 * 166 * @return the primitives which should be updated in the OSM database 167 */ 168 public List<OsmPrimitive> getPrimitivesToUpdate() { 169 return toUpdate; 170 } 171 172 /** 173 * Replies the primitives which should be deleted in the OSM database 174 * 175 * @return the primitives which should be deleted in the OSM database 176 */ 177 public List<OsmPrimitive> getPrimitivesToDelete() { 178 return toDelete; 179 } 180 181 /** 182 * Replies all primitives 183 * 184 * @return all primitives 185 */ 186 public List<OsmPrimitive> getPrimitives() { 187 LinkedList<OsmPrimitive> ret = new LinkedList<>(); 188 ret.addAll(toAdd); 189 ret.addAll(toUpdate); 190 ret.addAll(toDelete); 191 return ret; 192 } 193 194 /** 195 * Replies the number of objects to upload 196 * 197 * @return the number of objects to upload 198 */ 199 public int getSize() { 200 return toAdd.size() + toUpdate.size() + toDelete.size(); 201 } 202 203 public void removeProcessed(Collection<IPrimitive> processed) { 204 if (processed == null) return; 205 toAdd.removeAll(processed); 206 toUpdate.removeAll(processed); 207 toDelete.removeAll(processed); 208 } 209 210 /** 211 * Adjusts the upload order for new relations. Child relations are uploaded first, 212 * parent relations second. 213 * 214 * This method detects cyclic dependencies in new relation. Relations with cyclic 215 * dependencies can't be uploaded. 216 * 217 * @throws CyclicUploadDependencyException thrown, if a cyclic dependency is detected 218 */ 219 public void adjustRelationUploadOrder() throws CyclicUploadDependencyException{ 220 LinkedList<OsmPrimitive> newToAdd = new LinkedList<>(); 221 newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class)); 222 newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class)); 223 224 List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class)); 225 List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd); 226 newToAdd.addAll(noProblemRelations); 227 relationsToAdd.removeAll(noProblemRelations); 228 229 RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true); 230 newToAdd.addAll(graph.computeUploadOrder()); 231 toAdd = newToAdd; 232 233 LinkedList<OsmPrimitive> newToDelete = new LinkedList<>(); 234 graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false); 235 newToDelete.addAll(graph.computeUploadOrder()); 236 newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class)); 237 newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class)); 238 toDelete = newToDelete; 239 } 240 241 /** 242 * Replies the subset of relations in <code>relations</code> which are not referring to any 243 * new relation 244 * 245 * @param relations a list of relations 246 * @return the subset of relations in <code>relations</code> which are not referring to any 247 * new relation 248 */ 249 protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) { 250 List<Relation> ret = new LinkedList<>(); 251 for (Relation relation: relations) { 252 boolean refersToNewRelation = false; 253 for (RelationMember m : relation.getMembers()) { 254 if (m.isRelation() && m.getMember().isNewOrUndeleted()) { 255 refersToNewRelation = true; 256 break; 257 } 258 } 259 if (!refersToNewRelation) { 260 ret.add(relation); 261 } 262 } 263 return ret; 264 } 265 266 /** 267 * Utility class to sort a collection of new relations with their dependencies 268 * topologically. 269 * 270 */ 271 private static class RelationUploadDependencyGraph { 272 private Map<Relation, Set<Relation>> children = new HashMap<>(); 273 private Collection<Relation> relations; 274 private Set<Relation> visited = new HashSet<>(); 275 private List<Relation> uploadOrder; 276 private final boolean newOrUndeleted; 277 278 public RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) { 279 this.newOrUndeleted = newOrUndeleted; 280 build(relations); 281 } 282 283 public final void build(Collection<Relation> relations) { 284 this.relations = new HashSet<>(); 285 for(Relation relation: relations) { 286 if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) { 287 continue; 288 } 289 this.relations.add(relation); 290 for (RelationMember m: relation.getMembers()) { 291 if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) { 292 addDependency(relation, (Relation)m.getMember()); 293 } 294 } 295 } 296 } 297 298 public Set<Relation> getChildren(Relation relation) { 299 Set<Relation> p = children.get(relation); 300 if (p == null) { 301 p = new HashSet<>(); 302 children.put(relation, p); 303 } 304 return p; 305 } 306 307 public void addDependency(Relation relation, Relation child) { 308 getChildren(relation).add(child); 309 } 310 311 protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException{ 312 if (path.contains(current)) { 313 path.push(current); 314 throw new CyclicUploadDependencyException(path); 315 } 316 if (!visited.contains(current)) { 317 path.push(current); 318 visited.add(current); 319 for (Relation dependent : getChildren(current)) { 320 visit(path,dependent); 321 } 322 uploadOrder.add(current); 323 path.pop(); 324 } 325 } 326 327 public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException { 328 visited = new HashSet<>(); 329 uploadOrder = new LinkedList<>(); 330 Stack<Relation> path = new Stack<>(); 331 for (Relation relation: relations) { 332 visit(path, relation); 333 } 334 List<Relation> ret = new ArrayList<>(relations); 335 Collections.sort( 336 ret, 337 new Comparator<Relation>() { 338 @Override 339 public int compare(Relation o1, Relation o2) { 340 return Integer.valueOf(uploadOrder.indexOf(o1)).compareTo(uploadOrder.indexOf(o2)); 341 } 342 } 343 ); 344 return ret; 345 } 346 } 347}