arcweight 0.3.0

//! Core semiring traits for weight types.
//!
//! This module defines the fundamental algebraic abstractions for FST weight systems.
//! The traits here form the foundation for all semiring implementations and enable
//! generic algorithms that work across different weight types.
//!
//! # Overview
//!
//! The core traits are:
//!
//! - [`Semiring`]: Base trait for all weight types with $`\oplus`$ and $`\otimes`$ operations
//! - [`SemiringProperties`]: Characterizes algebraic properties for algorithm optimization
//! - [`DivisibleSemiring`]: Adds division operation for weight pushing
//! - [`StarSemiring`]: Adds Kleene closure for epsilon removal
//! - [`NaturallyOrderedSemiring`]: Provides compatible ordering
//! - [`InvertibleSemiring`]: Provides multiplicative inverses
//!
//! # References
//!
//! - Kuich, W., & Salomaa, A. (1986). *Semirings, Automata, Languages*. EATCS Monographs
//!   on Theoretical Computer Science, Vol. 5. Springer-Verlag.
//!
//! - Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems.
//!   *Journal of Automata, Languages and Combinatorics*, 7(3), 321–350.

use core::fmt::{Debug, Display};
use core::ops::{Add, Mul};
use num_traits::{One, Zero};

/// Core semiring trait defining algebraic operations for weights.
///
/// A **semiring** is an algebraic structure $`(K, \oplus, \otimes, \bar{0}, \bar{1})`$ that
/// generalizes arithmetic while relaxing some requirements. In the context of weighted
/// FSTs, semirings provide the mathematical framework for combining weights along paths
/// and across alternative paths.
///
/// # Mathematical Definition
///
/// A semiring consists of:
/// - A set $`K`$ of elements (weights)
/// - Binary operation $`\oplus : K \times K \to K`$ (addition, combining alternatives)
/// - Binary operation $`\otimes : K \times K \to K`$ (multiplication, extending paths)
/// - Additive identity $`\bar{0} \in K`$ (represents impossibility or "no path")
/// - Multiplicative identity $`\bar{1} \in K`$ (represents free/zero-cost transition)
///
/// # Semiring Axioms
///
/// For all $`a, b, c \in K`$:
///
/// 1. **$(K, \oplus, \bar{0})$ is a commutative monoid:**
///    - Associativity: $`(a \oplus b) \oplus c = a \oplus (b \oplus c)`$
///    - Commutativity: $`a \oplus b = b \oplus a`$
///    - Identity: $`a \oplus \bar{0} = \bar{0} \oplus a = a`$
///
/// 2. **$(K, \otimes, \bar{1})$ is a monoid:**
///    - Associativity: $`(a \otimes b) \otimes c = a \otimes (b \otimes c)`$
///    - Identity: $`a \otimes \bar{1} = \bar{1} \otimes a = a`$
///
/// 3. **$\otimes$ distributes over $\oplus$:**
///    - Left: $`a \otimes (b \oplus c) = (a \otimes b) \oplus (a \otimes c)`$
///    - Right: $`(a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c)`$
///
/// 4. **$\bar{0}$ is an annihilator for $\otimes$:**
///    - $`a \otimes \bar{0} = \bar{0} \otimes a = \bar{0}`$
///
/// # Implementation Guidelines
///
/// When implementing a custom semiring:
///
/// 1. **Verify all semiring axioms** are satisfied (associativity, commutativity of $`\oplus`$,
///    distributivity, identity elements, annihilation)
/// 2. **Use efficient implementations** for `plus()` and `times()` as they are called frequently
/// 3. **Override `approx_eq()`** for floating-point weights to handle numerical precision
/// 4. **Set appropriate `SemiringProperties`** to enable algorithm optimizations
/// 5. **Consider numerical stability** for probabilistic semirings (use log domain when needed)
///
/// # Examples
///
/// ## Using Existing Semirings
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // Tropical semiring for shortest path
/// let w1 = TropicalWeight::new(2.5);
/// let w2 = TropicalWeight::new(1.8);
/// let sum = w1.plus(&w2);      // min(2.5, 1.8) = 1.8
/// let product = w1.times(&w2); // 2.5 + 1.8 = 4.3
///
/// // Boolean semiring for recognition
/// let b1 = BooleanWeight::one();  // true
/// let b2 = BooleanWeight::zero(); // false
/// let or_result = b1.plus(&b2);   // true OR false = true
/// let and_result = b1.times(&b2); // true AND false = false
/// ```
///
/// ## Custom Semiring Implementation
///
/// ```rust
/// use arcweight::prelude::*;
/// use num_traits::{Zero, One};
/// use std::ops::{Add, Mul};
/// use std::fmt;
///
/// // Lexicographic semiring (primary_cost, secondary_count)
/// #[derive(Debug, Clone, PartialEq, PartialOrd, Eq, Ord, Hash)]
/// pub struct LexWeight {
///     cost: u32,  // Using u32 for total ordering
///     count: u32,
/// }
///
/// impl fmt::Display for LexWeight {
///     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
///         write!(f, "({}, {})", self.cost, self.count)
///     }
/// }
///
/// impl Add for LexWeight {
///     type Output = Self;
///     fn add(self, other: Self) -> Self {
///         self.plus(&other)
///     }
/// }
///
/// impl Mul for LexWeight {
///     type Output = Self;
///     fn mul(self, other: Self) -> Self {
///         self.times(&other)
///     }
/// }
///
/// impl Zero for LexWeight {
///     fn zero() -> Self {
///         Self { cost: u32::MAX, count: 0 }  // Infinite cost for zero
///     }
///     
///     fn is_zero(&self) -> bool {
///         self.cost == u32::MAX
///     }
/// }
///
/// impl One for LexWeight {
///     fn one() -> Self {
///         Self { cost: 0, count: 0 }  // Zero cost for identity
///     }
/// }
///
/// impl Semiring for LexWeight {
///     type Value = (u32, u32);
///     
///     fn new(value: Self::Value) -> Self {
///         Self { cost: value.0, count: value.1 }
///     }
///     
///     fn value(&self) -> &Self::Value {
///         // In practice this would store a tuple field
///         unimplemented!("Would need tuple storage for this")
///     }
///     
///     fn plus(&self, other: &Self) -> Self {
///         // Lexicographic minimum
///         if self.cost < other.cost ||
///            (self.cost == other.cost && self.count <= other.count) {
///             self.clone()
///         } else {
///             other.clone()
///         }
///     }
///     
///     fn times(&self, other: &Self) -> Self {
///         Self {
///             cost: self.cost + other.cost,
///             count: self.count + other.count,
///         }
///     }
///     
///     fn properties() -> SemiringProperties {
///         SemiringProperties {
///             left_semiring: true,
///             right_semiring: true,
///             commutative: true,
///             idempotent: false,
///             path: false,
///         }
///     }
///     
///     fn approx_eq(&self, other: &Self, _epsilon: f64) -> bool {
///         self == other
///     }
/// }
///
/// // Example usage
/// let w1 = LexWeight { cost: 5, count: 2 };
/// let w2 = LexWeight { cost: 3, count: 1 };
/// let sum = w1.plus(&w2);  // (3, 1) - lexicographically smaller
/// let product = w1.times(&w2);  // (8, 3) - costs and counts add
/// assert_eq!(sum, w2);
/// assert_eq!(product.cost, 8);
/// ```
///
/// # Common Semirings
///
/// - **[`TropicalWeight`]:** Min-plus algebra for shortest paths
/// - **[`LogWeight`]:** Log semiring for probabilistic computations  
/// - **[`BooleanWeight`]:** Boolean algebra for recognition
/// - **[`ProbabilityWeight`]:** Standard probability semiring
///
/// # Performance Considerations
///
/// - **In-place operations:** Use `plus_assign()` and `times_assign()` when possible
/// - **Numerical stability:** Use [`LogWeight`] instead of [`ProbabilityWeight`] for small probabilities
/// - **Custom semirings:** Profile addition and multiplication operations as they're called frequently
///
/// # See Also
///
/// - [`DivisibleSemiring`] for semirings supporting division
/// - [`StarSemiring`] for semirings supporting Kleene closure
/// - [`NaturallyOrderedSemiring`] for semirings with compatible ordering
/// - [`InvertibleSemiring`] for semirings with multiplicative inverses
///
/// # References
///
/// - Kuich, W., & Salomaa, A. (1986). *Semirings, Automata, Languages*. EATCS Monographs
///   on Theoretical Computer Science, Vol. 5. Springer-Verlag.
///
/// - Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems.
///   *Journal of Automata, Languages and Combinatorics*, 7(3), 321–350.
///
/// [`TropicalWeight`]: crate::semiring::TropicalWeight
/// [`LogWeight`]: crate::semiring::LogWeight
/// [`BooleanWeight`]: crate::semiring::BooleanWeight
/// [`ProbabilityWeight`]: crate::semiring::ProbabilityWeight
pub trait Semiring:
    Clone
    + Debug
    + Display
    + PartialEq
    + PartialOrd
    + Add<Output = Self>
    + Mul<Output = Self>
    + Zero
    + One
    + Send
    + Sync
    + 'static
{
    /// Type of the underlying value
    type Value: Clone + Debug + PartialEq + PartialOrd;

    /// Create a new weight from a value
    fn new(value: Self::Value) -> Self;

    /// Get the underlying value
    fn value(&self) -> &Self::Value;

    /// Semiring addition (⊕)
    fn plus(&self, other: &Self) -> Self {
        self.clone() + other.clone()
    }

    /// Semiring multiplication (⊗)
    fn times(&self, other: &Self) -> Self {
        self.clone() * other.clone()
    }

    /// In-place semiring addition
    fn plus_assign(&mut self, other: &Self) {
        *self = self.plus(other);
    }

    /// In-place semiring multiplication  
    fn times_assign(&mut self, other: &Self) {
        *self = self.times(other);
    }

    /// Check if weight is zero (additive identity)
    fn is_zero(&self) -> bool {
        self == &Self::zero()
    }

    /// Check if weight is one (multiplicative identity)
    fn is_one(&self) -> bool {
        self == &Self::one()
    }

    /// Semiring properties
    fn properties() -> SemiringProperties {
        SemiringProperties::default()
    }

    /// Approximate equality for floating-point weights
    fn approx_eq(&self, other: &Self, _epsilon: f64) -> bool {
        self == other
    }
}

