delaunay 0.7.8

//! Semantic classification and telemetry for triangulation operations.
//!
//! This module is intentionally **not** about implementation mechanics. It defines:
//! - What operation occurred (taxonomy)
//! - What the outcome was
//! - Lightweight telemetry/flags describing suspicious paths
//!
//! The actual algorithms live under `core::algorithms`.

#![forbid(unsafe_code)]

use crate::core::algorithms::incremental_insertion::InsertionError;
use crate::core::tds::SimplexKey;
use crate::core::validation::TopologyGuarantee;
use crate::repair::{DelaunayCheckPolicy, DelaunayRepairPolicy};

/// Semantic classification of topological modifications to a triangulation.
///
/// These correspond to bistellar (Pachner) move classes, but are not required
/// to be implemented as single atomic flips.
///
/// # Examples
///
/// ```rust
/// use delaunay::prelude::operations::TopologicalOperation;
/// use delaunay::prelude::TopologyGuarantee;
///
/// let op = TopologicalOperation::FacetFlip;
/// assert!(op.is_admissible_under(TopologyGuarantee::Pseudomanifold));
/// ```
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub enum TopologicalOperation {
    /// k = 1 forward: vertex insertion (1 → d+1).
    InsertVertex,
    /// k = 1 inverse: vertex deletion (d+1 → 1).
    DeleteVertex,
    /// k = 2: facet bistellar flip.
    FacetFlip,
    /// k ≥ 3: higher-order cavity flip (typically in higher dimensions).
    CavityFlip,
}

/// Decision outcome for a flip-based Delaunay repair attempt.
///
/// # Examples
///
/// ```rust
/// use delaunay::prelude::operations::{RepairDecision, RepairSkipReason, TopologicalOperation};
/// use delaunay::prelude::TopologyGuarantee;
///
/// let decision = RepairDecision::Skip {
///     reason: RepairSkipReason::Inadmissible {
///         operation: TopologicalOperation::CavityFlip,
///         required: TopologyGuarantee::PLManifold,
///         found: TopologyGuarantee::Pseudomanifold,
///     },
/// };
/// assert!(matches!(decision, RepairDecision::Skip { .. }));
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RepairDecision {
    /// Proceed with flip-based repair.
    Proceed,
    /// Skip repair, with a structured reason.
    Skip {
        /// Reason the repair was skipped.
        reason: RepairSkipReason,
    },
}

/// Reason why flip-based repair was skipped.
///
/// # Examples
///
/// ```rust
/// use delaunay::prelude::operations::RepairSkipReason;
///
/// let reason = RepairSkipReason::PolicyDisabled;
/// assert!(matches!(reason, RepairSkipReason::PolicyDisabled));
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum RepairSkipReason {
    /// Repair policy is disabled for this insertion count.
    PolicyDisabled,
    /// The requested operation is inadmissible under the current topology guarantee.
    Inadmissible {
        /// The operation that was attempted.
        operation: TopologicalOperation,
        /// Required topology guarantee for this operation.
        required: TopologyGuarantee,
        /// Actual topology guarantee.
        found: TopologyGuarantee,
    },
}

impl DelaunayRepairPolicy {
    /// Decide whether a flip-based repair should run, given topology and operation constraints.
    #[must_use]
    pub const fn decide(
        self,
        insertion_count: usize,
        topology: TopologyGuarantee,
        operation: TopologicalOperation,
    ) -> RepairDecision {
        if !self.should_repair(insertion_count) {
            return RepairDecision::Skip {
                reason: RepairSkipReason::PolicyDisabled,
            };
        }

        if !operation.is_admissible_under(topology) {
            return RepairDecision::Skip {
                reason: RepairSkipReason::Inadmissible {
                    operation,
                    required: operation.required_topology(),
                    found: topology,
                },
            };
        }

        RepairDecision::Proceed
    }
}

