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: trunk/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: trunk/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; + } + +}