// Optimal block planning (zopfli-style block splitting): the drop-in
// counterpart to the threshold planner in block_planner.mbt. A cheap greedy
// parse of each master chunk provides reference tokens; split points are
// searched by recursive narrowing (zopfli's FindMinimum) and inserted
// greedily while two blocks cost fewer exact bits than one, under a block
// budget. Segments are then re-parsed by the optimal parser, the splitting is
// repeated once on the optimal tokens (zopfli's blocksplittinglast), and the
// cheaper of the two groupings is emitted through the ordinary `emit_block` —
// planner and parser replaced, writer untouched, output standard DEFLATE.

///|
/// Splitting and parsing happen within master chunks of this many input
/// bytes, bounding the planner's working memory (zopfli's MASTER_BLOCK_SIZE
/// plays the same role).
let optimal_master_block = 262144

///|
/// Most blocks the splitter may cut one master chunk into (zopfli's default).
let optimal_max_blocks = 15

///|
/// Exact cost in bits of one block (3-bit header included): the cheapest of
/// stored / fixed / dynamic, mirroring `emit_block`'s accounting. Judges both
/// split candidates and squeeze iterations.
fn block_cost_bits(
  byte_len : Int,
  ll_freq_in : Array[Int],
  d_freq : Array[Int],
) -> Int {
  let ll_freq = Array::make(286, 0)
  for s in 0..<286 {
    ll_freq[s] = ll_freq_in[s]
  }
  ll_freq[256] += 1
  let dll_len = Array::make(286, 0)
  gen_huffman(ll_freq, 286, 15, dll_len)
  let dd_len = Array::make(30, 0)
  gen_huffman(d_freq, 30, 15, dd_len)
  let mut have_dist = false
  for d in 0..<30 {
    if dd_len[d] > 0 {
      have_dist = true
      break
    }
  }
  if !have_dist {
    dd_len[0] = 1
  }
  let mut hlit = 286
  while hlit > 257 && dll_len[hlit - 1] == 0 {
    hlit = hlit - 1
  }
  let mut hdist = 30
  while hdist > 1 && dd_len[hdist - 1] == 0 {
    hdist = hdist - 1
  }
  let codelen_syms = build_codelen_syms(dll_len, hlit, dd_len, hdist)
  let codelen_freq = Array::make(19, 0)
  for it in codelen_syms {
    codelen_freq[it.sym] += 1
  }
  let codelen_code_len = Array::make(19, 0)
  gen_huffman(codelen_freq, 19, 7, codelen_code_len)
  let mut hclen = 19
  while hclen > 4 && codelen_code_len[code_order[hclen - 1]] == 0 {
    hclen = hclen - 1
  }
  let mut dyn_sym = 0
  let mut fixed_sym = 0
  for s in 0..<286 {
    if ll_freq[s] != 0 {
      dyn_sym = dyn_sym + ll_freq[s] * dll_len[s]
      fixed_sym = fixed_sym + ll_freq[s] * (fixed_litlen_info[s] & 0xF)
    }
  }
  for d in 0..<30 {
    if d_freq[d] != 0 {
      dyn_sym = dyn_sym + d_freq[d] * dd_len[d]
      fixed_sym = fixed_sym + d_freq[d] * 5
    }
  }
  let mut extra = 0
  for i in 0..<29 {
    extra = extra + ll_freq[257 + i] * len_extra[i]
  }
  for d in 0..<30 {
    extra = extra + d_freq[d] * dist_extra[d]
  }
  let mut dyn_hdr = 14 + 3 * hclen
  for it in codelen_syms {
    dyn_hdr = dyn_hdr + codelen_code_len[it.sym] + it.nextra
  }
  let stored = 8 * (byte_len + 5 * stored_block_count(byte_len))
  let dynamic = 3 + dyn_hdr + dyn_sym + extra
  let fixed = 3 + fixed_sym + extra
  let mut best = stored
  if fixed < best {
    best = fixed
  }
  if dynamic < best {
    best = dynamic
  }
  best
}

