arcweight 0.3.0

//! Hopcroft's $`O(n \log n)`$ minimization algorithm.
//!
//! This module implements Hopcroft's partition refinement algorithm for DFA/FST
//! minimization. Unlike Brzozowski's algorithm which has exponential worst-case
//! complexity, Hopcroft's algorithm guarantees $`O(n \log n)`$ time, making it
//! preferable for large automata.
//!
//! # Algorithm
//!
//! Hopcroft's algorithm (1971) uses partition refinement with a clever worklist
//! strategy that ensures each transition is processed at most $`O(\log n)`$ times:
//!
//! 1. **Initialize:** Partition $`P = \{F, Q \setminus F\}`$ (final vs non-final)
//! 2. **Worklist:** $`W = \{(B, a) : B \in P, a \in \Sigma\}`$
//! 3. **Refine:** While $`W \neq \emptyset`$:
//!    - Pop splitter $`(S, a)`$ from $`W`$
//!    - Find predecessors: $`\text{pre}_a(S) = \{q : \delta(q, a) \in S\}`$
//!    - For each block $`B`$ split by $`\text{pre}_a(S)`$:
//!      - Split $`B`$ into $`B \cap \text{pre}_a(S)`$ and $`B \setminus \text{pre}_a(S)`$
//!      - Add smaller part to worklist (key optimization)
//! 4. **Result:** States in same block are equivalent
//!
//! # Complexity
//!
//! | Resource | Bound | Notes |
//! |----------|-------|-------|
//! | Time | $`O(n \log n)`$ | Each transition processed $`O(\log n)`$ times |
//! | Space | $`O(n + m)`$ | Partition blocks + reverse transitions |
//!
//! where $`n`$ = states, $`m`$ = transitions.
//!
//! # Requirements
//!
//! - Input FST should be **deterministic** for correct results
//! - Weight type must implement `Eq + Hash` for state equivalence
//!
//! # Comparison with Brzozowski
//!
//! | Algorithm | Worst Case | Best Case | Space |
//! |-----------|------------|-----------|-------|
//! | Brzozowski | $`O(2^n)`$ | $`O(n)`$ | $`O(2^n)`$ |
//! | Hopcroft | $`O(n \log n)`$ | $`O(n \log n)`$ | $`O(n + m)`$ |
//!
//! Use Hopcroft when:
//! - Worst-case guarantees are needed
//! - FST is large with many equivalent states
//! - Input is known to be deterministic
//!
//! # Example
//!
//! ```rust
//! use arcweight::prelude::*;
//! use arcweight::algorithms::minimize_hopcroft;
//!
//! 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());
//! fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::one(), s1));
//! fst.add_arc(s1, Arc::new(2, 2, TropicalWeight::one(), s2));
//!
//! let minimized: VectorFst<TropicalWeight> = minimize_hopcroft(&fst)?;
//! # Ok::<(), arcweight::Error>(())
//! ```
//!
//! # References
//!
//! \[1\] Hopcroft, J. E. 1971. An $`n \log n`$ algorithm for minimizing states in a
//!     finite automaton. In *Theory of Machines and Computations*, Z. Kohavi and
//!     A. Paz, Eds. Academic Press, 189-196. <https://doi.org/10.1016/B978-0-12-417750-5.50022-1>
//!
//! \[2\] Gries, D. 1973. Describing an algorithm by Hopcroft. *Acta Informatica*
//!     2, 2 (June 1973), 97-109. <https://doi.org/10.1007/BF00264025>
//!
//! \[3\] Knuutila, T. 2001. Re-describing an algorithm by Hopcroft. *Theoretical
//!     Computer Science* 250, 1-2 (January 2001), 333-363.
//!     <https://doi.org/10.1016/S0304-3975(99)00150-4>

use crate::arc::Arc;
use crate::fst::{Fst, Label, MutableFst, StateId};
use crate::semiring::Semiring;
use crate::Result;
use rustc_hash::{FxHashMap, FxHashSet};
use std::collections::VecDeque;

