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
|
use crate::*;
pub(crate) struct DepthSearchIterator<'tok, 'brand, 'arena, V> {
token: &'tok GhostToken<'brand>,
seen_vertices: Option<HashMap<usize, ptr!(Vertex)>>,
seen_edges: HashMap<usize, ptr!(Edge)>,
seen_faces: HashMap<usize, ptr!(Face)>,
edge_stack: Vec<ptr!(Edge)>,
face_stack: Vec<ptr!(Face)>,
}
impl<'tok, 'brand, 'arena, V> DepthSearchIterator<'tok, 'brand, 'arena, V> {
pub(crate) fn new(
edge: ptr!(Edge),
collect_vertices: bool,
token: &'tok impl ReflAsRef<GhostToken<'brand>>,
) -> Self {
Self {
token: token.as_ref(),
seen_vertices: collect_vertices.then(|| HashMap::new()),
seen_edges: HashMap::from([(edge.id(token), edge)]),
seen_faces: HashMap::new(),
edge_stack: Vec::from([edge]),
face_stack: Vec::new(),
}
}
fn add_edge(&mut self, edge: ptr!(Edge)) {
if self.seen_edges.insert(edge.id(self.token), edge).is_none() {
self.edge_stack.push(edge);
}
}
pub(crate) fn collect_seen(
edge: ptr!(Edge),
token: &'tok impl ReflAsRef<GhostToken<'brand>>,
) -> (
HashMap<usize, ptr!(Vertex)>,
HashMap<usize, ptr!(Edge)>,
HashMap<usize, ptr!(Face)>,
)
where
'brand: 'tok,
{
let mut x = Self::new(edge, true, token);
for _ in &mut x {}
(x.seen_vertices.unwrap(), x.seen_edges, x.seen_faces)
}
}
impl<'tok, 'brand, 'arena, V> Iterator for DepthSearchIterator<'tok, 'brand, 'arena, V> {
type Item = ptr!(Edge);
fn next(&mut self) -> Option<Self::Item> {
let Some(edge) = self.edge_stack.pop() else {
let face = self.face_stack.pop()?;
for loop_ in std::iter::once(face.lens(self.token).outer_loop())
.chain(face.iter_inner_loops(self.token))
{
self.add_edge(loop_.half_edges().edge().item);
}
return self.next();
};
for h in edge.half_edges(self.token) {
let face = h.loop_(self.token).face(self.token);
if self.seen_faces.insert(face.id(self.token), face).is_none() {
self.face_stack.push(face);
}
let origin = h.origin(self.token);
if let Some(seen_vertices) = self.seen_vertices.as_mut() {
seen_vertices.insert(origin.id(self.token), origin);
}
self.add_edge(h.next(self.token).edge(self.token));
}
Some(edge)
}
}
|
