# Survival / niching — C# ReferencePointManager + NondominatedSortingSurvival.
# Independent maps (associate / histograms / gather) use mid-split
# `a b = f(lo) f(hi)`. Nearest-ref stays sequential (associate_raw already
# splits per individual). Perpendicular distance squares `f - t*w` in one
# walk (same F32 order as scale-then-subtract). Last-front fill builds
# `NRow{i, ref, dist}` once so the sequential niche loop never `List.get`s
# an Assignment (or a fat
# Individual) per remaining candidate. Run's rng fill groups those rows
# into per-ref bags so each pick walks bags, not the whole front and not
# `List.get` on the counts spine. Same pick rules / same RNG order.
# Associate normalized individuals to Das–Dennis rays; select `target_size`
# from a combined pool (fill complete fronts, niche-preserve the last).
# Deterministic when C# rng is null (`select`): lowest ref among min-count
# niches, then min perpendicular distance if that niche is empty, else
# lowest index. `select_st` (Run) threads rng: random among equal
# min-count niches (C# Select(..., rng)). Empty niches take the closest
# unused member; extras draw among members within 2×best+0.01 of the
# ray — not uniform inNiche[rng.Next], which collapsed oracle ZDT2.

import Base
import ./individual.bend as Ind
import ./non_dominated_sort.bend as NDS
import ./normalization.bend as Norm
import ./rng.bend as Rng
import ./util.bend as Util

type Assignment is Data:
  MkAssignment{
    reference_index: Nat
    perpendicular_distance: F32
    niche_count: Nat
  }

def asg_ref(a: Assignment) -> Nat:
  match a:
    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
      reference_index

def asg_dist(a: Assignment) -> F32:
  match a:
    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
      perpendicular_distance

def asg_count(a: Assignment) -> Nat:
  match a:
    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
      niche_count

def get_asg(asgs: List<&2, Assignment>, i: Nat) -> Assignment:
  Maybe.default(&2, Assignment, List.get(&2, Assignment, asgs, i), MkAssignment{0n, 0.0, 0n})

def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
  Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))

# Last-front row: population index plus the two fields the fill loop
# reads. Built once from `asgs` so each pick walks this thin list
# instead of `List.get` into the combined-pool assignment spine.
type NRow is Data:
  NRow{
    i: Nat
    r: Nat
    d: F32
  }

def nrow_i(row: NRow) -> Nat:
  match row:
    case NRow{i, r, d}:
      i

def nrow_r(row: NRow) -> Nat:
  match row:
    case NRow{i, r, d}:
      r

def nrow_d(row: NRow) -> F32:
  match row:
    case NRow{i, r, d}:
      d

def nrows_of.go(+asgs: List<&2, Assignment>, cand: List<&2, Nat>, acc: List<&2, NRow>) -> List<&2, NRow>:
  match cand:
    case Nil{}:
      List.reverse(&2, NRow, acc)
    case +i <> rest:
      +a = get_asg(asgs, i)
      nrows_of.go(asgs, rest, NRow{i, asg_ref(a), asg_dist(a)} <> acc)

def nrows_of(+asgs: List<&2, Assignment>, +cand: List<&2, Nat>) -> List<&2, NRow>:
  nrows_of.go(asgs, cand, Nil{})

def first_row_i(rows: List<&2, NRow>) -> Nat:
  match rows:
    case Nil{}:
      0n
    case +row <> _:
      nrow_i(row)

def get_nrow(rows: List<&2, NRow>, i: Nat) -> NRow:
  Maybe.default(&2, NRow, List.get(&2, NRow, rows, i), NRow{0n, 0n, 0.0})

def drop_nrow.put(+row: NRow, rest: List<&2, NRow>, drop: Bool) -> List<&2, NRow>:
  match drop:
    case True{}:
      rest
    case False{}:
      row <> rest

def drop_nrow(rows: List<&2, NRow>, +pick: Nat) -> List<&2, NRow>:
  match rows:
    case Nil{}:
      Nil{}
    case +row <> rest:
      drop_nrow.put(row, drop_nrow(rest, pick), Nat.is_eq(nrow_i(row), pick))

def keep_nat(h: Nat, rest: List<&2, Nat>, keep: Bool) -> List<&2, Nat>:
  match keep:
    case True{}:
      h <> rest
    case False{}:
      rest

def uniq_refs.go(rows: List<&2, NRow>, +acc: List<&2, Nat>) -> List<&2, Nat>:
  match rows:
    case Nil{}:
      List.reverse(&2, Nat, acc)
    case +row <> rest:
      +r = nrow_r(row)
      uniq_refs.go(rest, keep_nat(r, acc, Bool.not(Util.in_nats(r, acc))))

def uniq_refs(rows: List<&2, NRow>) -> List<&2, Nat>:
  uniq_refs.go(rows, Nil{})

def min_count_rows.go(+counts: List<&2, Nat>, rows: List<&2, NRow>, +acc: Nat) -> Nat:
  match rows:
    case Nil{}:
      acc
    case +row <> rest:
      min_count_rows.go(counts, rest, Util.nat_min(acc, Util.get_nat(counts, nrow_r(row))))

def min_count_rows(+counts: List<&2, Nat>, rows: List<&2, NRow>) -> Nat:
  min_count_rows.go(counts, rows, 4294967295n)

def refs_at_seq(+counts: List<&2, Nat>, +need: Nat, refs: List<&2, Nat>) -> List<&2, Nat>:
  match refs:
    case Nil{}:
      Nil{}
    case +r <> rest:
      keep_nat(r, refs_at_seq(counts, need, rest), Nat.is_eq(Util.get_nat(counts, r), need))

def in_ref_rows(+r: Nat, rows: List<&2, NRow>) -> List<&2, NRow>:
  match rows:
    case Nil{}:
      Nil{}
    case +row <> rest:
      Util.keep_if(NRow, row, in_ref_rows(r, rest), Nat.is_eq(nrow_r(row), r))

def argmin_dist_rows.go(rows: List<&2, NRow>, +best_i: Nat, +best_d: F32) -> Nat:
  match rows:
    case Nil{}:
      best_i
    case +row <> rest:
      +d = nrow_d(row)
      +lt = F32.is_lt(d, best_d)
      argmin_dist_rows.go(rest, Bool.pick(Nat, lt, nrow_i(row), best_i), Bool.pick(F32, lt, d, best_d))

def argmin_dist_rows(rows: List<&2, NRow>) -> Nat:
  match rows:
    case Nil{}:
      0n
    case +row <> rest:
      argmin_dist_rows.go(rest, nrow_i(row), nrow_d(row))

def min_dist_rows.go(rows: List<&2, NRow>, +acc: F32) -> F32:
  match rows:
    case Nil{}:
      acc
    case +row <> rest:
      +d = nrow_d(row)
      min_dist_rows.go(rest, Bool.pick(F32, F32.is_lt(d, acc), d, acc))

