Index: /trunk/src/org/openstreetmap/josm/data/APIDataSet.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 2319)
+++ /trunk/src/org/openstreetmap/josm/data/APIDataSet.java	(revision 2320)
@@ -59,12 +59,13 @@
             }
             if (osm.isNew() && !osm.isDeleted()) {
-                toAdd.addLast(osm);
+                toAdd.add(osm);
             } else if (osm.isModified() && !osm.isDeleted()) {
-                toUpdate.addLast(osm);
+                toUpdate.add(osm);
             } else if (osm.isDeleted() && !osm.isNew() && osm.isModified()) {
-                toDelete.addFirst(osm);
+                toDelete.add(osm);
             }
         }
         sortDeleted();
+        sortNew();
     }
 
@@ -92,4 +93,34 @@
                         else if (o2 instanceof Way && o1 instanceof Relation)
                             return -1;
+
+                        return 0;
+                    }
+                }
+        );
+    }
+
+    /**
+     * Ensures that primitives are added in the following order: Nodes, then Ways,
+     * then Relations.
+     * 
+     */
+    protected void sortNew() {
+        Collections.sort(
+                toAdd,
+                new Comparator<OsmPrimitive>() {
+                    public int compare(OsmPrimitive o1, OsmPrimitive o2) {
+                        if (o1 instanceof Node && o2 instanceof Node)
+                            return 0;
+                        else if (o1 instanceof Node)
+                            return -1;
+                        else if (o2 instanceof Node)
+                            return 1;
+
+                        if (o1 instanceof Way && o2 instanceof Way)
+                            return 0;
+                        else if (o1 instanceof Way && o2 instanceof Relation)
+                            return -1;
+                        else if (o2 instanceof Way && o1 instanceof Relation)
+                            return 1;
 
                         return 0;
@@ -127,4 +158,5 @@
             }
         }
+        sortNew();
         sortDeleted();
     }