Index: /trunk/data_nodist/relation_sort.osm
===================================================================
--- /trunk/data_nodist/relation_sort.osm (revision 5630)
+++ /trunk/data_nodist/relation_sort.osm (revision 5630)
@@ -0,0 +1,165 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTable.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTable.java (revision 5629)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTable.java (revision 5630)
@@ -27,5 +27,6 @@
import org.openstreetmap.josm.gui.MapView;
import org.openstreetmap.josm.gui.MapView.LayerChangeListener;
-import org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction;
import org.openstreetmap.josm.gui.layer.Layer;
import org.openstreetmap.josm.gui.layer.OsmDataLayer;
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableLinkedCellRenderer.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableLinkedCellRenderer.java (revision 5629)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableLinkedCellRenderer.java (revision 5630)
@@ -11,5 +11,6 @@
import javax.swing.JTable;
-import org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction;
import org.openstreetmap.josm.tools.ImageProvider;
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableModel.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableModel.java (revision 5629)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/MemberTableModel.java (revision 5630)
@@ -1,10 +1,4 @@
// License: GPL. For details, see LICENSE file.
package org.openstreetmap.josm.gui.dialogs.relation;
-
-import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.BACKWARD;
-import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.FORWARD;
-import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.NONE;
-import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.ROUNDABOUT_LEFT;
-import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.ROUNDABOUT_RIGHT;
import java.util.ArrayList;
@@ -12,12 +6,8 @@
import java.util.Collection;
import java.util.Collections;
-import java.util.Comparator;
import java.util.EnumSet;
-import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
-import java.util.LinkedList;
import java.util.List;
-import java.util.Map;
import java.util.Set;
import java.util.concurrent.CopyOnWriteArrayList;
@@ -31,11 +21,8 @@
import org.openstreetmap.josm.Main;
import org.openstreetmap.josm.data.SelectionChangedListener;
-import org.openstreetmap.josm.data.coor.EastNorth;
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.data.osm.event.AbstractDatasetChangedEvent;
import org.openstreetmap.josm.data.osm.event.DataChangedEvent;
@@ -48,5 +35,7 @@
import org.openstreetmap.josm.data.osm.event.WayNodesChangedEvent;
import org.openstreetmap.josm.gui.dialogs.properties.PresetListPanel;
-import org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.RelationSorter;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionTypeCalculator;
import org.openstreetmap.josm.gui.layer.OsmDataLayer;
import org.openstreetmap.josm.gui.tagging.TaggingPreset;
@@ -66,11 +55,6 @@
private final PresetListPanel.PresetHandler presetHandler;
- private final int UNCONNECTED = Integer.MIN_VALUE;
-
- private static final Collection additionalSorters = new ArrayList();
-
- static {
- additionalSorters.add(new AssociatedStreetSorter());
- }
+ private final WayConnectionTypeCalculator wayConnectionTypeCalculator = new WayConnectionTypeCalculator();
+ private final RelationSorter relationSorter = new RelationSorter();
/**
@@ -590,7 +574,6 @@
*/
public static boolean hasMembersReferringTo(Collection members, Collection primitives) {
- if (primitives == null || primitives.isEmpty()) {
+ if (primitives == null || primitives.isEmpty())
return false;
- }
HashSet referrers = new HashSet();
for (RelationMember member : members) {
@@ -598,7 +581,6 @@
}
for (OsmPrimitive referred : primitives) {
- if (referrers.contains(referred)) {
+ if (referrers.contains(referred))
return true;
- }
}
return false;
@@ -699,80 +681,4 @@
}*/
- /*
- * Sort a collection of relation members by the way they are linked.
- *
- * @param relationMembers collection of relation members
- * @return sorted collection of relation members
- */
- private List sortMembers(List relationMembers) {
- ArrayList newMembers = new ArrayList();
-
- // Sort members with custom mechanisms (relation-dependent)
- List defaultMembers = new LinkedList();
- Map> customMap = new HashMap>();
-
- // Dispatch members to correct sorters
- for (RelationMember m : relationMembers) {
- for (AdditionalSorter sorter : additionalSorters) {
- List list = defaultMembers;
- if (sorter.acceptsMember(m)) {
- list = customMap.get(sorter);
- if (list == null) {
- customMap.put(sorter, list = new LinkedList());
- }
- }
- list.add(m);
- }
- }
-
- // Sort members and add them to result
- for (AdditionalSorter s : customMap.keySet()) {
- newMembers.addAll(s.sortMembers(customMap.get(s)));
- }
-
- RelationNodeMap map = new RelationNodeMap(defaultMembers);
- // List of groups of linked members
- //
- ArrayList> allGroups = new ArrayList>();
-
- // current group of members that are linked among each other
- // Two successive members are always linked i.e. have a common node.
- //
- LinkedList group;
-
- Integer first;
- while ((first = map.pop()) != null) {
- group = new LinkedList();
- 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);
- }
- }
-
- for (LinkedList tmpGroup : allGroups) {
- for (Integer p : tmpGroup) {
- newMembers.add(defaultMembers.get(p));
- }
- }
-
- // Finally, add members that have not been sorted at all
- for (Integer i : map.getNotSortableMembers()) {
- newMembers.add(defaultMembers.get(i));
- }
-
- return newMembers;
- }
/**
@@ -784,8 +690,8 @@
List newMembers;
if (selectedMembers.size() <= 1) {
- newMembers = sortMembers(members);
+ newMembers = relationSorter.sortMembers(members);
sortedMembers = newMembers;
} else {
- sortedMembers = sortMembers(selectedMembers);
+ sortedMembers = relationSorter.sortMembers(selectedMembers);
List selectedIndices = getSelectedIndices();
newMembers = new ArrayList();
@@ -811,126 +717,8 @@
}
- private Direction determineDirection(int ref_i, Direction ref_direction, int k) {
- return determineDirection(ref_i, ref_direction, k, false);
- }
- /**
- * Determines the direction of way k with respect to the way ref_i.
- * The way ref_i is assumed to have the direction ref_direction and
- * to be the predecessor of k.
- *
- * 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.
- * Direction is FORWARD if it is legal and BACKWARD if it is illegal to do so for the given way.
- *
- **/
- private Direction determineDirection(int ref_i, final Direction ref_direction, int k, boolean reversed) {
- if (ref_i < 0 || k < 0 || ref_i >= members.size() || k >= members.size())
- return NONE;
- if (ref_direction == NONE)
- return NONE;
-
- final RelationMember m_ref = members.get(ref_i);
- final RelationMember m = members.get(k);
- Way way_ref = null;
- Way way = null;
-
- if (m_ref.isWay()) {
- way_ref = m_ref.getWay();
- }
- if (m.isWay()) {
- way = m.getWay();
- }
-
- if (way_ref == null || way == null)
- return NONE;
-
- /** the list of nodes the way k can dock to */
- List refNodes= new ArrayList();
-
- switch (ref_direction) {
- case FORWARD:
- refNodes.add(way_ref.lastNode());
- break;
- case BACKWARD:
- refNodes.add(way_ref.firstNode());
- break;
- case ROUNDABOUT_LEFT:
- case ROUNDABOUT_RIGHT:
- refNodes = way_ref.getNodes();
- break;
- }
-
- if (refNodes == null)
- return NONE;
-
- for (Node n : refNodes) {
- if (n == null) {
- continue;
- }
- if (roundaboutType(k) != NONE) {
- for (Node nn : way.getNodes()) {
- if (n == nn)
- return roundaboutType(k);
- }
- } else if(isOneway(m)) {
- if (n == RelationNodeMap.firstOnewayNode(m) && !reversed) {
- if(isBackward(m))
- return BACKWARD;
- else
- return FORWARD;
- }
- if (n == RelationNodeMap.lastOnewayNode(m) && reversed) {
- if(isBackward(m))
- return FORWARD;
- else
- return BACKWARD;
- }
- } else {
- if (n == way.firstNode())
- return FORWARD;
- if (n == way.lastNode())
- return BACKWARD;
- }
- }
- return NONE;
- }
-
- /**
- * determine, if the way i is a roundabout and if yes, what type of roundabout
- */
- private Direction roundaboutType(int i) {
- RelationMember m = members.get(i);
- if (m == null || !m.isWay()) return NONE;
- Way w = m.getWay();
- 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(1) != null &&
- w.getNode(2) != null &&
- w.firstNode() == w.lastNode()) {
- /** do some simple determinant / cross pruduct test on the first 3 nodes
- to see, if the roundabout goes clock wise or ccw */
- EastNorth en1 = w.getNode(0).getEastNorth();
- EastNorth en2 = w.getNode(1).getEastNorth();
- EastNorth en3 = w.getNode(2).getEastNorth();
- if (en1 != null && en2 != null && en3 != null) {
- en1 = en1.sub(en2);
- en2 = en2.sub(en3);
- return en1.north() * en2.east() - en2.north() * en1.east() > 0 ? ROUNDABOUT_LEFT : ROUNDABOUT_RIGHT;
- }
- }
- return NONE;
- }
WayConnectionType getWayConnection(int i) {
if (connectionType == null) {
- updateLinks();
+ connectionType = wayConnectionTypeCalculator.updateLinks(members);
}
return connectionType.get(i);
@@ -967,89 +755,4 @@
setSelectedMembersIdx(selectedIndices);
}
- }
-
- /**
- * refresh the cache of member WayConnectionTypes
- */
- public void updateLinks() {
- connectionType = null;
- final List con = new ArrayList();
-
- for (int i=0; i 0) {
- makeLoopIfNeeded(con, i-1);
- }
- con.set(i, new WayConnectionType());
- firstGroupIdx = i;
- continue;
- }
-
- WayConnectionType wct = new WayConnectionType(false);
- wct.linkPrev = i>0 && con.get(i-1) != null && con.get(i-1).isValid();
- wct.direction = NONE;
-
- if(isOneway(m)){
- if(lastWct != null && lastWct.isOnewayTail) {
- wct.isOnewayHead = true;
- }
- if(lastBackwardWay == UNCONNECTED && lastForwardWay == UNCONNECTED){ //Beginning of new oneway
- wct.isOnewayHead = true;
- lastForwardWay = i-1;
- lastBackwardWay = i-1;
- onewayBeginning = true;
- }
- }
-
- if (wct.linkPrev) {
- if(lastBackwardWay != UNCONNECTED && lastForwardWay != UNCONNECTED) {
- wct = determineOnewayConnectionType(con, m, i, wct);
- if(!wct.linkPrev) {
- firstGroupIdx = i;
- }
- }
-
- if(!isOneway(m)) {
- wct.direction = determineDirection(i-1, lastWct.direction, i);
- wct.linkPrev = (wct.direction != NONE);
- }
- }
-
- if (!wct.linkPrev) {
- wct.direction = determineDirectionOfFirst(i, m);
- if(isOneway(m)){
- wct.isOnewayLoopForwardPart = true;
- lastForwardWay = i;
- }
- }
-
- wct.linkNext = false;
- if(lastWct != null) {
- lastWct.linkNext = wct.linkPrev;
- }
- con.set(i, wct);
- lastWct = wct;
-
- if(!wct.linkPrev) {
- if(i > 0) {
- makeLoopIfNeeded(con, i-1);
- }
- firstGroupIdx = i;
- }
- }
- makeLoopIfNeeded(con, members.size()-1);
- connectionType = con;
}
@@ -1064,163 +767,3 @@
// }
- private static Direction reverse(final Direction dir){
- if(dir == FORWARD) return BACKWARD;
- if(dir == BACKWARD) return FORWARD;
- return dir;
- }
-
- private static boolean isBackward(final RelationMember member){
- return member.getRole().equals("backward");
- }
-
- private static boolean isForward(final RelationMember member){
- return member.getRole().equals("forward");
- }
-
- public static boolean isOneway(final RelationMember member){
- return isForward(member) || isBackward(member);
- }
-
- int firstGroupIdx;
- private void makeLoopIfNeeded(final List con, final int i) {
- boolean loop;
- if (i == firstGroupIdx) { //is primitive loop
- loop = determineDirection(i, FORWARD, i) == FORWARD;
- } else {
- loop = determineDirection(i, con.get(i).direction, firstGroupIdx) == con.get(firstGroupIdx).direction;
- }
- if (loop) {
- for (int j=firstGroupIdx; j <= i; ++j) {
- con.get(j).isLoop = true;
- }
- }
- }
-
- private Direction determineDirectionOfFirst(final int i, final RelationMember m) {
- if (roundaboutType(i) != NONE)
- return roundaboutType(i);
-
- if (isOneway(m)){
- if(isBackward(m)) return BACKWARD;
- else return FORWARD;
- } else { /** guess the direction and see if it fits with the next member */
- if(determineDirection(i, FORWARD, i+1) != NONE) return FORWARD;
- if(determineDirection(i, BACKWARD, i+1) != NONE) return BACKWARD;
- }
- return NONE;
- }
-
- int lastForwardWay, lastBackwardWay;
- boolean onewayBeginning;
- private WayConnectionType determineOnewayConnectionType(final List con,
- RelationMember m, int i, final WayConnectionType wct) {
- Direction dirFW = determineDirection(lastForwardWay, con.get(lastForwardWay).direction, i);
- Direction dirBW = NONE;
- if(onewayBeginning) {
- if(lastBackwardWay < 0) {
- dirBW = determineDirection(firstGroupIdx, reverse(con.get(firstGroupIdx).direction), i, true);
- } else {
- dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
- }
-
- if(dirBW != NONE) {
- onewayBeginning = false;
- }
- } else {
- dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
- }
-
- if(isOneway(m)) {
- if(dirBW != NONE){
- wct.direction = dirBW;
- lastBackwardWay = i;
- wct.isOnewayLoopBackwardPart = true;
- }
- if(dirFW != NONE){
- wct.direction = dirFW;
- lastForwardWay = i;
- wct.isOnewayLoopForwardPart = true;
- }
- if(dirFW == NONE && dirBW == NONE) { //Not connected to previous
- // unconnectPreviousLink(con, i, true);
- // unconnectPreviousLink(con, i, false);
- wct.linkPrev = false;
- if(isOneway(m)){
- wct.isOnewayHead = true;
- lastForwardWay = i-1;
- lastBackwardWay = i-1;
- } else {
- lastForwardWay = UNCONNECTED;
- lastBackwardWay = UNCONNECTED;
- }
- onewayBeginning = true;
- }
-
- if(dirFW != NONE && dirBW != NONE) { //End of oneway loop
- if(i+1 sortMembers(List list);
- }
-
- /**
- * Class that sorts type=associatedStreet relation's houses.
- */
- private static class AssociatedStreetSorter implements AdditionalSorter {
-
- @Override
- public boolean acceptsMember(RelationMember m) {
- return m != null
- && m.getRole() != null && m.getRole().equals("house")
- && m.getMember() != null && m.getMember().get("addr:housenumber") != null;
- }
-
- @Override
- public List sortMembers(List list) {
- Collections.sort(list, new Comparator() {
- @Override
- public int compare(RelationMember a, RelationMember b) {
- if (a == b || a.getMember() == b.getMember()) return 0;
- String addrA = a.getMember().get("addr:housenumber").trim();
- String addrB = b.getMember().get("addr:housenumber").trim();
- if (addrA.equals(addrB)) return 0;
- // Strip non-digits (from "1B" addresses for example)
- String addrAnum = addrA.replaceAll("\\D+", "");
- String addrBnum = addrB.replaceAll("\\D+", "");
- // Compare only numbers
- try {
- Integer res = Integer.parseInt(addrAnum) - Integer.parseInt(addrBnum);
- if (res != 0) return res;
- } catch (NumberFormatException e) {
- // Ignore NumberFormatException. If the number is not composed of digits, strings are compared next
- }
- // Same number ? Compare full strings
- return addrA.compareTo(addrB);
- }
- });
- return list;
- }
- }
}
Index: unk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/RelationNodeMap.java (revision 5629)
+++ (revision )
@@ -1,371 +1,0 @@
-// License: GPL. For details, see LICENSE file.
-package org.openstreetmap.josm.gui.dialogs.relation;
-
-import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.NONE;
-
-import java.util.ArrayList;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-import java.util.TreeMap;
-import java.util.TreeSet;
-
-import org.openstreetmap.josm.data.osm.Node;
-import org.openstreetmap.josm.data.osm.RelationMember;
-import org.openstreetmap.josm.data.osm.Way;
-
-/**
- * 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
- *
- */
-public class RelationNodeMap {
- private static class NodesWays{
- public Map> nodes = new TreeMap>();
- public Map> ways = new TreeMap>();
- public boolean oneWay;
- public NodesWays(boolean oneWay){
- this.oneWay = oneWay;
- }
- }
-
- /*
- * the maps. (Need TreeMap for efficiency.)
- */
- private NodesWays map = new NodesWays(false);
- /*
- * Maps for oneways (forward/backward roles)
- */
-
- private NodesWays onewayMap = new NodesWays(true);
- private NodesWays onewayReverseMap = new NodesWays(true);
- /*
- * Used to keep track of what members are done.
- */
- private Set remaining;
- private Map> remainingOneway = new TreeMap>();;
-
- /**
- * All members that are incomplete or not a way
- */
- private List notSortable = new ArrayList();
-
- public static Node firstOnewayNode(RelationMember m){
- if(!m.isWay()) return null;
- if(m.getRole().equals("backward")) return m.getWay().lastNode();
- return m.getWay().firstNode();
- }
-
- public static Node lastOnewayNode(RelationMember m){
- if(!m.isWay()) return null;
- if(m.getRole().equals("backward")) return m.getWay().firstNode();
- return m.getWay().lastNode();
- }
-
- RelationNodeMap(List members) {
- map.nodes = new TreeMap>();
- map.ways = new TreeMap>();
-
- for (int i = 0; i < members.size(); ++i) {
- RelationMember m = members.get(i);
- if (m.getMember().isIncomplete() || !m.isWay()) {
- notSortable.add(i);
- continue;
- }
-
- Way w = m.getWay();
- if ((MemberTableModel.roundaboutType(w) != NONE)) {
- for (Node nd : w.getNodes()) {
- addPair(nd, i);
- }
- } else if(MemberTableModel.isOneway(m)) {
- addNodeWayMap(firstOnewayNode(m), i);
- addWayNodeMap(lastOnewayNode(m), i);
- addNodeWayMapReverse(lastOnewayNode(m), i);
- addWayNodeMapReverse(firstOnewayNode(m), i);
- addRemainingForward(firstOnewayNode(m), i);
- addRemainingForward(lastOnewayNode(m), i);
- } else {
- addPair(w.firstNode(), i);
- addPair(w.lastNode(), i);
- }
- }
-
- remaining = new TreeSet();
- remaining.addAll(map.ways.keySet());
-
- /*
- * Clean up the maps, i.e. remove nodes from roundabouts and dead ends that
- * cannot be used in future. (only for performance)
- */
- // Iterator>> it = map.nodes.entrySet().iterator();
- // while (it.hasNext()) {
- // Map.Entry> nodeLinks = it.next();
- //
- // if (nodeLinks.getValue().size() < 2) {
- // if (nodeLinks.getValue().size() != 1) throw new AssertionError();
- //
- // Integer d_way = nodeLinks.getValue().iterator().next();
- // TreeSet d_way_nodes = map.ways.get(d_way);
- // d_way_nodes.remove(nodeLinks.getKey());
- //
- // it.remove();
- // continue;
- // }
- // }
- }
-
- private void addPair(Node n, int i) {
- Set ts = map.nodes.get(n);
- if (ts == null) {
- ts = new TreeSet();
- map.nodes.put(n, ts);
- }
- ts.add(i);
-
- Set ts2 = map.ways.get(i);
- if (ts2 == null) {
- ts2 = new TreeSet();
- map.ways.put(i, ts2);
- }
- ts2.add(n);
- }
-
- private void addNodeWayMap(Node n, int i) {
- Set ts = onewayMap.nodes.get(n);
- if (ts == null) {
- ts = new TreeSet();
- onewayMap.nodes.put(n, ts);
- }
- ts.add(i);
- }
-
- private void addWayNodeMap(Node n, int i) {
- Set ts2 = onewayMap.ways.get(i);
- if (ts2 == null) {
- ts2 = new TreeSet();
- onewayMap.ways.put(i, ts2);
- }
- ts2.add(n);
- }
-
- private void addNodeWayMapReverse(Node n, int i) {
- Set ts = onewayReverseMap.nodes.get(n);
- if (ts == null) {
- ts = new TreeSet();
- onewayReverseMap.nodes.put(n, ts);
- }
- ts.add(i);
- }
-
- private void addWayNodeMapReverse(Node n, int i) {
- Set ts2 = onewayReverseMap.ways.get(i);
- if (ts2 == null) {
- ts2 = new TreeSet();
- onewayReverseMap.ways.put(i, ts2);
- }
- ts2.add(n);
- }
-
- private void addRemainingForward(Node n, int i) {
- Set ts2 = remainingOneway.get(i);
- if (ts2 == null) {
- ts2 = new TreeSet();
- remainingOneway.put(i, ts2);
- }
- ts2.add(n);
- }
-
- Integer firstOneway = null;
- Node lastOnewayNode = null;
- Node firstCircular = null;
-
- /**
- * Return a relation member that is linked to the
- * member 'i', but has not been popped yet.
- * Return null if there is no such member left.
- */
- public Integer popAdjacent(Integer way) {
- if (lastOnewayNode != null) return popBackwardOnewayPart(way);
- if (firstOneway != null) return popForwardOnewayPart(way);
-
- if (map.ways.containsKey(way)){
- for (Node n : map.ways.get(way)) {
- Integer i = deleteAndGetAdjacentNode(map, n);
- if(i != null) return i;
-
- Integer j = deleteAndGetAdjacentNode(onewayMap, n);
- if(j != null) {
- firstOneway = j;
- return j;
- }
- }
- }
-
- firstOneway = way;
- return popForwardOnewayPart(way);
- }
-
- private Integer popForwardOnewayPart(Integer way) {
- if(onewayMap.ways.containsKey(way)) {
- for (Node n : onewayMap.ways.get(way)) {
- Integer i = findAdjacentWay(onewayMap, n);
- if(i == null) {
- continue;
- }
-
- lastOnewayNode = processBackwardIfEndOfLoopReached(i);
- if(lastOnewayNode != null)
- return popBackwardOnewayPart(firstOneway);
-
- deleteWayNode(onewayMap, i, n);
- return i;
- }
- }
-
- firstOneway = null;
- return null;
- }
-
- private Node processBackwardIfEndOfLoopReached(Integer way) { //find if we didn't reach end of the loop (and process backward part)
- if (onewayReverseMap.ways.containsKey(way)) {
- for (Node n : onewayReverseMap.ways.get(way)) {
- if((map.nodes.containsKey(n))
- || (onewayMap.nodes.containsKey(n) && onewayMap.nodes.get(n).size() > 1))
- return n;
- if(firstCircular != null && firstCircular == n)
- return firstCircular;
- }
- }
- return null;
- }
-
- private Integer popBackwardOnewayPart(int way){
- if (lastOnewayNode != null) {
- TreeSet nodes = new TreeSet();
- if (onewayReverseMap.ways.containsKey(way)) {
- nodes.addAll(onewayReverseMap.ways.get(way));
- }
- if (map.ways.containsKey(way)) {
- nodes.addAll(map.ways.get(way));
- }
- for (Node n : nodes) {
- if(n == lastOnewayNode) { //if oneway part ends
- firstOneway = null;
- lastOnewayNode = null;
- Integer j = deleteAndGetAdjacentNode(map, n);
- if(j != null) return j;
-
- Integer k = deleteAndGetAdjacentNode(onewayMap, n);
- if(k != null) {
- firstOneway = k;
- return k;
- }
- }
-
- Integer j = deleteAndGetAdjacentNode(onewayReverseMap, n);
- if(j != null) return j;
- }
- }
-
- firstOneway = null;
- lastOnewayNode = null;
-
- return null;
- }
-
- /**
- * find next node in nw NodeWays structure, if the node is found delete and return it
- * @param nw
- * @param n
- * @return node next to n
- */
- private Integer deleteAndGetAdjacentNode(NodesWays nw, Node n){
- Integer j = findAdjacentWay(nw, n);
- if(j == null) return null;
- deleteWayNode(nw, j, n);
- return j;
- }
-
- private Integer findAdjacentWay(NodesWays nw, Node n) {
- Set adj = nw.nodes.get(n);
- if (adj == null || adj.isEmpty()) return null;
- Integer j = adj.iterator().next();
- return j;
- }
-
- private void deleteWayNode(NodesWays nw, Integer way, Node n){
- if(nw.oneWay) {
- doneOneway(way);
- } else {
- done(way);
- }
- nw.ways.get(way).remove(n);
- }
-
- /**
- * Returns some remaining member or null if
- * every sortable member has been processed.
- */
- public Integer pop() {
- if (!remaining.isEmpty()){
- Integer i = remaining.iterator().next();
- done(i);
- return i;
- }
-
- if (remainingOneway.isEmpty()) return null;
- for(Integer i :remainingOneway.keySet()){ //find oneway, whic is connected to more than one way (is between two oneway loops)
- for(Node n : onewayReverseMap.ways.get(i)){
- if(onewayReverseMap.nodes.containsKey(n) && onewayReverseMap.nodes.get(n).size() > 1) {
- doneOneway(i);
- firstCircular = n;
- return i;
- }
- }
- }
-
- Integer i = remainingOneway.keySet().iterator().next();
- doneOneway(i);
- return i;
- }
-
- /**
- * This relation member has been processed.
- * Remove references in the map.nodes.
- */
- private void doneOneway(Integer i) {
- Set nodesForward = remainingOneway.get(i);
- for (Node n : nodesForward) {
- if(onewayMap.nodes.containsKey(n)) {
- onewayMap.nodes.get(n).remove(i);
- }
- if(onewayReverseMap.nodes.containsKey(n)) {
- onewayReverseMap.nodes.get(n).remove(i);
- }
- }
- remainingOneway.remove(i);
- }
-
- private void done(Integer i) {
- remaining.remove(i);
- Set nodes = map.ways.get(i);
- for (Node n : nodes) {
- boolean result = map.nodes.get(n).remove(i);
- if (!result) throw new AssertionError();
- }
- }
-
- public List getNotSortableMembers() {
- return notSortable;
- }
-}
Index: unk/src/org/openstreetmap/josm/gui/dialogs/relation/WayConnectionType.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/WayConnectionType.java (revision 5629)
+++ (revision )
@@ -1,87 +1,0 @@
-// License: GPL. For details, see LICENSE file.
-package org.openstreetmap.josm.gui.dialogs.relation;
-
-import static org.openstreetmap.josm.gui.dialogs.relation.WayConnectionType.Direction.NONE;
-import static org.openstreetmap.josm.tools.I18n.tr;
-
-public class WayConnectionType {
-
- /** True, if the corresponding primitive is not a way or the way is incomplete */
- private final boolean invalid;
-
- /** True, if linked to the previous / next member. */
- public boolean linkPrev;
- public boolean linkNext;
-
- /**
- * direction is FORWARD if the first node of this way is connected to the previous way
- * and / or the last node of this way is connected to the next way.
- * direction is BACKWARD if it is the other way around.
- * direction has a ROUNDABOUT value, if it is tagged as such and it is somehow
- * connected to the previous / next member.
- * If there is no connection to the previous or next member, then
- * direction has the value NONE.
- */
- public Direction direction;
-
- public enum Direction {
- FORWARD, BACKWARD, ROUNDABOUT_LEFT, ROUNDABOUT_RIGHT, NONE;
-
- public boolean isRoundabout() {
- return this == ROUNDABOUT_RIGHT || this == ROUNDABOUT_LEFT;
- }
- }
-
- /** True, if the element is part of a closed loop of ways. */
- public boolean isLoop;
-
- public boolean isOnewayLoopForwardPart = false;
- public boolean isOnewayLoopBackwardPart = false;
- public boolean isOnewayHead = false;
- public boolean isOnewayTail = false;
-
- public WayConnectionType(boolean linkPrev, boolean linkNext, Direction direction) {
- this.linkPrev = linkPrev;
- this.linkNext = linkNext;
- this.isLoop = false;
- this.direction = direction;
- invalid = false;
- }
-
- public WayConnectionType(boolean invalid){
- this.invalid = invalid;
- }
-
- /** construct invalid instance */
- public WayConnectionType() {
- this.linkPrev = false;
- this.linkNext = false;
- this.isLoop = false;
- this.direction = NONE;
- invalid = true;
- }
-
- public boolean isValid() {
- return !invalid;
- }
-
- @Override
- public String toString() {
- return "[P "+linkPrev+" ;N "+linkNext+" ;D "+direction+" ;L "+isLoop+
- " ;FP " + isOnewayLoopForwardPart+";BP " + isOnewayLoopBackwardPart+
- ";OH " + isOnewayHead+";OT " + isOnewayTail+"]";
- }
-
- public String getToolTip() {
- if (!isValid())
- return "";
- else if (linkPrev && linkNext)
- return tr("way is connected");
- else if (linkPrev)
- return tr("way is connected to previous relation member");
- else if (linkNext)
- return tr("way is connected to next relation member");
- else
- return tr("way is not connected to previous or next relation member");
- }
-}
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationNodeMap.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationNodeMap.java (revision 5630)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationNodeMap.java (revision 5630)
@@ -0,0 +1,368 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.gui.dialogs.relation.sort;
+
+import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.NONE;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+import org.openstreetmap.josm.data.osm.Node;
+import org.openstreetmap.josm.data.osm.RelationMember;
+import org.openstreetmap.josm.data.osm.Way;
+
+/**
+ * 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
+ *
+ */
+public class RelationNodeMap {
+
+ private static class NodesWays{
+ public final Map> nodes = new TreeMap>();
+ public final Map> ways = new TreeMap>();
+ public final boolean oneWay;
+ public NodesWays(boolean oneWay){
+ this.oneWay = oneWay;
+ }
+ }
+
+ /*
+ * the maps. (Need TreeMap for efficiency.)
+ */
+ private final NodesWays map = new NodesWays(false);
+ /*
+ * Maps for oneways (forward/backward roles)
+ */
+
+ private final NodesWays onewayMap = new NodesWays(true);
+ private final NodesWays onewayReverseMap = new NodesWays(true);
+ /*
+ * Used to keep track of what members are done.
+ */
+ private final Set remaining = new TreeSet();
+ private final Map> remainingOneway = new TreeMap>();
+
+ /**
+ * All members that are incomplete or not a way
+ */
+ private final List notSortable = new ArrayList();
+
+ public static Node firstOnewayNode(RelationMember m){
+ if(!m.isWay()) return null;
+ if(m.getRole().equals("backward")) return m.getWay().lastNode();
+ return m.getWay().firstNode();
+ }
+
+ public static Node lastOnewayNode(RelationMember m){
+ if(!m.isWay()) return null;
+ if(m.getRole().equals("backward")) return m.getWay().firstNode();
+ return m.getWay().lastNode();
+ }
+
+ RelationNodeMap(List members) {
+ for (int i = 0; i < members.size(); ++i) {
+ RelationMember m = members.get(i);
+ if (m.getMember().isIncomplete() || !m.isWay()) {
+ notSortable.add(i);
+ continue;
+ }
+
+ Way w = m.getWay();
+ if ((RelationSortUtils.roundaboutType(w) != NONE)) {
+ for (Node nd : w.getNodes()) {
+ addPair(nd, i);
+ }
+ } else if(RelationSortUtils.isOneway(m)) {
+ addNodeWayMap(firstOnewayNode(m), i);
+ addWayNodeMap(lastOnewayNode(m), i);
+ addNodeWayMapReverse(lastOnewayNode(m), i);
+ addWayNodeMapReverse(firstOnewayNode(m), i);
+ addRemainingForward(firstOnewayNode(m), i);
+ addRemainingForward(lastOnewayNode(m), i);
+ } else {
+ addPair(w.firstNode(), i);
+ addPair(w.lastNode(), i);
+ }
+ }
+
+ remaining.addAll(map.ways.keySet());
+
+ /*
+ * Clean up the maps, i.e. remove nodes from roundabouts and dead ends that
+ * cannot be used in future. (only for performance)
+ */
+ // Iterator>> it = map.nodes.entrySet().iterator();
+ // while (it.hasNext()) {
+ // Map.Entry> nodeLinks = it.next();
+ //
+ // if (nodeLinks.getValue().size() < 2) {
+ // if (nodeLinks.getValue().size() != 1) throw new AssertionError();
+ //
+ // Integer d_way = nodeLinks.getValue().iterator().next();
+ // TreeSet d_way_nodes = map.ways.get(d_way);
+ // d_way_nodes.remove(nodeLinks.getKey());
+ //
+ // it.remove();
+ // continue;
+ // }
+ // }
+ }
+
+ private void addPair(Node n, int i) {
+ Set ts = map.nodes.get(n);
+ if (ts == null) {
+ ts = new TreeSet();
+ map.nodes.put(n, ts);
+ }
+ ts.add(i);
+
+ Set ts2 = map.ways.get(i);
+ if (ts2 == null) {
+ ts2 = new TreeSet();
+ map.ways.put(i, ts2);
+ }
+ ts2.add(n);
+ }
+
+ private void addNodeWayMap(Node n, int i) {
+ Set ts = onewayMap.nodes.get(n);
+ if (ts == null) {
+ ts = new TreeSet();
+ onewayMap.nodes.put(n, ts);
+ }
+ ts.add(i);
+ }
+
+ private void addWayNodeMap(Node n, int i) {
+ Set ts2 = onewayMap.ways.get(i);
+ if (ts2 == null) {
+ ts2 = new TreeSet();
+ onewayMap.ways.put(i, ts2);
+ }
+ ts2.add(n);
+ }
+
+ private void addNodeWayMapReverse(Node n, int i) {
+ Set ts = onewayReverseMap.nodes.get(n);
+ if (ts == null) {
+ ts = new TreeSet();
+ onewayReverseMap.nodes.put(n, ts);
+ }
+ ts.add(i);
+ }
+
+ private void addWayNodeMapReverse(Node n, int i) {
+ Set ts2 = onewayReverseMap.ways.get(i);
+ if (ts2 == null) {
+ ts2 = new TreeSet();
+ onewayReverseMap.ways.put(i, ts2);
+ }
+ ts2.add(n);
+ }
+
+ private void addRemainingForward(Node n, int i) {
+ Set ts2 = remainingOneway.get(i);
+ if (ts2 == null) {
+ ts2 = new TreeSet();
+ remainingOneway.put(i, ts2);
+ }
+ ts2.add(n);
+ }
+
+ Integer firstOneway = null;
+ Node lastOnewayNode = null;
+ Node firstCircular = null;
+
+ /**
+ * Return a relation member that is linked to the
+ * member 'i', but has not been popped yet.
+ * Return null if there is no such member left.
+ */
+ public Integer popAdjacent(Integer way) {
+ if (lastOnewayNode != null) return popBackwardOnewayPart(way);
+ if (firstOneway != null) return popForwardOnewayPart(way);
+
+ if (map.ways.containsKey(way)){
+ for (Node n : map.ways.get(way)) {
+ Integer i = deleteAndGetAdjacentNode(map, n);
+ if(i != null) return i;
+
+ Integer j = deleteAndGetAdjacentNode(onewayMap, n);
+ if(j != null) {
+ firstOneway = j;
+ return j;
+ }
+ }
+ }
+
+ firstOneway = way;
+ return popForwardOnewayPart(way);
+ }
+
+ private Integer popForwardOnewayPart(Integer way) {
+ if(onewayMap.ways.containsKey(way)) {
+ for (Node n : onewayMap.ways.get(way)) {
+ Integer i = findAdjacentWay(onewayMap, n);
+ if(i == null) {
+ continue;
+ }
+
+ lastOnewayNode = processBackwardIfEndOfLoopReached(i);
+ if(lastOnewayNode != null)
+ return popBackwardOnewayPart(firstOneway);
+
+ deleteWayNode(onewayMap, i, n);
+ return i;
+ }
+ }
+
+ firstOneway = null;
+ return null;
+ }
+
+ private Node processBackwardIfEndOfLoopReached(Integer way) { //find if we didn't reach end of the loop (and process backward part)
+ if (onewayReverseMap.ways.containsKey(way)) {
+ for (Node n : onewayReverseMap.ways.get(way)) {
+ if((map.nodes.containsKey(n))
+ || (onewayMap.nodes.containsKey(n) && onewayMap.nodes.get(n).size() > 1))
+ return n;
+ if(firstCircular != null && firstCircular == n)
+ return firstCircular;
+ }
+ }
+ return null;
+ }
+
+ private Integer popBackwardOnewayPart(int way){
+ if (lastOnewayNode != null) {
+ TreeSet nodes = new TreeSet();
+ if (onewayReverseMap.ways.containsKey(way)) {
+ nodes.addAll(onewayReverseMap.ways.get(way));
+ }
+ if (map.ways.containsKey(way)) {
+ nodes.addAll(map.ways.get(way));
+ }
+ for (Node n : nodes) {
+ if(n == lastOnewayNode) { //if oneway part ends
+ firstOneway = null;
+ lastOnewayNode = null;
+ Integer j = deleteAndGetAdjacentNode(map, n);
+ if(j != null) return j;
+
+ Integer k = deleteAndGetAdjacentNode(onewayMap, n);
+ if(k != null) {
+ firstOneway = k;
+ return k;
+ }
+ }
+
+ Integer j = deleteAndGetAdjacentNode(onewayReverseMap, n);
+ if(j != null) return j;
+ }
+ }
+
+ firstOneway = null;
+ lastOnewayNode = null;
+
+ return null;
+ }
+
+ /**
+ * find next node in nw NodeWays structure, if the node is found delete and return it
+ * @param nw
+ * @param n
+ * @return node next to n
+ */
+ private Integer deleteAndGetAdjacentNode(NodesWays nw, Node n){
+ Integer j = findAdjacentWay(nw, n);
+ if(j == null) return null;
+ deleteWayNode(nw, j, n);
+ return j;
+ }
+
+ private Integer findAdjacentWay(NodesWays nw, Node n) {
+ Set adj = nw.nodes.get(n);
+ if (adj == null || adj.isEmpty()) return null;
+ Integer j = adj.iterator().next();
+ return j;
+ }
+
+ private void deleteWayNode(NodesWays nw, Integer way, Node n){
+ if(nw.oneWay) {
+ doneOneway(way);
+ } else {
+ done(way);
+ }
+ nw.ways.get(way).remove(n);
+ }
+
+ /**
+ * Returns some remaining member or null if
+ * every sortable member has been processed.
+ */
+ public Integer pop() {
+ if (!remaining.isEmpty()){
+ Integer i = remaining.iterator().next();
+ done(i);
+ return i;
+ }
+
+ if (remainingOneway.isEmpty()) return null;
+ for(Integer i :remainingOneway.keySet()){ //find oneway, which is connected to more than one way (is between two oneway loops)
+ for(Node n : onewayReverseMap.ways.get(i)){
+ if(onewayReverseMap.nodes.containsKey(n) && onewayReverseMap.nodes.get(n).size() > 1) {
+ doneOneway(i);
+ firstCircular = n;
+ return i;
+ }
+ }
+ }
+
+ Integer i = remainingOneway.keySet().iterator().next();
+ doneOneway(i);
+ return i;
+ }
+
+ /**
+ * This relation member has been processed.
+ * Remove references in the map.nodes.
+ */
+ private void doneOneway(Integer i) {
+ Set nodesForward = remainingOneway.get(i);
+ for (Node n : nodesForward) {
+ if(onewayMap.nodes.containsKey(n)) {
+ onewayMap.nodes.get(n).remove(i);
+ }
+ if(onewayReverseMap.nodes.containsKey(n)) {
+ onewayReverseMap.nodes.get(n).remove(i);
+ }
+ }
+ remainingOneway.remove(i);
+ }
+
+ private void done(Integer i) {
+ remaining.remove(i);
+ Set nodes = map.ways.get(i);
+ for (Node n : nodes) {
+ boolean result = map.nodes.get(n).remove(i);
+ if (!result) throw new AssertionError();
+ }
+ }
+
+ public List getNotSortableMembers() {
+ return notSortable;
+ }
+}
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSortUtils.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSortUtils.java (revision 5630)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSortUtils.java (revision 5630)
@@ -0,0 +1,59 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.gui.dialogs.relation.sort;
+
+import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.NONE;
+import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.ROUNDABOUT_LEFT;
+import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.ROUNDABOUT_RIGHT;
+
+import org.openstreetmap.josm.data.coor.EastNorth;
+import org.openstreetmap.josm.data.osm.RelationMember;
+import org.openstreetmap.josm.data.osm.Way;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction;
+
+class RelationSortUtils {
+
+ /**
+ * determine, if the way i is a roundabout and if yes, what type of roundabout
+ */
+ static Direction roundaboutType(RelationMember member) {
+ if (member == null || !member.isWay()) return NONE;
+ Way w = member.getWay();
+ 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(1) != null &&
+ w.getNode(2) != null &&
+ w.firstNode() == w.lastNode()) {
+ /** do some simple determinant / cross pruduct test on the first 3 nodes
+ to see, if the roundabout goes clock wise or ccw */
+ EastNorth en1 = w.getNode(0).getEastNorth();
+ EastNorth en2 = w.getNode(1).getEastNorth();
+ EastNorth en3 = w.getNode(2).getEastNorth();
+ if (en1 != null && en2 != null && en3 != null) {
+ en1 = en1.sub(en2);
+ en2 = en2.sub(en3);
+ return en1.north() * en2.east() - en2.north() * en1.east() > 0 ? ROUNDABOUT_LEFT : ROUNDABOUT_RIGHT;
+ }
+ }
+ return NONE;
+ }
+
+ static boolean isBackward(final RelationMember member){
+ return member.getRole().equals("backward");
+ }
+
+ static boolean isForward(final RelationMember member){
+ return member.getRole().equals("forward");
+ }
+
+ static boolean isOneway(final RelationMember member){
+ return isForward(member) || isBackward(member);
+ }
+
+}
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSorter.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSorter.java (revision 5630)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSorter.java (revision 5630)
@@ -0,0 +1,144 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.gui.dialogs.relation.sort;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+
+import org.openstreetmap.josm.data.osm.RelationMember;
+
+public class RelationSorter {
+
+ private static interface AdditionalSorter {
+ public boolean acceptsMember(RelationMember m);
+ public List sortMembers(List list);
+ }
+
+ private static final Collection additionalSorters = new ArrayList();
+
+ static {
+ additionalSorters.add(new AssociatedStreetSorter());
+ }
+
+ /**
+ * Class that sorts type=associatedStreet relation's houses.
+ */
+ private static class AssociatedStreetSorter implements AdditionalSorter {
+
+ @Override
+ public boolean acceptsMember(RelationMember m) {
+ return m != null
+ && m.getRole() != null && m.getRole().equals("house")
+ && m.getMember() != null && m.getMember().get("addr:housenumber") != null;
+ }
+
+ @Override
+ public List sortMembers(List list) {
+ Collections.sort(list, new Comparator() {
+ @Override
+ public int compare(RelationMember a, RelationMember b) {
+ if (a == b || a.getMember() == b.getMember()) return 0;
+ String addrA = a.getMember().get("addr:housenumber").trim();
+ String addrB = b.getMember().get("addr:housenumber").trim();
+ if (addrA.equals(addrB)) return 0;
+ // Strip non-digits (from "1B" addresses for example)
+ String addrAnum = addrA.replaceAll("\\D+", "");
+ String addrBnum = addrB.replaceAll("\\D+", "");
+ // Compare only numbers
+ try {
+ Integer res = Integer.parseInt(addrAnum) - Integer.parseInt(addrBnum);
+ if (res != 0) return res;
+ } catch (NumberFormatException e) {
+ // Ignore NumberFormatException. If the number is not composed of digits, strings are compared next
+ }
+ // Same number ? Compare full strings
+ return addrA.compareTo(addrB);
+ }
+ });
+ return list;
+ }
+ }
+
+ /*
+ * Sort a collection of relation members by the way they are linked.
+ *
+ * @param relationMembers collection of relation members
+ * @return sorted collection of relation members
+ */
+ public List sortMembers(List relationMembers) {
+ ArrayList newMembers = new ArrayList();
+
+ // Sort members with custom mechanisms (relation-dependent)
+ List defaultMembers = new ArrayList(relationMembers.size());
+ Map> customMap = new HashMap>();
+
+ // Dispatch members to correct sorters
+ for (RelationMember m : relationMembers) {
+ for (AdditionalSorter sorter : additionalSorters) {
+ List list = defaultMembers;
+ if (sorter.acceptsMember(m)) {
+ list = customMap.get(sorter);
+ if (list == null) {
+ customMap.put(sorter, list = new LinkedList());
+ }
+ }
+ list.add(m);
+ }
+ }
+
+ // Sort members and add them to result
+ for (AdditionalSorter s : customMap.keySet()) {
+ newMembers.addAll(s.sortMembers(customMap.get(s)));
+ }
+
+ RelationNodeMap map = new RelationNodeMap(defaultMembers);
+ // List of groups of linked members
+ //
+ List> allGroups = new ArrayList>();
+
+ // current group of members that are linked among each other
+ // Two successive members are always linked i.e. have a common node.
+ //
+ LinkedList group;
+
+ Integer first;
+ while ((first = map.pop()) != null) {
+ group = new LinkedList();
+ 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);
+ }
+ }
+
+ for (LinkedList tmpGroup : allGroups) {
+ for (Integer p : tmpGroup) {
+ newMembers.add(defaultMembers.get(p));
+ }
+ }
+
+ // Finally, add members that have not been sorted at all
+ for (Integer i : map.getNotSortableMembers()) {
+ newMembers.add(defaultMembers.get(i));
+ }
+
+ return newMembers;
+ }
+
+}
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionType.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionType.java (revision 5630)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionType.java (revision 5630)
@@ -0,0 +1,87 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.gui.dialogs.relation.sort;
+
+import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.NONE;
+import static org.openstreetmap.josm.tools.I18n.tr;
+
+public class WayConnectionType {
+
+ /** True, if the corresponding primitive is not a way or the way is incomplete */
+ private final boolean invalid;
+
+ /** True, if linked to the previous / next member. */
+ public boolean linkPrev;
+ public boolean linkNext;
+
+ /**
+ * direction is FORWARD if the first node of this way is connected to the previous way
+ * and / or the last node of this way is connected to the next way.
+ * direction is BACKWARD if it is the other way around.
+ * direction has a ROUNDABOUT value, if it is tagged as such and it is somehow
+ * connected to the previous / next member.
+ * If there is no connection to the previous or next member, then
+ * direction has the value NONE.
+ */
+ public Direction direction;
+
+ public enum Direction {
+ FORWARD, BACKWARD, ROUNDABOUT_LEFT, ROUNDABOUT_RIGHT, NONE;
+
+ public boolean isRoundabout() {
+ return this == ROUNDABOUT_RIGHT || this == ROUNDABOUT_LEFT;
+ }
+ }
+
+ /** True, if the element is part of a closed loop of ways. */
+ public boolean isLoop;
+
+ public boolean isOnewayLoopForwardPart = false;
+ public boolean isOnewayLoopBackwardPart = false;
+ public boolean isOnewayHead = false;
+ public boolean isOnewayTail = false;
+
+ public WayConnectionType(boolean linkPrev, boolean linkNext, Direction direction) {
+ this.linkPrev = linkPrev;
+ this.linkNext = linkNext;
+ this.isLoop = false;
+ this.direction = direction;
+ invalid = false;
+ }
+
+ public WayConnectionType(boolean invalid){
+ this.invalid = invalid;
+ }
+
+ /** construct invalid instance */
+ public WayConnectionType() {
+ this.linkPrev = false;
+ this.linkNext = false;
+ this.isLoop = false;
+ this.direction = NONE;
+ invalid = true;
+ }
+
+ public boolean isValid() {
+ return !invalid;
+ }
+
+ @Override
+ public String toString() {
+ return "[P "+linkPrev+" ;N "+linkNext+" ;D "+direction+" ;L "+isLoop+
+ " ;FP " + isOnewayLoopForwardPart+";BP " + isOnewayLoopBackwardPart+
+ ";OH " + isOnewayHead+";OT " + isOnewayTail+"]";
+ }
+
+ public String getToolTip() {
+ if (!isValid())
+ return "";
+ else if (linkPrev && linkNext)
+ return tr("way is connected");
+ else if (linkPrev)
+ return tr("way is connected to previous relation member");
+ else if (linkNext)
+ return tr("way is connected to next relation member");
+ else
+ return tr("way is not connected to previous or next relation member");
+ }
+}
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculator.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculator.java (revision 5630)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculator.java (revision 5630)
@@ -0,0 +1,301 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.gui.dialogs.relation.sort;
+
+import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.BACKWARD;
+import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.FORWARD;
+import static org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction.NONE;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import org.openstreetmap.josm.data.osm.Node;
+import org.openstreetmap.josm.data.osm.RelationMember;
+import org.openstreetmap.josm.data.osm.Way;
+import org.openstreetmap.josm.gui.dialogs.relation.sort.WayConnectionType.Direction;
+
+public class WayConnectionTypeCalculator {
+
+ private final int UNCONNECTED = Integer.MIN_VALUE;
+
+ private List members;
+
+ /**
+ * refresh the cache of member WayConnectionTypes
+ */
+ public List updateLinks(List members) {
+ this.members = members;
+ final List con = new ArrayList();
+
+ for (int i=0; i 0) {
+ makeLoopIfNeeded(con, i-1);
+ }
+ con.set(i, new WayConnectionType());
+ firstGroupIdx = i;
+ continue;
+ }
+
+ WayConnectionType wct = new WayConnectionType(false);
+ wct.linkPrev = i>0 && con.get(i-1) != null && con.get(i-1).isValid();
+ wct.direction = NONE;
+
+ if(RelationSortUtils.isOneway(m)){
+ if(lastWct != null && lastWct.isOnewayTail) {
+ wct.isOnewayHead = true;
+ }
+ if(lastBackwardWay == UNCONNECTED && lastForwardWay == UNCONNECTED){ //Beginning of new oneway
+ wct.isOnewayHead = true;
+ lastForwardWay = i-1;
+ lastBackwardWay = i-1;
+ onewayBeginning = true;
+ }
+ }
+
+ if (wct.linkPrev) {
+ if(lastBackwardWay != UNCONNECTED && lastForwardWay != UNCONNECTED) {
+ wct = determineOnewayConnectionType(con, m, i, wct);
+ if(!wct.linkPrev) {
+ firstGroupIdx = i;
+ }
+ }
+
+ if(!RelationSortUtils.isOneway(m)) {
+ wct.direction = determineDirection(i-1, lastWct.direction, i);
+ wct.linkPrev = (wct.direction != NONE);
+ }
+ }
+
+ if (!wct.linkPrev) {
+ wct.direction = determineDirectionOfFirst(i, m);
+ if(RelationSortUtils.isOneway(m)){
+ wct.isOnewayLoopForwardPart = true;
+ lastForwardWay = i;
+ }
+ }
+
+ wct.linkNext = false;
+ if(lastWct != null) {
+ lastWct.linkNext = wct.linkPrev;
+ }
+ con.set(i, wct);
+ lastWct = wct;
+
+ if(!wct.linkPrev) {
+ if(i > 0) {
+ makeLoopIfNeeded(con, i-1);
+ }
+ firstGroupIdx = i;
+ }
+ }
+ makeLoopIfNeeded(con, members.size()-1);
+
+ return con;
+ }
+
+ int firstGroupIdx;
+ private void makeLoopIfNeeded(final List con, final int i) {
+ boolean loop;
+ if (i == firstGroupIdx) { //is primitive loop
+ loop = determineDirection(i, FORWARD, i) == FORWARD;
+ } else {
+ loop = determineDirection(i, con.get(i).direction, firstGroupIdx) == con.get(firstGroupIdx).direction;
+ }
+ if (loop) {
+ for (int j=firstGroupIdx; j <= i; ++j) {
+ con.get(j).isLoop = true;
+ }
+ }
+ }
+
+ private Direction determineDirectionOfFirst(final int i, final RelationMember m) {
+ Direction result = RelationSortUtils.roundaboutType(m);
+ if (result != NONE)
+ return result;
+
+ if (RelationSortUtils.isOneway(m)){
+ if(RelationSortUtils.isBackward(m)) return BACKWARD;
+ else return FORWARD;
+ } else { /** guess the direction and see if it fits with the next member */
+ if(determineDirection(i, FORWARD, i+1) != NONE) return FORWARD;
+ if(determineDirection(i, BACKWARD, i+1) != NONE) return BACKWARD;
+ }
+ return NONE;
+ }
+
+ int lastForwardWay, lastBackwardWay;
+ boolean onewayBeginning;
+ private WayConnectionType determineOnewayConnectionType(final List con,
+ RelationMember m, int i, final WayConnectionType wct) {
+ Direction dirFW = determineDirection(lastForwardWay, con.get(lastForwardWay).direction, i);
+ Direction dirBW = NONE;
+ if(onewayBeginning) {
+ if(lastBackwardWay < 0) {
+ dirBW = determineDirection(firstGroupIdx, reverse(con.get(firstGroupIdx).direction), i, true);
+ } else {
+ dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
+ }
+
+ if(dirBW != NONE) {
+ onewayBeginning = false;
+ }
+ } else {
+ dirBW = determineDirection(lastBackwardWay, con.get(lastBackwardWay).direction, i, true);
+ }
+
+ if(RelationSortUtils.isOneway(m)) {
+ if(dirBW != NONE){
+ wct.direction = dirBW;
+ lastBackwardWay = i;
+ wct.isOnewayLoopBackwardPart = true;
+ }
+ if(dirFW != NONE){
+ wct.direction = dirFW;
+ lastForwardWay = i;
+ wct.isOnewayLoopForwardPart = true;
+ }
+ if(dirFW == NONE && dirBW == NONE) { //Not connected to previous
+ // unconnectPreviousLink(con, i, true);
+ // unconnectPreviousLink(con, i, false);
+ wct.linkPrev = false;
+ if(RelationSortUtils.isOneway(m)){
+ wct.isOnewayHead = true;
+ lastForwardWay = i-1;
+ lastBackwardWay = i-1;
+ } else {
+ lastForwardWay = UNCONNECTED;
+ lastBackwardWay = UNCONNECTED;
+ }
+ onewayBeginning = true;
+ }
+
+ if(dirFW != NONE && dirBW != NONE) { //End of oneway loop
+ if(i+1= members.size() || k >= members.size())
+ return NONE;
+ if (ref_direction == NONE)
+ return NONE;
+
+ final RelationMember m_ref = members.get(ref_i);
+ final RelationMember m = members.get(k);
+ Way way_ref = null;
+ Way way = null;
+
+ if (m_ref.isWay()) {
+ way_ref = m_ref.getWay();
+ }
+ if (m.isWay()) {
+ way = m.getWay();
+ }
+
+ if (way_ref == null || way == null)
+ return NONE;
+
+ /** the list of nodes the way k can dock to */
+ List refNodes= new ArrayList();
+
+ switch (ref_direction) {
+ case FORWARD:
+ refNodes.add(way_ref.lastNode());
+ break;
+ case BACKWARD:
+ refNodes.add(way_ref.firstNode());
+ break;
+ case ROUNDABOUT_LEFT:
+ case ROUNDABOUT_RIGHT:
+ refNodes = way_ref.getNodes();
+ break;
+ }
+
+ if (refNodes == null)
+ return NONE;
+
+ for (Node n : refNodes) {
+ if (n == null) {
+ continue;
+ }
+ if (RelationSortUtils.roundaboutType(members.get(k)) != NONE) {
+ for (Node nn : way.getNodes()) {
+ if (n == nn)
+ return RelationSortUtils.roundaboutType(members.get(k));
+ }
+ } else if(RelationSortUtils.isOneway(m)) {
+ if (n == RelationNodeMap.firstOnewayNode(m) && !reversed) {
+ if(RelationSortUtils.isBackward(m))
+ return BACKWARD;
+ else
+ return FORWARD;
+ }
+ if (n == RelationNodeMap.lastOnewayNode(m) && reversed) {
+ if(RelationSortUtils.isBackward(m))
+ return FORWARD;
+ else
+ return BACKWARD;
+ }
+ } else {
+ if (n == way.firstNode())
+ return FORWARD;
+ if (n == way.lastNode())
+ return BACKWARD;
+ }
+ }
+ return NONE;
+ }
+
+}
Index: /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSorterTest.java
===================================================================
--- /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSorterTest.java (revision 5630)
+++ /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSorterTest.java (revision 5630)
@@ -0,0 +1,61 @@
+// License: GPL. For details, see LICENSE file.
+package org.openstreetmap.josm.gui.dialogs.relation.sort;
+
+import java.io.FileInputStream;
+import java.io.FileNotFoundException;
+import java.util.List;
+
+import org.junit.Assert;
+import org.junit.BeforeClass;
+import org.junit.Test;
+import org.openstreetmap.josm.Main;
+import org.openstreetmap.josm.data.Preferences;
+import org.openstreetmap.josm.data.osm.DataSet;
+import org.openstreetmap.josm.data.osm.Relation;
+import org.openstreetmap.josm.data.osm.RelationMember;
+import org.openstreetmap.josm.data.projection.Projections;
+import org.openstreetmap.josm.gui.progress.NullProgressMonitor;
+import org.openstreetmap.josm.io.IllegalDataException;
+import org.openstreetmap.josm.io.OsmReader;
+
+public class RelationSorterTest {
+
+ private RelationSorter sorter = new RelationSorter();
+ private static DataSet testDataset;
+
+ @BeforeClass
+ public static void loadData() throws FileNotFoundException, IllegalDataException {
+ Main.pref = new Preferences();
+ Main.setProjection(Projections.getProjectionByCode("EPSG:3857")); // Mercator
+ testDataset = OsmReader.parseDataSet(new FileInputStream("data_nodist/relation_sort.osm"), NullProgressMonitor.INSTANCE);
+ }
+
+ private Relation getRelation(String testType) {
+ for (Relation r: testDataset.getRelations()) {
+ if (testType.equals(r.get("test")))
+ return r;
+ }
+ return null;
+ }
+
+ private String[] getNames(List members) {
+ String[] result = new String[members.size()];
+ for (int i=0; i connections) {
+ String[] result = new String[connections.size()];
+ for (int i=0; i 0) {
+ sb.append(" ");
+ }
+ sb.append(wc.direction);
+ result[i] = sb.toString();
+
+ } else {
+ result[i] = "I";
+ }
+
+ }
+ return Arrays.toString(result);
+ }
+
+ @Test
+ public void testGeneric() {
+ Relation relation = getRelation("generic");
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(relation.getMembers()));
+ Assert.assertEquals("[NONE, NONE, FORWARD, FORWARD, NONE, NONE, NONE, I, I]", actual);
+ actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ Assert.assertEquals("[BACKWARD, BACKWARD, BACKWARD, BACKWARD, BACKWARD, BACKWARD, NONE, I, I]", actual);
+ }
+
+ @Test
+ public void testAssociatedStreet() {
+ Relation relation = getRelation("associatedStreet");
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(relation.getMembers()));
+ Assert.assertEquals("[FORWARD, FORWARD, I, I, I, I]" , actual);
+ actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ Assert.assertEquals("[I, I, I, I, FORWARD, FORWARD]", actual);
+ }
+
+ @Test
+ public void testLoop() {
+ Relation relation = getRelation("loop");
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(relation.getMembers()));
+ Assert.assertEquals("[FPH FORWARD, FP FORWARD, NONE, FPH FORWARD, NONE, FPH FORWARD, NONE]", actual);
+ //TODO Sorting doesn't work well in this case
+ actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ Assert.assertEquals("[BACKWARD, BACKWARD, BACKWARD, FPH FORWARD, FPH FORWARD, FPH FORWARD, FPH FORWARD]", actual);
+ }
+
+
+}