Index: /trunk/nodist/data/relation_sort.osm
===================================================================
--- /trunk/nodist/data/relation_sort.osm (revision 16885)
+++ /trunk/nodist/data/relation_sort.osm (revision 16886)
@@ -63,4 +63,33 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
@@ -188,4 +217,146 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
@@ -198,4 +369,5 @@
+
@@ -209,4 +381,5 @@
+
@@ -221,4 +394,5 @@
+
@@ -230,4 +404,5 @@
+
@@ -241,5 +416,144 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationNodeMap.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationNodeMap.java (revision 16885)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationNodeMap.java (revision 16886)
@@ -177,17 +177,20 @@
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;
- }
+ Node exitNode = onewayMap.ways.get(way).iterator().next();
+
+ if (checkIfEndOfLoopReached(exitNode)) {
+ lastOnewayNode = exitNode;
+ return popBackwardOnewayPart(firstOneway);
+ }
+
+ Integer i = deleteAndGetAdjacentNode(onewayMap, exitNode);
+ if (i != null) return i;
+
+ // When our forward route ends in a dead end try to start
+ // the backward route anyway from the split point
+ // (firstOneWay), to support routes with split a split start
+ // or end.
+ lastOnewayNode = exitNode;
+ return popBackwardOnewayPart(firstOneway);
}
@@ -196,15 +199,14 @@
}
- 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;
+ // Check if the given node can be the end of the loop (i.e. it has
+ // an outgoing bidirectional or multiple outgoing oneways, or we
+ // looped back to our first circular node)
+ private boolean checkIfEndOfLoopReached(Node n) {
+ if (map.nodes.containsKey(n)
+ || (onewayMap.nodes.containsKey(n) && onewayMap.nodes.get(n).size() > 1))
+ return true;
+ if (firstCircular != null && firstCircular == n)
+ return true;
+ return false;
}
@@ -267,6 +269,9 @@
} else {
done(way);
- }
- nw.ways.get(way).remove(n);
+ // For bidirectional ways, remove the entry node, so
+ // subsequent lookups will only return the other node(s) as
+ // valid exit nodes.
+ nw.ways.get(way).remove(n);
+ }
}
Index: /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculator.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculator.java (revision 16885)
+++ /trunk/src/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculator.java (revision 16886)
@@ -146,5 +146,5 @@
if (!wct.linkPrev) {
- wct.direction = determineDirectionOfFirst(i, m);
+ wct.direction = determineDirectionOfFirst(i, m, false);
if (RelationSortUtils.isOneway(m)) {
wct.isOnewayLoopForwardPart = true;
@@ -218,5 +218,5 @@
}
- private Direction determineDirectionOfFirst(final int i, final RelationMember m) {
+ private Direction determineDirectionOfFirst(final int i, final RelationMember m, boolean reversed) {
Direction result = RelationSortUtils.roundaboutType(m);
if (result != NONE)
@@ -224,5 +224,5 @@
if (RelationSortUtils.isOneway(m)) {
- if (RelationSortUtils.isBackward(m)) return BACKWARD;
+ if (RelationSortUtils.isBackward(m) != reversed) return BACKWARD;
else return FORWARD;
} else { /** guess the direction and see if it fits with the next member */
@@ -248,4 +248,27 @@
}
+ // Support split-start routes. When the current way does
+ // not fit as forward or backward and we have no backward
+ // ways yet (onewayBeginning) and the most recent oneway
+ // head starts a new segment (!linkPrev), instead of
+ // disconnecting the current way, make it the start of the
+ // backward route. To render properly, unset isOnewayHead on
+ // the most recent head (since the current backward way does
+ // no longer start there).
+ if (dirFW == NONE && dirBW == NONE && RelationSortUtils.isOneway(m) && !wct.isOnewayHead) {
+ WayConnectionType prevHead = null;
+ for (int j = i - 1; j >= 0; --j) {
+ if (con.get(j).isOnewayHead) {
+ prevHead = con.get(j);
+ break;
+ }
+ }
+
+ if (prevHead != null && !prevHead.linkPrev) {
+ dirBW = determineDirectionOfFirst(i, m, true);
+ prevHead.isOnewayHead = false;
+ }
+ }
+
if (dirBW != NONE) {
onewayBeginning = false;
@@ -269,12 +292,7 @@
if (dirFW == NONE && dirBW == NONE) {
wct.linkPrev = false;
- if (RelationSortUtils.isOneway(m)) {
- wct.isOnewayHead = true;
- lastForwardWay = i-1;
- lastBackwardWay = i-1;
- } else {
- lastForwardWay = UNCONNECTED;
- lastBackwardWay = UNCONNECTED;
- }
+ wct.isOnewayHead = true;
+ lastForwardWay = i-1;
+ lastBackwardWay = i-1;
onewayBeginning = true;
}
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 16885)
+++ /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/relation/sort/RelationSorterTest.java (revision 16886)
@@ -59,4 +59,8 @@
}
+ // This cluster of tests checks whether these relations are sorted
+ // as expected, so these relations are of course not sorted in the
+ // data file.
+
@Test
public void testGeneric() {
@@ -79,3 +83,101 @@
Assert.assertArrayEquals(new String[]{"t2w1", "t2w2", "t2n1", "t2n2", "t2n3", "t2n4", "playground", "tree"}, actual);
}
+
+ // The following cluster of tests does the same, but with various
+ // configurations involving split / dual carriageway routes (i.e.
+ // containing members with role=forward or role=backward). Again,
+ // these are intentionally not already sorted.
+
+ @Test
+ public void testThreeLoopsEndsLoop() {
+ Relation relation = getRelation("three-loops-ends-loop");
+ // Check the first way before sorting, otherwise the sorter
+ // might pick a different loop starting point than expected below
+ Assert.assertEquals("t5w1", relation.getMembers().get(0).getMember().get("name"));
+
+ String[] actual = getNames(sorter.sortMembers(relation.getMembers()));
+ Assert.assertArrayEquals(new String[]{
+ "t5w1", "t5w2a", "t5w3a", "t5w4a", "t5w2b", "t5w3b", "t5w4b",
+ "t5w5", "t5w6a", "t5w7a", "t5w8a", "t5w6b", "t5w7b", "t5w8b",
+ "t5w9a", "t5w10a", "t5w11a", "t5w9b", "t5w10b", "t5w11b",
+ "t5w12", "t5w13",
+ }, actual);
+ }
+
+ @Test
+ public void testThreeLoopsEndsWay() {
+ Relation relation = getRelation("three-loops-ends-way");
+ // Check the first way before sorting, otherwise the sorter
+ // might sort in reverse compared to what is expected below
+ Assert.assertEquals("t5w1", relation.getMembers().get(0).getMember().get("name"));
+
+ String[] actual = getNames(sorter.sortMembers(relation.getMembers()));
+ Assert.assertArrayEquals(new String[]{
+ "t5w1", "t5w2a", "t5w3a", "t5w4a", "t5w2b", "t5w3b", "t5w4b",
+ "t5w5", "t5w6a", "t5w7a", "t5w8a", "t5w6b", "t5w7b", "t5w8b",
+ "t5w9a", "t5w10a", "t5w11a", "t5w9b", "t5w10b", "t5w11b",
+ "t5w12",
+ }, actual);
+ }
+
+ @Test
+ public void testThreeLoopsEndsNode() {
+ Relation relation = getRelation("three-loops-ends-node");
+ String[] actual = getNames(sorter.sortMembers(relation.getMembers()));
+ Assert.assertArrayEquals(new String[]{
+ "t5w4a", "t5w3a", "t5w2a", "t5w2b", "t5w3b", "t5w4b",
+ "t5w5", "t5w6a", "t5w7a", "t5w8a", "t5w6b", "t5w7b", "t5w8b",
+ "t5w9a", "t5w10a", "t5w11a", "t5w11b", "t5w10b", "t5w9b",
+ }, actual);
+ }
+
+ @Test
+ public void testOneLoopEndsSplit() {
+ Relation relation = getRelation("one-loop-ends-split");
+ String[] actual = getNames(sorter.sortMembers(relation.getMembers()));
+ Assert.assertArrayEquals(new String[]{
+ "t5w3a", "t5w4a", "t5w3b", "t5w4b",
+ "t5w5", "t5w6a", "t5w7a", "t5w8a", "t5w6b", "t5w7b", "t5w8b",
+ "t5w9a", "t5w10a", "t5w9b", "t5w10b",
+ }, actual);
+ }
+
+ @Test
+ public void testNoLoopEndsSplit() {
+ Relation relation = getRelation("no-loop-ends-split");
+ // TODO: This is not yet sorted properly, so this route is
+ // presorted in the data file, making this a bit of a dummy test
+ // for now.
+ String[] actual = getNames(relation.getMembers());
+ Assert.assertArrayEquals(new String[]{
+ "t5w7a", "t5w8a", "t5w7b", "t5w8b",
+ "t5w9a", "t5w10a", "t5w9b", "t5w10b",
+ }, actual);
+ }
+
+ @Test
+ public void testIncompleteLoops() {
+ Relation relation = getRelation("incomplete-loops");
+ // TODO: This is not yet sorted perfectly (might not be possible)
+ String[] actual = getNames(sorter.sortMembers(relation.getMembers()));
+ Assert.assertArrayEquals(new String[]{
+ "t5w1", "t5w2a", "t5w3a", "t5w4a", "t5w2b", "t5w3b",
+ "t5w5", "t5w6a", "t5w7a", "t5w8a", "t5w9a", "t5w10a", "t5w11a", "t5w6b", "t5w7b",
+ "t5w12", "t5w11b", "t5w10b", "t5w9b",
+ }, actual);
+ }
+
+ @Test
+ public void testParallelOneWay() {
+ Relation relation = getRelation("parallel-oneway");
+ // TODO: This is not always sorted properly, only when the right
+ // way is already at the top, so check that
+ Assert.assertEquals("t6w1a", relation.getMembers().get(0).getMember().get("name"));
+
+ String[] actual = getNames(sorter.sortMembers(relation.getMembers()));
+ Assert.assertArrayEquals(new String[]{
+ "t6w1a", "t6w2a", "t6w3a",
+ "t6w1b", "t6w2b", "t6w3b",
+ }, actual);
+ }
}
Index: /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculatorTest.java
===================================================================
--- /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculatorTest.java (revision 16885)
+++ /trunk/test/unit/org/openstreetmap/josm/gui/dialogs/relation/sort/WayConnectionTypeCalculatorTest.java (revision 16886)
@@ -105,4 +105,8 @@
}
+ // This cluster of tests checks the rendering before and after
+ // sorting of a few relations. Initially, these relations are
+ // intentionally not sorted to ensure the sorting has some work.
+
@Test
public void testGeneric() {
@@ -130,5 +134,105 @@
//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);
+ Assert.assertEquals("[BACKWARD, BACKWARD, BACKWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, BPT BACKWARD]", actual);
+ }
+
+ // The following cluster of tests checks various configurations
+ // involving split / dual carriageway routes (i.e. containing
+ // members with role=forward or role=backward). Again, these are
+ // intentionally not sorted.
+
+ @Test
+ public void testThreeLoopsEndsLoop() {
+ Relation relation = getRelation("three-loops-ends-loop");
+ // Check the first way before sorting, otherwise the sorter
+ // might pick a different loop starting point than expected below
+ Assert.assertEquals("t5w1", relation.getMembers().get(0).getMember().get("name"));
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ String expected = "[" +
+ "L FORWARD, LFPH FORWARD, LFP FORWARD, LFP FORWARD, LBP BACKWARD, LBP BACKWARD, LBPT BACKWARD, " +
+ "L FORWARD, LFPH FORWARD, LFP FORWARD, LFP FORWARD, LBP BACKWARD, LBP BACKWARD, LBPT BACKWARD, " +
+ "LFPH FORWARD, LFP FORWARD, LFP FORWARD, LBP BACKWARD, LBP BACKWARD, LBPT BACKWARD, " +
+ "L FORWARD, L FORWARD" +
+ "]";
+ Assert.assertEquals(expected, actual);
+ }
+
+ @Test
+ public void testThreeLoopsEndsWay() {
+ Relation relation = getRelation("three-loops-ends-way");
+ // Check the first way before sorting, otherwise the sorter
+ // might sort in reverse compared to what is expected below
+ Assert.assertEquals("t5w1", relation.getMembers().get(0).getMember().get("name"));
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ String expected = "[" +
+ "FORWARD, FPH FORWARD, FP FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, BPT BACKWARD, " +
+ "FORWARD, FPH FORWARD, FP FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, BPT BACKWARD, " +
+ "FPH FORWARD, FP FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, BPT BACKWARD, " +
+ "FORWARD" +
+ "]";
+ Assert.assertEquals(expected, actual);
+ }
+
+ @Test
+ public void testThreeLoopsEndsNode() {
+ Relation relation = getRelation("three-loops-ends-node");
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ String expected = "[" +
+ "FPH FORWARD, BP BACKWARD, BP BACKWARD, BP BACKWARD, BP BACKWARD, BPT BACKWARD, " +
+ "FORWARD, FPH FORWARD, FP FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, BPT BACKWARD, " +
+ "FPH FORWARD, FP FORWARD, FP FORWARD, FP FORWARD, FP FORWARD, BPT BACKWARD" +
+ "]";
+ Assert.assertEquals(expected, actual);
+ }
+
+ @Test
+ public void testOneLoopEndsSplit() {
+ Relation relation = getRelation("one-loop-ends-split");
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ String expected = "[" +
+ "FP FORWARD, FP FORWARD, BP BACKWARD, BPT BACKWARD, " +
+ "FORWARD, FPH FORWARD, FP FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, BPT BACKWARD, " +
+ "FPH FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD" +
+ "]";
+ Assert.assertEquals(expected, actual);
+ }
+
+ @Test
+ public void testNoLoopEndsSplit() {
+ Relation relation = getRelation("no-loop-ends-split");
+ // TODO: This is not yet sorted properly, so this route is
+ // presorted in the data file
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(relation.getMembers()));
+ String expected = "[" +
+ "FP FORWARD, FP FORWARD, BP BACKWARD, BPT BACKWARD, " +
+ "FPH FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD" +
+ "]";
+ Assert.assertEquals(expected, actual);
+ }
+
+ @Test
+ public void testIncompleteLoops() {
+ Relation relation = getRelation("incomplete-loops");
+ // TODO: This is not yet sorted perfectly (might not be possible)
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ String expected = "[" +
+ "FORWARD, FPH FORWARD, FP FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, " +
+ "FORWARD, FPH FORWARD, FP FORWARD, FP FORWARD, FP FORWARD, FP FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, " +
+ "BACKWARD, FPH FORWARD, FP FORWARD, FP FORWARD" +
+ "]";
+ Assert.assertEquals(expected, actual);
+ }
+
+ @Test
+ public void testParallelOneWay() {
+ Relation relation = getRelation("parallel-oneway");
+ // TODO: This is not always sorted properly, only when the right
+ // way is already at the top, so check that
+ Assert.assertEquals("t6w1a", relation.getMembers().get(0).getMember().get("name"));
+ String actual = getConnections(wayConnectionTypeCalculator.updateLinks(sorter.sortMembers(relation.getMembers())));
+ String expected = "[" +
+ "FP FORWARD, FP FORWARD, FP FORWARD, BP BACKWARD, BP BACKWARD, BP BACKWARD" +
+ "]";
+ Assert.assertEquals(expected, actual);
}