honeycomb_core/cmap/dim2/
orbits.rs

1//! Orbit implementation
2//!
3//! This module contains all code used to model orbits, a notion defined
4//! along the structure of combinatorial maps.
5
6use std::collections::{HashSet, VecDeque};
7
8use crate::cmap::{CMap2, DartIdType, NULL_DART_ID, OrbitPolicy, try_from_fn};
9use crate::geometry::CoordsFloat;
10use crate::stm::{StmClosureResult, Transaction};
11
12/// **Orbits**
13impl<T: CoordsFloat> CMap2<T> {
14    /// Generic orbit implementation.
15    ///
16    /// # Arguments
17    /// - `opolicy: OrbitPolicy` -- Policy used by the orbit for the BFS.
18    /// - `dart_id: DartIdentifier` -- Dart of which the structure will compute the orbit.
19    ///
20    /// # The search algorithm
21    ///
22    /// The search algorithm used to establish the list of dart included in the orbit is a
23    /// [Breadth-First Search algorithm][WIKIBFS]. This means that:
24    ///
25    /// - we look at the images of the current dart through all beta functions,
26    ///   adding those to a queue, before moving on to the next dart.
27    /// - we apply the beta functions in their specified order; This guarantees a consistent and
28    ///   predictable result.
29    ///
30    /// # Performance
31    ///
32    /// Currently, orbits use two dynamically allocated structures for computation: a `VecDeque`,
33    /// and a `HashSet`. There is a possibility to use static thread-local instances to avoid
34    /// ephemeral allocations, but [it would require a guard mechanism][PR].
35    ///
36    /// [WIKIBFS]: https://en.wikipedia.org/wiki/Breadth-first_search
37    /// [PR]: https://github.com/LIHPC-Computational-Geometry/honeycomb/pull/293
38    #[allow(clippy::needless_for_each)]
39    pub fn orbit(
40        &self,
41        opolicy: OrbitPolicy,
42        dart_id: DartIdType,
43    ) -> impl Iterator<Item = DartIdType> {
44        let mut pending = VecDeque::new();
45        let mut marked: HashSet<DartIdType> = HashSet::new();
46        pending.push_back(dart_id);
47        marked.insert(NULL_DART_ID);
48        marked.insert(dart_id); // we're starting here, so we mark it beforehand
49
50        // FIXME: move the match block out of the iterator
51        std::iter::from_fn(move || {
52            if let Some(d) = pending.pop_front() {
53                // I have to define the closure here due to mutability constraints
54                let mut check = |d: DartIdType| {
55                    if marked.insert(d) {
56                        // if true, we did not see this dart yet
57                        // i.e. we need to visit it later
58                        pending.push_back(d);
59                    }
60                };
61                // compute the next images
62                match opolicy {
63                    OrbitPolicy::Vertex => {
64                        let im1 = self.beta::<1>(self.beta::<2>(d));
65                        let im2 = self.beta::<2>(self.beta::<0>(d));
66                        check(im1);
67                        check(im2);
68                    }
69                    OrbitPolicy::VertexLinear => {
70                        let im = self.beta::<1>(self.beta::<2>(d));
71                        check(im);
72                    }
73                    OrbitPolicy::Edge => {
74                        let im = self.beta::<2>(d);
75                        check(im);
76                    }
77                    OrbitPolicy::Face => {
78                        let im1 = self.beta::<1>(d);
79                        let im2 = self.beta::<0>(d);
80                        check(im1);
81                        check(im2);
82                    }
83                    OrbitPolicy::FaceLinear => {
84                        let im = self.beta::<1>(d);
85                        check(im);
86                    }
87                    OrbitPolicy::Custom(beta_slice) => {
88                        for beta_id in beta_slice {
89                            let im = self.beta_rt(*beta_id, d);
90                            check(im);
91                        }
92                    }
93                    OrbitPolicy::Volume | OrbitPolicy::VolumeLinear => {
94                        unimplemented!("3-cells aren't defined for 2-maps")
95                    }
96                }
97
98                return Some(d);
99            }
100            None // queue is empty, we're done
101        })
102    }
103
104    /// Generic orbit transactional implementation.
105    #[allow(clippy::needless_for_each)]
106    pub fn orbit_transac(
107        &self,
108        t: &mut Transaction,
109        opolicy: OrbitPolicy,
110        dart_id: DartIdType,
111    ) -> impl Iterator<Item = StmClosureResult<DartIdType>> {
112        let mut pending = VecDeque::new();
113        let mut marked: HashSet<DartIdType> = HashSet::new();
114        pending.push_back(dart_id);
115        marked.insert(NULL_DART_ID);
116        marked.insert(dart_id); // we're starting here, so we mark it beforehand
117
118        try_from_fn(move || {
119            if let Some(d) = pending.pop_front() {
120                // I have to define the closure here due to mutability constraints
121                let mut check = |d: DartIdType| {
122                    if marked.insert(d) {
123                        // if true, we did not see this dart yet
124                        // i.e. we need to visit it later
125                        pending.push_back(d);
126                    }
127                };
128                match opolicy {
129                    OrbitPolicy::Vertex => {
130                        let b2 = self.beta_transac::<2>(t, d)?;
131                        let b0 = self.beta_transac::<0>(t, d)?;
132                        let im1 = self.beta_transac::<1>(t, b2)?;
133                        let im2 = self.beta_transac::<2>(t, b0)?;
134                        check(im1);
135                        check(im2);
136                    }
137                    OrbitPolicy::VertexLinear => {
138                        let b2 = self.beta_transac::<2>(t, d)?;
139                        let im = self.beta_transac::<1>(t, b2)?;
140                        check(im);
141                    }
142                    OrbitPolicy::Edge => {
143                        let im = self.beta_transac::<2>(t, d)?;
144                        check(im);
145                    }
146                    OrbitPolicy::Face => {
147                        let im1 = self.beta_transac::<1>(t, d)?;
148                        let im2 = self.beta_transac::<0>(t, d)?;
149                        check(im1);
150                        check(im2);
151                    }
152                    OrbitPolicy::FaceLinear => {
153                        let im = self.beta_transac::<1>(t, d)?;
154                        check(im);
155                    }
156                    OrbitPolicy::Custom(beta_slice) => {
157                        for beta_id in beta_slice {
158                            let im = self.beta_rt_transac(t, *beta_id, d)?;
159                            check(im);
160                        }
161                    }
162                    OrbitPolicy::Volume | OrbitPolicy::VolumeLinear => {
163                        unimplemented!("3-cells aren't defined for 2-maps")
164                    }
165                }
166                return Ok(Some(d));
167            }
168            Ok(None) // queue is empty, we're done
169        })
170    }
171
172    /// Return the orbit defined by a dart and its `I`-cell.
173    ///
174    /// # Usage
175    ///
176    /// The returned item can be iterated upon to retrieve all dart member of the cell. Note that
177    /// **the dart passed as an argument is included as the first element of the returned orbit**.
178    ///
179    /// # Panics
180    ///
181    /// The method will panic if *I* is not 0, 1 or 2.
182    #[must_use = "unused return value"]
183    pub fn i_cell<const I: u8>(&self, dart_id: DartIdType) -> impl Iterator<Item = DartIdType> {
184        assert!(I < 3);
185        match I {
186            0 => self.orbit(OrbitPolicy::Vertex, dart_id),
187            1 => self.orbit(OrbitPolicy::Edge, dart_id),
188            2 => self.orbit(OrbitPolicy::Face, dart_id),
189            _ => unreachable!(),
190        }
191    }
192}