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. This slice is
6	# unconstrained, so CV branches are unused (all individuals are treated
7	# feasible). A/B does not score this path; see src/trn_seed682.bend.
8	
9	import Base
10	import ./individual.bend as Ind
11	import ./non_dominated_sort.bend as NDS
12	import ./normalization.bend as Norm
13	import ./survival.bend as Surv
14	import ./rng.bend as Rng
15	import ./util.bend as Util
16	
17	type Mode is Data:
18	  PymooCompatible{}
19	  RankNicheDistance{}
20	
21	def pymoo() -> Mode:
22	  PymooCompatible{}
23	
24	def rank_niche() -> Mode:
25	  RankNicheDistance{}
26	
27	def get_ind(+pop: List<&2, Ind.Individual>, i: Nat) -> Ind.Individual:
28	  Maybe.default(&2, Ind.Individual, List.get(&2, Ind.Individual, pop, i), Ind.from_objectives(Nil{}))
29	
30	def coin(a: Ind.Individual, b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
31	  +rng2 = Rng.next_double(rng)
32	  (rng2, Bool.pick(Ind.Individual, F32.is_lt(Rng.last_double(rng2), 0.5), a, b))
33	
34	def cmp_pick(a: Ind.Individual, b: Ind.Individual, rng: Rng.State, ab: Bool, ba: Bool) -> Rng.State & Ind.Individual:
35	  match ab ba:
36	    case True{} _:
37	      (rng, a)
38	    case False{} True{}:
39	      (rng, b)
40	    case False{} False{}:
41	      coin(a, b, rng)
42	
43	def by_dist(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
44	  +da = Ind.perp_dist(a)
45	  +db = Ind.perp_dist(b)
46	  cmp_pick(a, b, rng, F32.is_lt(da, db), F32.is_lt(db, da))
47	
48	def by_rank.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
49	  match same:
50	    case True{}:
51	      by_dist(a, b, rng)
52	    case False{}:
53	      cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))
54	
55	def by_rank(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
56	  by_rank.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
57	
58	def winner_pymoo.same(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
59	  match same:
60	    case True{}:
61	      by_rank(a, b, rng)
62	    case False{}:
63	      coin(a, b, rng)
64	
65	def winner_pymoo(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
66	  winner_pymoo.same(a, b, rng, Nat.is_eq(Ind.associated_ref(a), Ind.associated_ref(b)))
67	
68	# Equal niche counts fall through to perpendicular distance (then coin).
69	# A count tie used to coin immediately and skip distance.
70	def by_niche.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
71	  match same:
72	    case True{}:
73	      by_dist(a, b, rng)
74	    case False{}:
75	      cmp_pick(a, b, rng, Nat.is_lt(Ind.niche(a), Ind.niche(b)), Nat.is_lt(Ind.niche(b), Ind.niche(a)))
76	
77	def by_niche(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
78	  by_niche.eq(a, b, rng, Nat.is_eq(Ind.niche(a), Ind.niche(b)))
79	
80	def winner_rnd.eq(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State, same: Bool) -> Rng.State & Ind.Individual:
81	  match same:
82	    case True{}:
83	      by_niche(a, b, rng)
84	    case False{}:
85	      cmp_pick(a, b, rng, Nat.is_lt(Ind.rank(a), Ind.rank(b)), Nat.is_lt(Ind.rank(b), Ind.rank(a)))
86	
87	def winner_rnd(+a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
88	  winner_rnd.eq(a, b, rng, Nat.is_eq(Ind.rank(a), Ind.rank(b)))
89	
90	def winner(mode: Mode, +a: Ind.Individual, +b: Ind.Individual, rng: Rng.State) -> Rng.State & Ind.Individual:
91	  match mode:
92	    case PymooCompatible{}:
93	      winner_pymoo(a, b, rng)
94	    case RankNicheDistance{}:
95	      winner_rnd(a, b, rng)
96	
97	def one(+mode: Mode, +pop: List<&2, Ind.Individual>, rng: Rng.State) -> Rng.State & Ind.Individual:
98	  +n = Util.list_len(Ind.Individual, pop)
99	  +rng_a = Rng.next_nat(rng, n)
100	  +ia = Rng.last_nat(rng_a)
101	  +rng_b = Rng.next_except(rng_a, n, ia)
102	  +ib = Rng.last_nat(rng_b)
103	  winner(mode, get_ind(pop, ia), get_ind(pop, ib), rng_b)
104	
105	type PHold is Data:
106	  PH{
107	    rng: Rng.State
108	    acc: List<&2, Ind.Individual>
109	  }
110	
111	def parents_next.w(acc: List<&2, Ind.Individual>, pair: Rng.State & Ind.Individual) -> PHold:
112	  (rng, w) = pair
113	  PH{rng, w <> acc}
114	
115	def parents_next(+mode: Mode, +pop: List<&2, Ind.Individual>, hold: PHold) -> PHold:
116	  match hold:
117	    case PH{rng, acc}:
118	      parents_next.w(acc, one(mode, pop, rng))
119	
120	def parents_loop(fuel: Nat, hold: PHold, +mode: Mode, +pop: List<&2, Ind.Individual>) -> Rng.State & List<&2, Ind.Individual>:
121	  match fuel hold:
122	    case 0n PH{rng, acc}:
123	      (rng, List.reverse(&2, Ind.Individual, acc))
124	    case 1n+f h:
125	      parents_loop(f, parents_next(mode, pop, h), mode, pop)
126	
127	def select_parents(+mode: Mode, +pop: List<&2, Ind.Individual>, count: Nat, rng: Rng.State) -> Rng.State & List<&2, Ind.Individual>:
128	  parents_loop(count, PH{rng, Nil{}}, mode, pop)
129	
130	def parents_of(pair: Rng.State & List<&2, Ind.Individual>) -> List<&2, Ind.Individual>:
131	  (rng, xs) = pair
132	  xs
133	
134	def stamp_front(idxs: List<&2, Nat>, +pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>:
135	  match idxs:
136	    case Nil{}:
137	      pop
138	    case +i <> rest:
139	      stamp_front(rest, List.set(&2, Ind.Individual, pop, i, Ind.set_rank(get_ind(pop, i), r)), r)
140	
141	def stamp_ranks(fronts: List<&2, List<&2, Nat>>, pop: List<&2, Ind.Individual>, +r: Nat) -> List<&2, Ind.Individual>:
142	  match fronts:
143	    case Nil{}:
144	      pop
145	    case fr <> rest:
146	      stamp_ranks(rest, stamp_front(fr, pop, r), 1n+r)
147	
148	def stamp_asgs.one(+a: Surv.Assignment, +ind: Ind.Individual) -> Ind.Individual:
149	  Ind.stamp(ind, Ind.rank(ind), Surv.asg_count(a), Surv.asg_ref(a), Surv.asg_dist(a))
150	
151	# Zip pop with assignments. Mid-split both lists at the same mid.
152	def stamp_asgs.go(+fuel: Nat, pop: List<&2, Ind.Individual>, +asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>:
153	  match fuel pop:
154	    case 0n Nil{}:
155	      Nil{}
156	    case 0n +ind <> rest:
157	      match asgs:
158	        case Nil{}:
159	          {ind <> rest : List<&2, Ind.Individual>}
160	        case +a <> as:
161	          stamp_asgs.one(a, ind) <> stamp_asgs.go(0n, rest, as)
162	    case 1n+p Nil{}:
163	      Nil{}
164	    case 1n+p +ind <> Nil{}:
165	      match asgs:
166	        case Nil{}:
167	          ind <> Nil{}
168	        case +a <> as:
169	          stamp_asgs.one(a, ind) <> Nil{}
170	    case 1n+p h <> t:
171	      +all = {h <> t : List<&2, Ind.Individual>}
172	      +mid = Nat.div(Util.list_len(Ind.Individual, all), 2n)
173	      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))
174	      List.append(&2, Ind.Individual, lo, hi)
175	
176	def stamp_asgs(+pop: List<&2, Ind.Individual>, asgs: List<&2, Surv.Assignment>) -> List<&2, Ind.Individual>:
177	  stamp_asgs.go(Util.list_len(Ind.Individual, pop), pop, asgs)
178	
179	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>:
180	  (st, F) = pair
181	  +ranked = stamp_ranks(fronts, pop, 0n)
182	  (st, stamp_asgs(ranked, Surv.associate(ranked, F, dirs)))
183	
184	# Recompute ranks + niche association (C# PrepareForSelection). Threads
185	# the persistent Normalization state.
186	def prepare(+pop: List<&2, Ind.Individual>, +dirs: List<&2, List<&2, F32>>, state: Norm.State) -> Norm.State & List<&2, Ind.Individual>:
187	  +fronts = NDS.sort(pop)
188	  prepare.with(dirs, pop, fronts, Norm.normalize_nd(state, pop, Surv.front0(fronts)))