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