ICFP 2007 Contest: https://web.archive.org/web/20090301164728/https://save-endo.cs.uu.nl/
drubery.com
1use dna_parsing::base::Base;
2use std::collections::VecDeque;
3use std::ops::Add;
4use std::ops::AddAssign;
5use std::ops::Deref;
6use std::ops::Index;
7use std::rc::Rc;
8
9#[derive(Clone, Debug)]
10pub enum Dna {
11 Empty,
12 Leaf(Base),
13 TwoNode(TwoNode),
14 ThreeNode(ThreeNode),
15}
16
17#[derive(Clone, Debug)]
18// Wrap Rc in a single-value enum so I can implement traits for it.
19pub enum DnaRef {
20 DnaRef(Rc<Dna>),
21}
22
23#[derive(Clone, Debug)]
24pub struct TwoNode {
25 len: usize,
26 depth: usize,
27 children: (DnaRef, DnaRef),
28}
29
30#[derive(Clone, Debug)]
31pub struct ThreeNode {
32 len: usize,
33 depth: usize,
34 children: (DnaRef, DnaRef, DnaRef),
35}
36
37impl DnaRef {
38 pub fn new() -> Self {
39 Self::DnaRef(Rc::new(Dna::Empty))
40 }
41
42 pub fn from_base(b: Base) -> Self {
43 Self::DnaRef(Rc::new(Dna::Leaf(b)))
44 }
45
46 fn from_two_children(a: DnaRef, b: DnaRef) -> Self {
47 debug_assert_eq!(a.depth(), b.depth());
48 Self::DnaRef(Rc::new(Dna::TwoNode(TwoNode {
49 len: a.len() + b.len(),
50 depth: a.depth() + 1,
51 children: (a, b),
52 })))
53 }
54
55 fn from_three_children(a: DnaRef, b: DnaRef, c: DnaRef) -> Self {
56 debug_assert_eq!(a.depth(), b.depth());
57 debug_assert_eq!(a.depth(), c.depth());
58 Self::DnaRef(Rc::new(Dna::ThreeNode(ThreeNode {
59 len: a.len() + b.len() + c.len(),
60 depth: a.depth() + 1,
61 children: (a, b, c),
62 })))
63 }
64
65 pub fn from_string(s: &str) -> Self {
66 s.chars()
67 .filter_map(|c| Base::from_char(c))
68 .map(|b| DnaRef::from_base(b))
69 .collect::<DnaRef>()
70 }
71
72 pub fn len(&self) -> usize {
73 match &**self {
74 Dna::Empty => 0,
75 Dna::Leaf(_) => 1,
76 Dna::TwoNode(node) => node.len,
77 Dna::ThreeNode(node) => node.len,
78 }
79 }
80
81 fn depth(&self) -> usize {
82 match &**self {
83 Dna::Empty => 0,
84 Dna::Leaf(_) => 1,
85 Dna::TwoNode(node) => node.depth,
86 Dna::ThreeNode(node) => node.depth,
87 }
88 }
89
90 pub fn iter<'a>(&'a self) -> DnaIterator<'a> {
91 let mut stack = Vec::new();
92 stack.push(self);
93 DnaIterator { stack }
94 }
95
96 pub fn split(&self, n: usize) -> (DnaRef, DnaRef) {
97 debug_assert!(n <= self.len());
98 match &**self {
99 Dna::Empty => (DnaRef::new(), DnaRef::new()),
100 Dna::Leaf(b) => {
101 if n == 0 {
102 (DnaRef::new(), DnaRef::from_base(*b))
103 } else {
104 (DnaRef::from_base(*b), DnaRef::new())
105 }
106 }
107 Dna::TwoNode(node) => {
108 let (a, b) = &node.children;
109 if n < a.len() {
110 let (x, y) = a.split(n);
111 (x, y + b)
112 } else if n == a.len() {
113 (a.clone(), b.clone())
114 } else {
115 let (x, y) = b.split(n - a.len());
116 (a + x, y)
117 }
118 }
119 Dna::ThreeNode(node) => {
120 let (a, b, c) = &node.children;
121 if n < a.len() {
122 let (x, y) = a.split(n);
123 (x, y + b + c)
124 } else if n == a.len() {
125 (a.clone(), b + c)
126 } else if n - a.len() < b.len() {
127 let (x, y) = b.split(n - a.len());
128 (a + x, y + c)
129 } else if n == a.len() + b.len() {
130 (a + b, c.clone())
131 } else {
132 let (x, y) = c.split(n - a.len() - b.len());
133 (a + b + x, y)
134 }
135 }
136 }
137 }
138
139 #[cfg(test)]
140 pub fn to_string(&self) -> String {
141 self.iter().map(|b| Base::to_char(&b)).collect::<String>()
142 }
143}
144
145impl Deref for DnaRef {
146 type Target = Dna;
147
148 fn deref(&self) -> &Self::Target {
149 match self {
150 DnaRef::DnaRef(r) => &*r,
151 }
152 }
153}
154
155struct DnaRefIter<I>
156where
157 I: Iterator<Item = DnaRef>,
158{
159 iter: I,
160 buf: VecDeque<DnaRef>,
161}
162
163impl<I> DnaRefIter<I>
164where
165 I: Iterator<Item = DnaRef>,
166{
167 fn new(iter: I) -> DnaRefIter<I> {
168 DnaRefIter {
169 iter: iter,
170 buf: VecDeque::with_capacity(5),
171 }
172 }
173}
174
175impl<I> Iterator for DnaRefIter<I>
176where
177 I: Iterator<Item = DnaRef>,
178{
179 type Item = DnaRef;
180 fn next(&mut self) -> Option<Self::Item> {
181 while self.buf.len() < 5 {
182 let Some(x) = self.iter.next() else {
183 break;
184 };
185
186 self.buf.push_back(x);
187 }
188
189 if self.buf.len() == 5 || self.buf.len() == 3 {
190 let a = self.buf.pop_front().unwrap();
191 let b = self.buf.pop_front().unwrap();
192 let c = self.buf.pop_front().unwrap();
193
194 return Some(DnaRef::from_three_children(a, b, c));
195 } else if self.buf.len() == 4 || self.buf.len() == 2 {
196 let a = self.buf.pop_front().unwrap();
197 let b = self.buf.pop_front().unwrap();
198
199 return Some(DnaRef::from_two_children(a, b));
200 } else {
201 return None;
202 }
203 }
204}
205
206impl FromIterator<DnaRef> for DnaRef {
207 fn from_iter<I: IntoIterator<Item = DnaRef>>(iter: I) -> DnaRef {
208 // We need some kind of buffer no matter what, even if we aggregate as we go.
209 // This implementation does the easy thing and just repeatedly collects into a Vec.
210 let mut cur: Vec<DnaRef> = iter.into_iter().collect::<Vec<_>>();
211 while cur.len() > 1 {
212 cur = DnaRefIter::new(cur.into_iter()).collect();
213 }
214
215 match cur.pop() {
216 Some(dna) => dna,
217 None => DnaRef::new(),
218 }
219 }
220}
221
222pub struct DnaIterator<'a> {
223 stack: Vec<&'a DnaRef>,
224}
225
226impl<'a> Iterator for DnaIterator<'a> {
227 type Item = Base;
228
229 fn next(&mut self) -> Option<Self::Item> {
230 while let Some(node) = self.stack.pop() {
231 match &**node {
232 Dna::Empty => return None,
233 Dna::Leaf(c) => return Some(*c),
234 Dna::TwoNode(node) => {
235 let (a, b) = &node.children;
236 self.stack.push(b);
237 self.stack.push(a);
238 }
239 Dna::ThreeNode(node) => {
240 let (a, b, c) = &node.children;
241 self.stack.push(c);
242 self.stack.push(b);
243 self.stack.push(a);
244 }
245 }
246 }
247
248 return None;
249 }
250}
251
252enum AddState {
253 One(DnaRef),
254 Two(DnaRef, DnaRef),
255}
256
257fn add_helper(lhs: &DnaRef, rhs: &DnaRef) -> AddState {
258 if lhs.depth() == rhs.depth() {
259 AddState::Two(lhs.clone(), rhs.clone())
260 } else if lhs.depth() < rhs.depth() {
261 match &**rhs {
262 Dna::Empty => unreachable!(),
263 Dna::Leaf(_) => AddState::One(rhs.clone()),
264 Dna::TwoNode(node) => {
265 let (a, b) = &node.children;
266 match add_helper(lhs, a) {
267 AddState::One(x) => AddState::One(DnaRef::from_two_children(x, b.clone())),
268 AddState::Two(x, y) => {
269 AddState::One(DnaRef::from_three_children(x, y, b.clone()))
270 }
271 }
272 }
273 Dna::ThreeNode(node) => {
274 let (a, b, c) = &node.children;
275 match add_helper(lhs, a) {
276 AddState::One(x) => {
277 AddState::One(DnaRef::from_three_children(x, b.clone(), c.clone()))
278 }
279 AddState::Two(x, y) => AddState::Two(
280 DnaRef::from_two_children(x, y),
281 DnaRef::from_two_children(b.clone(), c.clone()),
282 ),
283 }
284 }
285 }
286 } else {
287 match &**lhs {
288 Dna::Empty => unreachable!(),
289 Dna::Leaf(_) => AddState::One(lhs.clone()),
290 Dna::TwoNode(node) => {
291 let (a, b) = &node.children;
292 match add_helper(b, rhs) {
293 AddState::One(x) => AddState::One(DnaRef::from_two_children(a.clone(), x)),
294 AddState::Two(x, y) => {
295 AddState::One(DnaRef::from_three_children(a.clone(), x, y))
296 }
297 }
298 }
299 Dna::ThreeNode(node) => {
300 let (a, b, c) = &node.children;
301 match add_helper(c, rhs) {
302 AddState::One(x) => {
303 AddState::One(DnaRef::from_three_children(a.clone(), b.clone(), x))
304 }
305 AddState::Two(x, y) => AddState::Two(
306 DnaRef::from_two_children(a.clone(), b.clone()),
307 DnaRef::from_two_children(x, y),
308 ),
309 }
310 }
311 }
312 }
313}
314
315impl Add<DnaRef> for DnaRef {
316 type Output = DnaRef;
317
318 fn add(self, other: DnaRef) -> DnaRef {
319 match add_helper(&self, &other) {
320 AddState::One(a) => a,
321 AddState::Two(a, b) => DnaRef::from_two_children(a, b),
322 }
323 }
324}
325
326impl Add<&DnaRef> for DnaRef {
327 type Output = DnaRef;
328
329 fn add(self, other: &DnaRef) -> DnaRef {
330 match add_helper(&self, other) {
331 AddState::One(a) => a,
332 AddState::Two(a, b) => DnaRef::from_two_children(a, b),
333 }
334 }
335}
336
337impl Add<DnaRef> for &DnaRef {
338 type Output = DnaRef;
339
340 fn add(self, other: DnaRef) -> DnaRef {
341 match add_helper(self, &other) {
342 AddState::One(a) => a,
343 AddState::Two(a, b) => DnaRef::from_two_children(a, b),
344 }
345 }
346}
347
348impl Add<&DnaRef> for &DnaRef {
349 type Output = DnaRef;
350
351 fn add(self, other: &DnaRef) -> DnaRef {
352 match add_helper(self, other) {
353 AddState::One(a) => a,
354 AddState::Two(a, b) => DnaRef::from_two_children(a, b),
355 }
356 }
357}
358
359impl AddAssign<DnaRef> for DnaRef {
360 fn add_assign(&mut self, other: DnaRef) {
361 match add_helper(self, &other) {
362 AddState::One(a) => {
363 *self = a;
364 }
365 AddState::Two(a, b) => {
366 *self = Self::from_two_children(a, b);
367 }
368 }
369 }
370}
371
372impl AddAssign<&DnaRef> for DnaRef {
373 fn add_assign(&mut self, other: &DnaRef) {
374 match add_helper(self, other) {
375 AddState::One(a) => {
376 *self = a;
377 }
378 AddState::Two(a, b) => {
379 *self = Self::from_two_children(a, b);
380 }
381 }
382 }
383}
384
385impl Index<usize> for DnaRef {
386 type Output = Base;
387
388 fn index(&self, n: usize) -> &Self::Output {
389 debug_assert!(n < self.len());
390
391 match &**self {
392 Dna::Empty => unreachable!(),
393 Dna::Leaf(c) => c,
394 Dna::TwoNode(node) => {
395 let (a, b) = &node.children;
396 if n < a.len() {
397 a.index(n)
398 } else {
399 b.index(n - a.len())
400 }
401 }
402 Dna::ThreeNode(node) => {
403 let (a, b, c) = &node.children;
404 if n < a.len() {
405 a.index(n)
406 } else if n < a.len() + b.len() {
407 b.index(n - a.len())
408 } else {
409 c.index(n - a.len() - b.len())
410 }
411 }
412 }
413 }
414}
415
416#[cfg(test)]
417mod tests {
418 use super::*;
419
420 #[test]
421 fn test_empty() {
422 let dna: DnaRef = DnaRef::new();
423 assert_eq!(dna.len(), 0);
424 }
425
426 #[test]
427 fn test_to_from_string() {
428 let dna: DnaRef = DnaRef::from_string("ICFP");
429 assert_eq!(dna.to_string(), "ICFP");
430 }
431
432 #[test]
433 fn test_index() {
434 let s = "ICFP";
435 let dna: DnaRef = DnaRef::from_string(s);
436 assert_eq!(dna[0], Base::I);
437 assert_eq!(dna[1], Base::C);
438 assert_eq!(dna[2], Base::F);
439 assert_eq!(dna[3], Base::P);
440 }
441
442 #[test]
443 fn test_add() {
444 let lhs = DnaRef::from_string("IIIC");
445 let rhs = DnaRef::from_string("PFFF");
446 assert_eq!((lhs + rhs).to_string(), "IIICPFFF");
447 }
448
449 #[test]
450 fn test_split() {
451 let dna = DnaRef::from_string("IIICPFFF");
452 let (lhs, rhs) = dna.split(4);
453 assert_eq!(lhs.to_string(), "IIIC");
454 assert_eq!(rhs.to_string(), "PFFF");
455 }
456}