/// Properties of a semiring that determine algorithmic optimizations and guarantees.
///
/// These properties characterize the mathematical structure of a semiring and enable
/// algorithm implementers to choose appropriate optimizations, select efficient data
/// structures, and guarantee correctness of iterative procedures.
///
/// # Mathematical Properties
///
/// ## Distributivity Properties
///
/// - **Left semiring:** Multiplication distributes from the left:
///   $`(a \oplus b) \otimes c = (a \otimes c) \oplus (b \otimes c)`$
/// - **Right semiring:** Multiplication distributes from the right:
///   $`c \otimes (a \oplus b) = (c \otimes a) \oplus (c \otimes b)`$
///
/// Most practical semirings are both left and right semirings (true semirings).
///
/// ## Optimization Properties
///
/// - **Commutative:** Multiplication order doesn't matter: $`a \otimes b = b \otimes a`$
/// - **Idempotent:** Addition is idempotent: $`a \oplus a = a`$
/// - **Path property:** Addition selects one operand: $`a \oplus b \in \{a, b\}`$
///
/// # Algorithmic Implications
///
/// ## Idempotent Semirings
/// Enable optimization in shortest-path algorithms:
/// - **Convergence:** Guarantee that iterative algorithms terminate
/// - **Memoization:** Safe to cache intermediate results
/// - **Pruning:** Can eliminate dominated alternatives early
///
/// ## Path Property
/// Ensures that algorithms find actual optimal solutions:
/// - **Single path:** Addition selects rather than combines
/// - **Optimization:** Enables shortest-path semantics
/// - **Determinism:** Reproducible results with consistent tie-breaking
///
/// ## Commutativity
/// Allows reordering optimizations:
/// - **Parallel computation:** Operations can be reordered safely
/// - **Memory layout:** Can optimize for cache locality
/// - **Batch processing:** Can group operations efficiently
///
/// # Examples by Semiring Type
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // Tropical: idempotent, path property, commutative
/// let props = TropicalWeight::properties();
/// assert!(props.idempotent);  // min(a, a) = a
/// assert!(props.path);        // min(a, b) ∈ {a, b}
/// assert!(props.commutative); // a + b = b + a
///
/// // Boolean: idempotent, path property, commutative  
/// let props = BooleanWeight::properties();
/// assert!(props.idempotent);  // a ∨ a = a
/// assert!(props.path);        // a ∨ b ∈ {a, b}
/// assert!(props.commutative); // a ∧ b = b ∧ a
///
/// // Probability: NOT idempotent, NOT path property, commutative
/// let props = ProbabilityWeight::properties();
/// assert!(!props.idempotent); // p + p ≠ p (usually)
/// assert!(!props.path);       // p + q ∉ {p, q} (usually)
/// assert!(props.commutative); // p × q = q × p
/// ```
///
/// # Performance Optimization Guidelines
///
/// ## For Idempotent Semirings
/// - Use hash-based duplicate elimination
/// - Implement early termination in iterative algorithms
/// - Cache results of expensive computations
///
/// ## For Path Property Semirings  
/// - Implement efficient priority queues for shortest-path algorithms
/// - Use deterministic tie-breaking for reproducible results
/// - Optimize for single-path extraction rather than path enumeration
///
/// ## For Commutative Semirings
/// - Reorder operations for numerical stability
/// - Use SIMD instructions for batch operations
/// - Optimize memory access patterns
///
/// # See Also
///
/// - [`Semiring::properties`] method for querying these properties
/// - FST algorithms that leverage these properties for optimization
///
/// # References
///
/// - Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems.
///   *Journal of Automata, Languages and Combinatorics*, 7(3), 321–350.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct SemiringProperties {
    /// Left semiring: (a ⊕ b) ⊗ c = (a ⊗ c) ⊕ (b ⊗ c)
    pub left_semiring: bool,
    /// Right semiring: c ⊗ (a ⊕ b) = (c ⊗ a) ⊕ (c ⊗ b)
    pub right_semiring: bool,
    /// Commutative: a ⊗ b = b ⊗ a
    pub commutative: bool,
    /// Idempotent: a ⊕ a = a
    pub idempotent: bool,
    /// Path property: a ⊕ b ∈ {a, b}
    pub path: bool,
}