impl TopologicalOperation {
    /// Returns `true` if this operation requires a PL-manifold topology guarantee.
    #[must_use]
    pub const fn requires_pl_manifold(self) -> bool {
        // Higher-order cavity flips rely on stronger local topology guarantees.
        //
        // Note: k=2/k=3 flips used for Delaunay repair are admissible under the weaker
        // pseudomanifold invariants (facet degree + closed boundary). Callers that need
        // strict PL-manifold guarantees should select `TopologyGuarantee::PLManifold`.
        matches!(self, Self::CavityFlip)
    }

    /// Returns `true` if this operation is admissible under the given topology guarantee.
    #[must_use]
    pub const fn is_admissible_under(self, topology: TopologyGuarantee) -> bool {
        match topology {
            TopologyGuarantee::PLManifold | TopologyGuarantee::PLManifoldStrict => true,
            TopologyGuarantee::Pseudomanifold => !self.requires_pl_manifold(),
        }
    }

    /// Returns the minimum topology guarantee required for this operation.
    #[must_use]
    pub const fn required_topology(self) -> TopologyGuarantee {
        if self.requires_pl_manifold() {
            TopologyGuarantee::PLManifold
        } else {
            TopologyGuarantee::Pseudomanifold
        }
    }
}

/// Result of an insertion attempt.
///
/// # Examples
///
/// ```rust
/// use delaunay::prelude::operations::InsertionResult;
///
/// let result = InsertionResult::default();
/// assert_eq!(result, InsertionResult::Inserted);
/// ```
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum InsertionResult {
    /// The vertex was successfully inserted.
    #[default]
    Inserted,
    /// The vertex was skipped due to duplicate coordinates.
    SkippedDuplicate,
    /// The vertex was skipped due to geometric degeneracy after retries.
    SkippedDegeneracy,
}

/// Statistics about a vertex insertion operation.
///
/// # Examples
///
/// ```rust
/// use delaunay::prelude::operations::{InsertionResult, InsertionStatistics};
///
/// let stats = InsertionStatistics {
///     attempts: 2,
///     simplices_removed_during_repair: 1,
///     result: InsertionResult::Inserted,
/// };
/// assert!(stats.used_perturbation());
/// assert!(stats.success());
/// assert!(!stats.skipped());
/// ```
#[derive(Debug, Clone, Copy, Default)]
pub struct InsertionStatistics {
    /// Number of insertion attempts (1 = success on first try, >1 = needed perturbation)
    pub attempts: usize,
    /// Number of simplices removed during repair
    pub simplices_removed_during_repair: usize,
    /// Result of the insertion attempt
    pub result: InsertionResult,
}

impl InsertionStatistics {
    /// Returns true if perturbation was applied (attempts > 1).
    #[must_use]
    pub const fn used_perturbation(&self) -> bool {
        self.attempts > 1
    }

    /// Returns true if the insertion succeeded.
    #[must_use]
    pub const fn success(&self) -> bool {
        matches!(self.result, InsertionResult::Inserted)
    }

    /// Returns true if the vertex was skipped (any reason).
    #[must_use]
    pub const fn skipped(&self) -> bool {
        matches!(
            self.result,
            InsertionResult::SkippedDuplicate | InsertionResult::SkippedDegeneracy
        )
    }

    /// Returns true if the vertex was skipped due to duplicate coordinates.
    #[must_use]
    pub const fn skipped_duplicate(&self) -> bool {
        matches!(self.result, InsertionResult::SkippedDuplicate)
    }
}

/// Controls whether insertion telemetry records only event counters or also
/// wall-clock timings.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum InsertionTelemetryMode {
    /// Record event counters without starting wall-clock timers.
    CountsOnly,
    /// Record both event counters and wall-clock timings.
    CountsAndTimings,
}

impl InsertionTelemetryMode {
    /// Returns true when the insertion path should start `Instant` timers.
    pub(crate) const fn records_timings(self) -> bool {
        matches!(self, Self::CountsAndTimings)
    }
}

