Changeset 15574 in josm for trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java

Timestamp:

2019-12-09T09:47:20+01:00 (4 years ago)

Author:

GerdP

Message:

fix #18367 and #18385: CombineWayAction (C) refuses to combine ways or silently reverses ways
Changes:

• try first to combine the ways with the method Multipolygon.joinWays() If that method returns a single line string we can use it, else use the result of NodeGraph.buildSpanningPathNoRemove(). Both methods will not add or remove segments
• if ways are combined execute checks for overlapping segments or self-intersection and show a notification popup right after the command was added to the UndoRedoHandler
• The code which handles reversed ways needed changes. In the unpatched version it sometimes claims wrongly that ways were reversed, in special cases it sometimes silently reverted ways. The old code did not handle the case properly that a node can appear more than once. I really hope that I got it right now.
• Fix some sonarlint issues
• let NodeGraph routines return an ArrayList instead of a LinkedList (improves performance a bit)
• Add unit tests

File:

• trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java (modified) (5 diffs)

trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java

@@ -12 +12 @@
 import java.util.LinkedHashMap;
 import java.util.LinkedHashSet;
-import java.util.LinkedList;
 import java.util.List;
 import java.util.Map;
@@ -18 +17 @@
 import java.util.Optional;
 import java.util.Set;
-import java.util.Stack;
 import java.util.TreeMap;
 
@@ -249 +247 @@
     }
 
-    protected List<Node> buildPathFromNodePairs(Stack<NodePair> path) {
-        List<Node> ret = new LinkedList<>();
-        for (NodePair pair: path) {
+    protected List<Node> buildPathFromNodePairs(Deque<NodePair> path) {
+        List<Node> ret = new ArrayList<>(path.size() + 1);
+        for (NodePair pair : path) {
             ret.add(pair.getA());
         }
-        ret.add(path.peek().getB());
+        ret.add(path.peekLast().getB());
         return ret;
     }
@@ -264 +262 @@
      *
      * @param startNode the start node
-     * @return the spanning path; null, if no path is found
+     * @return the spanning path; empty list if no path is found
      */
     protected List<Node> buildSpanningPath(Node startNode) {
         if (startNode != null) {
-            // do not simply replace `Stack` by `ArrayDeque` because of different iteration behaviour, see #11957
-            Stack<NodePair> path = new Stack<>();
+            Deque<NodePair> path = new ArrayDeque<>();
             Set<NodePair> dupCheck = new HashSet<>();
-            Stack<NodePair> nextPairs = new Stack<>();
+            Deque<NodePair> nextPairs = new ArrayDeque<>();
             nextPairs.addAll(getOutboundPairs(startNode));
             while (!nextPairs.isEmpty()) {
-                NodePair cur = nextPairs.pop();
+                NodePair cur = nextPairs.removeLast();
                 if (!dupCheck.contains(cur) && !dupCheck.contains(cur.swap())) {
-                    while (!path.isEmpty() && !path.peek().isPredecessorOf(cur)) {
-                        dupCheck.remove(path.pop());
+                    while (!path.isEmpty() && !path.peekLast().isPredecessorOf(cur)) {
+                        dupCheck.remove(path.removeLast());
                     }
-                    path.push(cur);
+                    path.addLast(cur);
                     dupCheck.add(cur);
-                    if (isSpanningWay(path)) return buildPathFromNodePairs(path);
-                    nextPairs.addAll(getOutboundPairs(path.peek()));
+                    if (isSpanningWay(path))
+                        return buildPathFromNodePairs(path);
+                    nextPairs.addAll(getOutboundPairs(path.peekLast()));
                 }
             }
@@ -324 +322 @@
      * any duplicated edge was removed.
      *
-     * @return the path; null, if no path was found or duplicated edges were found
-     * @since 15555
+     * @return List of nodes that build the path; an empty list if no path or duplicated edges were found
+     * @since 15573 (return value not null)
      */
     public List<Node> buildSpanningPathNoRemove() {
-        if (edges.size() != addedEdges)
-            return null;
-        return buildSpanningPath();
+        List<Node> path = null;
+        if (edges.size() == addedEdges)
+            path = buildSpanningPath();
+        return path == null ? Collections.emptyList() : path;
     }