///|
/// Symbol frequencies of `tokens[lo:hi)`.
fn range_freqs(
  tokens : Array[Int],
  lo : Int,
  hi : Int,
  ll_freq : Array[Int],
  d_freq : Array[Int],
) -> Unit {
  for s in 0..<286 {
    ll_freq[s] = 0
  }
  for d in 0..<30 {
    d_freq[d] = 0
  }
  for k in lo..> 16
      let distance = tok & 0xFFFF
      ll_freq[257 + len_to_idx[length]] += 1
      d_freq[dist_index(distance)] += 1
    }
  }
}

///|
/// Exact block cost of `tokens[lo:hi)` covering `byte_len` input bytes.
fn split_range_cost(
  tokens : Array[Int],
  lo : Int,
  hi : Int,
  byte_len : Int,
  ll_freq : Array[Int],
  d_freq : Array[Int],
) -> Int {
  range_freqs(tokens, lo, hi, ll_freq, d_freq)
  block_cost_bits(byte_len, ll_freq, d_freq)
}

///|
fn split_candidate_cost(
  tokens : Array[Int],
  tok_pos : Array[Int],
  lo : Int,
  hi : Int,
  k : Int,
  ll_freq : Array[Int],
  d_freq : Array[Int],
) -> Int {
  split_range_cost(tokens, lo, k, tok_pos[k] - tok_pos[lo], ll_freq, d_freq) +
  split_range_cost(tokens, k, hi, tok_pos[hi] - tok_pos[k], ll_freq, d_freq)
}

