arcweight 0.3.0

//! Core FST traits defining the fundamental interface for weighted finite-state transducers.
//!
//! This module provides the foundational traits that all FST implementations must satisfy.
//! The trait hierarchy is designed to support a range of FST implementations from simple
//! in-memory structures to lazy, on-demand computed automata.
//!
//! # Trait Hierarchy
//!
//! ```text
//! Fst<W>                  Read-only access to FST structure
//!   |
//!   +-- MutableFst<W>     Construction and modification operations
//!   |
//!   +-- ExpandedFst<W>    Direct slice access to arc arrays
//!   |
//!   +-- LazyFst<W>        On-demand state expansion
//! ```
//!
//! # Type Definitions
//!
//! - [`StateId`]: 32-bit unsigned integer for state identification
//! - [`Label`]: 32-bit unsigned integer for input/output symbols
//! - [`NO_STATE_ID`]: Sentinel value indicating no state (similar to `None`)
//! - [`NO_LABEL`]: Reserved label value 0 for epsilon transitions
//!
//! # References
//!
//! - Mohri, M. (1997). Finite-State Transducers in Language and Speech Processing.
//!   *Computational Linguistics*, 23(2), 269-311.
//!
//! - Mohri, M., Pereira, F., & Riley, M. (2002). Weighted Finite-State Transducers
//!   in Speech Recognition. *Computer Speech & Language*, 16(1), 69-88.

use crate::arc::{Arc, ArcIterator};
use crate::properties::FstProperties;
use crate::semiring::Semiring;
use crate::Result;
use core::fmt::Debug;

/// State identifier type.
///
/// States are identified by 32-bit unsigned integers, allowing up to 2^32 - 1 states
/// (reserving `u32::MAX` as the sentinel value [`NO_STATE_ID`]). States are typically
/// numbered consecutively from 0.
pub type StateId = u32;

/// Label type for input/output symbols.
///
/// Labels are 32-bit unsigned integers representing symbols from the input or output
/// alphabet. Label 0 is reserved for epsilon (empty string) transitions, following
/// the convention established in OpenFst.
pub type Label = u32;

/// Special state ID indicating no state exists.
///
/// This sentinel value is used to represent the absence of a state, similar to
/// `Option::None`. Common uses include indicating that an FST has no start state
/// or that a lookup operation failed to find a matching state.
pub const NO_STATE_ID: StateId = u32::MAX;

/// Special label reserved for epsilon transitions.
///
/// Epsilon transitions consume no input and produce no output, allowing the
/// transducer to change states without reading or writing symbols. This is
/// essential for representing optional elements, alternations, and other
/// patterns that cannot be expressed with purely synchronous transitions.
pub const NO_LABEL: Label = 0;

