arcweight 0.3.0

//! # Arc
//!
//! Arc types and traits for weighted finite-state transducers.
//!
//! ## Overview
//!
//! This module provides the fundamental arc representation used throughout
//! the library. Arcs represent weighted transitions between states in a
//! finite-state transducer (FST), forming the edges of the underlying graph.
//!
//! An [`Arc`] consists of four components:
//!
//! | Component | Field | Description |
//! |-----------|-------|-------------|
//! | Input label | `ilabel` | Symbol consumed from input tape |
//! | Output label | `olabel` | Symbol produced on output tape |
//! | Weight | `weight` | Cost or probability of the transition |
//! | Next state | `nextstate` | Target state ID |
//!
//! ## Arc Variants
//!
//! ### Regular Arcs
//!
//! Standard transitions with explicit input/output labels:
//!
//! ```
//! use arcweight::prelude::*;
//!
//! // Transducer arc: transforms input 1 to output 2
//! let arc = Arc::new(1, 2, TropicalWeight::new(0.5), 3);
//! assert_eq!(arc.ilabel, 1);
//! assert_eq!(arc.olabel, 2);
//! ```
//!
//! ### Acceptor Arcs
//!
//! When input and output labels match (common in acceptors):
//!
//! ```
//! use arcweight::prelude::*;
//!
//! // Acceptor arc: consumes and produces symbol 1
//! let arc = Arc::new(1, 1, TropicalWeight::one(), 2);
//! assert_eq!(arc.ilabel, arc.olabel);
//! ```
//!
//! ### Epsilon Arcs
//!
//! Transitions that consume or produce no symbols (label = 0):
//!
//! ```
//! use arcweight::prelude::*;
//!
//! // Full epsilon arc: no input or output symbols
//! let eps = Arc::epsilon(TropicalWeight::new(0.1), 1);
//! assert!(eps.is_epsilon());
//!
//! // Input epsilon: produces output without consuming input
//! let in_eps = Arc::new(0, 5, TropicalWeight::one(), 2);
//! assert!(in_eps.is_epsilon_input());
//! assert!(!in_eps.is_epsilon_output());
//! ```
//!
//! ## Memory Layout
//!
//! Arcs are stored inline with their weight type, making them cache-efficient
//! for common weight types like [`TropicalWeight`] (8 bytes for the weight,
//! 16 bytes total for labels and next state).
//!
//! ## Arc Iterators
//!
//! The [`ArcIterator`] trait provides a common interface for iterating
//! over arcs leaving a state. Different FST implementations provide
//! optimized iterators.
//!
//! ```
//! use arcweight::prelude::*;
//!
//! let mut fst = VectorFst::<TropicalWeight>::new();
//! let s0 = fst.add_state();
//! fst.add_arc(s0, Arc::new(1, 2, TropicalWeight::one(), s0));
//!
//! // Iterate over arcs from state s0
//! for arc in fst.arcs(s0) {
//!     println!("Arc: {} -> {}", arc.ilabel, arc.olabel);
//! }
//! ```
//!
//! ## Examples
//!
//! ### Building an FST with Arcs
//!
//! ```
//! use arcweight::prelude::*;
//!
//! let mut fst = VectorFst::<TropicalWeight>::new();
//! let s0 = fst.add_state();
//! let s1 = fst.add_state();
//! let s2 = fst.add_state();
//!
//! fst.set_start(s0);
//! fst.set_final(s2, TropicalWeight::one());
//!
//! // Chain of arcs forming a path
//! fst.add_arc(s0, Arc::new(1, 10, TropicalWeight::new(0.5), s1));
//! fst.add_arc(s1, Arc::new(2, 20, TropicalWeight::new(0.3), s2));
//! ```
//!
//! ### Arc Comparison and Hashing
//!
//! Arcs implement [`Eq`] and [`Hash`], enabling use in collections:
//!
//! ```
//! use arcweight::prelude::*;
//! use std::collections::HashSet;
//!
//! let mut seen = HashSet::new();
//! let arc = Arc::new(1, 2, TropicalWeight::new(0.5), 3);
//! seen.insert(arc.clone());
//!
//! assert!(seen.contains(&arc));
//! ```
//!
//! [`TropicalWeight`]: crate::semiring::TropicalWeight