/// Minimizes an FST using Hopcroft's $`O(n \log n)`$ partition refinement algorithm.
///
/// This algorithm provides guaranteed polynomial-time minimization, unlike Brzozowski's
/// algorithm which can be exponential. Particularly effective for large deterministic
/// FSTs with many equivalent states.
///
/// # Type Parameters
///
/// * `W` - Weight type implementing [`Semiring`], [`Eq`], and [`Hash`]
/// * `F` - Input FST type
/// * `M` - Output FST type (mutable)
///
/// # Arguments
///
/// * `fst` - Input FST (should be deterministic for correct results)
///
/// # Returns
///
/// Minimized FST with equivalent states merged.
///
/// # Complexity
///
/// - **Time:** $`O(n \log n)`$ where $`n`$ is the number of states
/// - **Space:** $`O(n + m)`$ where $`m`$ is the number of transitions
///
/// # Algorithm
///
/// 1. Build reverse transition map for efficient predecessor lookup
/// 2. Initialize partition by final weight (states with different final weights
///    cannot be equivalent)
/// 3. Refine partition using splitter blocks until stable
/// 4. Construct minimized FST with one state per equivalence class
///
/// # Requirements
///
/// - Input FST should be **deterministic** for semantically correct minimization
/// - Non-deterministic inputs may produce correct but suboptimal results
/// - Weight type must implement `Eq + Hash` for equivalence checking
///
/// # Example
///
/// ```rust
/// use arcweight::prelude::*;
/// use arcweight::algorithms::minimize_hopcroft;
///
/// 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());
/// fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::one(), s1));
/// fst.add_arc(s1, Arc::new(2, 2, TropicalWeight::one(), s2));
///
/// let minimized: VectorFst<TropicalWeight> = minimize_hopcroft(&fst)?;
/// assert!(minimized.num_states() <= fst.num_states());
/// # Ok::<(), arcweight::Error>(())
/// ```
///
/// # References
///
/// \[1\] Hopcroft, J. E. 1971. An $`n \log n`$ algorithm for minimizing states in a
///     finite automaton. In *Theory of Machines and Computations*, 189-196.
///     <https://doi.org/10.1016/B978-0-12-417750-5.50022-1>
///
/// # See Also
///
/// - [`minimize`](crate::algorithms::minimize()) - Brzozowski's algorithm (often faster in practice)
/// - [`determinize`](crate::algorithms::determinize()) - Required preprocessing for non-deterministic FSTs
pub fn minimize_hopcroft<W, F, M>(fst: &F) -> Result<M>
where
    W: Semiring + Eq + std::hash::Hash,
    F: Fst<W>,
    M: MutableFst<W> + Default,
{
    let num_states = fst.num_states();

    if num_states == 0 {
        return Ok(M::default());
    }

    // Build reverse transition map: (target_state, label) -> source_states
    let reverse_delta = build_reverse_delta(fst);

    // Collect all labels
    let all_labels = collect_all_labels(fst);

    // Initial partition: separate final from non-final states
    // Also separate states by final weight value for weighted FSTs
    let mut partition = initial_partition(fst);

    // State to block mapping
    let mut state_to_block: Vec<usize> = vec![0; num_states];
    for (block_idx, block) in partition.iter().enumerate() {
        for &state in block {
            state_to_block[state as usize] = block_idx;
        }
    }

    // Worklist of (block_index, label) pairs to process
    let mut worklist: VecDeque<(usize, Label)> = VecDeque::new();

    // Initialize worklist with all (block, label) pairs
    for block_idx in 0..partition.len() {
        for &label in &all_labels {
            worklist.push_back((block_idx, label));
        }
    }

    // Main refinement loop
    while let Some((splitter_block_idx, label)) = worklist.pop_front() {
        if splitter_block_idx >= partition.len() {
            continue;
        }

        let splitter = &partition[splitter_block_idx];
        if splitter.is_empty() {
            continue;
        }

        // Find all states that transition to splitter on label
        let mut predecessors: FxHashSet<StateId> = FxHashSet::default();
        for &target in splitter {
            let key = (target, label);
            if let Some(sources) = reverse_delta.get(&key) {
                for &source in sources {
                    predecessors.insert(source);
                }
            }
        }

        if predecessors.is_empty() {
            continue;
        }

        // Try to split each block
        let mut new_blocks: Vec<FxHashSet<StateId>> = Vec::new();
        let mut blocks_to_split: Vec<(usize, FxHashSet<StateId>, FxHashSet<StateId>)> = Vec::new();

        // Group predecessors by their current block
        let mut preds_by_block: FxHashMap<usize, FxHashSet<StateId>> = FxHashMap::default();
        for &pred in &predecessors {
            let block_idx = state_to_block[pred as usize];
            preds_by_block.entry(block_idx).or_default().insert(pred);
        }

        for (block_idx, preds_in_block) in preds_by_block {
            if block_idx >= partition.len() {
                continue;
            }

            let block = &partition[block_idx];
            if preds_in_block.len() < block.len() && !preds_in_block.is_empty() {
                // This block can be split
                let not_preds: FxHashSet<StateId> = block
                    .iter()
                    .filter(|s| !preds_in_block.contains(s))
                    .copied()
                    .collect();

                if !not_preds.is_empty() {
                    blocks_to_split.push((block_idx, preds_in_block, not_preds));
                }
            }
        }

        // Perform the splits
        for (block_idx, preds, not_preds) in blocks_to_split {
            // Keep smaller set in original block, move larger to new block
            let (keep, move_out) = if preds.len() <= not_preds.len() {
                (preds, not_preds)
            } else {
                (not_preds, preds)
            };

            // Update the original block
            partition[block_idx] = keep;

            // Create new block
            let new_block_idx = partition.len();

            // Update state_to_block for moved states
            for &state in &move_out {
                state_to_block[state as usize] = new_block_idx;
            }

            new_blocks.push(move_out);

            // Add new block to worklist for all labels
            for &l in &all_labels {
                worklist.push_back((new_block_idx, l));
            }
        }

        // Add new blocks to partition
        for block in new_blocks {
            partition.push(block);
        }
    }

    // Build the minimized FST
    build_minimized_fst(fst, &partition, &state_to_block)
}