/// Core trait for all FST types providing read-only access.
///
/// The `Fst` trait defines the fundamental interface for weighted finite-state transducers,
/// providing operations to query the structure, navigate states, and access weights.
/// This trait corresponds to the abstract FST interface described in the OpenFst library
/// design (Allauzen et al., 2007).
///
/// # Type Parameters
///
/// - `W`: The semiring type for arc and final state weights. Must implement [`Semiring`].
///
/// # Associated Types
///
/// - `ArcIter<'a>`: Iterator type for traversing arcs from a state. Must implement
///   [`ArcIterator<W>`] and be valid for the lifetime of the FST reference.
///
/// # Complexity
///
/// The following complexity bounds apply to conforming implementations:
///
/// | Operation | Time Complexity | Notes |
/// |-----------|----------------|-------|
/// | `start()` | $`O(1)`$ | Direct field access |
/// | `final_weight(s)` | $`O(1)`$ | Direct state lookup |
/// | `num_arcs(s)` | $`O(1)`$ | Cached or computed |
/// | `num_states()` | $`O(1)`$ | Cached value |
/// | `arcs(s)` | $`O(1)`$ to create | Iterator creation |
/// | `states()` | $`O(1)`$ to create | Range iterator |
/// | `num_arcs_total()` | $`O(V)`$ | Sums over all states |
///
/// # Implementation Guidelines
///
/// When implementing this trait:
/// - `start()` must return `None` for FSTs with no designated initial state
/// - `final_weight(s)` must return `None` for non-final states and invalid state IDs
/// - Arc iterators must yield arcs in a consistent order across multiple iterations
/// - States are numbered consecutively from 0 to `num_states() - 1`
/// - Label 0 is reserved for epsilon transitions per the OpenFst convention
///
/// # Thread Safety
///
/// All FST implementations are required to be `Send + Sync`, enabling safe sharing
/// between threads for read-only operations. Mutable access requires appropriate
/// synchronization through external means or the [`ConcurrentFst`] implementation.
///
/// # Examples
///
/// ## Basic FST Traversal
///
/// ```rust
/// use arcweight::prelude::*;
///
/// fn analyze_fst<W: Semiring>(fst: &impl Fst<W>) {
///     if let Some(start) = fst.start() {
///         println!("FST has {} states", fst.num_states());
///         println!("Start state: {}", start);
///
///         // Iterate over arcs from start state
///         for arc in fst.arcs(start) {
///             println!("Arc: {} -> {} / {} : {}",
///                      arc.ilabel, arc.olabel, arc.weight, arc.nextstate);
///         }
///
///         // Check if start state is final
///         if let Some(weight) = fst.final_weight(start) {
///             println!("Start state is final with weight: {}", weight);
///         }
///     } else {
///         println!("Empty FST (no start state)");
///     }
/// }
/// ```
///
/// ## Depth-First Traversal
///
/// ```rust
/// use arcweight::prelude::*;
/// use std::collections::HashSet;
///
/// fn count_reachable_states<W: Semiring>(fst: &impl Fst<W>) -> usize {
///     let mut visited = HashSet::new();
///     let mut stack = Vec::new();
///
///     if let Some(start) = fst.start() {
///         stack.push(start);
///     }
///
///     while let Some(state) = stack.pop() {
///         if visited.insert(state) {
///             for arc in fst.arcs(state) {
///                 if !visited.contains(&arc.nextstate) {
///                     stack.push(arc.nextstate);
///                 }
///             }
///         }
///     }
///
///     visited.len()
/// }
/// ```
///
/// # References
///
/// - Allauzen, C., Riley, M., Schalkwyk, J., Skut, W., & Mohri, M. (2007).
///   OpenFst: A General and Efficient Weighted Finite-State Transducer Library.
///   In *Proc. CIAA 2007*, LNCS 4783, pp. 11-23. Springer.
///
/// # See Also
///
/// - [`MutableFst`] for FSTs that support modification
/// - [`ExpandedFst`] for FSTs with direct slice access to arcs
/// - [`LazyFst`] for on-demand computed FSTs
///
/// [`VectorFst`]: crate::fst::VectorFst
/// [`ConstFst`]: crate::fst::ConstFst
/// [`CacheFst`]: crate::fst::CacheFst
/// [`ConcurrentFst`]: crate::fst::ConcurrentFst
pub trait Fst<W: Semiring>: Debug + Send + Sync {
    /// Arc iterator type for traversing outgoing transitions.
    ///
    /// This associated type must implement [`ArcIterator<W>`] and produce
    /// [`Arc<W>`] items representing the outgoing transitions from a state.
    type ArcIter<'a>: ArcIterator<W>
    where
        Self: 'a;

    /// Returns the unique start (initial) state of the FST.
    ///
    /// # Returns
    ///
    /// - `Some(state_id)` if the FST has a designated start state
    /// - `None` if the FST has no start state (empty or uninitialized)
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - direct field access.
    fn start(&self) -> Option<StateId>;

