1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
use super::*;
use std::iter::{IntoIterator, Iterator};
use std::mem;
use bonzai::*;
impl<'t, T> IntoIterator for &'t MTree<T> {
type Item = &'t T;
type IntoIter = Iter<'t, T>;
fn into_iter(self) -> Iter<'t, T> {
Iter::new(self.traverse_read_root())
}
}
pub struct Iter<'t, T> {
trav: Option<TreeReadTraverser<'t, Octant<T>, [ChildId; 8]>>
}
impl<'t, T> Iter<'t, T> {
fn new(trav: Option<TreeReadTraverser<'t, Octant<T>, [ChildId; 8]>>) -> Self {
match trav {
Some(trav) => {
Self::seek_bottom_left(&trav);
Iter { trav: Some(trav) }
},
None => Iter { trav: None }
}
}
fn seek_bottom_left(trav: &TreeReadTraverser<'t, Octant<T>, [ChildId; 8]>) {
'seek: loop {
for b in 0..8 {
if trav.seek_child(b).unwrap().is_ok() {
continue 'seek;
}
}
break 'seek;
}
}
}
impl<'t, T> Iterator for Iter<'t, T> {
type Item = &'t T;
fn next(&mut self) -> Option<&'t T> {
match self.trav {
None => None,
Some(ref mut trav) => {
// capture the current element
let curr = match trav.elem() {
&Octant::Leaf {
ref elem,
..
} => elem,
&Octant::Branch { .. } => unreachable!(),
};
// move up until we can move down into the next branch index
'up: loop {
match trav.this_branch_index() {
Ok(this_branch) =>{
trav.seek_parent().unwrap();
for next_branch in this_branch + 1..8 {
// if we can seek down to the side
if trav.seek_child(next_branch).unwrap().is_ok() {
// then seek bottom left and break out
Self::seek_bottom_left(trav);
assert!(match trav.elem() {
&Octant::Leaf { .. } => true,
&Octant::Branch { .. } => false,
});
break 'up;
}
}
// if we can't seek down to the side, then we
// only stay here if we're a leaf
match trav.elem() {
&Octant::Leaf { .. } => {
break 'up;
},
&Octant::Branch { .. } => {
continue 'up;
},
};
},
Err(_) => {
// however, if we've hit the top, that means we're done iterating
mem::drop(trav);
self.trav = None;
break 'up;
}
}
};
Some(curr)
}
}
}
}