Repository: graphhopper/graphhopper
Pull request #2169 (2020-11-02 22:35:13)

Replace split 2D array with linked list for CHPreparationGraph
Slightly reduces memory usage during CH preparation


Patch:
diff --git a/core/src/main/java/com/graphhopper/routing/ch/CHPreparationGraph.java b/core/src/main/java/com/graphhopper/routing/ch/CHPreparationGraph.java
index eb9189d1e..8c784066b 100644
--- a/core/src/main/java/com/graphhopper/routing/ch/CHPreparationGraph.java
+++ b/core/src/main/java/com/graphhopper/routing/ch/CHPreparationGraph.java
@@ -44,12 +44,12 @@ public class CHPreparationGraph {
     private final int edges;
     private final boolean edgeBased;
     private final TurnCostFunction turnCostFunction;
-    // each edge/shortcut between nodes a/b is represented as a single object and we maintain a list of references
-    // to these objects at every node. this needs to be memory-efficient especially for node-based (because there
-    // are less shortcuts overall so the size of the prepare graph is crucial, while for edge-based most memory is
-    // consumed towards the end of the preparation anyway). for edge-based it would actually be better/faster to keep
-    // separate lists of incoming/outgoing edges and even use uni-directional edge-objects.
-    private SplitArray2D<PrepareEdge> prepareEdges;
+    // each edge/shortcut between nodes a/b is represented as a single object and we maintain two linked lists of such
+    // objects for every node (one for outgoing edges and one for incoming edges).
+    private PrepareEdge[] prepareEdgesOut;
+    private PrepareEdge[] prepareEdgesIn;
+    // todo: maybe we can get rid of this
+    private int[] degrees;
     private IntSet neighborSet;
     private OrigGraph origGraph;
     private OrigGraph.Builder origGraphBuilder;
@@ -74,7 +74,9 @@ public class CHPreparationGraph {
         this.nodes = nodes;
         this.edges = edges;
         this.edgeBased = edgeBased;
-        prepareEdges = new SplitArray2D<>(nodes, 2);
+        prepareEdgesOut = new PrepareEdge[nodes];
+        prepareEdgesIn = new PrepareEdge[nodes];
+        degrees = new int[nodes];
         origGraphBuilder = edgeBased ? new OrigGraph.Builder() : null;
         neighborSet = new IntHashSet();
         nextShortcutId = edges;
@@ -166,7 +168,7 @@ public class CHPreparationGraph {
     }
 
     public int getDegree(int node) {
-        return prepareEdges.size(node);
+        return degrees[node];
     }
 
     public void addEdge(int from, int to, int edge, double weightFwd, double weightBwd) {
@@ -202,7 +204,6 @@ public class CHPreparationGraph {
 
     public void prepareForContraction() {
         checkNotReady();
-        prepareEdges.trimToSize();
         origGraph = edgeBased ? origGraphBuilder.build() : null;
         origGraphBuilder = null;
         ready = true;
@@ -210,12 +211,12 @@ public class CHPreparationGraph {
 
     public PrepareGraphEdgeExplorer createOutEdgeExplorer() {
         checkReady();
-        return new PrepareGraphEdgeExplorerImpl(prepareEdges, false);
+        return new PrepareGraphEdgeExplorerImpl(prepareEdgesOut, false);
     }
 
     public PrepareGraphEdgeExplorer createInEdgeExplorer() {
         checkReady();
-        return new PrepareGraphEdgeExplorerImpl(prepareEdges, true);
+        return new PrepareGraphEdgeExplorerImpl(prepareEdgesIn, true);
     }
 
     public PrepareGraphOrigEdgeExplorer createOutOrigEdgeExplorer() {
@@ -242,36 +243,98 @@ public class CHPreparationGraph {
         // node ids
         neighborSet.clear();
         IntArrayList neighbors = new IntArrayList(getDegree(node));
-        for (int i = 0; i < prepareEdges.size(node); i++) {
-            PrepareEdge prepareEdge = prepareEdges.get(node, i);
-            int adjNode = prepareEdge.getNodeB();
+        PrepareEdge currOut = prepareEdgesOut[node];
+        while (currOut != null) {
+            int adjNode = currOut.getNodeB();
             if (adjNode == node)
-                adjNode = prepareEdge.getNodeA();
+                adjNode = currOut.getNodeA();
+            if (adjNode == node) {
+                // this is a loop
+                currOut = currOut.getNextOut(node);
+                continue;
+            }
+            removeInEdge(adjNode, currOut);
+            if (neighborSet.add(adjNode))
+                neighbors.add(adjNode);
+            currOut = currOut.getNextOut(node);
+        }
+        PrepareEdge currIn = prepareEdgesIn[node];
+        while (currIn != null) {
+            int adjNode = currIn.getNodeB();
             if (adjNode == node)
+                adjNode = currIn.getNodeA();
+            if (adjNode == node) {
                 // this is a loop
+                currIn = currIn.getNextIn(node);
                 continue;
-            prepareEdges.remove(adjNode, prepareEdge);
+            }
+            removeOutEdge(adjNode, currIn);
             if (neighborSet.add(adjNode))
                 neighbors.add(adjNode);
+            currIn = currIn.getNextIn(node);
         }
-        prepareEdges.clear(node);
+        prepareEdgesOut[node] = null;
+        prepareEdgesIn[node] = null;
+        degrees[node] = 0;
         return neighbors;
     }
 
+    private void removeOutEdge(int node, PrepareEdge prepareEdge) {
+        PrepareEdge prevOut = null;
+        PrepareEdge currOut = prepareEdgesOut[node];
+        while (currOut != null) {
+            if (currOut == prepareEdge) {
+                if (prevOut == null) {
+                    prepareEdgesOut[node] = currOut.getNextOut(node);
+                } else {
+                    prevOut.setNextOut(node, currOut.getNextOut(node));
+                }
+                degrees[node]--;
+            } else {
+                prevOut = currOut;
+            }
+            currOut = currOut.getNextOut(node);
+        }
+    }
+
+    private void removeInEdge(int node, PrepareEdge prepareEdge) {
+        PrepareEdge prevIn = null;
+        PrepareEdge currIn = prepareEdgesIn[node];
+        while (currIn != null) {
+            if (currIn == prepareEdge) {
+                if (prevIn == null) {
+                    prepareEdgesIn[node] = currIn.getNextIn(node);
+                } else {
+                    prevIn.setNextIn(node, currIn.getNextIn(node));
+                }
+                degrees[node]--;
+            } else {
+                prevIn = currIn;
+            }
+            currIn = currIn.getNextIn(node);
+        }
+    }
+
     public void close() {
         checkReady();
-        prepareEdges = null;
+        prepareEdgesOut = null;
+        prepareEdgesIn = null;
+        degrees = null;
         neighborSet = null;
         if (edgeBased)
             origGraph = null;
     }
 
     private void addOutEdge(int node, PrepareEdge prepareEdge) {
-        prepareEdges.addPartTwo(node, prepareEdge);
+        prepareEdge.setNextOut(node, prepareEdgesOut[node]);
+        prepareEdgesOut[node] = prepareEdge;
+        degrees[node]++;
     }
 
     private void addInEdge(int node, PrepareEdge prepareEdge) {
-        prepareEdges.addPartOne(node, prepareEdge);
+        prepareEdge.setNextIn(node, prepareEdgesIn[node]);
+        prepareEdgesIn[node] = prepareEdge;
+        degrees[node]++;
     }
 
     private void checkReady() {
@@ -290,14 +353,13 @@ public class CHPreparationGraph {
     }
 
     private static class PrepareGraphEdgeExplorerImpl implements PrepareGraphEdgeExplorer, PrepareGraphEdgeIterator {
-        private final SplitArray2D<PrepareEdge> prepareEdges;
+        private final PrepareEdge[] prepareEdges;
         private final boolean reverse;
         private int node = -1;
-        private int end;
         private PrepareEdge currEdge;
-        private int index;
+        private PrepareEdge nextEdge;
 
-        PrepareGraphEdgeExplorerImpl(SplitArray2D<PrepareEdge> prepareEdges, boolean reverse) {
+        PrepareGraphEdgeExplorerImpl(PrepareEdge[] prepareEdges, boolean reverse) {
             this.prepareEdges = prepareEdges;
             this.reverse = reverse;
         }
@@ -305,20 +367,17 @@ public class CHPreparationGraph {
         @Override
         public PrepareGraphEdgeIterator setBaseNode(int node) {
             this.node = node;
-            // we store the in edges in the first and the out edges in the second part of the prepareEdges
-            this.index = reverse ? -1 : (prepareEdges.mid(node) - 1);
-            this.end = reverse ? prepareEdges.mid(node) : prepareEdges.size(node);
+            currEdge = null;
+            nextEdge = prepareEdges[node];
             return this;
         }
 
         @Override
         public boolean next() {
-            index++;
-            if (index == end) {
-                currEdge = null;
+            currEdge = nextEdge;
+            if (currEdge == null)
                 return false;
-            }
-            currEdge = prepareEdges.get(node, index);
+            nextEdge = reverse ? currEdge.getNextIn(node) : currEdge.getNextOut(node);
             return true;
         }
 
@@ -438,6 +497,15 @@ public class CHPreparationGraph {
         void setWeight(double weight);
 
         void setOrigEdgeCount(int origEdgeCount);
+
+        PrepareEdge getNextOut(int base);
+
+        void setNextOut(int base, PrepareEdge prepareEdge);
+
+        PrepareEdge getNextIn(int base);
+
+        void setNextIn(int base, PrepareEdge prepareEdge);
+
     }
 
     public static class PrepareBaseEdge implements PrepareEdge {
@@ -446,6 +514,10 @@ public class CHPreparationGraph {
         private final int nodeB;
         private final float weightAB;
         private final float weightBA;
+        private PrepareEdge nextOutA;
+        private PrepareEdge nextOutB;
+        private PrepareEdge nextInA;
+        private PrepareEdge nextInB;
 
         public PrepareBaseEdge(int prepareEdge, int nodeA, int nodeB, float weightAB, float weightBA) {
             this.prepareEdge = prepareEdge;
@@ -542,6 +614,46 @@ public class CHPreparationGraph {
             throw new UnsupportedOperationException();
         }
 
+        @Override
+        public PrepareEdge getNextOut(int base) {
+            if (base == nodeA)
+                return nextOutA;
+            else if (base == nodeB)
+                return nextOutB;
+            else
+                throw new IllegalStateException("Cannot get next out edge as the given base " + base + " is not adjacent to the current edge");
+        }
+
+        @Override
+        public void setNextOut(int base, PrepareEdge prepareEdge) {
+            if (base == nodeA)
+                nextOutA = prepareEdge;
+            else if (base == nodeB)
+                nextOutB = prepareEdge;
+            else
+                throw new IllegalStateException("Cannot set next out edge as the given base " + base + " is not adjacent to the current edge");
+        }
+
+        @Override
+        public PrepareEdge getNextIn(int base) {
+            if (base == nodeA)
+                return nextInA;
+            else if (base == nodeB)
+                return nextInB;
+            else
+                throw new IllegalStateException("Cannot get next in edge as the given base " + base + " is not adjacent to the current edge");
+        }
+
+        @Override
+        public void setNextIn(int base, PrepareEdge prepareEdge) {
+            if (base == nodeA)
+                nextInA = prepareEdge;
+            else if (base == nodeB)
+                nextInB = prepareEdge;
+            else
+                throw new IllegalStateException("Cannot set next in edge as the given base " + base + " is not adjacent to the current edge");
+        }
+
         @Override
         public String toString() {
             return nodeA + "-" + nodeB + " (" + prepareEdge + ") " + weightAB + " " + weightBA;
@@ -556,6 +668,8 @@ public class CHPreparationGraph {
         private int skipped1;
         private int skipped2;
         private int origEdgeCount;
+        private PrepareEdge nextOut;
+        private PrepareEdge nextIn;
 
         private PrepareShortcut(int prepareEdge, int from, int to, double weight, int skipped1, int skipped2, int origEdgeCount) {
             this.prepareEdge = prepareEdge;
@@ -653,6 +767,26 @@ public class CHPreparationGraph {
             this.origEdgeCount = origEdgeCount;
         }
 
+        @Override
+        public PrepareEdge getNextOut(int base) {
+            return nextOut;
+        }
+
+        @Override
+        public void setNextOut(int base, PrepareEdge prepareEdge) {
+            this.nextOut = prepareEdge;
+        }
+
+        @Override
+        public PrepareEdge getNextIn(int base) {
+            return nextIn;
+        }
+
+        @Override
+        public void setNextIn(int base, PrepareEdge prepareEdge) {
+            this.nextIn = prepareEdge;
+        }
+
         @Override
         public String toString() {
             return from + "-" + to + " " + weight;
diff --git a/core/src/main/java/com/graphhopper/routing/ch/SplitArray2D.java b/core/src/main/java/com/graphhopper/routing/ch/SplitArray2D.java
deleted file mode 100644
index cc290920d..000000000
--- a/core/src/main/java/com/graphhopper/routing/ch/SplitArray2D.java
+++ /dev/null
@@ -1,140 +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.ch;
-
-import java.util.Arrays;
-
-/**
- * This is a more memory-efficient version of two equal length `ArrayList<T>[]`s, i.e. this is a fixed size array where
- * each element is a variable sized sub-array and each sub-array is divided into two parts.
- * This is more memory efficient than two arrays of `ArrayList`s, because it saves the object-overhead of using an
- * ArrayList object for each sub-array.
- * <p>
- * The elements in each sub-array are divided into two parts with ranges [0,mid[ and [mid,size[. We can add elements
- * to either of the two parts.
- */
-class SplitArray2D<T> {
-    private static final int GROW_FACTOR = 2;
-    private final int initialSubArrayCapacity;
-    private final Object[][] data;
-    // todo: mids/sizes can probably be combined into a single int to save some memory, but need to check maximum values
-    // checking for Bayern and Germany it seemed like the maximum values were around 50/100 and independent of the
-    // map size
-    private final int[] mids;
-    private final int[] sizes;
-
-    SplitArray2D(int size, int initialSubArrayCapacity) {
-        data = new Object[size][];
-        sizes = new int[size];
-        mids = new int[size];
-        this.initialSubArrayCapacity = initialSubArrayCapacity;
-    }
-
-    int mid(int n) {
-        return mids[n];
-    }
-
-    int size(int n) {
-        return sizes[n];
-    }
-
-    T get(int n, int index) {
-        return (T) data[n][index];
-    }
-
-    /**
-     * Adds the given element to the first part of the n-th sub-array. This changes the order of the existing elements.
-     */
-    void addPartOne(int n, T element) {
-        if (data[n] == null) {
-            data[n] = new Object[initialSubArrayCapacity];
-            data[n][0] = element;
-            mids[n] = 1;
-            sizes[n] = 1;
-        } else {
-            assert data[n].length != 0;
-            if (sizes[n] == data[n].length)
-                grow(n);
-            data[n][sizes[n]] = data[n][mids[n]];
-            data[n][mids[n]] = element;
-            mids[n]++;
-            sizes[n]++;
-        }
-    }
-
-    /**
-     * Adds the given element to the second part of the n-th sub-array. This changes the order of the existing elements.
-     */
-    void addPartTwo(int n, T element) {
-        if (data[n] == null) {
-            data[n] = new Object[initialSubArrayCapacity];
-            data[n][0] = element;
-            sizes[n] = 1;
-        } else {
-            assert data[n].length != 0;
-            if (sizes[n] == data[n].length)
-                grow(n);
-            data[n][sizes[n]] = element;
-            sizes[n]++;
-        }
-    }
-
-    /**
-     * Removes all occurrences of the given element from the given sub-array. Using this method changes the order of the
-     * existing elements in the sub-array unless we remove only the very last element(s)!
-     */
-    void remove(int n, T element) {
-        for (int i = 0; i < mids[n]; ++i) {
-            while (mids[n] > 0 && i < mids[n] && data[n][i] == element) {
-                data[n][i] = data[n][mids[n] - 1];
-                data[n][mids[n] - 1] = data[n][sizes[n] - 1];
-                data[n][sizes[n] - 1] = null;
-                mids[n]--;
-                sizes[n]--;
-            }
-        }
-        for (int i = mids[n]; i < sizes[n]; ++i) {
-            while (sizes[n] > mids[n] && i < sizes[n] && data[n][i] == element) {
-                data[n][i] = data[n][sizes[n] - 1];
-                data[n][sizes[n] - 1] = null;
-                sizes[n]--;
-            }
-        }
-    }
-
-    void clear(int n) {
-        data[n] = null;
-        sizes[n] = 0;
-        mids[n] = 0;
-    }
-
-    private void grow(int n) {
-        // todo: think about grow factor: trimming and then doubling the size might be not what we want, rather
-        // increase by 50% or something?
-        data[n] = Arrays.copyOf(data[n], data[n].length * GROW_FACTOR);
-    }
-
-    void trimToSize() {
-        for (int n = 0; n < data.length; n++) {
-            if (data[n] != null)
-                data[n] = Arrays.copyOf(data[n], sizes[n]);
-        }
-    }
-
-}


Test patch:
diff --git a/core/src/test/java/com/graphhopper/routing/AlternativeRouteEdgeCHTest.java b/core/src/test/java/com/graphhopper/routing/AlternativeRouteEdgeCHTest.java
index 6281fd605..10bcd535a 100644
--- a/core/src/test/java/com/graphhopper/routing/AlternativeRouteEdgeCHTest.java
+++ b/core/src/test/java/com/graphhopper/routing/AlternativeRouteEdgeCHTest.java
@@ -141,9 +141,10 @@ public class AlternativeRouteEdgeCHTest {
         hints.putObject("alternative_route.max_paths", 4);
         AlternativeRouteEdgeCH altDijkstra = new AlternativeRouteEdgeCH(g.getRoutingCHGraph(), hints);
         List<AlternativeRouteEdgeCH.AlternativeInfo> pathInfos = altDijkstra.calcAlternatives(10, 5);
-        assertEquals(2, pathInfos.size());
+        assertEquals(3, pathInfos.size());
         assertEquals(IntArrayList.from(10, 4, 3, 6, 5), pathInfos.get(0).path.calcNodes());
         assertEquals(IntArrayList.from(10, 4, 8, 7, 6, 5), pathInfos.get(1).path.calcNodes());
+        assertEquals(IntArrayList.from(10, 4, 8, 7, 6, 3, 2, 9, 1, 5), pathInfos.get(2).path.calcNodes());
         // The shortest path works (no restrictions on the way back
     }
 
diff --git a/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java b/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java
index 4beaef8d5..6148cb662 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/EdgeBasedNodeContractorTest.java
@@ -553,8 +553,8 @@ public class EdgeBasedNodeContractorTest {
         GraphWithTwoLoops g = new GraphWithTwoLoops(3, maxCost, 1, maxCost, 3, maxCost);
         g.contractAndCheckShortcuts(
                 createShortcut(6, 7, g.e7to6.getEdge(), g.e1to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(3), 13, false, true),
-                createShortcut(6, 7, g.e7to6.getEdge(), g.e3to6.getEdge(), g.getScEdge(4), g.getScEdge(2), 24, false, true),
-                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(5), g.e6to8.getEdge(), 33, true, false)
+                createShortcut(6, 7, g.e7to6.getEdge(), g.e3to6.getEdge(), g.getScEdge(5), g.getScEdge(2), 24, false, true),
+                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(4), g.e6to8.getEdge(), 33, true, false)
         );
     }
 
@@ -564,8 +564,8 @@ public class EdgeBasedNodeContractorTest {
         GraphWithTwoLoops g = new GraphWithTwoLoops(maxCost, 5, 4, 2, maxCost, maxCost);
         g.contractAndCheckShortcuts(
                 createShortcut(6, 7, g.e7to6.getEdge(), g.e3to6.getEdge(), g.e7to6.getEdge(), g.getScEdge(2), 16, false, true),
-                createShortcut(6, 7, g.e7to6.getEdge(), g.e1to6.getEdge(), g.getScEdge(4), g.getScEdge(3), 25, false, true),
-                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(5), g.e6to8.getEdge(), 33, true, false)
+                createShortcut(6, 7, g.e7to6.getEdge(), g.e1to6.getEdge(), g.getScEdge(5), g.getScEdge(3), 25, false, true),
+                createShortcut(7, 8, g.e7to6.getEdge(), g.e6to8.getEdge(), g.getScEdge(4), g.e6to8.getEdge(), 33, true, false)
         );
     }
 
@@ -1056,9 +1056,9 @@ public class EdgeBasedNodeContractorTest {
                 // from node 5 contraction
                 createShortcut(2, 2, 3, 2, 3, 2, 99, true, false),
                 createShortcut(2, 2, 3, 1, 3, 6, 134, true, false),
-                createShortcut(2, 2, 1, 2, 9, 2, 114, true, false),
+                createShortcut(2, 2, 1, 2, 8, 2, 114, true, false),
                 createShortcut(3, 2, 2, 4, 2, 7, 106, false, true),
-                createShortcut(3, 2, 4, 2, 8, 2, 105, true, false)
+                createShortcut(3, 2, 4, 2, 9, 2, 105, true, false)
         );
     }
 
diff --git a/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java b/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
index 6d760cf65..d93fb8d7a 100644
--- a/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
+++ b/core/src/test/java/com/graphhopper/routing/ch/NodeBasedNodeContractorTest.java
@@ -133,8 +133,8 @@ public class NodeBasedNodeContractorTest {
                 expectedShortcut(4, 6, iter8to4, iter6to8, false, true),
                 expectedShortcut(4, 6, iter4to5, iter5to6, true, false),
                 // there should be two different shortcuts for both directions!
-                expectedShortcut(1, 6, lg.getEdgeIteratorState(7, 4), lg.getEdgeIteratorState(8, 6), true, false),
-                expectedShortcut(1, 6, lg.getEdgeIteratorState(7, 1), lg.getEdgeIteratorState(9, 4), false, true)
+                expectedShortcut(1, 6, lg.getEdgeIteratorState(8, 4), lg.getEdgeIteratorState(7, 6), true, false),
+                expectedShortcut(1, 6, lg.getEdgeIteratorState(8, 1), lg.getEdgeIteratorState(9, 4), false, true)
         );
     }
 
diff --git a/core/src/test/java/com/graphhopper/routing/ch/SplitArray2DTest.java b/core/src/test/java/com/graphhopper/routing/ch/SplitArray2DTest.java
deleted file mode 100644
index 3aa75bea9..000000000
--- a/core/src/test/java/com/graphhopper/routing/ch/SplitArray2DTest.java
+++ /dev/null
@@ -1,143 +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.ch;
-
-import com.carrotsearch.hppc.IntArrayList;
-import org.junit.jupiter.api.Test;
-
-import java.util.stream.IntStream;
-
-import static org.junit.jupiter.api.Assertions.assertEquals;
-
-class SplitArray2DTest {
-
-    @Test
-    void basic() {
-        SplitArray2D<Integer> arr = new SplitArray2D<>(5, 1);
-        final int n = 1;
-        IntStream.range(0, 5).forEach(i -> assertEquals(0, arr.size(i)));
-        IntStream.range(0, 5).forEach(i -> assertEquals(0, arr.mid(i)));
-        arr.addPartOne(n, 5);
-        arr.addPartTwo(n, 6);
-        arr.addPartOne(n, 4);
-        arr.addPartTwo(n, 5);
-        arr.addPartTwo(n, 7);
-        arr.addPartTwo(n, 6);
-        assertEquals(2, arr.mid(n));
-        assertEquals(6, arr.size(n));
-        assertEquals(IntArrayList.from(5, 4), getIn(arr, n));
-        assertEquals(IntArrayList.from(6, 5, 7, 6), getOut(arr, n));
-        arr.remove(n, 6);
-        assertEquals(2, arr.mid(n));
-        assertEquals(4, arr.size(n));
-        arr.remove(n, 5);
-        assertEquals(IntArrayList.from(4), getIn(arr, n));
-        assertEquals(IntArrayList.from(7), getOut(arr, n));
-        assertEquals(n, arr.mid(n));
-        assertEquals(2, arr.size(n));
-        arr.clear(n);
-        assertEquals(0, arr.mid(n));
-        assertEquals(0, arr.size(n));
-        arr.addPartTwo(n, 23);
-        arr.addPartOne(n, 17);
-        assertEquals(1, arr.mid(n));
-        assertEquals(2, arr.size(n));
-        assertEquals(17, arr.get(n, 0));
-        assertEquals(23, arr.get(n, 1));
-        assertEquals(IntArrayList.from(17), getIn(arr, n));
-        assertEquals(IntArrayList.from(23), getOut(arr, n));
-    }
-
-    @Test
-    void remove() {
-        SplitArray2D<Integer> arr = new SplitArray2D<>(3, 1);
-        arr.addPartOne(0, 3);
-        arr.addPartOne(0, 2);
-        arr.addPartOne(0, 4);
-        arr.addPartOne(0, 6);
-        arr.addPartTwo(0, 1);
-        arr.addPartTwo(0, 8);
-        arr.addPartTwo(0, 2);
-        assertEquals(IntArrayList.from(3, 2, 4, 6), getIn(arr, 0));
-        assertEquals(IntArrayList.from(1, 8, 2), getOut(arr, 0));
-        arr.remove(0, 2);
-        assertEquals(IntArrayList.from(3, 6, 4), getIn(arr, 0));
-        assertEquals(IntArrayList.from(8, 1), getOut(arr, 0));
-    }
-
-    @Test
-    void remove2() {
-        SplitArray2D<Integer> arr = new SplitArray2D<>(3, 1);
-        arr.addPartOne(0, 3);
-        arr.addPartOne(0, 2);
-        arr.addPartOne(0, 4);
-        arr.addPartOne(0, 4);
-        arr.addPartOne(0, 4);
-        arr.addPartOne(0, 6);
-        arr.addPartOne(0, 4);
-        arr.addPartTwo(0, 1);
-        arr.addPartTwo(0, 3);
-        arr.addPartTwo(0, 2);
-        arr.addPartTwo(0, 1);
-        arr.addPartTwo(0, 1);
-        arr.addPartTwo(0, 4);
-
-        assertEquals(IntArrayList.from(3, 2, 4, 4, 4, 6, 4), getIn(arr, 0));
-        assertEquals(IntArrayList.from(1, 3, 2, 1, 1, 4), getOut(arr, 0));
-        arr.remove(0, 4);
-        assertEquals(IntArrayList.from(3, 2, 6), getIn(arr, 0));
-        assertEquals(IntArrayList.from(2, 1, 1, 3, 1), getOut(arr, 0));
-        arr.remove(0, 1);
-        assertEquals(IntArrayList.from(3, 2, 6), getIn(arr, 0));
-        assertEquals(IntArrayList.from(2, 3), getOut(arr, 0));
-        arr.remove(0, 2);
-        assertEquals(IntArrayList.from(3, 6), getIn(arr, 0));
-        assertEquals(IntArrayList.from(3), getOut(arr, 0));
-    }
-
-    @Test
-    void remove3() {
-        SplitArray2D<Integer> arr = new SplitArray2D<>(3, 1);
-        arr.addPartOne(0, 1);
-        arr.addPartOne(0, 2);
-        arr.addPartTwo(0, 1);
-        arr.addPartTwo(0, 2);
-        assertEquals(IntArrayList.from(1, 2), getIn(arr, 0));
-        assertEquals(IntArrayList.from(1, 2), getOut(arr, 0));
-        arr.remove(0, 2);
-        assertEquals(IntArrayList.from(1), getIn(arr, 0));
-        assertEquals(IntArrayList.from(1), getOut(arr, 0));
-    }
-
-    private IntArrayList getIn(SplitArray2D<Integer> arr, int n) {
-        return getRange(arr, n, 0, arr.mid(n));
-    }
-
-    private IntArrayList getOut(SplitArray2D<Integer> arr, int n) {
-        return getRange(arr, n, arr.mid(n), arr.size(n));
-    }
-
-    private IntArrayList getRange(SplitArray2D<Integer> arr, int n, int start, int end) {
-        IntArrayList res = new IntArrayList(end - start);
-        for (int i = start; i < end; i++) {
-            res.add(arr.get(n, i));
-        }
-        return res;
-    }
-}
\ No newline at end of file
diff --git a/reader-osm/src/test/java/com/graphhopper/GraphHopperTest.java b/reader-osm/src/test/java/com/graphhopper/GraphHopperTest.java
index 19a485c74..ebfd94faf 100644
--- a/reader-osm/src/test/java/com/graphhopper/GraphHopperTest.java
+++ b/reader-osm/src/test/java/com/graphhopper/GraphHopperTest.java
@@ -90,8 +90,8 @@ public class GraphHopperTest {
             ASTAR + ",false,439",
             DIJKSTRA_BI + ",false,208",
             ASTAR_BI + ",false,172",
-            ASTAR_BI + ",true,45",
-            DIJKSTRA_BI + ",true,43"
+            ASTAR_BI + ",true,35",
+            DIJKSTRA_BI + ",true,34"
     })
     public void testMonacoDifferentAlgorithms(String algo, boolean withCH, int expectedVisitedNodes) {
         final String vehicle = "car";