    /// Returns the final weight for a state, if the state is final.
    ///
    /// In weighted FST theory, a state is final (accepting) if it has a
    /// non-zero final weight. The final weight contributes to the total
    /// weight of paths that end in this state.
    ///
    /// # Arguments
    ///
    /// * `state` - The state identifier to query
    ///
    /// # Returns
    ///
    /// - `Some(&weight)` if the state is final
    /// - `None` if the state is non-final or the state ID is invalid
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - direct state lookup.
    fn final_weight(&self, state: StateId) -> Option<&W>;

    /// Checks whether a state is final (accepting).
    ///
    /// This is a convenience method equivalent to `self.final_weight(state).is_some()`.
    ///
    /// # Arguments
    ///
    /// * `state` - The state identifier to check
    ///
    /// # Returns
    ///
    /// `true` if the state has a final weight, `false` otherwise.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - delegates to `final_weight`.
    fn is_final(&self, state: StateId) -> bool {
        self.final_weight(state).is_some()
    }

    /// Returns the number of outgoing arcs from a state.
    ///
    /// # Arguments
    ///
    /// * `state` - The state identifier to query
    ///
    /// # Returns
    ///
    /// The count of outgoing transitions from the state, or 0 if the
    /// state ID is invalid.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - typically cached or directly computed from storage.
    fn num_arcs(&self, state: StateId) -> usize;

    /// Returns the total number of states in the FST.
    ///
    /// States are numbered from 0 to `num_states() - 1`. Not all states
    /// may be reachable from the start state; use graph traversal algorithms
    /// to compute the reachable subset.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - cached value.
    fn num_states(&self) -> usize;

    /// Returns the computed or cached properties of the FST.
    ///
    /// FST properties encode structural characteristics such as whether
    /// the FST is deterministic, has epsilon transitions, is acyclic, etc.
    /// These properties can be used to select optimized algorithm variants.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ if cached, $`O(V + E)`$ if computed on demand.
    fn properties(&self) -> FstProperties;

    /// Creates an iterator over arcs leaving a state.
    ///
    /// The iterator yields [`Arc<W>`] values representing outgoing transitions.
    /// Each arc contains the input label, output label, weight, and target state.
    ///
    /// # Arguments
    ///
    /// * `state` - The source state for arc iteration
    ///
    /// # Returns
    ///
    /// An iterator over the outgoing arcs. If the state ID is invalid,
    /// returns an empty iterator.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ to create the iterator. Iteration itself is $`O(k)`$ where
    /// $`k`$ is the number of arcs from the state.
    fn arcs(&self, state: StateId) -> Self::ArcIter<'_>;

    /// Returns an iterator over all state identifiers.
    ///
    /// This provides a convenient way to iterate over all states in the FST
    /// without needing to know the internal storage format.
    ///
    /// # Returns
    ///
    /// An iterator yielding state IDs from 0 to `num_states() - 1`.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ to create. Full iteration is $`O(V)`$ where $`V`$ is the state count.
    fn states(&self) -> impl Iterator<Item = StateId> {
        0..self.num_states() as StateId
    }

    /// Returns the total number of arcs across all states.
    ///
    /// This is useful for estimating memory requirements or algorithm complexity.
    ///
    /// # Complexity
    ///
    /// $`O(V)`$ where $`V`$ is the number of states, as it must sum arc counts.
    fn num_arcs_total(&self) -> usize {
        self.states().map(|s| self.num_arcs(s)).sum()
    }

    /// Checks whether the FST is empty (has no start state or no states).
    ///
    /// An FST is considered empty if it has no designated start state or
    /// contains zero states, meaning it accepts no strings.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - checks cached values.
    fn is_empty(&self) -> bool {
        self.start().is_none() || self.num_states() == 0
    }
}

