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	
20	import Base
21	import ./individual.bend as Ind
22	import ./non_dominated_sort.bend as NDS
23	import ./normalization.bend as Norm
24	import ./rng.bend as Rng
25	import ./util.bend as Util
26	
27	type Assignment is Data:
28	  MkAssignment{
29	    reference_index: Nat
30	    perpendicular_distance: F32
31	    niche_count: Nat
32	  }
33	
34	def asg_ref(a: Assignment) -> Nat:
35	  match a:
36	    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
37	      reference_index
38	
39	def asg_dist(a: Assignment) -> F32:
40	  match a:
41	    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
42	      perpendicular_distance
43	
44	def asg_count(a: Assignment) -> Nat:
45	  match a:
46	    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
47	      niche_count
48	
49	def 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	
52	def 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.
58	type NRow is Data:
59	  NRow{
60	    i: Nat
61	    r: Nat
62	    d: F32
63	  }
64	
65	def nrow_i(row: NRow) -> Nat:
66	  match row:
67	    case NRow{i, r, d}:
68	      i
69	
70	def nrow_r(row: NRow) -> Nat:
71	  match row:
72	    case NRow{i, r, d}:
73	      r
74	
75	def nrow_d(row: NRow) -> F32:
76	  match row:
77	    case NRow{i, r, d}:
78	      d
79	
80	def 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	
88	def nrows_of(+asgs: List<&2, Assignment>, +cand: List<&2, Nat>) -> List<&2, NRow>:
89	  nrows_of.go(asgs, cand, Nil{})
90	
91	def first_row_i(rows: List<&2, NRow>) -> Nat:
92	  match rows:
93	    case Nil{}:
94	      0n
95	    case +row <> _:
96	      nrow_i(row)
97	
98	def 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	
101	def 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	
108	def 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	
115	def 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	
122	def 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	
130	def uniq_refs(rows: List<&2, NRow>) -> List<&2, Nat>:
131	  uniq_refs.go(rows, Nil{})
132	
133	def 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	
140	def min_count_rows(+counts: List<&2, Nat>, rows: List<&2, NRow>) -> Nat:
141	  min_count_rows.go(counts, rows, 4294967295n)
142	
143	def 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	
150	def 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	
157	def 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	
166	def 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	
173	def 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	
181	def 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	
188	def 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	
195	def 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	
202	def 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.
211	def 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	
223	def 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	
227	def 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	
234	def 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	
241	def 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.
247	def 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	
261	def nearest_one(f: List<&2, F32>, dirs: List<&2, List<&2, F32>>) -> Assignment:
262	  nearest_go(f, dirs, 0n, 0n, 1000000000.0)
263	
264	def 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.
272	def 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	
297	def 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.
301	def 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	
317	def 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.
322	def 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	
329	def 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	
334	def 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	
337	def 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	
341	def 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	
348	def n_fronts(fronts: List<&2, List<&2, Nat>>) -> Nat:
349	  Util.list_len(List<&2, Nat>, fronts)
350	
351	def 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	
358	def gather.one(+pop: List<&2, Ind.Individual>, +i: Nat) -> Ind.Individual:
359	  get_ind(pop, i)
360	
361	def 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	
364	def cand_ref.one(+asgs: List<&2, Assignment>, +i: Nat) -> Nat:
365	  asg_ref(get_asg(asgs, i))
366	
367	def 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	
370	def 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	
386	def 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	
394	def 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).
402	def 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	
409	def uniq_nats(xs: List<&2, Nat>) -> List<&2, Nat>:
410	  uniq_nats.go(xs, Nil{})
411	
412	type CntNeed is Data:
413	  CN{
414	    counts: List<&2, Nat>
415	    need: Nat
416	  }
417	
418	def 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	
423	def 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	
426	def 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	
433	def 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	
440	def 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	
444	type RefPick is Data:
445	  RP{
446	    asgs: List<&2, Assignment>
447	    r: Nat
448	  }
449	
450	def 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	
455	def 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	
458	def 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	
461	def 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	
479	def 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	
487	def 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).
496	def first_cand(cand: List<&2, Nat>) -> Nat:
497	  match cand:
498	    case Nil{}:
499	      0n
500	    case x <> _:
501	      x
502	
503	def 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	
510	def 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.
515	def 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	
525	def 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	
528	def 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).
540	def near_lim(+best: F32) -> F32:
541	  F32.add(F32.mul(best, 2.0), 0.01)
542	
543	def near_ok(+asgs: List<&2, Assignment>, +i: Nat, +lim: F32) -> Bool:
544	  F32.is_le(asg_dist(get_asg(asgs, i)), lim)
545	
546	type NearPick is Data:
547	  NP{
548	    asgs: List<&2, Assignment>
549	    lim: F32
550	  }
551	
552	def near_members.ok(+ctx: NearPick, +i: Nat) -> Bool:
553	  match ctx:
554	    case NP{asgs, lim}:
555	      near_ok(asgs, i, lim)
556	
557	def 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	
560	def 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	
570	def 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	
574	def 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	
581	def 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	
588	def 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	
597	def 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	
613	def 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.
617	def 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	
621	def 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	
628	def 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	
635	def 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	
638	def 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	
648	def 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	
652	def 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	
659	def 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	
679	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>:
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	
707	def 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.
724	type MRow is Data:
725	  MRow{
726	    pos: Nat
727	    row: NRow
728	  }
729	
730	type Bag is Data:
731	  Bag{
732	    ref: Nat
733	    count: Nat
734	    members: List<&2, MRow>
735	  }
736	
737	def 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	
744	def 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	
765	def 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	
768	def 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	
775	def bags_of(+counts: List<&2, Nat>, +rows: List<&2, NRow>) -> List<&2, Bag>:
776	  bags_of.go(counts, rows, Nil{}, 0n)
777	
778	def 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	
785	def 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	
792	def min_bag_count(bags: List<&2, Bag>) -> Nat:
793	  min_bag_count.go(bags, 4294967295n)
794	
795	def 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	
802	def refs_of_count(+bags: List<&2, Bag>) -> List<&2, Nat>:
803	  refs_of_count.go(bags, min_bag_count(bags), Nil{})
804	
805	def 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	
808	def 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	
817	def bag_count_of(+bags: List<&2, Bag>, +r: Nat) -> Nat:
818	  bag_count_go(bags, r, head_is_ref(bags, r))
819	
820	def 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	
827	def 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	
836	def bag_members_of(+bags: List<&2, Bag>, +r: Nat) -> List<&2, NRow>:
837	  bag_members_go(bags, r, head_is_ref(bags, r))
838	
839	def 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	
846	def 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	
853	def 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	
860	def 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	
869	def 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	
872	def head_pos.ms(ms: List<&2, MRow>) -> Nat:
873	  match ms:
874	    case Nil{}:
875	      4294967295n
876	    case MRow{+pos, row} <> _:
877	      pos
878	
879	def head_pos(b: Bag) -> Nat:
880	  match b:
881	    case Bag{ref, count, +members}:
882	      head_pos.ms(members)
883	
884	def 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	
891	def 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	
900	def sort_put(+acc: List<&2, Bag>, +b: Bag) -> List<&2, Bag>:
901	  insert_bag(acc, b, insert_before(acc, b))
902	
903	def 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	
910	def sort_bags(+bags: List<&2, Bag>) -> List<&2, Bag>:
911	  sort_go(bags, Nil{})
912	
913	def 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	
936	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:
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	
965	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:
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	
977	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>:
978	  (st, F) = pair
979	  fill.wrap(fronts, target, associate(pop, F, dirs), Util.list_len(List<&2, F32>, dirs))
980	
981	def 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	
985	def 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	
992	def 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	
1005	type CvRow is Data:
1006	  CvRow{
1007	    i: Nat
1008	    ind: Ind.Individual
1009	  }
1010	
1011	def any_infeas.on(later: Bool, feas: Bool) -> Bool:
1012	  match feas:
1013	    case False{}:
1014	      True{}
1015	    case True{}:
1016	      later
1017	
1018	def 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	
1025	def 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.
1041	def 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	
1056	def 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	
1059	def 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	
1066	def row_ind(row: CvRow) -> Ind.Individual:
1067	  match row:
1068	    case CvRow{i, ind}:
1069	      ind
1070	
1071	def 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	
1078	def 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	
1085	def 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	
1088	def 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	
1096	def 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).
1102	def 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	
1105	def clip_idxs(+xs: List<&2, Nat>, +want: Nat) -> List<&2, Nat>:
1106	  List.take(&2, Nat, xs, want)
1107	
1108	def 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	
1111	def 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	
1116	def 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.
1121	def 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	
1128	def 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	
1131	type Split is Data:
1132	  Split{
1133	    feas: List<&2, Ind.Individual>
1134	    rows: List<&2, CvRow>
1135	  }
1136	
1137	def split_add.feas(+h: Ind.Individual, sp: Split) -> Split:
1138	  match sp:
1139	    case Split{feas, rows}:
1140	      Split{h <> feas, rows}
1141	
1142	def 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	
1147	def 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	
1154	def 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	
1161	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>:
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	
1168	def 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	
1173	def 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).
1179	def 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	
1183	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:
1184	  (idxs, rng2) = pair
1185	  (st, gather(pop, idxs), rng2)
1186	
1187	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:
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	
1193	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:
1194	  +fronts = NDS.sort(pop)
1195	  select_st.with(pop, target, dirs, fronts, Norm.normalize_nd(state, pop, front0(fronts)), rng)
1196	
1197	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:
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	
1201	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:
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	
1208	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:
1209	  (st, fs) = pair
1210	  (st, feas, rng)
1211	
1212	def 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	
1215	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:
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	
1222	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:
1223	  feas_keep.st.on(feas, target, dirs, state, rng, Nat.is_le(Util.list_len(Ind.Individual, feas), target))
1224	
1225	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:
1226	  (st, kept, rng2) = trip
1227	  (st, append_fill(kept, rows, target), rng2)
1228	
1229	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:
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	
1236	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:
1237	  match sp:
1238	    case Split{feas, rows}:
1239	      select_st.constrained.feas(feas, rows, target, dirs, state, rng)
1240	
1241	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:
1242	  select_st.constrained.from(split.go(pop, 0n), target, dirs, state, rng)
1243	
1244	def 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).
1253	def 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).
1260	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:
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	
1267	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:
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	
1274	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:
1275	  +n = Util.list_len(Ind.Individual, combined)
1276	  select_st.by(combined, target_size, dirs, state, rng, Nat.is_le(n, target_size))