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}