/// Trait for FSTs that support modification operations.
///
/// The `MutableFst` trait extends [`Fst`] with operations for constructing and
/// modifying FST structure. This includes adding states and arcs, setting start
/// and final states, and managing the FST's topology. Implementations provide
/// the foundation for FST construction algorithms and dynamic modifications.
///
/// # Type Parameters
///
/// - `W`: The semiring type for arc and final state weights.
///
/// # Complexity
///
/// The following complexity bounds apply to conforming implementations:
///
/// | Operation | Time Complexity | Notes |
/// |-----------|----------------|-------|
/// | `add_state()` | $`O(1)`$ amortized | May trigger reallocation |
/// | `add_arc(s, arc)` | $`O(1)`$ amortized | Appends to state's arc list |
/// | `set_start(s)` | $`O(1)`$ | Direct field assignment |
/// | `set_final(s, w)` | $`O(1)`$ | Direct state update |
/// | `delete_arcs(s)` | $`O(k)`$ | $`k`$ = arcs from state |
/// | `clear()` | $`O(V + E)`$ | Deallocates all storage |
///
/// # Implementation Guidelines
///
/// When implementing this trait:
/// - `add_state()` must return a unique, sequential state ID starting from 0
/// - State IDs must remain valid after insertion (no compaction during mutation)
/// - `set_final()` with `W::zero()` should remove final status (semiring zero)
/// - `clear()` must reset to an empty FST with no states or arcs
/// - Memory reservations are optimization hints and may be ignored
///
/// # Construction Patterns
///
/// ## Basic FST Construction
///
/// ```rust
/// use arcweight::prelude::*;
///
/// fn build_simple_fst() -> VectorFst<TropicalWeight> {
///     let mut fst = VectorFst::new();
///
///     // Add states
///     let s0 = fst.add_state();
///     let s1 = fst.add_state();
///
///     // Set start state
///     fst.set_start(s0);
///
///     // Add an arc: input 'a', output 'b', weight 1.5
///     fst.add_arc(s0, Arc::new(
///         'a' as u32,
///         'b' as u32,
///         TropicalWeight::new(1.5),
///         s1
///     ));
///
///     // Make s1 final with identity weight
///     fst.set_final(s1, TropicalWeight::one());
///
///     fst
/// }
/// ```
///
/// ## Efficient Batch Construction
///
/// ```rust
/// use arcweight::prelude::*;
///
/// fn build_trie_fst(words: &[&str]) -> VectorFst<BooleanWeight> {
///     let mut fst = VectorFst::new();
///
///     // Pre-allocate for better performance
///     let estimated_states = words.iter().map(|w| w.len()).sum::<usize>();
///     fst.reserve_states(estimated_states);
///
///     let start = fst.add_state();
///     fst.set_start(start);
///
///     for word in words {
///         let mut current = start;
///         for ch in word.chars() {
///             let next = fst.add_state();
///             fst.add_arc(current, Arc::new(
///                 ch as u32, ch as u32, BooleanWeight::one(), next
///             ));
///             current = next;
///         }
///         fst.set_final(current, BooleanWeight::one());
///     }
///
///     fst
/// }
/// ```
///
/// # References
///
/// - Allauzen, C., Riley, M., Schalkwyk, J., Skut, W., & Mohri, M. (2007).
///   OpenFst: A General and Efficient Weighted Finite-State Transducer Library.
///   In *Proc. CIAA 2007*, LNCS 4783, pp. 11-23. Springer.
///
/// # See Also
///
/// - [`Fst`] for read-only operations
/// - [`VectorFst`] for the primary mutable implementation
/// - [`ConcurrentFst`] for thread-safe mutable access
///
/// [`VectorFst`]: crate::fst::VectorFst
/// [`ConcurrentFst`]: crate::fst::ConcurrentFst
pub trait MutableFst<W: Semiring>: Fst<W> {
    /// Adds a new state to the FST and returns its identifier.
    ///
    /// The returned state ID is guaranteed to be unique within this FST and
    /// will be the smallest unused non-negative integer (typically the current
    /// state count before insertion).
    ///
    /// # Returns
    ///
    /// The identifier of the newly created state.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ amortized, may trigger reallocation.
    fn add_state(&mut self) -> StateId;

