[2512] | 1 | // License: GPL. For details, see LICENSE file.
|
---|
| 2 | package org.openstreetmap.josm.data;
|
---|
| 3 |
|
---|
| 4 | import java.util.ArrayList;
|
---|
| 5 | import java.util.Collection;
|
---|
[10647] | 6 | import java.util.Comparator;
|
---|
[2512] | 7 | import java.util.HashMap;
|
---|
| 8 | import java.util.HashSet;
|
---|
| 9 | import java.util.LinkedList;
|
---|
| 10 | import java.util.List;
|
---|
[6317] | 11 | import java.util.Map;
|
---|
[2512] | 12 | import java.util.Set;
|
---|
[8856] | 13 | import java.util.Stack;
|
---|
[11175] | 14 | import java.util.stream.Collectors;
|
---|
| 15 | import java.util.stream.Stream;
|
---|
[2512] | 16 |
|
---|
[2979] | 17 | import org.openstreetmap.josm.data.conflict.ConflictCollection;
|
---|
[12673] | 18 | import org.openstreetmap.josm.data.osm.CyclicUploadDependencyException;
|
---|
[2512] | 19 | import org.openstreetmap.josm.data.osm.DataSet;
|
---|
[4534] | 20 | import org.openstreetmap.josm.data.osm.IPrimitive;
|
---|
[2512] | 21 | import org.openstreetmap.josm.data.osm.Node;
|
---|
| 22 | import org.openstreetmap.josm.data.osm.OsmPrimitive;
|
---|
[11177] | 23 | import org.openstreetmap.josm.data.osm.OsmPrimitiveComparator;
|
---|
[2979] | 24 | import org.openstreetmap.josm.data.osm.PrimitiveId;
|
---|
[2512] | 25 | import org.openstreetmap.josm.data.osm.Relation;
|
---|
| 26 | import org.openstreetmap.josm.data.osm.RelationMember;
|
---|
| 27 | import org.openstreetmap.josm.data.osm.Way;
|
---|
[13161] | 28 | import org.openstreetmap.josm.tools.Logging;
|
---|
[4100] | 29 | import org.openstreetmap.josm.tools.Utils;
|
---|
[2512] | 30 |
|
---|
| 31 | /**
|
---|
[7599] | 32 | * Represents a collection of {@link OsmPrimitive}s which should be uploaded to the API.
|
---|
[5266] | 33 | * The collection is derived from the modified primitives of an {@link DataSet} and it provides methods
|
---|
[2598] | 34 | * for sorting the objects in upload order.
|
---|
[7599] | 35 | * @since 2025
|
---|
[2512] | 36 | */
|
---|
| 37 | public class APIDataSet {
|
---|
[6317] | 38 | private List<OsmPrimitive> toAdd;
|
---|
| 39 | private List<OsmPrimitive> toUpdate;
|
---|
| 40 | private List<OsmPrimitive> toDelete;
|
---|
[2512] | 41 |
|
---|
| 42 | /**
|
---|
[13161] | 43 | * The type of operation we can perform with OSM API on a primitive.
|
---|
| 44 | * @since 13161
|
---|
| 45 | */
|
---|
| 46 | public enum APIOperation {
|
---|
| 47 | /** Add a new primitive */
|
---|
| 48 | ADD,
|
---|
| 49 | /** Update an existing primitive */
|
---|
| 50 | UPDATE,
|
---|
| 51 | /** Delete an existing primitive */
|
---|
| 52 | DELETE;
|
---|
| 53 |
|
---|
| 54 | /**
|
---|
| 55 | * Determines the API operation to perform on a primitive.
|
---|
| 56 | * @param osm OSM primitive
|
---|
| 57 | * @return the API operation to perform on {@code osm}
|
---|
| 58 | */
|
---|
| 59 | public static APIOperation of(OsmPrimitive osm) {
|
---|
| 60 | if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
|
---|
| 61 | return ADD;
|
---|
| 62 | } else if (osm.isModified() && !osm.isDeleted()) {
|
---|
| 63 | return UPDATE;
|
---|
| 64 | } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
|
---|
| 65 | return DELETE;
|
---|
| 66 | }
|
---|
| 67 | return null;
|
---|
| 68 | }
|
---|
| 69 | }
|
---|
| 70 |
|
---|
| 71 | /**
|
---|
[2512] | 72 | * creates a new empty data set
|
---|
| 73 | */
|
---|
| 74 | public APIDataSet() {
|
---|
[7005] | 75 | toAdd = new LinkedList<>();
|
---|
| 76 | toUpdate = new LinkedList<>();
|
---|
| 77 | toDelete = new LinkedList<>();
|
---|
[2512] | 78 | }
|
---|
| 79 |
|
---|
| 80 | /**
|
---|
| 81 | * initializes the API data set with the modified primitives in <code>ds</code>
|
---|
| 82 | *
|
---|
| 83 | * @param ds the data set. Ignored, if null.
|
---|
| 84 | */
|
---|
| 85 | public void init(DataSet ds) {
|
---|
| 86 | if (ds == null) return;
|
---|
[5589] | 87 | init(ds.allPrimitives());
|
---|
| 88 | }
|
---|
| 89 |
|
---|
[11175] | 90 | /**
|
---|
| 91 | * Initializes the API data set with the modified primitives, ignores unmodified primitives.
|
---|
| 92 | *
|
---|
| 93 | * @param primitives the primitives
|
---|
| 94 | */
|
---|
[6890] | 95 | public final void init(Collection<OsmPrimitive> primitives) {
|
---|
[2512] | 96 | toAdd.clear();
|
---|
| 97 | toUpdate.clear();
|
---|
| 98 | toDelete.clear();
|
---|
| 99 |
|
---|
[5589] | 100 | for (OsmPrimitive osm :primitives) {
|
---|
[13161] | 101 | switch (APIOperation.of(osm)) {
|
---|
| 102 | case ADD: toAdd.add(osm); break;
|
---|
| 103 | case UPDATE: toUpdate.add(osm); break;
|
---|
| 104 | case DELETE: toDelete.add(osm); break;
|
---|
| 105 | default: Logging.trace("Ignored primitive {0}", osm);
|
---|
[2512] | 106 | }
|
---|
| 107 | }
|
---|
[11177] | 108 | final Comparator<OsmPrimitive> orderingNodesWaysRelations = OsmPrimitiveComparator.orderingNodesWaysRelations();
|
---|
| 109 | final Comparator<OsmPrimitive> byUniqueId = OsmPrimitiveComparator.comparingUniqueId();
|
---|
[11176] | 110 | toAdd.sort(orderingNodesWaysRelations.thenComparing(byUniqueId));
|
---|
| 111 | toUpdate.sort(orderingNodesWaysRelations.thenComparing(byUniqueId));
|
---|
| 112 | toDelete.sort(orderingNodesWaysRelations.reversed().thenComparing(byUniqueId));
|
---|
[2512] | 113 | }
|
---|
| 114 |
|
---|
| 115 | /**
|
---|
| 116 | * initializes the API data set with the modified primitives in <code>ds</code>
|
---|
| 117 | *
|
---|
| 118 | * @param ds the data set. Ignored, if null.
|
---|
| 119 | */
|
---|
| 120 | public APIDataSet(DataSet ds) {
|
---|
| 121 | this();
|
---|
| 122 | init(ds);
|
---|
| 123 | }
|
---|
| 124 |
|
---|
| 125 | /**
|
---|
[2979] | 126 | * Replies true if one of the primitives to be updated or to be deleted
|
---|
| 127 | * participates in at least one conflict in <code>conflicts</code>
|
---|
[3530] | 128 | *
|
---|
[2979] | 129 | * @param conflicts the collection of conflicts
|
---|
| 130 | * @return true if one of the primitives to be updated or to be deleted
|
---|
| 131 | * participates in at least one conflict in <code>conflicts</code>
|
---|
| 132 | */
|
---|
| 133 | public boolean participatesInConflict(ConflictCollection conflicts) {
|
---|
| 134 | if (conflicts == null || conflicts.isEmpty()) return false;
|
---|
[11175] | 135 | Set<PrimitiveId> idsParticipatingInConflicts = conflicts.get().stream()
|
---|
| 136 | .flatMap(c -> Stream.of(c.getMy(), c.getTheir()))
|
---|
| 137 | .map(OsmPrimitive::getPrimitiveId)
|
---|
| 138 | .collect(Collectors.toSet());
|
---|
| 139 | return Stream.of(toUpdate, toDelete)
|
---|
| 140 | .flatMap(Collection::stream)
|
---|
| 141 | .map(OsmPrimitive::getPrimitiveId)
|
---|
| 142 | .anyMatch(idsParticipatingInConflicts::contains);
|
---|
[2979] | 143 | }
|
---|
| 144 |
|
---|
| 145 | /**
|
---|
[2512] | 146 | * initializes the API data set with the primitives in <code>primitives</code>
|
---|
| 147 | *
|
---|
| 148 | * @param primitives the collection of primitives
|
---|
| 149 | */
|
---|
| 150 | public APIDataSet(Collection<OsmPrimitive> primitives) {
|
---|
| 151 | this();
|
---|
[5589] | 152 | init(primitives);
|
---|
[2512] | 153 | }
|
---|
| 154 |
|
---|
| 155 | /**
|
---|
| 156 | * Replies true if there are no primitives to upload
|
---|
| 157 | *
|
---|
| 158 | * @return true if there are no primitives to upload
|
---|
| 159 | */
|
---|
| 160 | public boolean isEmpty() {
|
---|
| 161 | return toAdd.isEmpty() && toUpdate.isEmpty() && toDelete.isEmpty();
|
---|
| 162 | }
|
---|
| 163 |
|
---|
| 164 | /**
|
---|
| 165 | * Replies the primitives which should be added to the OSM database
|
---|
| 166 | *
|
---|
| 167 | * @return the primitives which should be added to the OSM database
|
---|
| 168 | */
|
---|
| 169 | public List<OsmPrimitive> getPrimitivesToAdd() {
|
---|
| 170 | return toAdd;
|
---|
| 171 | }
|
---|
| 172 |
|
---|
| 173 | /**
|
---|
| 174 | * Replies the primitives which should be updated in the OSM database
|
---|
| 175 | *
|
---|
| 176 | * @return the primitives which should be updated in the OSM database
|
---|
| 177 | */
|
---|
| 178 | public List<OsmPrimitive> getPrimitivesToUpdate() {
|
---|
| 179 | return toUpdate;
|
---|
| 180 | }
|
---|
| 181 |
|
---|
| 182 | /**
|
---|
| 183 | * Replies the primitives which should be deleted in the OSM database
|
---|
| 184 | *
|
---|
| 185 | * @return the primitives which should be deleted in the OSM database
|
---|
| 186 | */
|
---|
| 187 | public List<OsmPrimitive> getPrimitivesToDelete() {
|
---|
| 188 | return toDelete;
|
---|
| 189 | }
|
---|
| 190 |
|
---|
| 191 | /**
|
---|
| 192 | * Replies all primitives
|
---|
| 193 | *
|
---|
| 194 | * @return all primitives
|
---|
| 195 | */
|
---|
| 196 | public List<OsmPrimitive> getPrimitives() {
|
---|
[8338] | 197 | List<OsmPrimitive> ret = new LinkedList<>();
|
---|
[2512] | 198 | ret.addAll(toAdd);
|
---|
| 199 | ret.addAll(toUpdate);
|
---|
| 200 | ret.addAll(toDelete);
|
---|
| 201 | return ret;
|
---|
| 202 | }
|
---|
| 203 |
|
---|
| 204 | /**
|
---|
[2598] | 205 | * Replies the number of objects to upload
|
---|
[2711] | 206 | *
|
---|
[2598] | 207 | * @return the number of objects to upload
|
---|
| 208 | */
|
---|
| 209 | public int getSize() {
|
---|
| 210 | return toAdd.size() + toUpdate.size() + toDelete.size();
|
---|
| 211 | }
|
---|
| 212 |
|
---|
[12374] | 213 | /**
|
---|
| 214 | * Removes the given primitives from this {@link APIDataSet}
|
---|
| 215 | * @param processed The primitives to remove
|
---|
| 216 | */
|
---|
[4534] | 217 | public void removeProcessed(Collection<IPrimitive> processed) {
|
---|
[2598] | 218 | if (processed == null) return;
|
---|
| 219 | toAdd.removeAll(processed);
|
---|
| 220 | toUpdate.removeAll(processed);
|
---|
| 221 | toDelete.removeAll(processed);
|
---|
| 222 | }
|
---|
| 223 |
|
---|
| 224 | /**
|
---|
[2512] | 225 | * Adjusts the upload order for new relations. Child relations are uploaded first,
|
---|
| 226 | * parent relations second.
|
---|
| 227 | *
|
---|
| 228 | * This method detects cyclic dependencies in new relation. Relations with cyclic
|
---|
| 229 | * dependencies can't be uploaded.
|
---|
| 230 | *
|
---|
[8291] | 231 | * @throws CyclicUploadDependencyException if a cyclic dependency is detected
|
---|
[2512] | 232 | */
|
---|
[8510] | 233 | public void adjustRelationUploadOrder() throws CyclicUploadDependencyException {
|
---|
[8338] | 234 | List<OsmPrimitive> newToAdd = new LinkedList<>();
|
---|
[4100] | 235 | newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
|
---|
| 236 | newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
|
---|
[2512] | 237 |
|
---|
[7005] | 238 | List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class));
|
---|
[2512] | 239 | List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
|
---|
| 240 | newToAdd.addAll(noProblemRelations);
|
---|
| 241 | relationsToAdd.removeAll(noProblemRelations);
|
---|
| 242 |
|
---|
[6776] | 243 | RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
|
---|
[13018] | 244 | newToAdd.addAll(graph.computeUploadOrder(false));
|
---|
[2512] | 245 | toAdd = newToAdd;
|
---|
[6776] | 246 |
|
---|
[8338] | 247 | List<OsmPrimitive> newToDelete = new LinkedList<>();
|
---|
[6776] | 248 | graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
|
---|
[13018] | 249 | newToDelete.addAll(graph.computeUploadOrder(true));
|
---|
[6801] | 250 | newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
|
---|
| 251 | newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
|
---|
[6776] | 252 | toDelete = newToDelete;
|
---|
[2512] | 253 | }
|
---|
| 254 |
|
---|
| 255 | /**
|
---|
| 256 | * Replies the subset of relations in <code>relations</code> which are not referring to any
|
---|
| 257 | * new relation
|
---|
| 258 | *
|
---|
| 259 | * @param relations a list of relations
|
---|
| 260 | * @return the subset of relations in <code>relations</code> which are not referring to any
|
---|
| 261 | * new relation
|
---|
| 262 | */
|
---|
| 263 | protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
|
---|
[7005] | 264 | List<Relation> ret = new LinkedList<>();
|
---|
[2512] | 265 | for (Relation relation: relations) {
|
---|
| 266 | boolean refersToNewRelation = false;
|
---|
| 267 | for (RelationMember m : relation.getMembers()) {
|
---|
[3336] | 268 | if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
|
---|
[2512] | 269 | refersToNewRelation = true;
|
---|
| 270 | break;
|
---|
| 271 | }
|
---|
| 272 | }
|
---|
| 273 | if (!refersToNewRelation) {
|
---|
| 274 | ret.add(relation);
|
---|
| 275 | }
|
---|
| 276 | }
|
---|
| 277 | return ret;
|
---|
| 278 | }
|
---|
| 279 |
|
---|
| 280 | /**
|
---|
[2915] | 281 | * Utility class to sort a collection of new relations with their dependencies
|
---|
[2512] | 282 | * topologically.
|
---|
| 283 | *
|
---|
| 284 | */
|
---|
[4874] | 285 | private static class RelationUploadDependencyGraph {
|
---|
[9067] | 286 | private final Map<Relation, Set<Relation>> children = new HashMap<>();
|
---|
[2512] | 287 | private Collection<Relation> relations;
|
---|
[7005] | 288 | private Set<Relation> visited = new HashSet<>();
|
---|
[2512] | 289 | private List<Relation> uploadOrder;
|
---|
[6776] | 290 | private final boolean newOrUndeleted;
|
---|
[2512] | 291 |
|
---|
[8836] | 292 | RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
|
---|
[6776] | 293 | this.newOrUndeleted = newOrUndeleted;
|
---|
[2512] | 294 | build(relations);
|
---|
| 295 | }
|
---|
| 296 |
|
---|
[6890] | 297 | public final void build(Collection<Relation> relations) {
|
---|
[7005] | 298 | this.relations = new HashSet<>();
|
---|
[8510] | 299 | for (Relation relation: relations) {
|
---|
[6776] | 300 | if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
|
---|
[2512] | 301 | continue;
|
---|
| 302 | }
|
---|
| 303 | this.relations.add(relation);
|
---|
| 304 | for (RelationMember m: relation.getMembers()) {
|
---|
[6776] | 305 | if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
|
---|
[8510] | 306 | addDependency(relation, (Relation) m.getMember());
|
---|
[2512] | 307 | }
|
---|
| 308 | }
|
---|
| 309 | }
|
---|
| 310 | }
|
---|
| 311 |
|
---|
| 312 | public Set<Relation> getChildren(Relation relation) {
|
---|
[12865] | 313 | return children.computeIfAbsent(relation, k -> new HashSet<>());
|
---|
[2512] | 314 | }
|
---|
| 315 |
|
---|
| 316 | public void addDependency(Relation relation, Relation child) {
|
---|
| 317 | getChildren(relation).add(child);
|
---|
| 318 | }
|
---|
| 319 |
|
---|
[8856] | 320 | protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException {
|
---|
[2512] | 321 | if (path.contains(current)) {
|
---|
| 322 | path.push(current);
|
---|
| 323 | throw new CyclicUploadDependencyException(path);
|
---|
| 324 | }
|
---|
| 325 | if (!visited.contains(current)) {
|
---|
| 326 | path.push(current);
|
---|
| 327 | visited.add(current);
|
---|
| 328 | for (Relation dependent : getChildren(current)) {
|
---|
[8510] | 329 | visit(path, dependent);
|
---|
[2512] | 330 | }
|
---|
| 331 | uploadOrder.add(current);
|
---|
| 332 | path.pop();
|
---|
| 333 | }
|
---|
| 334 | }
|
---|
| 335 |
|
---|
[13018] | 336 | public List<Relation> computeUploadOrder(boolean reverse) throws CyclicUploadDependencyException {
|
---|
[7005] | 337 | visited = new HashSet<>();
|
---|
| 338 | uploadOrder = new LinkedList<>();
|
---|
[8856] | 339 | Stack<Relation> path = new Stack<>();
|
---|
[2512] | 340 | for (Relation relation: relations) {
|
---|
| 341 | visit(path, relation);
|
---|
| 342 | }
|
---|
[7005] | 343 | List<Relation> ret = new ArrayList<>(relations);
|
---|
[13018] | 344 | Comparator<? super Relation> cmpr = Comparator.comparingInt(uploadOrder::indexOf);
|
---|
| 345 | if (reverse) {
|
---|
| 346 | cmpr = cmpr.reversed();
|
---|
| 347 | }
|
---|
| 348 | ret.sort(cmpr);
|
---|
[2512] | 349 | return ret;
|
---|
| 350 | }
|
---|
| 351 | }
|
---|
| 352 | }
|
---|