impl Default for SemiringProperties {
    fn default() -> Self {
        Self {
            left_semiring: true,
            right_semiring: true,
            commutative: false,
            idempotent: false,
            path: false,
        }
    }
}

/// Trait for weights that can be divided.
///
/// A **divisible semiring** supports a division operation, enabling specialized
/// algorithms like weight pushing and composition optimization. The division
/// operation is the partial inverse of multiplication.
///
/// # Mathematical Definition
///
/// For a divisible semiring, if $`a \otimes b = c`$, then `c.divide(&b) = Some(a)`
/// (when the division is defined).
///
/// Division may be undefined when:
/// - Dividing by zero ($`\bar{0}`$)
/// - The result would be outside the semiring's domain
///
/// # Examples
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // Tropical semiring supports division
/// let a = TropicalWeight::new(5.0);
/// let b = TropicalWeight::new(2.0);
/// let c = a.times(&b); // 5.0 + 2.0 = 7.0
///
/// // Division: c / b = a
/// if let Some(result) = c.divide(&b) {
///     assert_eq!(result, a); // 7.0 - 2.0 = 5.0
/// }
/// ```
///
/// # See Also
///
/// - [`TropicalWeight`] implements this trait (division is subtraction)
/// - [`LogWeight`] implements this trait (division is subtraction in log space)
/// - [`ProbabilityWeight`] implements this trait (standard division)
/// - [`BooleanWeight`] does NOT implement this (division not meaningful)
///
/// # References
///
/// - Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems.
///   *Journal of Automata, Languages and Combinatorics*, 7(3), 321–350.
///
/// [`TropicalWeight`]: crate::semiring::TropicalWeight
/// [`LogWeight`]: crate::semiring::LogWeight
/// [`ProbabilityWeight`]: crate::semiring::ProbabilityWeight
/// [`BooleanWeight`]: crate::semiring::BooleanWeight
pub trait DivisibleSemiring: Semiring {
    /// Division operation
    fn divide(&self, other: &Self) -> Option<Self>;
}

