Index: trunk/src/org/openstreetmap/josm/gui/dialogs/relation/GenericRelationEditor.java =================================================================== --- trunk/src/org/openstreetmap/josm/gui/dialogs/relation/GenericRelationEditor.java (revision 1784) +++ trunk/src/org/openstreetmap/josm/gui/dialogs/relation/GenericRelationEditor.java (revision 1785) @@ -19,4 +19,6 @@ import java.util.Arrays; import java.util.Collection; +import java.util.LinkedList; +import java.util.Vector; import javax.swing.JDialog; @@ -365,166 +367,213 @@ private void sort() { - java.util.HashMap> points = - new java.util.HashMap>(); - java.util.HashMap nodes = - new java.util.HashMap(); - int i; - boolean lastWayStartUsed = true; - - // TODO: sort only selected rows - - for (i = 1; i < getClone().members.size(); ++i) + RelationNodeMap map = new RelationNodeMap(getClone()); + Vector> segments; + LinkedList segment; + Node startSearchNode; + Node endSearchNode; + boolean something_done; + + /* + * sort any 2 or more connected elements together + * may be slow with many unconnected members + * TODO: cleanup again, too much code in 1 method + */ + + segments = new Vector>(); + // add first member of relation, not strictly necessary + if (map.remove(0, getClone().members.get(0))) { - RelationMember m = getClone().members.get(i); - if (m.member.incomplete) - // TODO: emit some message that sorting failed - return; - try + segment = new LinkedList(); + segment.add(Integer.valueOf(0)); + segments.add(segment); + } + while (!map.isEmpty()) + { + segment = segments.lastElement(); + + do { - Way w = (Way)m.member; - if (!points.containsKey(w.firstNode())) + something_done = false; + startSearchNode = null; + endSearchNode = null; + if (segment.size() == 1) { - points.put(w.firstNode(), new java.util.TreeSet()); - } - points.get(w.firstNode()).add(Integer.valueOf(i)); - - if (!points.containsKey(w.lastNode())) - { - points.put(w.lastNode(), new java.util.TreeSet()); - } - points.get(w.lastNode()).add(Integer.valueOf(i)); - } - catch(ClassCastException e1) - { - try - { - Node n = (Node)m.member; - nodes.put(n, Integer.valueOf(i)); - } - catch(ClassCastException e2) - { - System.err.println("relation member sort: member " + i + " is not a way or node"); - return; - } - } - } - - for (i = 0; i < getClone().members.size(); ++i) - { - RelationMember m = getClone().members.get(i); - Integer m2 = null; - Node searchNode = null; - try - { - Way w = (Way)m.member; - - if (lastWayStartUsed || ((i == 0) && !m.role.equals("backward"))) - { - // try end node - searchNode = w.lastNode(); - } - else /* if ((m2 == null) && (!lastWayStartUsed || (i == 0))) */ - { - searchNode = w.firstNode(); - } - } - catch(ClassCastException e1) - { - try - { - Node n = (Node)m.member; - searchNode = n; - } - catch(ClassCastException e2) - { - // impossible - } - } - - try { - m2 = nodes.get(searchNode); - if (m2 == null) - { - m2 = points.get(searchNode).first(); - if (m.member == getClone().members.get(m2).member) + RelationMember m = getClone().members.get(segment.getFirst()); + try { - m2 = points.get(searchNode).last(); - } - } - } catch(NullPointerException f) {} - catch(java.util.NoSuchElementException e) {} - - if ((m2 == null) && ((i+1) < getClone().members.size())) - { - // TODO: emit some message that sorting failed - System.err.println("relation member sort: could not find linked way or node for member " + i); - break; - } - - if (m2 != null) - { - try - { - Way next = (Way)getClone().members.get(m2).member; - lastWayStartUsed = searchNode.equals(next.firstNode()); - } - catch(ClassCastException e) - { - } - - if ((m2 < getClone().members.size()) && ((i+1) < getClone().members.size())) - { - RelationMember a = getClone().members.get(i+1); - RelationMember b = getClone().members.get(m2); - - if (m2 != (i+1)) + Way w = (Way)m.member; + endSearchNode = w.lastNode(); + startSearchNode = w.firstNode(); + } + catch(ClassCastException e1) { - getClone().members.set(i+1, b); - getClone().members.set(m2, a); - try { - if (!points.get(((Way)b.member).firstNode()).remove(m2)) - { - System.err.println("relation member sort: could not remove start mapping for " + m2); - } - if (!points.get(((Way)b.member).lastNode()).remove(m2)) - { - System.err.println("relation member sort: could not remove end mapping for " + m2); - } - } - catch(ClassCastException e1) + Node n = (Node)m.member; + endSearchNode = n; + } + catch(ClassCastException e2) { - nodes.remove(b.member); - } - + // impossible + } + } + } + else + { + // add unused node of first element and unused node of last element + // start with the first element + RelationMember element = getClone().members.get(segment.getFirst()); + RelationMember other_element = getClone().members.get(segment.get(1)); + + try + { + Way w = (Way)element.member; try { - points.get(((Way)a.member).firstNode()).add(m2); - points.get(((Way)a.member).lastNode()).add(m2); - } - catch(ClassCastException e1) + Way x = (Way)other_element.member; + if ((w.firstNode() == x.firstNode()) || (w.firstNode() == x.lastNode())) + { + startSearchNode = w.lastNode(); + } + else + { + startSearchNode = w.firstNode(); + } + } + catch(ClassCastException e3) { - nodes.put((Node)a.member, m2); - } - } + try + { + Node m = (Node)other_element.member; + if (w.firstNode() == m) + { + startSearchNode = w.lastNode(); + } + else + { + startSearchNode = w.firstNode(); + } + } + catch(ClassCastException e4) + { + // impossible + } + } + } + catch(ClassCastException e1) + { + try + { + Node n = (Node)element.member; + startSearchNode = n; + } + catch(ClassCastException e2) + { + // impossible + } + } + // now the same for the last element + element = getClone().members.get(segment.getLast()); + other_element = getClone().members.get(segment.get(segment.size() - 2)); + try { - if (!points.get(((Way)a.member).firstNode()).remove(i+1)) + Way w = (Way)element.member; + try { - System.err.println("relation member sort: could not remove start mapping for " + (i+1)); - } - if (!points.get(((Way)a.member).lastNode()).remove(i+1)) + Way x = (Way)other_element.member; + if ((w.firstNode() == x.firstNode()) || (w.firstNode() == x.lastNode())) + { + endSearchNode = w.lastNode(); + } + else + { + endSearchNode = w.firstNode(); + } + } + catch(ClassCastException e3) { - System.err.println("relation member sort: could not remove end mapping for " + (i+1)); + try + { + Node m = (Node)other_element.member; + if (w.firstNode() == m) + { + endSearchNode = w.lastNode(); + } + else + { + endSearchNode = w.firstNode(); + } + } + catch(ClassCastException e4) + { + // impossible + } } } catch(ClassCastException e1) { - nodes.remove(a.member); - } - } - } - } + try + { + Node n = (Node)element.member; + endSearchNode = n; + } + catch(ClassCastException e2) + { + // impossible + } + } + } + + // 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, getClone().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, getClone().members.get(m2)); + something_done = true; + } + } + } while (something_done); + + Integer next = map.pop(); + if (next == null) + { + break; + } + + segment = new LinkedList(); + segment.add(next); + segments.add(segment); + } + // append map.remaining() to segments list (as a single segment) + segment = new LinkedList(); + segment.addAll(map.getRemaining()); + segments.add(segment); + + // now we need to actually re-order the relation members + ArrayList newmembers = new ArrayList(); + for (LinkedList segment2 : segments) + { + for (Integer p : segment2) + { + newmembers.add(getClone().members.get(p)); + } + } + getClone().members.clear(); + getClone().members.addAll(newmembers); + refreshTables(); } @@ -651,4 +700,5 @@ Node way2first = ((Way)(way2.member)).firstNode(); Node way2last = ((Way)(way2.member)).lastNode(); + /* if (way1.role.equals("forward")) { way1first = null; @@ -661,5 +711,5 @@ way2first = null; } - + */ if (way1first != null && way2first != null && way1first.equals(way2first)) { link = WayConnectionType.tail_to_tail; Index: trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java =================================================================== --- trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java (revision 1785) +++ trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java (revision 1785) @@ -0,0 +1,157 @@ +package org.openstreetmap.josm.gui.dialogs.relation; + +import org.openstreetmap.josm.data.osm.Node; +import org.openstreetmap.josm.data.osm.Relation; +import org.openstreetmap.josm.data.osm.RelationMember; +import org.openstreetmap.josm.data.osm.Way; + +/** + * A mapping from Node positions to elements in a Relation + * (currently Nodes and Ways only) + * + * @author Christiaan Welvaart + * + */ +public class RelationNodeMap { + private java.util.HashMap> points; + private java.util.HashMap nodes; + private java.util.Vector remaining; + private Relation relation; + + RelationNodeMap(Relation relation) + { + int i; + + this.relation = relation; + points = new java.util.HashMap>(); + nodes = new java.util.HashMap(); + remaining = new java.util.Vector(); + + for (i = 0; i < relation.members.size(); ++i) + { + RelationMember m = relation.members.get(i); + if (m.member.incomplete) + { + // throw an exception? + return; + } + 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 (relation.members.get(current).member == relation.members.get(result).member) + { + result = points.get(node).last(); + } + } + } catch(NullPointerException f) {} + catch(java.util.NoSuchElementException e) {} + + return result; + } + + void add(int n, RelationMember m) + { + try + { + Way w = (Way)m.member; + if (!points.containsKey(w.firstNode())) + { + points.put(w.firstNode(), new java.util.TreeSet()); + } + points.get(w.firstNode()).add(Integer.valueOf(n)); + + if (!points.containsKey(w.lastNode())) + { + points.put(w.lastNode(), new java.util.TreeSet()); + } + points.get(w.lastNode()).add(Integer.valueOf(n)); + } + catch(ClassCastException e1) + { + try + { + Node node = (Node)m.member; + nodes.put(node, Integer.valueOf(n)); + } + catch(ClassCastException e2) + { + remaining.add(Integer.valueOf(n)); + } + } + } + + boolean remove(int n, RelationMember a) + { + boolean result; + + try + { + result = points.get(((Way)a.member).firstNode()).remove(n); + result &= points.get(((Way)a.member).lastNode()).remove(n); + } + catch(ClassCastException e1) + { + result = (nodes.remove(a.member) != null); + } + + return result; + } + + void move(int from, int to) + { + if (from != to) + { + RelationMember b = relation.members.get(from); + RelationMember a = relation.members.get(to); + + remove(to, b); + add(to, a); + } + } + + // no node-mapped entries left + boolean isEmpty() + { + return points.isEmpty() && nodes.isEmpty(); + } + + java.util.Vector getRemaining() + { + return remaining; + } + + Integer pop() + { + Integer result = null; + + if (!nodes.isEmpty()) + { + result = nodes.values().iterator().next(); + nodes.remove(result); + } + else if (!points.isEmpty()) + { + for (java.util.TreeSet set : points.values()) + { + if (!set.isEmpty()) + { + result = set.first(); + break; + } + } + } + + return result; + } + +}