arcweight 0.3.0

//! Utility types and data structures for FST operations.
//!
//! This module provides essential supporting utilities used throughout the ArcWeight
//! library for symbol management, state exploration queues, FST visualization, arc
//! encoding, and path iteration.
//!
//! # Overview
//!
//! The utilities in this module fall into several categories:
//!
//! | Component | Purpose | Complexity |
//! |-----------|---------|------------|
//! | [`SymbolTable`] | Symbol-to-label bidirectional mapping | O(1) lookup |
//! | [`Queue`] types | State exploration for FST algorithms | O(1) to O(log n) |
//! | [`EncodeMapper`] | Arc compression for memory efficiency | O(1) per arc |
//! | [`PathsIterator`] | Enumerate accepting paths | O(paths) |
//! | [`DrawingConfig`] | GraphViz DOT visualization | O(V + E) |
//!
//! # Symbol Tables
//!
//! [`SymbolTable`] manages bidirectional mapping between human-readable symbols and
//! numeric labels used in FST arcs:
//!
//! ```
//! use arcweight::utils::SymbolTable;
//!
//! let mut symbols = SymbolTable::new();
//!
//! // Add symbols and get their IDs
//! let cat_id = symbols.add_symbol("cat");
//! let dog_id = symbols.add_symbol("dog");
//!
//! // Bidirectional lookup
//! assert_eq!(symbols.find_id("cat"), Some(cat_id));
//! assert_eq!(symbols.find(cat_id), Some("cat"));
//!
//! // Epsilon is always label 0
//! assert_eq!(symbols.find(0), Some("<eps>"));
//! ```
//!
//! # Queue Types
//!
//! Different queue implementations support various FST traversal strategies:
//!
//! | Queue | Order | Algorithm | Complexity |
//! |-------|-------|-----------|------------|
//! | [`FifoQueue`] | First-In-First-Out | BFS, shortest path | O(1) |
//! | [`LifoQueue`] | Last-In-First-Out | DFS, cycle detection | O(1) |
//! | [`StateQueue`] | Priority-based | Dijkstra, A* | O(log n) |
//! | [`TopOrderQueue`] | Topological | DP on DAGs | O(1) |
//!
//! All queues implement the [`Queue`] trait for algorithm genericity:
//!
//! ```
//! use arcweight::prelude::*;
//! use arcweight::utils::{Queue, FifoQueue, LifoQueue};
//!
//! fn explore_fst<Q: Queue>(fst: &impl Fst<TropicalWeight>, mut queue: Q) {
//!     if let Some(start) = fst.start() {
//!         queue.enqueue(start);
//!         while let Some(state) = queue.dequeue() {
//!             for arc in fst.arcs(state) {
//!                 queue.enqueue(arc.nextstate);
//!             }
//!         }
//!     }
//! }
//!
//! let fst = VectorFst::<TropicalWeight>::new();
//! explore_fst(&fst, FifoQueue::new());  // Breadth-first
//! explore_fst(&fst, LifoQueue::new());  // Depth-first
//! ```
//!
//! # Arc Encoding
//!
//! [`EncodeMapper`] compresses FST arcs by mapping repeated label pairs and weights
//! to compact integer representations:
//!
//! ```
//! use arcweight::utils::{EncodeMapper, EncodeType};
//! use arcweight::prelude::*;
//!
//! let mut encoder = EncodeMapper::<TropicalWeight>::new(EncodeType::EncodeLabelsOnly);
//!
//! let arc = Arc::new(97, 98, TropicalWeight::new(0.5), 1);
//! let encoded = encoder.encode(&arc);
//!
//! // Same label pair always maps to same encoded value
//! let arc2 = Arc::new(97, 98, TropicalWeight::new(1.0), 2);
//! let encoded2 = encoder.encode(&arc2);
//! assert_eq!(encoded.ilabel, encoded2.ilabel);
//! ```
//!
//! # Path Iteration
//!
//! [`PathsIterator`] and [`StringPathsIterator`] enumerate accepting paths through
//! an FST with optional filtering:
//!
//! ```
//! use arcweight::prelude::*;
//! use arcweight::utils::PathIterExt;
//!
//! 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, 2, TropicalWeight::new(0.5), s1));
//!
//! for path in fst.paths_iter().with_max_paths(10) {
//!     println!("Path weight: {:?}", path.weight);
//! }
//! ```
//!
//! # FST Visualization
//!
//! [`draw_fst`] generates GraphViz DOT format for FST visualization:
//!
//! ```
//! use arcweight::prelude::*;
//! use arcweight::utils::{draw_fst_default, DrawingConfig};
//!
//! 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));
//!
//! let dot = draw_fst_default(&fst).unwrap();
//! // Output can be rendered with: dot -Tpng fst.dot -o fst.png
//! ```
//!
//! # Performance Characteristics
//!
//! | Component | Memory | Time (typical operation) |
//! |-----------|--------|-------------------------|
//! | `SymbolTable` | O(n) symbols | O(1) lookup |
//! | `FifoQueue` | O(n) states | O(1) enqueue/dequeue |
//! | `LifoQueue` | O(depth) | O(1) push/pop |
//! | `StateQueue` | O(n) states | O(log n) operations |
//! | `EncodeMapper` | O(unique labels) | O(1) per arc |
//!
//! # References
//!
//! - Mehryar Mohri, Fernando Pereira, and Michael Riley. 2002. Weighted
//!   finite-state transducers in speech recognition. *Computer Speech &
//!   Language* 16, 1 (2002), 69-88.
//!   <https://doi.org/10.1006/csla.2001.0184>

mod drawing;
mod encode;
mod path_iter;
mod queue;
mod symbol_table;

pub use drawing::{draw_fst, draw_fst_default, DrawingConfig};
pub use encode::{EncodeMapper, EncodeType};
pub use path_iter::{FstPath, PathIterExt, PathsIterator, StringPath, StringPathsIterator};
pub use queue::{FifoQueue, LifoQueue, Queue, StateQueue, TopOrderQueue};
pub use symbol_table::SymbolTable;