#!/usr/bin/env python3
# Source: q2-stats-probability.html
import random
from typing import Iterable, TypeVar

T = TypeVar("T")


def reservoir_sample(stream: Iterable[T], k: int, seed: int | None = None) -> list[T]:
    """Return k items chosen uniformly at random from a stream.

    Each item ends up in the result with probability k / n, where n is the
    stream length. One pass, O(k) memory, O(1) work per item.

    Args:
        stream: Any iterable. Its length need not be known.
        k: Sample size. Must be at least 1.
        seed: Optional seed for reproducible tests.

    Returns:
        A list of min(k, n) items.
    """
    if k < 1:
        raise ValueError("k must be at least 1")
    rng = random.Random(seed)
    reservoir: list[T] = []

    for i, item in enumerate(stream, start=1):   # i is the 1-based position
        if i <= k:
            reservoir.append(item)               # fill the first k slots
        else:
            j = rng.randint(1, i)                # uniform on 1..i
            if j <= k:                           # true with chance k / i
                reservoir[j - 1] = item          # j is also a uniform slot
    return reservoir