/// Build reverse transition map: (target_state, label) -> `[source_states]`
fn build_reverse_delta<W, F>(fst: &F) -> FxHashMap<(StateId, Label), Vec<StateId>>
where
    W: Semiring,
    F: Fst<W>,
{
    let mut reverse = FxHashMap::default();

    for state in 0..fst.num_states() as StateId {
        for arc in fst.arcs(state) {
            let key = (arc.nextstate, arc.ilabel);
            reverse.entry(key).or_insert_with(Vec::new).push(state);
        }
    }

    reverse
}

/// Collect all labels used in the FST
fn collect_all_labels<W, F>(fst: &F) -> FxHashSet<Label>
where
    W: Semiring,
    F: Fst<W>,
{
    let mut labels = FxHashSet::default();

    for state in 0..fst.num_states() as StateId {
        for arc in fst.arcs(state) {
            labels.insert(arc.ilabel);
        }
    }

    labels
}

/// Create initial partition separating states by final weight
fn initial_partition<W, F>(fst: &F) -> Vec<FxHashSet<StateId>>
where
    W: Semiring + Eq + std::hash::Hash,
    F: Fst<W>,
{
    // Group states by final weight (including None for non-final)
    let mut weight_groups: FxHashMap<Option<W>, FxHashSet<StateId>> = FxHashMap::default();

    for state in 0..fst.num_states() as StateId {
        let final_weight = fst.final_weight(state).cloned();
        weight_groups.entry(final_weight).or_default().insert(state);
    }

    weight_groups.into_values().collect()
}

