1	import Base
2	
3	# Edlib sentinels are distinct constructors, never wrapped U32 values.
4	type Mode is Data:
5	  NW{}
6	  SHW{}
7	  HW{}
8	
9	type Task is Data:
10	  Distance{}
11	  Locations{}
12	  Path{}
13	
14	type Threshold is Data:
15	  Unlimited{}
16	  MaxDistance{value: Nat}
17	
18	type EqualityPair is Data:
19	  EqualityPair{first: Char, second: Char}
20	
21	type CigarFormat is Data:
22	  Standard{}
23	  Extended{}
24	
25	type AlignConfig is Data:
26	  AlignConfig{mode: Mode, task: Task, threshold: Threshold,
27	    equalities: List<&2, EqualityPair>, cigar_format: CigarFormat}
28	
29	type Status is Data:
30	  Ok{}
31	  Error{}
32	
33	type EditDistance is Data:
34	  Found{value: Nat}
35	  NotFound{}
36	
37	type Coordinate is Data:
38	  BeforeStart{}
39	  Position{index: Nat}
40	
41	type Operation is Data:
42	  Match{}
43	  Insert{}
44	  Delete{}
45	  Mismatch{}
46	
47	type AlignResult is Data:
48	  AlignResult{status: Status, distance: EditDistance,
49	    end_locations: List<&2, Coordinate>,
50	    start_locations: Maybe<&2, List<&2, Coordinate>>,
51	    alignment: Maybe<&2, List<&2, Operation>>, cigar: Maybe<&2, String>}
52	
53	def default_config() -> AlignConfig:
54	  AlignConfig{NW{}, Distance{}, Unlimited{}, Nil{}, Extended{}}
55	
56	def end_coordinate(length: Nat) -> Coordinate:
57	  match length:
58	    case 0n:
59	      BeforeStart{}
60	    case 1n+p:
61	      Position{p}
62	
63	def distance_show(distance: EditDistance) -> String:
64	  match distance:
65	    case Found{value}:
66	      Nat.show(value)
67	    case NotFound{}:
68	      "-1"
69	
70	def coordinate_show(position: Coordinate) -> String:
71	  match position:
72	    case BeforeStart{}:
73	      "-1"
74	    case Position{index}:
75	      Nat.show(index)
76	
77	def status_show(status: Status) -> String:
78	  match status:
79	    case Ok{}:
80	      "0"
81	    case Error{}:
82	      "1"
83	
84	def operation_show(operation: Operation) -> String:
85	  match operation:
86	    case Match{}:
87	      "0"
88	    case Insert{}:
89	      "1"
90	    case Delete{}:
91	      "2"
92	    case Mismatch{}:
93	      "3"
94	
95	def operation_char(format: CigarFormat, operation: Operation) -> Char:
96	  match format operation:
97	    case _ Insert{}:
98	      'I'
99	    case _ Delete{}:
100	      'D'
101	    case Standard{} _:
102	      'M'
103	    case Extended{} Match{}:
104	      '='
105	    case Extended{} Mismatch{}:
106	      'X'
107	
108	def cigar_step(rest: Unit -> String, symbol: Char, count: Nat, same: Bool) -> String:
109	  match same:
110	    case True{}:
111	      rest(Unit{})
112	    case False{}:
113	      Nat.show(count) ++ SCon{symbol, rest(Unit{})}
114	
115	def cigar_runs(operations: List<&2, Operation>, +format: CigarFormat,
116	               +symbol: Char, +count: Nat) -> String:
117	  match operations:
118	    case Nil{}:
119	      Nat.show(count) ++ SCon{symbol, ""}
120	    case h <> t:
121	      +next = operation_char(format, h)
122	      cigar_step(_ => cigar_runs(t, format, next,
123	        Bool.pick(Nat, Char.is_eq(symbol, next), 1n+count, 1n)),
124	        symbol, count, Char.is_eq(symbol, next))
125	
126	def alignment_to_cigar(operations: List<&2, Operation>, +format: CigarFormat) -> String:
127	  match operations:
128	    case Nil{}:
129	      ""
130	    case h <> t:
131	      cigar_runs(t, format, operation_char(format, h), 1n)
132	
133	def coordinates_show(locations: List<&2, Coordinate>) -> String:
134	  List.show(~&2, ~Coordinate, ~coordinate_show, locations)
135	
136	def starts_show(locations: Maybe<&2, List<&2, Coordinate>>) -> String:
137	  match locations:
138	    case None{}:
139	      "null"
140	    case Some{values}:
141	      coordinates_show(values)
142	
143	def alignment_show(alignment: Maybe<&2, List<&2, Operation>>) -> String:
144	  match alignment:
145	    case None{}:
146	      "null"
147	    case Some{operations}:
148	      List.show(~&2, ~Operation, ~operation_show, operations)
149	
150	# CIGAR contains only decimal counts and MID=X, so needs no JSON escaping.
151	def cigar_show(cigar: Maybe<&2, String>) -> String:
152	  match cigar:
153	    case None{}:
154	      "null"
155	    case Some{value}:
156	      "\"" ++ value ++ "\""
157	
158	def result_show(result: AlignResult) -> String:
159	  match result:
160	    case AlignResult{status, distance, ends, starts, alignment, cigar}:
161	      "{\"status\":" ++ status_show(status) ++
162	      ",\"edit_distance\":" ++ distance_show(distance) ++
163	      ",\"end_locations\":" ++ coordinates_show(ends) ++
164	      ",\"start_locations\":" ++ starts_show(starts) ++
165	      ",\"alignment\":" ++ alignment_show(alignment) ++
166	      ",\"cigar\":" ++ cigar_show(cigar) ++ "}"
167	
168	def not_found() -> AlignResult:
169	  AlignResult{Ok{}, NotFound{}, Nil{}, None{}, None{}, None{}}
170	
171	def within_threshold(threshold: Threshold, distance: Nat) -> Bool:
172	  match threshold:
173	    case Unlimited{}:
174	      True{}
175	    case MaxDistance{maximum}:
176	      Nat.is_le(distance, maximum)
177	
178	def distance_result(distance: Nat, end: Coordinate, accepted: Bool) -> AlignResult:
179	  match accepted:
180	    case True{}:
181	      AlignResult{Ok{}, Found{distance}, [end], None{}, None{}, None{}}
182	    case False{}:
183	      not_found()