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)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/src/org/openstreetmap/josm/data/osm/NodeGraph.java
r15559 r15574 12 12 import java.util.LinkedHashMap; 13 13 import java.util.LinkedHashSet; 14 import java.util.LinkedList;15 14 import java.util.List; 16 15 import java.util.Map; … … 18 17 import java.util.Optional; 19 18 import java.util.Set; 20 import java.util.Stack;21 19 import java.util.TreeMap; 22 20 … … 249 247 } 250 248 251 protected List<Node> buildPathFromNodePairs( Stack<NodePair> path) {252 List<Node> ret = new LinkedList<>();253 for (NodePair pair : path) {249 protected List<Node> buildPathFromNodePairs(Deque<NodePair> path) { 250 List<Node> ret = new ArrayList<>(path.size() + 1); 251 for (NodePair pair : path) { 254 252 ret.add(pair.getA()); 255 253 } 256 ret.add(path.peek ().getB());254 ret.add(path.peekLast().getB()); 257 255 return ret; 258 256 } … … 264 262 * 265 263 * @param startNode the start node 266 * @return the spanning path; null,if no path is found264 * @return the spanning path; empty list if no path is found 267 265 */ 268 266 protected List<Node> buildSpanningPath(Node startNode) { 269 267 if (startNode != null) { 270 // do not simply replace `Stack` by `ArrayDeque` because of different iteration behaviour, see #11957 271 Stack<NodePair> path = new Stack<>(); 268 Deque<NodePair> path = new ArrayDeque<>(); 272 269 Set<NodePair> dupCheck = new HashSet<>(); 273 Stack<NodePair> nextPairs = new Stack<>();270 Deque<NodePair> nextPairs = new ArrayDeque<>(); 274 271 nextPairs.addAll(getOutboundPairs(startNode)); 275 272 while (!nextPairs.isEmpty()) { 276 NodePair cur = nextPairs. pop();273 NodePair cur = nextPairs.removeLast(); 277 274 if (!dupCheck.contains(cur) && !dupCheck.contains(cur.swap())) { 278 while (!path.isEmpty() && !path.peek ().isPredecessorOf(cur)) {279 dupCheck.remove(path. pop());275 while (!path.isEmpty() && !path.peekLast().isPredecessorOf(cur)) { 276 dupCheck.remove(path.removeLast()); 280 277 } 281 path. push(cur);278 path.addLast(cur); 282 279 dupCheck.add(cur); 283 if (isSpanningWay(path)) return buildPathFromNodePairs(path); 284 nextPairs.addAll(getOutboundPairs(path.peek())); 280 if (isSpanningWay(path)) 281 return buildPathFromNodePairs(path); 282 nextPairs.addAll(getOutboundPairs(path.peekLast())); 285 283 } 286 284 } … … 324 322 * any duplicated edge was removed. 325 323 * 326 * @return the path; null, if no path was foundor duplicated edges were found327 * @since 155 55324 * @return List of nodes that build the path; an empty list if no path or duplicated edges were found 325 * @since 15573 (return value not null) 328 326 */ 329 327 public List<Node> buildSpanningPathNoRemove() { 330 if (edges.size() != addedEdges) 331 return null; 332 return buildSpanningPath(); 328 List<Node> path = null; 329 if (edges.size() == addedEdges) 330 path = buildSpanningPath(); 331 return path == null ? Collections.emptyList() : path; 333 332 } 334 333
Note:
See TracChangeset
for help on using the changeset viewer.