def min_dist_rows(rows: List<&2, NRow>) -> F32:
  match rows:
    case Nil{}:
      0.0
    case +row <> rest:
      min_dist_rows.go(rest, nrow_d(row))

def min_idx_rows.go(rows: List<&2, NRow>, +acc: Nat) -> Nat:
  match rows:
    case Nil{}:
      acc
    case +row <> rest:
      min_idx_rows.go(rest, Util.nat_min(acc, nrow_i(row)))

def min_idx_rows(rows: List<&2, NRow>) -> Nat:
  match rows:
    case Nil{}:
      0n
    case +row <> rest:
      min_idx_rows.go(rest, nrow_i(row))

def near_rows(+lim: F32, rows: List<&2, NRow>) -> List<&2, NRow>:
  match rows:
    case Nil{}:
      Nil{}
    case +row <> rest:
      Util.keep_if(NRow, row, near_rows(lim, rest), F32.is_le(nrow_d(row), lim))

# Same F32 steps as `vec_sqnorm(vec_sub(f, vec_scale(t, w)))`: left-to-right
# `r*r` with `r = f - t*w`, no scaled-vector and residual-vector spines.
def resid_sq(+t: F32, f: List<&2, F32>, w: List<&2, F32>) -> F32:
  match f w:
    case Nil{} Nil{}:
      0.0
    case x <> xs y <> ys:
      +r = F32.sub(x, F32.mul(t, y))
      F32.add(F32.mul(r, r), resid_sq(t, xs, ys))
    case Nil{} y <> ys:
      0.0
    case x <> xs Nil{}:
      0.0

def perp.big(+f: List<&2, F32>, +w: List<&2, F32>, +ww: F32) -> F32:
  +t = F32.div(Util.vec_dot(f, w), ww)
  F32.sqrt(resid_sq(t, f, w))

def perp.zero(+f: List<&2, F32>, tiny: Bool) -> F32:
  match tiny:
    case True{}:
      F32.sqrt(Util.vec_sqnorm(f))
    case False{}:
      0.0

def perp.pick(+f: List<&2, F32>, +w: List<&2, F32>, +ww: F32, tiny: Bool) -> F32:
  match tiny:
    case True{}:
      perp.zero(f, True{})
    case False{}:
      perp.big(f, w, ww)

def perp(+f: List<&2, F32>, +w: List<&2, F32>) -> F32:
  +ww = Util.vec_sqnorm(w)
  perp.pick(f, w, ww, F32.is_lt(ww, 0.0000000000000001))

# First-min on strict `<` (ties keep the lower index). Sequential over
# dirs; associate_raw already mid-splits per individual.
def nearest_go(+f: List<&2, F32>, dirs: List<&2, List<&2, F32>>, +i: Nat, +best_i: Nat, +best_d: F32) -> Assignment:
  match dirs:
    case Nil{}:
      MkAssignment{best_i, best_d, 0n}
    case +w <> ws:
      +d = perp(f, w)
      nearest_go(
        f,
        ws,
        1n+i,
        Bool.pick(Nat, F32.is_lt(d, best_d), i, best_i),
        Bool.pick(F32, F32.is_lt(d, best_d), d, best_d)
      )

def nearest_one(f: List<&2, F32>, dirs: List<&2, List<&2, F32>>) -> Assignment:
  nearest_go(f, dirs, 0n, 0n, 1000000000.0)

def associate_head(+dirs: List<&2, List<&2, F32>>, +ind: Ind.Individual, F: List<&2, List<&2, F32>>) -> Assignment:
  match F:
    case Nil{}:
      nearest_one(Ind.objectives(ind), dirs)
    case f <> fs:
      nearest_one(f, dirs)

# Nearest-ref per individual is independent given dirs. Mid-split pop and F.
def associate_raw.go(
  +dirs: List<&2, List<&2, F32>>,
  +fuel: Nat,
  pop: List<&2, Ind.Individual>,
  +F: List<&2, List<&2, F32>>
) -> List<&2, Assignment>:
  match fuel pop:
    case 0n Nil{}:
      Nil{}
    case 0n ind <> rest:
      match F:
        case Nil{}:
          nearest_one(Ind.objectives(ind), dirs) <> associate_raw.go(dirs, 0n, rest, Nil{})
        case f <> fs:
          nearest_one(f, dirs) <> associate_raw.go(dirs, 0n, rest, fs)
    case 1n+p Nil{}:
      Nil{}
    case 1n+p ind <> Nil{}:
      associate_head(dirs, ind, F) <> Nil{}
    case 1n+p h <> t:
      +all = {h <> t : List<&2, Ind.Individual>}
      +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
      lo hi = associate_raw.go(dirs, p, List.take(&2, Ind.Individual, all, mid), List.take(&2, List<&2, F32>, F, mid)) associate_raw.go(dirs, p, List.drop(&2, Ind.Individual, all, mid), List.drop(&2, List<&2, F32>, F, mid))
      List.append(&2, Assignment, lo, hi)

def associate_raw(+pop: List<&2, Ind.Individual>, +F: List<&2, List<&2, F32>>, +dirs: List<&2, List<&2, F32>>) -> List<&2, Assignment>:
  associate_raw.go(dirs, Util.list_len(Ind.Individual, pop), pop, F)

# Histogram increments commute. Mid-split asgs, then add count vectors.
def count_raw.go(+n: Nat, +fuel: Nat, asgs: List<&2, Assignment>) -> List<&2, Nat>:
  match fuel asgs:
    case 0n Nil{}:
      Util.zeros_nat(n)
    case 0n a <> rest:
      Util.inc_at(count_raw.go(n, 0n, rest), asg_ref(a))
    case 1n+p Nil{}:
      Util.zeros_nat(n)
    case 1n+p a <> Nil{}:
      Util.inc_at(Util.zeros_nat(n), asg_ref(a))
    case 1n+p h <> t:
      +all = {h <> t : List<&2, Assignment>}
      +mid = Nat.div(Util.list_len(Assignment, all), 2n)
      lo hi = count_raw.go(n, p, List.take(&2, Assignment, all, mid)) count_raw.go(n, p, List.drop(&2, Assignment, all, mid))
      Util.nats_add(lo, hi)

def count_asg(+asgs: List<&2, Assignment>, +acc: List<&2, Nat>) -> List<&2, Nat>:
  Util.nats_add(acc, count_raw.go(Util.list_len(Nat, acc), Util.list_len(Assignment, asgs), asgs))

# Assignments whose reference_index lands in a length-n histogram.
# Out-of-range refs are silent no-ops in inc_at / List.set.
def in_bin_count(asgs: List<&2, Assignment>, +n: Nat) -> Nat:
  match asgs:
    case Nil{}:
      0n
    case +a <> rest:
      Nat.add(Util.bin_hit(asg_ref(a), n), in_bin_count(rest, n))