/// Build the minimized FST from partition
fn build_minimized_fst<W, F, M>(
    fst: &F,
    partition: &[FxHashSet<StateId>],
    state_to_block: &[usize],
) -> Result<M>
where
    W: Semiring,
    F: Fst<W>,
    M: MutableFst<W> + Default,
{
    let mut result = M::default();

    // Create mapping from block index to new state id
    let mut block_to_new_state: FxHashMap<usize, StateId> = FxHashMap::default();

    // Filter out empty blocks and create new states
    for (block_idx, block) in partition.iter().enumerate() {
        if !block.is_empty() {
            let new_state = result.add_state();
            block_to_new_state.insert(block_idx, new_state);
        }
    }

    // Set start state
    if let Some(start) = fst.start() {
        let start_block = state_to_block[start as usize];
        if let Some(&new_start) = block_to_new_state.get(&start_block) {
            result.set_start(new_start);
        }
    }

    // For each block, pick a representative state and copy its structure
    let mut processed_blocks: FxHashSet<usize> = FxHashSet::default();

    for (block_idx, block) in partition.iter().enumerate() {
        if block.is_empty() || processed_blocks.contains(&block_idx) {
            continue;
        }
        processed_blocks.insert(block_idx);

        // Pick any state from this block as representative
        let representative = *block.iter().next().unwrap();

        let Some(&new_state) = block_to_new_state.get(&block_idx) else {
            continue;
        };

        // Set final weight if applicable
        if let Some(w) = fst.final_weight(representative) {
            result.set_final(new_state, w.clone());
        }

        // Add arcs, combining weights for arcs with same (ilabel, olabel, target_block)
        // using the semiring's plus operation.
        //
        // NOTE: This requires the semiring's plus operation to be commutative (a + b = b + a)
        // because the order in which arcs are processed may vary. All standard semirings
        // (tropical, log, probability, boolean) are commutative. For non-commutative
        // semirings, results may depend on iteration order.
        let mut arc_weights: FxHashMap<(Label, Label, usize), W> = FxHashMap::default();

        for arc in fst.arcs(representative) {
            let target_block = state_to_block[arc.nextstate as usize];
            let arc_key = (arc.ilabel, arc.olabel, target_block);

            arc_weights
                .entry(arc_key)
                .and_modify(|w| w.plus_assign(&arc.weight))
                .or_insert_with(|| arc.weight.clone());
        }

        // Create the deduplicated arcs with combined weights
        for ((ilabel, olabel, target_block), weight) in arc_weights {
            if let Some(&new_target) = block_to_new_state.get(&target_block) {
                result.add_arc(new_state, Arc::new(ilabel, olabel, weight, new_target));
            }
        }
    }

    Ok(result)
}

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

    #[test]
    fn test_hopcroft_empty_fst() {
        let fst = VectorFst::<TropicalWeight>::new();
        let result: VectorFst<TropicalWeight> = minimize_hopcroft(&fst).unwrap();
        assert_eq!(result.num_states(), 0);
    }

    #[test]
    fn test_hopcroft_single_state() {
        let mut fst = VectorFst::<TropicalWeight>::new();
        let s0 = fst.add_state();
        fst.set_start(s0);
        fst.set_final(s0, TropicalWeight::one());

        let result: VectorFst<TropicalWeight> = minimize_hopcroft(&fst).unwrap();
        assert_eq!(result.num_states(), 1);
        assert_eq!(result.start(), Some(0));
    }

    #[test]
    fn test_hopcroft_equivalent_states() {
        // Create FST with equivalent states that should be merged
        let mut fst = VectorFst::<TropicalWeight>::new();
        let s0 = fst.add_state();
        let s1 = fst.add_state();
        let s2 = fst.add_state();
        let s3 = fst.add_state();

        fst.set_start(s0);
        // s1 and s2 are equivalent: both go to s3 on label 1
        fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::one(), s1));
        fst.add_arc(s0, Arc::new(2, 2, TropicalWeight::one(), s2));
        fst.add_arc(s1, Arc::new(1, 1, TropicalWeight::one(), s3));
        fst.add_arc(s2, Arc::new(1, 1, TropicalWeight::one(), s3));
        fst.set_final(s3, TropicalWeight::one());

        let result: VectorFst<TropicalWeight> = minimize_hopcroft(&fst).unwrap();

        // s1 and s2 should be merged, so we should have 3 states
        assert!(result.num_states() <= 3);
    }

    #[test]
    fn test_hopcroft_already_minimal() {
        // Linear chain - already minimal
        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.add_arc(s0, Arc::new(1, 1, TropicalWeight::one(), s1));
        fst.add_arc(s1, Arc::new(2, 2, TropicalWeight::one(), s2));
        fst.set_final(s2, TropicalWeight::one());

        let result: VectorFst<TropicalWeight> = minimize_hopcroft(&fst).unwrap();
        assert_eq!(result.num_states(), 3);
    }

    #[test]
    fn test_hopcroft_preserves_language() {
        // Create a simple acceptor
        let mut fst = VectorFst::<TropicalWeight>::new();
        let s0 = fst.add_state();
        let s1 = fst.add_state();
        let s2 = fst.add_state();
        let s3 = fst.add_state();

        fst.set_start(s0);
        fst.add_arc(
            s0,
            Arc::new(b'a' as u32, b'a' as u32, TropicalWeight::one(), s1),
        );
        fst.add_arc(
            s0,
            Arc::new(b'a' as u32, b'a' as u32, TropicalWeight::one(), s2),
        );
        fst.add_arc(
            s1,
            Arc::new(b'b' as u32, b'b' as u32, TropicalWeight::one(), s3),
        );
        fst.add_arc(
            s2,
            Arc::new(b'b' as u32, b'b' as u32, TropicalWeight::one(), s3),
        );
        fst.set_final(s3, TropicalWeight::one());

        let result: VectorFst<TropicalWeight> = minimize_hopcroft(&fst).unwrap();

        // The minimized FST should accept the same language
        assert!(result.start().is_some());
        // After minimization, s1 and s2 should be merged (they're equivalent)
        assert!(result.num_states() <= 3);
    }

    #[test]
    fn test_hopcroft_combines_arc_weights() {
        // Test that arc weights are properly combined when merging states
        // with multiple arcs to the same target
        let mut fst = VectorFst::<TropicalWeight>::new();
        let s0 = fst.add_state();
        let s1 = fst.add_state();

        fst.set_start(s0);
        fst.set_final(s1, TropicalWeight::one());

        // Two arcs with same label going to same state but different weights
        // In tropical semiring, min(1.0, 2.0) = 1.0
        fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(1.0), s1));
        fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(2.0), s1));

        let result: VectorFst<TropicalWeight> = minimize_hopcroft(&fst).unwrap();

        // Should have same structure
        assert_eq!(result.num_states(), 2);

        // The combined arc should have weight 1.0 (min of 1.0 and 2.0)
        if let Some(start) = result.start() {
            let arcs: Vec<_> = result.arcs(start).collect();
            assert_eq!(arcs.len(), 1, "Should have one combined arc");
            assert_eq!(
                arcs[0].weight,
                TropicalWeight::new(1.0),
                "Weight should be min(1.0, 2.0) = 1.0"
            );
        }
    }
}