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). Last-front fill builds `NRow{i, ref, dist}` once
5	# so the sequential niche loop never `List.get`s an Assignment (or a fat
6	# Individual) per remaining candidate. Same pick rules / same RNG order.
7	# Associate normalized individuals to Das–Dennis rays; select `target_size`
8	# from a combined pool (fill complete fronts, niche-preserve the last).
9	# Deterministic when C# rng is null (`select`): lowest ref among min-count
10	# niches, then min perpendicular distance if that niche is empty, else
11	# lowest index. `select_st` (Run) threads rng: random among equal
12	# min-count niches (C# Select(..., rng)). Empty niches take the closest
13	# unused member; extras draw among members within 2×best+0.01 of the
14	# ray — not uniform inNiche[rng.Next], which collapsed oracle ZDT2.
15	
16	import Base
17	import ./individual.bend as Ind
18	import ./non_dominated_sort.bend as NDS
19	import ./normalization.bend as Norm
20	import ./rng.bend as Rng
21	import ./util.bend as Util
22	
23	type Assignment is Data:
24	  MkAssignment{
25	    reference_index: Nat
26	    perpendicular_distance: F32
27	    niche_count: Nat
28	  }
29	
30	def asg_ref(a: Assignment) -> Nat:
31	  match a:
32	    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
33	      reference_index
34	
35	def asg_dist(a: Assignment) -> F32:
36	  match a:
37	    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
38	      perpendicular_distance
39	
40	def asg_count(a: Assignment) -> Nat:
41	  match a:
42	    case MkAssignment{reference_index, perpendicular_distance, niche_count}:
43	      niche_count
44	
45	def get_asg(asgs: List<&2, Assignment>, i: Nat) -> Assignment:
46	  Maybe.default(&2, Assignment, List.get(&2, Assignment, asgs, i), MkAssignment{0n, 0.0, 0n})
47	
48	def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
49	  Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))
50	
51	# Last-front row: population index plus the two fields the fill loop
52	# reads. Built once from `asgs` so each pick walks this thin list
53	# instead of `List.get` into the combined-pool assignment spine.
54	type NRow is Data:
55	  NRow{
56	    i: Nat
57	    r: Nat
58	    d: F32
59	  }
60	
61	def nrow_i(row: NRow) -> Nat:
62	  match row:
63	    case NRow{i, r, d}:
64	      i
65	
66	def nrow_r(row: NRow) -> Nat:
67	  match row:
68	    case NRow{i, r, d}:
69	      r
70	
71	def nrow_d(row: NRow) -> F32:
72	  match row:
73	    case NRow{i, r, d}:
74	      d
75	
76	def nrows_of.go(+asgs: List<&2, Assignment>, cand: List<&2, Nat>, acc: List<&2, NRow>) -> List<&2, NRow>:
77	  match cand:
78	    case Nil{}:
79	      List.reverse(&2, NRow, acc)
80	    case +i <> rest:
81	      +a = get_asg(asgs, i)
82	      nrows_of.go(asgs, rest, NRow{i, asg_ref(a), asg_dist(a)} <> acc)
83	
84	def nrows_of(+asgs: List<&2, Assignment>, +cand: List<&2, Nat>) -> List<&2, NRow>:
85	  nrows_of.go(asgs, cand, Nil{})
86	
87	def first_row_i(rows: List<&2, NRow>) -> Nat:
88	  match rows:
89	    case Nil{}:
90	      0n
91	    case +row <> _:
92	      nrow_i(row)
93	
94	def first_row_r(rows: List<&2, NRow>) -> Nat:
95	  match rows:
96	    case Nil{}:
97	      0n
98	    case +row <> _:
99	      nrow_r(row)
100	
101	def get_nrow(rows: List<&2, NRow>, i: Nat) -> NRow:
102	  Maybe.default(&2, NRow, List.get(&2, NRow, rows, i), NRow{0n, 0n, 0.0})
103	
104	def drop_nrow.put(+row: NRow, rest: List<&2, NRow>, drop: Bool) -> List<&2, NRow>:
105	  match drop:
106	    case True{}:
107	      rest
108	    case False{}:
109	      row <> rest
110	
111	def drop_nrow(rows: List<&2, NRow>, +pick: Nat) -> List<&2, NRow>:
112	  match rows:
113	    case Nil{}:
114	      Nil{}
115	    case +row <> rest:
116	      drop_nrow.put(row, drop_nrow(rest, pick), Nat.is_eq(nrow_i(row), pick))
117	
118	def keep_nat(h: Nat, rest: List<&2, Nat>, keep: Bool) -> List<&2, Nat>:
119	  match keep:
120	    case True{}:
121	      h <> rest
122	    case False{}:
123	      rest
124	
125	def uniq_refs.go(rows: List<&2, NRow>, +acc: List<&2, Nat>) -> List<&2, Nat>:
126	  match rows:
127	    case Nil{}:
128	      List.reverse(&2, Nat, acc)
129	    case +row <> rest:
130	      +r = nrow_r(row)
131	      uniq_refs.go(rest, keep_nat(r, acc, Bool.not(Util.in_nats(r, acc))))
132	
133	def uniq_refs(rows: List<&2, NRow>) -> List<&2, Nat>:
134	  uniq_refs.go(rows, Nil{})
135	
136	def min_count_rows.go(+counts: List<&2, Nat>, rows: List<&2, NRow>, +acc: Nat) -> Nat:
137	  match rows:
138	    case Nil{}:
139	      acc
140	    case +row <> rest:
141	      min_count_rows.go(counts, rest, Util.nat_min(acc, Util.get_nat(counts, nrow_r(row))))
142	
143	def min_count_rows(+counts: List<&2, Nat>, rows: List<&2, NRow>) -> Nat:
144	  min_count_rows.go(counts, rows, 4294967295n)
145	
146	def refs_at_seq(+counts: List<&2, Nat>, +need: Nat, refs: List<&2, Nat>) -> List<&2, Nat>:
147	  match refs:
148	    case Nil{}:
149	      Nil{}
150	    case +r <> rest:
151	      keep_nat(r, refs_at_seq(counts, need, rest), Nat.is_eq(Util.get_nat(counts, r), need))
152	
153	def in_ref_rows(+r: Nat, rows: List<&2, NRow>) -> List<&2, NRow>:
154	  match rows:
155	    case Nil{}:
156	      Nil{}
157	    case +row <> rest:
158	      Util.keep_if(NRow, row, in_ref_rows(r, rest), Nat.is_eq(nrow_r(row), r))
159	
160	def argmin_dist_rows.go(rows: List<&2, NRow>, +best_i: Nat, +best_d: F32) -> Nat:
161	  match rows:
162	    case Nil{}:
163	      best_i
164	    case +row <> rest:
165	      +d = nrow_d(row)
166	      +lt = F32.is_lt(d, best_d)
167	      argmin_dist_rows.go(rest, Bool.pick(Nat, lt, nrow_i(row), best_i), Bool.pick(F32, lt, d, best_d))
168	
169	def argmin_dist_rows(rows: List<&2, NRow>) -> Nat:
170	  match rows:
171	    case Nil{}:
172	      0n
173	    case +row <> rest:
174	      argmin_dist_rows.go(rest, nrow_i(row), nrow_d(row))
175	
176	def min_dist_rows.go(rows: List<&2, NRow>, +acc: F32) -> F32:
177	  match rows:
178	    case Nil{}:
179	      acc
180	    case +row <> rest:
181	      +d = nrow_d(row)
182	      min_dist_rows.go(rest, Bool.pick(F32, F32.is_lt(d, acc), d, acc))
183	
184	def min_dist_rows(rows: List<&2, NRow>) -> F32:
185	  match rows:
186	    case Nil{}:
187	      0.0
188	    case +row <> rest:
189	      min_dist_rows.go(rest, nrow_d(row))
190	
191	def min_idx_rows.go(rows: List<&2, NRow>, +acc: Nat) -> Nat:
192	  match rows:
193	    case Nil{}:
194	      acc
195	    case +row <> rest:
196	      min_idx_rows.go(rest, Util.nat_min(acc, nrow_i(row)))
197	
198	def min_idx_rows(rows: List<&2, NRow>) -> Nat:
199	  match rows:
200	    case Nil{}:
201	      0n
202	    case +row <> rest:
203	      min_idx_rows.go(rest, nrow_i(row))
204	
205	def near_rows(+lim: F32, rows: List<&2, NRow>) -> List<&2, NRow>:
206	  match rows:
207	    case Nil{}:
208	      Nil{}
209	    case +row <> rest:
210	      Util.keep_if(NRow, row, near_rows(lim, rest), F32.is_le(nrow_d(row), lim))
211	
212	def perp.big(+f: List<&2, F32>, +w: List<&2, F32>, +ww: F32) -> F32:
213	  +t = F32.div(Util.vec_dot(f, w), ww)
214	  F32.sqrt(Util.vec_sqnorm(Util.vec_sub(f, Util.vec_scale(t, w))))
215	
216	def perp.zero(+f: List<&2, F32>, tiny: Bool) -> F32:
217	  match tiny:
218	    case True{}:
219	      F32.sqrt(Util.vec_sqnorm(f))
220	    case False{}:
221	      0.0
222	
223	def perp.pick(+f: List<&2, F32>, +w: List<&2, F32>, +ww: F32, tiny: Bool) -> F32:
224	  match tiny:
225	    case True{}:
226	      perp.zero(f, True{})
227	    case False{}:
228	      perp.big(f, w, ww)
229	
230	def perp(+f: List<&2, F32>, +w: List<&2, F32>) -> F32:
231	  +ww = Util.vec_sqnorm(w)
232	  perp.pick(f, w, ww, F32.is_lt(ww, 0.0000000000000001))
233	
234	# First-min on strict `<` (ties keep the lower index). Sequential over
235	# dirs; associate_raw already mid-splits per individual.
236	def nearest_go(+f: List<&2, F32>, dirs: List<&2, List<&2, F32>>, +i: Nat, +best_i: Nat, +best_d: F32) -> Assignment:
237	  match dirs:
238	    case Nil{}:
239	      MkAssignment{best_i, best_d, 0n}
240	    case +w <> ws:
241	      +d = perp(f, w)
242	      nearest_go(
243	        f,
244	        ws,
245	        1n+i,
246	        Bool.pick(Nat, F32.is_lt(d, best_d), i, best_i),
247	        Bool.pick(F32, F32.is_lt(d, best_d), d, best_d)
248	      )
249	
250	def nearest_one(f: List<&2, F32>, dirs: List<&2, List<&2, F32>>) -> Assignment:
251	  nearest_go(f, dirs, 0n, 0n, 1000000000.0)
252	
253	def associate_head(+dirs: List<&2, List<&2, F32>>, +ind: Ind.Individual, F: List<&2, List<&2, F32>>) -> Assignment:
254	  match F:
255	    case Nil{}:
256	      nearest_one(Ind.objectives(ind), dirs)
257	    case f <> fs:
258	      nearest_one(f, dirs)
259	
260	# Nearest-ref per individual is independent given dirs. Mid-split pop and F.
261	def associate_raw.go(
262	  +dirs: List<&2, List<&2, F32>>,
263	  +fuel: Nat,
264	  pop: List<&2, Ind.Individual>,
265	  +F: List<&2, List<&2, F32>>
266	) -> List<&2, Assignment>:
267	  match fuel pop:
268	    case 0n Nil{}:
269	      Nil{}
270	    case 0n ind <> rest:
271	      match F:
272	        case Nil{}:
273	          nearest_one(Ind.objectives(ind), dirs) <> associate_raw.go(dirs, 0n, rest, Nil{})
274	        case f <> fs:
275	          nearest_one(f, dirs) <> associate_raw.go(dirs, 0n, rest, fs)
276	    case 1n+p Nil{}:
277	      Nil{}
278	    case 1n+p ind <> Nil{}:
279	      associate_head(dirs, ind, F) <> Nil{}
280	    case 1n+p h <> t:
281	      +all = {h <> t : List<&2, Ind.Individual>}
282	      +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
283	      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))
284	      List.append(&2, Assignment, lo, hi)
285	
286	def associate_raw(+pop: List<&2, Ind.Individual>, +F: List<&2, List<&2, F32>>, +dirs: List<&2, List<&2, F32>>) -> List<&2, Assignment>:
287	  associate_raw.go(dirs, Util.list_len(Ind.Individual, pop), pop, F)
288	
289	# Histogram increments commute. Mid-split asgs, then add count vectors.
290	def count_raw.go(+n: Nat, +fuel: Nat, asgs: List<&2, Assignment>) -> List<&2, Nat>:
291	  match fuel asgs:
292	    case 0n Nil{}:
293	      Util.zeros_nat(n)
294	    case 0n a <> rest:
295	      Util.inc_at(count_raw.go(n, 0n, rest), asg_ref(a))
296	    case 1n+p Nil{}:
297	      Util.zeros_nat(n)
298	    case 1n+p a <> Nil{}:
299	      Util.inc_at(Util.zeros_nat(n), asg_ref(a))
300	    case 1n+p h <> t:
301	      +all = {h <> t : List<&2, Assignment>}
302	      +mid = Nat.div(Util.list_len(Assignment, all), 2n)
303	      lo hi = count_raw.go(n, p, List.take(&2, Assignment, all, mid)) count_raw.go(n, p, List.drop(&2, Assignment, all, mid))
304	      Util.nats_add(lo, hi)
305	
306	def count_asg(+asgs: List<&2, Assignment>, +acc: List<&2, Nat>) -> List<&2, Nat>:
307	  Util.nats_add(acc, count_raw.go(Util.list_len(Nat, acc), Util.list_len(Assignment, asgs), asgs))
308	
309	# Assignments whose reference_index lands in a length-n histogram.
310	# Out-of-range refs are silent no-ops in inc_at / List.set.
311	def in_bin_count(asgs: List<&2, Assignment>, +n: Nat) -> Nat:
312	  match asgs:
313	    case Nil{}:
314	      0n
315	    case +a <> rest:
316	      Nat.add(Util.bin_hit(asg_ref(a), n), in_bin_count(rest, n))
317	
318	def with_counts.one(+counts: List<&2, Nat>, +a: Assignment) -> Assignment:
319	  match a:
320	    case MkAssignment{+r, d, n}:
321	      MkAssignment{r, d, Util.get_nat(counts, r)}
322	
323	def with_counts(+counts: List<&2, Nat>, +asgs: List<&2, Assignment>) -> List<&2, Assignment>:
324	  Util.map_halves(~Assignment, ~Assignment, ~List<&2, Nat>, ~with_counts.one, counts, asgs)
325	
326	def associate(+pop: List<&2, Ind.Individual>, +F: List<&2, List<&2, F32>>, +dirs: List<&2, List<&2, F32>>) -> List<&2, Assignment>:
327	  +raw = associate_raw(pop, F, dirs)
328	  with_counts(count_asg(raw, Util.zeros_nat(Util.list_len(List<&2, F32>, dirs))), raw)
329	
330	def front0(fronts: List<&2, List<&2, Nat>>) -> List<&2, Nat>:
331	  match fronts:
332	    case Nil{}:
333	      Nil{}
334	    case h <> t:
335	      h
336	
337	def n_fronts(fronts: List<&2, List<&2, Nat>>) -> Nat:
338	  Util.list_len(List<&2, Nat>, fronts)
339	
340	def head_len(fronts: List<&2, List<&2, Nat>>) -> Nat:
341	  match fronts:
342	    case Nil{}:
343	      0n
344	    case h <> t:
345	      Util.list_len(Nat, h)
346	
347	def gather.one(+pop: List<&2, Ind.Individual>, +i: Nat) -> Ind.Individual:
348	  get_ind(pop, i)
349	
350	def gather(+pop: List<&2, Ind.Individual>, +idxs: List<&2, Nat>) -> List<&2, Ind.Individual>:
351	  Util.map_halves(~Nat, ~Ind.Individual, ~List<&2, Ind.Individual>, ~gather.one, pop, idxs)
352	
353	def cand_ref.one(+asgs: List<&2, Assignment>, +i: Nat) -> Nat:
354	  asg_ref(get_asg(asgs, i))
355	
356	def cand_refs(+asgs: List<&2, Assignment>, cand: List<&2, Nat>) -> List<&2, Nat>:
357	  Util.map_halves(~Nat, ~Nat, ~List<&2, Assignment>, ~cand_ref.one, asgs, cand)
358	
359	def min_count.go(+counts: List<&2, Nat>, +fuel: Nat, refs: List<&2, Nat>) -> Nat:
360	  match fuel refs:
361	    case 0n Nil{}:
362	      4294967295n
363	    case 0n +r <> rs:
364	      Util.nat_min(Util.get_nat(counts, r), min_count.go(counts, 0n, rs))
365	    case 1n+p Nil{}:
366	      4294967295n
367	    case 1n+p +r <> Nil{}:
368	      Util.get_nat(counts, r)
369	    case 1n+p h <> t:
370	      +all = {h <> t : List<&2, Nat>}
371	      +mid = Nat.div(Util.list_len(Nat, all), 2n)
372	      lo hi = min_count.go(counts, p, List.take(&2, Nat, all, mid)) min_count.go(counts, p, List.drop(&2, Nat, all, mid))
373	      Util.nat_min(lo, hi)
374	
375	def min_count(+counts: List<&2, Nat>, refs: List<&2, Nat>, acc: Nat) -> Nat:
376	  match refs:
377	    case Nil{}:
378	      acc
379	    case +r <> +rs:
380	      +xs = {r <> rs : List<&2, Nat>}
381	      Util.nat_min(acc, min_count.go(counts, Util.list_len(Nat, xs), xs))
382	
383	def cons_if(h: Nat, rest: List<&2, Nat>, keep: Bool) -> List<&2, Nat>:
384	  match keep:
385	    case True{}:
386	      h <> rest
387	    case False{}:
388	      rest
389	
390	# First-occurrence unique (C# HashSet of refs-with-candidates).
391	def uniq_nats.go(xs: List<&2, Nat>, +acc: List<&2, Nat>) -> List<&2, Nat>:
392	  match xs:
393	    case Nil{}:
394	      List.reverse(&2, Nat, acc)
395	    case +h <> t:
396	      uniq_nats.go(t, cons_if(h, acc, Bool.not(Util.in_nats(h, acc))))
397	
398	def uniq_nats(xs: List<&2, Nat>) -> List<&2, Nat>:
399	  uniq_nats.go(xs, Nil{})
400	
401	type CntNeed is Data:
402	  CN{
403	    counts: List<&2, Nat>
404	    need: Nat
405	  }
406	
407	def refs_at.ok(+ctx: CntNeed, +r: Nat) -> Bool:
408	  match ctx:
409	    case CN{counts, need}:
410	      Nat.is_eq(Util.get_nat(counts, r), need)
411	
412	def refs_at(+counts: List<&2, Nat>, +need: Nat, refs: List<&2, Nat>) -> List<&2, Nat>:
413	  Util.filter_halves(~Nat, ~CntNeed, ~refs_at.ok, CN{counts, need}, refs)
414	
415	def min_idx(xs: List<&2, Nat>, acc: Nat) -> Nat:
416	  match xs:
417	    case Nil{}:
418	      acc
419	    case +x <> rest:
420	      min_idx(rest, Util.nat_min(acc, x))
421	
422	def min_idx_ne(xs: List<&2, Nat>) -> Nat:
423	  match xs:
424	    case Nil{}:
425	      0n
426	    case x <> rest:
427	      min_idx(rest, x)
428	
429	def pick_ref(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>) -> Nat:
430	  +refs = cand_refs(asgs, cand)
431	  min_idx_ne(refs_at(counts, min_count(counts, refs, 4294967295n), refs))
432	
433	type RefPick is Data:
434	  RP{
435	    asgs: List<&2, Assignment>
436	    r: Nat
437	  }
438	
439	def in_ref.ok(+ctx: RefPick, +i: Nat) -> Bool:
440	  match ctx:
441	    case RP{asgs, r}:
442	      Nat.is_eq(asg_ref(get_asg(asgs, i)), r)
443	
444	def in_ref(+asgs: List<&2, Assignment>, +r: Nat, cand: List<&2, Nat>) -> List<&2, Nat>:
445	  Util.filter_halves(~Nat, ~RefPick, ~in_ref.ok, RP{asgs, r}, cand)
446	
447	def argmin_join(+asgs: List<&2, Assignment>, +ia: Nat, +ib: Nat) -> Nat:
448	  Bool.pick(Nat, F32.is_lt(asg_dist(get_asg(asgs, ib)), asg_dist(get_asg(asgs, ia))), ib, ia)
449	
450	def argmin_dist.go(+asgs: List<&2, Assignment>, +fuel: Nat, cand: List<&2, Nat>) -> Nat:
451	  match fuel cand:
452	    case 0n Nil{}:
453	      0n
454	    case 0n +i <> Nil{}:
455	      i
456	    case 0n +i <> +j <> js:
457	      argmin_join(asgs, i, argmin_dist.go(asgs, 0n, j <> js))
458	    case 1n+p Nil{}:
459	      0n
460	    case 1n+p +i <> Nil{}:
461	      i
462	    case 1n+p h <> t:
463	      +all = {h <> t : List<&2, Nat>}
464	      +mid = Nat.div(Util.list_len(Nat, all), 2n)
465	      lo hi = argmin_dist.go(asgs, p, List.take(&2, Nat, all, mid)) argmin_dist.go(asgs, p, List.drop(&2, Nat, all, mid))
466	      argmin_join(asgs, lo, hi)
467	
468	def argmin_dist(+asgs: List<&2, Assignment>, cand: List<&2, Nat>) -> Nat:
469	  match cand:
470	    case Nil{}:
471	      0n
472	    case +i <> +rest:
473	      +xs = {i <> rest : List<&2, Nat>}
474	      argmin_dist.go(asgs, Util.list_len(Nat, xs), xs)
475	
476	def pick_member.by(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool) -> Nat:
477	  match empty_niche:
478	    case True{}:
479	      argmin_dist(asgs, group)
480	    case False{}:
481	      min_idx_ne(group)
482	
483	# First remaining last-front index. Used when inNiche is empty
484	# (C# would throw; never pick a phantom combined-pool index 0).
485	def first_cand(cand: List<&2, Nat>) -> Nat:
486	  match cand:
487	    case Nil{}:
488	      0n
489	    case x <> _:
490	      x
491	
492	def pick_member.by.safe(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool, +fallback: Nat) -> Nat:
493	  match group:
494	    case Nil{}:
495	      fallback
496	    case g0 <> gs:
497	      pick_member.by(asgs, {g0 <> gs : List<&2, Nat>}, empty_niche)
498	
499	def pick_member(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, +r: Nat) -> Nat:
500	  pick_member.by.safe(asgs, in_ref(asgs, r, cand), Nat.is_eq(Util.get_nat(counts, r), 0n), first_cand(cand))
501	
502	# Affine API: advanced State; chosen index is `Rng.last_nat` (no pair match).
503	# C# Select(..., rng): draw only when more than one min-count ref.
504	def pick_ref.rng.go(+mins: List<&2, Nat>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
505	  match n:
506	    case 0n:
507	      Rng.with_k(rng, fallback)
508	    case 1n:
509	      Rng.with_k(rng, min_idx_ne(mins))
510	    case 1n+p:
511	      +rng2 = Rng.next_nat(rng, 1n+p)
512	      Rng.with_k(rng2, Util.get_nat(mins, Rng.last_nat(rng2)))
513	
514	def pick_ref.rng.after(+mins: List<&2, Nat>, +fallback: Nat, rng: Rng.State) -> Rng.State:
515	  pick_ref.rng.go(mins, Util.list_len(Nat, mins), fallback, rng)
516	
517	def pick_ref.rng(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, rng: Rng.State) -> Rng.State:
518	  +refs = uniq_nats(cand_refs(asgs, cand))
519	  pick_ref.rng.after(
520	    refs_at(counts, min_count(counts, refs, 4294967295n), refs),
521	    asg_ref(get_asg(asgs, first_cand(cand))),
522	    rng
523	  )
524	
525	# Uniform inNiche[rng.Next] (C# non-empty + rng) lets far-from-ray last-front
526	# junk into a niche. With this LCG that pile-up dominates ZDT2's concave
527	# front (x0 → 0). Draw extras only among members within 2×best+0.01 of
528	# the ray (first assignment to a niche stays closest).
529	def near_lim(+best: F32) -> F32:
530	  F32.add(F32.mul(best, 2.0), 0.01)
531	
532	def near_ok(+asgs: List<&2, Assignment>, +i: Nat, +lim: F32) -> Bool:
533	  F32.is_le(asg_dist(get_asg(asgs, i)), lim)
534	
535	type NearPick is Data:
536	  NP{
537	    asgs: List<&2, Assignment>
538	    lim: F32
539	  }
540	
541	def near_members.ok(+ctx: NearPick, +i: Nat) -> Bool:
542	  match ctx:
543	    case NP{asgs, lim}:
544	      near_ok(asgs, i, lim)
545	
546	def near_members(+asgs: List<&2, Assignment>, group: List<&2, Nat>, +lim: F32) -> List<&2, Nat>:
547	  Util.filter_halves(~Nat, ~NearPick, ~near_members.ok, NP{asgs, lim}, group)
548	
549	def pick_among.rng(+group: List<&2, Nat>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
550	  match n:
551	    case 0n:
552	      Rng.with_k(rng, fallback)
553	    case 1n:
554	      Rng.with_k(rng, min_idx_ne(group))
555	    case 1n+p:
556	      +rng2 = Rng.next_nat(rng, 1n+p)
557	      Rng.with_k(rng2, Util.get_nat(group, Rng.last_nat(rng2)))
558	
559	def pick_near.rng(+asgs: List<&2, Assignment>, +group: List<&2, Nat>, rng: Rng.State) -> Rng.State:
560	  +near = near_members(asgs, group, near_lim(asg_dist(get_asg(asgs, argmin_dist(asgs, group)))))
561	  pick_among.rng(near, Util.list_len(Nat, near), first_cand(group), rng)
562	
563	def pick_member.rng.empty(+asgs: List<&2, Assignment>, +group: List<&2, Nat>, empty_niche: Bool, rng: Rng.State) -> Rng.State:
564	  match empty_niche:
565	    case True{}:
566	      Rng.with_k(rng, argmin_dist(asgs, group))
567	    case False{}:
568	      pick_near.rng(asgs, group, rng)
569	
570	def pick_member.rng.by(+asgs: List<&2, Assignment>, group: List<&2, Nat>, empty_niche: Bool, +fallback: Nat, rng: Rng.State) -> Rng.State:
571	  match group:
572	    case Nil{}:
573	      Rng.with_k(rng, fallback)
574	    case g0 <> gs:
575	      pick_member.rng.empty(asgs, {g0 <> gs : List<&2, Nat>}, empty_niche, rng)
576	
577	def pick_member.rng(+asgs: List<&2, Assignment>, +counts: List<&2, Nat>, +cand: List<&2, Nat>, +r: Nat, rng: Rng.State) -> Rng.State:
578	  pick_member.rng.by(
579	    asgs,
580	    in_ref(asgs, r, cand),
581	    Nat.is_eq(Util.get_nat(counts, r), 0n),
582	    first_cand(cand),
583	    rng
584	  )
585	
586	def seed_raw.go(+asgs: List<&2, Assignment>, +n: Nat, +fuel: Nat, selected: List<&2, Nat>) -> List<&2, Nat>:
587	  match fuel selected:
588	    case 0n Nil{}:
589	      Util.zeros_nat(n)
590	    case 0n +i <> rest:
591	      Util.inc_at(seed_raw.go(asgs, n, 0n, rest), asg_ref(get_asg(asgs, i)))
592	    case 1n+p Nil{}:
593	      Util.zeros_nat(n)
594	    case 1n+p +i <> Nil{}:
595	      Util.inc_at(Util.zeros_nat(n), asg_ref(get_asg(asgs, i)))
596	    case 1n+p h <> t:
597	      +all = {h <> t : List<&2, Nat>}
598	      +mid = Nat.div(Util.list_len(Nat, all), 2n)
599	      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))
600	      Util.nats_add(lo, hi)
601	
602	def seed_counts(+asgs: List<&2, Assignment>, +selected: List<&2, Nat>, +acc: List<&2, Nat>) -> List<&2, Nat>:
603	  Util.nats_add(acc, seed_raw.go(asgs, Util.list_len(Nat, acc), Util.list_len(Nat, selected), selected))
604	
605	# fuel, k, cand first so the match follows binder order and fuel shrinks.
606	def pick_ref.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>) -> Nat:
607	  +refs = uniq_refs(rows)
608	  min_idx_ne(refs_at_seq(counts, min_count_rows(counts, rows), refs))
609	
610	def pick_member.by.ne.rows(+group: List<&2, NRow>, empty_niche: Bool) -> Nat:
611	  match empty_niche:
612	    case True{}:
613	      argmin_dist_rows(group)
614	    case False{}:
615	      min_idx_rows(group)
616	
617	def pick_member.by.rows(group: List<&2, NRow>, empty_niche: Bool, +fallback: Nat) -> Nat:
618	  match group:
619	    case Nil{}:
620	      fallback
621	    case g0 <> gs:
622	      pick_member.by.ne.rows({g0 <> gs : List<&2, NRow>}, empty_niche)
623	
624	def pick_member.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>, +r: Nat) -> Nat:
625	  pick_member.by.rows(in_ref_rows(r, rows), Nat.is_eq(Util.get_nat(counts, r), 0n), first_row_i(rows))
626	
627	def pick_ref.rng.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>, rng: Rng.State) -> Rng.State:
628	  +refs = uniq_refs(rows)
629	  pick_ref.rng.after(
630	    refs_at_seq(counts, min_count_rows(counts, rows), refs),
631	    first_row_r(rows),
632	    rng
633	  )
634	
635	def pick_among.nrows(+rows: List<&2, NRow>, n: Nat, +fallback: Nat, rng: Rng.State) -> Rng.State:
636	  match n:
637	    case 0n:
638	      Rng.with_k(rng, fallback)
639	    case 1n:
640	      Rng.with_k(rng, first_row_i(rows))
641	    case 1n+p:
642	      +rng2 = Rng.next_nat(rng, 1n+p)
643	      Rng.with_k(rng2, nrow_i(get_nrow(rows, Rng.last_nat(rng2))))
644	
645	def pick_near.rng.rows(+group: List<&2, NRow>, rng: Rng.State) -> Rng.State:
646	  +near = near_rows(near_lim(min_dist_rows(group)), group)
647	  pick_among.nrows(near, Util.list_len(NRow, near), first_row_i(group), rng)
648	
649	def pick_member.rng.empty.rows(+group: List<&2, NRow>, empty_niche: Bool, rng: Rng.State) -> Rng.State:
650	  match empty_niche:
651	    case True{}:
652	      Rng.with_k(rng, argmin_dist_rows(group))
653	    case False{}:
654	      pick_near.rng.rows(group, rng)
655	
656	def pick_member.rng.by.rows(group: List<&2, NRow>, empty_niche: Bool, +fallback: Nat, rng: Rng.State) -> Rng.State:
657	  match group:
658	    case Nil{}:
659	      Rng.with_k(rng, fallback)
660	    case g0 <> gs:
661	      pick_member.rng.empty.rows({g0 <> gs : List<&2, NRow>}, empty_niche, rng)
662	
663	def pick_member.rng.rows(+counts: List<&2, Nat>, +rows: List<&2, NRow>, +r: Nat, rng: Rng.State) -> Rng.State:
664	  pick_member.rng.by.rows(
665	    in_ref_rows(r, rows),
666	    Nat.is_eq(Util.get_nat(counts, r), 0n),
667	    first_row_i(rows),
668	    rng
669	  )
670	
671	def niche_loop(fuel: Nat, k: Nat, rows: List<&2, NRow>, +counts: List<&2, Nat>, selected: List<&2, Nat>) -> List<&2, Nat>:
672	  match fuel k rows:
673	    case 0n kk r:
674	      selected
675	    case f 0n r:
676	      selected
677	    case f kk Nil{}:
678	      selected
679	    case 1n+f 1n+krest +r0 <> +rs:
680	      +rows2 = {r0 <> rs : List<&2, NRow>}
681	      +r = pick_ref.rows(counts, rows2)
682	      +pick = pick_member.rows(counts, rows2, r)
683	      niche_loop(
684	        f,
685	        krest,
686	        drop_nrow(rows2, pick),
687	        Util.inc_at(counts, r),
688	        List.append(&2, Nat, selected, [pick])
689	      )
690	
691	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>:
692	  match fuel fronts fits:
693	    case 0n fs p:
694	      acc
695	    case f Nil{} p:
696	      acc
697	    case 1n+f +fr <> +rest False{}:
698	      +need = Nat.sub(target, Util.list_len(Nat, acc))
699	      +rows = nrows_of(asgs, fr)
700	      niche_loop(
701	        1n+Util.list_len(NRow, rows),
702	        need,
703	        rows,
704	        seed_counts(asgs, acc, Util.zeros_nat(n_dirs)),
705	        acc
706	      )
707	    case 1n+f +fr <> +rest True{}:
708	      +new_acc = List.append(&2, Nat, acc, fr)
709	      fill(
710	        f,
711	        rest,
712	        Nat.is_le(Nat.add(Util.list_len(Nat, new_acc), head_len(rest)), target),
713	        new_acc,
714	        target,
715	        asgs,
716	        n_dirs
717	      )
718	
719	def fill.wrap(+fronts: List<&2, List<&2, Nat>>, +target: Nat, +asgs: List<&2, Assignment>, +n_dirs: Nat) -> List<&2, Nat>:
720	  fill(
721	    1n+n_fronts(fronts),
722	    fronts,
723	    Nat.is_le(head_len(fronts), target),
724	    Nil{},
725	    target,
726	    asgs,
727	    n_dirs
728	  )
729	
730	def niche_loop.rng(fuel: Nat, k: Nat, rows: List<&2, NRow>, +counts: List<&2, Nat>, selected: List<&2, Nat>, rng: Rng.State) -> List<&2, Nat> & Rng.State:
731	  match fuel k rows:
732	    case 0n kk r:
733	      (selected, rng)
734	    case f 0n r:
735	      (selected, rng)
736	    case f kk Nil{}:
737	      (selected, rng)
738	    case 1n+f 1n+krest +r0 <> +rs:
739	      +rows2 = {r0 <> rs : List<&2, NRow>}
740	      +rng1 = pick_ref.rng.rows(counts, rows2, rng)
741	      +r = Rng.last_nat(rng1)
742	      +rng2 = pick_member.rng.rows(counts, rows2, r, rng1)
743	      +pick = Rng.last_nat(rng2)
744	      niche_loop.rng(
745	        f,
746	        krest,
747	        drop_nrow(rows2, pick),
748	        Util.inc_at(counts, r),
749	        List.append(&2, Nat, selected, [pick]),
750	        rng2
751	      )
752	
753	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:
754	  match fuel fronts fits:
755	    case 0n fs p:
756	      (acc, rng)
757	    case f Nil{} p:
758	      (acc, rng)
759	    case 1n+f +fr <> +rest False{}:
760	      +need = Nat.sub(target, Util.list_len(Nat, acc))
761	      +rows = nrows_of(asgs, fr)
762	      niche_loop.rng(
763	        1n+Util.list_len(NRow, rows),
764	        need,
765	        rows,
766	        seed_counts(asgs, acc, Util.zeros_nat(n_dirs)),
767	        acc,
768	        rng
769	      )
770	    case 1n+f +fr <> +rest True{}:
771	      +new_acc = List.append(&2, Nat, acc, fr)
772	      fill.rng(
773	        f,
774	        rest,
775	        Nat.is_le(Nat.add(Util.list_len(Nat, new_acc), head_len(rest)), target),
776	        new_acc,
777	        target,
778	        asgs,
779	        n_dirs,
780	        rng
781	      )
782	
783	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:
784	  fill.rng(
785	    1n+n_fronts(fronts),
786	    fronts,
787	    Nat.is_le(head_len(fronts), target),
788	    Nil{},
789	    target,
790	    asgs,
791	    n_dirs,
792	    rng
793	  )
794	
795	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>:
796	  (st, F) = pair
797	  fill.wrap(fronts, target, associate(pop, F, dirs), Util.list_len(List<&2, F32>, dirs))
798	
799	def select_idx.big(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Nat>:
800	  +fronts = NDS.sort(pop)
801	  select_idx.with(pop, target, dirs, fronts, Norm.normalize_nd(Norm.new_state(0n), pop, front0(fronts)))
802	
803	def select_idx.dirs(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, empty_dirs: Bool) -> List<&2, Nat>:
804	  match empty_dirs:
805	    case True{}:
806	      List.take(&2, Nat, List.range(Util.list_len(Ind.Individual, pop)), target)
807	    case False{}:
808	      select_idx.big(pop, target, dirs)
809	
810	def select_idx.by(+pop: List<&2, Ind.Individual>, +target: Nat, +dirs: List<&2, List<&2, F32>>, small: Bool) -> List<&2, Nat>:
811	  match small:
812	    case True{}:
813	      List.range(Util.list_len(Ind.Individual, pop))
814	    case False{}:
815	      select_idx.dirs(pop, target, dirs, List.is_empty(&2, List<&2, F32>, dirs))
816	
817	def unused_idxs(+used: List<&2, Nat>, +n: Nat) -> List<&2, Nat>:
818	  Util.minus(List.range(n), used)
819	
820	# Length lock: |take(pad(core, want, n), want)| = want when want ≤ n.
821	# Identity when core is already a unique subset of 0..n-1 of length want
822	# (the fill / range / take paths used in A/B).
823	def pad_idxs(+xs: List<&2, Nat>, +want: Nat, +n: Nat) -> List<&2, Nat>:
824	  List.append(&2, Nat, xs, List.take(&2, Nat, unused_idxs(xs, n), Nat.sub(want, Util.list_len(Nat, xs))))
825	
826	def clip_idxs(+xs: List<&2, Nat>, +want: Nat) -> List<&2, Nat>:
827	  List.take(&2, Nat, xs, want)
828	
829	def size_lock(+xs: List<&2, Nat>, +want: Nat, +n: Nat) -> List<&2, Nat>:
830	  clip_idxs(List.append(&2, Nat, pad_idxs(xs, want, n), List.range(want)), want)
831	
832	def select_idx(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Nat>:
833	  +n = Util.list_len(Ind.Individual, combined)
834	  +want = Util.nat_min(target_size, n)
835	  size_lock(select_idx.by(combined, target_size, dirs, Nat.is_le(n, target_size)), want, n)
836	
837	def select(+combined: List<&2, Ind.Individual>, +target_size: Nat, +dirs: List<&2, List<&2, F32>>) -> List<&2, Ind.Individual>:
838	  gather(combined, select_idx(combined, target_size, dirs))
839	
840	# Persistent-normalization Select for Unsga3Algorithm.Run. Threads rng
841	# so last-front niching matches C# Select(..., rng) on min-count niche
842	# ties. Empty niches take closest; extras are random among near-best
843	# on that ray. v0 `select` stays the `rng == null` path (empty laws).
844	def size_lock.rng(+want: Nat, +n: Nat, pair: List<&2, Nat> & Rng.State) -> List<&2, Nat> & Rng.State:
845	  (xs, rng) = pair
846	  (size_lock(xs, want, n), rng)
847	
848	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:
849	  (idxs, rng2) = pair
850	  (st, gather(pop, idxs), rng2)
851	
852	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:
853	  (st, F) = pair
854	  +n = Util.list_len(Ind.Individual, pop)
855	  +want = Util.nat_min(target, n)
856	  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)))
857	
858	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:
859	  +fronts = NDS.sort(pop)
860	  select_st.with(pop, target, dirs, fronts, Norm.normalize_nd(state, pop, front0(fronts)), rng)
861	
862	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:
863	  +n = Util.list_len(Ind.Individual, pop)
864	  (state, gather(pop, size_lock(List.take(&2, Nat, List.range(n), target), Util.nat_min(target, n), n)), rng)
865	
866	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:
867	  match empty_dirs:
868	    case True{}:
869	      select_st.take(pop, target, state, rng)
870	    case False{}:
871	      select_st.big(pop, target, dirs, state, rng)
872	
873	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:
874	  match small:
875	    case True{}:
876	      (state, pop, rng)
877	    case False{}:
878	      select_st.dirs(pop, target, dirs, state, rng, List.is_empty(&2, List<&2, F32>, dirs))
879	
880	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:
881	  +n = Util.list_len(Ind.Individual, combined)
882	  select_st.by(combined, target_size, dirs, state, rng, Nat.is_le(n, target_size))