Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableModel.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableModel.java	(revision 2420)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableModel.java	(revision 2421)
@@ -1,2 +1,3 @@
+// License: GPL. For details, see LICENSE file.
 package org.openstreetmap.josm.gui.dialogs.relation;
 
@@ -569,106 +570,57 @@
     }
 
+    /**
+     * Sort the relation members by the way they are linked.
+     */
     void sort() {
         RelationNodeMap map = new RelationNodeMap(members);
-        Vector<LinkedList<Integer>> segments;
-        LinkedList<Integer> segment;
-        Node startSearchNode;
-        Node endSearchNode;
-        boolean something_done;
-
-        /*
-         * sort any 2 or more connected elements together may be slow with many unconnected members
-         */
-
-        if (map.isEmpty())
-            // empty relation or incomplete members
-            return;
-        segments = new Vector<LinkedList<Integer>>();
-
-        while (!map.isEmpty()) {
-            // find an element for the next segment
-            // try first element in relation if we just started
-            // otherwise, or if first element is another relation, just fetch some element from the
-            // map
-            Integer next;
-            if ((segments.size() == 0) && map.remove(0, members.get(0))) {
-                next = 0;
-            } else {
-                next = map.pop();
-                if (next == null) {
-                    break;
-                }
-            }
-
-            segment = new LinkedList<Integer>();
-            segment.add(next);
-            segments.add(segment);
-
-            do {
-                something_done = false;
-                startSearchNode = null;
-                endSearchNode = null;
-                if (segment.size() == 1) {
-                    // only one element in segment, so try to link against each linkable node of element
-                    RelationMember m = members.get(segment.getFirst());
-                    if (m.isWay()) {
-                        Way w = m.getWay();
-                        endSearchNode = w.lastNode();
-                        if (w.lastNode() != w.firstNode())
-                        {
-                            startSearchNode = w.firstNode();
-                        }
-                    } else if (m.isNode()) {
-                        Node n = m.getNode();
-                        endSearchNode = n;
-                    }
-                } else {
-                    // add unused node of first element and unused node of last element
-                    // start with the first element (compared to next element)
-                    startSearchNode = getUnusedNode(members.get(segment.getFirst()), members.get(segment.get(1)));
-
-                    // now the same for the last element (compared to previous element)
-                    endSearchNode = getUnusedNode(members.get(segment.getLast()), members.get(segment.get(segment.size() - 2)));
-                }
-
-                // let's see if we can find connected elements for endSearchNode and startSearchNode
-                if (startSearchNode != null) {
-                    Integer m2 = map.find(startSearchNode, segment.getFirst());
-                    if (m2 != null) {
-                        segment.add(0, m2);
-                        map.remove(m2, members.get(m2));
-                        something_done = true;
-                    }
-                }
-                if (endSearchNode != null) {
-                    Integer m2 = map.find(endSearchNode, segment.getLast());
-                    if (m2 != null) {
-                        segment.add(segment.size(), m2);
-                        map.remove(m2, members.get(m2));
-                        something_done = true;
-                    }
-                }
-            } while (something_done);
-
-        }
-
-        if (segments.size() > 0) {
-            // append map.remaining() to segments list (as a single segment)
-            segment = new LinkedList<Integer>();
-            segment.addAll(map.getRemaining());
-            segments.add(segment);
-
-            // now we need to actually re-order the relation members
-            ArrayList<RelationMember> newmembers = new ArrayList<RelationMember>();
-            for (LinkedList<Integer> segment2 : segments) {
-                for (Integer p : segment2) {
-                    newmembers.add(members.get(p));
-                }
-            }
-            members.clear();
-            members.addAll(newmembers);
-
-            fireTableDataChanged();
-        }
+
+        // List of groups of linked members
+        //
+        ArrayList<LinkedList<Integer>> allGroups = new ArrayList<LinkedList<Integer>>();
+
+        // current group of members that are linked among each other
+        // Two successive members are always linked i.e. have a common node.
+        // 
+        LinkedList<Integer> group;
+
+        Integer first;
+        while ((first = map.pop()) != null) {
+            group = new LinkedList<Integer>();
+            group.add(first);
+
+            allGroups.add(group);
+
+            Integer next = first;
+            while ((next = map.popAdjacent(next)) != null) {
+                group.addLast(next);
+            }
+
+            // The first element need not be in front of the list.
+            // So the search goes in both directions
+            //
+            next = first;
+            while ((next = map.popAdjacent(next)) != null) {
+                group.addFirst(next);
+            }
+
+        }
+
+        group = new LinkedList<Integer>();
+        group.addAll(map.getNotSortableMembers());
+        allGroups.add(group);
+
+        ArrayList<RelationMember> newMembers = new ArrayList<RelationMember>();
+        for (LinkedList<Integer> tmpGroup : allGroups) {
+            for (Integer p : tmpGroup) {
+                newMembers.add(members.get(p));
+            }
+        }
+
+        if (members.size() != newMembers.size()) throw new AssertionError();
+        
+        members.clear();
+        members.addAll(newMembers);
+        fireTableDataChanged();
     }
 