use crate::fst::{Label, StateId};
use crate::semiring::Semiring;
use core::fmt;

/// A weighted arc (transition) in a finite-state transducer.
///
/// Arcs are the fundamental building blocks of FSTs, representing labeled,
/// weighted transitions between states. Each arc specifies:
///
/// - An input symbol to consume (or epsilon if `ilabel == 0`)
/// - An output symbol to produce (or epsilon if `olabel == 0`)
/// - A weight from the semiring `W`
/// - The destination state
///
/// # Type Parameters
///
/// * `W` - The semiring type for arc weights (e.g., [`TropicalWeight`], [`LogWeight`])
///
/// # Fields
///
/// | Field | Type | Description |
/// |-------|------|-------------|
/// | `ilabel` | [`Label`] | Input symbol (0 = epsilon) |
/// | `olabel` | [`Label`] | Output symbol (0 = epsilon) |
/// | `weight` | `W` | Transition weight |
/// | `nextstate` | [`StateId`] | Destination state ID |
///
/// # Examples
///
/// Creating different types of arcs:
///
/// ```
/// use arcweight::prelude::*;
///
/// // Regular arc with different input/output labels
/// let arc1 = Arc::new(1, 2, TropicalWeight::new(0.5), 3);
///
/// // Acceptor arc (same input/output)
/// let arc2 = Arc::new(1, 1, TropicalWeight::one(), 2);
///
/// // Epsilon arc (input=0, output=0)
/// let epsilon = Arc::epsilon(TropicalWeight::new(0.1), 1);
///
/// assert_eq!(arc1.ilabel, 1);
/// assert_eq!(arc1.olabel, 2);
/// assert!(epsilon.is_epsilon());
/// ```
///
/// Using arcs in FST construction:
///
/// ```
/// use arcweight::prelude::*;
///
/// let mut fst = VectorFst::<TropicalWeight>::new();
/// let s0 = fst.add_state();
/// let s1 = fst.add_state();
///
/// // Add a transducer arc
/// fst.add_arc(s0, Arc::new(1, 2, TropicalWeight::new(0.5), s1));
/// ```
///
/// [`TropicalWeight`]: crate::semiring::TropicalWeight
/// [`LogWeight`]: crate::semiring::LogWeight
/// [`Label`]: crate::fst::Label
/// [`StateId`]: crate::fst::StateId
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Arc<W: Semiring> {
    /// Input label consumed by this transition.
    ///
    /// A value of 0 indicates an epsilon transition on the input tape,
    /// meaning no symbol is consumed.
    pub ilabel: Label,

    /// Output label produced by this transition.
    ///
    /// A value of 0 indicates an epsilon transition on the output tape,
    /// meaning no symbol is produced.
    pub olabel: Label,

    /// Weight of this transition in the semiring `W`.
    ///
    /// The weight represents the cost, probability, or other measure
    /// associated with taking this transition, as defined by the semiring.
    pub weight: W,

    /// Destination state ID.
    ///
    /// The state that becomes current after taking this transition.
    pub nextstate: StateId,
}

impl<W: Semiring> Arc<W> {
    /// Creates a new arc with the specified labels, weight, and destination.
    ///
    /// This is the primary constructor for arcs in FST construction.
    ///
    /// # Arguments
    ///
    /// * `ilabel` - Input label (0 for epsilon)
    /// * `olabel` - Output label (0 for epsilon)
    /// * `weight` - Arc weight in the semiring
    /// * `nextstate` - Destination state ID
    ///
    /// # Returns
    ///
    /// A new `Arc` with the specified components.
    ///
    /// # Examples
    ///
    /// ```
    /// use arcweight::prelude::*;
    ///
    /// let arc = Arc::new(1, 2, TropicalWeight::new(0.5), 3);
    ///
    /// assert_eq!(arc.ilabel, 1);
    /// assert_eq!(arc.olabel, 2);
    /// assert_eq!(arc.weight, TropicalWeight::new(0.5));
    /// assert_eq!(arc.nextstate, 3);
    /// ```
    #[inline]
    pub fn new(ilabel: Label, olabel: Label, weight: W, nextstate: StateId) -> Self {
        Self {
            ilabel,
            olabel,
            weight,
            nextstate,
        }
    }