/// Release-visible telemetry for one transactional insertion.
///
/// These counters are intended for aggregate diagnostics rather than stable performance
/// benchmarking. They let batch construction report whether insertion time is dominated by
/// point location, scan fallbacks, local conflict regions, or global exterior-point scans.
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub(crate) struct InsertionTelemetry {
    /// Number of point-location calls performed for this insertion.
    pub locate_calls: usize,
    /// Total facet-walk steps across all point-location calls.
    pub locate_walk_steps_total: usize,
    /// Maximum facet-walk steps taken by a single point-location call.
    pub locate_walk_steps_max: usize,
    /// Number of point-location calls that used the caller-provided hint.
    pub locate_hint_uses: usize,
    /// Number of point-location calls that fell back to a brute-force scan.
    pub locate_scan_fallbacks: usize,
    /// Number of point-location calls that ended inside a simplex.
    pub located_inside: usize,
    /// Number of point-location calls that ended outside the convex hull.
    pub located_outside: usize,
    /// Number of point-location calls that ended on a lower-dimensional feature.
    pub located_on_boundary: usize,

    /// Number of local conflict-region computations observed by insertion.
    pub conflict_region_calls: usize,
    /// Total number of simplices in local conflict regions.
    pub conflict_region_simplices_total: usize,
    /// Maximum number of simplices in a single local conflict region.
    pub conflict_region_simplices_max: usize,
    /// Wall-clock nanoseconds spent computing local conflict regions.
    pub conflict_region_nanos: u64,
    /// Maximum wall-clock nanoseconds spent computing one local conflict region.
    pub conflict_region_nanos_max: u64,

    /// Number of cavity insertion attempts observed by insertion.
    pub cavity_insertion_calls: usize,
    /// Wall-clock nanoseconds spent filling cavities and wiring neighbors.
    pub cavity_insertion_nanos: u64,
    /// Maximum wall-clock nanoseconds spent in one cavity insertion attempt.
    pub cavity_insertion_nanos_max: u64,

    /// Number of hull extension attempts observed by insertion.
    pub hull_extension_calls: usize,
    /// Wall-clock nanoseconds spent extending the convex hull.
    pub hull_extension_nanos: u64,
    /// Maximum wall-clock nanoseconds spent in one hull extension attempt.
    pub hull_extension_nanos_max: u64,

    /// Number of post-insertion topology validations observed by insertion.
    pub topology_validation_calls: usize,
    /// Wall-clock nanoseconds spent in post-insertion topology validation.
    pub topology_validation_nanos: u64,
    /// Maximum wall-clock nanoseconds spent in one post-insertion validation.
    pub topology_validation_nanos_max: u64,

    /// Number of global exterior-point conflict scans.
    pub global_conflict_scans: usize,
    /// Total simplices scanned by global exterior-point conflict scans.
    pub global_conflict_simplices_scanned: usize,
    /// Total simplices found by global exterior-point conflict scans.
    pub global_conflict_simplices_found_total: usize,
    /// Maximum simplices found by a single global exterior-point conflict scan.
    pub global_conflict_simplices_found_max: usize,
    /// Wall-clock nanoseconds spent in global exterior-point conflict scans.
    pub global_conflict_scan_nanos: u64,
}

/// Ephemeral insertion state used by Delaunay triangulations.
#[derive(Clone, Copy, Debug)]
pub(crate) struct DelaunayInsertionState {
    /// Hint for the next `locate()` call (last inserted simplex).
    pub last_inserted_simplex: Option<SimplexKey>,
    /// Policy controlling automatic Delaunay repair (flip-based).
    pub delaunay_repair_policy: DelaunayRepairPolicy,
    /// Policy controlling automatic global Delaunay validation (Level 4).
    pub delaunay_check_policy: DelaunayCheckPolicy,
    /// Count of successful insertions (used to schedule repairs/checks).
    pub delaunay_repair_insertion_count: usize,
    /// When `true` (default), D<4 per-insertion repair falls back to global
    /// `repair_delaunay_with_flips_k2_k3` when the bounded local pass cycles.
    /// Set to `false` for constructions where global repair could disrupt
    /// the triangulation topology (e.g. periodic image-point builds).
    pub use_global_repair_fallback: bool,
}