///|
/// zopfli's FindMinimum: locate the split point inside (lo, hi) minimizing
/// the two halves' summed exact cost, by sampling 9 evenly spaced candidates
/// and recursively narrowing to the winner's neighborhood; small intervals
/// are scanned exhaustively. Writes split index and cost to `result[0:2]`;
/// index -1 means the interval admits no interior point. The caller reuses the
/// pair so each candidate search does not allocate a return tuple.
fn find_best_split(
  tokens : Array[Int],
  tok_pos : Array[Int],
  lo : Int,
  hi : Int,
  result : FixedArray[Int],
  ll_freq : Array[Int],
  d_freq : Array[Int],
) -> Unit {
  let sample = 9
  let mut plo = lo + 1
  let mut phi = hi - 1
  let mut best_k = -1
  let mut best_cost = 0x3FFFFFFF
  while phi - plo > sample {
    let step = (phi - plo) / (sample + 1)
    let mut win_i = 0
    let mut win_k = plo
    let mut win_c = 0x3FFFFFFF
    for i in 0.. Array[Int] {
  let bounds : Array[Int] = [0, tokens.length()]
  let split_result = FixedArray::make(2, 0)
  let ll_freq = Array::make(286, 0)
  let d_freq = Array::make(30, 0)
  while bounds.length() - 1 < optimal_max_blocks {
    let mut best_gain = 0
    let mut best_seg = -1
    let mut best_k = -1
    for s in 0..<(bounds.length() - 1) {
      let lo = bounds[s]
      let hi = bounds[s + 1]
      if hi - lo < 16 {
        continue
      }
      let whole = split_range_cost(
        tokens,
        lo,
        hi,
        tok_pos[hi] - tok_pos[lo],
        ll_freq,
        d_freq,
      )
      find_best_split(tokens, tok_pos, lo, hi, split_result, ll_freq, d_freq)
      let k = split_result[0]
      let cost = split_result[1]
      if k >= 0 && whole - cost > best_gain {
        best_gain = whole - cost
        best_seg = s
        best_k = k
      }
    }
    if best_seg < 0 {
      break
    }
    bounds.insert(best_seg + 1, best_k)
  }
  bounds
}

///|
/// Total exact cost of a grouping (consecutive bounds over `tokens`).
fn grouping_cost(
  tokens : Array[Int],
  tok_pos : Array[Int],
  bounds : Array[Int],
) -> Int {
  let mut total = 0
  let ll_freq = Array::make(286, 0)
  let d_freq = Array::make(30, 0)
  for s in 0..<(bounds.length() - 1) {
    let lo = bounds[s]
    let hi = bounds[s + 1]
    total = total +
      split_range_cost(
        tokens,
        lo,
        hi,
        tok_pos[hi] - tok_pos[lo],
        ll_freq,
        d_freq,
      )
  }
  total
}

///|
/// Compress with zopfli-style effort: content-driven block splitting plus
/// iterated optimal parsing, with a second splitting pass over the optimal
/// tokens (blocksplittinglast). Tens to hundreds of times slower than
/// `deflate_all` — for compress-once, serve-forever artifacts.  `iterations` is the squeeze count
/// per block (zopfli's default is 15).
pub fn deflate_all_optimal(input : Bytes, iterations? : Int = 15) -> Bytes {
  let iters = if iterations < 1 { 1 } else { iterations }
  let w = BitWriter::new()
  let n = input.length()
  if n == 0 {
    let ll_freq = Array::make(286, 0)
    let d_freq = Array::make(30, 0)
    let none : Array[Int] = []
    emit_block(w, input, 0, 0, none[:], ll_freq, d_freq, is_final=true)
    w.flush()
    return Bytes::from_array(w.out)
  }
  let mut pos = 0
  for ;; {
    let target = if pos + optimal_master_block < n {
      pos + optimal_master_block
    } else {
      n
    }
    // Phase 1: cheap greedy reference parse (level-9 tuning), split it, and
    // optimal-parse each segment, concatenating the optimal tokens.
    let gtoks : Array[Int] = []
    let greedy_ll_freq = Array::make(286, 0)
    let greedy_d_freq = Array::make(30, 0)
    let processed = tokenize(
      input,
      pos,
      target,
      level_configs[9],
      gtoks,
      greedy_ll_freq,
      greedy_d_freq,
    )
    let chunk_end = processed // a boundary match may overhang `target`
    let gtok_pos = Array::make(gtoks.length() + 1, 0)
    let mut p = pos
    for k in 0..> 16 })
    }
    gtok_pos[gtoks.length()] = chunk_end
    let bounds1 = plan_split_points(gtoks, gtok_pos)
    let all : Array[Int] = []
    let joins : Array[Int] = [0] // phase-1 boundaries, as optimal-token indices
    for s in 0..<(bounds1.length() - 1) {
      let a = gtok_pos[bounds1[s]]
      let b = gtok_pos[bounds1[s + 1]]
      let toks = tokenize_optimal(input, a, b, iters)
      for t in toks {
        all.push(t)
      }
      joins.push(all.length())
    }
    let all_pos = Array::make(all.length() + 1, 0)
    let mut q = pos
    for k in 0..> 16 })
    }
    all_pos[all.length()] = chunk_end
    // Phase 2 (blocksplittinglast): re-split over the optimal tokens, then
    // emit whichever grouping is cheaper by exact cost.
    let bounds2 = plan_split_points(all, all_pos)
    let bounds = if grouping_cost(all, all_pos, bounds2) <
      grouping_cost(all, all_pos, joins) {
      bounds2
    } else {
      joins
    }
    for s in 0..<(bounds.length() - 1) {
      let lo = bounds[s]
      let hi = bounds[s + 1]
      let ll_freq = Array::make(286, 0)
      let d_freq = Array::make(30, 0)
      range_freqs(all, lo, hi, ll_freq, d_freq)
      emit_block(
        w,
        input,
        all_pos[lo],
        all_pos[hi],
        all[lo:hi],
        ll_freq,
        d_freq,
        is_final=all_pos[hi] == n,
      )
    }
    pos = chunk_end
    if pos >= n {
      break
    }
  }
  w.flush()
  Bytes::from_array(w.out)
}