    /// Creates an epsilon arc (no input or output symbol).
    ///
    /// Epsilon arcs have input and output labels of 0, representing
    /// transitions that neither consume nor produce symbols. These are
    /// commonly used in NFA-to-DFA conversions and composition algorithms.
    ///
    /// # Arguments
    ///
    /// * `weight` - Arc weight in the semiring
    /// * `nextstate` - Destination state ID
    ///
    /// # Returns
    ///
    /// A new `Arc` with `ilabel = 0` and `olabel = 0`.
    ///
    /// # Examples
    ///
    /// ```
    /// use arcweight::prelude::*;
    ///
    /// let epsilon = Arc::epsilon(TropicalWeight::one(), 2);
    ///
    /// assert_eq!(epsilon.ilabel, 0);
    /// assert_eq!(epsilon.olabel, 0);
    /// assert!(epsilon.is_epsilon());
    /// assert!(epsilon.is_epsilon_input());
    /// assert!(epsilon.is_epsilon_output());
    /// ```
    #[inline]
    pub fn epsilon(weight: W, nextstate: StateId) -> Self {
        Self::new(0, 0, weight, nextstate)
    }

    /// Returns `true` if the input label is epsilon (0).
    ///
    /// An epsilon input means this transition does not consume
    /// any symbol from the input tape.
    ///
    /// # Returns
    ///
    /// `true` if `ilabel == 0`, `false` otherwise.
    ///
    /// # Examples
    ///
    /// ```
    /// use arcweight::prelude::*;
    ///
    /// let eps = Arc::new(0, 5, TropicalWeight::one(), 1);
    /// let regular = Arc::new(1, 5, TropicalWeight::one(), 1);
    ///
    /// assert!(eps.is_epsilon_input());
    /// assert!(!regular.is_epsilon_input());
    /// ```
    #[inline]
    pub fn is_epsilon_input(&self) -> bool {
        self.ilabel == 0
    }

    /// Returns `true` if the output label is epsilon (0).
    ///
    /// An epsilon output means this transition does not produce
    /// any symbol on the output tape.
    ///
    /// # Returns
    ///
    /// `true` if `olabel == 0`, `false` otherwise.
    ///
    /// # Examples
    ///
    /// ```
    /// use arcweight::prelude::*;
    ///
    /// let eps = Arc::new(5, 0, TropicalWeight::one(), 1);
    /// let regular = Arc::new(5, 1, TropicalWeight::one(), 1);
    ///
    /// assert!(eps.is_epsilon_output());
    /// assert!(!regular.is_epsilon_output());
    /// ```
    #[inline]
    pub fn is_epsilon_output(&self) -> bool {
        self.olabel == 0
    }

    /// Returns `true` if both input and output labels are epsilon.
    ///
    /// A fully epsilon arc neither consumes input nor produces output,
    /// representing a "free" transition between states. Such arcs are
    /// commonly removed during epsilon removal optimization.
    ///
    /// # Returns
    ///
    /// `true` if both `ilabel == 0` and `olabel == 0`, `false` otherwise.
    ///
    /// # Examples
    ///
    /// ```
    /// use arcweight::prelude::*;
    ///
    /// let full_eps = Arc::epsilon(TropicalWeight::one(), 1);
    /// let input_eps = Arc::new(0, 5, TropicalWeight::one(), 1);
    /// let regular = Arc::new(1, 2, TropicalWeight::one(), 1);
    ///
    /// assert!(full_eps.is_epsilon());
    /// assert!(!input_eps.is_epsilon());  // Only input is epsilon
    /// assert!(!regular.is_epsilon());
    /// ```
    #[inline]
    pub fn is_epsilon(&self) -> bool {
        self.is_epsilon_input() && self.is_epsilon_output()
    }
}

impl<W: Semiring> fmt::Display for Arc<W> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}:{}:{} -> {}",
            self.ilabel, self.olabel, self.weight, self.nextstate
        )
    }
}

