# UNDF: UNDF-2026-000000408
# graphhopper-0002: AlternativeRouteEdgeCH — IntArrayList.contains() O(P) inside edge loop

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

## Severity
**HIGH**

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

## Defective Code

```java
// sharedDistanceWithShortest() — O(E × P) per call
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;
}

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

## Root Cause
Identical to graphhopper-0001. This is the edge-based CH variant of the same algorithm.
`AlternativeInfo.nodes` is an `IntArrayList` backed by `Path.calcNodes()`. Every call to
`contains()` performs a linear scan over path nodes.

## 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)** |

## Fixed Code

Same fix as graphhopper-0001: add an `IntScatterSet nodeSet` field to `AlternativeInfo`,
populate it at construction time from `nodes`, and use `nodeSet.contains()` in all
membership test calls.

```java
public static class AlternativeInfo {
    final double shareWeight;
    final Path path;
    final IntIndexedContainer nodes;
    final IntSet nodeSet;  // ADD

    AlternativeInfo(Path path, double shareWeight) {
        this.path = path;
        this.shareWeight = shareWeight;
        this.nodes = path.calcNodes();
        IntScatterSet set = new IntScatterSet(nodes.size());
        for (int i = 0; i < nodes.size(); i++) set.add(nodes.get(i));
        this.nodeSet = set;
    }
}
```

Replace all `alternative.nodes.contains(v)` and `alternatives.get(0).nodes.contains(x)` with
the corresponding `nodeSet.contains()` calls.
