From 81bce1d38758d3a7d000b3fdf0b1821621885782 Mon Sep 17 00:00:00 2001 From: Charlotte Pabst Date: Wed, 17 Jan 2024 21:18:38 +0100 Subject: --- src/main.rs | 545 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 545 insertions(+) create mode 100644 src/main.rs (limited to 'src/main.rs') diff --git a/src/main.rs b/src/main.rs new file mode 100644 index 0000000..960c334 --- /dev/null +++ b/src/main.rs @@ -0,0 +1,545 @@ +#![allow(unused)] +// the cell! macro will expand to complex types but makes things easier to read for humans +// unlike type definitions, a macro can capture the 'brand and 'arena lifetimes from the scope +#![allow(clippy::type_complexity)] + +use either::Either::{self, *}; +use ghost_cell::{GhostBorrow, GhostCell, GhostToken}; +use typed_arena::Arena; + +type Id = Option; + +// trait for a kind of topological element (i.e. Vertex, HalfEdge, Face) +trait Kind { + type Init; + + fn new(id: usize, init: Self::Init) -> Self; + + fn is_alive(&self) -> bool { + self.get_id().is_some() + } + + fn get_id(&self) -> Id; + fn clear(&mut self); +} + +macro_rules! cell_t { + ($T:ty) => { + &'arena GhostCell<'brand, $T> + } +} + +macro_rules! cell { + ($T:ident) => { + &'arena GhostCell<'brand, $T<'brand, 'arena, V>> + }; +} + +macro_rules! impl_kind { + ($T:ident, $init_name:ident: $init_ty:ty $(, $($init_field:ident : $init_expr:tt),* )? $(; $($fields:ident),*)?) => { + impl<'brand, 'arena, V> Kind for $T<'brand, 'arena, V> { + type Init = $init_ty; + + fn get_id(&self) -> Id { + self.id + } + + fn new(id: usize, $init_name: $init_ty) -> Self { + Self { + id: Some(id), + $($($init_field: $init_expr,)*)? + $($($fields: Default::default(),)*)? + } + } + + fn clear(&mut self) { + self.id = Default::default(); + #[cfg(debug_assertions)] + { $($(self.$fields = Default::default();)*)? } + } + } + + impl<'brand, 'arena, V: Default> PartialEq for $T<'brand, 'arena, V> { + fn eq(&self, other: &Self) -> bool { + self.get_id() == other.get_id() + } + } + impl<'brand, 'arena, V: Default> Eq for $T<'brand, 'arena, V> {} + }; +} + +use std::fmt; + +trait DcelDebug<'brand> { + fn fmt( + &self, + long: bool, + token: &GhostToken<'brand>, + f: &mut fmt::Formatter<'_>, + ) -> Result<(), fmt::Error>; +} + +macro_rules! impl_debug { + ($T:ty) => { + impl<'brand> DcelDebug<'brand> for $T { + fn fmt( + &self, + long: bool, + token: &GhostToken<'brand>, + f: &mut fmt::Formatter<'_>, + ) -> Result<(), fmt::Error> { + fmt::Debug::fmt(self, f)?; + writeln!(f, "") + } + } + }; +} + +impl<'brand, T: DcelDebug<'brand>> DcelDebug<'brand> for Option { + fn fmt( + &self, + long: bool, + token: &GhostToken<'brand>, + f: &mut fmt::Formatter<'_>, + ) -> Result<(), fmt::Error> { + match self { + None => write!(f, "None"), + Some(x) => DcelDebug::fmt(x, long, token, f), + } + } +} + +macro_rules! impl_kind_debug { + ($T:ident $(, $($fields:ident),*)?) => { + impl<'brand, 'arena, V> DcelDebug<'brand> for &'arena GhostCell<'brand, $T<'brand, 'arena, V>> where V: DcelDebug<'brand> { + fn fmt( + &self, + long: bool, + token: &GhostToken<'brand>, + f: &mut fmt::Formatter<'_>, + ) -> Result<(), fmt::Error> { + writeln!(f, "{} {:?}", stringify!($T), self.borrow(token).id)?; + + if long { + $($( + write!(f, "\t{} = ", stringify!($fields))?; + DcelDebug::fmt(&self.borrow(token).$fields, false, token, f)?; + )*)? + } + + Ok(()) + } + } + }; +} + +// responsible for allocation of a certain Kind +struct Container<'brand, 'arena, T: Kind> { + next_id: usize, + arena: &'arena Arena, + elements: Vec, + freelist: Vec, +} + +impl<'brand, 'arena, T: Kind> Container<'brand, 'arena, T> { + fn new(arena: &'arena Arena) -> Self { + Self { + next_id: 0, + arena, + elements: Vec::new(), + freelist: Vec::new(), + } + } + + fn alloc( + &mut self, + token: &mut GhostToken<'brand>, + init: T::Init, /*f: impl FnOnce(Id) -> T*/ + ) -> cell_t!(T) { + let id = self.next_id; + self.next_id += 1; + + let t = Kind::new(id, init); + + if let Some(cell) = self.freelist.pop() { + *cell.borrow_mut(token) = t; + cell + } else { + let cell = GhostCell::from_mut(self.arena.alloc(t)); + self.elements.push(cell); + cell + } + } + + fn free(&mut self, token: &mut GhostToken<'brand>, cell: cell_t!(T)) { + debug_assert!(!cell.borrow(token).is_alive(), "double free"); + cell.borrow_mut(token).clear(); + self.freelist.push(cell); + } +} + +#[derive(Default)] +struct DcelAllocator<'brand, 'arena, V> { + edge: Arena>, + vertex: Arena>, + face: Arena>, +} + +struct Dcel<'brand, 'arena, V: Default> { + token: GhostToken<'brand>, + half_edges: Container<'brand, 'arena, HalfEdge<'brand, 'arena, V>>, + vertices: Container<'brand, 'arena, Vertex<'brand, 'arena, V>>, + faces: Container<'brand, 'arena, Face<'brand, 'arena, V>>, +} + +struct Vertex<'brand, 'arena, V> { + id: Id, + data: V, + outgoing: Option, +} +//type VertexRef<'brand, 'arena, V> = &'arena GhostCell<'brand, Vertex<'brand, 'arena, V>>; +impl_kind!(Vertex, init: V, data: init; outgoing); +impl_kind_debug!(Vertex, data, outgoing); + +struct HalfEdge<'brand, 'arena, V> { + id: Id, + next: Option, + origin: Option, + twin: Option, + face: Option, + prev: Option, +} +//type HalfEdgeRef<'brand, 'arena, V> = &'arena GhostCell<'brand, HalfEdge<'brand, 'arena, V>>; +impl_kind!(HalfEdge, init: (); origin, twin, face, next, prev); +impl_kind_debug!(HalfEdge, origin, twin, face, next, prev); + +/* +struct FaceL<'brand, 'arena, V> { + id: Id, + outer: Vec, + inner: Vec, + solid: Option, +} + +struct Solid<'brand, 'arena, V> { + id: Id, + faces: Vec, + half_edges: Vec, +}*/ + +struct Face<'brand, 'arena, V> { + id: Id, + outer: Vec, + inner: Vec, +} +//type FaceRef<'brand, 'arena, V> = &'arena GhostCell<'brand, Face<'brand, 'arena, V>>; +impl_kind!(Face, init: (); outer, inner); +impl_kind_debug!(Face); + +impl<'brand, 'arena, V: Default> Dcel<'brand, 'arena, V> { + fn new(token: GhostToken<'brand>, alloc: &'arena DcelAllocator<'brand, 'arena, V>) -> Self { + Self { + token, + half_edges: Container::new(&alloc.edge), + vertices: Container::new(&alloc.vertex), + faces: Container::new(&alloc.face), + } + } + + pub fn mvsf(&mut self, data: V) -> (cell!(Vertex), cell!(Face)) { + let f = self.faces.alloc(&mut self.token, ()); + let v = self.vertices.alloc(&mut self.token, data); + + (v, f) + } + + pub fn mevvls(&mut self, data: [V; 2]) -> (cell!(HalfEdge), [cell!(Vertex); 2], cell!(Face)) { + let [d1, d2] = data; + + let l = self.faces.alloc(&mut self.token, ()); + let v1 = self.vertices.alloc(&mut self.token, d1); + let v2 = self.vertices.alloc(&mut self.token, d2); + let a = self.half_edges.alloc(&mut self.token, ()); + let b = self.half_edges.alloc(&mut self.token, ()); + + self.twin(a, b); + self.follow(a, b); + self.follow(b, a); + self.origin(v1, a); + self.origin(v2, b); + + (a, [v1, v2], l) + } + + #[inline(always)] + fn twin(&mut self, a: cell!(HalfEdge), b: cell!(HalfEdge)) { + a.borrow_mut(&mut self.token).twin = Some(b); + b.borrow_mut(&mut self.token).twin = Some(a); + } + + #[inline(always)] + fn origin(&mut self, v: cell!(Vertex), h: cell!(HalfEdge)) { + v.borrow_mut(&mut self.token).outgoing = Some(h); + h.borrow_mut(&mut self.token).origin = Some(v); + } + + #[inline(always)] + fn follow(&mut self, prev: cell!(HalfEdge), next: cell!(HalfEdge)) { + next.borrow_mut(&mut self.token).prev = Some(prev); + prev.borrow_mut(&mut self.token).next = Some(next); + } + + pub fn mve( + &mut self, + edge: cell!(HalfEdge), + data: V, + ) -> Option<(cell!(HalfEdge), cell!(Vertex))> { + // before: + // + // fa + // / a3 + // a1 -> + // v1 v v2 + // <- b1 + // \ b3 + // fb + // + // after: + // + // fa + // / a3 + // a1 -> a2 -> + // v1 v v2 + // <- b1 <- b2 + // \ b3 + // fb + + let v = self.vertices.alloc(&mut self.token, data); + let a2 = self.half_edges.alloc(&mut self.token, ()); + let b2 = self.half_edges.alloc(&mut self.token, ()); + + let a1 = edge; + let v1 = a1.borrow(&self.token).origin?; + //let fa = a1.borrow(&self.token).face?; + + let b1 = a1.borrow(&self.token).twin?; + let v2 = b1.borrow(&self.token).origin?; + //let fb = b1.borrow(&self.token).face?; + + let mut a3 = a1.borrow(&self.token).next?; + if a3.borrow(&self.token) == b1.borrow(&self.token) { + a3 = b2; + } + + let mut b3 = b1.borrow(&self.token).prev?; + if b3.borrow(&self.token) == a1.borrow(&self.token) { + b3 = a2; + } + + self.twin(a2, b2); + + self.origin(v, a2); + self.origin(v, b1); + self.origin(v2, b2); + + self.follow(a1, a2); + self.follow(a2, a3); + + self.follow(b3, b2); + self.follow(b2, b1); + + Some((a1, v)) + } + + pub fn mel(&mut self, v1: cell!(Vertex), v2: cell!(Vertex)) -> Option<()> { + Some(()) + } + + fn mev( + &mut self, + from: cell!(Vertex), + data: V, + ) -> (cell!(Vertex), cell!(HalfEdge), cell!(HalfEdge)) { + let v = self.vertices.alloc(&mut self.token, data); + let a = self.half_edges.alloc(&mut self.token, ()); + let b = self.half_edges.alloc(&mut self.token, ()); + + self.twin(a, b); + + self.origin(v, a); + self.origin(from, b); + + self.follow(a, b); + self.follow(b, a); + + (v, a, b) + } +} + +struct DcelDotOptions { + pub twin: bool, + pub next: bool, + pub prev: bool, +} + +impl DcelDotOptions { + fn none() -> Self { + Self { + twin: false, + next: false, + prev: false, + } + } + + fn all() -> Self { + Self { + twin: true, + next: true, + prev: true, + } + } +} + +fn dcel_write_dot( + dcel: &Dcel<(&'static str, [i64; 2])>, + f: &mut fmt::Formatter<'_>, + opt: DcelDotOptions, +) -> fmt::Result { + use rand::Rng; + use std::collections::HashSet; + + writeln!(f, "digraph DCEL {{")?; + writeln!(f, "node [shape = circle]")?; + //writeln!(f, "nodesep = 1")?; + + let mut rank = Vec::new(); + + for v in dcel.vertices.elements.iter() { + let v = v.borrow(&dcel.token); + if let Some(id) = v.id { + // writeln!(f, "\t{id} [pos=\"{},{}!\"]", v.data.0, v.data.1)?; + writeln!( + f, + "{id} [label=\"{}\", pos=\"{},{}!\"]", + v.data.0, v.data.1[0], v.data.1[1] + ); + rank.push(id); + } + } + + /* + write!(f, "{{ rank=same; ")?; + for r in rank { + write!(f, "{r}; ")?; + } + writeln!(f, "}}");*/ + + for h in dcel.half_edges.elements.iter() { + let h = h.borrow(&dcel.token); + if let Some(id) = h.id { + let twin = h.twin.unwrap().borrow(&dcel.token); + let twin_id = twin.id.unwrap(); + + let a_v = h.origin.unwrap().borrow(&dcel.token); + let b_v = twin.origin.unwrap().borrow(&dcel.token); + + let mut vec = [ + -(b_v.data.1[1] - a_v.data.1[1]) as f64, + (b_v.data.1[0] - a_v.data.1[0]) as f64, + ]; + + let len = (vec[0] * vec[0] + vec[1] * vec[1]).sqrt(); + vec[0] *= 0.2 / len; + vec[1] *= 0.2 / len; + + let mid = [ + (a_v.data.1[0] + b_v.data.1[0]) as f64 / 2.0 + vec[0], + (a_v.data.1[1] + b_v.data.1[1]) as f64 / 2.0 + vec[1], + ]; + + let a = a_v.id.unwrap(); + let b = b_v.id.unwrap(); + + writeln!( + f, + "edge_{id} [pos=\"{},{}!\", shape=point, width=0.01, height=0.01]", + mid[0], mid[1] + )?; + writeln!(f, "{a} -> edge_{id} [arrowhead=none]")?; + writeln!(f, "edge_{id} -> {b} [label=\"{id}\"]")?; + + if opt.twin { + writeln!(f, "edge_{id} -> edge_{twin_id} [color=\"red\"]")?; + } + + if opt.next { + writeln!( + f, + "edge_{id} -> edge_{} [color=\"green\"]", + h.next.unwrap().borrow(&dcel.token).id.unwrap() + )?; + } + + if opt.prev { + writeln!( + f, + "edge_{id} -> edge_{} [color=\"blue\"]", + h.prev.unwrap().borrow(&dcel.token).id.unwrap() + )?; + } + } + } + + writeln!(f, "}}") +} + +impl_debug!(i32); + +struct DisplayFn(T); +impl) -> fmt::Result> fmt::Display for DisplayFn { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + self.0(f) + } +} + +fn main() { + GhostToken::new(|token| { + let alloc = DcelAllocator::default(); + let mut dcel = Dcel::new(token, &alloc); + + let h0 = dcel.mevvls([("S", [0, 0]), ("E", [9, 0])]).0; + let h2 = dcel.mve(h0, ("P1", [6, 0])).unwrap().0; + dcel.mve(h2, ("P2", [3, 0])).unwrap(); + + dcel.mev(h0.borrow(&dcel.token).origin.unwrap(), ("B", [0, 3])); + + print!( + "{}", + DisplayFn(|f: &mut fmt::Formatter<'_>| dcel_write_dot( + &dcel, + f, + DcelDotOptions { + prev: false, + next: true, + twin: false, + } + )) + ); + + /* + print!( + "{}", + DisplayFn(|f: &mut fmt::Formatter<'_>| { + for v in dcel.vertices.elements.iter() { + DcelDebug::fmt(v, true, &dcel.token, f)?; + } + + for h in dcel.half_edges.elements.iter() { + DcelDebug::fmt(h, true, &dcel.token, f)?; + } + + Ok(()) + }) + );*/ + }); +} -- cgit v1.2.3