[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;
|
---|
| 6 | import java.util.Collections;
|
---|
| 7 | import java.util.Comparator;
|
---|
| 8 | import java.util.HashMap;
|
---|
| 9 | import java.util.HashSet;
|
---|
| 10 | import java.util.LinkedList;
|
---|
| 11 | import java.util.List;
|
---|
[6317] | 12 | import java.util.Map;
|
---|
[2512] | 13 | import java.util.Set;
|
---|
[8856] | 14 | import java.util.Stack;
|
---|
[2512] | 15 |
|
---|
[2598] | 16 | import org.openstreetmap.josm.actions.upload.CyclicUploadDependencyException;
|
---|
[2979] | 17 | import org.openstreetmap.josm.data.conflict.Conflict;
|
---|
| 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;
|
---|
[4113] | 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 |
|
---|
[6890] | 60 | public final void init(Collection<OsmPrimitive> primitives) {
|
---|
[2512] | 61 | toAdd.clear();
|
---|
| 62 | toUpdate.clear();
|
---|
| 63 | toDelete.clear();
|
---|
| 64 |
|
---|
[5589] | 65 | for (OsmPrimitive osm :primitives) {
|
---|
[3336] | 66 | if (osm.isNewOrUndeleted() && !osm.isDeleted()) {
|
---|
[2512] | 67 | toAdd.add(osm);
|
---|
| 68 | } else if (osm.isModified() && !osm.isDeleted()) {
|
---|
| 69 | toUpdate.add(osm);
|
---|
[3336] | 70 | } else if (osm.isDeleted() && !osm.isNew() && osm.isModified() && osm.isVisible()) {
|
---|
[2512] | 71 | toDelete.add(osm);
|
---|
| 72 | }
|
---|
| 73 | }
|
---|
[7120] | 74 | OsmPrimitiveComparator c = new OsmPrimitiveComparator(false, true);
|
---|
[4874] | 75 | Collections.sort(toDelete, c);
|
---|
| 76 | Collections.sort(toAdd, c);
|
---|
| 77 | Collections.sort(toUpdate, c);
|
---|
[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 APIDataSet(DataSet ds) {
|
---|
| 86 | this();
|
---|
| 87 | init(ds);
|
---|
| 88 | }
|
---|
| 89 |
|
---|
| 90 | /**
|
---|
[2979] | 91 | * Replies true if one of the primitives to be updated or to be deleted
|
---|
| 92 | * participates in the conflict <code>conflict</code>
|
---|
[3530] | 93 | *
|
---|
[2979] | 94 | * @param conflict the conflict
|
---|
| 95 | * @return true if one of the primitives to be updated or to be deleted
|
---|
| 96 | * participates in the conflict <code>conflict</code>
|
---|
| 97 | */
|
---|
| 98 | public boolean participatesInConflict(Conflict<?> conflict) {
|
---|
| 99 | 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>
|
---|
[3530] | 112 | *
|
---|
[2979] | 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;
|
---|
[7005] | 119 | Set<PrimitiveId> idsParticipatingInConflicts = new HashSet<>();
|
---|
[2979] | 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 | /**
|
---|
[2512] | 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();
|
---|
[5589] | 142 | init(primitives);
|
---|
[2512] | 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() {
|
---|
[8338] | 187 | List<OsmPrimitive> ret = new LinkedList<>();
|
---|
[2512] | 188 | ret.addAll(toAdd);
|
---|
| 189 | ret.addAll(toUpdate);
|
---|
| 190 | ret.addAll(toDelete);
|
---|
| 191 | return ret;
|
---|
| 192 | }
|
---|
| 193 |
|
---|
| 194 | /**
|
---|
[2598] | 195 | * Replies the number of objects to upload
|
---|
[2711] | 196 | *
|
---|
[2598] | 197 | * @return the number of objects to upload
|
---|
| 198 | */
|
---|
| 199 | public int getSize() {
|
---|
| 200 | return toAdd.size() + toUpdate.size() + toDelete.size();
|
---|
| 201 | }
|
---|
| 202 |
|
---|
[4534] | 203 | public void removeProcessed(Collection<IPrimitive> processed) {
|
---|
[2598] | 204 | if (processed == null) return;
|
---|
| 205 | toAdd.removeAll(processed);
|
---|
| 206 | toUpdate.removeAll(processed);
|
---|
| 207 | toDelete.removeAll(processed);
|
---|
| 208 | }
|
---|
| 209 |
|
---|
| 210 | /**
|
---|
[2512] | 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 | *
|
---|
[8291] | 217 | * @throws CyclicUploadDependencyException if a cyclic dependency is detected
|
---|
[2512] | 218 | */
|
---|
[8510] | 219 | public void adjustRelationUploadOrder() throws CyclicUploadDependencyException {
|
---|
[8338] | 220 | List<OsmPrimitive> newToAdd = new LinkedList<>();
|
---|
[4100] | 221 | newToAdd.addAll(Utils.filteredCollection(toAdd, Node.class));
|
---|
| 222 | newToAdd.addAll(Utils.filteredCollection(toAdd, Way.class));
|
---|
[2512] | 223 |
|
---|
[7005] | 224 | List<Relation> relationsToAdd = new ArrayList<>(Utils.filteredCollection(toAdd, Relation.class));
|
---|
[2512] | 225 | List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
|
---|
| 226 | newToAdd.addAll(noProblemRelations);
|
---|
| 227 | relationsToAdd.removeAll(noProblemRelations);
|
---|
| 228 |
|
---|
[6776] | 229 | RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd, true);
|
---|
[2512] | 230 | newToAdd.addAll(graph.computeUploadOrder());
|
---|
| 231 | toAdd = newToAdd;
|
---|
[6776] | 232 |
|
---|
[8338] | 233 | List<OsmPrimitive> newToDelete = new LinkedList<>();
|
---|
[6776] | 234 | graph = new RelationUploadDependencyGraph(Utils.filteredCollection(toDelete, Relation.class), false);
|
---|
| 235 | newToDelete.addAll(graph.computeUploadOrder());
|
---|
[6801] | 236 | newToDelete.addAll(Utils.filteredCollection(toDelete, Way.class));
|
---|
| 237 | newToDelete.addAll(Utils.filteredCollection(toDelete, Node.class));
|
---|
[6776] | 238 | toDelete = newToDelete;
|
---|
[2512] | 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) {
|
---|
[7005] | 250 | List<Relation> ret = new LinkedList<>();
|
---|
[2512] | 251 | for (Relation relation: relations) {
|
---|
| 252 | boolean refersToNewRelation = false;
|
---|
| 253 | for (RelationMember m : relation.getMembers()) {
|
---|
[3336] | 254 | if (m.isRelation() && m.getMember().isNewOrUndeleted()) {
|
---|
[2512] | 255 | refersToNewRelation = true;
|
---|
| 256 | break;
|
---|
| 257 | }
|
---|
| 258 | }
|
---|
| 259 | if (!refersToNewRelation) {
|
---|
| 260 | ret.add(relation);
|
---|
| 261 | }
|
---|
| 262 | }
|
---|
| 263 | return ret;
|
---|
| 264 | }
|
---|
| 265 |
|
---|
| 266 | /**
|
---|
[2915] | 267 | * Utility class to sort a collection of new relations with their dependencies
|
---|
[2512] | 268 | * topologically.
|
---|
| 269 | *
|
---|
| 270 | */
|
---|
[4874] | 271 | private static class RelationUploadDependencyGraph {
|
---|
[9067] | 272 | private final Map<Relation, Set<Relation>> children = new HashMap<>();
|
---|
[2512] | 273 | private Collection<Relation> relations;
|
---|
[7005] | 274 | private Set<Relation> visited = new HashSet<>();
|
---|
[2512] | 275 | private List<Relation> uploadOrder;
|
---|
[6776] | 276 | private final boolean newOrUndeleted;
|
---|
[2512] | 277 |
|
---|
[8836] | 278 | RelationUploadDependencyGraph(Collection<Relation> relations, boolean newOrUndeleted) {
|
---|
[6776] | 279 | this.newOrUndeleted = newOrUndeleted;
|
---|
[2512] | 280 | build(relations);
|
---|
| 281 | }
|
---|
| 282 |
|
---|
[6890] | 283 | public final void build(Collection<Relation> relations) {
|
---|
[7005] | 284 | this.relations = new HashSet<>();
|
---|
[8510] | 285 | for (Relation relation: relations) {
|
---|
[6776] | 286 | if (newOrUndeleted ? !relation.isNewOrUndeleted() : !relation.isDeleted()) {
|
---|
[2512] | 287 | continue;
|
---|
| 288 | }
|
---|
| 289 | this.relations.add(relation);
|
---|
| 290 | for (RelationMember m: relation.getMembers()) {
|
---|
[6776] | 291 | if (m.isRelation() && (newOrUndeleted ? m.getMember().isNewOrUndeleted() : m.getMember().isDeleted())) {
|
---|
[8510] | 292 | addDependency(relation, (Relation) m.getMember());
|
---|
[2512] | 293 | }
|
---|
| 294 | }
|
---|
| 295 | }
|
---|
| 296 | }
|
---|
| 297 |
|
---|
| 298 | public Set<Relation> getChildren(Relation relation) {
|
---|
| 299 | Set<Relation> p = children.get(relation);
|
---|
| 300 | if (p == null) {
|
---|
[7005] | 301 | p = new HashSet<>();
|
---|
[2512] | 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 |
|
---|
[8856] | 311 | protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException {
|
---|
[2512] | 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)) {
|
---|
[8510] | 320 | visit(path, dependent);
|
---|
[2512] | 321 | }
|
---|
| 322 | uploadOrder.add(current);
|
---|
| 323 | path.pop();
|
---|
| 324 | }
|
---|
| 325 | }
|
---|
| 326 |
|
---|
| 327 | public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
|
---|
[7005] | 328 | visited = new HashSet<>();
|
---|
| 329 | uploadOrder = new LinkedList<>();
|
---|
[8856] | 330 | Stack<Relation> path = new Stack<>();
|
---|
[2512] | 331 | for (Relation relation: relations) {
|
---|
| 332 | visit(path, relation);
|
---|
| 333 | }
|
---|
[7005] | 334 | List<Relation> ret = new ArrayList<>(relations);
|
---|
[2512] | 335 | Collections.sort(
|
---|
| 336 | ret,
|
---|
| 337 | new Comparator<Relation>() {
|
---|
[6084] | 338 | @Override
|
---|
[2512] | 339 | public int compare(Relation o1, Relation o2) {
|
---|
[8365] | 340 | return Integer.compare(uploadOrder.indexOf(o1), uploadOrder.indexOf(o2));
|
---|
[2512] | 341 | }
|
---|
| 342 | }
|
---|
[4874] | 343 | );
|
---|
[2512] | 344 | return ret;
|
---|
| 345 | }
|
---|
| 346 | }
|
---|
| 347 | }
|
---|