arcweight 0.3.0

//! Kleene closure algorithms.
//!
//! Implements Kleene star ($`T^*`$) and Kleene plus ($`T^+`$) operations for weighted
//! finite-state transducers, enabling repetition patterns and iterative language constructions.
//!
//! - **Kleene Star ($`T^*`$):** Accepts zero or more repetitions:
//!   $`L(T^*) = \{\varepsilon\} \cup L(T) \cup L(T^2) \cup \ldots`$
//! - **Kleene Plus ($`T^+`$):** Accepts one or more repetitions:
//!   $`L(T^+) = L(T) \cup L(T^2) \cup L(T^3) \cup \ldots`$
//!
//! # Complexity
//!
//! - **Time:** $`O(|V| + |E|)`$ -- single copy plus constant overhead for epsilon connections
//! - **Space:** $`O(|V| + |E|)`$ plus one additional state
//!
//! # Semiring Requirements
//!
//! Kleene closure requires a [`StarSemiring`] for proper weight computation in infinite
//! repetition scenarios. The star operation computes $`\bigoplus_{n=0}^{\infty} w^n`$ for
//! weights on cyclic paths.
//!
//! # References
//!
//! - Stephen Cole Kleene. 1956. Representation of events in nerve nets and finite automata.
//!   In *Automata Studies*, Claude E. Shannon and John McCarthy (Eds.). Princeton University
//!   Press, Princeton, NJ, 3-42.
//! - Mehryar Mohri. 2009. Weighted automata algorithms. In *Handbook of Weighted
//!   Automata*, Manfred Droste, Werner Kuich, and Heiko Vogler (Eds.). Springer,
//!   Berlin, Heidelberg, 213-254.
//!
//! [`StarSemiring`]: crate::semiring::StarSemiring

use crate::arc::Arc;
use crate::fst::{Fst, MutableFst};
use crate::semiring::StarSemiring;
use crate::Result;

/// Computes the Kleene closure (star) of an FST.
///
/// Creates a new FST that accepts zero or more repetitions of the input FST:
/// $`L(T^*) = \{\varepsilon\} \cup L(T) \cup L(T^2) \cup L(T^3) \cup \ldots`$
///
/// The result always accepts the empty string, plus any concatenation of strings
/// from the original language.
///
/// # Type Parameters
///
/// * `W` - Weight type implementing [`StarSemiring`]
/// * `F` - Input FST type implementing [`Fst<W>`]
/// * `M` - Output FST type implementing [`MutableFst<W>`] and [`Default`]
///
/// # Returns
///
/// A new FST accepting zero or more repetitions of the input language.
///
/// # Errors
///
/// Returns [`Error::Algorithm`](crate::Error::Algorithm) if the input FST is invalid.
///
/// # Examples
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // FST accepts "a"
/// let mut fst = VectorFst::<BooleanWeight>::new();
/// let s0 = fst.add_state();
/// let s1 = fst.add_state();
/// fst.set_start(s0);
/// fst.set_final(s1, BooleanWeight::one());
/// fst.add_arc(s0, Arc::new('a' as u32, 'a' as u32, BooleanWeight::one(), s1));
///
/// // a* accepts: ε, "a", "aa", "aaa", ...
/// let star_fst: VectorFst<BooleanWeight> = closure(&fst)?;
///
/// // New start state is also final (accepts empty string)
/// let start = star_fst.start().unwrap();
/// assert!(star_fst.is_final(start));
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # References
///
/// - Stephen Cole Kleene. 1956. Representation of events in nerve nets and finite automata.
///   In *Automata Studies*, Claude E. Shannon and John McCarthy (Eds.). Princeton University
///   Press, Princeton, NJ, 3-42.
///
/// [`StarSemiring`]: crate::semiring::StarSemiring
pub fn closure<W, F, M>(fst: &F) -> Result<M>
where
    W: StarSemiring,
    F: Fst<W>,
    M: MutableFst<W> + Default,
{
    closure_impl(fst, true)
}

