[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 |
|
---|
[2598] | 17 | import org.openstreetmap.josm.actions.upload.CyclicUploadDependencyException;
|
---|
[2979] | 18 | import org.openstreetmap.josm.data.conflict.ConflictCollection;
|
---|
[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;
|
---|
[4100] | 28 | import org.openstreetmap.josm.tools.Utils;
|
---|
[2512] | 29 |
|
---|
| 30 | /**
|
---|
[7599] | 31 | * Represents a collection of {@link OsmPrimitive}s which should be uploaded to the API.
|
---|
[5266] | 32 | * The collection is derived from the modified primitives of an {@link DataSet} and it provides methods
|
---|
[2598] | 33 | * for sorting the objects in upload order.
|
---|
[7599] | 34 | * @since 2025
|
---|
[2512] | 35 | */
|
---|
| 36 | public class APIDataSet {
|
---|
[6317] | 37 | private List<OsmPrimitive> toAdd;
|
---|
| 38 | private List<OsmPrimitive> toUpdate;
|
---|
| 39 | private List<OsmPrimitive> toDelete;
|
---|
[2512] | 40 |
|
---|
| 41 | /**
|
---|
| 42 | * creates a new empty data set
|
---|
| 43 | */
|
---|
| 44 | public APIDataSet() {
|
---|
[7005] | 45 | toAdd = new LinkedList<>();
|
---|
| 46 | toUpdate = new LinkedList<>();
|
---|
| 47 | toDelete = new LinkedList<>();
|
---|
[2512] | 48 | }
|
---|
| 49 |
|
---|
| 50 | /**
|
---|
| 51 | * initializes the API data set with the modified primitives in <code>ds</code>
|
---|
| 52 | *
|
---|
| 53 | * @param ds the data set. Ignored, if null.
|
---|
| 54 | */
|
---|
| 55 | public void init(DataSet ds) {
|
---|
| 56 | if (ds == null) return;
|
---|
[5589] | 57 | init(ds.allPrimitives());
|
---|
| 58 | }
|
---|
| 59 |
|
---|
[11175] | 60 | /**
|
---|
| 61 | * Initializes the API data set with the modified primitives, ignores unmodified primitives.
|
---|
| 62 | *
|
---|
| 63 | * @param primitives the primitives
|
---|
| 64 | */
|
---|
[6890] | 65 | public final void init(Collection<OsmPrimitive> primitives) {
|
---|
[2512] | 66 | toAdd.clear();
|
---|
| 67 | toUpdate.clear();
|
---|
| 68 | toDelete.clear();
|
---|
| 69 |
|
---|
[5589] | 70 | for (OsmPrimitive osm :primitives) {
|
---|
[3336] | 71 | if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
|
---|
[2512] | 72 | toAdd.add(osm);
|
---|
| 73 | } else if (osm.isModified() && !osm.isDeleted()) {
|
---|
| 74 | toUpdate.add(osm);
|
---|
[3336] | 75 | } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
|
---|
[2512] | 76 | toDelete.add(osm);
|
---|
| 77 | }
|
---|
| 78 | }
|
---|
[11177] | 79 | final Comparator<OsmPrimitive> orderingNodesWaysRelations = OsmPrimitiveComparator.orderingNodesWaysRelations();
|
---|
| 80 | final Comparator<OsmPrimitive> byUniqueId = OsmPrimitiveComparator.comparingUniqueId();
|
---|
[11176] | 81 | toAdd.sort(orderingNodesWaysRelations.thenComparing(byUniqueId));
|
---|
| 82 | toUpdate.sort(orderingNodesWaysRelations.thenComparing(byUniqueId));
|
---|
| 83 | toDelete.sort(orderingNodesWaysRelations.reversed().thenComparing(byUniqueId));
|
---|
[2512] | 84 | }
|
---|
| 85 |
|
---|
| 86 | /**
|
---|
| 87 | * initializes the API data set with the modified primitives in <code>ds</code>
|
---|
| 88 | *
|
---|
| 89 | * @param ds the data set. Ignored, if null.
|
---|
| 90 | */
|
---|
| 91 | public APIDataSet(DataSet ds) {
|
---|
| 92 | this();
|
---|
| 93 | init(ds);
|
---|
| 94 | }
|
---|
| 95 |
|
---|
| 96 | /**
|
---|
[2979] | 97 | * Replies true if one of the primitives to be updated or to be deleted
|
---|
| 98 | * participates in at least one conflict in <code>conflicts</code>
|
---|
[3530] | 99 | *
|
---|
[2979] | 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;
|
---|
[11175] | 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);
|
---|
[2979] | 114 | }
|
---|
| 115 |
|
---|
| 116 | /**
|
---|
[2512] | 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();
|
---|
[5589] | 123 | init(primitives);
|
---|
[2512] | 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() {
|
---|
[8338] | 168 | List<OsmPrimitive> ret = new LinkedList<>();
|
---|
[2512] | 169 | ret.addAll(toAdd);
|
---|
| 170 | ret.addAll(toUpdate);
|
---|
| 171 | ret.addAll(toDelete);
|
---|
| 172 | return ret;
|
---|
| 173 | }
|
---|
| 174 |
|
---|
| 175 | /**
|
---|
[2598] | 176 | * Replies the number of objects to upload
|
---|
[2711] | 177 | *
|
---|
[2598] | 178 | * @return the number of objects to upload
|
---|
| 179 | */
|
---|
| 180 | public int getSize() {
|
---|
| 181 | return toAdd.size() + toUpdate.size() + toDelete.size();
|
---|
| 182 | }
|
---|
| 183 |
|
---|
[4534] | 184 | public void removeProcessed(Collection<IPrimitive> processed) {
|
---|
[2598] | 185 | if (processed == null) return;
|
---|
| 186 | toAdd.removeAll(processed);
|
---|
| 187 | toUpdate.removeAll(processed);
|
---|
| 188 | toDelete.removeAll(processed);
|
---|
| 189 | }
|
---|
| 190 |
|
---|
| 191 | /**
|
---|
[2512] | 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 | *
|
---|
[8291] | 198 | * @throws CyclicUploadDependencyException if a cyclic dependency is detected
|
---|
[2512] | 199 | */
|
---|
[8510] | 200 | public void adjustRelationUploadOrder() throws CyclicUploadDependencyException {
|
---|
[8338] | 201 | List<OsmPrimitive> newToAdd = new LinkedList<>();
|
---|
[4100] | 202 | newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
|
---|
| 203 | newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
|
---|
[2512] | 204 |
|
---|
[7005] | 205 | List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class));
|
---|
[2512] | 206 | List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
|
---|
| 207 | newToAdd.addAll(noProblemRelations);
|
---|
| 208 | relationsToAdd.removeAll(noProblemRelations);
|
---|
| 209 |
|
---|
[6776] | 210 | RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
|
---|
[2512] | 211 | newToAdd.addAll(graph.computeUploadOrder());
|
---|
| 212 | toAdd = newToAdd;
|
---|
[6776] | 213 |
|
---|
[8338] | 214 | List<OsmPrimitive> newToDelete = new LinkedList<>();
|
---|
[6776] | 215 | graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
|
---|
| 216 | newToDelete.addAll(graph.computeUploadOrder());
|
---|
[6801] | 217 | newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
|
---|
| 218 | newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
|
---|
[6776] | 219 | toDelete = newToDelete;
|
---|
[2512] | 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) {
|
---|
[7005] | 231 | List<Relation> ret = new LinkedList<>();
|
---|
[2512] | 232 | for (Relation relation: relations) {
|
---|
| 233 | boolean refersToNewRelation = false;
|
---|
| 234 | for (RelationMember m : relation.getMembers()) {
|
---|
[3336] | 235 | if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
|
---|
[2512] | 236 | refersToNewRelation = true;
|
---|
| 237 | break;
|
---|
| 238 | }
|
---|
| 239 | }
|
---|
| 240 | if (!refersToNewRelation) {
|
---|
| 241 | ret.add(relation);
|
---|
| 242 | }
|
---|
| 243 | }
|
---|
| 244 | return ret;
|
---|
| 245 | }
|
---|
| 246 |
|
---|
| 247 | /**
|
---|
[2915] | 248 | * Utility class to sort a collection of new relations with their dependencies
|
---|
[2512] | 249 | * topologically.
|
---|
| 250 | *
|
---|
| 251 | */
|
---|
[4874] | 252 | private static class RelationUploadDependencyGraph {
|
---|
[9067] | 253 | private final Map<Relation, Set<Relation>> children = new HashMap<>();
|
---|
[2512] | 254 | private Collection<Relation> relations;
|
---|
[7005] | 255 | private Set<Relation> visited = new HashSet<>();
|
---|
[2512] | 256 | private List<Relation> uploadOrder;
|
---|
[6776] | 257 | private final boolean newOrUndeleted;
|
---|
[2512] | 258 |
|
---|
[8836] | 259 | RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
|
---|
[6776] | 260 | this.newOrUndeleted = newOrUndeleted;
|
---|
[2512] | 261 | build(relations);
|
---|
| 262 | }
|
---|
| 263 |
|
---|
[6890] | 264 | public final void build(Collection<Relation> relations) {
|
---|
[7005] | 265 | this.relations = new HashSet<>();
|
---|
[8510] | 266 | for (Relation relation: relations) {
|
---|
[6776] | 267 | if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
|
---|
[2512] | 268 | continue;
|
---|
| 269 | }
|
---|
| 270 | this.relations.add(relation);
|
---|
| 271 | for (RelationMember m: relation.getMembers()) {
|
---|
[6776] | 272 | if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
|
---|
[8510] | 273 | addDependency(relation, (Relation) m.getMember());
|
---|
[2512] | 274 | }
|
---|
| 275 | }
|
---|
| 276 | }
|
---|
| 277 | }
|
---|
| 278 |
|
---|
| 279 | public Set<Relation> getChildren(Relation relation) {
|
---|
| 280 | Set<Relation> p = children.get(relation);
|
---|
| 281 | if (p == null) {
|
---|
[7005] | 282 | p = new HashSet<>();
|
---|
[2512] | 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 |
|
---|
[8856] | 292 | protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException {
|
---|
[2512] | 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)) {
|
---|
[8510] | 301 | visit(path, dependent);
|
---|
[2512] | 302 | }
|
---|
| 303 | uploadOrder.add(current);
|
---|
| 304 | path.pop();
|
---|
| 305 | }
|
---|
| 306 | }
|
---|
| 307 |
|
---|
| 308 | public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
|
---|
[7005] | 309 | visited = new HashSet<>();
|
---|
| 310 | uploadOrder = new LinkedList<>();
|
---|
[8856] | 311 | Stack<Relation> path = new Stack<>();
|
---|
[2512] | 312 | for (Relation relation: relations) {
|
---|
| 313 | visit(path, relation);
|
---|
| 314 | }
|
---|
[7005] | 315 | List<Relation> ret = new ArrayList<>(relations);
|
---|
[10647] | 316 | ret.sort(Comparator.comparingInt(uploadOrder::indexOf));
|
---|
[2512] | 317 | return ret;
|
---|
| 318 | }
|
---|
| 319 | }
|
---|
| 320 | }
|
---|