1	# Mating tournament — C# TournamentSelection / TournamentMode.
2	# Default for algorithm A/B is PymooCompatible (pymoo
3	# comp_by_rank_and_ref_line_dist): same niche → rank then perp dist;
4	# else random. RankNicheDistance (C# WinnerRankNicheDistance) is
5	# rank → niche count → perpendicular distance → coin.
6	# Both modes take CV first. Feasible (cv ≤ 0) beats infeasible.
7	# PymooCompatible: if either is infeasible, smaller CV wins and equal
8	# CV is a coin (no rank / distance). RankNicheDistance: both infeasible
9	# and unequal CV → smaller CV; equal CV falls through to rank.
10	# cv 0 on both sides keeps the feasible comparators. A/B stays
11	# PymooCompatible. See src/trn_seed682.bend.
12	
13	import Base
14	import ./individual.bend as Ind
15	import ./non_dominated_sort.bend as NDS
16	import ./normalization.bend as Norm
17	import ./survival.bend as Surv
18	import ./rng.bend as Rng
19	import ./util.bend as Util
20	
21	type Mode is Data:
22	  PymooCompatible{}
23	  RankNicheDistance{}
24	
25	def pymoo() -> Mode:
26	  PymooCompatible{}
27	
28	def rank_niche() -> Mode:
29	  RankNicheDistance{}
30	
31	def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
32	  Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))
33	
34	def coin(a: Ind.Individual, b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
35	  +rng2 = Rng.next_double(rng)
36	  (rng2, Bool.pick(Ind.Individual, F32.is_lt(Rng.last_double(rng2), 0.5), a, b))
37	
38	def cmp_pick(a: Ind.Individual, b: Ind.Individual, rng: Rng.State, ab: Bool, ba: Bool) -> Rng.State & Ind.Individual:
39	  match ab ba:
40	    case True{} _:
41	      (rng, a)
42	    case False{} True{}:
43	      (rng, b)
44	    case False{} False{}:
45	      coin(a, b, rng)
46	
47	def by_dist(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
48	  +da = Ind.perp_dist(a)
49	  +db = Ind.perp_dist(b)
50	  cmp_pick(a, b, rng, F32.is_lt(da, db), F32.is_lt(db, da))
51	
52	def by_rank.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
53	  match same:
54	    case True{}:
55	      by_dist(a, b, rng)
56	    case False{}:
57	      cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))
58	
59	def by_rank(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
60	  by_rank.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
61	
62	def winner_pymoo.same(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
63	  match same:
64	    case True{}:
65	      by_rank(a, b, rng)
66	    case False{}:
67	      coin(a, b, rng)
68	
69	def winner_pymoo.cv_b(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, b_lt: Bool) -> Rng.State & Ind.Individual:
70	  match b_lt:
71	    case True{}:
72	      (rng, b)
73	    case False{}:
74	      coin(a, b, rng)
75	
76	# Either infeasible: smaller CV, else coin. Does not read rank.
77	def winner_pymoo.cv(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_lt: Bool, b_lt: Bool) -> Rng.State & Ind.Individual:
78	  match a_lt:
79	    case True{}:
80	      (rng, a)
81	    case False{}:
82	      winner_pymoo.cv_b(a, b, rng, b_lt)
83	
84	def winner_pymoo.gate(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, either: Bool) -> Rng.State & Ind.Individual:
85	  match either:
86	    case True{}:
87	      winner_pymoo.cv(a, b, rng, F32.is_lt(Ind.constraint_violation(a), Ind.constraint_violation(b)), F32.is_lt(Ind.constraint_violation(b), Ind.constraint_violation(a)))
88	    case False{}:
89	      winner_pymoo.same(a, b, rng, Nat.is_eq(Ind.associated_ref(a), Ind.associated_ref(b)))
90	
91	def winner_pymoo(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
92	  winner_pymoo.gate(
93	    a,
94	    b,
95	    rng,
96	    Bool.or(Bool.not(Ind.feasible(a)), Bool.not(Ind.feasible(b)))
97	  )
98	
99	# Equal niche counts fall through to perpendicular distance (then coin).
100	# A count tie used to coin immediately and skip distance.
101	def by_niche.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
102	  match same:
103	    case True{}:
104	      by_dist(a, b, rng)
105	    case False{}:
106	      cmp_pick(a, b, rng, Nat.is_lt(Ind.niche(a), Ind.niche(b)), Nat.is_lt(Ind.niche(b), Ind.niche(a)))
107	
108	def by_niche(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
109	  by_niche.eq(a, b, rng, Nat.is_eq(Ind.niche(a), Ind.niche(b)))
110	
111	def winner_rnd.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
112	  match same:
113	    case True{}:
114	      by_niche(a, b, rng)
115	    case False{}:
116	      cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))
117	
118	def winner_rnd.cv_b(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, b_lt: Bool) -> Rng.State & Ind.Individual:
119	  match b_lt:
120	    case True{}:
121	      (rng, b)
122	    case False{}:
123	      winner_rnd.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
124	
125	# Both infeasible. Equal CV falls through to rank (not a coin, not Pareto).
126	def winner_rnd.cv(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_lt: Bool, b_lt: Bool) -> Rng.State & Ind.Individual:
127	  match a_lt:
128	    case True{}:
129	      (rng, a)
130	    case False{}:
131	      winner_rnd.cv_b(a, b, rng, b_lt)
132	
133	def winner_rnd.gate(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, a_feas: Bool, b_feas: Bool) -> Rng.State & Ind.Individual:
134	  match a_feas b_feas:
135	    case True{} False{}:
136	      (rng, a)
137	    case False{} True{}:
138	      (rng, b)
139	    case True{} True{}:
140	      winner_rnd.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
141	    case False{} False{}:
142	      winner_rnd.cv(a, b, rng, F32.is_lt(Ind.constraint_violation(a), Ind.constraint_violation(b)), F32.is_lt(Ind.constraint_violation(b), Ind.constraint_violation(a)))
143	
144	def winner_rnd(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
145	  winner_rnd.gate(a, b, rng, Ind.feasible(a), Ind.feasible(b))
146	
147	def winner(mode: Mode, +a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
148	  match mode:
149	    case PymooCompatible{}:
150	      winner_pymoo(a, b, rng)
151	    case RankNicheDistance{}:
152	      winner_rnd(a, b, rng)
153	
154	def one(+mode: Mode, +pop: List<&2, Ind.Individual>, rng: Rng.State) -> Rng.State & Ind.Individual:
155	  +n = Util.list_len(Ind.Individual, pop)
156	  +rng_a = Rng.next_nat(rng, n)
157	  +ia = Rng.last_nat(rng_a)
158	  +rng_b = Rng.next_except(rng_a, n, ia)
159	  +ib = Rng.last_nat(rng_b)
160	  winner(mode, get_ind(pop, ia), get_ind(pop, ib), rng_b)
161	
162	type PHold is Data:
163	  PH{
164	    rng: Rng.State
165	    acc: List<&2, Ind.Individual>
166	  }
167	
168	def parents_next.w(acc: List<&2, Ind.Individual>, pair: Rng.State & Ind.Individual) -> PHold:
169	  (rng, w) = pair
170	  PH{rng, w <> acc}
171	
172	def parents_next(+mode: Mode, +pop: List<&2, Ind.Individual>, hold: PHold) -> PHold:
173	  match hold:
174	    case PH{rng, acc}:
175	      parents_next.w(acc, one(mode, pop, rng))
176	
177	def parents_loop(fuel: Nat, hold: PHold, +mode: Mode, +pop: List<&2, Ind.Individual>) -> Rng.State & List<&2, Ind.Individual>:
178	  match fuel hold:
179	    case 0n PH{rng, acc}:
180	      (rng, List.reverse(&2, Ind.Individual, acc))
181	    case 1n+f h:
182	      parents_loop(f, parents_next(mode, pop, h), mode, pop)
183	
184	def select_parents(+mode: Mode, +pop: List<&2, Ind.Individual>, count: Nat, rng: Rng.State) -> Rng.State & List<&2, Ind.Individual>:
185	  parents_loop(count, PH{rng, Nil{}}, mode, pop)
186	
187	def parents_of(pair: Rng.State & List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
188	  (rng, xs) = pair
189	  xs
190	
191	def stamp_front(idxs: List<&2, Nat>, +pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>:
192	  match idxs:
193	    case Nil{}:
194	      pop
195	    case +i <> rest:
196	      stamp_front(rest, List.set(&2, Ind.Individual, pop, i, Ind.set_rank(get_ind(pop, i), r)), r)
197	
198	def stamp_ranks(fronts: List<&2, List<&2, Nat>>, pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>:
199	  match fronts:
200	    case Nil{}:
201	      pop
202	    case fr <> rest:
203	      stamp_ranks(rest, stamp_front(fr, pop, r), 1n+r)
204	
205	def stamp_asgs.one(+a: Surv.Assignment, +ind: Ind.Individual) -> Ind.Individual:
206	  Ind.stamp(ind, Ind.rank(ind), Surv.asg_count(a), Surv.asg_ref(a), Surv.asg_dist(a))
207	
208	# Zip pop with assignments. Mid-split both lists at the same mid.
209	def stamp_asgs.go(+fuel: Nat, pop: List<&2, Ind.Individual>, +asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>:
210	  match fuel pop:
211	    case 0n Nil{}:
212	      Nil{}
213	    case 0n +ind <> rest:
214	      match asgs:
215	        case Nil{}:
216	          {ind <> rest : List<&2, Ind.Individual>}
217	        case +a <> as:
218	          stamp_asgs.one(a, ind) <> stamp_asgs.go(0n, rest, as)
219	    case 1n+p Nil{}:
220	      Nil{}
221	    case 1n+p +ind <> Nil{}:
222	      match asgs:
223	        case Nil{}:
224	          ind <> Nil{}
225	        case +a <> as:
226	          stamp_asgs.one(a, ind) <> Nil{}
227	    case 1n+p h <> t:
228	      +all = {h <> t : List<&2, Ind.Individual>}
229	      +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
230	      lo hi = stamp_asgs.go(p, List.take(&2, Ind.Individual, all, mid), List.take(&2, Surv.Assignment, asgs, mid)) stamp_asgs.go(p, List.drop(&2, Ind.Individual, all, mid), List.drop(&2, Surv.Assignment, asgs, mid))
231	      List.append(&2, Ind.Individual, lo, hi)
232	
233	def stamp_asgs(+pop: List<&2, Ind.Individual>, asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>:
234	  stamp_asgs.go(Util.list_len(Ind.Individual, pop), pop, asgs)
235	
236	def prepare.with(+dirs: List<&2, List<&2, F32>>, +pop: List<&2, Ind.Individual>, +fronts: List<&2, List<&2, Nat>>, pair: Norm.State & List<&2, List<&2, F32>>) -> Norm.State & List<&2, Ind.Individual>:
237	  (st, F) = pair
238	  +ranked = stamp_ranks(fronts, pop, 0n)
239	  (st, stamp_asgs(ranked, Surv.associate(ranked, F, dirs)))
240	
241	# Recompute ranks + niche association (C# PrepareForSelection). Threads
242	# the persistent Normalization state.
243	def prepare(+pop: List<&2, Ind.Individual>, +dirs: List<&2, List<&2, F32>>, state: Norm.State) -> Norm.State & List<&2, Ind.Individual>:
244	  +fronts = NDS.sort(pop)
245	  prepare.with(dirs, pop, fronts, Norm.normalize_nd(state, pop, Surv.front0(fronts)))