Repository: graphhopper/graphhopper
Pull request #1730 (2019-09-17 11:03:15)

Move path extraction logic out of `Path` class
This PR is supposed to move the path extraction stuff out of `Path`. So far `Path` was used by the routing algorithms to store some intermediate state (`SPTEntry`, `switchToFrom`, etc.) that later was used to 'extract' the `Path`. So basically some parts of the routing algorithm used to live inside `Path` and (because the extraction depends on the type of algorithm) the subclasses (`PathNative`, `Path4CH`, `PathBidirRef`, `EdgeBasedPath4CH`). However, since `Path` is the return type of the `RoutingAlgorithm` interface it should really be a data-only class IMO.

Here I basically did the following:

- Added dedicated classes for path extraction: `PathExtractor`, `BidirPathExtractor`, `Node/EdgeBasedCHBidirPathExtractor`, which basically take some `SPTEntry` (or two) and create a `Path` from it. In turn I removed the path extraction stuff from `Path` and deleted its subclasses.

- Instead of holding a reference to an (intermediate) `Path` instance (`bestPath`) `AbstractBidirAlgo` now just has a reference to the best fwd/bwd `SPTEntry` and the `bestWeight`. We can override `extractPath` if we want something different than the default path extraction, or just change the path extraction implementation by overriding `createPathExtractor`.


