# UNDF: UNDF-2026-000000407
# graphhopper-0001: AlternativeRouteCH — IntArrayList.contains() O(P) inside edge loop

## File
`core/src/main/java/com/graphhopper/routing/AlternativeRouteCH.java`

## Severity
**HIGH**

## Lines Affected
- Line 174: `alternatives.get(0).nodes.contains()` × 2 — inside per-edge loop
- Lines 182–187: `nodesInCurrentAlternativeSetContains()` — O(A×P) per edge call

## Defective Code

```java
// Line 159–168 — sharedDistance() — O(E × A × P) total
private double sharedDistance(Path path) {
    double sharedDistance = 0.0;
    List<EdgeIteratorState> edges = path.calcEdges();
    for (EdgeIteratorState edge : edges) {
        if (nodesInCurrentAlternativeSetContains(edge.getBaseNode()) && nodesInCurrentAlternativeSetContains(edge.getAdjNode())) {
            sharedDistance += edge.getDistance();
        }
    }
    return sharedDistance;
}

// Line 170–178 — sharedDistanceWithShortest() — O(E × P) total
private double sharedDistanceWithShortest(Path path) {
    double sharedDistance = 0.0;
    List<EdgeIteratorState> edges = path.calcEdges();
    for (EdgeIteratorState edge : edges) {
        if (alternatives.get(0).nodes.contains(edge.getBaseNode()) && alternatives.get(0).nodes.contains(edge.getAdjNode())) {
            sharedDistance += edge.getDistance();
        }
    }
    return sharedDistance;
}

// Line 181–188 — nodesInCurrentAlternativeSetContains() — O(A × P) per call
private boolean nodesInCurrentAlternativeSetContains(int v) {
    for (AlternativeInfo alternative : alternatives) {
        if (alternative.nodes.contains(v)) {   // IntArrayList.contains() = O(P) linear scan
            return true;
        }
    }
    return false;
}
```

`AlternativeInfo.nodes` is assigned from `path.calcNodes()` which returns an `IntArrayList`
(HPPC). `IntArrayList.contains()` is a linear scan over the node list — O(P) per call where
P = path length (number of nodes on the path).

## Root Cause
`Path.calcNodes()` returns `IntArrayList` (an indexed array list), not a hash set.
`AlternativeInfo` stores the result as `IntIndexedContainer` — the declared interface — which
does not prevent linear-scan `contains()`. Every edge shared-distance calculation performs
O(P) membership tests, called O(E) times per path evaluation, with up to A alternatives.

## Complexity Analysis
| Path | Per-call | Total calls | Overall |
|------|----------|-------------|---------|
| Slow (IntArrayList.contains) | O(P) | O(E × A) | **O(E × A × P)** |
| Fast (IntScatterSet.contains) | O(1) | O(E × A) | **O(E × A)** |

For a 1000-edge route with paths of 800 nodes and 3 alternatives: slow = 2,400,000 comparisons
vs fast = 3,000 comparisons — **800× speedup**.

## Fixed Code

```java
import com.carrotsearch.hppc.IntScatterSet;
import com.carrotsearch.hppc.IntSet;

// In AlternativeInfo inner class — store node set alongside node list:
public static class AlternativeInfo {
    final double shareWeight;
    final Path path;
    final IntIndexedContainer nodes;
    final IntSet nodeSet;   // ADD: O(1) lookup set

    AlternativeInfo(Path path, double shareWeight) {
        this.path = path;
        this.shareWeight = shareWeight;
        this.nodes = path.calcNodes();
        // Build O(1) lookup set from the node list
        IntScatterSet set = new IntScatterSet(nodes.size());
        for (int i = 0; i < nodes.size(); i++) {
            set.add(nodes.get(i));
        }
        this.nodeSet = set;
    }
}

// sharedDistanceWithShortest — use nodeSet instead of nodes
private double sharedDistanceWithShortest(Path path) {
    double sharedDistance = 0.0;
    List<EdgeIteratorState> edges = path.calcEdges();
    for (EdgeIteratorState edge : edges) {
        if (alternatives.get(0).nodeSet.contains(edge.getBaseNode())
                && alternatives.get(0).nodeSet.contains(edge.getAdjNode())) {
            sharedDistance += edge.getDistance();
        }
    }
    return sharedDistance;
}

// nodesInCurrentAlternativeSetContains — use nodeSet
private boolean nodesInCurrentAlternativeSetContains(int v) {
    for (AlternativeInfo alternative : alternatives) {
        if (alternative.nodeSet.contains(v)) {   // O(1) hash lookup
            return true;
        }
    }
    return false;
}
```
