honeycomb_core/cmap/dim3/
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::collections::{HashSet, VecDeque};
11
12use crate::attributes::UnknownAttributeStorage;
13use crate::cmap::{
14    CMap3, DartIdType, EdgeIdType, FaceIdType, Orbit3, OrbitPolicy, VertexIdType, VolumeIdType,
15    NULL_DART_ID,
16};
17use crate::geometry::CoordsFloat;
18use crate::stm::{atomically, StmClosureResult, StmError, Transaction};
19
20/// **Dart-related methods**
21impl<T: CoordsFloat> CMap3<T> {
22    // --- read
23
24    /// Return the current number of darts.
25    #[must_use = "unused return value"]
26    pub fn n_darts(&self) -> usize {
27        self.unused_darts.len()
28    }
29
30    /// Return the current number of unused darts.
31    #[must_use = "unused return value"]
32    pub fn n_unused_darts(&self) -> usize {
33        self.unused_darts.iter().filter(|v| v.read_atomic()).count()
34    }
35
36    // --- edit
37
38    /// Add a new free dart to the map.
39    ///
40    /// # Return
41    ///
42    /// Returns the ID of the new dart.
43    pub fn add_free_dart(&mut self) -> DartIdType {
44        let new_id = self.n_darts() as DartIdType;
45        self.betas.extend(1);
46        self.unused_darts.extend(1);
47        self.vertices.extend(1);
48        self.attributes.extend_storages(1);
49        new_id
50    }
51
52    /// Add `n_darts` new free darts to the map.
53    ///
54    /// # Return
55    ///
56    /// Returns the ID of the first new dart. Other IDs are in the range `ID..ID+n_darts`.
57    pub fn add_free_darts(&mut self, n_darts: usize) -> DartIdType {
58        let new_id = self.n_darts() as DartIdType;
59        self.betas.extend(n_darts);
60        self.unused_darts.extend(n_darts);
61        self.vertices.extend(n_darts);
62        self.attributes.extend_storages(n_darts);
63        new_id
64    }
65
66    /// Insert a new free dart into the map.
67    ///
68    /// This method attempts to reuse an unused dart slot if available; otherwise, it adds a new one.
69    ///
70    /// # Return
71    ///
72    /// Returns the ID of the inserted dart.
73    pub fn insert_free_dart(&mut self) -> DartIdType {
74        if let Some((new_id, _)) = self
75            .unused_darts
76            .iter()
77            .enumerate()
78            .find(|(_, u)| u.read_atomic())
79        {
80            atomically(|trans| self.unused_darts[new_id as DartIdType].write(trans, false));
81            new_id as DartIdType
82        } else {
83            self.add_free_dart()
84        }
85    }
86
87    /// Remove a free dart from the map.
88    ///
89    /// The removed dart identifier is added to the list of free darts. This way of proceeding is
90    /// necessary as the structure relies on dart indexing for encoding data, making reordering of
91    /// any sort extremely costly.
92    ///
93    /// # Arguments
94    ///
95    /// - `dart_id: DartIdType` -- Identifier of the dart to remove.
96    ///
97    /// # Panics
98    ///
99    /// This method may panic if:
100    /// - the dart is not free for all *i*,
101    /// - the dart is already marked as unused.
102    pub fn remove_free_dart(&mut self, dart_id: DartIdType) {
103        atomically(|trans| {
104            assert!(self.is_free(dart_id)); // all beta images are 0
105            assert!(!self.unused_darts[dart_id as DartIdType].replace(trans, true)?);
106            Ok(())
107        });
108    }
109}
110
111/// **Beta-related methods**
112impl<T: CoordsFloat> CMap3<T> {
113    // --- read
114
115    /// Return β<sub>`I`</sub>(`dart_id`).
116    ///
117    /// # Errors
118    ///
119    /// This method is meant to be called in a context where the returned `Result` is used to
120    /// validate the transaction passed as argument. Errors should not be processed manually,
121    /// only processed via the `?` operator.
122    ///
123    /// # Panics
124    ///
125    /// The method will panic if `I` is not 0, 1, 2, or 3.
126    pub fn beta_transac<const I: u8>(
127        &self,
128        trans: &mut Transaction,
129        dart_id: DartIdType,
130    ) -> StmClosureResult<DartIdType> {
131        assert!(I < 4);
132        self.betas[(I, dart_id)].read(trans)
133    }
134
135    /// Return β<sub>`i`</sub>(`dart_id`).
136    ///
137    /// # Errors
138    ///
139    /// This method is meant to be called in a context where the returned `Result` is used to
140    /// validate the transaction passed as argument. Errors should not be processed manually,
141    /// only processed via the `?` operator.
142    ///
143    /// # Panics
144    ///
145    /// The method will panic if `i` is not 0, 1, 2, or 3.
146    pub fn beta_rt_transac(
147        &self,
148        trans: &mut Transaction,
149        i: u8,
150        dart_id: DartIdType,
151    ) -> StmClosureResult<DartIdType> {
152        assert!(i < 4);
153        match i {
154            0 => self.beta_transac::<0>(trans, dart_id),
155            1 => self.beta_transac::<1>(trans, dart_id),
156            2 => self.beta_transac::<2>(trans, dart_id),
157            3 => self.beta_transac::<3>(trans, dart_id),
158            _ => unreachable!(),
159        }
160    }
161
162    /// Return β<sub>`I`</sub>(`dart_id`).
163    ///
164    /// # Panics
165    ///
166    /// The method will panic if `I` is not 0, 1, 2, or 3.
167    #[must_use = "unused return value"]
168    pub fn beta<const I: u8>(&self, dart_id: DartIdType) -> DartIdType {
169        assert!(I < 4);
170        self.betas[(I, dart_id)].read_atomic()
171    }
172
173    /// Return β<sub>`i`</sub>(`dart_id`).
174    ///
175    /// # Panics
176    ///
177    /// The method will panic if `i` is not 0, 1, 2, or 3.
178    #[must_use = "unused return value"]
179    pub fn beta_rt(&self, i: u8, dart_id: DartIdType) -> DartIdType {
180        assert!(i < 4);
181        match i {
182            0 => self.beta::<0>(dart_id),
183            1 => self.beta::<1>(dart_id),
184            2 => self.beta::<2>(dart_id),
185            3 => self.beta::<3>(dart_id),
186            _ => unreachable!(),
187        }
188    }
189
190    /// Check if a given dart is `I`-free.
191    ///
192    /// # Return
193    ///
194    /// The method returns:
195    /// - `true` if β<sub>`I`</sub>(`dart_id`) = `NULL_DART_ID`,
196    /// - `false` otherwise.
197    ///
198    /// # Panics
199    ///
200    /// The function will panic if *I* is not 0, 1, 2, or 3.
201    #[must_use = "unused return value"]
202    pub fn is_i_free<const I: u8>(&self, dart_id: DartIdType) -> bool {
203        self.beta::<I>(dart_id) == NULL_DART_ID
204    }
205
206    /// Check if a given dart is free for all `i`.
207    ///
208    /// # Return
209    ///
210    /// Returns `true` if the dart is 0-free, 1-free, 2-free, **and** 3-free.
211    #[must_use = "unused return value"]
212    pub fn is_free(&self, dart_id: DartIdType) -> bool {
213        self.beta::<0>(dart_id) == NULL_DART_ID
214            && self.beta::<1>(dart_id) == NULL_DART_ID
215            && self.beta::<2>(dart_id) == NULL_DART_ID
216            && self.beta::<3>(dart_id) == NULL_DART_ID
217    }
218}
219
220/// **I-cell-related methods**
221impl<T: CoordsFloat> CMap3<T> {
222    /// Compute the ID of the vertex a given dart is part of.
223    ///
224    /// This corresponds to the minimum dart ID among darts composing the 0-cell orbit.
225    #[must_use = "unused return value"]
226    pub fn vertex_id(&self, dart_id: DartIdType) -> VertexIdType {
227        let mut marked = HashSet::new();
228        let mut queue = VecDeque::new();
229        marked.insert(NULL_DART_ID);
230        queue.push_front(dart_id);
231        let mut min = dart_id;
232
233        while let Some(d) = queue.pop_front() {
234            if marked.insert(d) {
235                min = min.min(d);
236                let (b0, b2, b3) = (
237                    self.beta::<0>(d), // ?
238                    self.beta::<2>(d),
239                    self.beta::<3>(d),
240                );
241                queue.push_back(self.beta::<1>(b3));
242                queue.push_back(self.beta::<3>(b2));
243                queue.push_back(self.beta::<1>(b2));
244                queue.push_back(self.beta::<3>(b0)); // ?
245                queue.push_back(self.beta::<2>(b0)); // ?
246            }
247        }
248
249        min
250    }
251
252    /// Compute the ID of the vertex a given dart is part of, transactionally.
253    ///
254    /// This corresponds to the minimum dart ID among darts composing the 0-cell orbit.
255    ///
256    /// # Errors
257    ///
258    /// This method is meant to be called in a context where the returned `Result` is used to
259    /// validate the transaction passed as argument. Errors should not be processed manually,
260    /// only processed via the `?` operator.
261    pub fn vertex_id_transac(
262        &self,
263        trans: &mut Transaction,
264        dart_id: DartIdType,
265    ) -> Result<VertexIdType, StmError> {
266        let mut marked = HashSet::new();
267        let mut queue = VecDeque::new();
268        marked.insert(NULL_DART_ID);
269        queue.push_front(dart_id);
270        let mut min = dart_id;
271
272        while let Some(d) = queue.pop_front() {
273            if marked.insert(d) {
274                min = min.min(d);
275                let (b0, b2, b3) = (
276                    self.beta_transac::<0>(trans, d)?, // ?
277                    self.beta_transac::<2>(trans, d)?,
278                    self.beta_transac::<3>(trans, d)?,
279                );
280                queue.push_back(self.beta_transac::<1>(trans, b3)?);
281                queue.push_back(self.beta_transac::<3>(trans, b2)?);
282                queue.push_back(self.beta_transac::<1>(trans, b2)?);
283                queue.push_back(self.beta_transac::<3>(trans, b0)?); // ?
284                queue.push_back(self.beta_transac::<2>(trans, b0)?); // ?
285            }
286        }
287
288        Ok(min)
289    }
290
291    /// Compute the ID of the edge a given dart is part of.
292    ///
293    /// This corresponds to the minimum dart ID among darts composing the 1-cell orbit.
294    #[must_use = "unused return value"]
295    pub fn edge_id(&self, dart_id: DartIdType) -> EdgeIdType {
296        let mut marked = HashSet::new();
297        marked.insert(NULL_DART_ID);
298        let (mut lb, mut rb) = (dart_id, self.beta::<3>(dart_id));
299        let mut min = if rb == NULL_DART_ID { lb } else { lb.min(rb) };
300        let mut alt = true;
301
302        while marked.insert(lb) || marked.insert(rb) {
303            (lb, rb) = if alt {
304                (self.beta::<2>(lb), self.beta::<2>(rb))
305            } else {
306                (self.beta::<3>(lb), self.beta::<3>(rb))
307            };
308            if lb != NULL_DART_ID {
309                min = min.min(lb);
310            }
311            if rb != NULL_DART_ID {
312                min = min.min(rb);
313            }
314            alt = !alt;
315        }
316
317        min
318    }
319
320    /// Compute the ID of the edge a given dart is part of.
321    ///
322    /// This corresponds to the minimum dart ID among darts composing the 1-cell orbit.
323    ///
324    /// # Errors
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 edge_id_transac(
330        &self,
331        trans: &mut Transaction,
332        dart_id: DartIdType,
333    ) -> Result<EdgeIdType, StmError> {
334        let mut marked = HashSet::new();
335        marked.insert(NULL_DART_ID);
336        let (mut lb, mut rb) = (dart_id, self.beta_transac::<3>(trans, dart_id)?);
337        let mut min = if rb == NULL_DART_ID { lb } else { lb.min(rb) };
338        let mut alt = true;
339
340        while marked.insert(lb) || marked.insert(rb) {
341            (lb, rb) = if alt {
342                (
343                    self.beta_transac::<2>(trans, lb)?,
344                    self.beta_transac::<2>(trans, rb)?,
345                )
346            } else {
347                (
348                    self.beta_transac::<3>(trans, lb)?,
349                    self.beta_transac::<3>(trans, rb)?,
350                )
351            };
352            if lb != NULL_DART_ID {
353                min = min.min(lb);
354            }
355            if rb != NULL_DART_ID {
356                min = min.min(rb);
357            }
358            alt = !alt;
359        }
360
361        Ok(min)
362    }
363
364    /// Compute the ID of the face a given dart is part of.
365    ///
366    /// This corresponds to the minimum dart ID among darts composing the 2-cell orbit.
367    #[must_use = "unused return value"]
368    pub fn face_id(&self, dart_id: DartIdType) -> FaceIdType {
369        let mut marked = HashSet::new();
370        marked.insert(NULL_DART_ID);
371        let b3_dart_id = self.beta::<3>(dart_id);
372        let (mut lb, mut rb) = (dart_id, b3_dart_id);
373        let mut min = if rb == NULL_DART_ID { lb } else { lb.min(rb) };
374
375        while marked.insert(lb) || marked.insert(rb) {
376            (lb, rb) = (self.beta::<1>(lb), self.beta::<0>(rb));
377            if lb != NULL_DART_ID {
378                min = min.min(lb);
379            }
380            if rb != NULL_DART_ID {
381                min = min.min(rb);
382            }
383        }
384        // face is open, we need to iterate in the other direction
385        if lb == NULL_DART_ID || rb == NULL_DART_ID {
386            (lb, rb) = (self.beta::<0>(dart_id), self.beta::<1>(b3_dart_id));
387            while marked.insert(lb) || marked.insert(rb) {
388                (lb, rb) = (self.beta::<0>(lb), self.beta::<1>(rb));
389                if lb != NULL_DART_ID {
390                    min = min.min(lb);
391                }
392                if rb != NULL_DART_ID {
393                    min = min.min(rb);
394                }
395            }
396        }
397
398        min
399    }
400
401    /// Compute the ID of the face a given dart is part of.
402    ///
403    /// This corresponds to the minimum dart ID among darts composing the 2-cell orbit.
404    ///
405    /// # Errors
406    ///
407    /// This method is meant to be called in a context where the returned `Result` is used to
408    /// validate the transaction passed as argument. Errors should not be processed manually,
409    /// only processed via the `?` operator.
410    pub fn face_id_transac(
411        &self,
412        trans: &mut Transaction,
413        dart_id: DartIdType,
414    ) -> Result<FaceIdType, StmError> {
415        let mut marked = HashSet::new();
416        marked.insert(NULL_DART_ID);
417        let b3_dart_id = self.beta_transac::<3>(trans, dart_id)?;
418        let (mut lb, mut rb) = (dart_id, b3_dart_id);
419        let mut min = if rb == NULL_DART_ID { lb } else { lb.min(rb) };
420
421        while marked.insert(lb) || marked.insert(rb) {
422            (lb, rb) = (
423                self.beta_transac::<1>(trans, lb)?,
424                self.beta_transac::<0>(trans, rb)?,
425            );
426            if lb != NULL_DART_ID {
427                min = min.min(lb);
428            }
429            if rb != NULL_DART_ID {
430                min = min.min(rb);
431            }
432        }
433        // face is open, we need to iterate in the other direction
434        if lb == NULL_DART_ID || rb == NULL_DART_ID {
435            (lb, rb) = (
436                self.beta_transac::<0>(trans, dart_id)?,
437                self.beta_transac::<1>(trans, b3_dart_id)?,
438            );
439            while marked.insert(lb) || marked.insert(rb) {
440                (lb, rb) = (
441                    self.beta_transac::<0>(trans, lb)?,
442                    self.beta_transac::<1>(trans, rb)?,
443                );
444                if lb != NULL_DART_ID {
445                    min = min.min(lb);
446                }
447                if rb != NULL_DART_ID {
448                    min = min.min(rb);
449                }
450            }
451        }
452
453        Ok(min)
454    }
455
456    /// Compute the ID of the volume a given dart is part of.
457    ///
458    /// This corresponds to the minimum dart ID among darts composing the 3-cell orbit.
459    #[must_use = "unused return value"]
460    pub fn volume_id(&self, dart_id: DartIdType) -> VolumeIdType {
461        let mut marked = HashSet::new();
462        let mut queue = VecDeque::new();
463        marked.insert(NULL_DART_ID);
464        queue.push_front(dart_id);
465        let mut min = dart_id;
466
467        while let Some(d) = queue.pop_front() {
468            if marked.insert(d) {
469                min = min.min(d);
470                queue.push_back(self.beta::<1>(d));
471                queue.push_back(self.beta::<0>(d)); // ?
472                queue.push_back(self.beta::<2>(d));
473            }
474        }
475
476        min
477    }
478
479    /// Compute the ID of the volume a given dart is part of.
480    ///
481    /// This corresponds to the minimum dart ID among darts composing the 3-cell orbit.
482    ///
483    /// # Errors
484    ///
485    /// This method is meant to be called in a context where the returned `Result` is used to
486    /// validate the transaction passed as argument. Errors should not be processed manually,
487    /// only processed via the `?` operator.
488    pub fn volume_id_transac(
489        &self,
490        trans: &mut Transaction,
491        dart_id: DartIdType,
492    ) -> Result<VolumeIdType, StmError> {
493        let mut marked = HashSet::new();
494        let mut queue = VecDeque::new();
495        marked.insert(NULL_DART_ID);
496        queue.push_front(dart_id);
497        let mut min = dart_id;
498
499        while let Some(d) = queue.pop_front() {
500            if marked.insert(d) {
501                min = min.min(d);
502                queue.push_back(self.beta_transac::<1>(trans, d)?);
503                queue.push_back(self.beta_transac::<0>(trans, d)?); // ?
504                queue.push_back(self.beta_transac::<2>(trans, d)?);
505            }
506        }
507
508        Ok(min)
509    }
510
511    /// Return the orbit defined by a dart and its `I`-cell.
512    ///
513    /// # Usage
514    ///
515    /// The [`Orbit3`] can be iterated upon to retrieve all dart members of the cell. Note that
516    /// **the dart passed as an argument is included as the first element of the returned orbit**.
517    ///
518    /// # Panics
519    ///
520    /// The method will panic if *I* is not 0, 1, 2, or 3.
521    #[must_use = "unused return value"]
522    pub fn i_cell<const I: u8>(&self, dart_id: DartIdType) -> Orbit3<'_, T> {
523        assert!(I < 4);
524        match I {
525            0 => Orbit3::new(self, OrbitPolicy::Vertex, dart_id),
526            1 => Orbit3::new(self, OrbitPolicy::Edge, dart_id),
527            2 => Orbit3::new(self, OrbitPolicy::Face, dart_id),
528            3 => todo!(),
529            _ => unreachable!(),
530        }
531    }
532
533    /// Return an iterator over IDs of all the map's vertices.
534    pub fn iter_vertices(&self) -> impl Iterator<Item = VertexIdType> + '_ {
535        (1..self.n_darts() as DartIdType)
536            .zip(self.unused_darts.iter().skip(1))
537            .filter_map(
538                |(d, unused)| {
539                    if unused.read_atomic() {
540                        None
541                    } else {
542                        Some(d)
543                    }
544                },
545            )
546            .filter_map(|d| {
547                let vid = self.vertex_id(d);
548                if d == vid {
549                    Some(vid)
550                } else {
551                    None
552                }
553            })
554    }
555
556    /// Return an iterator over IDs of all the map's edges.
557    pub fn iter_edges(&self) -> impl Iterator<Item = EdgeIdType> + '_ {
558        (1..self.n_darts() as DartIdType)
559            .zip(self.unused_darts.iter().skip(1))
560            .filter_map(
561                |(d, unused)| {
562                    if unused.read_atomic() {
563                        None
564                    } else {
565                        Some(d)
566                    }
567                },
568            )
569            .filter_map(|d| {
570                let eid = self.edge_id(d);
571                if d == eid {
572                    Some(eid)
573                } else {
574                    None
575                }
576            })
577    }
578
579    /// Return an iterator over IDs of all the map's faces.
580    pub fn iter_faces(&self) -> impl Iterator<Item = FaceIdType> + '_ {
581        (1..self.n_darts() as DartIdType)
582            .zip(self.unused_darts.iter().skip(1))
583            .filter_map(
584                |(d, unused)| {
585                    if unused.read_atomic() {
586                        None
587                    } else {
588                        Some(d)
589                    }
590                },
591            )
592            .filter_map(|d| {
593                let fid = self.face_id(d);
594                if d == fid {
595                    Some(fid)
596                } else {
597                    None
598                }
599            })
600    }
601
602    /// Return an iterator over IDs of all the map's volumes.
603    pub fn iter_volumes(&self) -> impl Iterator<Item = VolumeIdType> + '_ {
604        (1..self.n_darts() as DartIdType)
605            .zip(self.unused_darts.iter().skip(1))
606            .filter_map(
607                |(d, unused)| {
608                    if unused.read_atomic() {
609                        None
610                    } else {
611                        Some(d)
612                    }
613                },
614            )
615            .filter_map(|d| {
616                let vid = self.volume_id(d);
617                if d == vid {
618                    Some(vid)
619                } else {
620                    None
621                }
622            })
623    }
624}
honeycomb_core/cmap/dim3/basic_ops.rs

honeycomb_core/cmap/dim3/
basic_ops.rs
