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

honeycomb_core/cmap/dim2/
structure.rs