impl DelaunayInsertionState {
    /// Create a fresh insertion state with default repair policy.
    #[must_use]
    pub const fn new() -> Self {
        Self {
            last_inserted_simplex: None,
            delaunay_repair_policy: DelaunayRepairPolicy::EveryInsertion,
            delaunay_check_policy: DelaunayCheckPolicy::EndOnly,
            delaunay_repair_insertion_count: 0,
            use_global_repair_fallback: true,
        }
    }
}

/// Outcome of a single-vertex insertion attempt.
///
/// This distinguishes between:
/// - A successful insertion (`Inserted`)
/// - An intentionally skipped insertion (`Skipped`) where the triangulation is left unchanged
///   for this vertex (transactional rollback). This can happen for example when:
///   - The input vertex is a duplicate/near-duplicate (skipped immediately)
///   - A retryable geometric degeneracy exhausts all perturbation attempts
///
/// Strict insertion APIs return skipped insertions as `Err(InsertionError)` so
/// callers using `?` cannot miss them. The explicitly named
/// `insert_best_effort_with_statistics` API preserves `Skipped` as an `Ok`
/// outcome for diagnostics and best-effort ingestion. Other non-recoverable
/// structural failures are returned as `Err(InsertionError)` instead (e.g.
/// duplicate UUID).
///
/// # Examples
///
/// ```rust
/// use delaunay::prelude::insertion::InsertionError;
/// use delaunay::prelude::operations::InsertionOutcome;
///
/// let outcome = InsertionOutcome::Skipped {
///     error: InsertionError::DuplicateCoordinates {
///         coordinates: "[0.0, 0.0, 0.0]".to_string(),
///     },
/// };
/// assert!(matches!(outcome, InsertionOutcome::Skipped { .. }));
/// ```
#[derive(Debug, Clone)]
pub enum InsertionOutcome {
    /// The vertex was inserted successfully.
    Inserted {
        /// Key of the inserted vertex.
        vertex_key: crate::core::tds::VertexKey,
        /// Optional simplex key that can be used as a hint for subsequent insertions.
        hint: Option<crate::core::tds::SimplexKey>,
    },
    /// The vertex was intentionally not inserted.
    ///
    /// This covers both immediate skips (e.g. duplicate/near-duplicate coordinates) and skips
    /// after exhausting retry attempts for geometric degeneracies.
    ///
    /// The triangulation is left unchanged for this vertex (transactional rollback).
    Skipped {
        /// The reason the vertex was skipped.
        ///
        /// This may be non-retryable (e.g. [`InsertionError::DuplicateCoordinates`]) or, for
        /// retry-based skips, the last error encountered.
        error: InsertionError,
    },
}

/// Adaptive error-checking on suspicious operations.
///
/// # Examples
///
/// ```rust
/// use delaunay::prelude::operations::SuspicionFlags;
///
/// let flags = SuspicionFlags {
///     perturbation_used: true,
///     neighbor_pointers_rebuilt: true,
///     ..SuspicionFlags::default()
/// };
/// assert!(flags.perturbation_used);
/// assert!(flags.neighbor_pointers_rebuilt);
/// ```
#[derive(Clone, Copy, Debug, Default)]
#[expect(
    clippy::struct_excessive_bools,
    reason = "A small set of boolean flags is clearer here than bitflags or an enum"
)]
pub struct SuspicionFlags {
    /// A perturbation retry was required to resolve a geometric degeneracy.
    pub perturbation_used: bool,

    /// A conflict-region computation returned an empty set for an interior point.
    pub empty_conflict_region: bool,

    /// The insertion fell back to splitting the containing simplex (star-split) to avoid
    /// creating a dangling vertex.
    pub fallback_star_split: bool,

    /// The non-manifold repair loop was entered after insertion/hull extension.
    pub repair_loop_entered: bool,

