Changeset 2168 in josm for trunk/src/org/openstreetmap/josm/data

Timestamp:

2009-09-20T11:46:08+02:00 (15 years ago)

Author:

Gubaer

Message:

fixed #3304: Upload failed - Placeholder Relation not found
fixed #2353: Wrong relation upload order results in 512 Precondition Failed
Warning: this is going to break plugins which register Upload Hooks. These plugins will be fixed shortly.

File:

• trunk/src/org/openstreetmap/josm/data/APIDataSet.java (modified) (3 diffs)

trunk/src/org/openstreetmap/josm/data/APIDataSet.java

@@ -2 +2 @@
 package org.openstreetmap.josm.data;
 
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+import java.util.logging.Logger;
 
 import org.openstreetmap.josm.data.osm.DataSet;
+import org.openstreetmap.josm.data.osm.Node;
 import org.openstreetmap.josm.data.osm.OsmPrimitive;
+import org.openstreetmap.josm.data.osm.Relation;
+import org.openstreetmap.josm.data.osm.RelationMember;
+import org.openstreetmap.josm.data.osm.Way;
+
+import org.openstreetmap.josm.actions.upload.CyclicUploadDependencyException;
 
 /**
@@ -13 +28 @@
  * The collection is derived from the modified primitives of an {@see DataSet}.
  * 
- * FIXME: use to optimize the upload order before uploading, see various tickets in trac
  * 
  */
@@ -113 +127 @@
         return ret;
     }
+
+    /**
+     * Adjusts the upload order for new relations. Child relations are uploaded first,
+     * parent relations second.
+     * 
+     * This method detects cyclic dependencies in new relation. Relations with cyclic
+     * dependencies can't be uploaded.
+     * 
+     * @throws CyclicUploadDependencyException thrown, if a cyclic dependency is detected
+     */
+    public void adjustRelationUploadOrder() throws CyclicUploadDependencyException{
+        LinkedList<OsmPrimitive> newToAdd = new LinkedList<OsmPrimitive>();
+        newToAdd.addAll(OsmPrimitive.getFilteredList(toAdd, Node.class));
+        newToAdd.addAll(OsmPrimitive.getFilteredList(toAdd, Way.class));
+
+        List<Relation> relationsToAdd = OsmPrimitive.getFilteredList(toAdd, Relation.class);
+        List<Relation> noProblemRelations = filterRelationsNotReferringToNewRelations(relationsToAdd);
+        newToAdd.addAll(noProblemRelations);
+        relationsToAdd.removeAll(noProblemRelations);
+
+        RelationUploadDependencyGraph graph = new RelationUploadDependencyGraph(relationsToAdd);
+        newToAdd.addAll(graph.computeUploadOrder());
+        toAdd = newToAdd;
+    }
+
+    /**
+     * Replies the subset of relations in <code>relations</code> which are not referring to any
+     * new relation
+     * 
+     * @param relations a list of relations
+     * @return the subset of relations in <code>relations</code> which are not referring to any
+     * new relation
+     */
+    protected List<Relation> filterRelationsNotReferringToNewRelations(Collection<Relation> relations) {
+        List<Relation> ret = new LinkedList<Relation>();
+        for (Relation relation: relations) {
+            boolean refersToNewRelation = false;
+            for (RelationMember m : relation.getMembers()) {
+                if (m.isRelation() && m.getMember().getId() <= 0) {
+                    refersToNewRelation = true;
+                    break;
+                }
+            }
+            if (!refersToNewRelation) {
+                ret.add(relation);
+            }
+        }
+        return ret;
+    }
+
+    /**
+     * Utility class to sort a collection of of new relations with their dependencies
+     * topologically.
+     * 
+     */
+    private class RelationUploadDependencyGraph {
+        private final Logger logger = Logger.getLogger(RelationUploadDependencyGraph.class.getName());
+        private HashMap<Relation, Set<Relation>> children;
+        private Collection<Relation> relations;
+        private Set<Relation> visited;
+        private List<Relation> uploadOrder;
+
+        public RelationUploadDependencyGraph() {
+            this.children = new HashMap<Relation, Set<Relation>>();
+            this.visited = new HashSet<Relation>();
+        }
+
+        public RelationUploadDependencyGraph(Collection<Relation> relations) {
+            this();
+            build(relations);
+        }
+
+        public void build(Collection<Relation> relations) {
+            this.relations = new HashSet<Relation>();
+            for(Relation relation: relations) {
+                if (relation.getId() > 0 ) {
+                    continue;
+                }
+                this.relations.add(relation);
+                for (RelationMember m: relation.getMembers()) {
+                    if (m.isRelation() && m.getMember().getId() == 0) {
+                        addDependency(relation, (Relation)m.getMember());
+                    }
+                }
+            }
+        }
+
+        public Set<Relation> getChildren(Relation relation) {
+            Set<Relation> p = children.get(relation);
+            if (p == null) {
+                p = new HashSet<Relation>();
+                children.put(relation, p);
+            }
+            return p;
+        }
+
+        public void addDependency(Relation relation, Relation child) {
+            getChildren(relation).add(child);
+        }
+
+        protected void visit(Stack<Relation> path, Relation current) throws CyclicUploadDependencyException{
+            if (path.contains(current)) {
+                path.push(current);
+                throw new CyclicUploadDependencyException(path);
+            }
+            if (!visited.contains(current)) {
+                path.push(current);
+                visited.add(current);
+                for (Relation dependent : getChildren(current)) {
+                    visit(path,dependent);
+                }
+                uploadOrder.add(current);
+                path.pop();
+            }
+        }
+
+        public List<Relation> computeUploadOrder() throws CyclicUploadDependencyException {
+            visited = new HashSet<Relation>();
+            uploadOrder = new LinkedList<Relation>();
+            Stack<Relation> path = new Stack<Relation>();
+            for (Relation relation: relations) {
+                visit(path, relation);
+            }
+            ArrayList<Relation> ret = new ArrayList<Relation>(relations);
+            Collections.sort(
+                    ret,
+                    new Comparator<Relation>() {
+                        public int compare(Relation o1, Relation o2) {
+                            return new Integer(uploadOrder.indexOf(o1)).compareTo(uploadOrder.indexOf(o2));
+                        }
+                    }
+            );
+            return ret;
+        }
+    }
 }