honeycomb_core/cmap/dim2/basic_ops.rs
1//! Basic operations implementation
2//!
3//! This module contains code used to implement basic operations of combinatorial maps, such as
4//! (but not limited to):
5//!
6//! - Dart addition / insertion / removal
7//! - Beta function interfaces
8//! - i-cell computations
9
10use std::cell::RefCell;
11use std::collections::{HashSet, VecDeque};
12
13use rayon::prelude::*;
14
15use crate::cmap::{CMap2, DartIdType, EdgeIdType, FaceIdType, NULL_DART_ID, VertexIdType};
16use crate::geometry::CoordsFloat;
17use crate::stm::{StmClosureResult, Transaction, atomically};
18
19// use thread local hashset and queue for orbit traversal of ID comp.
20// not applied to orbit currently bc they are lazily onsumed, and therefore require dedicated
21// instances to be robust
22thread_local! {
23 static AUXILIARIES: RefCell<(VecDeque<DartIdType>, HashSet<DartIdType>)> = RefCell::new((VecDeque::with_capacity(10), HashSet::with_capacity(10)));
24}
25
26/// **Beta-related methods**
27impl<T: CoordsFloat> CMap2<T> {
28 // --- read
29
30 /// Return β<sub>`I`</sub>(`dart_id`).
31 ///
32 /// # Panics
33 ///
34 /// The method will panic if `I` is not 0, 1 or 2.
35 #[must_use = "unused return value"]
36 pub fn beta<const I: u8>(&self, dart_id: DartIdType) -> DartIdType {
37 assert!(I < 3);
38 self.betas[(I, dart_id)].read_atomic()
39 }
40
41 /// Return β<sub>`i`</sub>(`dart_id`).
42 ///
43 /// # Panics
44 ///
45 /// The method will panic if `i` is not 0, 1 or 2.
46 #[must_use = "unused return value"]
47 pub fn beta_rt(&self, i: u8, dart_id: DartIdType) -> DartIdType {
48 assert!(i < 3);
49 match i {
50 0 => self.beta::<0>(dart_id),
51 1 => self.beta::<1>(dart_id),
52 2 => self.beta::<2>(dart_id),
53 _ => unreachable!(),
54 }
55 }
56
57 /// Return β<sub>`I`</sub>(`dart_id`).
58 ///
59 /// # Errors
60 ///
61 /// This method is meant to be called in a context where the returned `Result` is used to
62 /// validate the transaction passed as argument. Errors should not be processed manually,
63 /// only processed via the `?` operator.
64 ///
65 /// # Panics
66 ///
67 /// The method will panic if `I` is not 0, 1 or 2.
68 pub fn beta_tx<const I: u8>(
69 &self,
70 t: &mut Transaction,
71 dart_id: DartIdType,
72 ) -> StmClosureResult<DartIdType> {
73 assert!(I < 3);
74 self.betas[(I, dart_id)].read(t)
75 }
76
77 /// Return β<sub>`i`</sub>(`dart_id`).
78 ///
79 /// # Errors
80 ///
81 /// This method is meant to be called in a context where the returned `Result` is used to
82 /// validate the transaction passed as argument. Errors should not be processed manually,
83 /// only processed via the `?` operator.
84 ///
85 /// # Panics
86 ///
87 /// The method will panic if `i` is not 0, 1 or 2.
88 pub fn beta_rt_tx(
89 &self,
90 t: &mut Transaction,
91 i: u8,
92 dart_id: DartIdType,
93 ) -> StmClosureResult<DartIdType> {
94 assert!(i < 3);
95 match i {
96 0 => self.beta_tx::<0>(t, dart_id),
97 1 => self.beta_tx::<1>(t, dart_id),
98 2 => self.beta_tx::<2>(t, dart_id),
99 _ => unreachable!(),
100 }
101 }
102
103 /// Check if a given dart is `I`-free.
104 ///
105 /// # Return
106 ///
107 /// Return a boolean indicating if the dart is `I`-free, i.e.:
108 /// - `true` if β<sub>`I`</sub>(`dart_id`) = `NULL_DART_ID`,
109 /// - `false` else.
110 ///
111 /// # Panics
112 ///
113 /// The function will panic if *I* is not 0, 1 or 2.
114 ///
115 #[must_use = "unused return value"]
116 pub fn is_i_free<const I: u8>(&self, dart_id: DartIdType) -> bool {
117 self.beta::<I>(dart_id) == NULL_DART_ID
118 }
119
120 /// Check if a given dart is `i`-free, for all `i`.
121 ///
122 /// # Return
123 ///
124 /// Return a boolean indicating if the dart is 0-free, 1-free **and** 2-free.
125 #[must_use = "unused return value"]
126 pub fn is_free(&self, dart_id: DartIdType) -> bool {
127 atomically(|t| self.is_free_tx(t, dart_id))
128 }
129
130 #[allow(clippy::missing_errors_doc)]
131 /// Check if a given dart is `i`-free, for all `i`.
132 ///
133 /// # Return / Errors
134 ///
135 /// Return a boolean indicating if the dart is 0-free, 1-free **and** 2-free.
136 ///
137 /// This method is meant to be called in a context where the returned `Result` is used to
138 /// validate the transaction passed as argument. Errors should not be processed manually,
139 /// only processed via the `?` operator.
140 #[must_use = "unused return value"]
141 pub fn is_free_tx(&self, t: &mut Transaction, dart_id: DartIdType) -> StmClosureResult<bool> {
142 Ok(self.beta_tx::<0>(t, dart_id)? == NULL_DART_ID
143 && self.beta_tx::<1>(t, dart_id)? == NULL_DART_ID
144 && self.beta_tx::<2>(t, dart_id)? == NULL_DART_ID)
145 }
146}
147
148/// **I-cell-related methods**
149impl<T: CoordsFloat> CMap2<T> {
150 /// Compute the ID of the vertex a given dart is part of.
151 ///
152 /// This corresponds to the minimum dart ID among darts composing the 0-cell orbit.
153 #[must_use = "unused return value"]
154 pub fn vertex_id(&self, dart_id: DartIdType) -> VertexIdType {
155 atomically(|t| self.vertex_id_tx(t, dart_id))
156 }
157
158 /// Compute the ID of the vertex a given dart is part of.
159 ///
160 /// This corresponds to the minimum dart ID among darts composing the 0-cell orbit.
161 ///
162 /// # Errors
163 ///
164 /// This method is meant to be called in a context where the returned `Result` is used to
165 /// validate the transaction passed as argument. Errors should not be processed manually,
166 /// only processed via the `?` operator.
167 pub fn vertex_id_tx(
168 &self,
169 t: &mut Transaction,
170 dart_id: DartIdType,
171 ) -> StmClosureResult<VertexIdType> {
172 AUXILIARIES.with(|cell| {
173 let (pending, marked) = &mut *cell.borrow_mut();
174 // clear from previous computations
175 pending.clear();
176 marked.clear();
177 // initialize
178 pending.push_back(dart_id);
179 marked.insert(NULL_DART_ID); // we don't want to include the null dart in the orbit
180 marked.insert(dart_id); // we're starting here, so we mark it beforehand
181
182 let mut min = dart_id;
183
184 while let Some(d) = pending.pop_front() {
185 // THIS CODE IS ONLY VALID IN 2D
186 let (b2d, b0d) = (self.beta_tx::<2>(t, d)?, self.beta_tx::<0>(t, d)?);
187 let image1 = self.beta_tx::<1>(t, b2d)?;
188 if marked.insert(image1) {
189 // if true, we did not see this dart yet
190 // i.e. we need to visit it later
191 min = min.min(image1);
192 pending.push_back(image1);
193 }
194 let image2 = self.beta_tx::<2>(t, b0d)?;
195 if marked.insert(image2) {
196 // if true, we did not see this dart yet
197 // i.e. we need to visit it later
198 min = min.min(image2);
199 pending.push_back(image2);
200 }
201 }
202
203 Ok(min)
204 })
205 }
206
207 /// Compute the ID of the edge a given dart is part of.
208 ///
209 /// This corresponds to the minimum dart ID among darts composing the 1-cell orbit.
210 #[must_use = "unused return value"]
211 pub fn edge_id(&self, dart_id: DartIdType) -> EdgeIdType {
212 atomically(|t| self.edge_id_tx(t, dart_id))
213 }
214
215 /// Compute the ID of the edge a given dart is part of.
216 ///
217 /// This corresponds to the minimum dart ID among darts composing the 1-cell orbit.
218 ///
219 /// # Errors
220 ///
221 /// This method is meant to be called in a context where the returned `Result` is used to
222 /// validate the transaction passed as argument. Errors should not be processed manually,
223 /// only processed via the `?` operator.
224 pub fn edge_id_tx(
225 &self,
226 t: &mut Transaction,
227 dart_id: DartIdType,
228 ) -> StmClosureResult<EdgeIdType> {
229 // optimizing this one bc I'm tired
230 let b2 = self.beta_tx::<2>(t, dart_id)?;
231 if b2 == NULL_DART_ID {
232 Ok(dart_id as EdgeIdType)
233 } else {
234 Ok(b2.min(dart_id) as EdgeIdType)
235 }
236 }
237
238 /// Compute the ID of the face a given dart is part of.
239 ///
240 /// This corresponds to the minimum dart ID among darts composing the 2-cell orbit.
241 #[must_use = "unused return value"]
242 pub fn face_id(&self, dart_id: DartIdType) -> FaceIdType {
243 atomically(|t| self.face_id_tx(t, dart_id))
244 }
245
246 /// Compute the ID of the face a given dart is part of.
247 ///
248 /// This corresponds to the minimum dart ID among darts composing the 2-cell orbit.
249 ///
250 /// # Errors
251 ///
252 /// This method is meant to be called in a context where the returned `Result` is used to
253 /// validate the transaction passed as argument. Errors should not be processed manually,
254 /// only processed via the `?` operator.
255 pub fn face_id_tx(
256 &self,
257 t: &mut Transaction,
258 dart_id: DartIdType,
259 ) -> StmClosureResult<FaceIdType> {
260 AUXILIARIES.with(|cell| {
261 let (pending, marked) = &mut *cell.borrow_mut();
262 // clear from previous computations
263 pending.clear();
264 marked.clear();
265 // initialize
266 pending.push_back(dart_id);
267 marked.insert(NULL_DART_ID); // we don't want to include the null dart in the orbit
268 marked.insert(dart_id); // we're starting here, so we mark it beforehand
269
270 let mut min = dart_id;
271
272 while let Some(d) = pending.pop_front() {
273 // THIS CODE IS ONLY VALID IN 2D
274 let image1 = self.beta_tx::<1>(t, d)?;
275 if marked.insert(image1) {
276 // if true, we did not see this dart yet
277 // i.e. we need to visit it later
278 min = min.min(image1);
279 pending.push_back(image1);
280 }
281 let image2 = self.beta_tx::<0>(t, d)?;
282 if marked.insert(image2) {
283 // if true, we did not see this dart yet
284 // i.e. we need to visit it later
285 min = min.min(image2);
286 pending.push_back(image2);
287 }
288 }
289
290 Ok(min)
291 })
292 }
293
294 /// Return an iterator over IDs of all the map's vertices.
295 #[must_use = "unused return value"]
296 pub fn iter_vertices(&self) -> impl Iterator<Item = VertexIdType> + '_ {
297 (1..self.n_darts() as DartIdType)
298 .zip(self.unused_darts.iter().skip(1))
299 .filter_map(
300 |(d, unused)| {
301 if unused.read_atomic() { None } else { Some(d) }
302 },
303 )
304 .filter_map(|d| {
305 let vid = self.vertex_id(d);
306 if d == vid { Some(vid) } else { None }
307 })
308 }
309
310 /// Return an iterator over IDs of all the map's edges.
311 #[must_use = "unused return value"]
312 pub fn iter_edges(&self) -> impl Iterator<Item = EdgeIdType> + '_ {
313 (1..self.n_darts() as DartIdType)
314 .zip(self.unused_darts.iter().skip(1))
315 .filter_map(
316 |(d, unused)| {
317 if unused.read_atomic() { None } else { Some(d) }
318 },
319 )
320 .filter_map(|d| {
321 let eid = self.edge_id(d);
322 if d == eid { Some(eid) } else { None }
323 })
324 }
325
326 /// Return an iterator over IDs of all the map's faces.
327 #[must_use = "unused return value"]
328 pub fn iter_faces(&self) -> impl Iterator<Item = FaceIdType> + '_ {
329 (1..self.n_darts() as DartIdType)
330 .zip(self.unused_darts.iter().skip(1))
331 .filter_map(
332 |(d, unused)| {
333 if unused.read_atomic() { None } else { Some(d) }
334 },
335 )
336 .filter_map(|d| {
337 let fid = self.face_id(d);
338 if d == fid { Some(fid) } else { None }
339 })
340 }
341
342 /// Return an iterator over IDs of all the map's vertices.
343 #[must_use = "unused return value"]
344 pub fn par_iter_vertices(&self) -> impl ParallelIterator<Item = VertexIdType> + '_ {
345 (1..self.n_darts() as DartIdType)
346 .into_par_iter()
347 .filter_map(|d| if self.is_unused(d) { None } else { Some(d) })
348 .filter_map(|d| {
349 let vid = self.vertex_id(d);
350 if d == vid { Some(vid) } else { None }
351 })
352 }
353
354 /// Return an iterator over IDs of all the map's edges.
355 #[must_use = "unused return value"]
356 pub fn par_iter_edges(&self) -> impl ParallelIterator<Item = EdgeIdType> + '_ {
357 (1..self.n_darts() as DartIdType)
358 .into_par_iter()
359 .filter_map(|d| if self.is_unused(d) { None } else { Some(d) })
360 .filter_map(|d| {
361 let eid = self.edge_id(d);
362 if d == eid { Some(eid) } else { None }
363 })
364 }
365
366 /// Return an iterator over IDs of all the map's faces.
367 #[must_use = "unused return value"]
368 pub fn par_iter_faces(&self) -> impl ParallelIterator<Item = FaceIdType> + '_ {
369 (1..self.n_darts() as DartIdType)
370 .into_par_iter()
371 .filter_map(|d| if self.is_unused(d) { None } else { Some(d) })
372 .filter_map(|d| {
373 let fid = self.face_id(d);
374 if d == fid { Some(fid) } else { None }
375 })
376 }
377}