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.actions.upload.CyclicUploadDependencyException; 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 /** 061 * Initializes the API data set with the modified primitives, ignores unmodified primitives. 062 * 063 * @param primitives the primitives 064 */ 065 public final void init(Collection<OsmPrimitive> primitives) { 066 toAdd.clear(); 067 toUpdate.clear(); 068 toDelete.clear(); 069 070 for (OsmPrimitive osm :primitives) { 071 if (osm.isNewOrUndeleted() && !osm.isDeleted()) { 072 toAdd.add(osm); 073 } else if (osm.isModified() && !osm.isDeleted()) { 074 toUpdate.add(osm); 075 } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) { 076 toDelete.add(osm); 077 } 078 } 079 final Comparator<OsmPrimitive> orderingNodesWaysRelations = OsmPrimitiveComparator.orderingNodesWaysRelations(); 080 final Comparator<OsmPrimitive> byUniqueId = OsmPrimitiveComparator.comparingUniqueId(); 081 toAdd.sort(orderingNodesWaysRelations.thenComparing(byUniqueId)); 082 toUpdate.sort(orderingNodesWaysRelations.thenComparing(byUniqueId)); 083 toDelete.sort(orderingNodesWaysRelations.reversed().thenComparing(byUniqueId)); 084 } 085 086 /** 087 * initializes the API data set with the modified primitives in <code>ds</code> 088 * 089 * @param ds the data set. Ignored, if null. 090 */ 091 public APIDataSet(DataSet ds) { 092 this(); 093 init(ds); 094 } 095 096 /** 097 * Replies true if one of the primitives to be updated or to be deleted 098 * participates in at least one conflict in <code>conflicts</code> 099 * 100 * @param conflicts the collection of conflicts 101 * @return true if one of the primitives to be updated or to be deleted 102 * participates in at least one conflict in <code>conflicts</code> 103 */ 104 public boolean participatesInConflict(ConflictCollection conflicts) { 105 if (conflicts == null || conflicts.isEmpty()) return false; 106 Set<PrimitiveId> idsParticipatingInConflicts = conflicts.get().stream() 107 .flatMap(c -> Stream.of(c.getMy(), c.getTheir())) 108 .map(OsmPrimitive::getPrimitiveId) 109 .collect(Collectors.toSet()); 110 return Stream.of(toUpdate, toDelete) 111 .flatMap(Collection::stream) 112 .map(OsmPrimitive::getPrimitiveId) 113 .anyMatch(idsParticipatingInConflicts::contains); 114 } 115 116 /** 117 * initializes the API data set with the primitives in <code>primitives</code> 118 * 119 * @param primitives the collection of primitives 120 */ 121 public APIDataSet(Collection<OsmPrimitive> primitives) { 122 this(); 123 init(primitives); 124 } 125 126 /** 127 * Replies true if there are no primitives to upload 128 * 129 * @return true if there are no primitives to upload 130 */ 131 public boolean isEmpty() { 132 return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty(); 133 } 134 135 /** 136 * Replies the primitives which should be added to the OSM database 137 * 138 * @return the primitives which should be added to the OSM database 139 */ 140 public List<OsmPrimitive> getPrimitivesToAdd() { 141 return toAdd; 142 } 143 144 /** 145 * Replies the primitives which should be updated in the OSM database 146 * 147 * @return the primitives which should be updated in the OSM database 148 */ 149 public List<OsmPrimitive> getPrimitivesToUpdate() { 150 return toUpdate; 151 } 152 153 /** 154 * Replies the primitives which should be deleted in the OSM database 155 * 156 * @return the primitives which should be deleted in the OSM database 157 */ 158 public List<OsmPrimitive> getPrimitivesToDelete() { 159 return toDelete; 160 } 161 162 /** 163 * Replies all primitives 164 * 165 * @return all primitives 166 */ 167 public List<OsmPrimitive> getPrimitives() { 168 List<OsmPrimitive> ret = new LinkedList<>(); 169 ret.addAll(toAdd); 170 ret.addAll(toUpdate); 171 ret.addAll(toDelete); 172 return ret; 173 } 174 175 /** 176 * Replies the number of objects to upload 177 * 178 * @return the number of objects to upload 179 */ 180 public int getSize() { 181 return toAdd.size() + toUpdate.size() + toDelete.size(); 182 } 183 184 public void removeProcessed(Collection<IPrimitive> processed) { 185 if (processed == null) return; 186 toAdd.removeAll(processed); 187 toUpdate.removeAll(processed); 188 toDelete.removeAll(processed); 189 } 190 191 /** 192 * Adjusts the upload order for new relations. Child relations are uploaded first, 193 * parent relations second. 194 * 195 * This method detects cyclic dependencies in new relation. Relations with cyclic 196 * dependencies can't be uploaded. 197 * 198 * @throws CyclicUploadDependencyException if a cyclic dependency is detected 199 */ 200 public void adjustRelationUploadOrder() throws CyclicUploadDependencyException { 201 List<OsmPrimitive> newToAdd = new LinkedList<>(); 202 newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class)); 203 newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class)); 204 205 List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class)); 206 List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd); 207 newToAdd.addAll(noProblemRelations); 208 relationsToAdd.removeAll(noProblemRelations); 209 210 RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true); 211 newToAdd.addAll(graph.computeUploadOrder()); 212 toAdd = newToAdd; 213 214 List<OsmPrimitive> newToDelete = new LinkedList<>(); 215 graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false); 216 newToDelete.addAll(graph.computeUploadOrder()); 217 newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class)); 218 newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class)); 219 toDelete = newToDelete; 220 } 221 222 /** 223 * Replies the subset of relations in <code>relations</code> which are not referring to any 224 * new relation 225 * 226 * @param relations a list of relations 227 * @return the subset of relations in <code>relations</code> which are not referring to any 228 * new relation 229 */ 230 protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) { 231 List<Relation> ret = new LinkedList<>(); 232 for (Relation relation: relations) { 233 boolean refersToNewRelation = false; 234 for (RelationMember m : relation.getMembers()) { 235 if (m.isRelation() && m.getMember().isNewOrUndeleted()) { 236 refersToNewRelation = true; 237 break; 238 } 239 } 240 if (!refersToNewRelation) { 241 ret.add(relation); 242 } 243 } 244 return ret; 245 } 246 247 /** 248 * Utility class to sort a collection of new relations with their dependencies 249 * topologically. 250 * 251 */ 252 private static class RelationUploadDependencyGraph { 253 private final Map<Relation, Set<Relation>> children = new HashMap<>(); 254 private Collection<Relation> relations; 255 private Set<Relation> visited = new HashSet<>(); 256 private List<Relation> uploadOrder; 257 private final boolean newOrUndeleted; 258 259 RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) { 260 this.newOrUndeleted = newOrUndeleted; 261 build(relations); 262 } 263 264 public final void build(Collection<Relation> relations) { 265 this.relations = new HashSet<>(); 266 for (Relation relation: relations) { 267 if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) { 268 continue; 269 } 270 this.relations.add(relation); 271 for (RelationMember m: relation.getMembers()) { 272 if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) { 273 addDependency(relation, (Relation) m.getMember()); 274 } 275 } 276 } 277 } 278 279 public Set<Relation> getChildren(Relation relation) { 280 Set<Relation> p = children.get(relation); 281 if (p == null) { 282 p = new HashSet<>(); 283 children.put(relation, p); 284 } 285 return p; 286 } 287 288 public void addDependency(Relation relation, Relation child) { 289 getChildren(relation).add(child); 290 } 291 292 protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException { 293 if (path.contains(current)) { 294 path.push(current); 295 throw new CyclicUploadDependencyException(path); 296 } 297 if (!visited.contains(current)) { 298 path.push(current); 299 visited.add(current); 300 for (Relation dependent : getChildren(current)) { 301 visit(path, dependent); 302 } 303 uploadOrder.add(current); 304 path.pop(); 305 } 306 } 307 308 public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException { 309 visited = new HashSet<>(); 310 uploadOrder = new LinkedList<>(); 311 Stack<Relation> path = new Stack<>(); 312 for (Relation relation: relations) { 313 visit(path, relation); 314 } 315 List<Relation> ret = new ArrayList<>(relations); 316 ret.sort(Comparator.comparingInt(uploadOrder::indexOf)); 317 return ret; 318 } 319 } 320}