def with_counts.one(+counts: List<&2, Nat>, +a: Assignment) -> Assignment:
  match a:
    case MkAssignment{+r, d, n}:
      MkAssignment{r, d, Util.get_nat(counts, r)}

def with_counts(+counts: List<&2, Nat>, +asgs: List<&2, Assignment>) -> List<&2, Assignment>:
  Util.map_halves(~Assignment, ~Assignment, ~List<&2, Nat>, ~with_counts.one, counts, asgs)

def associate(+pop: List<&2, Ind.Individual>, +F: List<&2, List<&2, F32>>, +dirs: List<&2, List<&2, F32>>) -> List<&2, Assignment>:
  +raw = associate_raw(pop, F, dirs)
  with_counts(count_asg(raw, Util.zeros_nat(Util.list_len(List<&2, F32>, dirs))), raw)

def front0(fronts: List<&2, List<&2, Nat>>) -> List<&2, Nat>:
  match fronts:
    case Nil{}:
      Nil{}
    case h <> t:
      h

def n_fronts(fronts: List<&2, List<&2, Nat>>) -> Nat:
  Util.list_len(List<&2, Nat>, fronts)

def head_len(fronts: List<&2, List<&2, Nat>>) -> Nat:
  match fronts:
    case Nil{}:
      0n
    case h <> t:
      Util.list_len(Nat, h)

def gather.one(+pop: List<&2, Ind.Individual>, +i: Nat) -> Ind.Individual:
  get_ind(pop, i)

def gather(+pop: List<&2, Ind.Individual>, +idxs: List<&2, Nat>) -> List<&2, Ind.Individual>:
  Util.map_halves(~Nat, ~Ind.Individual, ~List<&2, Ind.Individual>, ~gather.one, pop, idxs)

def cand_ref.one(+asgs: List<&2, Assignment>, +i: Nat) -> Nat:
  asg_ref(get_asg(asgs, i))

def cand_refs(+asgs: List<&2, Assignment>, cand: List<&2, Nat>) -> List<&2, Nat>:
  Util.map_halves(~Nat, ~Nat, ~List<&2, Assignment>, ~cand_ref.one, asgs, cand)

def min_count.go(+counts: List<&2, Nat>, +fuel: Nat, refs: List<&2, Nat>) -> Nat:
  match fuel refs:
    case 0n Nil{}:
      4294967295n
    case 0n +r <> rs:
      Util.nat_min(Util.get_nat(counts, r), min_count.go(counts, 0n, rs))
    case 1n+p Nil{}:
      4294967295n
    case 1n+p +r <> Nil{}:
      Util.get_nat(counts, r)
    case 1n+p h <> t:
      +all = {h <> t : List<&2, Nat>}
      +mid = Nat.div(Util.list_len(Nat, all), 2n)
      lo hi = min_count.go(counts, p, List.take(&2, Nat, all, mid)) min_count.go(counts, p, List.drop(&2, Nat, all, mid))
      Util.nat_min(lo, hi)

def min_count(+counts: List<&2, Nat>, refs: List<&2, Nat>, acc: Nat) -> Nat:
  match refs:
    case Nil{}:
      acc
    case +r <> +rs:
      +xs = {r <> rs : List<&2, Nat>}
      Util.nat_min(acc, min_count.go(counts, Util.list_len(Nat, xs), xs))

def cons_if(h: Nat, rest: List<&2, Nat>, keep: Bool) -> List<&2, Nat>:
  match keep:
    case True{}:
      h <> rest
    case False{}:
      rest

# First-occurrence unique (C# HashSet of refs-with-candidates).
def uniq_nats.go(xs: List<&2, Nat>, +acc: List<&2, Nat>) -> List<&2, Nat>:
  match xs:
    case Nil{}:
      List.reverse(&2, Nat, acc)
    case +h <> t:
      uniq_nats.go(t, cons_if(h, acc, Bool.not(Util.in_nats(h, acc))))

def uniq_nats(xs: List<&2, Nat>) -> List<&2, Nat>:
  uniq_nats.go(xs, Nil{})

type CntNeed is Data:
  CN{
    counts: List<&2, Nat>
    need: Nat
  }

def refs_at.ok(+ctx: CntNeed, +r: Nat) -> Bool:
  match ctx:
    case CN{counts, need}:
      Nat.is_eq(Util.get_nat(counts, r), need)

def refs_at(+counts: List<&2, Nat>, +need: Nat, refs: List<&2, Nat>) -> List<&2, Nat>:
  Util.filter_halves(~Nat, ~CntNeed, ~refs_at.ok, CN{counts, need}, refs)

def min_idx(xs: List<&2, Nat>, acc: Nat) -> Nat:
  match xs:
    case Nil{}:
      acc
    case +x <> rest:
      min_idx(rest, Util.nat_min(acc, x))

def min_idx_ne(xs: List<&2, Nat>) -> Nat:
  match xs:
    case Nil{}:
      0n
    case x <> rest:
      min_idx(rest, x)

def pick_ref(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>) -> Nat:
  +refs = cand_refs(asgs, cand)
  min_idx_ne(refs_at(counts, min_count(counts, refs, 4294967295n), refs))

type RefPick is Data:
  RP{
    asgs: List<&2, Assignment>
    r: Nat
  }

def in_ref.ok(+ctx: RefPick, +i: Nat) -> Bool:
  match ctx:
    case RP{asgs, r}:
      Nat.is_eq(asg_ref(get_asg(asgs, i)), r)

def in_ref(+asgs: List<&2, Assignment>, +r: Nat, cand: List<&2, Nat>) -> List<&2, Nat>:
  Util.filter_halves(~Nat, ~RefPick, ~in_ref.ok, RP{asgs, r}, cand)

def argmin_join(+asgs: List<&2, Assignment>, +ia: Nat, +ib: Nat) -> Nat:
  Bool.pick(Nat, F32.is_lt(asg_dist(get_asg(asgs, ib)), asg_dist(get_asg(asgs, ia))), ib, ia)

def argmin_dist.go(+asgs: List<&2, Assignment>, +fuel: Nat, cand: List<&2, Nat>) -> Nat:
  match fuel cand:
    case 0n Nil{}:
      0n
    case 0n +i <> Nil{}:
      i
    case 0n +i <> +j <> js:
      argmin_join(asgs, i, argmin_dist.go(asgs, 0n, j <> js))
    case 1n+p Nil{}:
      0n
    case 1n+p +i <> Nil{}:
      i
    case 1n+p h <> t:
      +all = {h <> t : List<&2, Nat>}
      +mid = Nat.div(Util.list_len(Nat, all), 2n)
      lo hi = argmin_dist.go(asgs, p, List.take(&2, Nat, all, mid)) argmin_dist.go(asgs, p, List.drop(&2, Nat, all, mid))
      argmin_join(asgs, lo, hi)

