survival.bend

unified-nsga-iii@0.2.2.0 · 1,276 lines · 183 definitions

1# Survival / niching — C# ReferencePointManager + NondominatedSortingSurvival.
2# Independent maps (associate / histograms / gather) use mid-split
3# `a b = f(lo) f(hi)`. Nearest-ref stays sequential (associate_raw already
4# splits per individual). Perpendicular distance squares `f - t*w` in one
5# walk (same F32 order as scale-then-subtract). Last-front fill builds
6# `NRow{i, ref, dist}` once so the sequential niche loop never `List.get`s
7# an Assignment (or a fat
8# Individual) per remaining candidate. Run's rng fill groups those rows
9# into per-ref bags so each pick walks bags, not the whole front and not
10# `List.get` on the counts spine. Same pick rules / same RNG order.
11# Associate normalized individuals to Das–Dennis rays; select `target_size`
12# from a combined pool (fill complete fronts, niche-preserve the last).
13# Deterministic when C# rng is null (`select`): lowest ref among min-count
14# niches, then min perpendicular distance if that niche is empty, else
15# lowest index. `select_st` (Run) threads rng: random among equal
16# min-count niches (C# Select(..., rng)). Empty niches take the closest
17# unused member; extras draw among members within 2×best+0.01 of the
18# ray — not uniform inNiche[rng.Next], which collapsed oracle ZDT2.
19
20import Base
21import unified-nsga-iii@0.2.2.0/individual.bend as Ind
22import unified-nsga-iii@0.2.2.0/non_dominated_sort.bend as NDS
23import unified-nsga-iii@0.2.2.0/normalization.bend as Norm
24import unified-nsga-iii@0.2.2.0/rng.bend as Rng
25import unified-nsga-iii@0.2.2.0/util.bend as Util
26
27type Assignment is Data:
28  MkAssignment{
29    reference_index: Nat
30    perpendicular_distance: F32
31    niche_count: Nat
32  }
33
34def asg_ref(a: Assignment) -> Nat:
35  match a:
36    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
37      reference_index
38
39def asg_dist(a: Assignment) -> F32:
40  match a:
41    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
42      perpendicular_distance
43
44def asg_count(a: Assignment) -> Nat:
45  match a:
46    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
47      niche_count
48
49def get_asg(asgs: List<&2, Assignment>, i: Nat) -> Assignment:
50  Maybe.default(&2, Assignment, List.get(&2, Assignment, asgs, i), MkAssignment{0n, 0.0, 0n})
51
52def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
53  Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))
54
55# Last-front row: population index plus the two fields the fill loop
56# reads. Built once from `asgs` so each pick walks this thin list
57# instead of `List.get` into the combined-pool assignment spine.
58type NRow is Data:
59  NRow{
60    i: Nat
61    r: Nat
62    d: F32
63  }
64
65def nrow_i(row: NRow) -> Nat:
66  match row:
67    case NRow{i, r, d}:
68      i
69
70def nrow_r(row: NRow) -> Nat:
71  match row:
72    case NRow{i, r, d}:
73      r
74
75def nrow_d(row: NRow) -> F32:
76  match row:
77    case NRow{i, r, d}:
78      d
79
80def nrows_of.go(+asgs: List<&2, Assignment>, cand: List<&2, Nat>, acc: List<&2, NRow>) -> List<&2, NRow>:
81  match cand:
82    case Nil{}:
83      List.reverse(&2, NRow, acc)
84    case +i <> rest:
85      +a = get_asg(asgs, i)
86      nrows_of.go(asgs, rest, NRow{i, asg_ref(a), asg_dist(a)} <> acc)
87
88def nrows_of(+asgs: List<&2, Assignment>, +cand: List<&2, Nat>) -> List<&2, NRow>:
89  nrows_of.go(asgs, cand, Nil{})
90
91def first_row_i(rows: List<&2, NRow>) -> Nat:
92  match rows:
93    case Nil{}:
94      0n
95    case +row <> _:
96      nrow_i(row)
97
98def get_nrow(rows: List<&2, NRow>, i: Nat) -> NRow:
99  Maybe.default(&2, NRow, List.get(&2, NRow, rows, i), NRow{0n, 0n, 0.0})
100
101def drop_nrow.put(+row: NRow, rest: List<&2, NRow>, drop: Bool) -> List<&2, NRow>:
102  match drop:
103    case True{}:
104      rest
105    case False{}:
106      row <> rest
107
108def drop_nrow(rows: List<&2, NRow>, +pick: Nat) -> List<&2, NRow>:
109  match rows:
110    case Nil{}:
111      Nil{}
112    case +row <> rest:
113      drop_nrow.put(row, drop_nrow(rest, pick), Nat.is_eq(nrow_i(row), pick))
114
115def keep_nat(h: Nat, rest: List<&2, Nat>, keep: Bool) -> List<&2, Nat>:
116  match keep:
117    case True{}:
118      h <> rest
119    case False{}:
120      rest
121
122def uniq_refs.go(rows: List<&2, NRow>, +acc: List<&2, Nat>) -> List<&2, Nat>:
123  match rows:
124    case Nil{}:
125      List.reverse(&2, Nat, acc)
126    case +row <> rest:
127      +r = nrow_r(row)
128      uniq_refs.go(rest, keep_nat(r, acc, Bool.not(Util.in_nats(r, acc))))
129
130def uniq_refs(rows: List<&2, NRow>) -> List<&2, Nat>:
131  uniq_refs.go(rows, Nil{})
132
133def min_count_rows.go(+counts: List<&2, Nat>, rows: List<&2, NRow>, +acc: Nat) -> Nat:
134  match rows:
135    case Nil{}:
136      acc
137    case +row <> rest:
138      min_count_rows.go(counts, rest, Util.nat_min(acc, Util.get_nat(counts, nrow_r(row))))
139
140def min_count_rows(+counts: List<&2, Nat>, rows: List<&2, NRow>) -> Nat:
141  min_count_rows.go(counts, rows, 4294967295n)
142
143def refs_at_seq(+counts: List<&2, Nat>, +need: Nat, refs: List<&2, Nat>) -> List<&2, Nat>:
144  match refs:
145    case Nil{}:
146      Nil{}
147    case +r <> rest:
148      keep_nat(r, refs_at_seq(counts, need, rest), Nat.is_eq(Util.get_nat(counts, r), need))
149
150def in_ref_rows(+r: Nat, rows: List<&2, NRow>) -> List<&2, NRow>:
151  match rows:
152    case Nil{}:
153      Nil{}
154    case +row <> rest:
155      Util.keep_if(NRow, row, in_ref_rows(r, rest), Nat.is_eq(nrow_r(row), r))
156
157def argmin_dist_rows.go(rows: List<&2, NRow>, +best_i: Nat, +best_d: F32) -> Nat:
158  match rows:
159    case Nil{}:
160      best_i
161    case +row <> rest:
162      +d = nrow_d(row)
163      +lt = F32.is_lt(d, best_d)
164      argmin_dist_rows.go(rest, Bool.pick(Nat, lt, nrow_i(row), best_i), Bool.pick(F32, lt, d, best_d))
165
166def argmin_dist_rows(rows: List<&2, NRow>) -> Nat:
167  match rows:
168    case Nil{}:
169      0n
170    case +row <> rest:
171      argmin_dist_rows.go(rest, nrow_i(row), nrow_d(row))
172
173def min_dist_rows.go(rows: List<&2, NRow>, +acc: F32) -> F32:
174  match rows:
175    case Nil{}:
176      acc
177    case +row <> rest:
178      +d = nrow_d(row)
179      min_dist_rows.go(rest, Bool.pick(F32, F32.is_lt(d, acc), d, acc))
180
181def min_dist_rows(rows: List<&2, NRow>) -> F32:
182  match rows:
183    case Nil{}:
184      0.0
185    case +row <> rest:
186      min_dist_rows.go(rest, nrow_d(row))
187
188def min_idx_rows.go(rows: List<&2, NRow>, +acc: Nat) -> Nat:
189  match rows:
190    case Nil{}:
191      acc
192    case +row <> rest:
193      min_idx_rows.go(rest, Util.nat_min(acc, nrow_i(row)))
194
195def min_idx_rows(rows: List<&2, NRow>) -> Nat:
196  match rows:
197    case Nil{}:
198      0n
199    case +row <> rest:
200      min_idx_rows.go(rest, nrow_i(row))
201
202def near_rows(+lim: F32, rows: List<&2, NRow>) -> List<&2, NRow>:
203  match rows:
204    case Nil{}:
205      Nil{}
206    case +row <> rest:
207      Util.keep_if(NRow, row, near_rows(lim, rest), F32.is_le(nrow_d(row), lim))
208
209# Same F32 steps as `vec_sqnorm(vec_sub(f, vec_scale(t, w)))`: left-to-right
210# `r*r` with `r = f - t*w`, no scaled-vector and residual-vector spines.
211def resid_sq(+t: F32, f: List<&2, F32>, w: List<&2, F32>) -> F32:
212  match f w:
213    case Nil{} Nil{}:
214      0.0
215    case x <> xs y <> ys:
216      +r = F32.sub(x, F32.mul(t, y))
217      F32.add(F32.mul(r, r), resid_sq(t, xs, ys))
218    case Nil{} y <> ys:
219      0.0
220    case x <> xs Nil{}:
221      0.0
222
223def perp.big(+f: List<&2, F32>, +w: List<&2, F32>, +ww: F32) -> F32:
224  +t = F32.div(Util.vec_dot(f, w), ww)
225  F32.sqrt(resid_sq(t, f, w))
226
227def perp.zero(+f: List<&2, F32>, tiny: Bool) -> F32:
228  match tiny:
229    case True{}:
230      F32.sqrt(Util.vec_sqnorm(f))
231    case False{}:
232      0.0
233
234def perp.pick(+f: List<&2, F32>, +w: List<&2, F32>, +ww: F32, tiny: Bool) -> F32:
235  match tiny:
236    case True{}:
237      perp.zero(f, True{})
238    case False{}:
239      perp.big(f, w, ww)
240
241def perp(+f: List<&2, F32>, +w: List<&2, F32>) -> F32:
242  +ww = Util.vec_sqnorm(w)
243  perp.pick(f, w, ww, F32.is_lt(ww, 0.0000000000000001))
244
245# First-min on strict `<` (ties keep the lower index). Sequential over
246# dirs; associate_raw already mid-splits per individual.
247def nearest_go(+f: List<&2, F32>, dirs: List<&2, List<&2, F32>>, +i: Nat, +best_i: Nat, +best_d: F32) -> Assignment:
248  match dirs:
249    case Nil{}:
250      MkAssignment{best_i, best_d, 0n}
251    case +w <> ws:
252      +d = perp(f, w)
253      nearest_go(
254        f,
255        ws,
256        1n+i,
257        Bool.pick(Nat, F32.is_lt(d, best_d), i, best_i),
258        Bool.pick(F32, F32.is_lt(d, best_d), d, best_d)
259      )
260
261def nearest_one(f: List<&2, F32>, dirs: List<&2, List<&2, F32>>) -> Assignment:
262  nearest_go(f, dirs, 0n, 0n, 1000000000.0)
263
264def associate_head(+dirs: List<&2, List<&2, F32>>, +ind: Ind.Individual, F: List<&2, List<&2, F32>>) -> Assignment:
265  match F:
266    case Nil{}:
267      nearest_one(Ind.objectives(ind), dirs)
268    case f <> fs:
269      nearest_one(f, dirs)
270
271# Nearest-ref per individual is independent given dirs. Mid-split pop and F.
272def associate_raw.go(
273  +dirs: List<&2, List<&2, F32>>,
274  +fuel: Nat,
275  pop: List<&2, Ind.Individual>,
276  +F: List<&2, List<&2, F32>>
277) -> List<&2, Assignment>:
278  match fuel pop:
279    case 0n Nil{}:
280      Nil{}
281    case 0n ind <> rest:
282      match F:
283        case Nil{}:
284          nearest_one(Ind.objectives(ind), dirs) <> associate_raw.go(dirs, 0n, rest, Nil{})
285        case f <> fs:
286          nearest_one(f, dirs) <> associate_raw.go(dirs, 0n, rest, fs)
287    case 1n+p Nil{}:
288      Nil{}
289    case 1n+p ind <> Nil{}:
290      associate_head(dirs, ind, F) <> Nil{}
291    case 1n+p h <> t:
292      +all = {h <> t : List<&2, Ind.Individual>}
293      +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
294      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))
295      List.append(&2, Assignment, lo, hi)
296
297def associate_raw(+pop: List<&2, Ind.Individual>, +F: List<&2, List<&2, F32>>, +dirs: List<&2, List<&2, F32>>) -> List<&2, Assignment>:
298  associate_raw.go(dirs, Util.list_len(Ind.Individual, pop), pop, F)
299
300# Histogram increments commute. Mid-split asgs, then add count vectors.
301def count_raw.go(+n: Nat, +fuel: Nat, asgs: List<&2, Assignment>) -> List<&2, Nat>:
302  match fuel asgs:
303    case 0n Nil{}:
304      Util.zeros_nat(n)
305    case 0n a <> rest:
306      Util.inc_at(count_raw.go(n, 0n, rest), asg_ref(a))
307    case 1n+p Nil{}:
308      Util.zeros_nat(n)
309    case 1n+p a <> Nil{}:
310      Util.inc_at(Util.zeros_nat(n), asg_ref(a))
311    case 1n+p h <> t:
312      +all = {h <> t : List<&2, Assignment>}
313      +mid = Nat.div(Util.list_len(Assignment, all), 2n)
314      lo hi = count_raw.go(n, p, List.take(&2, Assignment, all, mid)) count_raw.go(n, p, List.drop(&2, Assignment, all, mid))
315      Util.nats_add(lo, hi)
316
317def count_asg(+asgs: List<&2, Assignment>, +acc: List<&2, Nat>) -> List<&2, Nat>:
318  Util.nats_add(acc, count_raw.go(Util.list_len(Nat, acc), Util.list_len(Assignment, asgs), asgs))
319
320# Assignments whose reference_index lands in a length-n histogram.
321# Out-of-range refs are silent no-ops in inc_at / List.set.
322def in_bin_count(asgs: List<&2, Assignment>, +n: Nat) -> Nat:
323  match asgs:
324    case Nil{}:
325      0n
326    case +a <> rest:
327      Nat.add(Util.bin_hit(asg_ref(a), n), in_bin_count(rest, n))
328
329def with_counts.one(+counts: List<&2, Nat>, +a: Assignment) -> Assignment:
330  match a:
331    case MkAssignment{+r, d, n}:
332      MkAssignment{r, d, Util.get_nat(counts, r)}
333
334def with_counts(+counts: List<&2, Nat>, +asgs: List<&2, Assignment>) -> List<&2, Assignment>:
335  Util.map_halves(~Assignment, ~Assignment, ~List<&2, Nat>, ~with_counts.one, counts, asgs)
336
337def associate(+pop: List<&2, Ind.Individual>, +F: List<&2, List<&2, F32>>, +dirs: List<&2, List<&2, F32>>) -> List<&2, Assignment>:
338  +raw = associate_raw(pop, F, dirs)
339  with_counts(count_asg(raw, Util.zeros_nat(Util.list_len(List<&2, F32>, dirs))), raw)
340
341def front0(fronts: List<&2, List<&2, Nat>>) -> List<&2, Nat>:
342  match fronts:
343    case Nil{}:
344      Nil{}
345    case h <> t:
346      h
347
348def n_fronts(fronts: List<&2, List<&2, Nat>>) -> Nat:
349  Util.list_len(List<&2, Nat>, fronts)
350
351def head_len(fronts: List<&2, List<&2, Nat>>) -> Nat:
352  match fronts:
353    case Nil{}:
354      0n
355    case h <> t:
356      Util.list_len(Nat, h)
357
358def gather.one(+pop: List<&2, Ind.Individual>, +i: Nat) -> Ind.Individual:
359  get_ind(pop, i)
360
361def gather(+pop: List<&2, Ind.Individual>, +idxs: List<&2, Nat>) -> List<&2, Ind.Individual>:
362  Util.map_halves(~Nat, ~Ind.Individual, ~List<&2, Ind.Individual>, ~gather.one, pop, idxs)
363
364def cand_ref.one(+asgs: List<&2, Assignment>, +i: Nat) -> Nat:
365  asg_ref(get_asg(asgs, i))
366
367def cand_refs(+asgs: List<&2, Assignment>, cand: List<&2, Nat>) -> List<&2, Nat>:
368  Util.map_halves(~Nat, ~Nat, ~List<&2, Assignment>, ~cand_ref.one, asgs, cand)
369
370def min_count.go(+counts: List<&2, Nat>, +fuel: Nat, refs: List<&2, Nat>) -> Nat:
371  match fuel refs:
372    case 0n Nil{}:
373      4294967295n
374    case 0n +r <> rs:
375      Util.nat_min(Util.get_nat(counts, r), min_count.go(counts, 0n, rs))
376    case 1n+p Nil{}:
377      4294967295n
378    case 1n+p +r <> Nil{}:
379      Util.get_nat(counts, r)
380    case 1n+p h <> t:
381      +all = {h <> t : List<&2, Nat>}
382      +mid = Nat.div(Util.list_len(Nat, all), 2n)
383      lo hi = min_count.go(counts, p, List.take(&2, Nat, all, mid)) min_count.go(counts, p, List.drop(&2, Nat, all, mid))
384      Util.nat_min(lo, hi)
385
386def min_count(+counts: List<&2, Nat>, refs: List<&2, Nat>, acc: Nat) -> Nat:
387  match refs:
388    case Nil{}:
389      acc
390    case +r <> +rs:
391      +xs = {r <> rs : List<&2, Nat>}
392      Util.nat_min(acc, min_count.go(counts, Util.list_len(Nat, xs), xs))
393
394def cons_if(h: Nat, rest: List<&2, Nat>, keep: Bool) -> List<&2, Nat>:
395  match keep:
396    case True{}:
397      h <> rest
398    case False{}:
399      rest
400
401# First-occurrence unique (C# HashSet of refs-with-candidates).
402def uniq_nats.go(xs: List<&2, Nat>, +acc: List<&2, Nat>) -> List<&2, Nat>:
403  match xs:
404    case Nil{}:
405      List.reverse(&2, Nat, acc)
406    case +h <> t:
407      uniq_nats.go(t, cons_if(h, acc, Bool.not(Util.in_nats(h, acc))))
408
409def uniq_nats(xs: List<&2, Nat>) -> List<&2, Nat>:
410  uniq_nats.go(xs, Nil{})
411
412type CntNeed is Data:
413  CN{
414    counts: List<&2, Nat>
415    need: Nat
416  }
417
418def refs_at.ok(+ctx: CntNeed, +r: Nat) -> Bool:
419  match ctx:
420    case CN{counts, need}:
421      Nat.is_eq(Util.get_nat(counts, r), need)
422
423def refs_at(+counts: List<&2, Nat>, +need: Nat, refs: List<&2, Nat>) -> List<&2, Nat>:
424  Util.filter_halves(~Nat, ~CntNeed, ~refs_at.ok, CN{counts, need}, refs)
425
426def min_idx(xs: List<&2, Nat>, acc: Nat) -> Nat:
427  match xs:
428    case Nil{}:
429      acc
430    case +x <> rest:
431      min_idx(rest, Util.nat_min(acc, x))
432
433def min_idx_ne(xs: List<&2, Nat>) -> Nat:
434  match xs:
435    case Nil{}:
436      0n
437    case x <> rest:
438      min_idx(rest, x)
439
440def pick_ref(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>) -> Nat:
441  +refs = cand_refs(asgs, cand)
442  min_idx_ne(refs_at(counts, min_count(counts, refs, 4294967295n), refs))
443
444type RefPick is Data:
445  RP{
446    asgs: List<&2, Assignment>
447    r: Nat
448  }
449
450def in_ref.ok(+ctx: RefPick, +i: Nat) -> Bool:
451  match ctx:
452    case RP{asgs, r}:
453      Nat.is_eq(asg_ref(get_asg(asgs, i)), r)
454
455def in_ref(+asgs: List<&2, Assignment>, +r: Nat, cand: List<&2, Nat>) -> List<&2, Nat>:
456  Util.filter_halves(~Nat, ~RefPick, ~in_ref.ok, RP{asgs, r}, cand)
457
458def argmin_join(+asgs: List<&2, Assignment>, +ia: Nat, +ib: Nat) -> Nat:
459  Bool.pick(Nat, F32.is_lt(asg_dist(get_asg(asgs, ib)), asg_dist(get_asg(asgs, ia))), ib, ia)
460
461def argmin_dist.go(+asgs: List<&2, Assignment>, +fuel: Nat, cand: List<&2, Nat>) -> Nat:
462  match fuel cand:
463    case 0n Nil{}:
464      0n
465    case 0n +i <> Nil{}:
466      i
467    case 0n +i <> +j <> js:
468      argmin_join(asgs, i, argmin_dist.go(asgs, 0n, j <> js))
469    case 1n+p Nil{}:
470      0n
471    case 1n+p +i <> Nil{}:
472      i
473    case 1n+p h <> t:
474      +all = {h <> t : List<&2, Nat>}
475      +mid = Nat.div(Util.list_len(Nat, all), 2n)
476      lo hi = argmin_dist.go(asgs, p, List.take(&2, Nat, all, mid)) argmin_dist.go(asgs, p, List.drop(&2, Nat, all, mid))
477      argmin_join(asgs, lo, hi)
478
479def argmin_dist(+asgs: List<&2, Assignment>, cand: List<&2, Nat>) -> Nat:
480  match cand:
481    case Nil{}:
482      0n
483    case +i <> +rest:
484      +xs = {i <> rest : List<&2, Nat>}
485      argmin_dist.go(asgs, Util.list_len(Nat, xs), xs)
486
487def pick_member.by(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool) -> Nat:
488  match empty_niche:
489    case True{}:
490      argmin_dist(asgs, group)
491    case False{}:
492      min_idx_ne(group)
493
494# First remaining last-front index. Used when inNiche is empty
495# (C# would throw; never pick a phantom combined-pool index 0).
496def first_cand(cand: List<&2, Nat>) -> Nat:
497  match cand:
498    case Nil{}:
499      0n
500    case x <> _:
501      x
502
503def pick_member.by.safe(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool, +fallback: Nat) -> Nat:
504  match group:
505    case Nil{}:
506      fallback
507    case g0 <> gs:
508      pick_member.by(asgs, {g0 <> gs : List<&2, Nat>}, empty_niche)
509
510def pick_member(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, +r: Nat) -> Nat:
511  pick_member.by.safe(asgs, in_ref(asgs, r, cand), Nat.is_eq(Util.get_nat(counts, r), 0n), first_cand(cand))
512
513# Affine API: advanced State; chosen index is `Rng.last_nat` (no pair match).
514# C# Select(..., rng): draw only when more than one min-count ref.
515def pick_ref.rng.go(+mins: List<&2, Nat>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
516  match n:
517    case 0n:
518      Rng.with_k(rng, fallback)
519    case 1n:
520      Rng.with_k(rng, min_idx_ne(mins))
521    case 1n+p:
522      +rng2 = Rng.next_nat(rng, 1n+p)
523      Rng.with_k(rng2, Util.get_nat(mins, Rng.last_nat(rng2)))
524
525def pick_ref.rng.after(+mins: List<&2, Nat>, +fallback: Nat, rng: Rng.State) -> Rng.State:
526  pick_ref.rng.go(mins, Util.list_len(Nat, mins), fallback, rng)
527
528def pick_ref.rng(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, rng: Rng.State) -> Rng.State:
529  +refs = uniq_nats(cand_refs(asgs, cand))
530  pick_ref.rng.after(
531    refs_at(counts, min_count(counts, refs, 4294967295n), refs),
532    asg_ref(get_asg(asgs, first_cand(cand))),
533    rng
534  )
535
536# Uniform inNiche[rng.Next] (C# non-empty + rng) lets far-from-ray last-front
537# junk into a niche. With this LCG that pile-up dominates ZDT2's concave
538# front (x0 → 0). Draw extras only among members within 2×best+0.01 of
539# the ray (first assignment to a niche stays closest).
540def near_lim(+best: F32) -> F32:
541  F32.add(F32.mul(best, 2.0), 0.01)
542
543def near_ok(+asgs: List<&2, Assignment>, +i: Nat, +lim: F32) -> Bool:
544  F32.is_le(asg_dist(get_asg(asgs, i)), lim)
545
546type NearPick is Data:
547  NP{
548    asgs: List<&2, Assignment>
549    lim: F32
550  }
551
552def near_members.ok(+ctx: NearPick, +i: Nat) -> Bool:
553  match ctx:
554    case NP{asgs, lim}:
555      near_ok(asgs, i, lim)
556
557def near_members(+asgs: List<&2, Assignment>, group: List<&2, Nat>, +lim: F32) -> List<&2, Nat>:
558  Util.filter_halves(~Nat, ~NearPick, ~near_members.ok, NP{asgs, lim}, group)
559
560def pick_among.rng(+group: List<&2, Nat>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
561  match n:
562    case 0n:
563      Rng.with_k(rng, fallback)
564    case 1n:
565      Rng.with_k(rng, min_idx_ne(group))
566    case 1n+p:
567      +rng2 = Rng.next_nat(rng, 1n+p)
568      Rng.with_k(rng2, Util.get_nat(group, Rng.last_nat(rng2)))
569
570def pick_near.rng(+asgs: List<&2, Assignment>, +group: List<&2, Nat>, rng: Rng.State) -> Rng.State:
571  +near = near_members(asgs, group, near_lim(asg_dist(get_asg(asgs, argmin_dist(asgs, group)))))
572  pick_among.rng(near, Util.list_len(Nat, near), first_cand(group), rng)
573
574def pick_member.rng.empty(+asgs: List<&2, Assignment>, +group: List<&2, Nat>, empty_niche: Bool, rng: Rng.State) -> Rng.State:
575  match empty_niche:
576    case True{}:
577      Rng.with_k(rng, argmin_dist(asgs, group))
578    case False{}:
579      pick_near.rng(asgs, group, rng)
580
581def pick_member.rng.by(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool, +fallback: Nat, rng: Rng.State) -> Rng.State:
582  match group:
583    case Nil{}:
584      Rng.with_k(rng, fallback)
585    case g0 <> gs:
586      pick_member.rng.empty(asgs, {g0 <> gs : List<&2, Nat>}, empty_niche, rng)
587
588def pick_member.rng(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, +r: Nat, rng: Rng.State) -> Rng.State:
589  pick_member.rng.by(
590    asgs,
591    in_ref(asgs, r, cand),
592    Nat.is_eq(Util.get_nat(counts, r), 0n),
593    first_cand(cand),
594    rng
595  )
596
597def seed_raw.go(+asgs: List<&2, Assignment>, +n: Nat, +fuel: Nat, selected: List<&2, Nat>) -> List<&2, Nat>:
598  match fuel selected:
599    case 0n Nil{}:
600      Util.zeros_nat(n)
601    case 0n +i <> rest:
602      Util.inc_at(seed_raw.go(asgs, n, 0n, rest), asg_ref(get_asg(asgs, i)))
603    case 1n+p Nil{}:
604      Util.zeros_nat(n)
605    case 1n+p +i <> Nil{}:
606      Util.inc_at(Util.zeros_nat(n), asg_ref(get_asg(asgs, i)))
607    case 1n+p h <> t:
608      +all = {h <> t : List<&2, Nat>}
609      +mid = Nat.div(Util.list_len(Nat, all), 2n)
610      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))
611      Util.nats_add(lo, hi)
612
613def seed_counts(+asgs: List<&2, Assignment>, +selected: List<&2, Nat>, +acc: List<&2, Nat>) -> List<&2, Nat>:
614  Util.nats_add(acc, seed_raw.go(asgs, Util.list_len(Nat, acc), Util.list_len(Nat, selected), selected))
615
616# fuel, k, cand first so the match follows binder order and fuel shrinks.
617def pick_ref.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>) -> Nat:
618  +refs = uniq_refs(rows)
619  min_idx_ne(refs_at_seq(counts, min_count_rows(counts, rows), refs))
620
621def pick_member.by.ne.rows(+group: List<&2, NRow>, empty_niche: Bool) -> Nat:
622  match empty_niche:
623    case True{}:
624      argmin_dist_rows(group)
625    case False{}:
626      min_idx_rows(group)
627
628def pick_member.by.rows(group: List<&2, NRow>, empty_niche: Bool, +fallback: Nat) -> Nat:
629  match group:
630    case Nil{}:
631      fallback
632    case g0 <> gs:
633      pick_member.by.ne.rows({g0 <> gs : List<&2, NRow>}, empty_niche)
634
635def pick_member.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>, +r: Nat) -> Nat:
636  pick_member.by.rows(in_ref_rows(r, rows), Nat.is_eq(Util.get_nat(counts, r), 0n), first_row_i(rows))
637
638def pick_among.nrows(+rows: List<&2, NRow>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
639  match n:
640    case 0n:
641      Rng.with_k(rng, fallback)
642    case 1n:
643      Rng.with_k(rng, first_row_i(rows))
644    case 1n+p:
645      +rng2 = Rng.next_nat(rng, 1n+p)
646      Rng.with_k(rng2, nrow_i(get_nrow(rows, Rng.last_nat(rng2))))
647
648def pick_near.rng.rows(+group: List<&2, NRow>, rng: Rng.State) -> Rng.State:
649  +near = near_rows(near_lim(min_dist_rows(group)), group)
650  pick_among.nrows(near, Util.list_len(NRow, near), first_row_i(group), rng)
651
652def pick_member.rng.empty.rows(+group: List<&2, NRow>, empty_niche: Bool, rng: Rng.State) -> Rng.State:
653  match empty_niche:
654    case True{}:
655      Rng.with_k(rng, argmin_dist_rows(group))
656    case False{}:
657      pick_near.rng.rows(group, rng)
658
659def niche_loop(fuel: Nat, k: Nat, rows: List<&2, NRow>, +counts: List<&2, Nat>, selected: List<&2, Nat>) -> List<&2, Nat>:
660  match fuel k rows:
661    case 0n kk r:
662      selected
663    case f 0n r:
664      selected
665    case f kk Nil{}:
666      selected
667    case 1n+f 1n+krest +r0 <> +rs:
668      +rows2 = {r0 <> rs : List<&2, NRow>}
669      +r = pick_ref.rows(counts, rows2)
670      +pick = pick_member.rows(counts, rows2, r)
671      niche_loop(
672        f,
673        krest,
674        drop_nrow(rows2, pick),
675        Util.inc_at(counts, r),
676        List.append(&2, Nat, selected, [pick])
677      )
678
679def 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>:
680  match fuel fronts fits:
681    case 0n fs p:
682      acc
683    case f Nil{} p:
684      acc
685    case 1n+f +fr <> +rest False{}:
686      +need = Nat.sub(target, Util.list_len(Nat, acc))
687      +rows = nrows_of(asgs, fr)
688      niche_loop(
689        1n+Util.list_len(NRow, rows),
690        need,
691        rows,
692        seed_counts(asgs, acc, Util.zeros_nat(n_dirs)),
693        acc
694      )
695    case 1n+f +fr <> +rest True{}:
696      +new_acc = List.append(&2, Nat, acc, fr)
697      fill(
698        f,
699        rest,
700        Nat.is_le(Nat.add(Util.list_len(Nat, new_acc), head_len(rest)), target),
701        new_acc,
702        target,
703        asgs,
704        n_dirs
705      )
706
707def fill.wrap(+fronts: List<&2, List<&2, Nat>>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat) -> List<&2, Nat>:
708  fill(
709    1n+n_fronts(fronts),
710    fronts,
711    Nat.is_le(head_len(fronts), target),
712    Nil{},
713    target,
714    asgs,
715    n_dirs
716  )
717
718# Occupied last-front reference. Members stay in original row order.
719# `pos` is that row's place in the last front, so a per-pick sort by the
720# earliest remaining member restores first-seen ref order (deleting an
721# early row can move its ref behind one that started later). `count` is
722# the niche histogram, not the member length. Counts live on the bag, so
723# a pick does not `List.get` the counts spine.
724type MRow is Data:
725  MRow{
726    pos: Nat
727    row: NRow
728  }
729
730type Bag is Data:
731  Bag{
732    ref: Nat
733    count: Nat
734    members: List<&2, MRow>
735  }
736
737def head_is_ref(bags: List<&2, Bag>, +r: Nat) -> Bool:
738  match bags:
739    case Nil{}:
740      False{}
741    case Bag{+ref, count, members} <> _:
742      Nat.is_eq(ref, r)
743
744def bag_put.go(
745  bags: List<&2, Bag>,
746  +row: NRow,
747  +seeded: Nat,
748  +pos: Nat,
749  +rev: List<&2, Bag>,
750  same: Bool
751) -> List<&2, Bag>:
752  match bags same:
753    case Nil{} p:
754      List.append(&2, Bag, List.reverse(&2, Bag, rev), [Bag{nrow_r(row), seeded, [MRow{pos, row}]}])
755    case Bag{+ref, +count, +members} <> rest True{}:
756      List.append(
757        &2,
758        Bag,
759        List.reverse(&2, Bag, rev),
760        Bag{ref, count, List.append(&2, MRow, members, [MRow{pos, row}])} <> rest
761      )
762    case Bag{+ref, +count, +members} <> +rest False{}:
763      bag_put.go(rest, row, seeded, pos, Bag{ref, count, members} <> rev, head_is_ref(rest, nrow_r(row)))
764
765def bag_put(+bags: List<&2, Bag>, +row: NRow, +seeded: Nat, +pos: Nat) -> List<&2, Bag>:
766  bag_put.go(bags, row, seeded, pos, Nil{}, head_is_ref(bags, nrow_r(row)))
767
768def bags_of.go(+counts: List<&2, Nat>, rows: List<&2, NRow>, +acc: List<&2, Bag>, +pos: Nat) -> List<&2, Bag>:
769  match rows:
770    case Nil{}:
771      acc
772    case +row <> rest:
773      bags_of.go(counts, rest, bag_put(acc, row, Util.get_nat(counts, nrow_r(row)), pos), 1n+pos)
774
775def bags_of(+counts: List<&2, Nat>, +rows: List<&2, NRow>) -> List<&2, Bag>:
776  bags_of.go(counts, rows, Nil{}, 0n)
777
778def first_bag_ref(bags: List<&2, Bag>) -> Nat:
779  match bags:
780    case Nil{}:
781      0n
782    case Bag{+ref, count, members} <> _:
783      ref
784
785def min_bag_count.go(bags: List<&2, Bag>, +acc: Nat) -> Nat:
786  match bags:
787    case Nil{}:
788      acc
789    case Bag{ref, +count, members} <> rest:
790      min_bag_count.go(rest, Util.nat_min(acc, count))
791
792def min_bag_count(bags: List<&2, Bag>) -> Nat:
793  min_bag_count.go(bags, 4294967295n)
794
795def refs_of_count.go(bags: List<&2, Bag>, +need: Nat, +acc: List<&2, Nat>) -> List<&2, Nat>:
796  match bags:
797    case Nil{}:
798      List.reverse(&2, Nat, acc)
799    case Bag{+ref, +count, members} <> rest:
800      refs_of_count.go(rest, need, keep_nat(ref, acc, Nat.is_eq(count, need)))
801
802def refs_of_count(+bags: List<&2, Bag>) -> List<&2, Nat>:
803  refs_of_count.go(bags, min_bag_count(bags), Nil{})
804
805def pick_ref.rng.bags(+bags: List<&2, Bag>, rng: Rng.State) -> Rng.State:
806  pick_ref.rng.after(refs_of_count(bags), first_bag_ref(bags), rng)
807
808def bag_count_go(bags: List<&2, Bag>, +r: Nat, hit: Bool) -> Nat:
809  match bags hit:
810    case Nil{} p:
811      0n
812    case Bag{ref, +count, members} <> rest True{}:
813      count
814    case Bag{ref, count, members} <> +rest False{}:
815      bag_count_go(rest, r, head_is_ref(rest, r))
816
817def bag_count_of(+bags: List<&2, Bag>, +r: Nat) -> Nat:
818  bag_count_go(bags, r, head_is_ref(bags, r))
819
820def mrows_rows(ms: List<&2, MRow>) -> List<&2, NRow>:
821  match ms:
822    case Nil{}:
823      Nil{}
824    case MRow{pos, +row} <> rest:
825      row <> mrows_rows(rest)
826
827def bag_members_go(bags: List<&2, Bag>, +r: Nat, hit: Bool) -> List<&2, NRow>:
828  match bags hit:
829    case Nil{} p:
830      Nil{}
831    case Bag{ref, count, +members} <> rest True{}:
832      mrows_rows(members)
833    case Bag{ref, count, members} <> +rest False{}:
834      bag_members_go(rest, r, head_is_ref(rest, r))
835
836def bag_members_of(+bags: List<&2, Bag>, +r: Nat) -> List<&2, NRow>:
837  bag_members_go(bags, r, head_is_ref(bags, r))
838
839def drop_mrow.put(+row: MRow, rest: List<&2, MRow>, drop: Bool) -> List<&2, MRow>:
840  match drop:
841    case True{}:
842      rest
843    case False{}:
844      row <> rest
845
846def drop_mrow(ms: List<&2, MRow>, +pick: Nat) -> List<&2, MRow>:
847  match ms:
848    case Nil{}:
849      Nil{}
850    case MRow{+pos, +row} <> rest:
851      drop_mrow.put(MRow{pos, row}, drop_mrow(rest, pick), Nat.is_eq(nrow_i(row), pick))
852
853def bags_kept(+ref: Nat, +count: Nat, members: List<&2, MRow>, rest: List<&2, Bag>) -> List<&2, Bag>:
854  match members:
855    case Nil{}:
856      rest
857    case +m <> +ms:
858      Bag{ref, 1n+count, {m <> ms : List<&2, MRow>}} <> rest
859
860def bags_refill.go(bags: List<&2, Bag>, +r: Nat, +pick: Nat, hit: Bool) -> List<&2, Bag>:
861  match bags hit:
862    case Nil{} p:
863      Nil{}
864    case Bag{+ref, +count, +members} <> rest True{}:
865      bags_kept(ref, count, drop_mrow(members, pick), rest)
866    case Bag{+ref, +count, +members} <> +rest False{}:
867      Bag{ref, count, members} <> bags_refill.go(rest, r, pick, head_is_ref(rest, r))
868
869def bags_refill(+bags: List<&2, Bag>, +r: Nat, +pick: Nat) -> List<&2, Bag>:
870  bags_refill.go(bags, r, pick, head_is_ref(bags, r))
871
872def head_pos.ms(ms: List<&2, MRow>) -> Nat:
873  match ms:
874    case Nil{}:
875      4294967295n
876    case MRow{+pos, row} <> _:
877      pos
878
879def head_pos(b: Bag) -> Nat:
880  match b:
881    case Bag{ref, count, +members}:
882      head_pos.ms(members)
883
884def insert_before(acc: List<&2, Bag>, +b: Bag) -> Bool:
885  match acc:
886    case Nil{}:
887      True{}
888    case +h <> _:
889      Nat.is_le(head_pos(b), head_pos(h))
890
891def insert_bag(acc: List<&2, Bag>, +b: Bag, before: Bool) -> List<&2, Bag>:
892  match acc before:
893    case Nil{} p:
894      [b]
895    case +h <> t True{}:
896      b <> {h <> t : List<&2, Bag>}
897    case +h <> +t False{}:
898      h <> insert_bag(t, b, insert_before(t, b))
899
900def sort_put(+acc: List<&2, Bag>, +b: Bag) -> List<&2, Bag>:
901  insert_bag(acc, b, insert_before(acc, b))
902
903def sort_go(bags: List<&2, Bag>, +acc: List<&2, Bag>) -> List<&2, Bag>:
904  match bags:
905    case Nil{}:
906      acc
907    case +b <> rest:
908      sort_go(rest, sort_put(acc, b))
909
910def sort_bags(+bags: List<&2, Bag>) -> List<&2, Bag>:
911  sort_go(bags, Nil{})
912
913def niche_loop.bags(fuel: Nat, k: Nat, bags: List<&2, Bag>, selected: List<&2, Nat>, rng: Rng.State) -> List<&2, Nat> & Rng.State:
914  match fuel k bags:
915    case 0n kk bs:
916      (selected, rng)
917    case f 0n bs:
918      (selected, rng)
919    case f kk Nil{}:
920      (selected, rng)
921    case 1n+f 1n+krest +b0 <> +bs:
922      +bags2 = sort_bags({b0 <> bs : List<&2, Bag>})
923      +rng1 = pick_ref.rng.bags(bags2, rng)
924      +r = Rng.last_nat(rng1)
925      +rng2 = pick_member.rng.empty.rows(bag_members_of(bags2, r), Nat.is_eq(bag_count_of(bags2, r), 0n), rng1)
926      +pick = Rng.last_nat(rng2)
927      +next = bags_refill(bags2, r, pick)
928      niche_loop.bags(
929        f,
930        krest,
931        next,
932        List.append(&2, Nat, selected, [pick]),
933        rng2
934      )
935
936def 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:
937  match fuel fronts fits:
938    case 0n fs p:
939      (acc, rng)
940    case f Nil{} p:
941      (acc, rng)
942    case 1n+f +fr <> +rest False{}:
943      +need = Nat.sub(target, Util.list_len(Nat, acc))
944      +rows = nrows_of(asgs, fr)
945      niche_loop.bags(
946        1n+Util.list_len(NRow, rows),
947        need,
948        bags_of(seed_counts(asgs, acc, Util.zeros_nat(n_dirs)), rows),
949        acc,
950        rng
951      )
952    case 1n+f +fr <> +rest True{}:
953      +new_acc = List.append(&2, Nat, acc, fr)
954      fill.rng(
955        f,
956        rest,
957        Nat.is_le(Nat.add(Util.list_len(Nat, new_acc), head_len(rest)), target),
958        new_acc,
959        target,
960        asgs,
961        n_dirs,
962        rng
963      )
964
965def 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:
966  fill.rng(
967    1n+n_fronts(fronts),
968    fronts,
969    Nat.is_le(head_len(fronts), target),
970    Nil{},
971    target,
972    asgs,
973    n_dirs,
974    rng
975  )
976
977def 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>:
978  (st, F) = pair
979  fill.wrap(fronts, target, associate(pop, F, dirs), Util.list_len(List<&2, F32>, dirs))
980
981def select_idx.big(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Nat>:
982  +fronts = NDS.sort(pop)
983  select_idx.with(pop, target, dirs, fronts, Norm.normalize_nd(Norm.new_state(0n), pop, front0(fronts)))
984
985def select_idx.dirs(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, empty_dirs: Bool) -> List<&2, Nat>:
986  match empty_dirs:
987    case True{}:
988      List.take(&2, Nat, List.range(Util.list_len(Ind.Individual, pop)), target)
989    case False{}:
990      select_idx.big(pop, target, dirs)
991
992def select_idx.by(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, small: Bool) -> List<&2, Nat>:
993  match small:
994    case True{}:
995      List.range(Util.list_len(Ind.Individual, pop))
996    case False{}:
997      select_idx.dirs(pop, target, dirs, List.is_empty(&2, List<&2, F32>, dirs))
998
999# --- constrained survival (C# NondominatedSortingSurvival) ---
1000# An all-feasible pool stays on the paths above. A mixed or infeasible
1001# pool niches only the feasible subset and fills a shortfall by ascending
1002# CV (original index breaks ties). Fillers are not niche-linked.
1003# All-infeasible does not move the hyperplane.
1004
1005type CvRow is Data:
1006  CvRow{
1007    i: Nat
1008    ind: Ind.Individual
1009  }
1010
1011def any_infeas.on(later: Bool, feas: Bool) -> Bool:
1012  match feas:
1013    case False{}:
1014      True{}
1015    case True{}:
1016      later
1017
1018def any_infeas(pop: List<&2, Ind.Individual>) -> Bool:
1019  match pop:
1020    case Nil{}:
1021      False{}
1022    case h <> t:
1023      any_infeas.on(any_infeas(t), Ind.feasible(h))
1024
1025def row_before(a: CvRow, b: CvRow) -> Bool:
1026  match a b:
1027    case CvRow{i, ind} CvRow{j, other}:
1028      +ca = Ind.constraint_violation(ind)
1029      +cb = Ind.constraint_violation(other)
1030      Bool.or(F32.is_lt(ca, cb), Bool.and(F32.is_eq(ca, cb), Bool.not(Nat.is_le(j, i))))
1031
1032# Insertion sort step. One def: the recursive call is only the
1033# `before = False` arm, and that arm's tail is the original rest.
1034# `before = True` conses onto that same rest (no second insert).
1035# phase 0 reads the next cons; phase 1 places the row. Fuel is 1+2|xs|.
1036# Recursing through a tail that already contains `x`, then consing `x`
1037# again, duplicates the row. Each smaller CV doubles the list. At the
1038# constrained budgets that exponential spine overflows the native stack
1039# (`memory fault (machine stack overflow?)` on OSY / C1-DTLZ1; TNK
1040# fail-stops). `src/constrained_budget.bend` runs those budgets.
1041def insert_row.go(fuel: Nat, phase: Nat, before: Bool, +x: CvRow, xs: List<&2, CvRow>, +h: CvRow) -> List<&2, CvRow>:
1042  match fuel phase before:
1043    case 0n p b:
1044      x <> xs
1045    case 1n+f 0n b:
1046      match xs:
1047        case Nil{}:
1048          x <> Nil{}
1049        case +head <> tail:
1050          insert_row.go(f, 1n, row_before(x, head), x, tail, head)
1051    case 1n+f 1n+ph True{}:
1052      x <> h <> xs
1053    case 1n+f 1n+ph False{}:
1054      h <> insert_row.go(f, 0n, False{}, x, xs, h)
1055
1056def insert_row(+x: CvRow, +xs: List<&2, CvRow>) -> List<&2, CvRow>:
1057  insert_row.go(Nat.add(1n, Nat.mul(2n, Util.list_len(CvRow, xs))), 0n, False{}, x, xs, x)
1058
1059def sort_rows(xs: List<&2, CvRow>) -> List<&2, CvRow>:
1060  match xs:
1061    case Nil{}:
1062      Nil{}
1063    case h <> t:
1064      insert_row(h, sort_rows(t))
1065
1066def row_ind(row: CvRow) -> Ind.Individual:
1067  match row:
1068    case CvRow{i, ind}:
1069      ind
1070
1071def rows_inds(xs: List<&2, CvRow>) -> List<&2, Ind.Individual>:
1072  match xs:
1073    case Nil{}:
1074      Nil{}
1075    case h <> t:
1076      row_ind(h) <> rows_inds(t)
1077
1078def map_clear(xs: List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
1079  match xs:
1080    case Nil{}:
1081      Nil{}
1082    case h <> t:
1083      Ind.clear_niche(h) <> map_clear(t)
1084
1085def take_clear(rows: List<&2, CvRow>, +n: Nat) -> List<&2, Ind.Individual>:
1086  map_clear(List.take(&2, Ind.Individual, rows_inds(sort_rows(rows)), n))
1087
1088def append_fill(+kept: List<&2, Ind.Individual>, rows: List<&2, CvRow>, +target: Nat) -> List<&2, Ind.Individual>:
1089  List.append(
1090    &2,
1091    Ind.Individual,
1092    kept,
1093    take_clear(rows, Nat.sub(target, Util.list_len(Ind.Individual, kept)))
1094  )
1095
1096def unused_idxs(+used: List<&2, Nat>, +n: Nat) -> List<&2, Nat>:
1097  Util.minus(List.range(n), used)
1098
1099# Length lock: |take(pad(core, want, n), want)| = want when want ≤ n.
1100# Identity when core is already a unique subset of 0..n-1 of length want
1101# (the fill / range / take paths used in A/B).
1102def pad_idxs(+xs: List<&2, Nat>, +want: Nat, +n: Nat) -> List<&2, Nat>:
1103  List.append(&2, Nat, xs, List.take(&2, Nat, unused_idxs(xs, n), Nat.sub(want, Util.list_len(Nat, xs))))
1104
1105def clip_idxs(+xs: List<&2, Nat>, +want: Nat) -> List<&2, Nat>:
1106  List.take(&2, Nat, xs, want)
1107
1108def size_lock(+xs: List<&2, Nat>, +want: Nat, +n: Nat) -> List<&2, Nat>:
1109  clip_idxs(List.append(&2, Nat, pad_idxs(xs, want, n), List.range(want)), want)
1110
1111def select_idx(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Nat>:
1112  +n = Util.list_len(Ind.Individual, combined)
1113  +want = Util.nat_min(target_size, n)
1114  size_lock(select_idx.by(combined, target_size, dirs, Nat.is_le(n, target_size)), want, n)
1115
1116def select_plain(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
1117  gather(combined, select_idx(combined, target_size, dirs))
1118
1119# Feasible subset already fits: keep original order. Niching runs only
1120# when that subset is longer than the slot count.
1121def feas_keep.det.on(+feas: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, fits: Bool) -> List<&2, Ind.Individual>:
1122  match fits:
1123    case True{}:
1124      feas
1125    case False{}:
1126      select_plain(feas, target, dirs)
1127
1128def feas_keep.det(+feas: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
1129  feas_keep.det.on(feas, target, dirs, Nat.is_le(Util.list_len(Ind.Individual, feas), target))
1130
1131type Split is Data:
1132  Split{
1133    feas: List<&2, Ind.Individual>
1134    rows: List<&2, CvRow>
1135  }
1136
1137def split_add.feas(+h: Ind.Individual, sp: Split) -> Split:
1138  match sp:
1139    case Split{feas, rows}:
1140      Split{h <> feas, rows}
1141
1142def split_add.infeas(+h: Ind.Individual, +i: Nat, sp: Split) -> Split:
1143  match sp:
1144    case Split{feas, rows}:
1145      Split{feas, CvRow{i, h} <> rows}
1146
1147def split_on(+h: Ind.Individual, rest: Split, +i: Nat, feas: Bool) -> Split:
1148  match feas:
1149    case True{}:
1150      split_add.feas(h, rest)
1151    case False{}:
1152      split_add.infeas(h, i, rest)
1153
1154def split.go(pop: List<&2, Ind.Individual>, +i: Nat) -> Split:
1155  match pop:
1156    case Nil{}:
1157      Split{Nil{}, Nil{}}
1158    case +h <> t:
1159      split_on(h, split.go(t, 1n+i), i, Ind.feasible(h))
1160
1161def select_constrained.feas(feas: List<&2, Ind.Individual>, +rows: List<&2, CvRow>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
1162  match feas:
1163    case Nil{}:
1164      take_clear(rows, target)
1165    case h <> t:
1166      append_fill(feas_keep.det(h <> t, target, dirs), rows, target)
1167
1168def select_constrained.from(sp: Split, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
1169  match sp:
1170    case Split{feas, rows}:
1171      select_constrained.feas(feas, rows, target, dirs)
1172
1173def select_constrained(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
1174  select_constrained.from(split.go(pop, 0n), target, dirs)
1175
1176# All-feasible Run path. Defined before constrained fill so a feasible
1177# subset that still needs niching calls this directly (no cycle through
1178# select_st).
1179def size_lock.rng(+want: Nat, +n: Nat, pair: List<&2, Nat> & Rng.State) -> List<&2, Nat> & Rng.State:
1180  (xs, rng) = pair
1181  (size_lock(xs, want, n), rng)
1182
1183def 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:
1184  (idxs, rng2) = pair
1185  (st, gather(pop, idxs), rng2)
1186
1187def 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:
1188  (st, F) = pair
1189  +n = Util.list_len(Ind.Individual, pop)
1190  +want = Util.nat_min(target, n)
1191  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)))
1192
1193def 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:
1194  +fronts = NDS.sort(pop)
1195  select_st.with(pop, target, dirs, fronts, Norm.normalize_nd(state, pop, front0(fronts)), rng)
1196
1197def select_st.take(+pop: List<&2, Ind.Individual>, +target: Nat, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
1198  +n = Util.list_len(Ind.Individual, pop)
1199  (state, gather(pop, size_lock(List.take(&2, Nat, List.range(n), target), Util.nat_min(target, n), n)), rng)
1200
1201def 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:
1202  match empty_dirs:
1203    case True{}:
1204      select_st.take(pop, target, state, rng)
1205    case False{}:
1206      select_st.big(pop, target, dirs, state, rng)
1207
1208def 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:
1209  (st, fs) = pair
1210  (st, feas, rng)
1211
1212def feas_keep.st.fit(+feas: List<&2, Ind.Individual>, state: Norm.State, rng: Rng.State) -> Norm.State & List<&2, Ind.Individual> & Rng.State:
1213  feas_keep.st.fit.unpack(feas, rng, Norm.normalize_nd(state, feas, front0(NDS.sort(feas))))
1214
1215def 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:
1216  match fits:
1217    case True{}:
1218      feas_keep.st.fit(feas, state, rng)
1219    case False{}:
1220      select_st.dirs(feas, target, dirs, state, rng, List.is_empty(&2, List<&2, F32>, dirs))
1221
1222def 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:
1223  feas_keep.st.on(feas, target, dirs, state, rng, Nat.is_le(Util.list_len(Ind.Individual, feas), target))
1224
1225def 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:
1226  (st, kept, rng2) = trip
1227  (st, append_fill(kept, rows, target), rng2)
1228
1229def 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:
1230  match feas:
1231    case Nil{}:
1232      (state, take_clear(rows, target), rng)
1233    case h <> t:
1234      select_st.constrained.kept(rows, target, feas_keep.st(h <> t, target, dirs, state, rng))
1235
1236def 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:
1237  match sp:
1238    case Split{feas, rows}:
1239      select_st.constrained.feas(feas, rows, target, dirs, state, rng)
1240
1241def 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:
1242  select_st.constrained.from(split.go(pop, 0n), target, dirs, state, rng)
1243
1244def select.route(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>, constrained: Bool) -> List<&2, Ind.Individual>:
1245  match constrained:
1246    case True{}:
1247      select_constrained(combined, target_size, dirs)
1248    case False{}:
1249      select_plain(combined, target_size, dirs)
1250
1251# `select` stays the rng-null length-locked path (`Laws.select_size`).
1252# Constrained feasible-niching + CV fill is `select_st` (Run).
1253def select(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
1254  select_plain(combined, target_size, dirs)
1255
1256# Persistent-normalization Select for Unsga3Algorithm.Run. Threads rng
1257# so last-front niching matches C# Select(..., rng) on min-count niche
1258# ties. Empty niches take closest; extras are random among near-best
1259# on that ray. v0 `select` stays the `rng == null` path (empty laws).
1260def 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:
1261  match bad:
1262    case False{}:
1263      select_st.dirs(pop, target, dirs, state, rng, List.is_empty(&2, List<&2, F32>, dirs))
1264    case True{}:
1265      select_st.constrained(pop, target, dirs, state, rng)
1266
1267def 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:
1268  match small:
1269    case True{}:
1270      (state, pop, rng)
1271    case False{}:
1272      select_st.large(pop, target, dirs, state, rng, any_infeas(pop))
1273
1274def 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:
1275  +n = Util.list_len(Ind.Individual, combined)
1276  select_st.by(combined, target_size, dirs, state, rng, Nat.is_le(n, target_size))