/// Computes the Kleene plus of an FST.
///
/// Creates a new FST that accepts one or more repetitions of the input FST:
/// $`L(T^+) = L(T) \cup L(T^2) \cup L(T^3) \cup \ldots`$
///
/// Unlike Kleene star, Kleene plus does **not** accept the empty string -- it requires
/// at least one iteration of the original FST language.
///
/// # Type Parameters
///
/// * `W` - Weight type implementing [`StarSemiring`]
/// * `F` - Input FST type implementing [`Fst<W>`]
/// * `M` - Output FST type implementing [`MutableFst<W>`] and [`Default`]
///
/// # Returns
///
/// A new FST accepting one or more repetitions of the input language.
///
/// # Errors
///
/// Returns [`Error::Algorithm`](crate::Error::Algorithm) if the input FST is invalid.
///
/// # Examples
///
/// ```rust
/// use arcweight::prelude::*;
///
/// // FST accepts single digit
/// let mut digit = VectorFst::<BooleanWeight>::new();
/// let s0 = digit.add_state();
/// let s1 = digit.add_state();
/// digit.set_start(s0);
/// digit.set_final(s1, BooleanWeight::one());
/// digit.add_arc(s0, Arc::new('0' as u32, '0' as u32, BooleanWeight::one(), s1));
///
/// // digit+ accepts: "0", "00", "000", ... but NOT empty string
/// let number: VectorFst<BooleanWeight> = closure_plus(&digit)?;
///
/// // New start state is NOT final (rejects empty string)
/// let start = number.start().unwrap();
/// assert!(!number.is_final(start));
/// # Ok::<(), Box<dyn std::error::Error>>(())
/// ```
///
/// # References
///
/// - Stephen Cole Kleene. 1956. Representation of events in nerve nets and finite automata.
///   In *Automata Studies*, Claude E. Shannon and John McCarthy (Eds.). Princeton University
///   Press, Princeton, NJ, 3-42.
///
/// [`StarSemiring`]: crate::semiring::StarSemiring
pub fn closure_plus<W, F, M>(fst: &F) -> Result<M>
where
    W: StarSemiring,
    F: Fst<W>,
    M: MutableFst<W> + Default,
{
    closure_impl(fst, false)
}

fn closure_impl<W, F, M>(fst: &F, allow_empty: bool) -> Result<M>
where
    W: StarSemiring,
    F: Fst<W>,
    M: MutableFst<W> + Default,
{
    let mut result = M::default();

    // copy original FST
    let mut state_map = vec![None; fst.num_states()];
    for state in fst.states() {
        let new_state = result.add_state();
        state_map[state as usize] = Some(new_state);
    }

    // create new start/final state
    let new_start = result.add_state();
    result.set_start(new_start);
    result.set_final(new_start, W::one());

    // connect to original start
    if let Some(orig_start) = fst.start() {
        if let Some(mapped_start) = state_map[orig_start as usize] {
            result.add_arc(new_start, Arc::epsilon(W::one(), mapped_start));

            if !allow_empty {
                // for plus, remove final weight from new start
                result.remove_final(new_start);
            }
        }
    }

    // copy arcs
    for state in fst.states() {
        if let Some(new_state) = state_map[state as usize] {
            for arc in fst.arcs(state) {
                if let Some(new_nextstate) = state_map[arc.nextstate as usize] {
                    result.add_arc(
                        new_state,
                        Arc::new(arc.ilabel, arc.olabel, arc.weight.clone(), new_nextstate),
                    );
                }
            }

            // connect final states back to new start
            if let Some(weight) = fst.final_weight(state) {
                result.add_arc(new_state, Arc::epsilon(weight.clone(), new_start));
            }
        }
    }

    Ok(result)
}

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

    #[test]
    fn test_closure_with_boolean_weight() {
        let mut fst = VectorFst::<BooleanWeight>::new();
        let s0 = fst.add_state();
        let s1 = fst.add_state();
        fst.set_start(s0);
        fst.set_final(s1, BooleanWeight::one());
        fst.add_arc(s0, Arc::new(1, 1, BooleanWeight::new(true), s1));

        let star: VectorFst<BooleanWeight> = closure(&fst).unwrap();

        // Closure should add states for start/final
        assert!(star.num_states() > fst.num_states());
        assert!(star.start().is_some());

        // Start state should be final (empty string acceptance)
        let start = star.start().unwrap();
        assert!(star.is_final(start));
    }

    #[test]
    fn test_closure_plus_with_boolean_weight() {
        let mut fst = VectorFst::<BooleanWeight>::new();
        let s0 = fst.add_state();
        let s1 = fst.add_state();
        fst.set_start(s0);
        fst.set_final(s1, BooleanWeight::one());
        fst.add_arc(s0, Arc::new(1, 1, BooleanWeight::new(true), s1));

        let plus: VectorFst<BooleanWeight> = closure_plus(&fst).unwrap();

        // Plus closure should not accept empty string
        assert!(plus.start().is_some());

        // Start state should not be final
        let start = plus.start().unwrap();
        assert!(!plus.is_final(start));
    }
}