def argmin_dist(+asgs: List<&2, Assignment>, cand: List<&2, Nat>) -> Nat:
  match cand:
    case Nil{}:
      0n
    case +i <> +rest:
      +xs = {i <> rest : List<&2, Nat>}
      argmin_dist.go(asgs, Util.list_len(Nat, xs), xs)

def pick_member.by(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool) -> Nat:
  match empty_niche:
    case True{}:
      argmin_dist(asgs, group)
    case False{}:
      min_idx_ne(group)

# First remaining last-front index. Used when inNiche is empty
# (C# would throw; never pick a phantom combined-pool index 0).
def first_cand(cand: List<&2, Nat>) -> Nat:
  match cand:
    case Nil{}:
      0n
    case x <> _:
      x

def pick_member.by.safe(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool, +fallback: Nat) -> Nat:
  match group:
    case Nil{}:
      fallback
    case g0 <> gs:
      pick_member.by(asgs, {g0 <> gs : List<&2, Nat>}, empty_niche)

def pick_member(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, +r: Nat) -> Nat:
  pick_member.by.safe(asgs, in_ref(asgs, r, cand), Nat.is_eq(Util.get_nat(counts, r), 0n), first_cand(cand))

# Affine API: advanced State; chosen index is `Rng.last_nat` (no pair match).
# C# Select(..., rng): draw only when more than one min-count ref.
def pick_ref.rng.go(+mins: List<&2, Nat>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
  match n:
    case 0n:
      Rng.with_k(rng, fallback)
    case 1n:
      Rng.with_k(rng, min_idx_ne(mins))
    case 1n+p:
      +rng2 = Rng.next_nat(rng, 1n+p)
      Rng.with_k(rng2, Util.get_nat(mins, Rng.last_nat(rng2)))

def pick_ref.rng.after(+mins: List<&2, Nat>, +fallback: Nat, rng: Rng.State) -> Rng.State:
  pick_ref.rng.go(mins, Util.list_len(Nat, mins), fallback, rng)

def pick_ref.rng(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, rng: Rng.State) -> Rng.State:
  +refs = uniq_nats(cand_refs(asgs, cand))
  pick_ref.rng.after(
    refs_at(counts, min_count(counts, refs, 4294967295n), refs),
    asg_ref(get_asg(asgs, first_cand(cand))),
    rng
  )

# Uniform inNiche[rng.Next] (C# non-empty + rng) lets far-from-ray last-front
# junk into a niche. With this LCG that pile-up dominates ZDT2's concave
# front (x0 → 0). Draw extras only among members within 2×best+0.01 of
# the ray (first assignment to a niche stays closest).
def near_lim(+best: F32) -> F32:
  F32.add(F32.mul(best, 2.0), 0.01)

def near_ok(+asgs: List<&2, Assignment>, +i: Nat, +lim: F32) -> Bool:
  F32.is_le(asg_dist(get_asg(asgs, i)), lim)

type NearPick is Data:
  NP{
    asgs: List<&2, Assignment>
    lim: F32
  }

def near_members.ok(+ctx: NearPick, +i: Nat) -> Bool:
  match ctx:
    case NP{asgs, lim}:
      near_ok(asgs, i, lim)

def near_members(+asgs: List<&2, Assignment>, group: List<&2, Nat>, +lim: F32) -> List<&2, Nat>:
  Util.filter_halves(~Nat, ~NearPick, ~near_members.ok, NP{asgs, lim}, group)

def pick_among.rng(+group: List<&2, Nat>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
  match n:
    case 0n:
      Rng.with_k(rng, fallback)
    case 1n:
      Rng.with_k(rng, min_idx_ne(group))
    case 1n+p:
      +rng2 = Rng.next_nat(rng, 1n+p)
      Rng.with_k(rng2, Util.get_nat(group, Rng.last_nat(rng2)))

def pick_near.rng(+asgs: List<&2, Assignment>, +group: List<&2, Nat>, rng: Rng.State) -> Rng.State:
  +near = near_members(asgs, group, near_lim(asg_dist(get_asg(asgs, argmin_dist(asgs, group)))))
  pick_among.rng(near, Util.list_len(Nat, near), first_cand(group), rng)

def pick_member.rng.empty(+asgs: List<&2, Assignment>, +group: List<&2, Nat>, empty_niche: Bool, rng: Rng.State) -> Rng.State:
  match empty_niche:
    case True{}:
      Rng.with_k(rng, argmin_dist(asgs, group))
    case False{}:
      pick_near.rng(asgs, group, rng)

def pick_member.rng.by(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool, +fallback: Nat, rng: Rng.State) -> Rng.State:
  match group:
    case Nil{}:
      Rng.with_k(rng, fallback)
    case g0 <> gs:
      pick_member.rng.empty(asgs, {g0 <> gs : List<&2, Nat>}, empty_niche, rng)

def pick_member.rng(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, +r: Nat, rng: Rng.State) -> Rng.State:
  pick_member.rng.by(
    asgs,
    in_ref(asgs, r, cand),
    Nat.is_eq(Util.get_nat(counts, r), 0n),
    first_cand(cand),
    rng
  )

def seed_raw.go(+asgs: List<&2, Assignment>, +n: Nat, +fuel: Nat, selected: List<&2, Nat>) -> List<&2, Nat>:
  match fuel selected:
    case 0n Nil{}:
      Util.zeros_nat(n)
    case 0n +i <> rest:
      Util.inc_at(seed_raw.go(asgs, n, 0n, rest), asg_ref(get_asg(asgs, i)))
    case 1n+p Nil{}:
      Util.zeros_nat(n)
    case 1n+p +i <> Nil{}:
      Util.inc_at(Util.zeros_nat(n), asg_ref(get_asg(asgs, i)))
    case 1n+p h <> t:
      +all = {h <> t : List<&2, Nat>}
      +mid = Nat.div(Util.list_len(Nat, all), 2n)
      lo hi = seed_raw.go(asgs, n, p, List.take(&2, Nat, all, mid)) seed_raw.go(asgs, n, p, List.drop(&2, Nat, all, mid))
      Util.nats_add(lo, hi)

def seed_counts(+asgs: List<&2, Assignment>, +selected: List<&2, Nat>, +acc: List<&2, Nat>) -> List<&2, Nat>:
  Util.nats_add(acc, seed_raw.go(asgs, Util.list_len(Nat, acc), Util.list_len(Nat, selected), selected))

# fuel, k, cand first so the match follows binder order and fuel shrinks.
def pick_ref.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>) -> Nat:
  +refs = uniq_refs(rows)
  min_idx_ne(refs_at_seq(counts, min_count_rows(counts, rows), refs))

def pick_member.by.ne.rows(+group: List<&2, NRow>, empty_niche: Bool) -> Nat:
  match empty_niche:
    case True{}:
      argmin_dist_rows(group)
    case False{}:
      min_idx_rows(group)

def pick_member.by.rows(group: List<&2, NRow>, empty_niche: Bool, +fallback: Nat) -> Nat:
  match group:
    case Nil{}:
      fallback
    case g0 <> gs:
      pick_member.by.ne.rows({g0 <> gs : List<&2, NRow>}, empty_niche)

def pick_member.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>, +r: Nat) -> Nat:
  pick_member.by.rows(in_ref_rows(r, rows), Nat.is_eq(Util.get_nat(counts, r), 0n), first_row_i(rows))

