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.Comparator; 007import java.util.HashMap; 008import java.util.HashSet; 009import java.util.LinkedList; 010import java.util.List; 011import java.util.Map; 012import java.util.Set; 013import java.util.Stack; 014import java.util.stream.Collectors; 015import java.util.stream.Stream; 016 017import org.openstreetmap.josm.data.conflict.ConflictCollection; 018import org.openstreetmap.josm.data.osm.CyclicUploadDependencyException; 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.Logging; 029import org.openstreetmap.josm.tools.Utils; 030 031/** 032 * Represents a collection of {@link OsmPrimitive}s which should be uploaded to the 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 * @since 2025 036 */ 037public class APIDataSet { 038 private List<OsmPrimitive> toAdd; 039 private List<OsmPrimitive> toUpdate; 040 private List<OsmPrimitive> toDelete; 041 042 /** 043 * The type of operation we can perform with OSM API on a primitive. 044 * @since 13161 045 */ 046 public enum APIOperation { 047 /** Add a new primitive */ 048 ADD, 049 /** Update an existing primitive */ 050 UPDATE, 051 /** Delete an existing primitive */ 052 DELETE; 053 054 /** 055 * Determines the API operation to perform on a primitive. 056 * @param osm OSM primitive 057 * @return the API operation to perform on {@code osm} 058 */ 059 public static APIOperation of(OsmPrimitive osm) { 060 if (osm.isNewOrUndeleted() && !osm.isDeleted()) { 061 return ADD; 062 } else if (osm.isModified() && !osm.isDeleted()) { 063 return UPDATE; 064 } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) { 065 return DELETE; 066 } 067 return null; 068 } 069 } 070 071 /** 072 * creates a new empty data set 073 */ 074 public APIDataSet() { 075 toAdd = new LinkedList<>(); 076 toUpdate = new LinkedList<>(); 077 toDelete = new LinkedList<>(); 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 void init(DataSet ds) { 086 if (ds == null) return; 087 init(ds.allPrimitives()); 088 } 089 090 /** 091 * Initializes the API data set with the modified primitives, ignores unmodified primitives. 092 * 093 * @param primitives the primitives 094 */ 095 public final void init(Collection<OsmPrimitive> primitives) { 096 toAdd.clear(); 097 toUpdate.clear(); 098 toDelete.clear(); 099 100 for (OsmPrimitive osm :primitives) { 101 APIOperation op = APIOperation.of(osm); 102 if (op != null) { 103 switch (op) { 104 case ADD: toAdd.add(osm); break; 105 case UPDATE: toUpdate.add(osm); break; 106 case DELETE: toDelete.add(osm); break; 107 default: Logging.trace("Ignored primitive {0} -> {1}", osm, op); 108 } 109 } 110 } 111 final Comparator<OsmPrimitive> orderingNodesWaysRelations = OsmPrimitiveComparator.orderingNodesWaysRelations(); 112 final Comparator<OsmPrimitive> byUniqueId = OsmPrimitiveComparator.comparingUniqueId(); 113 toAdd.sort(orderingNodesWaysRelations.thenComparing(byUniqueId)); 114 toUpdate.sort(orderingNodesWaysRelations.thenComparing(byUniqueId)); 115 toDelete.sort(orderingNodesWaysRelations.reversed().thenComparing(byUniqueId)); 116 } 117 118 /** 119 * initializes the API data set with the modified primitives in <code>ds</code> 120 * 121 * @param ds the data set. Ignored, if null. 122 */ 123 public APIDataSet(DataSet ds) { 124 this(); 125 init(ds); 126 } 127 128 /** 129 * Replies true if one of the primitives to be updated or to be deleted 130 * participates in at least one conflict in <code>conflicts</code> 131 * 132 * @param conflicts the collection of conflicts 133 * @return true if one of the primitives to be updated or to be deleted 134 * participates in at least one conflict in <code>conflicts</code> 135 */ 136 public boolean participatesInConflict(ConflictCollection conflicts) { 137 if (conflicts == null || conflicts.isEmpty()) return false; 138 Set<PrimitiveId> idsParticipatingInConflicts = conflicts.get().stream() 139 .flatMap(c -> Stream.of(c.getMy(), c.getTheir())) 140 .map(OsmPrimitive::getPrimitiveId) 141 .collect(Collectors.toSet()); 142 return Stream.of(toUpdate, toDelete) 143 .flatMap(Collection::stream) 144 .map(OsmPrimitive::getPrimitiveId) 145 .anyMatch(idsParticipatingInConflicts::contains); 146 } 147 148 /** 149 * initializes the API data set with the primitives in <code>primitives</code> 150 * 151 * @param primitives the collection of primitives 152 */ 153 public APIDataSet(Collection<OsmPrimitive> primitives) { 154 this(); 155 init(primitives); 156 } 157 158 /** 159 * Replies true if there are no primitives to upload 160 * 161 * @return true if there are no primitives to upload 162 */ 163 public boolean isEmpty() { 164 return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty(); 165 } 166 167 /** 168 * Replies the primitives which should be added to the OSM database 169 * 170 * @return the primitives which should be added to the OSM database 171 */ 172 public List<OsmPrimitive> getPrimitivesToAdd() { 173 return toAdd; 174 } 175 176 /** 177 * Replies the primitives which should be updated in the OSM database 178 * 179 * @return the primitives which should be updated in the OSM database 180 */ 181 public List<OsmPrimitive> getPrimitivesToUpdate() { 182 return toUpdate; 183 } 184 185 /** 186 * Replies the primitives which should be deleted in the OSM database 187 * 188 * @return the primitives which should be deleted in the OSM database 189 */ 190 public List<OsmPrimitive> getPrimitivesToDelete() { 191 return toDelete; 192 } 193 194 /** 195 * Replies all primitives 196 * 197 * @return all primitives 198 */ 199 public List<OsmPrimitive> getPrimitives() { 200 List<OsmPrimitive> ret = new LinkedList<>(); 201 ret.addAll(toAdd); 202 ret.addAll(toUpdate); 203 ret.addAll(toDelete); 204 return ret; 205 } 206 207 /** 208 * Replies the number of objects to upload 209 * 210 * @return the number of objects to upload 211 */ 212 public int getSize() { 213 return toAdd.size() + toUpdate.size() + toDelete.size(); 214 } 215 216 /** 217 * Removes the given primitives from this {@link APIDataSet} 218 * @param processed The primitives to remove 219 */ 220 public void removeProcessed(Collection<IPrimitive> processed) { 221 if (processed == null) return; 222 toAdd.removeAll(processed); 223 toUpdate.removeAll(processed); 224 toDelete.removeAll(processed); 225 } 226 227 /** 228 * Adjusts the upload order for new relations. Child relations are uploaded first, 229 * parent relations second. 230 * 231 * This method detects cyclic dependencies in new relation. Relations with cyclic 232 * dependencies can't be uploaded. 233 * 234 * @throws CyclicUploadDependencyException if a cyclic dependency is detected 235 */ 236 public void adjustRelationUploadOrder() throws CyclicUploadDependencyException { 237 List<OsmPrimitive> newToAdd = new LinkedList<>(); 238 newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class)); 239 newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class)); 240 241 List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class)); 242 List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd); 243 newToAdd.addAll(noProblemRelations); 244 relationsToAdd.removeAll(noProblemRelations); 245 246 RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true); 247 newToAdd.addAll(graph.computeUploadOrder(false)); 248 toAdd = newToAdd; 249 250 List<OsmPrimitive> newToDelete = new LinkedList<>(); 251 graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false); 252 newToDelete.addAll(graph.computeUploadOrder(true)); 253 newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class)); 254 newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class)); 255 toDelete = newToDelete; 256 } 257 258 /** 259 * Replies the subset of relations in <code>relations</code> which are not referring to any 260 * new relation 261 * 262 * @param relations a list of relations 263 * @return the subset of relations in <code>relations</code> which are not referring to any 264 * new relation 265 */ 266 protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) { 267 List<Relation> ret = new LinkedList<>(); 268 for (Relation relation: relations) { 269 boolean refersToNewRelation = false; 270 for (RelationMember m : relation.getMembers()) { 271 if (m.isRelation() && m.getMember().isNewOrUndeleted()) { 272 refersToNewRelation = true; 273 break; 274 } 275 } 276 if (!refersToNewRelation) { 277 ret.add(relation); 278 } 279 } 280 return ret; 281 } 282 283 /** 284 * Utility class to sort a collection of new relations with their dependencies 285 * topologically. 286 * 287 */ 288 private static class RelationUploadDependencyGraph { 289 private final Map<Relation, Set<Relation>> children = new HashMap<>(); 290 private Collection<Relation> relations; 291 private Set<Relation> visited = new HashSet<>(); 292 private List<Relation> uploadOrder; 293 private final boolean newOrUndeleted; 294 295 RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) { 296 this.newOrUndeleted = newOrUndeleted; 297 build(relations); 298 } 299 300 public final void build(Collection<Relation> relations) { 301 this.relations = new HashSet<>(); 302 for (Relation relation: relations) { 303 if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) { 304 continue; 305 } 306 this.relations.add(relation); 307 for (RelationMember m: relation.getMembers()) { 308 if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) { 309 addDependency(relation, (Relation) m.getMember()); 310 } 311 } 312 } 313 } 314 315 public Set<Relation> getChildren(Relation relation) { 316 return children.computeIfAbsent(relation, k -> new HashSet<>()); 317 } 318 319 public void addDependency(Relation relation, Relation child) { 320 getChildren(relation).add(child); 321 } 322 323 protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException { 324 if (path.contains(current)) { 325 path.push(current); 326 throw new CyclicUploadDependencyException(path); 327 } 328 if (!visited.contains(current)) { 329 path.push(current); 330 visited.add(current); 331 for (Relation dependent : getChildren(current)) { 332 visit(path, dependent); 333 } 334 uploadOrder.add(current); 335 path.pop(); 336 } 337 } 338 339 public List<Relation> computeUploadOrder(boolean reverse) throws CyclicUploadDependencyException { 340 visited = new HashSet<>(); 341 uploadOrder = new LinkedList<>(); 342 Stack<Relation> path = new Stack<>(); 343 for (Relation relation: relations) { 344 visit(path, relation); 345 } 346 List<Relation> ret = new ArrayList<>(relations); 347 Comparator<? super Relation> cmpr = Comparator.comparingInt(uploadOrder::indexOf); 348 if (reverse) { 349 cmpr = cmpr.reversed(); 350 } 351 ret.sort(cmpr); 352 return ret; 353 } 354 } 355}