1use std::ops::Add;
2
3use lazy::{Lazy,strict,value,redirect};
4
5use digit;
6use digit::Digit;
7use digit::Digit::{One, Two, Three, Four};
8use self::FingerTree::{Empty, Single, Deep};
9use node::{Node, node3};
10use node::Node::{Leaf};
11use node;
12use measure::Measure;
13use zero::Zero;
14
15#[derive(Debug)]
16pub enum FingerTree<T,M> {
17 Empty,
18 Single(Lazy<Node<T,M>>),
19 Deep(M, Digit<T,M>, Lazy<FingerTree<T,M>>, Digit<T,M>)
20}
21
22impl<T,M> FingerTree<T,M> {
23 pub fn iter(&self) -> Iter<T,M> {
24 Iter::new(self)
25 }
26}
27pub fn empty<T,M>() -> Lazy<FingerTree<T,M>> {
28 strict(Empty)
29}
30pub fn single<T,M>(node: Lazy<Node<T,M>>) -> Lazy<FingerTree<T,M>> {
31 strict(Single(node))
32}
33pub fn deep<T,M>(left: Digit<T,M>, middle: Lazy<FingerTree<T,M>>, right: Digit<T,M>)
34 -> Lazy<FingerTree<T,M>>
35 where T: Measure<M> + 'static,
36 M: Add<Output=M> + Zero + Copy + 'static
37{
38 lazy_val!{
39 let measure = left.measure() +
40 middle.measure() +
41 right.measure();
42 Deep(measure, left, middle, right)
43 }
44}
45
46pub fn cons_node<T,M>(x0: Lazy<Node<T,M>>, tree: Lazy<FingerTree<T,M>>)
47 -> Lazy<FingerTree<T,M>>
48 where T: Measure<M> + 'static,
49 M: Add<Output=M> + Zero + Copy + 'static
50{
51 lazy_val!{
52 match *tree {
53 Empty => Single(x0),
54 Single(ref x1) => {
55 let measure = x0.measure() + x1.measure();
56 Deep(measure, One(x0), strict(Empty), One(x1.clone()))
57 },
58 Deep(measure, ref left, ref middle, ref right) => {
59 let measure = measure + x0.measure();
60 match *left {
61 Four(ref x1,ref x2,ref x3,ref x4) => {
62 let left = Two(x0.clone(),x1.clone());
63 let middle = cons_node(
64 node3(x2.clone(),x3.clone(),x4.clone()),
65 middle.clone());
66 Deep(measure, left, middle, right.clone())
67 },
68 Three(ref x1,ref x2,ref x3) => {
69 let left = Four(x0.clone(),x1.clone(),x2.clone(),x3.clone());
70 Deep(measure, left, middle.clone(), right.clone())
71 },
72 Two(ref x1,ref x2) => {
73 let left = Three(x0.clone(),x1.clone(),x2.clone());
74 Deep(measure, left, middle.clone(), right.clone())
75 },
76 One(ref x1) => {
77 let left = Two(x0.clone(),x1.clone());
78 Deep(measure, left, middle.clone(), right.clone())
79 },
80 }
81 }
82 }
83 }
84}
85
86pub fn snoc_node<T,M>(tree: Lazy<FingerTree<T,M>>, x0: Lazy<Node<T,M>>)
87 -> Lazy<FingerTree<T,M>>
88 where T: Measure<M> + 'static,
89 M: Add<Output=M> + Zero + Copy + 'static
90{
91 lazy_val!{
92 match *tree {
93 Empty => Single(x0),
94 Single(ref x1) => {
95 let measure = x1.measure() + x0.measure();
96 Deep(measure, One(x1.clone()), strict(Empty), One(x0))
97 },
98 Deep(measure, ref left, ref middle, ref right) => {
99 let measure = measure + x0.measure();
100 match *right {
101 Four(ref x4,ref x3,ref x2,ref x1) => {
102 let right = Two(x1.clone(),x0.clone());
103 let middle = snoc_node(
104 middle.clone(),
105 node3(x4.clone(),x3.clone(),x2.clone()));
106 Deep(measure, left.clone(), middle, right)
107 },
108 Three(ref x3,ref x2,ref x1) => {
109 let right = Four(x3.clone(),x2.clone(),x1.clone(),x0.clone());
110 Deep(measure, left.clone(), middle.clone(), right)
111 },
112 Two(ref x2,ref x1) => {
113 let right = Three(x2.clone(),x1.clone(),x0.clone());
114 Deep(measure, left.clone(), middle.clone(), right)
115 },
116 One(ref x1) => {
117 let right = Two(x1.clone(),x0.clone());
118 Deep(measure, left.clone(), middle.clone(), right)
119 },
120 }
121 }
122 }
123 }
124}
125
126macro_rules! cons_nodes {
127 ( ; $t: expr) => { $t };
128 ($e0: expr $(, $e: expr)* ; $t: expr) => {
129 cons_node(
130 $e0,
131 cons_nodes!($($e),* ; $t))
132 };
133}
134
135macro_rules! snoc_nodes{
136 ($t: expr ; ) => { $t };
137 ($t: expr ; $e0: expr $(, $e: expr)* ) => {
138 snoc_nodes!(
139 snoc_node($t, $e0) ;
140 $($e),*)
141 };
142}
143
144fn cons_digit<T,M>(digit: Digit<T,M>, tree: Lazy<FingerTree<T,M>>)
145 -> Lazy<FingerTree<T,M>>
146 where T: Measure<M> + 'static,
147 M: Add<Output=M> + Zero + Copy + 'static
148{
149 match digit {
150 One(x0) =>
151 cons_nodes!(x0; tree),
152 Two(x0, x1) =>
153 cons_nodes!(x0, x1; tree),
154 Three(x0, x1, x2) =>
155 cons_nodes!(x0, x1, x2; tree),
156 Four(x0, x1, x2, x3) =>
157 cons_nodes!(x0, x1, x2, x3; tree),
158 }
159}
160
161fn snoc_digit<T,M>(tree: Lazy<FingerTree<T,M>>, digit: Digit<T,M>)
162 -> Lazy<FingerTree<T,M>>
163 where T: Measure<M> + 'static,
164 M: Add<Output=M> + Zero + Copy + 'static
165{
166 match digit {
167 One(x0) =>
168 snoc_nodes!(tree; x0),
169 Two(x1, x0) =>
170 snoc_nodes!(tree; x1, x0),
171 Three(x2, x1, x0) =>
172 snoc_nodes!(tree; x2, x1, x0),
173 Four(x3, x2, x1, x0) =>
174 snoc_nodes!(tree; x3, x2, x1, x0),
175 }
176}
177
178pub fn tree_tree<T,M>(left: Lazy<FingerTree<T,M>>, right: Lazy<FingerTree<T,M>>)
179 -> Lazy<FingerTree<T,M>>
180 where T: Measure<M> + 'static,
181 M: Add<Output=M> + Zero + Copy + 'static
182{
183 lazy!{
184 if let Empty = *left {
185 return redirect(right)
186 };
187 if let Empty = *right {
188 return redirect(left)
189 };
190 if let Single(ref node) = *left {
191 return redirect(cons_node(node.clone(), right))
192 };
193 if let Single(ref node) = *right {
194 return redirect(snoc_node(left, node.clone()))
195 };
196 if let Deep(s0, ref l0, ref m0, ref r0) = *left {
197 if let Deep(s1, ref l1, ref m1, ref r1) = *right {
198 let s = s0 + s1;
199 let l = l0.clone();
200 let m = tree_digit_tree(
201 m0.clone(),
202 add_digits!(r0.clone(), l1.clone()),
203 m1.clone());
204 let r = r1.clone();
205 return value(Deep(s, l, m, r))
206 }
207 };
208 unsafe {debug_unreachable!()}
209 }
210}
211
212fn tree_digit_tree<T,M>(left: Lazy<FingerTree<T,M>>, d: Digit<T,M>, right: Lazy<FingerTree<T,M>>)
213 -> Lazy<FingerTree<T,M>>
214 where T: Measure<M> + 'static,
215 M: Add<Output=M> + Zero + Copy + 'static
216{
217 lazy!{
218 if let Empty = *left {
219 return redirect(cons_digit(d, right))
220 };
221 if let Empty = *right {
222 return redirect(snoc_digit(left, d))
223 };
224 if let Single(ref node) = *left {
225 return redirect(cons_node(node.clone(),
226 cons_digit(d, right)))
227 };
228 if let Single(ref node) = *right {
229 return redirect(snoc_node(snoc_digit(left, d),
230 node.clone()))
231 };
232 if let Deep(s0, ref l0, ref m0, ref r0) = *left {
233 if let Deep(s1, ref l1, ref m1, ref r1) = *right {
234 let s = s0 + d.measure() + s1;
235 let l = l0.clone();
236 let m = tree_digit_tree(m0.clone(), add_digits!(r0.clone(), d.clone(), l1.clone()), m1.clone());
237 let r = r1.clone();
238 return value(Deep(s, l, m, r))
239 }
240 };
241 unsafe {debug_unreachable!()}
242 }
243}
244
245pub fn front<T,M>(tree: &Lazy<FingerTree<T,M>>) -> Option<&T> {
246 let front_node = match **tree {
247 Empty => return None,
248 Single(ref node) => node,
249 Deep(_, ref left, _, _) => match *left {
250 One (ref node) => node,
251 Two (ref node, _) => node,
252 Three(ref node, _, _) => node,
253 Four (ref node, _, _, _) => node,
254 }
255 };
256 match **front_node {
257 Leaf(ref x) => Some(x),
258 _ => unsafe { debug_unreachable!() },
259 }
260}
261
262pub fn back<T,M>(tree: &Lazy<FingerTree<T,M>>) -> Option<&T> {
263 let back_node = match **tree {
264 Empty => return None,
265 Single(ref node) => node,
266 Deep(_, _, _, ref right) => match *right {
267 One (ref node) => node,
268 Two (_, ref node) => node,
269 Three(_, _, ref node) => node,
270 Four (_, _, _, ref node) => node,
271 }
272 };
273 match **back_node {
274 Leaf(ref x) => Some(x),
275 _ => unsafe { debug_unreachable!() },
276 }
277}
278
279impl<'a,T,M> From<&'a Digit<T,M>> for Lazy<FingerTree<T,M>>
280 where T: Measure<M> + 'static,
281 M: Add<Output=M> + Zero + Copy + 'static
282{
283 fn from(digit: &'a Digit<T,M>) -> Lazy<FingerTree<T,M>> {
284 match *digit {
285 One(ref x0) =>
286 single(x0.clone()),
287 Two(ref x0, ref x1) =>
288 deep(One(x0.clone()), empty(), One(x1.clone())),
289 Three(ref x0, ref x1, ref x2) =>
290 deep(Two(x0.clone(), x1.clone()), empty(), One(x2.clone())),
291 Four(ref x0, ref x1, ref x2, ref x3) =>
292 deep(Two(x0.clone(), x1.clone()), empty(), Two(x2.clone(), x3.clone())),
293 }
294 }
295}
296
297impl<T,M> From<Digit<T,M>> for Lazy<FingerTree<T,M>>
298 where T: Measure<M> + 'static,
299 M: Add<Output=M> + Zero + Copy + 'static
300{
301 fn from(digit: Digit<T,M>) -> Lazy<FingerTree<T,M>> {
302 (&digit).into()
303 }
304}
305
306impl<T,M> From<Option<Digit<T,M>>> for Lazy<FingerTree<T,M>>
307 where T: Measure<M> + 'static,
308 M: Add<Output=M> + Zero + Copy + 'static
309{
310 fn from(digit: Option<Digit<T,M>>) -> Lazy<FingerTree<T,M>> {
311 match digit {
312 None => empty(),
313 Some(digit) => digit.into(),
314 }
315 }
316}
317
318fn viewl_node<T,M>(tree: &Lazy<FingerTree<T,M>>) -> (Option<&Node<T,M>>, Lazy<FingerTree<T,M>>)
319 where T: Measure<M> + 'static,
320 M: Add<Output=M> + Zero + Copy + 'static
321{
322 match **tree {
323 Empty => (None, empty()),
324 Single(ref node) => (Some(node),empty()),
325 Deep(_, ref left, ref middle, ref right) =>
326 match *left {
327 Two(ref x0, ref x1) =>
328 (Some(x0), deep(One(x1.clone()),middle.clone(), right.clone())),
329 Three(ref x0, ref x1, ref x2) =>
330 (Some(x0), deep(Two(x1.clone(),x2.clone()),middle.clone(), right.clone())),
331 Four(ref x0, ref x1, ref x2, ref x3) =>
332 (Some(x0), deep(Three(x1.clone(),x2.clone(),x3.clone()),middle.clone(), right.clone())),
333 One(ref x0) => {
334 let remx = match viewl_node(middle) {
335 (None, _) =>
336 right.into(),
337 (Some(y),remy) =>
338 deep(y.into(), remy, right.clone())
339 };
340 (Some(x0), remx)
341 }
342 }
343 }
344}
345
346pub fn pop_front<T,M>(tree: &Lazy<FingerTree<T,M>>) -> Lazy<FingerTree<T,M>>
347 where T: Measure<M> + 'static,
348 M: Add<Output=M> + Zero + Copy + 'static
349{
350 match viewl_node(tree) {
351 (_,rem) => rem,
352 }
353}
354
355
356fn viewr_node<T,M>(tree: &Lazy<FingerTree<T,M>>) -> (Lazy<FingerTree<T,M>>, Option<&Node<T,M>>)
357 where T: Measure<M> + 'static,
358 M: Add<Output=M> + Zero + Copy + 'static
359{
360 match **tree {
361 Empty => (empty(), None),
362 Single(ref node) => (empty(), Some(node)),
363 Deep(_, ref left, ref middle, ref right) =>
364 match *right {
365 Two(ref x1,ref x0) =>
366 (deep(left.clone(), middle.clone(), One(x1.clone())), Some(x0)),
367 Three(ref x2,ref x1,ref x0) =>
368 (deep(left.clone(), middle.clone(), Two(x2.clone(), x1.clone())), Some(x0)),
369 Four(ref x3,ref x2,ref x1,ref x0) =>
370 (deep(left.clone(), middle.clone(), Three(x3.clone(), x2.clone(), x1.clone())), Some(x0)),
371 One(ref x0) => {
372 let remx = match viewr_node(middle) {
373 (_, None) =>
374 left.into(),
375 (remy, Some(y)) =>
376 deep(left.clone(), remy, y.into())
377 };
378 (remx, Some(x0))
379 }
380 }
381 }
382}
383
384pub fn pop_back<T,M>(tree: &Lazy<FingerTree<T,M>>) -> Lazy<FingerTree<T,M>>
385 where T: Measure<M> + 'static,
386 M: Add<Output=M> + Zero + Copy + 'static
387{
388 match viewr_node(tree) {
389 (rem,_) => rem,
390 }
391}
392
393pub fn lookup<T,M,P>(pred: P, i: M, tree: &Lazy<FingerTree<T,M>>) -> (&T,M)
394 where T: Measure<M> + 'static,
395 M: Add<Output=M> + Zero + Copy + 'static,
396 P: Fn(M) -> bool
397{
398 match **tree {
399 Empty => panic!("lookup in empty tree"),
400 Single(ref node) => node::lookup(pred, i, node),
401 Deep(_, ref left, ref middle, ref right) => {
402 let i1 = i + left.measure();
403 if pred(i1) {
404 return digit::lookup(pred, i, left)
405 }
406 let i2 = i1 + middle.measure();
407 if pred(i2) {
408 lookup(pred, i1, middle)
409 } else {
410 digit::lookup(pred, i2, right)
411 }
412 }
413 }
414}
415
416pub fn adjust<T,M,P,F>(func: F, pred: P, i: M, tree: &Lazy<FingerTree<T,M>>) -> Lazy<FingerTree<T,M>>
417 where T: Measure<M> + 'static,
418 M: Add<Output=M> + Zero + Copy + 'static,
419 P: Fn(M) -> bool,
420 F: FnOnce(&T) -> T
421{
422 match **tree {
423 Empty => tree.clone(),
424 Single(ref node) =>
425 single(node::adjust(func, pred, i, node)),
426 Deep(_, ref left, ref middle, ref right) => {
427 let i1 = i + left.measure();
428 if pred(i1) {
429 return deep(digit::adjust(func, pred, i, left), middle.clone(), right.clone())
430 }
431 let i2 = i1 + middle.measure();
432 if pred(i2) {
433 deep(left.clone(), adjust(func, pred, i1, middle), right.clone())
434 } else {
435 deep(left.clone(), middle.clone(), digit::adjust(func, pred, i2, right))
436 }
437 }
438 }
439}
440
441fn deep_left<T,M>(left: Option<Digit<T,M>>, middle: Lazy<FingerTree<T,M>>, right: Digit<T,M>)
442 -> Lazy<FingerTree<T,M>>
443 where T: Measure<M> + 'static,
444 M: Add<Output=M> + Zero + Copy + 'static
445{
446 match left {
447 Some(left) => deep(left, middle, right),
448 None => {
449 match viewl_node(&middle) {
450 (None,_) => right.into(),
451 (Some(node), rem) =>
452 deep(node.into(), rem, right.clone())
453 }
454 }
455 }
456}
457
458fn deep_right<T,M>(left: Digit<T,M>, middle: Lazy<FingerTree<T,M>>, right: Option<Digit<T,M>>)
459 -> Lazy<FingerTree<T,M>>
460 where T: Measure<M> + 'static,
461 M: Add<Output=M> + Zero + Copy + 'static
462{
463 match right {
464 Some(right) => deep(left, middle, right),
465 None => {
466 match viewr_node(&middle) {
467 (_, None) => left.into(),
468 (rem, Some(node)) =>
469 deep(left.clone(), rem, node.into())
470 }
471 }
472 }
473}
474
475pub fn split<'a,T,M,P>(pred: &P, i: M, tree: &'a FingerTree<T,M>)
476 -> (Lazy<FingerTree<T,M>>,&'a Lazy<Node<T,M>>,Lazy<FingerTree<T,M>>)
477 where T: Measure<M> + 'static,
478 M: Add<Output=M> + Zero + Copy + 'static,
479 P: Fn(M) -> bool
480{
481 match *tree {
482 Empty => panic!("split in empty tree"),
483 Single(ref node) => {
484 (empty(), node, empty())
485 },
490 Deep(_, ref left, ref middle, ref right) => {
491 let i1 = i + left.measure();
492 if pred(i1) {
493 let (before,x,after) = digit::split_once(pred, i, left);
494 let before:Lazy<FingerTree<T,M>> = before.into();
495 let after = deep_left(after, middle.clone(), right.clone());
496 return (before, x, after)
497 }
498 let i2 = i1 + middle.measure();
499 if pred(i2) {
500 let (before,node,after) = split(pred, i1, middle);
501 let i_node = i1 + before.measure();
502 let (node_before, x, node_after) = node::split_once(pred, i_node, node);
503 let before = deep_right(left.clone(), before, node_before);
504 let after = deep_left(node_after, after, right.clone());
505 (before, x, after)
506 } else {
507 let (before,x,after) = digit::split_once(pred, i2, right);
508 let before = deep_right(left.clone(), middle.clone(), before);
509 let after:Lazy<FingerTree<T,M>> = after.into();
510 (before, x, after)
511 }
512 }
513 }
514}
515
516#[derive(Debug)]
517pub enum IterFrame<'a, T:'a, M:'a> {
518 NodeFrame(&'a Node<T,M>),
519 FingerTreeFrame(&'a FingerTree<T,M>),
520}
521use self::IterFrame::{NodeFrame, FingerTreeFrame};
522
523#[derive(Debug)]
524pub struct Iter<'a, T:'a, M:'a> {
525 stack: Vec<IterFrame<'a,T,M>>,
526 inner: node::Iter<'a, T, M>,
527}
528
529impl<'a, T, M> Iter<'a, T, M> {
530 fn new(node: &'a FingerTree<T,M>) -> Iter<'a, T, M> {
531 Iter {
532 stack: vec![FingerTreeFrame(node)],
533 inner: node::Iter::empty(),
534 }
535 }
536 fn push_digit(&mut self, digit: &'a Digit<T,M>) {
537 match *digit {
538 One(ref x0) =>
539 self.stack.push(NodeFrame(x0)),
540 Two(ref x0,ref x1) => {
541 self.stack.push(NodeFrame(x1)); self.stack.push(NodeFrame(x0));},
542 Three(ref x0,ref x1,ref x2) => {
543 self.stack.push(NodeFrame(x2)); self.stack.push(NodeFrame(x1));
544 self.stack.push(NodeFrame(x0));},
545 Four(ref x0,ref x1,ref x2,ref x3) => {
546 self.stack.push(NodeFrame(x3)); self.stack.push(NodeFrame(x2));
547 self.stack.push(NodeFrame(x1)); self.stack.push(NodeFrame(x0));},
548 }
549 }
550}
551
552impl<'a, T:'a, M> Iterator for Iter<'a,T,M> {
553 type Item = &'a T;
554 fn next(&mut self) -> Option<&'a T> {
555 if let v@Some(_) = self.inner.next() {
556 return v
557 }
558 loop {
559 match self.stack.pop() {
560 None => return None,
561 Some(NodeFrame(node)) => {
562 self.inner = node.iter();
563 return self.inner.next();
564 },
565 Some(FingerTreeFrame(tree)) => {
566 match *tree {
567 Empty => {},
568 Single(ref x) => {
569 self.inner = x.iter();
570 return self.inner.next();
571 }
572 Deep(_, ref left, ref middle, ref right) => {
573 self.push_digit(right);
574 self.stack.push(FingerTreeFrame(middle));
575 self.push_digit(left);
576 }
577 }
578 },
579 }
580 }
581 }
582}
583
584impl<'a, T, M> IntoIterator for &'a FingerTree<T,M> {
585 type Item = &'a T;
586
587 type IntoIter = Iter<'a, T, M>;
588
589 fn into_iter(self) -> Iter<'a,T,M> {
590 self.iter()
591 }
592}
593
594impl<T,M> Measure<M> for FingerTree<T,M>
595 where T: Measure<M>,
596 M: Add<Output=M> + Zero + Copy {
597 fn measure(&self) -> M {
598 match *self {
599 Empty => M::zero(),
600 Single(ref x) => x.measure(),
601 Deep(measure,_,_,_) => measure
602 }
603 }
604}
605
606#[cfg(test)]
607mod test {
608 use super::FingerTree;
609 use super::*;
610 use node::{leaf, node2, node3};
611 use digit::Digit::{One,Two};
612
613 #[derive(Clone)]
614 struct Item<T>(T);
615
616 impl<T> Measure<usize> for Item<T> {
617 fn measure(&self) -> usize {
618 1
619 }
620 }
621
622 #[test]
623 fn test_iter_empty() {
624 let tree: Lazy<FingerTree<Item<u32>, usize>> =
625 empty();
626 let result:Vec<u32> = tree.iter().map(|&Item(x)| x).collect();
627 let expected:Vec<u32> = vec![];
628 assert_eq!(result, expected);
629 }
630
631 #[test]
632 fn test_iter_single() {
633 let tree: Lazy<FingerTree<Item<u32>, usize>> =
634 single(leaf(Item(0)));
635 let result:Vec<u32> = tree.iter().map(|&Item(x)| x).collect();
636 let expected:Vec<u32> = vec![0];
637 assert_eq!(result, expected);
638 }
639
640 #[test]
641 fn test_iter_inner_empty() {
642 let tree: Lazy<FingerTree<Item<u32>, usize>> =
643 deep(
644 One(
645 node2(
646 leaf(Item(0)),
647 leaf(Item(1)))),
648 deep(
649 One(
650 node2(
651 node3(
652 leaf(Item(2)),
653 leaf(Item(3)),
654 leaf(Item(4))),
655 node2(
656 leaf(Item(5)),
657 leaf(Item(6))))),
658 empty(),
659 One(
660 node2(
661 node2(
662 leaf(Item(7)),
663 leaf(Item(8))),
664 node2(
665 leaf(Item(9)),
666 leaf(Item(10)))))),
667 Two(
668 node2(
669 leaf(Item(11)),
670 leaf(Item(12))),
671 node2(
672 leaf(Item(13)),
673 leaf(Item(14)))));
674 let result:Vec<u32> = tree.iter().map(|&Item(x)| x).collect();
675 let expected:Vec<u32> = (0..15).collect();
676 assert_eq!(result, expected);
677 }
678
679 #[test]
680 fn test_iter_inner_single() {
681 let tree: Lazy<FingerTree<Item<u32>, usize>> =
682 deep(
683 One(
684 node2(
685 leaf(Item(0)),
686 leaf(Item(1)))),
687 deep(
688 One(
689 node2(
690 node3(
691 leaf(Item(2)),
692 leaf(Item(3)),
693 leaf(Item(4))),
694 node2(
695 leaf(Item(5)),
696 leaf(Item(6))))),
697 single(
698 node2(
699 node2(
700 leaf(Item(7)),
701 leaf(Item(8))),
702 node2(
703 leaf(Item(9)),
704 leaf(Item(10))))),
705 One(
706 node2(
707 node2(
708 leaf(Item(11)),
709 leaf(Item(12))),
710 node2(
711 leaf(Item(13)),
712 leaf(Item(14)))))),
713 Two(
714 node2(
715 leaf(Item(15)),
716 leaf(Item(16))),
717 node2(
718 leaf(Item(17)),
719 leaf(Item(18)))));
720 let result:Vec<u32> = tree.iter().map(|&Item(x)| x).collect();
721 let expected:Vec<u32> = (0..19).collect();
722 assert_eq!(result, expected);
723 }
724}