def pick_among.nrows(+rows: List<&2, NRow>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
  match n:
    case 0n:
      Rng.with_k(rng, fallback)
    case 1n:
      Rng.with_k(rng, first_row_i(rows))
    case 1n+p:
      +rng2 = Rng.next_nat(rng, 1n+p)
      Rng.with_k(rng2, nrow_i(get_nrow(rows, Rng.last_nat(rng2))))

def pick_near.rng.rows(+group: List<&2, NRow>, rng: Rng.State) -> Rng.State:
  +near = near_rows(near_lim(min_dist_rows(group)), group)
  pick_among.nrows(near, Util.list_len(NRow, near), first_row_i(group), rng)

def pick_member.rng.empty.rows(+group: List<&2, NRow>, empty_niche: Bool, rng: Rng.State) -> Rng.State:
  match empty_niche:
    case True{}:
      Rng.with_k(rng, argmin_dist_rows(group))
    case False{}:
      pick_near.rng.rows(group, rng)

def niche_loop(fuel: Nat, k: Nat, rows: List<&2, NRow>, +counts: List<&2, Nat>, selected: List<&2, Nat>) -> List<&2, Nat>:
  match fuel k rows:
    case 0n kk r:
      selected
    case f 0n r:
      selected
    case f kk Nil{}:
      selected
    case 1n+f 1n+krest +r0 <> +rs:
      +rows2 = {r0 <> rs : List<&2, NRow>}
      +r = pick_ref.rows(counts, rows2)
      +pick = pick_member.rows(counts, rows2, r)
      niche_loop(
        f,
        krest,
        drop_nrow(rows2, pick),
        Util.inc_at(counts, r),
        List.append(&2, Nat, selected, [pick])
      )

def fill(fuel: Nat, fronts: List<&2, List<&2, Nat>>, fits: Bool, +acc: List<&2, Nat>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat) -> List<&2, Nat>:
  match fuel fronts fits:
    case 0n fs p:
      acc
    case f Nil{} p:
      acc
    case 1n+f +fr <> +rest False{}:
      +need = Nat.sub(target, Util.list_len(Nat, acc))
      +rows = nrows_of(asgs, fr)
      niche_loop(
        1n+Util.list_len(NRow, rows),
        need,
        rows,
        seed_counts(asgs, acc, Util.zeros_nat(n_dirs)),
        acc
      )
    case 1n+f +fr <> +rest True{}:
      +new_acc = List.append(&2, Nat, acc, fr)
      fill(
        f,
        rest,
        Nat.is_le(Nat.add(Util.list_len(Nat, new_acc), head_len(rest)), target),
        new_acc,
        target,
        asgs,
        n_dirs
      )

def fill.wrap(+fronts: List<&2, List<&2, Nat>>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat) -> List<&2, Nat>:
  fill(
    1n+n_fronts(fronts),
    fronts,
    Nat.is_le(head_len(fronts), target),
    Nil{},
    target,
    asgs,
    n_dirs
  )

# Occupied last-front reference. Members stay in original row order.
# `pos` is that row's place in the last front, so a per-pick sort by the
# earliest remaining member restores first-seen ref order (deleting an
# early row can move its ref behind one that started later). `count` is
# the niche histogram, not the member length. Counts live on the bag, so
# a pick does not `List.get` the counts spine.
type MRow is Data:
  MRow{
    pos: Nat
    row: NRow
  }

type Bag is Data:
  Bag{
    ref: Nat
    count: Nat
    members: List<&2, MRow>
  }

def head_is_ref(bags: List<&2, Bag>, +r: Nat) -> Bool:
  match bags:
    case Nil{}:
      False{}
    case Bag{+ref, count, members} <> _:
      Nat.is_eq(ref, r)

def bag_put.go(
  bags: List<&2, Bag>,
  +row: NRow,
  +seeded: Nat,
  +pos: Nat,
  +rev: List<&2, Bag>,
  same: Bool
) -> List<&2, Bag>:
  match bags same:
    case Nil{} p:
      List.append(&2, Bag, List.reverse(&2, Bag, rev), [Bag{nrow_r(row), seeded, [MRow{pos, row}]}])
    case Bag{+ref, +count, +members} <> rest True{}:
      List.append(
        &2,
        Bag,
        List.reverse(&2, Bag, rev),
        Bag{ref, count, List.append(&2, MRow, members, [MRow{pos, row}])} <> rest
      )
    case Bag{+ref, +count, +members} <> +rest False{}:
      bag_put.go(rest, row, seeded, pos, Bag{ref, count, members} <> rev, head_is_ref(rest, nrow_r(row)))

def bag_put(+bags: List<&2, Bag>, +row: NRow, +seeded: Nat, +pos: Nat) -> List<&2, Bag>:
  bag_put.go(bags, row, seeded, pos, Nil{}, head_is_ref(bags, nrow_r(row)))

def bags_of.go(+counts: List<&2, Nat>, rows: List<&2, NRow>, +acc: List<&2, Bag>, +pos: Nat) -> List<&2, Bag>:
  match rows:
    case Nil{}:
      acc
    case +row <> rest:
      bags_of.go(counts, rest, bag_put(acc, row, Util.get_nat(counts, nrow_r(row)), pos), 1n+pos)

def bags_of(+counts: List<&2, Nat>, +rows: List<&2, NRow>) -> List<&2, Bag>:
  bags_of.go(counts, rows, Nil{}, 0n)

def first_bag_ref(bags: List<&2, Bag>) -> Nat:
  match bags:
    case Nil{}:
      0n
    case Bag{+ref, count, members} <> _:
      ref

def min_bag_count.go(bags: List<&2, Bag>, +acc: Nat) -> Nat:
  match bags:
    case Nil{}:
      acc
    case Bag{ref, +count, members} <> rest:
      min_bag_count.go(rest, Util.nat_min(acc, count))

def min_bag_count(bags: List<&2, Bag>) -> Nat:
  min_bag_count.go(bags, 4294967295n)

def refs_of_count.go(bags: List<&2, Bag>, +need: Nat, +acc: List<&2, Nat>) -> List<&2, Nat>:
  match bags:
    case Nil{}:
      List.reverse(&2, Nat, acc)
    case Bag{+ref, +count, members} <> rest:
      refs_of_count.go(rest, need, keep_nat(ref, acc, Nat.is_eq(count, need)))

def refs_of_count(+bags: List<&2, Bag>) -> List<&2, Nat>:
  refs_of_count.go(bags, min_bag_count(bags), Nil{})

def pick_ref.rng.bags(+bags: List<&2, Bag>, rng: Rng.State) -> Rng.State:
  pick_ref.rng.after(refs_of_count(bags), first_bag_ref(bags), rng)

def bag_count_go(bags: List<&2, Bag>, +r: Nat, hit: Bool) -> Nat:
  match bags hit:
    case Nil{} p:
      0n
    case Bag{ref, +count, members} <> rest True{}:
      count
    case Bag{ref, count, members} <> +rest False{}:
      bag_count_go(rest, r, head_is_ref(rest, r))

def bag_count_of(+bags: List<&2, Bag>, +r: Nat) -> Nat:
  bag_count_go(bags, r, head_is_ref(bags, r))

def mrows_rows(ms: List<&2, MRow>) -> List<&2, NRow>:
  match ms:
    case Nil{}:
      Nil{}
    case MRow{pos, +row} <> rest:
      row <> mrows_rows(rest)

def bag_members_go(bags: List<&2, Bag>, +r: Nat, hit: Bool) -> List<&2, NRow>:
  match bags hit:
    case Nil{} p:
      Nil{}
    case Bag{ref, count, +members} <> rest True{}:
      mrows_rows(members)
    case Bag{ref, count, members} <> +rest False{}:
      bag_members_go(rest, r, head_is_ref(rest, r))

def bag_members_of(+bags: List<&2, Bag>, +r: Nat) -> List<&2, NRow>:
  bag_members_go(bags, r, head_is_ref(bags, r))

def drop_mrow.put(+row: MRow, rest: List<&2, MRow>, drop: Bool) -> List<&2, MRow>:
  match drop:
    case True{}:
      rest
    case False{}:
      row <> rest

def drop_mrow(ms: List<&2, MRow>, +pick: Nat) -> List<&2, MRow>:
  match ms:
    case Nil{}:
      Nil{}
    case MRow{+pos, +row} <> rest:
      drop_mrow.put(MRow{pos, row}, drop_mrow(rest, pick), Nat.is_eq(nrow_i(row), pick))

def bags_kept(+ref: Nat, +count: Nat, members: List<&2, MRow>, rest: List<&2, Bag>) -> List<&2, Bag>:
  match members:
    case Nil{}:
      rest
    case +m <> +ms:
      Bag{ref, 1n+count, {m <> ms : List<&2, MRow>}} <> rest

def bags_refill.go(bags: List<&2, Bag>, +r: Nat, +pick: Nat, hit: Bool) -> List<&2, Bag>:
  match bags hit:
    case Nil{} p:
      Nil{}
    case Bag{+ref, +count, +members} <> rest True{}:
      bags_kept(ref, count, drop_mrow(members, pick), rest)
    case Bag{+ref, +count, +members} <> +rest False{}:
      Bag{ref, count, members} <> bags_refill.go(rest, r, pick, head_is_ref(rest, r))

def bags_refill(+bags: List<&2, Bag>, +r: Nat, +pick: Nat) -> List<&2, Bag>:
  bags_refill.go(bags, r, pick, head_is_ref(bags, r))

def head_pos.ms(ms: List<&2, MRow>) -> Nat:
  match ms:
    case Nil{}:
      4294967295n
    case MRow{+pos, row} <> _:
      pos

def head_pos(b: Bag) -> Nat:
  match b:
    case Bag{ref, count, +members}:
      head_pos.ms(members)

def insert_before(acc: List<&2, Bag>, +b: Bag) -> Bool:
  match acc:
    case Nil{}:
      True{}
    case +h <> _:
      Nat.is_le(head_pos(b), head_pos(h))

def insert_bag(acc: List<&2, Bag>, +b: Bag, before: Bool) -> List<&2, Bag>:
  match acc before:
    case Nil{} p:
      [b]
    case +h <> t True{}:
      b <> {h <> t : List<&2, Bag>}
    case +h <> +t False{}:
      h <> insert_bag(t, b, insert_before(t, b))

def sort_put(+acc: List<&2, Bag>, +b: Bag) -> List<&2, Bag>:
  insert_bag(acc, b, insert_before(acc, b))

def sort_go(bags: List<&2, Bag>, +acc: List<&2, Bag>) -> List<&2, Bag>:
  match bags:
    case Nil{}:
      acc
    case +b <> rest:
      sort_go(rest, sort_put(acc, b))

def sort_bags(+bags: List<&2, Bag>) -> List<&2, Bag>:
  sort_go(bags, Nil{})

def niche_loop.bags(fuel: Nat, k: Nat, bags: List<&2, Bag>, selected: List<&2, Nat>, rng: Rng.State) -> List<&2, Nat> & Rng.State:
  match fuel k bags:
    case 0n kk bs:
      (selected, rng)
    case f 0n bs:
      (selected, rng)
    case f kk Nil{}:
      (selected, rng)
    case 1n+f 1n+krest +b0 <> +bs:
      +bags2 = sort_bags({b0 <> bs : List<&2, Bag>})
      +rng1 = pick_ref.rng.bags(bags2, rng)
      +r = Rng.last_nat(rng1)
      +rng2 = pick_member.rng.empty.rows(bag_members_of(bags2, r), Nat.is_eq(bag_count_of(bags2, r), 0n), rng1)
      +pick = Rng.last_nat(rng2)
      +next = bags_refill(bags2, r, pick)
      niche_loop.bags(
        f,
        krest,
        next,
        List.append(&2, Nat, selected, [pick]),
        rng2
      )

def fill.rng(fuel: Nat, fronts: List<&2, List<&2, Nat>>, fits: Bool, +acc: List<&2, Nat>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat, rng: Rng.State) -> List<&2, Nat> & Rng.State:
  match fuel fronts fits:
    case 0n fs p:
      (acc, rng)
    case f Nil{} p:
      (acc, rng)
    case 1n+f +fr <> +rest False{}:
      +need = Nat.sub(target, Util.list_len(Nat, acc))
      +rows = nrows_of(asgs, fr)
      niche_loop.bags(
        1n+Util.list_len(NRow, rows),
        need,
        bags_of(seed_counts(asgs, acc, Util.zeros_nat(n_dirs)), rows),
        acc,
        rng
      )
    case 1n+f +fr <> +rest True{}:
      +new_acc = List.append(&2, Nat, acc, fr)
      fill.rng(
        f,
        rest,
        Nat.is_le(Nat.add(Util.list_len(Nat, new_acc), head_len(rest)), target),
        new_acc,
        target,
        asgs,
        n_dirs,
        rng
      )

def fill.wrap.rng(+fronts: List<&2, List<&2, Nat>>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat, rng: Rng.State) -> List<&2, Nat> & Rng.State:
  fill.rng(
    1n+n_fronts(fronts),
    fronts,
    Nat.is_le(head_len(fronts), target),
    Nil{},
    target,
    asgs,
    n_dirs,
    rng
  )

def select_idx.with(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, +fronts: List<&2, List<&2, Nat>>, pair: Norm.State & List<&2, List<&2, F32>>) -> List<&2, Nat>:
  (st, F) = pair
  fill.wrap(fronts, target, associate(pop, F, dirs), Util.list_len(List<&2, F32>, dirs))

def select_idx.big(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Nat>:
  +fronts = NDS.sort(pop)
  select_idx.with(pop, target, dirs, fronts, Norm.normalize_nd(Norm.new_state(0n), pop, front0(fronts)))

def select_idx.dirs(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, empty_dirs: Bool) -> List<&2, Nat>:
  match empty_dirs:
    case True{}:
      List.take(&2, Nat, List.range(Util.list_len(Ind.Individual, pop)), target)
    case False{}:
      select_idx.big(pop, target, dirs)

def select_idx.by(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, small: Bool) -> List<&2, Nat>:
  match small:
    case True{}:
      List.range(Util.list_len(Ind.Individual, pop))
    case False{}:
      select_idx.dirs(pop, target, dirs, List.is_empty(&2, List<&2, F32>, dirs))

# --- constrained survival (C# NondominatedSortingSurvival) ---
# An all-feasible pool stays on the paths above. A mixed or infeasible
# pool niches only the feasible subset and fills a shortfall by ascending
# CV (original index breaks ties). Fillers are not niche-linked.
# All-infeasible does not move the hyperplane.

type CvRow is Data:
  CvRow{
    i: Nat
    ind: Ind.Individual
  }

def any_infeas.on(later: Bool, feas: Bool) -> Bool:
  match feas:
    case False{}:
      True{}
    case True{}:
      later

def any_infeas(pop: List<&2, Ind.Individual>) -> Bool:
  match pop:
    case Nil{}:
      False{}
    case h <> t:
      any_infeas.on(any_infeas(t), Ind.feasible(h))

def row_before(a: CvRow, b: CvRow) -> Bool:
  match a b:
    case CvRow{i, ind} CvRow{j, other}:
      +ca = Ind.constraint_violation(ind)
      +cb = Ind.constraint_violation(other)
      Bool.or(F32.is_lt(ca, cb), Bool.and(F32.is_eq(ca, cb), Bool.not(Nat.is_le(j, i))))

# Insertion sort step. One def: the recursive call is only the
# `before = False` arm, and that arm's tail is the original rest.
# `before = True` conses onto that same rest (no second insert).
# phase 0 reads the next cons; phase 1 places the row. Fuel is 1+2|xs|.
# Recursing through a tail that already contains `x`, then consing `x`
# again, duplicates the row. Each smaller CV doubles the list. At the
# constrained budgets that exponential spine overflows the native stack
# (`memory fault (machine stack overflow?)` on OSY / C1-DTLZ1; TNK
# fail-stops). `src/constrained_budget.bend` runs those budgets.
def insert_row.go(fuel: Nat, phase: Nat, before: Bool, +x: CvRow, xs: List<&2, CvRow>, +h: CvRow) -> List<&2, CvRow>:
  match fuel phase before:
    case 0n p b:
      x <> xs
    case 1n+f 0n b:
      match xs:
        case Nil{}:
          x <> Nil{}
        case +head <> tail:
          insert_row.go(f, 1n, row_before(x, head), x, tail, head)
    case 1n+f 1n+ph True{}:
      x <> h <> xs
    case 1n+f 1n+ph False{}:
      h <> insert_row.go(f, 0n, False{}, x, xs, h)

def insert_row(+x: CvRow, +xs: List<&2, CvRow>) -> List<&2, CvRow>:
  insert_row.go(Nat.add(1n, Nat.mul(2n, Util.list_len(CvRow, xs))), 0n, False{}, x, xs, x)

def sort_rows(xs: List<&2, CvRow>) -> List<&2, CvRow>:
  match xs:
    case Nil{}:
      Nil{}
    case h <> t:
      insert_row(h, sort_rows(t))

def row_ind(row: CvRow) -> Ind.Individual:
  match row:
    case CvRow{i, ind}:
      ind

def rows_inds(xs: List<&2, CvRow>) -> List<&2, Ind.Individual>:
  match xs:
    case Nil{}:
      Nil{}
    case h <> t:
      row_ind(h) <> rows_inds(t)

def map_clear(xs: List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
  match xs:
    case Nil{}:
      Nil{}
    case h <> t:
      Ind.clear_niche(h) <> map_clear(t)

def take_clear(rows: List<&2, CvRow>, +n: Nat) -> List<&2, Ind.Individual>:
  map_clear(List.take(&2, Ind.Individual, rows_inds(sort_rows(rows)), n))

def append_fill(+kept: List<&2, Ind.Individual>, rows: List<&2, CvRow>, +target: Nat) -> List<&2, Ind.Individual>:
  List.append(
    &2,
    Ind.Individual,
    kept,
    take_clear(rows, Nat.sub(target, Util.list_len(Ind.Individual, kept)))
  )

def unused_idxs(+used: List<&2, Nat>, +n: Nat) -> List<&2, Nat>:
  Util.minus(List.range(n), used)

# Length lock: |take(pad(core, want, n), want)| = want when want ≤ n.
# Identity when core is already a unique subset of 0..n-1 of length want
# (the fill / range / take paths used in A/B).
def pad_idxs(+xs: List<&2, Nat>, +want: Nat, +n: Nat) -> List<&2, Nat>:
  List.append(&2, Nat, xs, List.take(&2, Nat, unused_idxs(xs, n), Nat.sub(want, Util.list_len(Nat, xs))))

def clip_idxs(+xs: List<&2, Nat>, +want: Nat) -> List<&2, Nat>:
  List.take(&2, Nat, xs, want)

def size_lock(+xs: List<&2, Nat>, +want: Nat, +n: Nat) -> List<&2, Nat>:
  clip_idxs(List.append(&2, Nat, pad_idxs(xs, want, n), List.range(want)), want)

def select_idx(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Nat>:
  +n = Util.list_len(Ind.Individual, combined)
  +want = Util.nat_min(target_size, n)
  size_lock(select_idx.by(combined, target_size, dirs, Nat.is_le(n, target_size)), want, n)

def select_plain(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
  gather(combined, select_idx(combined, target_size, dirs))

# Feasible subset already fits: keep original order. Niching runs only
# when that subset is longer than the slot count.
def feas_keep.det.on(+feas: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, fits: Bool) -> List<&2, Ind.Individual>:
  match fits:
    case True{}:
      feas
    case False{}:
      select_plain(feas, target, dirs)

def feas_keep.det(+feas: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
  feas_keep.det.on(feas, target, dirs, Nat.is_le(Util.list_len(Ind.Individual, feas), target))

type Split is Data:
  Split{
    feas: List<&2, Ind.Individual>
    rows: List<&2, CvRow>
  }

def split_add.feas(+h: Ind.Individual, sp: Split) -> Split:
  match sp:
    case Split{feas, rows}:
      Split{h <> feas, rows}

def split_add.infeas(+h: Ind.Individual, +i: Nat, sp: Split) -> Split:
  match sp:
    case Split{feas, rows}:
      Split{feas, CvRow{i, h} <> rows}

def split_on(+h: Ind.Individual, rest: Split, +i: Nat, feas: Bool) -> Split:
  match feas:
    case True{}:
      split_add.feas(h, rest)
    case False{}:
      split_add.infeas(h, i, rest)

def split.go(pop: List<&2, Ind.Individual>, +i: Nat) -> Split:
  match pop:
    case Nil{}:
      Split{Nil{}, Nil{}}
    case +h <> t:
      split_on(h, split.go(t, 1n+i), i, Ind.feasible(h))

def select_constrained.feas(feas: List<&2, Ind.Individual>, +rows: List<&2, CvRow>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
  match feas:
    case Nil{}:
      take_clear(rows, target)
    case h <> t:
      append_fill(feas_keep.det(h <> t, target, dirs), rows, target)

def select_constrained.from(sp: Split, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
  match sp:
    case Split{feas, rows}:
      select_constrained.feas(feas, rows, target, dirs)

def select_constrained(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
  select_constrained.from(split.go(pop, 0n), target, dirs)

# All-feasible Run path. Defined before constrained fill so a feasible
# subset that still needs niching calls this directly (no cycle through
# select_st).
def size_lock.rng(+want: Nat, +n: Nat, pair: List<&2, Nat> & Rng.State) -> List<&2, Nat> & Rng.State:
  (xs, rng) = pair
  (size_lock(xs, want, n), rng)

def select_st.after(+st: Norm.State, +pop: List<&2, Ind.Individual>, pair: List<&2, Nat> & Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  (idxs, rng2) = pair
  (st, gather(pop, idxs), rng2)

def select_st.with(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, +fronts: List<&2, List<&2, Nat>>, pair: Norm.State & List<&2, List<&2, F32>>, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  (st, F) = pair
  +n = Util.list_len(Ind.Individual, pop)
  +want = Util.nat_min(target, n)
  select_st.after(st, pop, size_lock.rng(want, n, fill.wrap.rng(fronts, target, associate(pop, F, dirs), Util.list_len(List<&2, F32>, dirs), rng)))

def select_st.big(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  +fronts = NDS.sort(pop)
  select_st.with(pop, target, dirs, fronts, Norm.normalize_nd(state, pop, front0(fronts)), rng)

def select_st.take(+pop: List<&2, Ind.Individual>, +target: Nat, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  +n = Util.list_len(Ind.Individual, pop)
  (state, gather(pop, size_lock(List.take(&2, Nat, List.range(n), target), Util.nat_min(target, n), n)), rng)

def select_st.dirs(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State, empty_dirs: Bool) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  match empty_dirs:
    case True{}:
      select_st.take(pop, target, state, rng)
    case False{}:
      select_st.big(pop, target, dirs, state, rng)

def feas_keep.st.fit.unpack(+feas: List<&2, Ind.Individual>, rng: Rng.State, pair: Norm.State & List<&2, List<&2, F32>>) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  (st, fs) = pair
  (st, feas, rng)

def feas_keep.st.fit(+feas: List<&2, Ind.Individual>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  feas_keep.st.fit.unpack(feas, rng, Norm.normalize_nd(state, feas, front0(NDS.sort(feas))))

def feas_keep.st.on(+feas: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State, fits: Bool) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  match fits:
    case True{}:
      feas_keep.st.fit(feas, state, rng)
    case False{}:
      select_st.dirs(feas, target, dirs, state, rng, List.is_empty(&2, List<&2, F32>, dirs))

def feas_keep.st(+feas: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  feas_keep.st.on(feas, target, dirs, state, rng, Nat.is_le(Util.list_len(Ind.Individual, feas), target))

def select_st.constrained.kept(+rows: List<&2, CvRow>, +target: Nat, trip: Norm.State & List<&2, Ind.Individual> & Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  (st, kept, rng2) = trip
  (st, append_fill(kept, rows, target), rng2)

def select_st.constrained.feas(feas: List<&2, Ind.Individual>, +rows: List<&2, CvRow>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  match feas:
    case Nil{}:
      (state, take_clear(rows, target), rng)
    case h <> t:
      select_st.constrained.kept(rows, target, feas_keep.st(h <> t, target, dirs, state, rng))

def select_st.constrained.from(sp: Split, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  match sp:
    case Split{feas, rows}:
      select_st.constrained.feas(feas, rows, target, dirs, state, rng)

def select_st.constrained(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  select_st.constrained.from(split.go(pop, 0n), target, dirs, state, rng)

def select.route(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>, constrained: Bool) -> List<&2, Ind.Individual>:
  match constrained:
    case True{}:
      select_constrained(combined, target_size, dirs)
    case False{}:
      select_plain(combined, target_size, dirs)

# `select` stays the rng-null length-locked path (`Laws.select_size`).
# Constrained feasible-niching + CV fill is `select_st` (Run).
def select(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
  select_plain(combined, target_size, dirs)

# Persistent-normalization Select for Unsga3Algorithm.Run. Threads rng
# so last-front niching matches C# Select(..., rng) on min-count niche
# ties. Empty niches take closest; extras are random among near-best
# on that ray. v0 `select` stays the `rng == null` path (empty laws).
def select_st.large(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State, bad: Bool) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  match bad:
    case False{}:
      select_st.dirs(pop, target, dirs, state, rng, List.is_empty(&2, List<&2, F32>, dirs))
    case True{}:
      select_st.constrained(pop, target, dirs, state, rng)

def select_st.by(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State, small: Bool) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  match small:
    case True{}:
      (state, pop, rng)
    case False{}:
      select_st.large(pop, target, dirs, state, rng, any_infeas(pop))

def select_st(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
  +n = Util.list_len(Ind.Individual, combined)
  select_st.by(combined, target_size, dirs, state, rng, Nat.is_le(n, target_size))