1	# NonDominatedSort — C# Unsga3.Core.NonDominatedSort.
2	# Fast non-dominated sorting by peeling (Deb et al.). v0: Pareto on
3	# objectives only (no constraint-domination until constraints exist).
4	#
5	# Layout (Bend guide: Arrays cannot ride a fork tree; List.get is a
6	# cons walk): one sequential pass materializes `Row{index, objectives}`
7	# so the peel never `List.get`s a fat Individual. Per-candidate split
8	# still mid-splits `a b = f(lo) f(hi)` (same front/leftover order as
9	# the tail-first walk). Inner is_dominated stays a sequential OR so a
10	# first hit skips the rest. Same dominance definition; same ranks and
11	# index order for the same population.
12	
13	import Base
14	import ./individual.bend as Ind
15	import ./util.bend as Util
16	
17	# One sort-row: population index plus the objective vector. Built once
18	# per `sort`; leftover peels reuse the same rows (no re-index).
19	type Row is Data:
20	  Row{
21	    i: Nat
22	    f: List<&2, F32>
23	  }
24	
25	def row_idx(r: Row) -> Nat:
26	  match r:
27	    case Row{i, f}:
28	      i
29	
30	def row_f(r: Row) -> List<&2, F32>:
31	  match r:
32	    case Row{i, f}:
33	      f
34	
35	def rows_of.go(pop: List<&2, Ind.Individual>, +i: Nat) -> List<&2, Row>:
36	  match pop:
37	    case Nil{}:
38	      Nil{}
39	    case +h <> t:
40	      Row{i, Ind.objectives(h)} <> rows_of.go(t, 1n+i)
41	
42	def rows_of(+pop: List<&2, Ind.Individual>) -> List<&2, Row>:
43	  rows_of.go(pop, 0n)
44	
45	def row_idxs(rs: List<&2, Row>) -> List<&2, Nat>:
46	  match rs:
47	    case Nil{}:
48	      Nil{}
49	    case +r <> t:
50	      row_idx(r) <> row_idxs(t)
51	
52	def verdict.a(bb: Bool) -> Nat:
53	  match bb:
54	    case True{}:
55	      0n
56	    case False{}:
57	      1n
58	
59	def verdict.b(bb: Bool) -> Nat:
60	  match bb:
61	    case True{}:
62	      2n
63	    case False{}:
64	      0n
65	
66	# Minimization: 0n = mutual non-domination, 1n = a dominates b, 2n = b dominates a.
67	def verdict(ab: Bool, bb: Bool) -> Nat:
68	  match ab:
69	    case True{}:
70	      verdict.a(bb)
71	    case False{}:
72	      verdict.b(bb)
73	
74	def compare_pareto.go(a: List<&2, F32>, b: List<&2, F32>, ab: Bool, bb: Bool) -> Nat:
75	  # Unequal lengths: mutual non-domination (0), even if the shared prefix
76	  # is strictly better. C# ComparePareto throws. ZDT/DTLZ use one length.
77	  # Locked by src/nds_unequal.bend.
78	  match a b:
79	    case Nil{} Nil{}:
80	      verdict(ab, bb)
81	    case +x <> xs +y <> ys:
82	      compare_pareto.go(xs, ys, Bool.or(ab, F32.is_lt(x, y)), Bool.or(bb, F32.is_lt(y, x)))
83	    case Nil{} y <> ys:
84	      0n
85	    case x <> xs Nil{}:
86	      0n
87	
88	def compare_pareto(a: List<&2, F32>, b: List<&2, F32>) -> Nat:
89	  compare_pareto.go(a, b, False{}, False{})
90	
91	def dominates.is1(p: Nat) -> Bool:
92	  match p:
93	    case 0n:
94	      True{}
95	    case 1n+q:
96	      False{}
97	
98	def dominates.fin(c: Nat) -> Bool:
99	  match c:
100	    case 0n:
101	      False{}
102	    case 1n+p:
103	      dominates.is1(p)
104	
105	def dominates(a: Ind.Individual, b: Ind.Individual) -> Bool:
106	  dominates.fin(compare_pareto(Ind.objectives(a), Ind.objectives(b)))
107	
108	def dominates_ff(+fa: List<&2, F32>, +fb: List<&2, F32>) -> Bool:
109	  dominates.fin(compare_pareto(fa, fb))
110	
111	# Sequential OR so a first hit can skip the rest. Candidate-level
112	# parallelism lives in split_walk (coarse mid-split). Walks `all`
113	# rows directly — no List.get into the population.
114	def is_dominated(+all: List<&2, Row>, +i: Nat, +fi: List<&2, F32>) -> Bool:
115	  match all:
116	    case Nil{}:
117	      False{}
118	    case +r <> rs:
119	      match r:
120	        case Row{+j, +fj}:
121	          Bool.or(
122	            Bool.and(Bool.not(Nat.is_eq(i, j)), dominates_ff(fj, fi)),
123	            is_dominated(rs, i, fi)
124	          )
125	
126	def row_dom(+all: List<&2, Row>, +r: Row) -> Bool:
127	  match r:
128	    case Row{+i, +f}:
129	      is_dominated(all, i, f)
130	
131	# Split remaining into (front indices, leftover rows). Same front
132	# membership and leftover order as the old index-list peel.
133	# |front| + |leftover| = |remaining| by construction.
134	type Split is Data:
135	  Split{
136	    ff: List<&2, Nat>
137	    ot: List<&2, Row>
138	  }
139	
140	def split_put(+r: Row, s: Split, dominated: Bool) -> Split:
141	  match s:
142	    case Split{ff, ot}:
143	      match dominated:
144	        case True{}:
145	          Split{ff, r <> ot}
146	        case False{}:
147	          Split{row_idx(r) <> ff, ot}
148	
149	def split_cat(a: Split, b: Split) -> Split:
150	  match a b:
151	    case Split{ff1, ot1} Split{ff2, ot2}:
152	      Split{List.append(&2, Nat, ff1, ff2), List.append(&2, Row, ot1, ot2)}
153	
154	# Per-candidate split is independent given `all`. Mid-split then
155	# concatenate fronts / leftovers so order matches the tail-first walk.
156	def split_walk.go(+all: List<&2, Row>, +fuel: Nat, cand: List<&2, Row>) -> Split:
157	  match fuel cand:
158	    case 0n Nil{}:
159	      Split{Nil{}, Nil{}}
160	    case 0n +r <> rest:
161	      split_put(r, split_walk.go(all, 0n, rest), row_dom(all, r))
162	    case 1n+p Nil{}:
163	      Split{Nil{}, Nil{}}
164	    case 1n+p +r <> Nil{}:
165	      split_put(r, Split{Nil{}, Nil{}}, row_dom(all, r))
166	    case 1n+p h <> t:
167	      +xs = {h <> t : List<&2, Row>}
168	      +mid = Nat.div(Util.list_len(Row, xs), 2n)
169	      lo hi = split_walk.go(all, p, List.take(&2, Row, xs, mid)) split_walk.go(all, p, List.drop(&2, Row, xs, mid))
170	      split_cat(lo, hi)
171	
172	def split_walk(+all: List<&2, Row>, +cand: List<&2, Row>) -> Split:
173	  split_walk.go(all, Util.list_len(Row, cand), cand)
174	
175	# Empty first front (unreachable on a finite Pareto set) keeps the head
176	# so peel stays a partition.
177	def split_ne(+r: Row, +rest: List<&2, Row>, s: Split) -> Split:
178	  match s:
179	    case Split{ff, ot}:
180	      match ff:
181	        case Nil{}:
182	          Split{row_idx(r) <> Nil{}, rest}
183	        case h <> t:
184	          Split{h <> t, ot}
185	
186	def split_front(remaining: List<&2, Row>) -> Split:
187	  match remaining:
188	    case Nil{}:
189	      Split{Nil{}, Nil{}}
190	    case +r <> +rest:
191	      split_ne(r, rest, split_walk(r <> rest, r <> rest))
192	
193	def split_fst(s: Split) -> List<&2, Nat>:
194	  match s:
195	    case Split{ff, ot}:
196	      ff
197	
198	def split_snd(s: Split) -> List<&2, Row>:
199	  match s:
200	    case Split{ff, ot}:
201	      ot
202	
203	def peel(fuel: Nat, remaining: List<&2, Row>) -> List<&2, List<&2, Nat>>:
204	  match fuel remaining:
205	    case 0n Nil{}:
206	      Nil{}
207	    case 1n+f Nil{}:
208	      Nil{}
209	    case 0n +r <> +rest:
210	      row_idxs({r <> rest : List<&2, Row>}) <> Nil{}
211	    case 1n+f +r <> +rest:
212	      +s = split_front({r <> rest : List<&2, Row>})
213	      split_fst(s) <> peel(f, split_snd(s))
214	
215	def sort(population: List<&2, Ind.Individual>) -> List<&2, List<&2, Nat>>:
216	  match population:
217	    case Nil{}:
218	      Nil{}
219	    case +h <> +t:
220	      +rs = rows_of.go({h <> t : List<&2, Ind.Individual>}, 0n)
221	      peel(Util.list_len(Row, rs), rs)
222	
223	def front_index_count(fronts: List<&2, List<&2, Nat>>) -> Nat:
224	  match fronts:
225	    case Nil{}:
226	      0n
227	    case h <> t:
228	      Nat.add(Util.list_len(Nat, h), front_index_count(t))