@@ -679,5 +631,5 @@
      *
      * If both ways are not linked in any way, NONE is returned.
-     * 
+     *
      * Else the direction is given as follows:
      * Let the relation be a route of oneway streets, and someone travels them in the given order.
@@ -711,7 +663,7 @@
         /** the list of nodes the way k can dock to */
         List<Node> refNodes= new ArrayList<Node>();
-        
+
         switch (ref_direction) {
-            case FORWARD: 
+            case FORWARD:
                 refNodes.add(way_ref.lastNode());
                 break;
@@ -728,5 +680,5 @@
             return NONE;
         }
-        
+
         for (Node n : refNodes) {
             if (n == null) continue;
@@ -752,13 +704,16 @@
      * determine, if the way i is a roundabout and if yes, what type of roundabout
      */
-    private Direction roundaboutType(int i) {
+    private Direction roundaboutType(int i) { //FIXME
         RelationMember m = members.get(i);
         if (m == null || !m.isWay()) return NONE;
         Way w = m.getWay();
-        if (w != null &&        
-                "roundabout".equals(w.get("junction")) && 
+        return roundaboutType(w);
+    }
+    static Direction roundaboutType(Way w) {
+        if (w != null &&
+                "roundabout".equals(w.get("junction")) &&
                 w.getNodesCount() < 200 &&
                 w.getNodesCount() > 2 &&
-                w.getNode(0) != null && 
+                w.getNode(0) != null &&
                 w.getNode(1) != null &&
                 w.getNode(2) != null &&
@@ -775,5 +730,5 @@
             return NONE;
     }
-    
+
     private WayConnectionType wayConnection(int i) {
         if (connectionType == null) {
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java	(revision 2420)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java	(revision 2421)
@@ -1,5 +1,10 @@
+// License: GPL. For details, see LICENSE file.
 package org.openstreetmap.josm.gui.dialogs.relation;
 
 import java.util.ArrayList;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.TreeMap;
 import java.util.TreeSet;
 
@@ -8,140 +13,166 @@
 import org.openstreetmap.josm.data.osm.Way;
 
+import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.*;
+
 /**
- * A mapping from Node positions to elements in a Relation (currently Nodes and Ways only)
+ * Auxiliary class for relation sorting.
+ *
+ * Constructs two mappings: One that maps each way to its nodes and the inverse mapping that
+ * maps each node to all ways that have this node.
+ * After construction both maps are consistent, but later on objects that are no longer needed
+ * are removed from the value sets.
+ * However the corresponding keys are not deleted even if they map to an empty set.
+ * Note that normal ways have 2 nodes (beginning and end) but roundabouts can have less or more
+ * (that are shared by other members).
  *
  * @author Christiaan Welvaart <cjw@time4t.net>
- *
+ * 
  */
 public class RelationNodeMap {
+    /*
+     * read only list of all relation members
+     */
+    private final List<RelationMember> members;
+    /*
+     * the maps. (Need TreeMap for efficiency.)
+     */
+    private TreeMap<Node, TreeSet<Integer>> nodesMap;
+    private TreeMap<Integer, TreeSet<Node>> waysMap;
+    /*
+     * Used to keep track of what members are done.
+     */
+    private TreeSet<Integer> remaining;
+
     /**
-     * For each way endpoint, list all ways that share this node
+     * All members that are incomplete or not a way
      */
-    private java.util.HashMap<Node, TreeSet<Integer>> points;
-    /**
-     * Singleton nodes
-     */
-    private java.util.HashMap<Node, Integer> nodes;
-    private java.util.Vector<Integer> remaining;
-    /**
-     * read only list
-     */
-    private final ArrayList<RelationMember> members;
+    private List<Integer> notSortable = new ArrayList<Integer>();
 
     RelationNodeMap(ArrayList<RelationMember> members) {
-        int i;
+        this.members = members;
 
-        this.members = members;
-        points = new java.util.HashMap<Node, TreeSet<Integer>>();
-        nodes = new java.util.HashMap<Node, Integer>();
-        remaining = new java.util.Vector<Integer>();
+        nodesMap = new TreeMap<Node, TreeSet<Integer>>();
+        waysMap = new TreeMap<Integer, TreeSet<Node>>();
 
-        for (i = 0; i < members.size(); ++i) {
+        for (int i = 0; i < members.size(); ++i) {
             RelationMember m = members.get(i);
-            if (m.getMember().incomplete)
+            if (m.getMember().incomplete || !m.isWay())
             {
-                remaining.add(Integer.valueOf(i));
+                notSortable.add(i);
             }
-            else
-            {
-                add(i, m);
-            }
-        }
-    }
-
-    Integer find(Node node, int current) {
-        Integer result = null;
-
-        try {
-            result = nodes.get(node);
-            if (result == null) {
-                result = points.get(node).first();
-                if (members.get(current).getMember() == members.get(result).getMember()) {
-                    result = points.get(node).last();
-                }
-            }
-        } catch (NullPointerException f) {
-        } catch (java.util.NoSuchElementException e) {
-        }
-
-        return result;
-    }
-
-    void add(int n, RelationMember m) {
-        if (m.isWay()) {
-            Way w = m.getWay();
-            if (w.lastNode() == w.firstNode())
-            {
-                nodes.put(w.firstNode(), n);
-            }
-            else
-            {
-                if (!points.containsKey(w.firstNode())) {
-                    points.put(w.firstNode(), new TreeSet<Integer>());
-                }
-                points.get(w.firstNode()).add(n);
-
-                if (!points.containsKey(w.lastNode())) {
-                    points.put(w.lastNode(), new TreeSet<Integer>());
-                }
-                points.get(w.lastNode()).add(n);
-            }
-        } else if (m.isNode()) {
-            Node node = m.getNode();
-            nodes.put(node, n);
-        } else {
-            remaining.add(n);
-        }
-    }
-
-    boolean remove(int n, RelationMember a) {
-        boolean result;
-        if (a.isWay()) {
-            Way w = a.getWay();
-            if (w.firstNode() == w.lastNode())
-            {
-                result = (nodes.remove(w.firstNode()) != null);
-            }
-            else
-            {
-                result = points.get(w.firstNode()).remove(n);
-                result &= points.get(w.lastNode()).remove(n);
-            }
-        } else {
-            result = (nodes.remove(a.getMember()) != null);
-        }
-        return result;
-    }
-
-    // no node-mapped entries left
-    boolean isEmpty() {
-        return points.isEmpty() && nodes.isEmpty();
-    }
-
-    java.util.Vector<Integer> getRemaining() {
-        return remaining;
-    }
-
-    Integer pop() {
-        Node node = null;
-        Integer result = null;
-
-        if (!nodes.isEmpty()) {
-            node = nodes.keySet().iterator().next();
-            result = nodes.get(node);
-            nodes.remove(node);
-        } else if (!points.isEmpty()) {
-            for (TreeSet<Integer> set : points.values()) {
-                if (!set.isEmpty()) {
-                    result = set.first();
-                    Way w = members.get(result).getWay();
-                    points.get(w.firstNode()).remove(result);
-                    points.get(w.lastNode()).remove(result);
-                    break;
+            else {
+                Way w = m.getWay();
+                if (MemberTableModel.roundaboutType(w) != NONE) {
+                    for (Node nd : w.getNodes()) {
+                        addPair(nd, i);
+                    }
+                } else {
+                    addPair(w.firstNode(), i);
+                    addPair(w.lastNode(), i);
                 }
             }
         }
 
-        return result;
+        remaining = new TreeSet<Integer>();
+        for (Integer k : waysMap.keySet()) {
+            remaining.add(k);
+        }
+
+        /*
+         * Clean up the maps, i.e. remove nodes from roundabouts and dead ends that
+         * cannot be used in future. (only for performance)
+         */
+        Iterator<Map.Entry<Node,TreeSet<Integer>>> it = nodesMap.entrySet().iterator();
+        while (it.hasNext()) {
+            Map.Entry<Node,TreeSet<Integer>> nodeLinks = it.next();
+
+            if (nodeLinks.getValue().size() < 2) {
+//                System.err.println("DELETE: "+nodeLinks.getKey()+" "+nodeLinks.getValue());
+                if (nodeLinks.getValue().size() != 1) throw new AssertionError();
+
+                Integer d_way = nodeLinks.getValue().iterator().next();
+                TreeSet<Node> d_way_nodes = waysMap.get(d_way);
+                d_way_nodes.remove(nodeLinks.getKey());
+
+                it.remove();
+                continue;
+            }
+//            System.err.println(nodeLinks.getKey()+" "+nodeLinks.getValue());
+
+        }
+//        System.err.println("");
+//        System.err.println(remaining);
+//        System.err.println("");
+//        System.err.println(nodesMap);
+//        System.err.println("");
+//        System.err.println(waysMap);
+
+    }
+
+    private void addPair(Node n, int i) {
+        TreeSet<Integer> ts = nodesMap.get(n);
+        if (ts == null) {
+            ts = new TreeSet<Integer>();
+            nodesMap.put(n, ts);
+        }
+        ts.add(i);
+
+        TreeSet<Node> ts2 = waysMap.get(i);
+        if (ts2 == null) {
+            ts2 = new TreeSet<Node>();
+            waysMap.put(i, ts2);
+        }
+        ts2.add(n);
+    }
+
+    /**
+     * Return a relation member that is linked to the
+     * member 'i', but has not been popped jet.
+     * Return null if there is no such member left.
+     */
+    public Integer popAdjacent(Integer i) {
+//        System.err.print("Adjacent["+i+"]:");
+        TreeSet<Node> nodes = waysMap.get(i);
+//        System.err.print(nodes);
+        for (Node n : nodes) {
+//            System.err.print(" {"+n.getId()+"} ");
+            TreeSet<Integer> adj = nodesMap.get(n);
+            if (!adj.isEmpty()) {
+                Integer j = adj.iterator().next();
+                done(j);
+                waysMap.get(j).remove(n);
+//                System.err.println(j);
+                return j;
+            }
+        }
+        return null;
+    }
+
+    /**
+     * Returns some remaining member or null if
+     * every sortable member has been processed.
+     */
+    public Integer pop() {
+        if (remaining.isEmpty()) return null;
+        Integer i = remaining.iterator().next();
+        done(i);
+        return i;
+    }
+
+    /**
+     * This relation member has been processed.
+     * Remove references in the nodesMap.
+     */
+    private void done(Integer i) {
+        remaining.remove(i);
+        TreeSet<Node> nodes = waysMap.get(i);
+        for (Node n : nodes) {
+            boolean result = nodesMap.get(n).remove(i);
+            if (!result) throw new AssertionError();
+        }
+    }
+
+    public List<Integer> getNotSortableMembers() {
+        return notSortable;
     }
 }