    /// Adds an arc (transition) from the specified source state.
    ///
    /// The arc specifies the input label, output label, weight, and target
    /// state for the transition. Arcs are typically stored in insertion order.
    ///
    /// # Arguments
    ///
    /// * `state` - The source state for the arc
    /// * `arc` - The arc to add, containing labels, weight, and target state
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ amortized, may trigger reallocation of the state's arc storage.
    fn add_arc(&mut self, state: StateId, arc: Arc<W>);

    /// Sets the start (initial) state of the FST.
    ///
    /// An FST can have at most one start state. Setting a new start state
    /// replaces any previously set start state.
    ///
    /// # Arguments
    ///
    /// * `state` - The state ID to designate as the start state
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - direct field assignment.
    fn set_start(&mut self, state: StateId);

    /// Sets the final weight for a state, making it a final (accepting) state.
    ///
    /// If `weight` equals the semiring zero element, the state becomes non-final.
    /// Otherwise, the state is marked as final with the given weight.
    ///
    /// # Arguments
    ///
    /// * `state` - The state to modify
    /// * `weight` - The final weight (use semiring zero to make non-final)
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - direct state update.
    fn set_final(&mut self, state: StateId, weight: W);

    /// Removes the final weight from a state, making it non-final.
    ///
    /// This is equivalent to `set_final(state, W::zero())`.
    ///
    /// # Arguments
    ///
    /// * `state` - The state to make non-final
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - delegates to `set_final`.
    fn remove_final(&mut self, state: StateId) {
        self.set_final(state, W::zero());
    }

    /// Deletes all arcs from a state.
    ///
    /// After this operation, `num_arcs(state)` returns 0 and `arcs(state)`
    /// yields an empty iterator.
    ///
    /// # Arguments
    ///
    /// * `state` - The state whose arcs should be deleted
    ///
    /// # Complexity
    ///
    /// $`O(k)`$ where $`k`$ is the number of arcs from the state.
    fn delete_arcs(&mut self, state: StateId);

    /// Deletes a single arc from a state by index.
    ///
    /// Arcs are indexed from 0 to `num_arcs(state) - 1` in iteration order.
    /// Deleting an arc may change the indices of subsequent arcs.
    ///
    /// # Arguments
    ///
    /// * `state` - The source state of the arc
    /// * `arc_idx` - The index of the arc to delete
    ///
    /// # Complexity
    ///
    /// $`O(k)`$ where $`k`$ is the number of arcs, due to potential shifting.
    fn delete_arc(&mut self, state: StateId, arc_idx: usize);

    /// Reserves capacity for additional states.
    ///
    /// This is an optimization hint that may reduce reallocations during
    /// construction. Implementations may ignore this hint.
    ///
    /// # Arguments
    ///
    /// * `n` - The number of additional states to reserve space for
    ///
    /// # Complexity
    ///
    /// $`O(n)`$ in the worst case if reallocation is required.
    fn reserve_states(&mut self, n: usize);

    /// Reserves capacity for additional arcs from a state.
    ///
    /// This is an optimization hint that may reduce reallocations when
    /// adding arcs. Implementations may ignore this hint.
    ///
    /// # Arguments
    ///
    /// * `state` - The state to reserve arc capacity for
    /// * `n` - The number of additional arcs to reserve space for
    ///
    /// # Complexity
    ///
    /// $`O(n)`$ in the worst case if reallocation is required.
    fn reserve_arcs(&mut self, state: StateId, n: usize);

    /// Clears all states and arcs, resetting the FST to empty.
    ///
    /// After this operation, `num_states()` returns 0 and `start()` returns `None`.
    ///
    /// # Complexity
    ///
    /// $`O(V + E)`$ to deallocate all states and arcs.
    fn clear(&mut self);
}

