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::{BTreeSet, VecDeque};
7
8use crate::cmap::{CMap2, DartIdType, OrbitPolicy, NULL_DART_ID};
9use crate::geometry::CoordsFloat;
10
11/// # Generic 2D orbit implementation
12///
13/// This structure only contains meta-data about the orbit in its initial state. All the darts
14/// making up the orbit are computed when using the methods that come with the [Iterator]
15/// implementation.
16///
17/// It is not currently possible to iterate over references, the orbit has to be consumed for its
18/// result to be used. This is most likely the best behavior since orbits should be consumed upon
19/// traversal to avoid inconsistencies created by a later mutable operation on the map.
20///
21/// ## Generics
22///
23/// - `'a` -- Lifetime of the reference to the map
24/// - `T: CoordsFloat` -- Generic parameter of the referenced map.
25///
26/// ## The search algorithm
27///
28/// The search algorithm used to establish the list of dart included in the orbit is a
29/// [Breadth-First Search algorithm][WIKIBFS]. This means that:
30///
31/// - we look at the images of the current dart through all beta functions,
32///   adding those to a queue, before moving on to the next dart.
33/// - we apply the beta functions in their specified order; This guarantees a consistent and
34///   predictable result.
35///
36/// [WIKIBFS]: https://en.wikipedia.org/wiki/Breadth-first_search
37pub struct Orbit2<'a, T: CoordsFloat> {
38    /// Reference to the map containing the beta functions used in the BFS.
39    map_handle: &'a CMap2<T>,
40    /// Policy used by the orbit for the BFS. It can be predetermined or custom.
41    orbit_policy: OrbitPolicy,
42    /// Set used to identify which dart is marked during the BFS.
43    marked: BTreeSet<DartIdType>,
44    /// Queue used to store which dart must be visited next during the BFS.
45    pending: VecDeque<DartIdType>,
46}
47
48impl<'a, T: CoordsFloat> Orbit2<'a, T> {
49    /// Constructor
50    ///
51    /// # Arguments
52    ///
53    /// - `map_handle: &'a CMap2<T>` -- Reference to the map containing the beta
54    ///   functions used in the BFS.
55    /// - `orbit_policy: OrbitPolicy` -- Policy used by the orbit for the BFS.
56    /// - `dart: DartIdentifier` -- Dart of which the structure will compute the orbit.
57    ///
58    /// # Performance
59    ///
60    /// Currently, orbits use two dynamically allocated structures for computation: a `VecDeque`,
61    /// and a `BTreeSet`. Allocations are made by the constructor since these structures aren't
62    /// empty initially.
63    #[must_use = "unused return value"]
64    pub fn new(map_handle: &'a CMap2<T>, orbit_policy: OrbitPolicy, dart: DartIdType) -> Self {
65        let mut marked = BTreeSet::<DartIdType>::new();
66        marked.insert(NULL_DART_ID); // we don't want to include the null dart in the orbit
67        marked.insert(dart); // we're starting here, so we mark it beforehand
68        let pending = VecDeque::from([dart]);
69        /*
70        if let OrbitPolicy::Custom(slice) = orbit_policy {
71            assert!(!slice.len().is_zero());
72        }
73        */
74        Self {
75            map_handle,
76            orbit_policy,
77            marked,
78            pending,
79        }
80    }
81}
82
83impl<T: CoordsFloat> Iterator for Orbit2<'_, T> {
84    type Item = DartIdType;
85
86    fn next(&mut self) -> Option<Self::Item> {
87        if let Some(d) = self.pending.pop_front() {
88            match self.orbit_policy {
89                OrbitPolicy::Vertex => {
90                    // THIS CODE IS ONLY VALID IN 2D
91                    let image1 = self.map_handle.beta::<1>(self.map_handle.beta::<2>(d));
92                    if self.marked.insert(image1) {
93                        // if true, we did not see this dart yet
94                        // i.e. we need to visit it later
95                        self.pending.push_back(image1);
96                    }
97                    let image2 = self.map_handle.beta::<2>(self.map_handle.beta::<0>(d));
98                    if self.marked.insert(image2) {
99                        // if true, we did not see this dart yet
100                        // i.e. we need to visit it later
101                        self.pending.push_back(image2);
102                    }
103                }
104                OrbitPolicy::VertexLinear => {
105                    // THIS CODE IS ONLY VALID IN 2D
106                    let image = self.map_handle.beta::<1>(self.map_handle.beta::<2>(d));
107                    if self.marked.insert(image) {
108                        // if true, we did not see this dart yet
109                        // i.e. we need to visit it later
110                        self.pending.push_back(image);
111                    }
112                }
113                OrbitPolicy::Edge => {
114                    // THIS CODE IS ONLY VALID IN 2D
115                    let image = self.map_handle.beta::<2>(d);
116                    if self.marked.insert(image) {
117                        // if true, we did not see this dart yet
118                        // i.e. we need to visit it later
119                        self.pending.push_back(image);
120                    }
121                }
122                OrbitPolicy::Face => {
123                    // THIS CODE IS ONLY VALID IN 2D
124                    let image1 = self.map_handle.beta::<1>(d);
125                    if self.marked.insert(image1) {
126                        // if true, we did not see this dart yet
127                        // i.e. we need to visit it later
128                        self.pending.push_back(image1);
129                    }
130                    let image2 = self.map_handle.beta::<0>(d);
131                    if self.marked.insert(image2) {
132                        // if true, we did not see this dart yet
133                        // i.e. we need to visit it later
134                        self.pending.push_back(image2);
135                    }
136                }
137                OrbitPolicy::FaceLinear => {
138                    // THIS CODE IS ONLY VALID IN 2D
139                    let image = self.map_handle.beta::<1>(d);
140                    if self.marked.insert(image) {
141                        // if true, we did not see this dart yet
142                        // i.e. we need to visit it later
143                        self.pending.push_back(image);
144                    }
145                }
146                OrbitPolicy::Custom(beta_slice) => {
147                    for beta_id in beta_slice {
148                        let image = self.map_handle.beta_rt(*beta_id, d);
149                        if self.marked.insert(image) {
150                            // if true, we did not see this dart yet
151                            // i.e. we need to visit it later
152                            self.pending.push_back(image);
153                        }
154                    }
155                }
156                OrbitPolicy::Volume | OrbitPolicy::VolumeLinear => {
157                    unimplemented!("3-cells aren't defined for 2-maps")
158                }
159            }
160            Some(d)
161        } else {
162            None
163        }
164    }
165}
166
167// ------ TESTS
168
169#[allow(unused_mut)]
170#[cfg(test)]
171mod tests {
172    use super::*;
173
174    fn simple_map() -> CMap2<f64> {
175        let mut map: CMap2<f64> = CMap2::new(11);
176        // tri1
177        map.force_link::<1>(1, 2).unwrap();
178        map.force_link::<1>(2, 3).unwrap();
179        map.force_link::<1>(3, 1).unwrap();
180        // tri2
181        map.force_link::<1>(4, 5).unwrap();
182        map.force_link::<1>(5, 6).unwrap();
183        map.force_link::<1>(6, 4).unwrap();
184        // pent on top
185        map.force_link::<1>(7, 8).unwrap();
186        map.force_link::<1>(8, 9).unwrap();
187        map.force_link::<1>(9, 10).unwrap();
188        map.force_link::<1>(10, 11).unwrap();
189        map.force_link::<1>(11, 7).unwrap();
190
191        // link all
192        map.force_link::<2>(2, 4).unwrap();
193        map.force_link::<2>(6, 7).unwrap();
194
195        assert!(map.force_write_vertex(1, (0.0, 0.0)).is_none());
196        assert!(map.force_write_vertex(2, (1.0, 0.0)).is_none());
197        assert!(map.force_write_vertex(6, (1.0, 1.0)).is_none());
198        assert!(map.force_write_vertex(3, (0.0, 1.0)).is_none());
199        assert!(map.force_write_vertex(9, (1.5, 1.5)).is_none());
200        assert!(map.force_write_vertex(10, (0.5, 2.0)).is_none());
201        assert!(map.force_write_vertex(11, (-0.5, 1.5)).is_none());
202
203        map
204    }
205
206    #[test]
207    fn full_map_from_orbit() {
208        let map = simple_map();
209        let orbit = Orbit2::new(&map, OrbitPolicy::Custom(&[1, 2]), 3);
210        let darts: Vec<DartIdType> = orbit.collect();
211        assert_eq!(darts.len(), 11);
212        // because the algorithm is consistent, we can predict the exact layout
213        assert_eq!(&darts, &[3, 1, 2, 4, 5, 6, 7, 8, 9, 10, 11]);
214    }
215
216    #[test]
217    fn orbit_variants() {
218        let map = simple_map();
219
220        // face is complete, so everything works
221        let face: Vec<DartIdType> = Orbit2::new(&map, OrbitPolicy::Face, 7).collect();
222        let face_linear: Vec<DartIdType> = Orbit2::new(&map, OrbitPolicy::FaceLinear, 7).collect();
223        let face_custom: Vec<DartIdType> =
224            Orbit2::new(&map, OrbitPolicy::Custom(&[0, 1]), 7).collect();
225        assert_eq!(&face, &[7, 8, 11, 9, 10]);
226        assert_eq!(&face_linear, &[7, 8, 9, 10, 11]);
227        assert_eq!(&face_custom, &[7, 11, 8, 10, 9]);
228
229        // vertex is incomplete, so using the linear variant will yield an incomplete orbit
230        let vertex: Vec<DartIdType> = Orbit2::new(&map, OrbitPolicy::Vertex, 4).collect();
231        let vertex_linear: Vec<DartIdType> =
232            Orbit2::new(&map, OrbitPolicy::VertexLinear, 4).collect();
233        assert_eq!(&vertex, &[4, 3, 7]);
234        assert_eq!(&vertex_linear, &[4, 3]);
235    }
236
237    #[test]
238    fn face_from_orbit() {
239        let map = simple_map();
240        let face_orbit = Orbit2::new(&map, OrbitPolicy::Face, 1);
241        let darts: Vec<DartIdType> = face_orbit.collect();
242        assert_eq!(darts.len(), 3);
243        assert_eq!(&darts, &[1, 2, 3]);
244        let other_face_orbit = Orbit2::new(&map, OrbitPolicy::Custom(&[1]), 5);
245        let other_darts: Vec<DartIdType> = other_face_orbit.collect();
246        assert_eq!(other_darts.len(), 3);
247        assert_eq!(&other_darts, &[5, 6, 4]);
248    }
249
250    #[test]
251    fn edge_from_orbit() {
252        let map = simple_map();
253        let face_orbit = Orbit2::new(&map, OrbitPolicy::Edge, 1);
254        let darts: Vec<DartIdType> = face_orbit.collect();
255        assert_eq!(darts.len(), 1);
256        assert_eq!(&darts, &[1]); // dart 1 is on the boundary
257        let other_face_orbit = Orbit2::new(&map, OrbitPolicy::Custom(&[2]), 4);
258        let other_darts: Vec<DartIdType> = other_face_orbit.collect();
259        assert_eq!(other_darts.len(), 2);
260        assert_eq!(&other_darts, &[4, 2]);
261    }
262
263    #[test]
264    fn vertex_from_orbit() {
265        let map = simple_map();
266        let orbit = Orbit2::new(&map, OrbitPolicy::Vertex, 4);
267        let darts: Vec<DartIdType> = orbit.collect();
268        assert_eq!(darts.len(), 3);
269        assert_eq!(&darts, &[4, 3, 7]);
270    }
271
272    #[test]
273    fn empty_orbit_policy() {
274        let map = simple_map();
275        let darts: Vec<DartIdType> = Orbit2::new(&map, OrbitPolicy::Custom(&[]), 3).collect();
276        assert_eq!(&darts, &[3]);
277    }
278
279    #[test]
280    #[should_panic(expected = "assertion failed: i < 3")]
281    fn invalid_orbit_policy() {
282        let map = simple_map();
283        let orbit = Orbit2::new(&map, OrbitPolicy::Custom(&[6]), 3);
284        let _: Vec<DartIdType> = orbit.collect();
285    }
286}
honeycomb_core/cmap/dim2/orbits.rs

honeycomb_core/cmap/dim2/
orbits.rs
