// Optimal LZ77 parsing (zopfli-style "squeeze"): the drop-in counterpart to
// the greedy/lazy parser in lz77.mbt, plugged into the same
// (tokens, frequencies) seam. The parse is a cost-driven shortest path over
// the token graph: every position may step one literal or any reachable
// match, with edge weights in bits. Real costs depend on the Huffman tables,
// which depend on the parse — so the parse is iterated: each round's
// frequencies build length-limited Huffman codes (the writer's own
// `gen_huffman`) whose code lengths become the next round's costs, and the
// cheapest parse seen (by exact block cost) wins.

///|
/// One Pareto-frontier entry among the matches at a position: lengths in
/// (previous entry's len, len] are reachable at `dist`, the smallest distance
/// achieving them (the chain walks nearest-first, so the first candidate
/// reaching a new length has the minimal distance for it).
priv struct MatchRange {
  len : Int
  dist : Int
}

///|
// The optimal parser has a separate candidate frontier and deliberately keeps
// its own temporary table. Its future binary-tree/cache work must not inherit
// the greedy/lazy session matchfinder's lifecycle.
fn insert_optimal_pos(
  data : Bytes,
  head : FixedArray[Int],
  prev : FixedArray[Int],
  i : Int,
  n : Int,
  seed_from : Int,
) -> Unit {
  if i + 3 <= n {
    let h = hash3(data, i)
    prev[i - seed_from] = head[h]
    head[h] = i
  }
}

///|
/// Chain candidates examined per position; effectively exhaustive, in keeping
/// with the offline effort budget.
const OPTIMAL_MAX_CHAIN : Int = 8192

///|
/// The match frontier at every position of `data[start:end)`, computed once
/// and reused by every squeeze iteration. Matches never extend past `end`
/// (the planner chose exact bounds). The window-eligible suffix of
/// `data[0:start)` is seeded as history so back-references may cross block
/// boundaries.
fn collect_matches(
  data : Bytes,
  start : Int,
  end : Int,
) -> FixedArray[Array[MatchRange]] {
  let seed_from = if start > WINDOW_SIZE { start - WINDOW_SIZE } else { 0 }
  let head = FixedArray::make(1 << HASH_BITS, -1)
  let prev = FixedArray::make(
    if end > seed_from {
      end - seed_from
    } else {
      1
    },
    -1,
  )
  let n = data.length()
  for j in seed_from..= 3 && i + 3 <= n {
      let h = hash3(data, i)
      let mut cand = head[h]
      let mut best = 2
      let mut steps = 0
      while cand >= 0 && steps < OPTIMAL_MAX_CHAIN && i - cand <= 32768 {
        let l = if match_candidate_can_beat(data, cand, i, best, limit) {
          match_len_up_to(data, cand, i, limit)
        } else {
          best
        }
        if l > best {
          frontier.push({ len: l, dist: i - cand, })
          best = l
          if l >= limit {
            break
          }
        }
        cand = prev[cand - seed_from]
        steps = steps + 1
      }
    }
    insert_optimal_pos(data, head, prev, i, n, seed_from)
    out[i - start] = frontier
  }
  out
}

///|
/// Trace the shortest path recorded in `len_choice`/`dist_choice` back from
/// the end of `data[start:start+m)`, then replay it forward into `tokens`,
/// tallying the literal/length and distance symbols consumed.
fn replay_tokens(
  data : Bytes,
  start : Int,
  m : Int,
  len_choice : FixedArray[Int],
  dist_choice : FixedArray[Int],
  tokens : Array[Int],
  ll_freq : FixedArray[Int],
  d_freq : FixedArray[Int],
) -> Unit {
  let steps : Array[Int] = []
  let mut o = m
  while o > 0 {
    steps.push(o)
    o = o - len_choice[o]
  }
  let mut pos = start
  for k = steps.length() - 1; k >= 0; k = k - 1 {
    let at = steps[k]
    let l = len_choice[at]
    if l == 1 && dist_choice[at] == 0 {
      let b = data[pos].to_int()
      tokens.push(b)
      ll_freq[b] += 1
    } else {
      tokens.push(pack_match_token(l, dist_choice[at]))
      ll_freq[257 + len_to_idx[l]] += 1
      d_freq[dist_index(dist_choice[at])] += 1
    }
    pos = pos + l
  }
}

///|
/// One shortest-path pass: bit costs in, parse out. `costs[o]` is the minimal
/// bits to encode `data[start:start+o)`; each position relaxes a literal edge
/// and every frontier match length.
fn squeeze_parse(
  data : Bytes,
  start : Int,
  end : Int,
  matches : FixedArray[Array[MatchRange]],
  ll_cost : FixedArray[Int],
  d_cost : FixedArray[Int],
  tokens : Array[Int],
  ll_freq : FixedArray[Int],
  d_freq : FixedArray[Int],
) -> Unit {
  let m = end - start
  let inf = 0x3FFFFFFF
  let costs = FixedArray::make(m + 1, inf)
  let len_choice = FixedArray::make(m + 1, 0)
  let dist_choice = FixedArray::make(m + 1, 0)
  costs[0] = 0
  for o in 0.. Unit {
  let ll_freq_eob = FixedArray::make(286, 0)
  for s in 0..<286 {
    ll_freq_eob[s] = ll_freq[s]
  }
  ll_freq_eob[256] += 1
  let ll_len = FixedArray::make(286, 0)
  gen_huffman(ll_freq_eob, 286, 15, ll_len)
  let dd_len = FixedArray::make(30, 0)
  gen_huffman(d_freq, 30, 15, dd_len)
  for s in 0..<286 {
    ll_cost[s] = if ll_len[s] == 0 { 15 } else { ll_len[s] }
  }
  for d in 0..<30 {
    d_cost[d] = if dd_len[d] == 0 { 15 } else { dd_len[d] }
  }
}

///|
/// Iterated optimal parse of `data[start:end)`: squeeze under fixed-table
/// costs first, then re-derive costs from each round's own statistics,
/// keeping the cheapest parse seen (judged by exact block cost).
fn tokenize_optimal(
  data : Bytes,
  start : Int,
  end : Int,
  iterations : Int,
) -> Array[Int] {
  let matches = collect_matches(data, start, end)
  let mut ll_cost = FixedArray::make(286, 0)
  for s in 0..<286 {
    ll_cost[s] = fixed_litlen_info[s] & 0xF
  }
  let mut d_cost = FixedArray::make(30, 5)
  let mut best_bits = 0x3FFFFFFF
  let mut best_tokens : Array[Int]? = None
  for _it in 0..