delaunay 0.8.0

D-dimensional Delaunay triangulations and convex hulls in Rust, with exact predicates, deterministic degeneracy handling, explicit topology validation, and bistellar flips for finite point sets.
Documentation 
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

//! TDS rollback snapshots and transactions.

#![forbid(unsafe_code)]

use crate::core::tds::Tds;
use std::ptr;

/// Owner abstraction for rollback guards that snapshot a canonical [`Tds`].
pub(crate) trait TdsRollbackOwner<U, V, const D: usize> {
    /// Returns the canonical [`Tds`] that a rollback transaction snapshots.
    fn rollback_tds(&self) -> &Tds<U, V, D>;

    /// Returns the canonical [`Tds`] that a rollback transaction restores.
    fn rollback_tds_mut(&mut self) -> &mut Tds<U, V, D>;
}

impl<U, V, const D: usize> TdsRollbackOwner<U, V, D> for Tds<U, V, D> {
    fn rollback_tds(&self) -> &Self {
        self
    }

    fn rollback_tds_mut(&mut self) -> &mut Self {
        self
    }
}

/// Owned TDS rollback snapshot kept private behind owner-bound guards.
struct TdsRollbackSnapshot<U, V, const D: usize> {
    owner: *const (),
    snapshot: Tds<U, V, D>,
}

impl<U, V, const D: usize> TdsRollbackSnapshot<U, V, D>
where
    U: Clone,
    V: Clone,
{
    /// Captures a rollback snapshot with rollback-preserving identity semantics.
    fn capture(tds: &Tds<U, V, D>) -> Self {
        Self {
            owner: ptr::from_ref(tds).cast::<()>(),
            snapshot: tds.clone_for_rollback(),
        }
    }

    /// Restores `tds` from this snapshot while preserving rollback identity.
    ///
    /// # Panics
    ///
    /// Panics if `tds` is not the canonical owner location this snapshot was
    /// captured from.
    fn restore_to(&self, tds: &mut Tds<U, V, D>) {
        let target_owner = ptr::from_ref(tds).cast::<()>();
        assert!(
            ptr::eq(self.owner, target_owner),
            "rollback snapshot must be restored to the TDS owner location it was captured from"
        );
        tds.clone_from_for_rollback(&self.snapshot);
    }
}

/// Scoped rollback guard for a mutation that must either commit explicitly or
/// restore the original TDS state.
#[must_use = "rollback transactions restore on drop unless explicitly committed or rolled back"]
pub(crate) struct TdsOwnerRollbackTransaction<'owner, O, U, V, const D: usize>
where
    O: TdsRollbackOwner<U, V, D>,
    U: Clone,
    V: Clone,
{
    owner: &'owner mut O,
    snapshot: TdsRollbackSnapshot<U, V, D>,
    finished: bool,
}

impl<'owner, O, U, V, const D: usize> TdsOwnerRollbackTransaction<'owner, O, U, V, D>
where
    O: TdsRollbackOwner<U, V, D>,
    U: Clone,
    V: Clone,
{
    /// Begins a rollback window by snapshotting the owner's canonical TDS while
    /// retaining runtime identity for cache provenance.
    pub(crate) fn begin(owner: &'owner mut O) -> Self {
        let snapshot = TdsRollbackSnapshot::capture(owner.rollback_tds());
        Self {
            owner,
            snapshot,
            finished: false,
        }
    }

    /// Borrows the mutable owner for a mutation step inside the transaction.
    pub(crate) const fn owner_mut(&mut self) -> &mut O {
        &mut *self.owner
    }

    /// Restores the owner to the saved state while keeping the transaction open
    /// for another attempt.
    pub(crate) fn restore(&mut self) {
        self.snapshot.restore_to(self.owner.rollback_tds_mut());
    }

    /// Commits the mutation, preventing the drop guard from restoring the snapshot.
    pub(crate) fn commit(mut self) {
        self.finished = true;
    }

    /// Restores the snapshot and closes the transaction.
    pub(crate) fn rollback(mut self) {
        self.restore();
        self.finished = true;
    }

    /// Marks the transaction committed for wrapper guards that own their own drop policy.
    pub(crate) const fn commit_in_place(&mut self) {
        self.finished = true;
    }
}

impl<O, U, V, const D: usize> Drop for TdsOwnerRollbackTransaction<'_, O, U, V, D>
where
    O: TdsRollbackOwner<U, V, D>,
    U: Clone,
    V: Clone,
{
    fn drop(&mut self) {
        if !self.finished {
            self.restore();
        }
    }
}

/// Owner-bound rollback guard for functions that mutate a [`Tds`] directly.
pub(crate) type TdsRollbackTransaction<'tds, U, V, const D: usize> =
    TdsOwnerRollbackTransaction<'tds, Tds<U, V, D>, U, V, D>;

impl<U, V, const D: usize> TdsOwnerRollbackTransaction<'_, Tds<U, V, D>, U, V, D>
where
    U: Clone,
    V: Clone,
{
    /// Borrows the mutable TDS for a mutation step inside the transaction.
    pub(crate) const fn tds_mut(&mut self) -> &mut Tds<U, V, D> {
        self.owner_mut()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[should_panic(
        expected = "rollback snapshot must be restored to the TDS owner location it was captured from"
    )]
    fn snapshot_restore_rejects_cross_owner_target() {
        let source: Tds<(), (), 2> = Tds::empty();
        let snapshot = TdsRollbackSnapshot::capture(&source);
        let mut target: Tds<(), (), 2> = Tds::empty();

        snapshot.restore_to(&mut target);
    }
}