# lonline_nb.py
import math

def lonline_network_benchmarking(network, path_list, bounces, C_budget, return_details=False):
    """
    L-Online 風の逐次削除型 NB。

    返り値（常に一貫）:
      return_details=False:
        (correctness: bool, cost: int, best_path_fidelity: float|None)
      return_details=True:
        (correctness: bool, cost: int, best_path_fidelity: float|None,
         alloc_by_path: dict[int,int], est_fid_by_path: dict[int,float])

    想定 I/F:
      network.benchmark_path(path, bounces, sample_times) -> (p, used_cost)
      忠実度変換: fidelity = p + (1 - p)/2
    """
    candidate_set = list(path_list)
    # 既存コード由来のパラメータ（必要に応じて合わせてください）
    s = 0
    C = 0.01
    delta = 0.1

    # 集計器
    cost = 0
    estimated_fidelities = {}

    # 詳細返却用の器（return_details に関わらず初期化：どの分岐でも形を揃える）
    alloc_by_path = {int(p): 0 for p in path_list}
    est_fid_by_path = {}

    if not candidate_set or C_budget <= 0:
        # 何も測れないケースでも形は揃えて返す
        if return_details:
            return False, int(cost), None, alloc_by_path, est_fid_by_path
        return False, int(cost), None

    # 1 経路を 1 サンプル測るコストの近似（ここでは hop 重みの和）
    cost_per_sample_unit = sum(bounces) if sum(bounces) > 0 else 1

    # ---- メインループ ----
    while cost < C_budget and len(candidate_set) > 1:
        s += 1
        # ラウンド s のサンプル回数（既存式）
        Ns = math.ceil(C * (2 ** (2 * s)) * math.log2(max((2 ** s) * len(candidate_set) / delta, 2)))
        if Ns < 4:
            Ns = 4

        # このラウンドで 1 経路に必要なコスト目安
        cost_needed_for_one_path = Ns * cost_per_sample_unit

        # 2 ラウンド目以降で 1 経路すら回せないなら終了
        if cost + cost_needed_for_one_path > C_budget and s > 1:
            break

        # hop ごとに同じ Ns を配る（network 側の想定 I/F に合わせる）
        sample_times = {h: int(Ns) for h in bounces}

        # ラウンド内の観測
        p_s = {}
        measured_paths = []

        for path in list(candidate_set):
            if cost + cost_needed_for_one_path > C_budget:
                continue  # 予算が入らない経路はこのラウンドでは測らない

            # 実測
            p, used = network.benchmark_path(path, bounces, sample_times)
            cost += int(used)

            # 忠実度推定を更新（既存式）
            fidelity = p + (1 - p) / 2.0
            estimated_fidelities[path] = fidelity
            p_s[path] = p
            measured_paths.append(path)

            # 詳細集計
            alloc_by_path[int(path)] = alloc_by_path.get(int(path), 0) + int(used)
            est_fid_by_path[int(path)] = float(fidelity)

        # このラウンドで 1 本も測れなかったら終了
        if not p_s:
            break

        # 連続削除（幅 2^{-s}）
        p_max = max(p_s.values())
        new_candidate_set = []
        for path in measured_paths:
            if p_s[path] + 2 ** (-s) > p_max - 2 ** (-s):
                new_candidate_set.append(path)

        # 全消し回避：空になったら据え置き
        candidate_set = new_candidate_set or candidate_set

    # 1 本も推定できなかった場合
    if not estimated_fidelities:
        if return_details:
            return False, int(cost), None, alloc_by_path, est_fid_by_path
        return False, int(cost), None

    # 最良推定パスと正解判定
    best_path = max(estimated_fidelities, key=estimated_fidelities.get)
    best_path_fidelity = estimated_fidelities[best_path]
    correctness = (best_path == getattr(network, "best_path", None))

    if return_details:
        return bool(correctness), int(cost), best_path_fidelity, alloc_by_path, est_fid_by_path
    return bool(correctness), int(cost), best_path_fidelity


# 互換用エイリアス（古い呼び名を使っているコード向け）
lonline_network_benchmarking_with_budget = lonline_network_benchmarking