EdlibTypes.bend
bend-edit-distance@0.2.2.0 · 217 lines · 35 definitions
1import Base
2
3
4type Mode is Data:
5 NW{}
6 SHW{}
7 HW{}
8
9type Task is Data:
10 Distance{}
11 Locations{}
12 Path{}
13
14type Threshold is Data:
15 Unlimited{}
16 MaxDistance{value: Nat}
17
18type EqualityPair is Data:
19 EqualityPair{first: Char, second: Char}
20
21type CigarFormat is Data:
22 Standard{}
23 Extended{}
24
25type AlignConfig is Data:
26 AlignConfig{mode: Mode, task: Task, threshold: Threshold,
27 equalities: List<&2, EqualityPair>, cigar_format: CigarFormat}
28
29
30type AlignJob is Data:
31 AlignJob{query: String, target: String, config: AlignConfig}
32
33type Status is Data:
34 Ok{}
35 Error{}
36
37type EditDistance is Data:
38 Found{value: Nat}
39 NotFound{}
40
41type Coordinate is Data:
42 BeforeStart{}
43 Position{index: Nat}
44
45type Operation is Data:
46 Match{}
47 Insert{}
48 Delete{}
49 Mismatch{}
50
51
52
53type CigarRun is Data:
54 CigarRun{count: Nat, symbol: Char}
55
56type AlignResult is Data:
57 AlignResult{status: Status, distance: EditDistance,
58 end_locations: List<&2, Coordinate>,
59 start_locations: Maybe<&2, List<&2, Coordinate>>,
60 alignment: Maybe<&2, List<&2, Operation>>, cigar: Maybe<&2, String>}
61
62def default_config() -> AlignConfig:
63 AlignConfig{NW{}, Distance{}, Unlimited{}, Nil{}, Extended{}}
64
65
66
67def pair_matches(pair: EqualityPair, +a: Char, +b: Char) -> Bool:
68 match pair:
69 case EqualityPair{+first, +second}:
70 Bool.or(Bool.and(Char.is_eq(a, first), Char.is_eq(b, second)),
71 Bool.and(Char.is_eq(a, second), Char.is_eq(b, first)))
72
73def equal(pairs: List<&2, EqualityPair>, +a: Char, +b: Char) -> Bool:
74 match pairs:
75 case Nil{}:
76 Char.is_eq(a, b)
77 case pair <> tail:
78 Bool.or(pair_matches(pair, a, b), equal(tail, a, b))
79
80def end_coordinate(length: Nat) -> Coordinate:
81 match length:
82 case 0n:
83 BeforeStart{}
84 case 1n+p:
85 Position{p}
86
87def distance_show(distance: EditDistance) -> String:
88 match distance:
89 case Found{value}:
90 Nat.show(value)
91 case NotFound{}:
92 "-1"
93
94def coordinate_show(position: Coordinate) -> String:
95 match position:
96 case BeforeStart{}:
97 "-1"
98 case Position{index}:
99 Nat.show(index)
100
101def status_show(status: Status) -> String:
102 match status:
103 case Ok{}:
104 "0"
105 case Error{}:
106 "1"
107
108def operation_show(operation: Operation) -> String:
109 match operation:
110 case Match{}:
111 "0"
112 case Insert{}:
113 "1"
114 case Delete{}:
115 "2"
116 case Mismatch{}:
117 "3"
118
119def operation_char(format: CigarFormat, operation: Operation) -> Char:
120 match format operation:
121 case _ Insert{}:
122 'I'
123 case _ Delete{}:
124 'D'
125 case Standard{} _:
126 'M'
127 case Extended{} Match{}:
128 '='
129 case Extended{} Mismatch{}:
130 'X'
131
132def cigar_run_step(runs: List<&2, CigarRun>, count: Nat, symbol: Char,
133 next: Char, same: Bool) -> List<&2, CigarRun>:
134 match same:
135 case True{}:
136 CigarRun{1n+count, symbol} <> runs
137 case False{}:
138 CigarRun{1n, next} <> CigarRun{count, symbol} <> runs
139
140
141
142def alignment_runs_reversed(operations: List<&2, Operation>, +format: CigarFormat,
143 runs: List<&2, CigarRun>) -> List<&2, CigarRun>:
144 match operations runs:
145 case Nil{} _:
146 runs
147 case h <> t Nil{}:
148 alignment_runs_reversed(t, format, [CigarRun{1n, operation_char(format, h)}])
149 case h <> t CigarRun{count, +symbol} <> tail:
150 +next = operation_char(format, h)
151 alignment_runs_reversed(t, format,
152 cigar_run_step(tail, count, symbol, next, Char.is_eq(symbol, next)))
153
154def alignment_runs(operations: List<&2, Operation>, format: CigarFormat) -> List<&2, CigarRun>:
155 List.reverse(&2, CigarRun, alignment_runs_reversed(operations, format, Nil{}))
156
157def cigar_runs_show(runs: List<&2, CigarRun>) -> String:
158 match runs:
159 case Nil{}:
160 ""
161 case CigarRun{count, symbol} <> tail:
162 Nat.show(count) ++ SCon{symbol, cigar_runs_show(tail)}
163
164def alignment_to_cigar(operations: List<&2, Operation>, format: CigarFormat) -> String:
165 cigar_runs_show(alignment_runs(operations, format))
166
167def coordinates_show(locations: List<&2, Coordinate>) -> String:
168 List.show(~&2, ~Coordinate, ~coordinate_show, locations)
169
170def starts_show(locations: Maybe<&2, List<&2, Coordinate>>) -> String:
171 match locations:
172 case None{}:
173 "null"
174 case Some{values}:
175 coordinates_show(values)
176
177def alignment_show(alignment: Maybe<&2, List<&2, Operation>>) -> String:
178 match alignment:
179 case None{}:
180 "null"
181 case Some{operations}:
182 List.show(~&2, ~Operation, ~operation_show, operations)
183
184
185def cigar_show(cigar: Maybe<&2, String>) -> String:
186 match cigar:
187 case None{}:
188 "null"
189 case Some{value}:
190 "\"" ++ value ++ "\""
191
192def result_show(result: AlignResult) -> String:
193 match result:
194 case AlignResult{status, distance, ends, starts, alignment, cigar}:
195 "{\"status\":" ++ status_show(status) ++
196 ",\"edit_distance\":" ++ distance_show(distance) ++
197 ",\"end_locations\":" ++ coordinates_show(ends) ++
198 ",\"start_locations\":" ++ starts_show(starts) ++
199 ",\"alignment\":" ++ alignment_show(alignment) ++
200 ",\"cigar\":" ++ cigar_show(cigar) ++ "}"
201
202def not_found() -> AlignResult:
203 AlignResult{Ok{}, NotFound{}, Nil{}, None{}, None{}, None{}}
204
205def within_threshold(threshold: Threshold, distance: Nat) -> Bool:
206 match threshold:
207 case Unlimited{}:
208 True{}
209 case MaxDistance{maximum}:
210 Nat.is_le(distance, maximum)
211
212def distance_result(distance: Nat, end: Coordinate, accepted: Bool) -> AlignResult:
213 match accepted:
214 case True{}:
215 AlignResult{Ok{}, Found{distance}, [end], None{}, None{}, None{}}
216 case False{}:
217 not_found()