/// Trait for weights that support star operation (Kleene closure).
///
/// The **star semiring** enables Kleene closure operations, which compute the infinite
/// sum representing all possible path repetitions. This is essential for epsilon
/// removal algorithms and cyclic path analysis in FSTs.
///
/// # Mathematical Definition
///
/// The **Kleene star** (or closure) of a weight $`w`$ is defined as:
///
/// $`w^* = \bigoplus_{i=0}^{\infty} w^i = \bar{1} \oplus w \oplus w^2 \oplus w^3 \oplus \cdots`$
///
/// For this to be well-defined, the semiring must be **k-closed**, meaning the
/// infinite sum converges (either finitely or to a limit).
///
/// ## Convergence Conditions
///
/// Different semirings have different convergence properties:
///
/// - **Tropical:** $`w^* = \bar{1}`$ for $`w \geq 0`$ (converges immediately)
/// - **Boolean:** $`w^* = \bar{1}`$ for all $`w`$ (always converges)
/// - **Probability:** $`w^* = \frac{1}{1-w}`$ for $`w < 1`$ (geometric series)
///
/// # Examples
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // Boolean semiring: w* = true for any w ≠ false
/// let w = BooleanWeight::one();
/// let star = w.star(); // Always true (can reach via 0 or more steps)
///
/// // Note: TropicalWeight does not implement StarSemiring in this implementation
/// // Tropical star operation requires additional mathematical considerations
/// ```
///
/// # Applications
///
/// - **Closure algorithms:** Computing transitive closure of FSTs
/// - **Cycle analysis:** Finding optimal paths through cycles
/// - **Regular expression:** Implementing Kleene star operator
///
/// # See Also
///
/// - [`BooleanWeight`] implements this trait
/// - [`TropicalWeight`] implements this trait
/// - [`ProbabilityWeight`] implements this trait
///
/// # References
///
/// - Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems.
///   *Journal of Automata, Languages and Combinatorics*, 7(3), 321–350.
///
/// - Kuich, W., & Salomaa, A. (1986). *Semirings, Automata, Languages*. Chapter 4:
///   "The algebraic theory of regular expressions." Springer-Verlag.
///
/// [`BooleanWeight`]: crate::semiring::BooleanWeight
/// [`TropicalWeight`]: crate::semiring::TropicalWeight
/// [`ProbabilityWeight`]: crate::semiring::ProbabilityWeight
pub trait StarSemiring: Semiring {
    /// Star operation: w* = 1 ⊕ w ⊕ w² ⊕ ...
    fn star(&self) -> Self;
}

