honeycomb_core/cmap/dim3/
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::VecDeque;
7
8use rustc_hash::FxHashSet as HashSet;
9
10use crate::cmap::{CMap3, DartIdType, NULL_DART_ID, OrbitPolicy, try_from_fn};
11use crate::geometry::CoordsFloat;
12use crate::stm::{StmClosureResult, Transaction};
13
14impl<T: CoordsFloat> CMap3<T> {
15    /// Generic orbit implementation.
16    ///
17    /// # Arguments
18    /// - `opolicy: OrbitPolicy` -- Policy used by the orbit for the BFS.
19    /// - `dart_id: DartIdentifier` -- Dart of which the structure will compute the orbit.
20    ///
21    /// # The search algorithm
22    ///
23    /// The search algorithm used to establish the list of dart included in the orbit is a
24    /// [Breadth-First Search algorithm][WIKIBFS]. This means that:
25    ///
26    /// - we look at the images of the current dart through all beta functions,
27    ///   adding those to a queue, before moving on to the next dart.
28    /// - we apply the beta functions in their specified order; This guarantees a consistent and
29    ///   predictable result.
30    ///
31    /// # Performance
32    ///
33    /// Currently, orbits use two dynamically allocated structures for computation: a `VecDeque`,
34    /// and a `HashSet`. There is a possibility to use static thread-local instances to avoid
35    /// ephemeral allocations, but [it would require a guard mechanism][PR].
36    ///
37    /// [WIKIBFS]: https://en.wikipedia.org/wiki/Breadth-first_search
38    /// [PR]: https://github.com/LIHPC-Computational-Geometry/honeycomb/pull/293
39    #[allow(clippy::needless_for_each, clippy::too_many_lines)]
40    #[rustfmt::skip]
41    pub fn orbit(
42        &self,
43        opolicy: OrbitPolicy,
44        dart_id: DartIdType,
45    ) -> impl Iterator<Item = DartIdType> {
46        let mut pending = VecDeque::new();
47        let mut marked: HashSet<DartIdType> = HashSet::default();
48        pending.push_back(dart_id);
49        marked.insert(NULL_DART_ID);
50        marked.insert(dart_id); // we're starting here, so we mark it beforehand
51
52        // FIXME: move the match block out of the iterator
53        std::iter::from_fn(move || {
54            if let Some(d) = pending.pop_front() {
55                let mut check = |d: DartIdType| {
56                    if marked.insert(d) {
57                        pending.push_back(d);
58                    }
59                };
60                // compute the next images
61                match opolicy {
62                    // B3oB2, B1oB3, B1oB2, B3oB0, B2oB0
63                    OrbitPolicy::Vertex => {
64                        [
65                            self.beta::<1>(self.beta::<2>(d)), // b1(b2(d))
66                            self.beta::<2>(self.beta::<0>(d)), // b2(b0(d))
67                            self.beta::<1>(self.beta::<3>(d)), // b1(b3(d))
68                            self.beta::<3>(self.beta::<0>(d)), // b3(b0(d))
69                            self.beta::<2>(self.beta::<3>(d)), // b2(b3(d))
70                            self.beta::<3>(self.beta::<2>(d)), // b3(b2(d))
71                        ]
72                        .into_iter()
73                        .for_each(check);
74                    }
75                    // B3oB2, B1oB3, B1oB2
76                    OrbitPolicy::VertexLinear => {
77                        [
78                            self.beta::<1>(self.beta::<2>(d)), // b1(b2(d))
79                            self.beta::<1>(self.beta::<3>(d)), // b1(b3(d))
80                            self.beta::<2>(self.beta::<3>(d)), // b2(b3(d))
81                        ]
82                        .into_iter()
83                        .for_each(check);
84                    }
85                    // B2, B3
86                    OrbitPolicy::Edge => {
87                        [
88                            self.beta::<2>(d),
89                            self.beta::<3>(d),
90                        ]
91                        .into_iter()
92                        .for_each(check);
93                    }
94                    // B1, B0, B3
95                    OrbitPolicy::Face => {
96                        [
97                            self.beta::<1>(d),
98                            self.beta::<0>(d),
99                            self.beta::<3>(d),
100                        ]
101                        .into_iter()
102                        .for_each(check);
103                    }
104                    // B1, B3
105                    OrbitPolicy::FaceLinear => {
106                        [
107                            self.beta::<1>(d),
108                            self.beta::<3>(d),
109                        ]
110                        .into_iter()
111                        .for_each(check);
112                    }
113                    // B1, B0, B2
114                    OrbitPolicy::Volume => {
115                        [
116                            self.beta::<1>(d),
117                            self.beta::<0>(d),
118                            self.beta::<2>(d),
119                        ]
120                        .into_iter()
121                        .for_each(check);
122                    }
123                    // B1, B2
124                    OrbitPolicy::VolumeLinear => {
125                        [
126                            self.beta::<1>(d),
127                            self.beta::<2>(d),
128                        ]
129                        .into_iter()
130                        .for_each(check);
131                    }
132                    OrbitPolicy::Custom(beta_slice) => {
133                        for beta_id in beta_slice {
134                            let im = self.beta_rt(*beta_id, d);
135                            check(im);
136                        }
137                    }
138                }
139
140                return Some(d);
141            }
142            None // queue is empty, we're done
143        })
144    }
145
146    /// Generic orbit transactional implementation.
147    #[allow(clippy::needless_for_each, clippy::too_many_lines)]
148    #[rustfmt::skip]
149    pub fn orbit_tx(
150        &self,
151        t: &mut Transaction,
152        opolicy: OrbitPolicy,
153        dart_id: DartIdType,
154    ) -> impl Iterator<Item = StmClosureResult<DartIdType>> {
155        let mut pending = VecDeque::new();
156        let mut marked: HashSet<DartIdType> = HashSet::default();
157        pending.push_back(dart_id);
158        marked.insert(NULL_DART_ID);
159        marked.insert(dart_id); // we're starting here, so we mark it beforehand
160
161        // FIXME: move the match block out of the iterator
162        try_from_fn(move || {
163            if let Some(d) = pending.pop_front() {
164                let mut check = |d: DartIdType| {
165                    if marked.insert(d) {
166                        pending.push_back(d);
167                    }
168                };
169                // compute the next images
170                match opolicy {
171                    // B1oB2, B2oB0, B1oB3, B3oB0, B2oB3, B3oB2
172                    OrbitPolicy::Vertex => {
173                        let (b0, b2, b3) = (
174                            self.beta_tx::<0>(t, d)?,
175                            self.beta_tx::<2>(t, d)?,
176                            self.beta_tx::<3>(t, d)?,
177                        );
178                        [
179                            self.beta_tx::<1>(t, b2)?, // b1(b2(d))
180                            self.beta_tx::<2>(t, b0)?, // b2(b0(d))
181                            self.beta_tx::<1>(t, b3)?, // b1(b3(d))
182                            self.beta_tx::<3>(t, b0)?, // b3(b0(d))
183                            self.beta_tx::<2>(t, b3)?, // b2(b3(d))
184                            self.beta_tx::<3>(t, b2)?, // b3(b2(d))
185                        ]
186                        .into_iter()
187                        .for_each(check);
188                    }
189                    // B2oB3, B1oB3, B1oB2
190                    OrbitPolicy::VertexLinear => {
191                        let (b2, b3) =
192                            (self.beta_tx::<2>(t, d)?, self.beta_tx::<3>(t, d)?);
193                        [
194                            self.beta_tx::<1>(t, b2)?, // b1(b2(d))
195                            self.beta_tx::<1>(t, b3)?, // b1(b3(d))
196                            self.beta_tx::<2>(t, b3)?, // b2(b3(d))
197                        ]
198                        .into_iter()
199                        .for_each(check);
200                    }
201                    // B2, B3
202                    OrbitPolicy::Edge => {
203                        [self.beta_tx::<2>(t, d)?, self.beta_tx::<3>(t, d)?]
204                            .into_iter()
205                            .for_each(check);
206                    }
207                    // B1, B0, B3
208                    OrbitPolicy::Face => {
209                        [
210                            self.beta_tx::<1>(t, d)?,
211                            self.beta_tx::<0>(t, d)?,
212                            self.beta_tx::<3>(t, d)?,
213                        ]
214                        .into_iter()
215                        .for_each(check);
216                    }
217                    // B1, B3
218                    OrbitPolicy::FaceLinear => {
219                        [
220                            self.beta_tx::<1>(t, d)?,
221                            self.beta_tx::<3>(t, d)?,
222                        ]
223                        .into_iter()
224                        .for_each(check);
225                    }
226                    // B1, B0, B2
227                    OrbitPolicy::Volume => {
228                        [
229                            self.beta_tx::<1>(t, d)?,
230                            self.beta_tx::<0>(t, d)?,
231                            self.beta_tx::<2>(t, d)?,
232                        ]
233                        .into_iter()
234                        .for_each(check);
235                    }
236                    // B1, B2
237                    OrbitPolicy::VolumeLinear => {
238                        [self.beta_tx::<1>(t, d)?, self.beta_tx::<2>(t, d)?]
239                            .into_iter()
240                            .for_each(check);
241                    }
242                    OrbitPolicy::Custom(beta_slice) => {
243                        for beta_id in beta_slice {
244                            let im = self.beta_rt_tx(t, *beta_id, d)?;
245                            check(im);
246                        }
247                    }
248                }
249
250                return Ok(Some(d));
251            }
252            Ok(None) // queue is empty, we're done
253        })
254    }
255
256    /// Return the orbit defined by a dart and its `I`-cell.
257    ///
258    /// # Usage
259    ///
260    /// The returned item can be iterated upon to retrieve all dart members of the cell. Note that
261    /// **the dart passed as an argument is included as the first element of the returned orbit**.
262    ///
263    /// # Panics
264    ///
265    /// The method will panic if *I* is not 0, 1, 2, or 3.
266    #[must_use = "unused return value"]
267    pub fn i_cell<const I: u8>(&self, dart_id: DartIdType) -> impl Iterator<Item = DartIdType> {
268        assert!(I < 4);
269        match I {
270            0 => self.orbit(OrbitPolicy::Vertex, dart_id),
271            1 => self.orbit(OrbitPolicy::Edge, dart_id),
272            2 => self.orbit(OrbitPolicy::Face, dart_id),
273            3 => self.orbit(OrbitPolicy::Volume, dart_id),
274            _ => unreachable!(),
275        }
276    }
277}
honeycomb_core/cmap/dim3/orbits.rs

honeycomb_core/cmap/dim3/
orbits.rs
