honeycomb_core/cmap/dim3/orbits.rs
1//! Orbit implementation
2//!
3//! This module contains all code used to model orbits, a notion defined
4//! along the structure of combinatorial maps.
5
6use std::collections::{HashSet, VecDeque};
7
8use crate::cmap::{CMap3, DartIdType, NULL_DART_ID, OrbitPolicy, try_from_fn};
9use crate::geometry::CoordsFloat;
10use crate::stm::{StmClosureResult, Transaction};
11
12impl<T: CoordsFloat> CMap3<T> {
13 /// Generic orbit implementation.
14 ///
15 /// # Arguments
16 /// - `opolicy: OrbitPolicy` -- Policy used by the orbit for the BFS.
17 /// - `dart_id: DartIdentifier` -- Dart of which the structure will compute the orbit.
18 ///
19 /// # The search algorithm
20 ///
21 /// The search algorithm used to establish the list of dart included in the orbit is a
22 /// [Breadth-First Search algorithm][WIKIBFS]. This means that:
23 ///
24 /// - we look at the images of the current dart through all beta functions,
25 /// adding those to a queue, before moving on to the next dart.
26 /// - we apply the beta functions in their specified order; This guarantees a consistent and
27 /// predictable result.
28 ///
29 /// # Performance
30 ///
31 /// Currently, orbits use two dynamically allocated structures for computation: a `VecDeque`,
32 /// and a `HashSet`. There is a possibility to use static thread-local instances to avoid
33 /// ephemeral allocations, but [it would require a guard mechanism][PR].
34 ///
35 /// [WIKIBFS]: https://en.wikipedia.org/wiki/Breadth-first_search
36 /// [PR]: https://github.com/LIHPC-Computational-Geometry/honeycomb/pull/293
37 #[allow(clippy::needless_for_each, clippy::too_many_lines)]
38 #[rustfmt::skip]
39 pub fn orbit(
40 &self,
41 opolicy: OrbitPolicy,
42 dart_id: DartIdType,
43 ) -> impl Iterator<Item = DartIdType> {
44 let mut pending = VecDeque::new();
45 let mut marked: HashSet<DartIdType> = HashSet::new();
46 pending.push_back(dart_id);
47 marked.insert(NULL_DART_ID);
48 marked.insert(dart_id); // we're starting here, so we mark it beforehand
49
50 // FIXME: move the match block out of the iterator
51 std::iter::from_fn(move || {
52 if let Some(d) = pending.pop_front() {
53 let mut check = |d: DartIdType| {
54 if marked.insert(d) {
55 pending.push_back(d);
56 }
57 };
58 // compute the next images
59 match opolicy {
60 // B3oB2, B1oB3, B1oB2, B3oB0, B2oB0
61 OrbitPolicy::Vertex => {
62 [
63 self.beta::<1>(self.beta::<2>(d)), // b1(b2(d))
64 self.beta::<2>(self.beta::<0>(d)), // b2(b0(d))
65 self.beta::<1>(self.beta::<3>(d)), // b1(b3(d))
66 self.beta::<3>(self.beta::<0>(d)), // b3(b0(d))
67 self.beta::<2>(self.beta::<3>(d)), // b2(b3(d))
68 self.beta::<3>(self.beta::<2>(d)), // b3(b2(d))
69 ]
70 .into_iter()
71 .for_each(check);
72 }
73 // B3oB2, B1oB3, B1oB2
74 OrbitPolicy::VertexLinear => {
75 [
76 self.beta::<1>(self.beta::<2>(d)), // b1(b2(d))
77 self.beta::<1>(self.beta::<3>(d)), // b1(b3(d))
78 self.beta::<2>(self.beta::<3>(d)), // b2(b3(d))
79 ]
80 .into_iter()
81 .for_each(check);
82 }
83 // B2, B3
84 OrbitPolicy::Edge => {
85 [
86 self.beta::<2>(d),
87 self.beta::<3>(d),
88 ]
89 .into_iter()
90 .for_each(check);
91 }
92 // B1, B0, B3
93 OrbitPolicy::Face => {
94 [
95 self.beta::<1>(d),
96 self.beta::<0>(d),
97 self.beta::<3>(d),
98 ]
99 .into_iter()
100 .for_each(check);
101 }
102 // B1, B3
103 OrbitPolicy::FaceLinear => {
104 [
105 self.beta::<1>(d),
106 self.beta::<3>(d),
107 ]
108 .into_iter()
109 .for_each(check);
110 }
111 // B1, B0, B2
112 OrbitPolicy::Volume => {
113 [
114 self.beta::<1>(d),
115 self.beta::<0>(d),
116 self.beta::<2>(d),
117 ]
118 .into_iter()
119 .for_each(check);
120 }
121 // B1, B2
122 OrbitPolicy::VolumeLinear => {
123 [
124 self.beta::<1>(d),
125 self.beta::<2>(d),
126 ]
127 .into_iter()
128 .for_each(check);
129 }
130 OrbitPolicy::Custom(beta_slice) => {
131 for beta_id in beta_slice {
132 let im = self.beta_rt(*beta_id, d);
133 check(im);
134 }
135 }
136 }
137
138 return Some(d);
139 }
140 None // queue is empty, we're done
141 })
142 }
143
144 /// Generic orbit transactional implementation.
145 #[allow(clippy::needless_for_each, clippy::too_many_lines)]
146 #[rustfmt::skip]
147 pub fn orbit_tx(
148 &self,
149 t: &mut Transaction,
150 opolicy: OrbitPolicy,
151 dart_id: DartIdType,
152 ) -> impl Iterator<Item = StmClosureResult<DartIdType>> {
153 let mut pending = VecDeque::new();
154 let mut marked: HashSet<DartIdType> = HashSet::new();
155 pending.push_back(dart_id);
156 marked.insert(NULL_DART_ID);
157 marked.insert(dart_id); // we're starting here, so we mark it beforehand
158
159 // FIXME: move the match block out of the iterator
160 try_from_fn(move || {
161 if let Some(d) = pending.pop_front() {
162 let mut check = |d: DartIdType| {
163 if marked.insert(d) {
164 pending.push_back(d);
165 }
166 };
167 // compute the next images
168 match opolicy {
169 // B1oB2, B2oB0, B1oB3, B3oB0, B2oB3, B3oB2
170 OrbitPolicy::Vertex => {
171 let (b0, b2, b3) = (
172 self.beta_tx::<0>(t, d)?,
173 self.beta_tx::<2>(t, d)?,
174 self.beta_tx::<3>(t, d)?,
175 );
176 [
177 self.beta_tx::<1>(t, b2)?, // b1(b2(d))
178 self.beta_tx::<2>(t, b0)?, // b2(b0(d))
179 self.beta_tx::<1>(t, b3)?, // b1(b3(d))
180 self.beta_tx::<3>(t, b0)?, // b3(b0(d))
181 self.beta_tx::<2>(t, b3)?, // b2(b3(d))
182 self.beta_tx::<3>(t, b2)?, // b3(b2(d))
183 ]
184 .into_iter()
185 .for_each(check);
186 }
187 // B2oB3, B1oB3, B1oB2
188 OrbitPolicy::VertexLinear => {
189 let (b2, b3) =
190 (self.beta_tx::<2>(t, d)?, self.beta_tx::<3>(t, d)?);
191 [
192 self.beta_tx::<1>(t, b2)?, // b1(b2(d))
193 self.beta_tx::<1>(t, b3)?, // b1(b3(d))
194 self.beta_tx::<2>(t, b3)?, // b2(b3(d))
195 ]
196 .into_iter()
197 .for_each(check);
198 }
199 // B2, B3
200 OrbitPolicy::Edge => {
201 [self.beta_tx::<2>(t, d)?, self.beta_tx::<3>(t, d)?]
202 .into_iter()
203 .for_each(check);
204 }
205 // B1, B0, B3
206 OrbitPolicy::Face => {
207 [
208 self.beta_tx::<1>(t, d)?,
209 self.beta_tx::<0>(t, d)?,
210 self.beta_tx::<3>(t, d)?,
211 ]
212 .into_iter()
213 .for_each(check);
214 }
215 // B1, B3
216 OrbitPolicy::FaceLinear => {
217 [
218 self.beta_tx::<1>(t, d)?,
219 self.beta_tx::<3>(t, d)?,
220 ]
221 .into_iter()
222 .for_each(check);
223 }
224 // B1, B0, B2
225 OrbitPolicy::Volume => {
226 [
227 self.beta_tx::<1>(t, d)?,
228 self.beta_tx::<0>(t, d)?,
229 self.beta_tx::<2>(t, d)?,
230 ]
231 .into_iter()
232 .for_each(check);
233 }
234 // B1, B2
235 OrbitPolicy::VolumeLinear => {
236 [self.beta_tx::<1>(t, d)?, self.beta_tx::<2>(t, d)?]
237 .into_iter()
238 .for_each(check);
239 }
240 OrbitPolicy::Custom(beta_slice) => {
241 for beta_id in beta_slice {
242 let im = self.beta_rt_tx(t, *beta_id, d)?;
243 check(im);
244 }
245 }
246 }
247
248 return Ok(Some(d));
249 }
250 Ok(None) // queue is empty, we're done
251 })
252 }
253
254 /// Return the orbit defined by a dart and its `I`-cell.
255 ///
256 /// # Usage
257 ///
258 /// The returned item can be iterated upon to retrieve all dart members of the cell. Note that
259 /// **the dart passed as an argument is included as the first element of the returned orbit**.
260 ///
261 /// # Panics
262 ///
263 /// The method will panic if *I* is not 0, 1, 2, or 3.
264 #[must_use = "unused return value"]
265 pub fn i_cell<const I: u8>(&self, dart_id: DartIdType) -> impl Iterator<Item = DartIdType> {
266 assert!(I < 4);
267 match I {
268 0 => self.orbit(OrbitPolicy::Vertex, dart_id),
269 1 => self.orbit(OrbitPolicy::Edge, dart_id),
270 2 => self.orbit(OrbitPolicy::Face, dart_id),
271 3 => self.orbit(OrbitPolicy::Volume, dart_id),
272 _ => unreachable!(),
273 }
274 }
275}