/// Trait for FSTs with all states and arcs expanded in memory.
///
/// The `ExpandedFst` trait is implemented by FST types that maintain all arc data
/// in contiguous memory, enabling direct slice access for high-performance operations.
/// This is in contrast to lazy or on-demand FSTs where arcs may be computed at access time.
///
/// # Type Parameters
///
/// - `W`: The semiring type for arc weights.
///
/// # Performance Benefits
///
/// Direct slice access provides several advantages over iterator-based access:
///
/// - **Zero iterator overhead**: No per-element virtual dispatch
/// - **Cache efficiency**: Contiguous memory enables hardware prefetching
/// - **SIMD compatibility**: Slice operations can be vectorized
/// - **Multiple passes**: Efficient for algorithms requiring repeated arc access
///
/// # Complexity
///
/// | Operation | Time Complexity | Notes |
/// |-----------|----------------|-------|
/// | `arcs_slice(s)` | $`O(1)`$ | Returns slice reference |
/// | Slice iteration | $`O(k)`$ | $`k`$ = arcs from state |
///
/// # Examples
///
/// ## Counting Epsilon Arcs
///
/// ```rust
/// use arcweight::prelude::*;
///
/// fn count_epsilon_arcs<W: Semiring>(fst: &impl ExpandedFst<W>) -> usize {
///     fst.states()
///         .map(|state| {
///             fst.arcs_slice(state)
///                 .iter()
///                 .filter(|arc| arc.ilabel == 0)
///                 .count()
///         })
///         .sum()
/// }
/// ```
///
/// ## Parallel Arc Processing
///
/// ```rust
/// use arcweight::prelude::*;
///
/// fn find_max_weight_arc<W: Semiring + Ord>(
///     fst: &impl ExpandedFst<W>,
///     state: StateId
/// ) -> Option<&Arc<W>> {
///     fst.arcs_slice(state)
///         .iter()
///         .max_by(|a, b| a.weight.partial_cmp(&b.weight).unwrap())
/// }
/// ```
///
/// # Implementations
///
/// This trait is implemented by FST types that store arcs in memory:
///
/// - [`VectorFst`]: Dynamic construction with slice access
/// - [`ConstFst`]: Optimized read-only with contiguous storage
/// - [`CsrFst`]: Cache-optimized CSR format
///
/// Note: Lazy FST types ([`LazyFstImpl`], [`CacheFst`]) do not implement this trait
/// because their arcs may be computed on demand.
///
/// [`VectorFst`]: crate::fst::VectorFst
/// [`ConstFst`]: crate::fst::ConstFst
/// [`CsrFst`]: crate::fst::CsrFst
/// [`LazyFstImpl`]: crate::fst::LazyFstImpl
/// [`CacheFst`]: crate::fst::CacheFst
pub trait ExpandedFst<W: Semiring>: Fst<W> {
    /// Returns a slice of all arcs from a state.
    ///
    /// Unlike the iterator-based `arcs()` method, this returns a direct slice
    /// reference to the arc storage, enabling efficient indexed access and
    /// operations that require multiple passes over the arcs.
    ///
    /// # Arguments
    ///
    /// * `state` - The state whose arcs to retrieve
    ///
    /// # Returns
    ///
    /// A slice containing all outgoing arcs from the state. Returns an empty
    /// slice if the state ID is invalid or the state has no outgoing arcs.
    ///
    /// # Complexity
    ///
    /// $`O(1)`$ - returns a reference to existing storage.
    fn arcs_slice(&self, state: StateId) -> &[Arc<W>];
}