/// Iterator over arcs leaving a state in an FST.
///
/// This trait extends [`Iterator`] to provide a uniform interface for
/// iterating over arcs from a particular state. Different FST implementations
/// provide optimized concrete iterator types implementing this trait.
///
/// # Type Parameters
///
/// * `W` - The semiring type for arc weights
///
/// # Provided Methods
///
/// * [`reset()`](ArcIterator::reset) - Resets the iterator to the beginning
///
/// # Usage
///
/// Arc iterators are typically obtained from FST types via the `arcs()` method:
///
/// ```
/// use arcweight::prelude::*;
///
/// let mut fst = VectorFst::<TropicalWeight>::new();
/// let state = fst.add_state();
/// fst.add_arc(state, Arc::new(1, 2, TropicalWeight::new(0.5), state));
/// fst.add_arc(state, Arc::new(3, 4, TropicalWeight::new(0.3), state));
///
/// // Iterate over all arcs from state
/// for arc in fst.arcs(state) {
///     println!("Arc: {} -> {} (weight: {})", arc.ilabel, arc.olabel, arc.weight);
/// }
/// ```
///
/// # Implementation Notes
///
/// - Iterators may cache arcs internally for efficiency
/// - The [`reset()`](ArcIterator::reset) method enables iterator reuse without reallocation
/// - Some implementations lazily compute arcs during iteration
/// - Iteration order depends on the FST implementation (typically insertion order)
///
/// # Implementors
///
/// This trait is implemented by iterator types from:
///
/// - [`VectorFst`](crate::fst::VectorFst) - Direct slice iteration
/// - [`ConstFst`](crate::fst::ConstFst) - Index-based iteration
/// - Lazy FST types - On-demand arc generation
pub trait ArcIterator<W: Semiring>: Iterator<Item = Arc<W>> {
    /// Resets the iterator to the beginning of the arc sequence.
    ///
    /// This method allows reusing an iterator without creating a new one,
    /// which can be more efficient for algorithms that need to iterate
    /// over the same arcs multiple times.
    ///
    /// # Default Implementation
    ///
    /// The default implementation is a no-op, suitable for iterators
    /// that don't maintain resettable state. Implementations that support
    /// true reset should override this method.
    ///
    /// # Examples
    ///
    /// ```
    /// use arcweight::prelude::*;
    ///
    /// let mut fst = VectorFst::<TropicalWeight>::new();
    /// let s0 = fst.add_state();
    /// fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::one(), s0));
    ///
    /// // Note: VectorFst returns a fresh iterator each call,
    /// // so reset() is not typically needed in practice
    /// let count1: usize = fst.arcs(s0).count();
    /// let count2: usize = fst.arcs(s0).count();
    /// assert_eq!(count1, count2);
    /// ```
    fn reset(&mut self) {
        // Default implementation does nothing
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::fst::{NO_LABEL, NO_STATE_ID};
    use crate::semiring::TropicalWeight;

    #[test]
    fn test_arc_creation() {
        let arc = Arc::new(1, 2, TropicalWeight::new(3.0), 4);

        assert_eq!(arc.ilabel, 1);
        assert_eq!(arc.olabel, 2);
        assert_eq!(*arc.weight.value(), 3.0);
        assert_eq!(arc.nextstate, 4);
    }

    #[test]
    fn test_epsilon_arc() {
        let arc = Arc::epsilon(TropicalWeight::new(1.5), 5);

        assert_eq!(arc.ilabel, NO_LABEL);
        assert_eq!(arc.olabel, NO_LABEL);
        assert_eq!(*arc.weight.value(), 1.5);
        assert_eq!(arc.nextstate, 5);
        assert!(arc.is_epsilon());
    }

    #[test]
    fn test_epsilon_checks() {
        let epsilon_arc = Arc::epsilon(TropicalWeight::new(1.0), 1);
        let regular_arc = Arc::new(1, 2, TropicalWeight::new(1.0), 1);
        let epsilon_input = Arc::new(0, 2, TropicalWeight::new(1.0), 1);
        let epsilon_output = Arc::new(1, 0, TropicalWeight::new(1.0), 1);

        // Full epsilon
        assert!(epsilon_arc.is_epsilon());
        assert!(epsilon_arc.is_epsilon_input());
        assert!(epsilon_arc.is_epsilon_output());

        // Regular arc
        assert!(!regular_arc.is_epsilon());
        assert!(!regular_arc.is_epsilon_input());
        assert!(!regular_arc.is_epsilon_output());

        // Epsilon input only
        assert!(!epsilon_input.is_epsilon());
        assert!(epsilon_input.is_epsilon_input());
        assert!(!epsilon_input.is_epsilon_output());

        // Epsilon output only
        assert!(!epsilon_output.is_epsilon());
        assert!(!epsilon_output.is_epsilon_input());
        assert!(epsilon_output.is_epsilon_output());
    }

    #[test]
    fn test_arc_display() {
        let arc = Arc::new(1, 2, TropicalWeight::new(3.0), 4);
        let display_str = format!("{arc}");

        assert!(display_str.contains("1"));
        assert!(display_str.contains("2"));
        assert!(display_str.contains("3"));
        assert!(display_str.contains("4"));
    }

    #[test]
    fn test_arc_equality() {
        let arc1 = Arc::new(1, 2, TropicalWeight::new(3.0), 4);
        let arc2 = Arc::new(1, 2, TropicalWeight::new(3.0), 4);
        let arc3 = Arc::new(1, 2, TropicalWeight::new(3.1), 4);
        let arc4 = Arc::new(1, 3, TropicalWeight::new(3.0), 4);

        assert_eq!(arc1, arc2);
        assert_ne!(arc1, arc3);
        assert_ne!(arc1, arc4);
    }

    #[test]
    fn test_arc_clone() {
        let arc = Arc::new(1, 2, TropicalWeight::new(3.0), 4);
        let arc_clone = arc.clone();

        assert_eq!(arc, arc_clone);
        assert_eq!(arc.ilabel, arc_clone.ilabel);
        assert_eq!(arc.olabel, arc_clone.olabel);
        assert_eq!(arc.weight, arc_clone.weight);
        assert_eq!(arc.nextstate, arc_clone.nextstate);
    }

    #[test]
    fn test_arc_debug() {
        let arc = Arc::new(1, 2, TropicalWeight::new(3.0), 4);
        let debug_str = format!("{arc:?}");

        assert!(debug_str.contains("Arc"));
        assert!(debug_str.contains("ilabel"));
        assert!(debug_str.contains("olabel"));
        assert!(debug_str.contains("weight"));
        assert!(debug_str.contains("nextstate"));
    }

    #[test]
    fn test_arc_special_labels() {
        let arc = Arc::new(NO_LABEL, NO_LABEL, TropicalWeight::new(1.0), 0);
        assert!(arc.is_epsilon());

        let arc = Arc::new(NO_STATE_ID, NO_LABEL, TropicalWeight::new(1.0), 0);
        assert_eq!(arc.ilabel, NO_STATE_ID);
    }

    #[test]
    fn test_arc_display_format() {
        let arc = Arc::new(10, 20, TropicalWeight::new(0.5), 30);
        let display = format!("{arc}");
        assert_eq!(display, "10:20:0.5 -> 30");
    }

    #[test]
    fn test_arc_hash() {
        use std::collections::HashSet;

        let mut set = HashSet::new();
        let arc1 = Arc::new(1, 2, TropicalWeight::new(3.0), 4);
        let arc2 = Arc::new(1, 2, TropicalWeight::new(3.0), 4);
        let arc3 = Arc::new(1, 2, TropicalWeight::new(3.1), 4);

        set.insert(arc1);
        assert!(set.contains(&arc2)); // Same arc
        assert!(!set.contains(&arc3)); // Different weight
    }

    // Property-based tests
    mod proptests {
        use super::*;
        use proptest::prelude::*;

        proptest! {
            #[test]
            fn test_arc_consistency_property(
                ilabel: u32,
                olabel: u32,
                weight: f32,
                nextstate in 0..100u32,
            ) {
                let arc = Arc::new(
                    ilabel,
                    olabel,
                    TropicalWeight::new(weight),
                    nextstate,
                );

                assert_eq!(arc.ilabel, ilabel);
                assert_eq!(arc.olabel, olabel);
                assert_eq!(*arc.weight.value(), weight);
                assert_eq!(arc.nextstate, nextstate);

                // Epsilon check consistency
                let is_epsilon = ilabel == NO_LABEL && olabel == NO_LABEL;
                assert_eq!(arc.is_epsilon(), is_epsilon);
            }
        }
    }
}