/// Trait for semirings with natural ordering compatible with semiring operations.
///
/// A **naturally ordered semiring** has a partial order $`\leq`$ that is compatible with
/// both addition and multiplication operations. This ordering enables efficient
/// shortest-path algorithms (like Dijkstra's) and provides convergence guarantees
/// for iterative procedures.
///
/// # Mathematical Definition
///
/// A semiring $`(K, \oplus, \otimes, \bar{0}, \bar{1})`$ is naturally ordered if there
/// exists a partial order $`\leq`$ such that for all $`a, b, c \in K`$:
///
/// 1. **Compatibility with $\oplus$:**
///    - $`a \leq a \oplus b`$ and $`b \leq a \oplus b`$
///
/// 2. **Monotonicity of $\oplus$:**
///    - If $`a \leq b`$, then $`a \oplus c \leq b \oplus c`$
///
/// 3. **Monotonicity of $\otimes$:**
///    - If $`a \leq b`$, then $`a \otimes c \leq b \otimes c`$ and $`c \otimes a \leq c \otimes b`$
///
/// # Algorithmic Benefits
///
/// Natural ordering enables several important algorithmic optimizations:
/// - **Monotonic algorithms:** Shortest-path algorithms maintain ordering invariants
/// - **Early termination:** Can stop when optimal solution is proven
/// - **Priority queues:** Efficient implementation of Dijkstra's algorithm variants
/// - **Convergence proofs:** Mathematical guarantees for iterative procedures
///
/// # Examples
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // Tropical semiring is naturally ordered by ≤ on real numbers
/// let w1 = TropicalWeight::new(2.0);
/// let w2 = TropicalWeight::new(3.0);
/// assert!(w1 <= w2);  // 2.0 ≤ 3.0
///
/// // Addition preserves ordering: min(2,3) = 2 ≤ max(2,3) = 3
/// let sum = w1.plus(&w2);
/// assert!(sum <= w1 && sum <= w2);  // min(a,b) ≤ a,b
///
/// // Boolean semiring is naturally ordered by false ≤ true  
/// let false_w = BooleanWeight::zero();
/// let true_w = BooleanWeight::one();
/// assert!(false_w <= true_w);
/// ```
///
/// # Implementation Requirements
///
/// Types implementing this trait must:
/// 1. Implement [`Ord`] with total ordering compatible with semiring structure
/// 2. Ensure ordering is preserved by semiring operations
/// 3. Provide efficient comparison operations for algorithm performance
///
/// # See Also
///
/// - [`TropicalWeight`] implements this trait
/// - [`BooleanWeight`] implements this trait
/// - [`MinWeight`] and [`MaxWeight`] implement this trait
/// - Shortest-path algorithms that require natural ordering
///
/// # References
///
/// - Mohri, M. (2002). Semiring frameworks and algorithms for shortest-distance problems.
///   *Journal of Automata, Languages and Combinatorics*, 7(3), 321–350.
///   Section 3: "Naturally ordered semirings."
///
/// [`TropicalWeight`]: crate::semiring::TropicalWeight
/// [`BooleanWeight`]: crate::semiring::BooleanWeight
/// [`MinWeight`]: crate::semiring::MinWeight
/// [`MaxWeight`]: crate::semiring::MaxWeight
pub trait NaturallyOrderedSemiring: Semiring + Ord {}