/// Trait for FSTs with on-demand (lazy) state computation.
///
/// The `LazyFst` trait extends [`Fst`] with explicit state expansion operations
/// for FSTs where states and arcs are computed dynamically rather than stored
/// in memory. This is essential for handling very large or infinite state spaces
/// that cannot be materialized entirely.
///
/// # Type Parameters
///
/// - `W`: The semiring type for arc weights.
///
/// # Use Cases
///
/// - **Composition**: On-the-fly computation of composed FST state pairs
/// - **Grammar intersection**: Dynamic exploration of parse forests
/// - **Search spaces**: State spaces too large to enumerate fully
/// - **External data**: States backed by databases or network services
///
/// # Examples
///
/// ```no_run
/// use arcweight::prelude::*;
/// use arcweight::fst::LazyFst;
///
/// fn expand_and_process<W: Semiring>(
///     fst: &impl LazyFst<W>,
///     state: StateId
/// ) -> arcweight::Result<()> {
///     // Ensure state is expanded before accessing arcs
///     fst.expand(state)?;
///
///     // Now arcs are available
///     for arc in fst.arcs(state) {
///         println!("Arc to state {}", arc.nextstate);
///     }
///
///     Ok(())
/// }
/// ```
///
/// # References
///
/// - Mohri, M., Pereira, F., & Riley, M. (2000). The Design Principles of a
///   Weighted Finite-State Transducer Library. *Theoretical Computer Science*,
///   231(1), 17-32.
pub trait LazyFst<W: Semiring>: Fst<W> {
    /// Expands a state by computing its arcs on demand.
    ///
    /// After successful expansion, the state's arcs are available via `arcs()`.
    /// Implementations may cache expanded states for subsequent access.
    ///
    /// # Arguments
    ///
    /// * `state` - The state identifier to expand
    ///
    /// # Returns
    ///
    /// - `Ok(())` if expansion succeeded
    /// - `Err(...)` if expansion failed
    ///
    /// # Errors
    ///
    /// Returns an error if:
    /// - The state ID is invalid or does not exist in the lazy state space
    /// - Computation of the state's arcs fails
    /// - Memory allocation fails during arc storage
    /// - External data sources (if any) are unavailable
    ///
    /// # Complexity
    ///
    /// Varies by implementation. Typically $`O(k)`$ where $`k`$ is the number
    /// of arcs computed for the state, plus any overhead from the computation
    /// function.
    fn expand(&self, state: StateId) -> Result<()>;
}

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

    #[test]
    fn test_state_id_constants() {
        assert_eq!(NO_STATE_ID, u32::MAX);
        assert_eq!(NO_LABEL, 0);
    }

    #[test]
    fn test_fst_trait_default_methods() {
        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());
        fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(0.5), s1));

        // Test is_final
        assert!(!fst.is_final(s0));
        assert!(fst.is_final(s1));

        // Test states iterator
        let states: Vec<_> = fst.states().collect();
        assert_eq!(states, vec![0, 1]);

        // Test num_arcs_total
        assert_eq!(fst.num_arcs_total(), 1);

        // Test is_empty
        assert!(!fst.is_empty());

        let empty_fst = VectorFst::<TropicalWeight>::new();
        assert!(empty_fst.is_empty());
    }

    #[test]
    fn test_mutable_fst_trait_methods() {
        let mut fst = VectorFst::<TropicalWeight>::new();

        // Test add_state
        let s0 = fst.add_state();
        let s1 = fst.add_state();
        assert_eq!(fst.num_states(), 2);

        // Test set_start
        fst.set_start(s0);
        assert_eq!(fst.start(), Some(s0));

        // Test add_arc
        fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::new(2.0), s1));
        assert_eq!(fst.num_arcs(s0), 1);

        // Test set_final and remove_final
        fst.set_final(s1, TropicalWeight::new(3.0));
        assert!(fst.is_final(s1));

        fst.remove_final(s1);
        assert!(!fst.is_final(s1));

        // Test clear
        fst.clear();
        assert_eq!(fst.num_states(), 0);
        assert!(fst.is_empty());
    }

    #[test]
    fn test_expanded_fst_trait() {
        let mut fst = VectorFst::<TropicalWeight>::new();
        let s0 = fst.add_state();
        let s1 = fst.add_state();

        fst.add_arc(s0, Arc::new(1, 1, TropicalWeight::one(), s1));
        fst.add_arc(s0, Arc::new(2, 2, TropicalWeight::new(0.5), s1));

        // Test arcs_slice
        let arcs = fst.arcs_slice(s0);
        assert_eq!(arcs.len(), 2);
        assert_eq!(arcs[0].ilabel, 1);
        assert_eq!(arcs[1].ilabel, 2);

        // Test empty state
        let empty_arcs = fst.arcs_slice(s1);
        assert_eq!(empty_arcs.len(), 0);
    }
}