honeycomb_core/cmap/dim2/structure.rs
1//! Main definitions
2//!
3//! This module contains the main structure definition ([`CMap2`]) as well as its constructor
4//! implementation.
5
6#[cfg(feature = "par-internals")]
7use rayon::prelude::*;
8
9use crate::attributes::{AttrSparseVec, AttrStorageManager, UnknownAttributeStorage};
10use crate::cmap::{
11 DartIdType, DartReleaseError, DartReservationError,
12 components::{betas::BetaFunctions, unused::UnusedDarts},
13};
14use crate::geometry::{CoordsFloat, Vertex2};
15use crate::stm::{
16 StmClosureResult, Transaction, TransactionClosureResult, abort, atomically_with_err,
17};
18
19use super::CMAP2_BETA;
20
21/// # 2D combinatorial map implementation
22///
23/// Information regarding maps can be found in the [user guide][UG].
24/// This documentation focuses on the implementation and its API.
25///
26/// [UG]: https://lihpc-computational-geometry.github.io/honeycomb/user-guide/definitions/cmaps
27///
28/// Notes on implementation:
29/// - We encode *β<sub>0</sub>* as the inverse function of *β<sub>1</sub>*. This is extremely
30/// useful (read *required*) to implement correct and efficient i-cell computation. Additionally,
31/// while *β<sub>0</sub>* can be accessed using the [`beta`][Self::beta] method, we do not define
32/// the 0-sew / 0-unsew operations.
33/// - We chose a boundary-less representation of meshes (i.e. darts on the boundary are 2-free).
34/// - The null dart will always be encoded as `0`.
35///
36/// ## Generics
37///
38/// - `T: CoordsFloat` -- Generic FP type for coordinates representation
39///
40/// ## Example
41///
42/// The following code corresponds to this flow of operations:
43///
44/// 
45///
46/// Note that:
47/// - we create the map using its builder structure: [`CMapBuilder`][crate::cmap::CMapBuilder]
48/// - we insert a few assertions to demonstrate the progressive changes applied to the structure
49/// - even though the faces are represented in the figure, they are not stored in the structure
50/// - we use a lot of methods with the `force_` prefix; these are convenience methods when
51/// synchronization isn't needed
52///
53/// ```
54/// # fn main() {
55/// use honeycomb_core::{
56/// cmap::{CMap2, CMapBuilder, OrbitPolicy},
57/// geometry::Vertex2
58/// };
59///
60/// // build a triangle (A)
61/// let mut map: CMap2<f64> = CMapBuilder::<2>::from_n_darts(3).build().unwrap(); // three darts
62/// map.force_link::<1>(1, 2); // beta1(1) = 2 & beta0(2) = 1
63/// map.force_link::<1>(2, 3); // beta1(2) = 3 & beta0(3) = 2
64/// map.force_link::<1>(3, 1); // beta1(3) = 1 & beta0(1) = 3
65/// map.force_write_vertex(1, (0.0, 0.0));
66/// map.force_write_vertex(2, (1.0, 0.0));
67/// map.force_write_vertex(3, (0.0, 1.0));
68///
69/// // we can go through the face using an orbit
70/// {
71/// let mut face = map.orbit(OrbitPolicy::Face, 1);
72/// assert_eq!(face.next(), Some(1));
73/// assert_eq!(face.next(), Some(2));
74/// assert_eq!(face.next(), Some(3));
75/// assert_eq!(face.next(), None);
76/// }
77///
78/// // build a second triangle (B)
79/// let first_added_dart_id = map.allocate_used_darts(3);
80/// assert_eq!(first_added_dart_id, 4);
81/// map.force_link::<1>(4, 5);
82/// map.force_link::<1>(5, 6);
83/// map.force_link::<1>(6, 4);
84/// map.force_write_vertex(4, (0.0, 2.0));
85/// map.force_write_vertex(5, (2.0, 0.0));
86/// map.force_write_vertex(6, (1.0, 1.0));
87///
88/// // there should be two faces now
89/// let faces: Vec<_> = map.iter_faces().collect();
90/// assert_eq!(&faces, &[1, 4]);
91///
92/// // sew both triangles (C)
93/// map.force_sew::<2>(2, 4);
94///
95/// // there are 5 edges now, making up a square & its diagonal
96/// let edges: Vec<_> = map.iter_edges().collect();
97/// assert_eq!(&edges, &[1, 2, 3, 5, 6]);
98///
99/// // adjust bottom-right & top-left vertex position (D)
100/// assert_eq!(
101/// map.force_write_vertex(2, Vertex2::from((1.0, 0.0))),
102/// Some(Vertex2(1.5, 0.0)) // `write` act as a `replace`
103/// );
104/// assert_eq!(
105/// map.force_write_vertex(3, Vertex2::from((0.0, 1.0))),
106/// Some(Vertex2(0.0, 1.5)) // these values were the average of sewn vertices
107/// );
108///
109/// // separate the diagonal from the rest (E)
110/// map.force_unsew::<1>(1);
111/// map.force_unsew::<1>(2);
112/// map.force_unsew::<1>(6);
113/// map.force_unsew::<1>(4);
114/// // break up & remove the diagonal
115/// map.force_unsew::<2>(2); // this makes dart 2 and 4 free
116/// map.release_dart(2);
117/// map.release_dart(4);
118/// // sew the square back up
119/// map.force_sew::<1>(1, 5);
120/// map.force_sew::<1>(6, 3);
121///
122/// // there's only the square face left
123/// let faces: Vec<_> = map.iter_faces().collect();
124/// assert_eq!(&faces, &[1]);
125/// // we can check the vertices
126/// let vertices = map.iter_vertices();
127/// let mut value_iterator = vertices.map(|vertex_id| map.force_read_vertex(vertex_id).unwrap());
128/// assert_eq!(value_iterator.next(), Some(Vertex2::from((0.0, 0.0)))); // vertex ID 1
129/// assert_eq!(value_iterator.next(), Some(Vertex2::from((0.0, 1.0)))); // vertex ID 3
130/// assert_eq!(value_iterator.next(), Some(Vertex2::from((1.0, 0.0)))); // vertex ID 5
131/// assert_eq!(value_iterator.next(), Some(Vertex2::from((1.0, 1.0)))); // vertex ID 6
132/// # }
133/// ```
134pub struct CMap2<T: CoordsFloat> {
135 /// List of vertices making up the represented mesh
136 pub(super) attributes: AttrStorageManager,
137 /// List of vertices making up the represented mesh
138 pub(super) vertices: AttrSparseVec<Vertex2<T>>,
139 /// List of free darts identifiers, i.e. empty spots
140 /// in the current dart list
141 pub(super) unused_darts: UnusedDarts,
142 /// Array representation of the beta functions
143 pub(super) betas: BetaFunctions<CMAP2_BETA>,
144 /// Current number of darts
145 pub(super) n_darts: usize,
146}
147
148unsafe impl<T: CoordsFloat> Send for CMap2<T> {}
149unsafe impl<T: CoordsFloat> Sync for CMap2<T> {}
150
151#[doc(hidden)]
152/// **Constructor convenience implementations**
153impl<T: CoordsFloat> CMap2<T> {
154 /// Creates a new 2D combinatorial map.
155 #[allow(unused)]
156 #[must_use = "unused return value"]
157 pub(crate) fn new(n_darts: usize) -> Self {
158 Self {
159 attributes: AttrStorageManager::default(),
160 vertices: AttrSparseVec::new(n_darts + 1),
161 unused_darts: UnusedDarts::new(n_darts + 1),
162 betas: BetaFunctions::new(n_darts + 1),
163 n_darts: n_darts + 1,
164 }
165 }
166
167 /// Creates a new 2D combinatorial map with user-defined attributes
168 ///
169 /// We expect the passed storages to be defined but empty, i.e. attributes are known,
170 /// but no space has been used/ allocated yet.
171 #[must_use = "unused return value"]
172 pub(crate) fn new_with_undefined_attributes(
173 n_darts: usize,
174 mut attr_storage_manager: AttrStorageManager,
175 ) -> Self {
176 // extend all storages to the expected length: n_darts + 1 (for the null dart)
177 attr_storage_manager.extend_storages(n_darts + 1);
178 Self {
179 attributes: attr_storage_manager,
180 vertices: AttrSparseVec::new(n_darts + 1),
181 unused_darts: UnusedDarts::new(n_darts + 1),
182 betas: BetaFunctions::new(n_darts + 1),
183 n_darts: n_darts + 1,
184 }
185 }
186}
187
188/// **Dart-related methods**
189impl<T: CoordsFloat> CMap2<T> {
190 // --- read
191
192 /// Return the current number of darts.
193 #[must_use = "unused return value"]
194 pub fn n_darts(&self) -> usize {
195 self.n_darts
196 }
197
198 #[cfg(not(feature = "par-internals"))]
199 /// Return the current number of unused darts.
200 #[must_use = "unused return value"]
201 pub fn n_unused_darts(&self) -> usize {
202 self.unused_darts.iter().filter(|v| v.read_atomic()).count()
203 }
204
205 #[cfg(feature = "par-internals")]
206 /// Return the current number of unused darts.
207 #[must_use = "unused return value"]
208 pub fn n_unused_darts(&self) -> usize {
209 self.unused_darts
210 .par_iter()
211 .filter(|v| v.read_atomic())
212 .count()
213 }
214
215 /// Return whether a given dart is unused or not.
216 #[must_use = "unused return value"]
217 pub fn is_unused(&self, d: DartIdType) -> bool {
218 self.unused_darts[d].read_atomic()
219 }
220
221 /// Return whether a given dart is unused or not.
222 ///
223 /// # Errors
224 ///
225 /// This method is meant to be called in a context where the returned `Result` is used to
226 /// validate the transaction passed as argument. Errors should not be processed manually,
227 /// only processed via the `?` operator.
228 #[must_use = "unused return value"]
229 pub fn is_unused_tx(&self, t: &mut Transaction, d: DartIdType) -> StmClosureResult<bool> {
230 self.unused_darts[d].read(t)
231 }
232
233 // --- allocation
234
235 /// Add `n_darts` new free darts to the map.
236 ///
237 /// This is an internal helper function
238 fn allocate_darts_core(&mut self, n_darts: usize, unused: bool) -> DartIdType {
239 let new_id = self.n_darts as DartIdType;
240 self.n_darts += n_darts;
241 self.betas.extend(n_darts);
242 self.unused_darts.extend_with(n_darts, unused);
243 self.vertices.extend(n_darts);
244 self.attributes.extend_storages(n_darts);
245 new_id
246 }
247
248 /// Add `n_darts` new free darts to the map.
249 ///
250 /// Added darts are marked as used.
251 ///
252 /// # Return
253 ///
254 /// Return the ID of the first new dart. Other IDs are in the range `ID..ID+n_darts`.
255 pub fn allocate_used_darts(&mut self, n_darts: usize) -> DartIdType {
256 self.allocate_darts_core(n_darts, false)
257 }
258
259 /// Add `n_darts` new free darts to the map.
260 ///
261 /// Added dart are marked as unused.
262 ///
263 /// # Return
264 ///
265 /// Return the ID of the first new dart. Other IDs are in the range `ID..ID+n_darts`.
266 pub fn allocate_unused_darts(&mut self, n_darts: usize) -> DartIdType {
267 self.allocate_darts_core(n_darts, true)
268 }
269
270 // --- reservation / removal
271
272 #[allow(clippy::missing_errors_doc)]
273 /// Mark `n_darts` free darts as used and return them for usage.
274 ///
275 /// # Return / Errors
276 ///
277 /// This function returns a vector containing IDs of the darts marked as used. It will fail if
278 /// there are not enough unused darts to return; darts will then be left as unused.
279 pub fn reserve_darts(&self, n_darts: usize) -> Result<Vec<DartIdType>, DartReservationError> {
280 atomically_with_err(|t| self.reserve_darts_tx(t, n_darts))
281 }
282
283 #[allow(clippy::missing_errors_doc)]
284 /// Mark `n_darts` free darts as used and return them for usage.
285 ///
286 /// # Return / Errors
287 ///
288 /// This function returns a vector containing IDs of the darts marked as used. It will fail if
289 /// there are not enough unused darts to return; darts will then be left as unused. Returned
290 /// darts are searched from the first one.
291 ///
292 /// This method is meant to be called in a context where the returned `Result` is used to
293 /// validate the transaction passed as argument. Errors should not be processed manually,
294 /// only processed via the `?` operator.
295 pub fn reserve_darts_tx(
296 &self,
297 t: &mut Transaction,
298 n_darts: usize,
299 ) -> TransactionClosureResult<Vec<DartIdType>, DartReservationError> {
300 let mut res = Vec::with_capacity(n_darts);
301
302 for d in 1..self.n_darts() as DartIdType {
303 if self.is_unused_tx(t, d)? {
304 self.claim_dart_tx(t, d)?;
305 res.push(d);
306 if res.len() == n_darts {
307 return Ok(res);
308 }
309 }
310 }
311
312 abort(DartReservationError(n_darts))
313 }
314
315 #[allow(clippy::missing_errors_doc)]
316 /// Mark `n_darts` free darts as used and return them for usage.
317 ///
318 /// While `reserve_darts_tx` search for free darts from dart 1, this function takes as argument
319 /// a dart ID which serve as the starting point of the search. This is useful in parallel
320 /// contexts; multiple threads may use different offsets to reserve darts without competing
321 /// repeatedly to claim the same elements.
322 ///
323 /// # Return / Errors
324 ///
325 /// This function returns a vector containing IDs of the darts marked as used. It will fail if
326 /// there are not enough unused darts to return; darts will then be left as unused.
327 ///
328 /// This method is meant to be called in a context where the returned `Result` is used to
329 /// validate the transaction passed as argument. Errors should not be processed manually,
330 /// only processed via the `?` operator.
331 pub fn reserve_darts_from_tx(
332 &self,
333 t: &mut Transaction,
334 n_darts: usize,
335 from: DartIdType,
336 ) -> TransactionClosureResult<Vec<DartIdType>, DartReservationError> {
337 let mut res = Vec::with_capacity(n_darts);
338
339 for d in (from..self.n_darts() as DartIdType).chain(1..from) {
340 if self.is_unused_tx(t, d)? {
341 self.claim_dart_tx(t, d)?;
342 res.push(d);
343 if res.len() == n_darts {
344 return Ok(res);
345 }
346 }
347 }
348
349 abort(DartReservationError(n_darts))
350 }
351
352 /// Set a given dart as used.
353 ///
354 /// # Errors
355 ///
356 /// This method is meant to be called in a context where the returned `Result` is used to
357 /// validate the transaction passed as argument. Errors should not be processed manually,
358 /// only processed via the `?` operator.
359 pub fn claim_dart_tx(&self, t: &mut Transaction, dart_id: DartIdType) -> StmClosureResult<()> {
360 self.unused_darts[dart_id].write(t, false)
361 }
362
363 #[allow(clippy::missing_errors_doc)]
364 /// Mark a free dart from the map as unused.
365 ///
366 /// # Return / Errors
367 ///
368 /// This method return a boolean indicating whether the art was already unused or not. It will
369 /// fail if the dart is not free, i.e. if one of its beta images isn't null.
370 pub fn release_dart(&self, dart_id: DartIdType) -> Result<bool, DartReleaseError> {
371 atomically_with_err(|t| self.release_dart_tx(t, dart_id))
372 }
373
374 #[allow(clippy::missing_errors_doc)]
375 /// Mark a free dart from the map as unused.
376 ///
377 /// # Return / Errors
378 ///
379 /// This method return a boolean indicating whether the art was already unused or not. It will
380 /// fail if the dart is not free, i.e. if one of its beta images isn't null.
381 ///
382 /// This method is meant to be called in a context where the returned `Result` is used to
383 /// validate the transaction passed as argument. Errors should not be processed manually,
384 /// only processed via the `?` operator.
385 pub fn release_dart_tx(
386 &self,
387 t: &mut Transaction,
388 dart_id: DartIdType,
389 ) -> TransactionClosureResult<bool, DartReleaseError> {
390 if !self.is_free_tx(t, dart_id)? {
391 abort(DartReleaseError(dart_id))?;
392 }
393 self.attributes.clear_attribute_values(t, dart_id)?;
394 self.vertices.clear_slot(t, dart_id)?;
395 Ok(self.unused_darts[dart_id].replace(t, true)?) // Ok(_?) necessary for err type coercion
396 }
397}