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