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

honeycomb_core/cmap/dim2/
structure.rs
