ICFP 2007 Contest: https://web.archive.org/web/20090301164728/https://save-endo.cs.uu.nl/
drubery.com
1use crate::base::Base;
2use crate::pattern::Pattern;
3use crate::pattern::PatternItem;
4use crate::rna::Rna;
5use crate::template::Template;
6use crate::template::TemplateItem;
7use std::mem;
8
9pub struct Parser<I>
10where
11 I: Iterator<Item = Base>,
12{
13 iter: I,
14 peeked: Vec<Base>,
15 index: usize,
16}
17
18impl<I> Parser<I>
19where
20 I: Iterator<Item = Base>,
21{
22 pub fn new(iter: I) -> Parser<I> {
23 Parser {
24 iter: iter,
25 peeked: Vec::new(),
26 index: 0,
27 }
28 }
29
30 pub fn index(&self) -> usize {
31 self.index
32 }
33
34 fn peek_to(&mut self, n: usize) {
35 while self.peeked.len() < n {
36 if let Some(b) = self.iter.next() {
37 self.peeked.push(b);
38 } else {
39 return;
40 }
41 }
42 }
43
44 pub fn next_is(&mut self, next: &[Base]) -> bool {
45 self.peek_to(next.len());
46 if self.peeked.len() < next.len() {
47 return false;
48 }
49 return &self.peeked[..next.len()] == next;
50 }
51
52 pub fn advance(&mut self, n: usize) {
53 self.peek_to(n);
54 self.index += n;
55 self.peeked.drain(..n);
56 }
57
58 pub fn nat(&mut self) -> Option<usize> {
59 let mut ret = 0;
60 let mut bit = 1;
61 loop {
62 if self.next_is(&[Base::P]) {
63 self.advance(1);
64 return Some(ret);
65 } else if self.next_is(&[Base::I]) || self.next_is(&[Base::F]) {
66 self.advance(1);
67 } else if self.next_is(&[Base::C]) {
68 ret += bit;
69 self.advance(1);
70 } else {
71 return None;
72 }
73
74 bit *= 2;
75 }
76 }
77
78 pub fn consts(&mut self) -> Vec<Base> {
79 let mut ret = Vec::new();
80 loop {
81 if self.next_is(&[Base::C]) {
82 self.advance(1);
83 ret.push(Base::I);
84 } else if self.next_is(&[Base::F]) {
85 self.advance(1);
86 ret.push(Base::C);
87 } else if self.next_is(&[Base::P]) {
88 self.advance(1);
89 ret.push(Base::F);
90 } else if self.next_is(&[Base::I, Base::C]) {
91 self.advance(2);
92 ret.push(Base::P);
93 } else {
94 return ret;
95 }
96 }
97 }
98
99 pub fn pattern(&mut self, rna: &mut Vec<Rna>) -> Option<Pattern> {
100 let mut ret = Vec::new();
101 let mut level = 0;
102 loop {
103 if self.next_is(&[Base::C]) {
104 self.advance(1);
105 ret.push(PatternItem::Base(Base::I));
106 } else if self.next_is(&[Base::F]) {
107 self.advance(1);
108 ret.push(PatternItem::Base(Base::C));
109 } else if self.next_is(&[Base::P]) {
110 self.advance(1);
111 ret.push(PatternItem::Base(Base::F));
112 } else if self.next_is(&[Base::I, Base::C]) {
113 self.advance(2);
114 ret.push(PatternItem::Base(Base::P));
115 } else if self.next_is(&[Base::I, Base::P]) {
116 self.advance(2);
117 let n = self.nat()?;
118 ret.push(PatternItem::Skip(n));
119 } else if self.next_is(&[Base::I, Base::F]) {
120 self.advance(3);
121 let s = self.consts();
122 ret.push(PatternItem::Search(s));
123 } else if self.next_is(&[Base::I, Base::I, Base::P]) {
124 self.advance(3);
125 level += 1;
126 ret.push(PatternItem::Open);
127 } else if self.next_is(&[Base::I, Base::I, Base::C])
128 || self.next_is(&[Base::I, Base::I, Base::F])
129 {
130 self.advance(3);
131 if level == 0 {
132 return Some(Pattern::new(ret));
133 }
134 level -= 1;
135 ret.push(PatternItem::Close);
136 } else if self.next_is(&[Base::I, Base::I, Base::I]) {
137 self.advance(3);
138 self.peek_to(7);
139 let mut r = Vec::new();
140 mem::swap(&mut r, &mut self.peeked);
141 rna.push(r.try_into().unwrap());
142 self.index += 7;
143 } else {
144 return None;
145 }
146 }
147 }
148
149 pub fn template(&mut self, rna: &mut Vec<Rna>) -> Option<Template> {
150 let mut ret = Vec::new();
151 loop {
152 if self.next_is(&[Base::C]) {
153 self.advance(1);
154 ret.push(TemplateItem::Base(Base::I));
155 } else if self.next_is(&[Base::F]) {
156 self.advance(1);
157 ret.push(TemplateItem::Base(Base::C));
158 } else if self.next_is(&[Base::P]) {
159 self.advance(1);
160 ret.push(TemplateItem::Base(Base::F));
161 } else if self.next_is(&[Base::I, Base::C]) {
162 self.advance(2);
163 ret.push(TemplateItem::Base(Base::P));
164 } else if self.next_is(&[Base::I, Base::P]) || self.next_is(&[Base::I, Base::F]) {
165 self.advance(2);
166 let l = self.nat()?;
167 let n = self.nat()?;
168 ret.push(TemplateItem::Ref(n, l));
169 } else if self.next_is(&[Base::I, Base::I, Base::C])
170 || self.next_is(&[Base::I, Base::I, Base::F])
171 {
172 self.advance(3);
173 return Some(Template::new(ret));
174 } else if self.next_is(&[Base::I, Base::I, Base::P]) {
175 self.advance(3);
176 let n = self.nat()?;
177 ret.push(TemplateItem::Len(n));
178 } else if self.next_is(&[Base::I, Base::I, Base::I]) {
179 self.advance(3);
180 self.peek_to(7);
181 let mut r = Vec::new();
182 mem::swap(&mut r, &mut self.peeked);
183 rna.push(r.try_into().unwrap());
184 self.index += 7;
185 } else {
186 return None;
187 }
188 }
189 }
190}
191
192#[cfg(test)]
193mod tests {
194 use super::*;
195
196 fn dna_from_str(s: &str) -> Vec<Base> {
197 s.chars().filter_map(|c| Base::from_char(c)).collect()
198 }
199
200 #[test]
201 fn test_base() {
202 let dna = dna_from_str("ICFP").into_iter();
203 let mut parser = Parser::new(dna);
204 assert!(parser.next_is(&[Base::I]));
205 assert!(parser.next_is(&[Base::I, Base::C]));
206 assert!(parser.next_is(&[Base::I, Base::C, Base::F]));
207 assert!(parser.next_is(&[Base::I, Base::C, Base::F, Base::P]));
208 }
209
210 #[test]
211 fn test_nat() {
212 let dna = dna_from_str("CP").into_iter();
213 let mut parser = Parser::new(dna);
214 assert_eq!(parser.nat(), Some(1));
215 assert_eq!(parser.index, 2);
216
217 let dna = dna_from_str("ICICP").into_iter();
218 let mut parser = Parser::new(dna);
219 assert_eq!(parser.nat(), Some(10));
220 assert_eq!(parser.index, 5);
221
222 let dna = dna_from_str("III").into_iter();
223 let mut parser = Parser::new(dna);
224 assert_eq!(parser.nat(), None);
225 assert_eq!(parser.index, 3);
226 }
227
228 #[test]
229 fn test_consts() {
230 let dna = dna_from_str("CFPICIIC").into_iter();
231 let mut parser = Parser::new(dna);
232 assert_eq!(parser.consts(), &[Base::I, Base::C, Base::F, Base::P]);
233 assert_eq!(parser.index, 5);
234 }
235
236 #[test]
237 fn test_pattern() {
238 let mut rna = Vec::new();
239
240 let dna = dna_from_str("CIIC").into_iter();
241 let mut parser = Parser::new(dna);
242 assert_eq!(
243 parser.pattern(&mut rna),
244 Some(Pattern::new(vec![PatternItem::Base(Base::I)]))
245 );
246 assert_eq!(parser.index, 4);
247
248 let dna = dna_from_str("IIPIPICPIICICIIF").into_iter();
249 let mut parser = Parser::new(dna);
250 assert_eq!(
251 parser.pattern(&mut rna),
252 Some(Pattern::new(vec![
253 PatternItem::Open,
254 PatternItem::Skip(2),
255 PatternItem::Close,
256 PatternItem::Base(Base::P)
257 ]))
258 );
259 assert_eq!(parser.index, 16);
260
261 let dna = dna_from_str("IIIPFCICFPIIC").into_iter();
262 let mut parser = Parser::new(dna);
263 assert_eq!(parser.pattern(&mut rna), Some(Pattern::new(vec![])));
264 assert_eq!(parser.index, 13);
265 assert_eq!(
266 rna,
267 vec![[
268 Base::P,
269 Base::F,
270 Base::C,
271 Base::I,
272 Base::C,
273 Base::F,
274 Base::P
275 ]]
276 );
277 }
278
279 #[test]
280 fn test_template() {
281 let mut rna = Vec::new();
282
283 let dna = dna_from_str("CFPICIFCPICPIIPIICPIIC").into_iter();
284 let mut parser = Parser::new(dna);
285 assert_eq!(
286 parser.template(&mut rna),
287 Some(Template::new(vec![
288 TemplateItem::Base(Base::I),
289 TemplateItem::Base(Base::C),
290 TemplateItem::Base(Base::F),
291 TemplateItem::Base(Base::P),
292 TemplateItem::Ref(2, 1),
293 TemplateItem::Len(4)
294 ]))
295 );
296 assert_eq!(parser.index, 22);
297
298 let dna = dna_from_str("IIIPFCICFPIIC").into_iter();
299 let mut parser = Parser::new(dna);
300 assert_eq!(parser.template(&mut rna), Some(Template::new(vec![])));
301 assert_eq!(parser.index, 13);
302 assert_eq!(
303 rna,
304 vec![[
305 Base::P,
306 Base::F,
307 Base::C,
308 Base::I,
309 Base::C,
310 Base::F,
311 Base::P
312 ]]
313 );
314 }
315}