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