karussell: The build error for openjdk13 drives me crazy. There was a mistake regarding the version, but now [this is fixed](https://github.com/graphhopper/graphhopper/commit/f65576ca0de54f677970cf1d3778b4a09384f0f9) and locally it builds fine with it, even if I do `rm -rf ~/.m2/repository/com/graphhopper/*`. Also I removed the caches for travis, but this does not help. Do you have an idea or can you reproduce the problem that travis has with openjdk13?

The command should be:
```
export JAVA_HOME=/path/to/jdk-13/
mvn -version # verify that jdk-13 is used
mvn clean test very checkstyle:check forbiddenapis:check
```

Or maybe we try without the caching setting again in .travis.yml ...
karussell: > Or maybe we try without the caching setting again in .travis.yml ...

Didn't help.

The problem is that it downloads the core dependency:

```
Downloading from sonatype-snapshots: https://oss.sonatype.org/content/repositories/snapshots/com/graphhopper/graphhopper-core/0.14-SNAPSHOT/graphhopper-core-0.14-20190918.103923-1.jar
```

Although it builds this dependency before:

```
[INFO] Building jar: /home/travis/build/graphhopper/graphhopper/core/target/graphhopper-core-0.14-SNAPSHOT.jar
```

Patch:
diff --git a/core/files/changelog.txt b/core/files/changelog.txt
index 176fba9e6..85b0be6ac 100644
--- a/core/files/changelog.txt
+++ b/core/files/changelog.txt
@@ -1,5 +1,6 @@
 0.14
     conditional turn restrictions now supported, #1683
+    removed PathNative,PathBidirRef,Path4CH,EdgeBasedPathCH and moved path extraction code out of Path class, added PathExtractor,BidirPathExtractor(+subclasses for CH) instead, #1730
 
 0.13
     removed docker compose file
diff --git a/core/src/main/java/com/graphhopper/routing/AStar.java b/core/src/main/java/com/graphhopper/routing/AStar.java
index b684795d2..28d936a49 100644
--- a/core/src/main/java/com/graphhopper/routing/AStar.java
+++ b/core/src/main/java/com/graphhopper/routing/AStar.java
@@ -38,12 +38,12 @@ import java.util.PriorityQueue;
  * @author Peter Karich
  */
 public class AStar extends AbstractRoutingAlgorithm {
-    private WeightApproximator weightApprox;
-    private int visitedCount;
     private GHIntObjectHashMap<AStarEntry> fromMap;
-    private PriorityQueue<AStarEntry> prioQueueOpenSet;
+    private PriorityQueue<AStarEntry> fromHeap;
     private AStarEntry currEdge;
-    private int to1 = -1;
+    private int visitedNodes;
+    private int to = -1;
+    private WeightApproximator weightApprox;
 
     public AStar(Graph graph, Weighting weighting, TraversalMode tMode) {
         super(graph, weighting, tMode);
@@ -64,97 +64,94 @@ public class AStar extends AbstractRoutingAlgorithm {
 
     protected void initCollections(int size) {
         fromMap = new GHIntObjectHashMap<>();
-        prioQueueOpenSet = new PriorityQueue<>(size);
+        fromHeap = new PriorityQueue<>(size);
     }
 
     @Override
     public Path calcPath(int from, int to) {
         checkAlreadyRun();
-        to1 = to;
-
+        this.to = to;
         weightApprox.setTo(to);
         double weightToGoal = weightApprox.approximate(from);
         currEdge = new AStarEntry(EdgeIterator.NO_EDGE, from, 0 + weightToGoal, 0);
         if (!traversalMode.isEdgeBased()) {
             fromMap.put(from, currEdge);
         }
-        return runAlgo();
+        runAlgo();
+        return extractPath();
     }
 
-    private Path runAlgo() {
+    private void runAlgo() {
         double currWeightToGoal, estimationFullWeight;
         EdgeExplorer explorer = outEdgeExplorer;
         while (true) {
-            int currVertex = currEdge.adjNode;
-            visitedCount++;
-            if (isMaxVisitedNodesExceeded())
-                return createEmptyPath();
-
-            if (finished())
+            visitedNodes++;
+            if (isMaxVisitedNodesExceeded() || finished())
                 break;
 
-            EdgeIterator iter = explorer.setBaseNode(currVertex);
+            int currNode = currEdge.adjNode;
+            EdgeIterator iter = explorer.setBaseNode(currNode);
             while (iter.next()) {
                 if (!accept(iter, currEdge.edge))
                     continue;
 
-                double alreadyVisitedWeight = weighting.calcWeight(iter, false, currEdge.edge)
-                        + currEdge.weightOfVisitedPath;
-                if (Double.isInfinite(alreadyVisitedWeight))
+                double tmpWeight = weighting.calcWeight(iter, false, currEdge.edge) + currEdge.weightOfVisitedPath;
+                if (Double.isInfinite(tmpWeight)) {
                     continue;
-
+                }
                 int traversalId = traversalMode.createTraversalId(iter, false);
+
                 AStarEntry ase = fromMap.get(traversalId);
-                if (ase == null || ase.weightOfVisitedPath > alreadyVisitedWeight) {
+                if (ase == null || ase.weightOfVisitedPath > tmpWeight) {
                     int neighborNode = iter.getAdjNode();
                     currWeightToGoal = weightApprox.approximate(neighborNode);
-                    estimationFullWeight = alreadyVisitedWeight + currWeightToGoal;
+                    estimationFullWeight = tmpWeight + currWeightToGoal;
                     if (ase == null) {
-                        ase = new AStarEntry(iter.getEdge(), neighborNode, estimationFullWeight, alreadyVisitedWeight);
+                        ase = new AStarEntry(iter.getEdge(), neighborNode, estimationFullWeight, tmpWeight);
                         fromMap.put(traversalId, ase);
                     } else {
 //                        assert (ase.weight > 0.9999999 * estimationFullWeight) : "Inconsistent distance estimate. It is expected weight >= estimationFullWeight but was "
 //                                + ase.weight + " < " + estimationFullWeight + " (" + ase.weight / estimationFullWeight + "), and weightOfVisitedPath:"
 //                                + ase.weightOfVisitedPath + " vs. alreadyVisitedWeight:" + alreadyVisitedWeight + " (" + ase.weightOfVisitedPath / alreadyVisitedWeight + ")";
 
-                        prioQueueOpenSet.remove(ase);
+                        fromHeap.remove(ase);
                         ase.edge = iter.getEdge();
                         ase.weight = estimationFullWeight;
-                        ase.weightOfVisitedPath = alreadyVisitedWeight;
+                        ase.weightOfVisitedPath = tmpWeight;
                     }
 
                     ase.parent = currEdge;
-                    prioQueueOpenSet.add(ase);
+                    fromHeap.add(ase);
 
                     updateBestPath(iter, ase, traversalId);
                 }
             }
 
-            if (prioQueueOpenSet.isEmpty())
-                return createEmptyPath();
+            if (fromHeap.isEmpty())
+                break;
 
-            currEdge = prioQueueOpenSet.poll();
+            currEdge = fromHeap.poll();
             if (currEdge == null)
                 throw new AssertionError("Empty edge cannot happen");
         }
-
-        return extractPath();
     }
 
     @Override
-    protected Path extractPath() {
-        return new Path(graph, weighting).
-                setWeight(currEdge.weight).setSPTEntry(currEdge).extract();
+    protected boolean finished() {
+        return currEdge.adjNode == to;
     }
 
     @Override
-    protected boolean finished() {
-        return currEdge.adjNode == to1;
+    protected Path extractPath() {
+        if (currEdge == null || !finished())
+            return createEmptyPath();
+
+        return PathExtractor.extractPath(graph, weighting, currEdge);
     }
 
     @Override
     public int getVisitedNodes() {
-        return visitedCount;
+        return visitedNodes;
     }
 
     protected void updateBestPath(EdgeIteratorState edgeState, SPTEntry bestSPTEntry, int traversalId) {
diff --git a/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java b/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java
index a2958b795..11261afe7 100644
--- a/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java
+++ b/core/src/main/java/com/graphhopper/routing/AStarBidirectionCH.java
@@ -17,7 +17,7 @@
  */
 package com.graphhopper.routing;
 
-import com.graphhopper.routing.ch.Path4CH;
+import com.graphhopper.routing.ch.NodeBasedCHBidirPathExtractor;
 import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
@@ -39,13 +39,12 @@ public class AStarBidirectionCH extends AStarBidirection {
             return true;
 
         // changed finish condition for CH
-        return currFrom.weight >= bestPath.getWeight() && currTo.weight >= bestPath.getWeight();
+        return currFrom.weight >= bestWeight && currTo.weight >= bestWeight;
     }
 
     @Override
-    protected Path createAndInitPath() {
-        bestPath = new Path4CH(graph, graph.getBaseGraph(), weighting);
-        return bestPath;
+    protected BidirPathExtractor createPathExtractor(Graph graph, Weighting weighting) {
+        return new NodeBasedCHBidirPathExtractor(graph, graph.getBaseGraph(), weighting);
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/AStarBidirectionEdgeCHNoSOD.java b/core/src/main/java/com/graphhopper/routing/AStarBidirectionEdgeCHNoSOD.java
index 4c712e924..c5d3915f8 100644
--- a/core/src/main/java/com/graphhopper/routing/AStarBidirectionEdgeCHNoSOD.java
+++ b/core/src/main/java/com/graphhopper/routing/AStarBidirectionEdgeCHNoSOD.java
@@ -45,12 +45,12 @@ public class AStarBidirectionEdgeCHNoSOD extends AbstractBidirectionEdgeCHNoSOD
 
     @Override
     protected boolean fwdSearchCanBeStopped() {
-        return getMinCurrFromPathWeight() > bestPath.getWeight();
+        return getMinCurrFromPathWeight() > bestWeight;
     }
 
     @Override
     protected boolean bwdSearchCanBeStopped() {
-        return getMinCurrToPathWeight() > bestPath.getWeight();
+        return getMinCurrToPathWeight() > bestWeight;
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
index 13ebfb958..f07193037 100644
--- a/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
+++ b/core/src/main/java/com/graphhopper/routing/AbstractBidirAlgo.java
@@ -50,7 +50,9 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
     protected IntObjectMap<SPTEntry> bestWeightMapOther;
     protected SPTEntry currFrom;
     protected SPTEntry currTo;
-    protected PathBidirRef bestPath;
+    protected SPTEntry bestFwdEntry;
+    protected SPTEntry bestBwdEntry;
+    protected double bestWeight;
     PriorityQueue<SPTEntry> pqOpenSetFrom;
     PriorityQueue<SPTEntry> pqOpenSetTo;
     private boolean updateBestPath = true;
@@ -63,6 +65,7 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
         super(graph, weighting, tMode);
         fromOutEdge = ANY_EDGE;
         toInEdge = ANY_EDGE;
+        bestWeight = Double.MAX_VALUE;
         int size = Math.min(Math.max(200, graph.getNodes() / 10), 150_000);
         initCollections(size);
     }
@@ -115,15 +118,13 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
         this.fromOutEdge = fromOutEdge;
         this.toInEdge = toInEdge;
         checkAlreadyRun();
-        createAndInitPath();
         init(from, 0, to, 0);
         runAlgo();
         return extractPath();
     }
 
-    protected Path createAndInitPath() {
-        bestPath = new PathBidirRef(graph, weighting);
-        return bestPath;
+    protected BidirPathExtractor createPathExtractor(Graph graph, Weighting weighting) {
+        return new BidirPathExtractor(graph, weighting);
     }
 
     void init(int from, double fromWeight, int to, double toWeight) {
@@ -162,9 +163,9 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
             if (currFrom.weight != 0 || currTo.weight != 0) {
                 throw new IllegalStateException("If from=to, the starting weight must be zero for from and to");
             }
-            bestPath.sptEntry = currFrom;
-            bestPath.edgeTo = currTo;
-            bestPath.setWeight(0);
+            bestFwdEntry = currFrom;
+            bestBwdEntry = currTo;
+            bestWeight = 0;
             finishedFrom = true;
             finishedTo = true;
             return;
@@ -244,7 +245,7 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
         if (finishedFrom || finishedTo)
             return true;
 
-        return currFrom.weight + currTo.weight >= bestPath.getWeight();
+        return currFrom.weight + currTo.weight >= bestWeight;
     }
 
     boolean fillEdgesFrom() {
@@ -327,11 +328,10 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
             weight -= weighting.calcWeight(edgeState, reverse, EdgeIterator.NO_EDGE);
         }
 
-        if (weight < bestPath.getWeight()) {
-            bestPath.setSwitchToFrom(reverse);
-            bestPath.setSPTEntry(entry);
-            bestPath.setSPTEntryTo(entryOther);
-            bestPath.setWeight(weight);
+        if (weight < bestWeight) {
+            bestFwdEntry = reverse ? entryOther : entry;
+            bestBwdEntry = reverse ? entry : entryOther;
+            bestWeight = weight;
         }
     }
 
@@ -364,9 +364,9 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
     @Override
     protected Path extractPath() {
         if (finished())
-            return bestPath.extract();
+            return createPathExtractor(graph, weighting).extract(bestFwdEntry, bestBwdEntry, bestWeight);
 
-        return bestPath;
+        return createEmptyPath();
     }
 
     protected boolean fromEntryCanBeSkipped() {
@@ -409,10 +409,6 @@ public abstract class AbstractBidirAlgo extends AbstractRoutingAlgorithm {
         updateBestPath = b;
     }
 
-    void setBestPath(PathBidirRef bestPath) {
-        this.bestPath = bestPath;
-    }
-
     @Override
     public int getVisitedNodes() {
         return visitedCountFrom + visitedCountTo;
diff --git a/core/src/main/java/com/graphhopper/routing/AbstractBidirectionEdgeCHNoSOD.java b/core/src/main/java/com/graphhopper/routing/AbstractBidirectionEdgeCHNoSOD.java
index 85622d95a..7d4eab92a 100644
--- a/core/src/main/java/com/graphhopper/routing/AbstractBidirectionEdgeCHNoSOD.java
+++ b/core/src/main/java/com/graphhopper/routing/AbstractBidirectionEdgeCHNoSOD.java
@@ -18,11 +18,12 @@
 package com.graphhopper.routing;
 
 import com.graphhopper.routing.ch.CHEntry;
-import com.graphhopper.routing.ch.EdgeBasedPathCH;
+import com.graphhopper.routing.ch.EdgeBasedCHBidirPathExtractor;
 import com.graphhopper.routing.util.DefaultEdgeFilter;
 import com.graphhopper.routing.util.EdgeFilter;
 import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.TurnWeighting;
+import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.SPTEntry;
 import com.graphhopper.util.EdgeExplorer;
@@ -65,7 +66,6 @@ public abstract class AbstractBidirectionEdgeCHNoSOD extends AbstractBidirAlgo {
                 }
             });
         }
-        finishedFrom = bestPath.isFound();
     }
 
     @Override
@@ -80,7 +80,6 @@ public abstract class AbstractBidirectionEdgeCHNoSOD extends AbstractBidirAlgo {
                 }
             });
         }
-        finishedTo = bestPath.isFound();
     }
 
     @Override
@@ -95,7 +94,7 @@ public abstract class AbstractBidirectionEdgeCHNoSOD extends AbstractBidirAlgo {
             return true;
 
         // changed also the final finish condition for CH
-        return currFrom.weight >= bestPath.getWeight() && currTo.weight >= bestPath.getWeight();
+        return currFrom.weight >= bestWeight && currTo.weight >= bestWeight;
     }
 
     @Override
@@ -107,11 +106,10 @@ public abstract class AbstractBidirectionEdgeCHNoSOD extends AbstractBidirAlgo {
         int oppositeEdge = reverse ? fromOutEdge : toInEdge;
         boolean oppositeEdgeRestricted = reverse ? (fromOutEdge != ANY_EDGE) : (toInEdge != ANY_EDGE);
         if (edgeState.getAdjNode() == oppositeNode && (!oppositeEdgeRestricted || getOrigEdgeId(edgeState, reverse) == oppositeEdge)) {
-            if (entry.getWeightOfVisitedPath() < bestPath.getWeight()) {
-                bestPath.setSwitchToFrom(reverse);
-                bestPath.setSPTEntry(entry);
-                bestPath.setSPTEntryTo(new CHEntry(oppositeNode, 0));
-                bestPath.setWeight(entry.getWeightOfVisitedPath());
+            if (entry.getWeightOfVisitedPath() < bestWeight) {
+                bestFwdEntry = reverse ? new CHEntry(oppositeNode, 0) : entry;
+                bestBwdEntry = reverse ? entry : new CHEntry(oppositeNode, 0);
+                bestWeight = entry.getWeightOfVisitedPath();
                 return;
             }
         }
@@ -137,19 +135,17 @@ public abstract class AbstractBidirectionEdgeCHNoSOD extends AbstractBidirAlgo {
                     turnWeighting.calcTurnWeight(prevOrNextOrigEdgeId, iter.getBaseNode(), edgeId);
 
             double newWeight = entry.getWeightOfVisitedPath() + entryOther.getWeightOfVisitedPath() + turnCostsAtBridgeNode;
-            if (newWeight < bestPath.getWeight()) {
-                bestPath.setSwitchToFrom(reverse);
-                bestPath.setSPTEntry(entry);
-                bestPath.setSPTEntryTo(entryOther);
-                bestPath.setWeight(newWeight);
+            if (newWeight < bestWeight) {
+                bestFwdEntry = reverse ? entryOther : entry;
+                bestBwdEntry = reverse ? entry : entryOther;
+                bestWeight = newWeight;
             }
         }
     }
 
     @Override
-    protected Path createAndInitPath() {
-        bestPath = new EdgeBasedPathCH(graph, graph.getBaseGraph(), weighting);
-        return bestPath;
+    protected BidirPathExtractor createPathExtractor(Graph graph, Weighting weighting) {
+        return new EdgeBasedCHBidirPathExtractor(graph, graph.getBaseGraph(), weighting);
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/AlternativeRoute.java b/core/src/main/java/com/graphhopper/routing/AlternativeRoute.java
index 145fb5622..a7b238bdd 100644
--- a/core/src/main/java/com/graphhopper/routing/AlternativeRoute.java
+++ b/core/src/main/java/com/graphhopper/routing/AlternativeRoute.java
@@ -173,12 +173,11 @@ public class AlternativeRoute implements RoutingAlgorithm {
             altBidirDijktra.setApproximation(weightApproximator);
         }
 
-        altBidirDijktra.searchBest(from, to);
+        Path bestPath = altBidirDijktra.searchBest(from, to);
         visitedNodes = altBidirDijktra.getVisitedNodes();
 
-        List<AlternativeInfo> alternatives = altBidirDijktra.
-                calcAlternatives(maxPaths, maxWeightFactor, 7, maxShareFactor, 0.8, minPlateauFactor, -0.2);
-        return alternatives;
+        return altBidirDijktra.
+                calcAlternatives(bestPath, maxPaths, maxWeightFactor, 7, maxShareFactor, 0.8, minPlateauFactor, -0.2);
     }
 
     @Override
@@ -273,18 +272,17 @@ public class AlternativeRoute implements RoutingAlgorithm {
                 return true;
 
             // The following condition is necessary to avoid traversing the full graph if areas are disconnected
-            // but it is only valid for none-CH e.g. for CH it can happen that finishedTo is true but the from-SPT could still reach 'to'
-            if (!bestPath.isFound() && (finishedFrom || finishedTo))
+            // but it is only valid for non-CH e.g. for CH it can happen that finishedTo is true but the from-SPT could still reach 'to'
+            if (finishedFrom || finishedTo)
                 return true;
 
             // increase overlap of both searches:
-            return currFrom.weight + currTo.weight > explorationFactor * bestPath.getWeight();
-            // This is more precise but takes roughly 20% longer: return currFrom.weight > bestPath.getWeight() && currTo.weight > bestPath.getWeight();
+            return currFrom.weight + currTo.weight > explorationFactor * bestWeight;
+            // This is more precise but takes roughly 20% longer: return currFrom.weight > bestWeight && currTo.weight > bestWeight;
             // For bidir A* and AStarEdge.getWeightOfVisitedPath see comment in AStarBidirection.finished
         }
 
         public Path searchBest(int from, int to) {
-            createAndInitPath();
             init(from, 0, to, 0);
             // init collections and bestPath.getWeight properly
             runAlgo();
@@ -295,11 +293,11 @@ public class AlternativeRoute implements RoutingAlgorithm {
          * @return the information necessary to handle alternative paths. Note that the paths are
          * not yet extracted.
          */
-        public List<AlternativeInfo> calcAlternatives(final int maxPaths,
+        public List<AlternativeInfo> calcAlternatives(final Path bestPath, final int maxPaths,
                                                       double maxWeightFactor, final double weightInfluence,
                                                       final double maxShareFactor, final double shareInfluence,
                                                       final double minPlateauFactor, final double plateauInfluence) {
-            final double maxWeight = maxWeightFactor * bestPath.getWeight();
+            final double maxWeight = maxWeightFactor * bestWeight;
             final GHIntObjectHashMap<IntSet> traversalIdMap = new GHIntObjectHashMap<>();
             final AtomicInteger startTID = addToMap(traversalIdMap, bestPath);
 
@@ -308,14 +306,14 @@ public class AlternativeRoute implements RoutingAlgorithm {
             // only for plateau start candidates (2)
             final List<AlternativeInfo> alternatives = new ArrayList<>(maxPaths);
 
-            double bestPlateau = bestPath.getWeight();
+            double bestPlateau = bestWeight;
             double bestShare = 0;
-            double sortBy = calcSortBy(weightInfluence, bestPath.getWeight(),
+            double sortBy = calcSortBy(weightInfluence, bestWeight,
                     shareInfluence, bestShare,
                     plateauInfluence, bestPlateau);
 
             final AlternativeInfo bestAlt = new AlternativeInfo(sortBy, bestPath,
-                    bestPath.sptEntry, bestPath.edgeTo, bestShare, getAltNames(graph, bestPath.sptEntry));
+                    bestFwdEntry, bestBwdEntry, bestShare, getAltNames(graph, bestFwdEntry));
             alternatives.add(bestAlt);
             final List<SPTEntry> bestPathEntries = new ArrayList<>(2);
 
@@ -347,7 +345,7 @@ public class AlternativeRoute implements RoutingAlgorithm {
                     // Accept from-EdgeEntries only if such a start of a plateau
                     // i.e. discard if its parent has the same edgeId as the next to-SPTEntry.
                     // Ignore already added best path
-                    if (isBestPath(fromSPTEntry, bestPath))
+                    if (isBestPath(fromSPTEntry))
                         return true;
 
                     // For edge based traversal we need the next entry to find out the plateau start
@@ -412,7 +410,7 @@ public class AlternativeRoute implements RoutingAlgorithm {
                     SPTEntry fromEE = getFirstShareEE(fromSPTEntry.parent, true);
                     SPTEntry toEE = getFirstShareEE(toSPTEntry.parent, false);
                     double shareWeight = fromEE.getWeightOfVisitedPath() + toEE.getWeightOfVisitedPath();
-                    boolean smallShare = shareWeight / bestPath.getWeight() < maxShareFactor;
+                    boolean smallShare = shareWeight / bestWeight < maxShareFactor;
                     if (smallShare) {
                         List<String> altNames = getAltNames(graph, fromSPTEntry);
 
@@ -421,10 +419,7 @@ public class AlternativeRoute implements RoutingAlgorithm {
 
                         // plateaus.add(new PlateauInfo(altName, plateauEdges));
                         if (sortBy < worstSortBy || alternatives.size() < maxPaths) {
-                            Path path = new PathBidirRef(graph, weighting).
-                                    setSPTEntryTo(toSPTEntry).setSPTEntry(fromSPTEntry).
-                                    setWeight(weight);
-                            path.extract();
+                            Path path = BidirPathExtractor.extractPath(graph, weighting, fromSPTEntry, toSPTEntry, weight);
 
                             // for now do not add alternatives to set, if we do we need to remove then on alternatives.clear too (see below)
                             // AtomicInteger tid = addToMap(traversalIDMap, path);
@@ -489,7 +484,7 @@ public class AlternativeRoute implements RoutingAlgorithm {
                 }
 
                 // returns true if fromSPTEntry is identical to the specified best path
-                boolean isBestPath(SPTEntry fromSPTEntry, Path bestPath) {
+                boolean isBestPath(SPTEntry fromSPTEntry) {
                     if (traversalMode.isEdgeBased()) {
                         if (GHUtility.getEdgeFromEdgeKey(startTID.get()) == fromSPTEntry.edge) {
                             if (fromSPTEntry.parent == null)
diff --git a/core/src/main/java/com/graphhopper/routing/BidirPathExtractor.java b/core/src/main/java/com/graphhopper/routing/BidirPathExtractor.java
new file mode 100644
index 000000000..58fdddaa2
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/BidirPathExtractor.java
@@ -0,0 +1,130 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH licenses this file to you under the Apache License,
+ *  Version 2.0 (the "License"); you may not use this file except in
+ *  compliance with the License. You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package com.graphhopper.routing;
+
+import com.graphhopper.routing.weighting.TurnWeighting;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.SPTEntry;
+import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.StopWatch;
+
+/**
+ * Builds a {@link Path} from the two fwd- and bwd-shortest path tree entries of a bidirectional search
+ *
+ * @author Peter Karich
+ * @author easbar
+ */
+public class BidirPathExtractor {
+    private final Graph graph;
+    private final Weighting weighting;
+    protected final Path path;
+
+    public static Path extractPath(Graph graph, Weighting weighting, SPTEntry fwdEntry, SPTEntry bwdEntry, double weight) {
+        return new BidirPathExtractor(graph, weighting).extract(fwdEntry, bwdEntry, weight);
+    }
+
+    protected BidirPathExtractor(Graph graph, Weighting weighting) {
+        this.graph = graph;
+        this.weighting = weighting;
+        this.path = new Path(graph, weighting);
+    }
+
+    protected Path extract(SPTEntry fwdEntry, SPTEntry bwdEntry, double weight) {
+        if (fwdEntry == null || bwdEntry == null) {
+            // path not found
+            return path;
+        }
+        if (fwdEntry.adjNode != bwdEntry.adjNode)
+            throw new IllegalStateException("forward and backward entries must have same adjacent nodes, fwdEntry:" + fwdEntry + ", bwdEntry:" + bwdEntry);
+
+        StopWatch sw = new StopWatch().start();
+        extractFwdPath(fwdEntry);
+        processMeetingPoint(fwdEntry, bwdEntry);
+        extractBwdPath(bwdEntry);
+        setExtractionTime(sw.stop().getNanos());
+        path.setFound(true);
+        path.setWeight(weight);
+        return path;
+    }
+
+    protected void extractFwdPath(SPTEntry sptEntry) {
+        SPTEntry fwdRoot = followParentsUntilRoot(sptEntry, false);
+        onFwdTreeRoot(fwdRoot.adjNode);
+        // since we followed the fwd path in backward direction we need to reverse the edge ids
+        path.reverseEdges();
+    }
+
+    protected void extractBwdPath(SPTEntry sptEntry) {
+        SPTEntry bwdRoot = followParentsUntilRoot(sptEntry, true);
+        onBwdTreeRoot(bwdRoot.adjNode);
+    }
+
+    protected void processMeetingPoint(SPTEntry fwdEntry, SPTEntry bwdEntry) {
+        int inEdge = getIncEdge(fwdEntry);
+        int outEdge = getIncEdge(bwdEntry);
+        onMeetingPoint(inEdge, fwdEntry.adjNode, outEdge);
+    }
+
+    protected SPTEntry followParentsUntilRoot(SPTEntry sptEntry, boolean reverse) {
+        SPTEntry currEntry = sptEntry;
+        SPTEntry parentEntry = currEntry.parent;
+        while (EdgeIterator.Edge.isValid(currEntry.edge)) {
+            onEdge(currEntry.edge, currEntry.adjNode, reverse, getIncEdge(parentEntry));
+            currEntry = parentEntry;
+            parentEntry = currEntry.parent;
+        }
+        return currEntry;
+    }
+
+    protected void setExtractionTime(long nanos) {
+        path.setDebugInfo("path extraction: " + nanos / 1000 + " micros");
+    }
+
+    protected int getIncEdge(SPTEntry entry) {
+        return entry.edge;
+    }
+
+    protected void onFwdTreeRoot(int node) {
+        path.setFromNode(node);
+    }
+
+    protected void onBwdTreeRoot(int node) {
+        path.setEndNode(node);
+    }
+
+    protected void onEdge(int edge, int adjNode, boolean reverse, int prevOrNextEdge) {
+        EdgeIteratorState edgeState = graph.getEdgeIteratorState(edge, adjNode);
+        path.addDistance(edgeState.getDistance());
+        path.addTime(weighting.calcMillis(edgeState, reverse, prevOrNextEdge));
+        path.addEdge(edge);
+    }
+
+    protected void onMeetingPoint(int inEdge, int viaNode, int outEdge) {
+        if (!EdgeIterator.Edge.isValid(inEdge) || !EdgeIterator.Edge.isValid(outEdge)) {
+            return;
+        }
+        if (weighting instanceof TurnWeighting) {
+            double turnWeight = ((TurnWeighting) weighting).calcTurnWeight(inEdge, viaNode, outEdge);
+            path.addTime((long) (turnWeight * 1000));
+        }
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/Dijkstra.java b/core/src/main/java/com/graphhopper/routing/Dijkstra.java
index a61eab106..6ad277fed 100644
--- a/core/src/main/java/com/graphhopper/routing/Dijkstra.java
+++ b/core/src/main/java/com/graphhopper/routing/Dijkstra.java
@@ -74,8 +74,8 @@ public class Dijkstra extends AbstractRoutingAlgorithm {
             if (isMaxVisitedNodesExceeded() || finished())
                 break;
 
-            int startNode = currEdge.adjNode;
-            EdgeIterator iter = explorer.setBaseNode(startNode);
+            int currNode = currEdge.adjNode;
+            EdgeIterator iter = explorer.setBaseNode(currNode);
             while (iter.next()) {
                 if (!accept(iter, currEdge.edge))
                     continue;
@@ -123,8 +123,7 @@ public class Dijkstra extends AbstractRoutingAlgorithm {
         if (currEdge == null || !finished())
             return createEmptyPath();
 
-        return new Path(graph, weighting).
-                setWeight(currEdge.weight).setSPTEntry(currEdge).extract();
+        return PathExtractor.extractPath(graph, weighting, currEdge);
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCHNoSOD.java b/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCHNoSOD.java
index 307f1cfe5..60684553e 100644
--- a/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCHNoSOD.java
+++ b/core/src/main/java/com/graphhopper/routing/DijkstraBidirectionCHNoSOD.java
@@ -17,7 +17,7 @@
  */
 package com.graphhopper.routing;
 
-import com.graphhopper.routing.ch.Path4CH;
+import com.graphhopper.routing.ch.NodeBasedCHBidirPathExtractor;
 import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
@@ -39,13 +39,12 @@ public class DijkstraBidirectionCHNoSOD extends DijkstraBidirectionRef {
             return true;
 
         // changed also the final finish condition for CH
-        return currFrom.weight >= bestPath.getWeight() && currTo.weight >= bestPath.getWeight();
+        return currFrom.weight >= bestWeight && currTo.weight >= bestWeight;
     }
 
     @Override
-    protected Path createAndInitPath() {
-        bestPath = new Path4CH(graph, graph.getBaseGraph(), weighting);
-        return bestPath;
+    protected BidirPathExtractor createPathExtractor(Graph graph, Weighting weighting) {
+        return new NodeBasedCHBidirPathExtractor(graph, graph.getBaseGraph(), weighting);
     }
 
     @Override
diff --git a/core/src/main/java/com/graphhopper/routing/DijkstraOneToMany.java b/core/src/main/java/com/graphhopper/routing/DijkstraOneToMany.java
index 49bf5500b..133e6bc4d 100644
--- a/core/src/main/java/com/graphhopper/routing/DijkstraOneToMany.java
+++ b/core/src/main/java/com/graphhopper/routing/DijkstraOneToMany.java
@@ -23,6 +23,7 @@ import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
 import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.EdgeIteratorState;
 import com.graphhopper.util.Helper;
 import com.graphhopper.util.Parameters;
 
@@ -75,15 +76,32 @@ public class DijkstraOneToMany extends AbstractRoutingAlgorithm {
 
     @Override
     public Path extractPath() {
-        PathNative p = new PathNative(graph, weighting, parents, edgeIds);
-        if (endNode >= 0)
-            p.setWeight(weights[endNode]);
-        p.setFromNode(fromNode);
-        // return 'not found' if invalid endNode or limit reached
-        if (endNode < 0 || isWeightLimitExceeded())
-            return p;
-
-        return p.setEndNode(endNode).extract();
+        if (endNode < 0 || isWeightLimitExceeded()) {
+            Path path = createEmptyPath();
+            path.setFromNode(fromNode);
+            path.setEndNode(endNode);
+            return path;
+        }
+
+        Path path = new Path(graph, weighting);
+        int node = endNode;
+        while (true) {
+            int edge = edgeIds[node];
+            if (!EdgeIterator.Edge.isValid(edge)) {
+                break;
+            }
+            EdgeIteratorState edgeState = graph.getEdgeIteratorState(edge, node);
+            path.addDistance(edgeState.getDistance());
+            path.addTime(weighting.calcMillis(edgeState, false, EdgeIterator.NO_EDGE));
+            path.addEdge(edge);
+            node = parents[node];
+        }
+        path.reverseEdges();
+        path.setFromNode(fromNode);
+        path.setEndNode(endNode);
+        path.setFound(true);
+        path.setWeight(weights[endNode]);
+        return path;
     }
 
     /**
diff --git a/core/src/main/java/com/graphhopper/routing/Path.java b/core/src/main/java/com/graphhopper/routing/Path.java
index f3fe8c985..f9ac21572 100644
--- a/core/src/main/java/com/graphhopper/routing/Path.java
+++ b/core/src/main/java/com/graphhopper/routing/Path.java
@@ -37,28 +37,19 @@ import org.slf4j.LoggerFactory;
 import java.util.*;
 
 /**
- * Stores the nodes for the found path of an algorithm. It additionally needs the edgeIds to make
- * edge determination faster and less complex as there could be several edges (u,v) especially for
- * graphs with shortcuts.
- * <p>
+ * This class represents the result of a shortest path calculation. It also provides methods to extract further
+ * information about the found path, like instructions etc.
  *
  * @author Peter Karich
  * @author Ottavio Campana
  * @author jan soe
+ * @author easbar
  */
 public class Path {
-    private final Logger logger = LoggerFactory.getLogger(getClass());
-
-    final StopWatch extractSW = new StopWatch("extract");
     protected Graph graph;
     protected double distance;
-    // we go upwards (via SPTEntry.parent) from the goal node to the origin node
     protected boolean reverseOrder = true;
     protected long time;
-    /**
-     * Shortest path tree entry
-     */
-    protected SPTEntry sptEntry;
     protected int endNode = -1;
     private List<String> description;
     protected Weighting weighting;
@@ -68,6 +59,7 @@ public class Path {
     private GHIntArrayList edgeIds;
     private double weight;
     private NodeAccess nodeAccess;
+    private String debugInfo = "";
 
     public Path(Graph graph, Weighting weighting) {
         this.weight = Double.MAX_VALUE;
@@ -78,16 +70,6 @@ public class Path {
         this.edgeIds = new GHIntArrayList();
     }
 
-    /**
-     * Populates an unextracted path instances from the specified path p.
-     */
-    Path(Path p) {
-        this(p.graph, p.weighting);
-        weight = p.weight;
-        edgeIds = new GHIntArrayList(p.edgeIds);
-        sptEntry = p.sptEntry;
-    }
-
     /**
      * @return the description of this route alternative to make it meaningful for the user e.g. it
      * displays one or two main roads of the route.
@@ -103,12 +85,7 @@ public class Path {
         return this;
     }
 
-    public Path setSPTEntry(SPTEntry sptEntry) {
-        this.sptEntry = sptEntry;
-        return this;
-    }
-
-    protected void addEdge(int edge) {
+    public void addEdge(int edge) {
         edgeIds.add(edge);
     }
 
@@ -122,7 +99,7 @@ public class Path {
      */
     private int getFromNode() {
         if (fromNode < 0)
-            throw new IllegalStateException("Call extract() before retrieving fromNode");
+            throw new IllegalStateException("fromNode < 0 should not happen");
 
         return fromNode;
     }
@@ -148,7 +125,7 @@ public class Path {
         return this;
     }
 
-    void reverseOrder() {
+    void reverseEdges() {
         if (!reverseOrder)
             throw new IllegalStateException("Switching order multiple times is not supported");
 
@@ -161,6 +138,11 @@ public class Path {
         return this;
     }
 
+    public Path addDistance(double distance) {
+        this.distance += distance;
+        return this;
+    }
+
     /**
      * @return distance in meter
      */
@@ -175,6 +157,11 @@ public class Path {
         return time;
     }
 
+    public Path addTime(long time) {
+        this.time += time;
+        return this;
+    }
+
     /**
      * This weight will be updated during the algorithm. The initial value is maximum double.
      */
@@ -187,32 +174,6 @@ public class Path {
         return this;
     }
 
-    /**
-     * Extracts the Path from the shortest-path-tree determined by sptEntry.
-     */
-    public Path extract() {
-        if (isFound())
-            throw new IllegalStateException("Extract can only be called once");
-
-        extractSW.start();
-        SPTEntry currEdge = sptEntry;
-        setEndNode(currEdge.adjNode);
-        boolean nextEdgeValid = EdgeIterator.Edge.isValid(currEdge.edge);
-        int nextEdge;
-        while (nextEdgeValid) {
-            // the reverse search needs the next edge
-            nextEdgeValid = EdgeIterator.Edge.isValid(currEdge.parent.edge);
-            nextEdge = nextEdgeValid ? currEdge.parent.edge : EdgeIterator.NO_EDGE;
-            processEdge(currEdge.edge, currEdge.adjNode, nextEdge);
-            currEdge = currEdge.parent;
-        }
-
-        setFromNode(currEdge.adjNode);
-        reverseOrder();
-        extractSW.stop();
-        return setFound(true);
-    }
-
     /**
      * Yields the final edge of the path
      */
@@ -220,27 +181,12 @@ public class Path {
         return graph.getEdgeIteratorState(edgeIds.get(edgeIds.size() - 1), endNode);
     }
 
-    /**
-     * @return the time it took to extract the path in nano (!) seconds
-     */
-    public long getExtractTime() {
-        return extractSW.getNanos();
+    public void setDebugInfo(String debugInfo) {
+        this.debugInfo = debugInfo;
     }
 
     public String getDebugInfo() {
-        return extractSW.toString();
-    }
-
-    /**
-     * Calculates the distance and time of the specified edgeId. Also it adds the edgeId to the path list.
-     *
-     * @param prevEdgeId the edge that comes before edgeId: --prevEdgeId-x-edgeId-->adjNode
-     */
-    protected void processEdge(int edgeId, int adjNode, int prevEdgeId) {
-        EdgeIteratorState iter = graph.getEdgeIteratorState(edgeId, adjNode);
-        distance += iter.getDistance();
-        time += weighting.calcMillis(iter, false, prevEdgeId);
-        addEdge(edgeId);
+        return debugInfo;
     }
 
     /**
diff --git a/core/src/main/java/com/graphhopper/routing/PathBidirRef.java b/core/src/main/java/com/graphhopper/routing/PathBidirRef.java
deleted file mode 100644
index cc5dc96c4..000000000
--- a/core/src/main/java/com/graphhopper/routing/PathBidirRef.java
+++ /dev/null
@@ -1,135 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.routing;
-
-import com.graphhopper.routing.weighting.TurnWeighting;
-import com.graphhopper.routing.weighting.Weighting;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.storage.SPTEntry;
-import com.graphhopper.util.EdgeIterator;
-import com.graphhopper.util.EdgeIteratorState;
-
-/**
- * This class creates a DijkstraPath from two Edge's resulting from a BidirectionalDijkstra
- * <p>
- *
- * @author Peter Karich
- */
-public class PathBidirRef extends Path {
-    protected SPTEntry edgeTo;
-    private boolean switchFromAndToSPTEntry = false;
-
-    public PathBidirRef(Graph g, Weighting weighting) {
-        super(g, weighting);
-    }
-
-    PathBidirRef(PathBidirRef p) {
-        super(p);
-        edgeTo = p.edgeTo;
-        switchFromAndToSPTEntry = p.switchFromAndToSPTEntry;
-    }
-
-    public PathBidirRef setSwitchToFrom(boolean b) {
-        switchFromAndToSPTEntry = b;
-        return this;
-    }
-
-    public PathBidirRef setSPTEntryTo(SPTEntry edgeTo) {
-        this.edgeTo = edgeTo;
-        return this;
-    }
-
-    /**
-     * Extracts path from two shortest-path-tree
-     */
-    @Override
-    public Path extract() {
-        if (sptEntry == null || edgeTo == null)
-            return this;
-
-        if (sptEntry.adjNode != edgeTo.adjNode)
-            throw new IllegalStateException("Locations of the 'to'- and 'from'-Edge have to be the same. " + toString() + ", fromEntry:" + sptEntry + ", toEntry:" + edgeTo);
-
-        extractSW.start();
-        if (switchFromAndToSPTEntry) {
-            SPTEntry ee = sptEntry;
-            sptEntry = edgeTo;
-            edgeTo = ee;
-        }
-        extractFwdPath();
-        processTurnAtMeetingPoint();
-        extractBwdPath();
-        extractSW.stop();
-        return setFound(true);
-    }
-
-    private void extractFwdPath() {
-        // we take the 'edgeFrom'/sptEntry that points at the meeting node and follow its parent pointers back to
-        // the source
-        SPTEntry currEdge = sptEntry;
-        SPTEntry prevEdge = currEdge.parent;
-        while (EdgeIterator.Edge.isValid(currEdge.edge)) {
-            processEdge(currEdge.edge, currEdge.adjNode, getIncEdge(prevEdge));
-            currEdge = prevEdge;
-            prevEdge = currEdge.parent;
-        }
-        setFromNode(currEdge.adjNode);
-        // since we followed the fwd path in backward direction we need to reverse the edge ids
-        reverseOrder();
-    }
-
-    private void extractBwdPath() {
-        // we take the edgeTo at the meeting node and follow its parent pointers to the target
-        SPTEntry currEdge = edgeTo;
-        SPTEntry nextEdge = currEdge.parent;
-        while (EdgeIterator.Edge.isValid(currEdge.edge)) {
-            processEdgeBwd(currEdge.edge, currEdge.adjNode, getIncEdge(nextEdge));
-            currEdge = nextEdge;
-            nextEdge = nextEdge.parent;
-        }
-        setEndNode(currEdge.adjNode);
-    }
-
-    private void processTurnAtMeetingPoint() {
-        processTurn(getIncEdge(sptEntry), sptEntry.adjNode, getIncEdge(edgeTo));
-    }
-
-    /**
-     * Similar to {@link #processEdge(int, int, int)}, but with the situation we encounter when doing a backward
-     * search: nextEdgeId--x<--edgeId--adjNode
-     */
-    protected void processEdgeBwd(int edgeId, int adjNode, int nextEdgeId) {
-        EdgeIteratorState edge = graph.getEdgeIteratorState(edgeId, adjNode);
-        distance += edge.getDistance();
-        time += weighting.calcMillis(edge, true, nextEdgeId);
-        addEdge(edgeId);
-    }
-
-    private void processTurn(int inEdge, int viaNode, int outEdge) {
-        if (!EdgeIterator.Edge.isValid(inEdge) || !EdgeIterator.Edge.isValid(outEdge)) {
-            return;
-        }
-        if (weighting instanceof TurnWeighting) {
-            time += ((TurnWeighting) weighting).calcTurnWeight(inEdge, viaNode, outEdge) * 1000;
-        }
-    }
-
-    protected int getIncEdge(SPTEntry entry) {
-        return entry.edge;
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/routing/PathExtractor.java b/core/src/main/java/com/graphhopper/routing/PathExtractor.java
new file mode 100644
index 000000000..d92e9f542
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/PathExtractor.java
@@ -0,0 +1,85 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH licenses this file to you under the Apache License,
+ *  Version 2.0 (the "License"); you may not use this file except in
+ *  compliance with the License. You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package com.graphhopper.routing;
+
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.SPTEntry;
+import com.graphhopper.util.EdgeIterator;
+import com.graphhopper.util.EdgeIteratorState;
+import com.graphhopper.util.StopWatch;
+
+public class PathExtractor {
+    private final Graph graph;
+    private final Weighting weighting;
+    protected final Path path;
+
+    public static Path extractPath(Graph graph, Weighting weighting, SPTEntry sptEntry) {
+        return new PathExtractor(graph, weighting).extract(sptEntry);
+    }
+
+    protected PathExtractor(Graph graph, Weighting weighting) {
+        this.graph = graph;
+        this.weighting = weighting;
+        path = new Path(graph, weighting);
+    }
+
+    protected Path extract(SPTEntry sptEntry) {
+        if (sptEntry == null) {
+            // path not found
+            return path;
+        }
+        StopWatch sw = new StopWatch().start();
+        extractPath(sptEntry);
+        path.setFound(true);
+        path.setWeight(sptEntry.weight);
+        setExtractionTime(sw.stop().getNanos());
+        return path;
+    }
+
+    private void extractPath(SPTEntry sptEntry) {
+        SPTEntry currEdge = followParentsUntilRoot(sptEntry);
+        path.reverseEdges();
+        path.setFromNode(currEdge.adjNode);
+        path.setEndNode(sptEntry.adjNode);
+    }
+
+    private SPTEntry followParentsUntilRoot(SPTEntry sptEntry) {
+        SPTEntry currEntry = sptEntry;
+        SPTEntry parentEntry = currEntry.parent;
+        while (EdgeIterator.Edge.isValid(currEntry.edge)) {
+            onEdge(currEntry.edge, currEntry.adjNode, parentEntry.edge);
+            currEntry = currEntry.parent;
+            parentEntry = currEntry.parent;
+        }
+        return currEntry;
+    }
+
+    private void setExtractionTime(long nanos) {
+        path.setDebugInfo("path extraction: " + nanos / 1000 + " micros");
+    }
+
+    protected void onEdge(int edge, int adjNode, int prevEdge) {
+        EdgeIteratorState edgeState = graph.getEdgeIteratorState(edge, adjNode);
+        path.addDistance(edgeState.getDistance());
+        path.addTime(weighting.calcMillis(edgeState, false, prevEdge));
+        path.addEdge(edge);
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/PathNative.java b/core/src/main/java/com/graphhopper/routing/PathNative.java
deleted file mode 100644
index 32a843c95..000000000
--- a/core/src/main/java/com/graphhopper/routing/PathNative.java
+++ /dev/null
@@ -1,58 +0,0 @@
-/*
- *  Licensed to GraphHopper GmbH under one or more contributor
- *  license agreements. See the NOTICE file distributed with this work for
- *  additional information regarding copyright ownership.
- *
- *  GraphHopper GmbH licenses this file to you under the Apache License,
- *  Version 2.0 (the "License"); you may not use this file except in
- *  compliance with the License. You may obtain a copy of the License at
- *
- *       http://www.apache.org/licenses/LICENSE-2.0
- *
- *  Unless required by applicable law or agreed to in writing, software
- *  distributed under the License is distributed on an "AS IS" BASIS,
- *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- *  See the License for the specific language governing permissions and
- *  limitations under the License.
- */
-package com.graphhopper.routing;
-
-import com.graphhopper.routing.util.FlagEncoder;
-import com.graphhopper.routing.weighting.Weighting;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.util.EdgeIterator;
-
-/**
- * This class creates a Path from a DijkstraOneToMany algorithm
- *
- * @author Peter Karich
- */
-public class PathNative extends Path {
-    private final int[] parentNodes;
-    private final int[] parentEdges;
-
-    public PathNative(Graph g, Weighting weighting, int[] parentNodes, int[] parentEdges) {
-        super(g, weighting);
-        this.parentNodes = parentNodes;
-        this.parentEdges = parentEdges;
-    }
-
-    @Override
-    public Path extract() {
-        if (endNode < 0)
-            return this;
-
-        int prevEdge = EdgeIterator.NO_EDGE;
-        while (true) {
-            int edgeId = parentEdges[endNode];
-            if (!EdgeIterator.Edge.isValid(edgeId))
-                break;
-
-            processEdge(edgeId, endNode, prevEdge);
-            prevEdge = edgeId;
-            endNode = parentNodes[endNode];
-        }
-        reverseOrder();
-        return setFound(true);
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedCHBidirPathExtractor.java b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedCHBidirPathExtractor.java
new file mode 100644
index 000000000..2711b3d2f
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedCHBidirPathExtractor.java
@@ -0,0 +1,68 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for
+ *  additional information regarding copyright ownership.
+ *
+ *  GraphHopper GmbH licenses this file to you under the Apache License,
+ *  Version 2.0 (the "License"); you may not use this file except in
+ *  compliance with the License. You may obtain a copy of the License at
+ *
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package com.graphhopper.routing.ch;
+
+import com.graphhopper.routing.BidirPathExtractor;
+import com.graphhopper.routing.weighting.TurnWeighting;
+import com.graphhopper.routing.weighting.Weighting;
+import com.graphhopper.storage.Graph;
+import com.graphhopper.storage.SPTEntry;
+import com.graphhopper.storage.ShortcutUnpacker;
+import com.graphhopper.util.EdgeIteratorState;
+
+/**
+ * @author easbar
+ */
+public class EdgeBasedCHBidirPathExtractor extends BidirPathExtractor {
+    private final ShortcutUnpacker shortcutUnpacker;
+
+    public EdgeBasedCHBidirPathExtractor(Graph routingGraph, Graph baseGraph, Weighting weighting) {
+        super(baseGraph, weighting);
+        shortcutUnpacker = createShortcutUnpacker(routingGraph, weighting);
+        if (!(weighting instanceof TurnWeighting)) {
+            throw new IllegalArgumentException("Need a TurnWeighting for edge-based CH");
+        }
+    }
+
+    @Override
+    public void onEdge(int edge, int adjNode, boolean reverse, int prevOrNextEdge) {
+        if (reverse) {
+            shortcutUnpacker.visitOriginalEdgesBwd(edge, adjNode, true, prevOrNextEdge);
+        } else {
+            shortcutUnpacker.visitOriginalEdgesFwd(edge, adjNode, true, prevOrNextEdge);
+        }
+    }
+
+    private ShortcutUnpacker createShortcutUnpacker(Graph routingGraph, final Weighting weighting) {
+        return new ShortcutUnpacker(routingGraph, new ShortcutUnpacker.Visitor() {
+            @Override
+            public void visit(EdgeIteratorState edge, boolean reverse, int prevOrNextEdgeId) {
+                path.addDistance(edge.getDistance());
+                path.addTime(weighting.calcMillis(edge, reverse, prevOrNextEdgeId));
+                path.addEdge(edge.getEdge());
+            }
+        }, true);
+    }
+
+    @Override
+    public int getIncEdge(SPTEntry sptEntry) {
+        return ((CHEntry) sptEntry).incEdge;
+    }
+
+}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedPathCH.java b/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedPathCH.java
deleted file mode 100644
index 0574ae359..000000000
--- a/core/src/main/java/com/graphhopper/routing/ch/EdgeBasedPathCH.java
+++ /dev/null
@@ -1,39 +0,0 @@
-package com.graphhopper.routing.ch;
-
-import com.graphhopper.routing.weighting.TurnWeighting;
-import com.graphhopper.routing.weighting.Weighting;
-import com.graphhopper.storage.Graph;
-import com.graphhopper.storage.SPTEntry;
-import com.graphhopper.storage.ShortcutUnpacker;
-import com.graphhopper.util.EdgeIteratorState;
-
-
-public class EdgeBasedPathCH extends Path4CH {
-
-    private final TurnWeighting turnWeighting;
-
-    public EdgeBasedPathCH(Graph routingGraph, Graph baseGraph, final Weighting weighting) {
-        super(routingGraph, baseGraph, weighting);
-        if (!(weighting instanceof TurnWeighting)) {
-            throw new IllegalArgumentException("Need a TurnWeighting for edge-based CH");
-        }
-        turnWeighting = (TurnWeighting) weighting;
-    }
-
-    @Override
-    protected ShortcutUnpacker getShortcutUnpacker(Graph routingGraph, final Weighting weighting) {
-        return new ShortcutUnpacker(routingGraph, new ShortcutUnpacker.Visitor() {
-            @Override
-            public void visit(EdgeIteratorState edge, boolean reverse, int prevOrNextEdgeId) {
-                distance += edge.getDistance();
-                time += turnWeighting.calcMillis(edge, reverse, prevOrNextEdgeId);
-                addEdge(edge.getEdge());
-            }
-        }, true);
-    }
-
-    @Override
-    protected int getIncEdge(SPTEntry entry) {
-        return ((CHEntry) entry).incEdge;
-    }
-}
diff --git a/core/src/main/java/com/graphhopper/routing/ch/Path4CH.java b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedCHBidirPathExtractor.java
similarity index 59%
rename from core/src/main/java/com/graphhopper/routing/ch/Path4CH.java
rename to core/src/main/java/com/graphhopper/routing/ch/NodeBasedCHBidirPathExtractor.java
index e77cadf5d..be8fc1adb 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/Path4CH.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/NodeBasedCHBidirPathExtractor.java
@@ -15,9 +15,10 @@
  *  See the License for the specific language governing permissions and
  *  limitations under the License.
  */
+
 package com.graphhopper.routing.ch;
 
-import com.graphhopper.routing.PathBidirRef;
+import com.graphhopper.routing.BidirPathExtractor;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
 import com.graphhopper.storage.ShortcutUnpacker;
@@ -25,33 +26,30 @@ import com.graphhopper.util.EdgeIteratorState;
 
 import static com.graphhopper.util.EdgeIterator.NO_EDGE;
 
-public class Path4CH extends PathBidirRef {
+public class NodeBasedCHBidirPathExtractor extends BidirPathExtractor {
     private final ShortcutUnpacker shortcutUnpacker;
 
-    public Path4CH(Graph routingGraph, Graph baseGraph, final Weighting weighting) {
+    public NodeBasedCHBidirPathExtractor(Graph routingGraph, Graph baseGraph, Weighting weighting) {
         super(baseGraph, weighting);
-        this.shortcutUnpacker = getShortcutUnpacker(routingGraph, weighting);
-    }
-
-    @Override
-    protected final void processEdge(int edgeId, int adjNode, int prevEdgeId) {
-        // Shortcuts do only contain valid weight so first expand before adding
-        // to distance and time
-        shortcutUnpacker.visitOriginalEdgesFwd(edgeId, adjNode, true, prevEdgeId);
+        shortcutUnpacker = createShortcutUnpacker(routingGraph, weighting);
     }
 
     @Override
-    protected void processEdgeBwd(int edgeId, int adjNode, int nextEdgeId) {
-        shortcutUnpacker.visitOriginalEdgesBwd(edgeId, adjNode, true, nextEdgeId);
+    public void onEdge(int edge, int adjNode, boolean reverse, int prevOrNextEdge) {
+        if (reverse) {
+            shortcutUnpacker.visitOriginalEdgesBwd(edge, adjNode, true, prevOrNextEdge);
+        } else {
+            shortcutUnpacker.visitOriginalEdgesFwd(edge, adjNode, true, prevOrNextEdge);
+        }
     }
 
-    protected ShortcutUnpacker getShortcutUnpacker(Graph routingGraph, final Weighting weighting) {
+    private ShortcutUnpacker createShortcutUnpacker(Graph routingGraph, final Weighting weighting) {
         return new ShortcutUnpacker(routingGraph, new ShortcutUnpacker.Visitor() {
             @Override
             public void visit(EdgeIteratorState edge, boolean reverse, int prevOrNextEdgeId) {
-                distance += edge.getDistance();
-                time += weighting.calcMillis(edge, reverse, NO_EDGE);
-                addEdge(edge.getEdge());
+                path.addDistance(edge.getDistance());
+                path.addTime(weighting.calcMillis(edge, reverse, NO_EDGE));
+                path.addEdge(edge.getEdge());
             }
         }, false);
     }
diff --git a/isochrone/src/main/java/com/graphhopper/isochrone/algorithm/Isochrone.java b/isochrone/src/main/java/com/graphhopper/isochrone/algorithm/Isochrone.java
index 05b02a36f..83dbc732f 100644
--- a/isochrone/src/main/java/com/graphhopper/isochrone/algorithm/Isochrone.java
+++ b/isochrone/src/main/java/com/graphhopper/isochrone/algorithm/Isochrone.java
@@ -22,6 +22,7 @@ import com.carrotsearch.hppc.procedures.IntObjectProcedure;
 import com.graphhopper.coll.GHIntObjectHashMap;
 import com.graphhopper.routing.AbstractRoutingAlgorithm;
 import com.graphhopper.routing.Path;
+import com.graphhopper.routing.PathExtractor;
 import com.graphhopper.routing.util.TraversalMode;
 import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.Graph;
@@ -291,7 +292,7 @@ public class Isochrone extends AbstractRoutingAlgorithm {
         if (currEdge == null || !finished()) {
             return createEmptyPath();
         }
-        return new Path(graph, weighting).setSPTEntry(currEdge).extract();
+        return PathExtractor.extractPath(graph, weighting, currEdge);
     }
 
     @Override


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java b/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
index 7e79aa6dd..8594b4ea6 100644
--- a/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
+++ b/core/src/test/java/com/graphhopper/routing/AStarBidirectionTest.java
@@ -94,7 +94,6 @@ public class AStarBidirectionTest extends AbstractRoutingAlgorithmTester {
                 toRef.set(currTo);
             }
         };
-        astar.createAndInitPath();
         astar.init(0, 1, 1, 0.5);
 
         assertEquals(1, ((AStar.AStarEntry) fromRef.get()).weightOfVisitedPath, .1);
diff --git a/core/src/test/java/com/graphhopper/routing/PathBidirRefTest.java b/core/src/test/java/com/graphhopper/routing/BidirPathExtractorTest.java
similarity index 78%
rename from core/src/test/java/com/graphhopper/routing/PathBidirRefTest.java
rename to core/src/test/java/com/graphhopper/routing/BidirPathExtractorTest.java
index 6ee7677a5..0c7e346a5 100644
--- a/core/src/test/java/com/graphhopper/routing/PathBidirRefTest.java
+++ b/core/src/test/java/com/graphhopper/routing/BidirPathExtractorTest.java
@@ -34,8 +34,9 @@ import static org.junit.Assert.assertEquals;
 
 /**
  * @author Peter Karich
+ * @author easbar
  */
-public class PathBidirRefTest {
+public class BidirPathExtractorTest {
     private FlagEncoder carEncoder = new CarFlagEncoder(5, 5, 10);
     private final EncodingManager encodingManager = EncodingManager.create(carEncoder);
 
@@ -47,11 +48,10 @@ public class PathBidirRefTest {
     public void testExtract() {
         Graph g = createGraph();
         g.edge(1, 2, 10, true);
-        PathBidirRef p = new PathBidirRef(g, new FastestWeighting(carEncoder));
-        p.sptEntry = new SPTEntry(0, 2, 0);
-        p.sptEntry.parent = new SPTEntry(EdgeIterator.NO_EDGE, 1, 10);
-        p.edgeTo = new SPTEntry(EdgeIterator.NO_EDGE, 2, 0);
-        p.extract();
+        SPTEntry fwdEntry = new SPTEntry(0, 2, 0);
+        fwdEntry.parent = new SPTEntry(EdgeIterator.NO_EDGE, 1, 10);
+        SPTEntry bwdEntry = new SPTEntry(EdgeIterator.NO_EDGE, 2, 0);
+        Path p = BidirPathExtractor.extractPath(g, new FastestWeighting(carEncoder), fwdEntry, bwdEntry, 0);
         assertEquals(IntArrayList.from(1, 2), p.calcNodes());
         assertEquals(10, p.getDistance(), 1e-4);
     }
@@ -67,15 +67,15 @@ public class PathBidirRefTest {
         TurnCostExtension turnCostExtension = (TurnCostExtension) g.getExtension();
         turnCostExtension.addTurnInfo(0, 2, 1, carEncoder.getTurnFlags(false, 5));
 
-        PathBidirRef p = new PathBidirRef(g, new TurnWeighting(new FastestWeighting(carEncoder), turnCostExtension));
-        p.sptEntry = new SPTEntry(0, 2, 0.6);
-        p.sptEntry.parent = new SPTEntry(EdgeIterator.NO_EDGE, 1, 0);
+        SPTEntry fwdEntry = new SPTEntry(0, 2, 0.6);
+        fwdEntry.parent = new SPTEntry(EdgeIterator.NO_EDGE, 1, 0);
 
-        p.edgeTo = new SPTEntry(1, 2, 1.2);
-        p.edgeTo.parent = new SPTEntry(EdgeIterator.NO_EDGE, 3, 0);
+        SPTEntry bwdEntry = new SPTEntry(1, 2, 1.2);
+        bwdEntry.parent = new SPTEntry(EdgeIterator.NO_EDGE, 3, 0);
+
+        Path p = BidirPathExtractor.extractPath(g, new TurnWeighting(new FastestWeighting(carEncoder), turnCostExtension), fwdEntry, bwdEntry, 0);
         p.setWeight(5 + 1.8);
 
-        p.extract();
         assertEquals(IntArrayList.from(1, 2, 3), p.calcNodes());
         assertEquals(30, p.getDistance(), 1e-4);
         assertEquals(5 + 1.8, p.getWeight(), 1e-4);
diff --git a/core/src/test/java/com/graphhopper/routing/PathTest.java b/core/src/test/java/com/graphhopper/routing/PathTest.java
index f816aa4de..baf8ae858 100644
--- a/core/src/test/java/com/graphhopper/routing/PathTest.java
+++ b/core/src/test/java/com/graphhopper/routing/PathTest.java
@@ -25,6 +25,7 @@ import com.graphhopper.routing.util.*;
 import com.graphhopper.routing.weighting.FastestWeighting;
 import com.graphhopper.routing.weighting.GenericWeighting;
 import com.graphhopper.routing.weighting.ShortestWeighting;
+import com.graphhopper.routing.weighting.Weighting;
 import com.graphhopper.storage.*;
 import com.graphhopper.util.*;
 import com.graphhopper.util.details.PathDetail;
@@ -79,12 +80,10 @@ public class PathTest {
         EdgeIteratorState edge2 = g.edge(2, 1).setDistance(2000).set(carAccessEnc, true).setReverse(carAccessEnc, true).set(carAvSpeedEnv, 50.0);
         edge2.setWayGeometry(Helper.createPointList(11, 1, 10, 1));
 
-        Path path = new Path(g, new FastestWeighting(encoder));
         SPTEntry e1 = new SPTEntry(edge2.getEdge(), 2, 1);
         e1.parent = new SPTEntry(edge1.getEdge(), 1, 1);
         e1.parent.parent = new SPTEntry(-1, 0, 1);
-        path.setSPTEntry(e1);
-        path.extract();
+        Path path = extractPath(g, new FastestWeighting(encoder), e1);
         // 0-1-2
         assertPList(Helper.createPointList(0, 0.1, 8, 1, 9, 1, 1, 0.1, 10, 1, 11, 1, 2, 0.1), path.calcPoints());
         InstructionList instr = path.calcInstructions(carManagerRoundabout, tr);
@@ -116,12 +115,10 @@ public class PathTest {
         na.setNode(3, 1.0, 1.0);
         g.edge(1, 3).setDistance(1000).set(carAccessEnc, true).setReverse(carAccessEnc, true).set(carAvSpeedEnv, 10.0);
 
-        path = new Path(g, new FastestWeighting(encoder));
         e1 = new SPTEntry(edge2.getEdge(), 2, 1);
         e1.parent = new SPTEntry(edge1.getEdge(), 1, 1);
         e1.parent.parent = new SPTEntry(-1, 0, 1);
-        path.setSPTEntry(e1);
-        path.extract();
+        path = extractPath(g, new FastestWeighting(encoder), e1);
         instr = path.calcInstructions(carManagerRoundabout, tr);
 
         tmp = instr.get(0);
@@ -142,12 +139,10 @@ public class PathTest {
         assertEquals(path.calcPoints().size() - 1, acc);
 
         // now reverse order
-        path = new Path(g, new FastestWeighting(encoder));
         e1 = new SPTEntry(edge1.getEdge(), 0, 1);
         e1.parent = new SPTEntry(edge2.getEdge(), 1, 1);
         e1.parent.parent = new SPTEntry(-1, 2, 1);
-        path.setSPTEntry(e1);
-        path.extract();
+        path = extractPath(g, new FastestWeighting(encoder), e1);
         // 2-1-0
         assertPList(Helper.createPointList(2, 0.1, 11, 1, 10, 1, 1, 0.1, 9, 1, 8, 1, 0, 0.1), path.calcPoints());
 
@@ -199,14 +194,12 @@ public class PathTest {
         g.edge(2, 5).setDistance(10000).set(carAccessEnc, true).setReverse(carAccessEnc, true).set(carAvSpeedEnv, 50.0);
         g.edge(3, 5).setDistance(100000).set(carAccessEnc, true).setReverse(carAccessEnc, true).set(carAvSpeedEnv, 50.0);
 
-        Path path = new Path(g, new FastestWeighting(encoder));
         SPTEntry e1 = new SPTEntry(edge4.getEdge(), 4, 1);
         e1.parent = new SPTEntry(edge3.getEdge(), 3, 1);
         e1.parent.parent = new SPTEntry(edge2.getEdge(), 2, 1);
         e1.parent.parent.parent = new SPTEntry(edge1.getEdge(), 1, 1);
         e1.parent.parent.parent.parent = new SPTEntry(-1, 0, 1);
-        path.setSPTEntry(e1);
-        path.extract();
+        Path path = extractPath(g, new FastestWeighting(encoder), e1);
 
         InstructionList il = path.calcInstructions(carManagerRoundabout, tr);
         Instruction nextInstr0 = il.find(-0.001, 0.0, 1000);
@@ -1026,4 +1019,8 @@ public class PathTest {
         }
     }
 
+    private static Path extractPath(Graph graph, Weighting weighting, SPTEntry sptEntry) {
+        return PathExtractor.extractPath(graph, weighting, sptEntry);
+    }
+
 }