[OSM-dev] [PATCH] JOSM - make reorder command work better.

[Robert Hart]

(reposted with patch inline - I think mailing list doesn't like attachments)

The patch below is a first attempt to fix problems with the reorder
tool in JOSM not acting as expected. With this patch the reorder tool
should work on a wider range of ways, particularly ways with loops at
the start and end, and should prefer the existing order when a way is
already sorted (I think). The behaviour with branched ways remains
undefined.

There are two parts to the fix:

1) Prefer to move forward from the end of the segment to the start of
the next. (specifically this prevents certain case where a correctly
ordered way would be scrambled by the reorder tool, by nipping the
wrong way down a loop but then continuing forward the correct way
around the loop.

2) Try and start from a segment that is likely to be at the start of the way.

The logic goes: For each of the nodes in the way count up how many
times it occurs as the start or end node of a segment in the way. Then
pick the first segment that has:
a) a start node used only once (i.e. most common ways)
b) a start node used an odd number of times (e.g. a way with a lollipop loop)
c) an end node used only once (e.g. a partially reversed way)
d) an end node used an odd number of times. (e.g. a partially reversed lollipop)
otherwise pick the first segment (e.g. closed loop)

Logically a non-branched way should contain either exactly two nodes
with odd reference counts or none.

This is related to trac#169, but not an entire fix yet as the reorder
logic is separate for tools that modify ways - I'll look into that
later.

 I don't write much java, so my perl mentality is probably shining
through a bit too much - feel free to complain and I'll try and
address any concerns.

Rob

Index: src/org/openstreetmap/josm/actions/ReorderAction.java
===================================================================
--- src/org/openstreetmap/josm/actions/ReorderAction.java	(revision 314)
+++ src/org/openstreetmap/josm/actions/ReorderAction.java	(working copy)
@@ -9,6 +9,7 @@
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.LinkedList;
+import java.util.HashMap;

 import javax.swing.JOptionPane;

@@ -172,28 +173,102 @@
 		
 		while (!segments.isEmpty()) {
 			LinkedList<Segment> pivotList = new LinkedList<Segment>();
-			pivotList.add(segments.getFirst());
-			segments.removeFirst();
+			pivotList.add(firstSegment(segments));
+			segments.remove(pivotList.getLast());
 			boolean found;
 			do {
 				found = false;
+				//try working forwards first
 				for (Iterator<Segment> it = segments.iterator(); it.hasNext();) {
 					Segment ls = it.next();
 					if (ls.incomplete)
 						continue; // incomplete segments are never added to a new way
-					if (ls.from == pivotList.getLast().to || (!strict && (ls.to ==
pivotList.getLast().to || ls.from == pivotList.getLast().from || ls.to
== pivotList.getLast().from))) {
+					if (ls.from == pivotList.getLast().to) {
 						pivotList.addLast(ls);
 						it.remove();
 						found = true;
+					}
+				}
+				if(!found){
+				    for (Iterator<Segment> it = segments.iterator(); it.hasNext();) {
+					Segment ls = it.next();
+					if (ls.incomplete)
+					    continue; // incomplete segments are never added to a new way
+					if (ls.from == pivotList.getLast().to || (!strict && (ls.to ==
pivotList.getLast().to || ls.from == pivotList.getLast().from || ls.to
== pivotList.getLast().from))) {
+					    pivotList.addLast(ls);
+					    it.remove();
+					    found = true;
 					} else if (ls.to == pivotList.getFirst().from || (!strict &&
(ls.from == pivotList.getFirst().from || ls.to ==
pivotList.getFirst().to || ls.from == pivotList.getFirst().to))) {
-						pivotList.addFirst(ls);
-						it.remove();
-						found = true;
+					    pivotList.addFirst(ls);
+					    it.remove();
+					    found = true;
 					}
+				    }
 				}
 			} while (found);
 			sortedSegments.addAll(pivotList);
 		}
 	    return sortedSegments;
 	}
+
+    /* This method searches for a good segment to start a reorder from.
+     * In most cases this will be a segment with a start node that occurs only
+     * once in the way. In cases with loops, this could be any odd
number. If no nodes
+     * are referenced an odd number of times, then any segment is a
good start point.
+     */
+	public static Segment firstSegment(LinkedList<Segment> segments) {
+	    HashMap refCount = new HashMap(segments.size()*2);
+	    //loop through all segments and count up how many times each
node is referenced
+	    for (Iterator<Segment> it = segments.iterator(); it.hasNext();) {
+		Segment seg = it.next();
+		int c;
+		Node node;
+
+		node = seg.from;
+		if(refCount.containsKey(node)){
+		    c = ((Integer)refCount.get(node)).intValue();
+		} else {
+		    c = 0;
+		}
+		refCount.put(node,new Integer(c+1));
+
+		node = seg.to;
+		if(refCount.containsKey(node)){
+		    c = ((Integer)refCount.get(node)).intValue();
+		} else {
+		    c = 0;
+		}
+		refCount.put(node,new Integer(c+1));
+	    }
+	    //now look for start nodes that are referenced only once
+	    for (Iterator<Segment> it = segments.iterator(); it.hasNext();) {
+		Segment seg = it.next();
+		int c;
+		c = ((Integer)refCount.get(seg.from)).intValue();
+		if(c==1) return seg;
+	    }
+	    //now look for start nodes that are referenced only (2n+1)
+	    for (Iterator<Segment> it = segments.iterator(); it.hasNext();) {
+		Segment seg = it.next();
+		int c;
+		c = ((Integer)refCount.get(seg.from)).intValue();
+		if((c%2)==1) return seg;
+	    }
+	    //now look for end nodes that are referenced only once
+	    for (Iterator<Segment> it = segments.iterator(); it.hasNext();) {
+		Segment seg = it.next();
+		int c;
+		c = ((Integer)refCount.get(seg.to)).intValue();
+		if(c==1) return seg;
+	    }
+	    //now look for end nodes that are referenced only (2n+1)
+	    for (Iterator<Segment> it = segments.iterator(); it.hasNext();) {
+		Segment seg = it.next();
+		int c;
+		c = ((Integer)refCount.get(seg.to)).intValue();
+		if((c%2)==1) return seg;
+	    }
+
+	    return segments.getFirst();
+	}
 }


-- 
-- 
Robert Hart