    /// One or more simplices were removed during non-manifold repair.
    pub simplices_removed: bool,

    /// Neighbor pointers were rebuilt (facet-matched) after topology repair.
    pub neighbor_pointers_rebuilt: bool,
}

impl SuspicionFlags {
    /// Returns `true` if any suspicious condition was observed.
    #[inline]
    #[must_use]
    pub const fn is_suspicious(&self) -> bool {
        self.perturbation_used
            || self.empty_conflict_region
            || self.fallback_star_split
            || self.repair_loop_entered
            || self.simplices_removed
            || self.neighbor_pointers_rebuilt
    }
}

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

    #[test]
    fn test_topological_operation_admissibility() {
        assert!(!TopologicalOperation::FacetFlip.requires_pl_manifold());
        assert!(TopologicalOperation::CavityFlip.requires_pl_manifold());
        assert!(!TopologicalOperation::InsertVertex.requires_pl_manifold());
        assert!(!TopologicalOperation::DeleteVertex.requires_pl_manifold());

        assert!(TopologicalOperation::FacetFlip.is_admissible_under(TopologyGuarantee::PLManifold));
        assert!(
            TopologicalOperation::FacetFlip
                .is_admissible_under(TopologyGuarantee::PLManifoldStrict)
        );
        assert!(
            TopologicalOperation::FacetFlip.is_admissible_under(TopologyGuarantee::Pseudomanifold)
        );

        assert!(
            TopologicalOperation::InsertVertex
                .is_admissible_under(TopologyGuarantee::Pseudomanifold)
        );
    }

    #[test]
    fn test_repair_policy_decide_respects_policy_and_topology() {
        let op = TopologicalOperation::FacetFlip;

        let decision =
            DelaunayRepairPolicy::EveryInsertion.decide(1, TopologyGuarantee::PLManifold, op);
        assert!(matches!(decision, RepairDecision::Proceed));

        let decision =
            DelaunayRepairPolicy::EveryInsertion.decide(0, TopologyGuarantee::PLManifold, op);
        assert!(matches!(
            decision,
            RepairDecision::Skip {
                reason: RepairSkipReason::PolicyDisabled
            }
        ));

        let decision =
            DelaunayRepairPolicy::EveryInsertion.decide(1, TopologyGuarantee::Pseudomanifold, op);
        assert!(matches!(decision, RepairDecision::Proceed));

        let decision = DelaunayRepairPolicy::Never.decide(1, TopologyGuarantee::PLManifold, op);
        assert!(matches!(
            decision,
            RepairDecision::Skip {
                reason: RepairSkipReason::PolicyDisabled
            }
        ));
    }

    #[test]
    fn test_repair_policy_decide_inadmissible_under_pseudomanifold() {
        // CavityFlip requires PLManifold; under Pseudomanifold it should be inadmissible.
        let op = TopologicalOperation::CavityFlip;
        let decision =
            DelaunayRepairPolicy::EveryInsertion.decide(1, TopologyGuarantee::Pseudomanifold, op);
        assert!(matches!(
            decision,
            RepairDecision::Skip {
                reason: RepairSkipReason::Inadmissible {
                    operation: TopologicalOperation::CavityFlip,
                    required: TopologyGuarantee::PLManifold,
                    found: TopologyGuarantee::Pseudomanifold,
                }
            }
        ));
    }

    #[test]
    fn test_required_topology_returns_correct_guarantee() {
        assert_eq!(
            TopologicalOperation::CavityFlip.required_topology(),
            TopologyGuarantee::PLManifold
        );
        assert_eq!(
            TopologicalOperation::FacetFlip.required_topology(),
            TopologyGuarantee::Pseudomanifold
        );
        assert_eq!(
            TopologicalOperation::InsertVertex.required_topology(),
            TopologyGuarantee::Pseudomanifold
        );
        assert_eq!(
            TopologicalOperation::DeleteVertex.required_topology(),
            TopologyGuarantee::Pseudomanifold
        );
    }
}