/// Trait for semirings that support multiplicative inverse operations.
///
/// An **invertible semiring** provides multiplicative inverses for non-zero elements,
/// enabling division-like operations and supporting algorithms that require
/// "undoing" multiplication operations. This is particularly useful for weight
/// pushing, normalization, and certain optimization procedures.
///
/// # Mathematical Definition
///
/// For an invertible semiring, each non-zero element $`a`$ has a multiplicative
/// inverse $`a^{-1}`$ such that:
///
/// $`a \otimes a^{-1} = a^{-1} \otimes a = \bar{1}`$
///
/// The zero element $`\bar{0}`$ typically has no inverse (division by zero is undefined).
///
/// # Relationship to Divisible Semirings
///
/// Invertible semirings are stronger than divisible semirings:
/// - **Divisible:** Can divide when the result exists  
/// - **Invertible:** Every element has an inverse (multiplicative group structure)
///
/// Many practical semirings are divisible but not invertible (e.g., tropical semiring).
///
/// # Applications
///
/// Invertible semirings enable specialized algorithms:
/// - **Weight pushing:** Redistributing weights for normalization
/// - **Matrix operations:** Implementing linear algebra over semirings
/// - **Formal series:** Manipulating power series with semiring coefficients
/// - **Constraint solving:** Solving systems of semiring equations
///
/// # Examples
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // RealWeight implements InvertibleSemiring for real number arithmetic
/// let a = RealWeight::new(2.0);
/// let b = RealWeight::new(0.5);
///
/// // Multiplicative inverses exist for non-zero elements
/// if let Some(inv_a) = a.inverse() {
///     // inv_a is 0.5, since 2.0 * 0.5 = 1.0
///     let identity = a.times(&inv_a);
///     assert_eq!(identity, RealWeight::one());
/// }
///
/// if let Some(inv_b) = b.inverse() {
///     // inv_b is 2.0, since 0.5 * 2.0 = 1.0
///     let identity = b.times(&inv_b);
///     assert_eq!(identity, RealWeight::one());
/// }
///
/// // Zero element has no inverse
/// let zero = RealWeight::zero();
/// assert_eq!(zero.inverse(), None);
/// ```
///
/// # Implementation Considerations
///
/// When implementing this trait:
/// 1. **Numerical stability:** Handle floating-point precision issues
/// 2. **Zero handling:** Return `None` for zero elements  
/// 3. **Overflow protection:** Guard against division by very small numbers
/// 4. **Performance:** Optimize for common cases (powers of 2, etc.)
///
/// # Mathematical Properties
///
/// Invertible semirings often have additional structure:
/// - **Group property:** Non-zero elements form a multiplicative group
/// - **Field-like:** May approach field semantics with additive inverses
/// - **Unique factorization:** Enable canonical decompositions
///
/// # See Also
///
/// - [`DivisibleSemiring`] for weaker division operations
/// - [`RealWeight`] implements this trait
///
/// # References
///
/// - Kuich, W., & Salomaa, A. (1986). *Semirings, Automata, Languages*. Chapter 1:
///   "Semirings and formal power series." Springer-Verlag.
///
/// [`RealWeight`]: crate::semiring::RealWeight
pub trait InvertibleSemiring: Semiring {
    /// Compute multiplicative inverse
    ///
    /// Returns `Some(inverse)` if the inverse exists, `None` for zero element
    /// or if the inverse cannot be computed (e.g., numerical instability).
    ///
    /// # Mathematical Property
    ///
    /// If `Some(inv) = a.inverse()`, then `a.times(&inv)` should equal `Self::one()`.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use arcweight::prelude::*;
    ///
    /// // RealWeight provides full InvertibleSemiring functionality
    /// let a = RealWeight::new(2.0);
    /// let b = RealWeight::new(0.5);
    ///
    /// // Multiplicative inverses exist for non-zero elements
    /// if let Some(inv_a) = a.inverse() {
    ///     // inv_a is 0.5, since 2.0 * 0.5 = 1.0
    ///     let identity = a.times(&inv_a);
    ///     assert_eq!(identity, RealWeight::one());
    /// }
    ///
    /// if let Some(inv_b) = b.inverse() {
    ///     // inv_b is 2.0, since 0.5 * 2.0 = 1.0
    ///     let identity = b.times(&inv_b);
    ///     assert_eq!(identity, RealWeight::one());
    /// }
    ///
    /// // Zero element has no inverse
    /// let zero = RealWeight::zero();
    /// assert_eq!(zero.inverse(), None);
    ///
    /// // Applications: weight normalization
    /// let weights = vec![
    ///     RealWeight::new(4.0),
    ///     RealWeight::new(2.0),
    ///     RealWeight::new(8.0),
    /// ];
    ///
    /// // Normalize by dividing by total (using inverses)
    /// let total = weights.iter().fold(RealWeight::zero(), |acc, w| acc.plus(w));
    /// if let Some(inv_total) = total.inverse() {
    ///     let normalized: Vec<_> = weights.iter()
    ///         .map(|w| w.times(&inv_total))
    ///         .collect();
    ///     
    ///     // Verify normalization: sum should equal 1.0
    ///     let sum = normalized.iter().fold(RealWeight::zero(), |acc, w| acc.plus(w));
    ///     assert!((sum.as_f64() - 1.0).abs() < 1e-10);
    /// }
    /// ```
    fn inverse(&self) -> Option<Self>;
}

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

    #[test]
    fn test_semiring_properties_default() {
        let props = SemiringProperties::default();
        assert!(props.left_semiring);
        assert!(props.right_semiring);
        assert!(!props.commutative);
        assert!(!props.idempotent);
        assert!(!props.path);
    }

    #[test]
    fn test_tropical_weight_semiring() {
        let w1 = TropicalWeight::new(2.0);
        let w2 = TropicalWeight::new(3.0);
        let _w3 = TropicalWeight::new(1.0);

        // Test semiring addition (min operation)
        let sum = w1.plus(&w2);
        assert_eq!(sum, w1); // min(2.0, 3.0) = 2.0

        // Test semiring multiplication (addition operation)
        let product = w1.times(&w2);
        assert_eq!(product, TropicalWeight::new(5.0)); // 2.0 + 3.0 = 5.0

        // Test zero element
        let zero = TropicalWeight::zero();
        assert!(Semiring::is_zero(&zero));
        assert_eq!(w1.plus(&zero), w1);
        assert_eq!(w1.times(&zero), zero);

        // Test one element
        let one = TropicalWeight::one();
        assert!(Semiring::is_one(&one));
        assert_eq!(w1.times(&one), w1);

        // Test properties
        let props = TropicalWeight::properties();
        assert!(props.idempotent);
        assert!(props.path);
        assert!(props.commutative);
    }

    #[test]
    fn test_boolean_weight_semiring() {
        let true_w = BooleanWeight::one();
        let false_w = BooleanWeight::zero();

        // Test semiring addition (OR operation)
        assert_eq!(true_w.plus(&false_w), true_w);
        assert_eq!(false_w.plus(&false_w), false_w);
        assert_eq!(true_w.plus(&true_w), true_w);

        // Test semiring multiplication (AND operation)
        assert_eq!(true_w.times(&false_w), false_w);
        assert_eq!(true_w.times(&true_w), true_w);
        assert_eq!(false_w.times(&false_w), false_w);

        // Test zero and one
        assert!(Semiring::is_zero(&false_w));
        assert!(Semiring::is_one(&true_w));

        // Test properties
        let props = BooleanWeight::properties();
        assert!(props.idempotent);
        assert!(props.path);
        assert!(props.commutative);
    }

    #[test]
    fn test_semiring_axioms_tropical() {
        let a = TropicalWeight::new(1.0);
        let b = TropicalWeight::new(2.0);
        let c = TropicalWeight::new(3.0);
        let zero = TropicalWeight::zero();
        let one = TropicalWeight::one();

        // Test associativity of addition: (a + b) + c = a + (b + c)
        let left = a.plus(&b).plus(&c);
        let right = a.plus(&b.plus(&c));
        assert_eq!(left, right);

        // Test commutativity of addition: a + b = b + a
        assert_eq!(a.plus(&b), b.plus(&a));

        // Test additive identity: a + 0 = a
        assert_eq!(a.plus(&zero), a);

        // Test associativity of multiplication: (a * b) * c = a * (b * c)
        let left = a.times(&b).times(&c);
        let right = a.times(&b.times(&c));
        assert_eq!(left, right);

        // Test multiplicative identity: a * 1 = a
        assert_eq!(a.times(&one), a);

        // Test annihilation: a * 0 = 0
        assert_eq!(a.times(&zero), zero);
    }

    #[test]
    fn test_in_place_operations() {
        let mut w = TropicalWeight::new(5.0);
        let other = TropicalWeight::new(3.0);

        // Test plus_assign
        w.plus_assign(&other);
        assert_eq!(w, TropicalWeight::new(3.0)); // min(5.0, 3.0) = 3.0

        // Test times_assign
        w.times_assign(&other);
        assert_eq!(w, TropicalWeight::new(6.0)); // 3.0 + 3.0 = 6.0
    }

    #[test]
    fn test_approx_eq() {
        let w1 = TropicalWeight::new(1.0);
        let w2 = TropicalWeight::new(1.0);
        let w3 = TropicalWeight::new(2.0);

        // Test exact equality (same values)
        assert!(w1.approx_eq(&w2, f64::EPSILON));
        assert!(!w1.approx_eq(&w3, 0.0));

        // Default implementation just uses regular equality
        assert!(w1.approx_eq(&w2, 1e-6));
        assert!(!w1.approx_eq(&w3, 1e-6));
    }

    #[test]
    fn test_divisible_semiring_tropical() {
        let a = TropicalWeight::new(5.0);
        let b = TropicalWeight::new(2.0);
        let c = a.times(&b); // 5.0 + 2.0 = 7.0

        // Test division: c / b should equal a
        let result = c.divide(&b).unwrap();
        assert_eq!(result, a); // 7.0 - 2.0 = 5.0

        // Test division by zero should return None
        let zero = TropicalWeight::zero();
        assert!(c.divide(&zero).is_none());
    }

    #[test]
    fn test_star_semiring_boolean() {
        let true_w = BooleanWeight::one();
        let false_w = BooleanWeight::zero();

        // Star of true should be true (can reach in 0 or more steps)
        assert_eq!(true_w.star(), true_w);

        // Star of false should be true (can reach in 0 steps via identity)
        assert_eq!(false_w.star(), true_w);
    }
}