libdictenstein 0.1.0

//! Character-level Dynamic DAWG with online modifications and Unicode support.
//!
//! This implementation supports incremental updates while maintaining
//! "near-minimal" structure. Perfect minimality can be restored via
//! explicit compaction.
//!
//! Unlike the byte-level `DynamicDawg`, this variant operates on Unicode
//! scalar values (`char`), providing correct character-level Levenshtein
//! distances for multi-byte UTF-8 sequences.
//!
//! # Performance Trade-offs
//!
//! - **Memory**: ~4x edge label storage (4 bytes per `char` vs 1 byte per `u8`)
//! - **Speed**: ~5-10% slower due to UTF-8 decoding
//! - **Correctness**: Proper Unicode semantics (e.g., "" → "¡" = distance 1, not 2)

use crate::dynamic_dawg_char_zipper::DynamicDawgCharZipper;
use crate::iterator::DictionaryIterator;
use crate::sync_compat::RwLock;
use crate::value::DictionaryValue;
use crate::{Dictionary, DictionaryNode, SyncStrategy};
use rustc_hash::FxHashMap;
use smallvec::SmallVec;
use std::sync::Arc;

/// A dynamic DAWG that supports online insertions and deletions.
///
/// # Type Parameters
///
/// - `V`: Optional value type associated with each term. Use `()` (default) for
///   dictionaries without values, or any type implementing `DictionaryValue`
///   (Clone + Send + Sync + 'static) for value-storing dictionaries.
///
/// # Minimality Trade-offs
///
/// - **After insertion**: Structure remains minimal (new nodes are shared)
/// - **After deletion**: May become non-minimal (orphaned branches)
/// - **Solution**: Call `compact()` periodically to restore minimality
///
/// # Thread Safety
///
/// Uses `Arc<RwLock<...>>` for interior mutability. Safe for concurrent
/// reads, exclusive writes.
///
/// # Performance
///
/// - Insertion: O(m) where m is term length (amortized)
/// - Deletion: O(m)
/// - Compaction: O(n) where n is total characters
/// - Space: Near-minimal to ~1.5x minimal (worst case between compactions)
///
/// # Examples
///
/// ```text
/// // Without values (default)
/// let mut dict = DynamicDawgChar::new();
/// dict.insert("hello");
///
/// // With values
/// let dict: DynamicDawgChar<u32> = DynamicDawgChar::new();
/// dict.insert_with_value("hello", 42);
/// ```
#[derive(Clone, Debug)]
pub struct DynamicDawgChar<V: DictionaryValue = ()> {
    pub(crate) inner: Arc<RwLock<DynamicDawgCharInner<V>>>,
}

// C1b algorithmic dedup (char DAWG): mirror of the byte path —
// the local `DynamicDawgCharInner<V>` struct + impl block was
// byte-for-byte identical to `crate::dawg_core::DawgCore<char, V>`.
// Replace with a type alias so all algorithmic methods live on the
// canonical generic core.
pub(crate) type DynamicDawgCharInner<V = ()> = crate::dawg_core::DawgCore<char, V>;

// C1 step (DAWG char variant): byte-for-byte-identical local
// `BloomFilter` is replaced with `crate::bloom_filter::BloomFilter`.
// Node signatures now live entirely in the canonical generic DAWG core.
use crate::bloom_filter::BloomFilter;

// C1 step (DAWG char variant): byte-for-byte-identical local
// `DawgNodeChar<V>` struct + 2-method impl block replaced with a type
// alias to the generic `crate::dawg_core::DawgNode<char, V>`. Derives
// + serde attrs live on the canonical struct, inherited by the alias.
pub(crate) type DawgNodeChar<V = ()> = crate::dawg_core::DawgNode<char, V>;

// Local `impl BloomFilter` removed — canonical type at
// `crate::bloom_filter` provides equivalent inherent methods (new,
// insert, might_contain, clear). Inherent impls on foreign types are
// not allowed in Rust, so this block had to go.

impl<V: DictionaryValue> DynamicDawgChar<V> {
    /// Create a new empty dynamic DAWG.
    ///
    /// By default, auto-minimization is disabled. Use `with_auto_minimize_threshold()`
    /// to enable automatic minimization.
    ///
    /// # Example
    ///
    /// ```text
    /// // Without values (default)
    /// let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();
    /// dawg.insert("hello");
    ///
    /// // With values
    /// let dawg: DynamicDawgChar<u32> = DynamicDawgChar::new();
    /// dawg.insert_with_value("hello", 42);
    /// ```
    pub fn new() -> Self {
        Self::with_auto_minimize_threshold(f32::INFINITY)
    }

    /// Create a new empty dynamic DAWG with custom auto-minimize threshold.
    ///
    /// The auto-minimize threshold determines when the DAWG automatically
    /// triggers minimization. A value of 1.5 means minimize when node count
    /// grows to 1.5x the last minimized size (50% bloat).
    ///
    /// # Parameters
    ///
    /// - `threshold`: Bloat ratio to trigger minimization (e.g., 1.5 = 50% bloat).
    ///   Use `f32::INFINITY` to disable auto-minimization.
    ///
    /// # Example
    ///
    /// ```text
    /// // Auto-minimize at 50% bloat (default)
    /// let dawg: DynamicDawgChar<()> = DynamicDawgChar::with_auto_minimize_threshold(1.5);
    ///
    /// // Disable auto-minimization (manual minimize() calls only)
    /// let dawg: DynamicDawgChar<()> = DynamicDawgChar::with_auto_minimize_threshold(f32::INFINITY);
    /// ```
    pub fn with_auto_minimize_threshold(threshold: f32) -> Self {
        Self::with_config(threshold, None)
    }

    /// Create a new empty dynamic DAWG with full configuration.
    ///
    /// # Parameters
    ///
    /// - `auto_minimize_threshold`: Bloat ratio to trigger minimization. Use `f32::INFINITY` to disable.
    /// - `bloom_filter_capacity`: Optional Bloom filter capacity for negative lookup optimization.
    ///   Use `Some(expected_size)` to enable, `None` to disable.
    ///
    /// # Example
    ///
    /// ```text
    /// // With Bloom filter for 10000 expected terms
    /// let dawg: DynamicDawgChar<()> = DynamicDawgChar::with_config(f32::INFINITY, Some(10000));
    ///
    /// // Without Bloom filter
    /// let dawg: DynamicDawgChar<()> = DynamicDawgChar::with_config(1.5, None);
    /// ```
    pub fn with_config(auto_minimize_threshold: f32, bloom_filter_capacity: Option<usize>) -> Self {
        let nodes = vec![DawgNodeChar::new(false)]; // Root at index 0

        let bloom_filter = bloom_filter_capacity.map(BloomFilter::new);

        DynamicDawgChar {
            inner: Arc::new(RwLock::new(DynamicDawgCharInner {
                nodes,
                term_count: 0,
                needs_compaction: false,
                suffix_cache: FxHashMap::default(),
                last_minimized_node_count: 1, // Start with root node
                auto_minimize_threshold,
                bloom_filter,
            })),
        }
    }

    /// Create from an iterator of terms (optimized batch insert).
    ///
    /// This method sorts terms before insertion for better prefix/suffix sharing.
    pub fn from_terms<I, S>(terms: I) -> Self
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        let mut term_vec: Vec<String> = terms.into_iter().map(|s| s.as_ref().to_string()).collect();
        term_vec.sort_unstable();

        let dawg = Self::new();
        for term in term_vec {
            dawg.insert(&term);
        }
        dawg
    }

    /// Create from sorted terms (assumes pre-sorted input).
    ///
    /// # Performance
    ///
    /// This is faster than `from_terms()` if your input is already sorted,
    /// as it skips the sorting step and takes advantage of better prefix sharing.
    ///
    /// # Example
    ///
    /// ```text
    /// let mut terms = vec!["apple", "banana", "cherry"];
    /// terms.sort();  // Already sorted
    /// let dawg: DynamicDawgChar<()> = DynamicDawgChar::from_sorted_terms(terms);
    /// ```
    pub fn from_sorted_terms<I, S>(terms: I) -> Self
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        let dawg = Self::new();
        for term in terms {
            dawg.insert(term.as_ref());
        }
        dawg
    }

    /// Create from an iterator of `(term, value)` pairs.
    ///
    /// Terms are sorted before insertion so the resulting DAWG benefits from
    /// the same prefix/suffix sharing as [`from_terms`](Self::from_terms).
    pub fn from_terms_with_values<I, S>(entries: I) -> Self
    where
        I: IntoIterator<Item = (S, V)>,
        S: AsRef<str>,
    {
        let mut pairs: Vec<(String, V)> = entries
            .into_iter()
            .map(|(s, v)| (s.as_ref().to_string(), v))
            .collect();
        pairs.sort_by(|a, b| a.0.cmp(&b.0));

        let dawg = Self::new();
        for (term, value) in pairs {
            dawg.insert_with_value(&term, value);
        }
        dawg
    }

    /// Insert a term into the DAWG.
    ///
    /// Returns `true` if the term was newly inserted, `false` if it already existed.
    ///
    /// # Minimality
    ///
    /// Insertions maintain minimality by sharing suffixes with existing nodes.
    pub fn insert(&self, term: &str) -> bool {
        let mut inner = self.inner.write();
        let chars: Vec<char> = term.chars().collect();
        let inserted = inner.insert_units(&chars);
        if inserted {
            inner.bloom_insert(term);
        }
        inserted
    }

    /// Insert a term with an associated value.
    ///
    /// Returns `true` if the term was newly inserted, `false` if it already existed.
    /// If the term already exists, its value is updated.
    ///
    /// # Example
    ///
    /// ```text
    /// let dict: DynamicDawgChar<u32> = DynamicDawgChar::new();
    /// assert!(dict.insert_with_value("hello", 42));
    /// assert!(!dict.insert_with_value("hello", 43)); // Updates value
    /// assert_eq!(dict.get_value("hello"), Some(43));
    /// ```
    pub fn insert_with_value(&self, term: &str, value: V) -> bool {
        let mut inner = self.inner.write();
        let chars: Vec<char> = term.chars().collect();
        let inserted = inner.insert_units_with_value(&chars, value);
        if inserted {
            inner.bloom_insert(term);
        }
        inserted
    }

    /// Update an existing term's value in place, or insert a new term with a default value.
    ///
    /// This method is useful when you want to incrementally modify a value (e.g., adding
    /// elements to a `HashSet` or `Vec`) without replacing it entirely.
    ///
    /// # Arguments
    ///
    /// * `term` - The term to update or insert
    /// * `default_value` - The value to use if the term doesn't exist
    /// * `update_fn` - Function to apply to the existing value if the term exists
    ///
    /// # Returns
    ///
    /// `true` if this was a new term (inserted with default), `false` if an existing term was updated.
    ///
    /// # Example
    ///
    /// ```text
    /// use std::collections::HashSet;
    ///
    /// let dict: DynamicDawgChar<HashSet<u32>> = DynamicDawgChar::new();
    ///
    /// // First call: inserts with default value {1}
    /// assert!(dict.update_or_insert("foo", HashSet::from([1]), |set| { set.insert(1); }));
    ///
    /// // Second call: updates existing value to {1, 2}
    /// assert!(!dict.update_or_insert("foo", HashSet::from([2]), |set| { set.insert(2); }));
    ///
    /// assert_eq!(dict.get_value("foo"), Some(HashSet::from([1, 2])));
    /// ```
    pub fn update_or_insert<F>(&self, term: &str, default_value: V, update_fn: F) -> bool
    where
        F: FnOnce(&mut V),
    {
        let mut inner = self.inner.write();
        let chars: Vec<char> = term.chars().collect();
        let inserted = inner.update_or_insert_units(&chars, default_value, update_fn);
        if inserted {
            inner.bloom_insert(term);
        }
        inserted
    }

    /// Get the value associated with a term.
    ///
    /// Returns `Some(value)` if the term exists, `None` otherwise.
    ///
    /// # Example
    ///
    /// ```text
    /// let dict: DynamicDawgChar<String> = DynamicDawgChar::new();
    /// dict.insert_with_value("key", "value".to_string());
    /// assert_eq!(dict.get_value("key"), Some("value".to_string()));
    /// assert_eq!(dict.get_value("unknown"), None);
    /// ```
    pub fn get_value(&self, term: &str) -> Option<V> {
        let inner = self.inner.read();
        let chars: Vec<char> = term.chars().collect();
        let mut node_idx = 0;

        // Navigate to the term
        for &ch in &chars {
            match inner.nodes[node_idx]
                .edges
                .iter()
                .find(|(c, _)| *c == ch)
                .map(|(_, idx)| idx)
            {
                Some(&child_idx) => node_idx = child_idx,
                None => return None,
            }
        }

        // Check if final and return value
        if inner.nodes[node_idx].is_final {
            inner.nodes[node_idx].value.clone()
        } else {
            None
        }
    }

    /// Remove a term from the DAWG.
    ///
    /// Returns `true` if the term was present and removed, `false` otherwise.
    ///
    /// # Minimality
    ///
    /// Deletions may leave the DAWG non-minimal. Call `compact()` to restore
    /// minimality by removing unreachable nodes.
    pub fn remove(&self, term: &str) -> bool {
        let mut inner = self.inner.write();
        let chars: Vec<char> = term.chars().collect();
        inner.remove_units(&chars)
    }

    /// Compact the DAWG to restore perfect minimality.
    ///
    /// This rebuilds the internal structure, merging equivalent suffixes
    /// and removing unreachable nodes. Ideal for batch operations:
    ///
    /// ```text
    /// // Batch updates
    /// dawg.insert("term1");
    /// dawg.insert("term2");
    /// dawg.remove("term3");
    /// // ... many more operations ...
    ///
    /// // Single compaction at the end
    /// let removed = dawg.compact();
    /// ```
    ///
    /// **Note**: This does a full rebuild (extracts, sorts, reconstructs, minimizes).
    /// For incremental minimization without rebuilding, use `minimize()`.
    ///
    /// Returns the number of nodes removed.
    pub fn compact(&self) -> usize {
        let mut inner = self.inner.write();
        inner.compact()
    }

    /// Minimize the DAWG using incremental suffix merging.
    ///
    /// Unlike `compact()`, this method:
    /// - **Makes no assumptions** about insertion order
    /// - **Only examines affected nodes** and their neighbors
    /// - **Preserves existing structure** where possible
    /// - **Faster than compact()** for localized updates
    ///
    /// This implements incremental minimization based on node signatures.
    /// If the DAWG was minimal before updates, only the new paths and
    /// their neighbors need to be examined.
    ///
    /// ```text
    /// // DAWG is minimal
    /// dawg.minimize();
    ///
    /// // Add some terms (locally affects structure)
    /// dawg.insert("newterm1");
    /// dawg.insert("newterm2");
    ///
    /// // Incremental minimize - only examines affected paths
    /// let merged = dawg.minimize(); // Much faster than compact()!
    /// ```
    ///
    /// Returns the number of nodes merged.
    pub fn minimize(&self) -> usize {
        let mut inner = self.inner.write();
        inner.minimize_incremental()
    }

    /// Batch insert multiple terms, then compact.
    ///
    /// This is more efficient than calling `insert()` followed by `compact()`
    /// separately, as it sorts terms for better prefix sharing and only rebuilds once.
    ///
    /// Returns the number of new terms added.
    pub fn extend<I, S>(&self, terms: I) -> usize
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        // Collect and sort for optimal prefix sharing
        let mut term_vec: Vec<String> = terms.into_iter().map(|s| s.as_ref().to_string()).collect();
        term_vec.sort_unstable();

        let mut added = 0;
        for term in term_vec {
            if self.insert(&term) {
                added += 1;
            }
        }

        if added > 0 {
            self.compact();
        }

        added
    }

    /// Batch remove multiple terms, then compact.
    ///
    /// More efficient than individual `remove()` calls followed by `compact()`.
    ///
    /// Returns the number of terms removed.
    pub fn remove_many<I, S>(&self, terms: I) -> usize
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        let mut removed = 0;
        for term in terms {
            if self.remove(term.as_ref()) {
                removed += 1;
            }
        }

        if removed > 0 {
            self.compact();
        }

        removed
    }

    /// Get the number of terms in the DAWG.
    pub fn term_count(&self) -> usize {
        self.inner.read().term_count
    }

    /// Get the number of nodes in the DAWG.
    pub fn node_count(&self) -> usize {
        self.inner.read().nodes.len()
    }

    /// Check if compaction is recommended.
    ///
    /// Returns `true` if deletions have occurred and compaction would
    /// likely reduce memory usage.
    pub fn needs_compaction(&self) -> bool {
        self.inner.read().needs_compaction
    }

    /// Check if a term is in the DAWG.
    ///
    /// This method is optimized with a Bloom filter (if enabled) for fast negative lookup rejection.
    pub fn contains(&self, term: &str) -> bool {
        let inner = self.inner.read();

        // Fast path: Bloom filter check (if enabled)
        if let Some(ref bloom) = inner.bloom_filter {
            if !bloom.might_contain(term) {
                return false; // Definitely not in DAWG
            }
            // Might be in DAWG, need full check
        }

        // Full check: traverse DAWG
        drop(inner); // Release lock before traversal
        let mut node = self.root();
        for ch in term.chars() {
            if let Some(next_node) = node.transition(ch) {
                node = next_node;
            } else {
                return false;
            }
        }
        node.is_final()
    }
}

// C1b algorithmic dedup: the original ~460-LOC impl<V> DynamicDawgCharInner<V>
// block lived here. All algorithmic methods (check_and_auto_minimize,
// insert_edge_sorted, minimize_incremental, plus signature/reachability
// helpers) now live on the canonical generic
// crate::dawg_core::DawgCore<U, V> shared with the byte DAWG variant.
// Original code preserved in git history.

impl<V: DictionaryValue> DynamicDawgChar<V> {
    /// Iterate over all `(term, value)` pairs as character vectors.
    ///
    /// Returns an iterator yielding `(Vec<char>, V)` tuples in depth-first order.
    /// This is more efficient than `iter()` as it avoids String allocation.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use libdictenstein::dynamic_dawg_char::DynamicDawgChar;
    ///
    /// let dict: DynamicDawgChar<u32> = DynamicDawgChar::new();
    /// dict.insert_with_value("café", 1);
    /// dict.insert_with_value("naïve", 2);
    ///
    /// for (chars, value) in dict.iter_chars() {
    ///     let term: String = chars.iter().collect();
    ///     println!("{} -> {}", term, value);
    /// }
    /// ```
    pub fn iter_chars(&self) -> DictionaryIterator<DynamicDawgCharZipper<V>> {
        let zipper = DynamicDawgCharZipper::new_from_dict(self);
        DictionaryIterator::new(zipper)
    }

    /// Iterate over all `(term, value)` pairs as UTF-8 strings.
    ///
    /// Returns an iterator yielding `(String, V)` tuples in depth-first order.
    /// For better performance with raw characters, use `iter_chars()` instead.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use libdictenstein::dynamic_dawg_char::DynamicDawgChar;
    ///
    /// let dict: DynamicDawgChar<u32> = DynamicDawgChar::new();
    /// dict.insert_with_value("café", 1);
    /// dict.insert_with_value("naïve", 2);
    ///
    /// for (term, value) in dict.iter() {
    ///     println!("{} -> {}", term, value);
    /// }
    /// ```
    pub fn iter(&self) -> impl Iterator<Item = (String, V)> + '_ {
        self.iter_chars()
            .map(|(chars, value)| (chars.into_iter().collect::<String>(), value))
    }
}

impl<V: DictionaryValue> IntoIterator for &DynamicDawgChar<V> {
    type Item = (Vec<char>, V);
    type IntoIter = DictionaryIterator<DynamicDawgCharZipper<V>>;

    /// Creates an iterator over all `(term, value)` pairs as character vectors.
    fn into_iter(self) -> Self::IntoIter {
        self.iter_chars()
    }
}

impl<V: DictionaryValue> Default for DynamicDawgChar<V> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(feature = "serialization")]
impl<V: DictionaryValue + serde::Serialize> serde::Serialize for DynamicDawgChar<V> {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: serde::Serializer,
    {
        // Extract the inner data by acquiring read lock
        let inner = self.inner.read();
        inner.serialize(serializer)
    }
}

/// Deserialize implementation when only `serialization` feature is enabled (not `persistent-artrie`).
/// In this case, we need explicit `Deserialize` bounds.
#[cfg(all(feature = "serialization", not(feature = "persistent-artrie")))]
impl<'de, V: DictionaryValue + serde::Deserialize<'de>> serde::Deserialize<'de>
    for DynamicDawgChar<V>
{
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        let inner = DynamicDawgCharInner::deserialize(deserializer)?;
        Ok(DynamicDawgChar {
            inner: Arc::new(RwLock::new(inner)),
        })
    }
}

/// Deserialize implementation when `persistent-artrie` feature is enabled.
/// `DictionaryValue` already includes `DeserializeOwned`, so no additional bounds needed.
#[cfg(all(feature = "serialization", feature = "persistent-artrie"))]
impl<'de, V: DictionaryValue> serde::Deserialize<'de> for DynamicDawgChar<V> {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: serde::Deserializer<'de>,
    {
        let inner = DynamicDawgCharInner::deserialize(deserializer)?;
        Ok(DynamicDawgChar {
            inner: Arc::new(RwLock::new(inner)),
        })
    }
}

impl<V: DictionaryValue> Dictionary for DynamicDawgChar<V> {
    type Node = DynamicDawgCharNode<V>;

    fn root(&self) -> Self::Node {
        // Phase 1.2: Load cached data with single lock acquisition
        let inner = self.inner.read();
        let node = &inner.nodes[0];
        DynamicDawgCharNode {
            dawg: Arc::clone(&self.inner),
            node_idx: 0,
            is_final: node.is_final,
            edges: node.edges.clone(),
        }
    }

    fn len(&self) -> Option<usize> {
        Some(self.term_count())
    }

    fn sync_strategy(&self) -> SyncStrategy {
        SyncStrategy::ExternalSync
    }
}

/// Node handle for dynamic DAWG traversal.
///
/// Phase 1.2: Caches is_final and edges to avoid lock acquisition on hot paths.
/// This eliminates locks from is_final() and edge_count(), and drastically
/// reduces locks in transition() (only for successful transitions).
#[derive(Clone)]
pub struct DynamicDawgCharNode<V: DictionaryValue = ()> {
    dawg: Arc<RwLock<DynamicDawgCharInner<V>>>,
    node_idx: usize,
    // Phase 1.2: Cached data
    is_final: bool,
    edges: SmallVec<[(char, usize); 4]>,
}

impl<V: DictionaryValue> DictionaryNode for DynamicDawgCharNode<V> {
    type Unit = char;

    // Phase 1.2: Use cached data - no lock needed
    fn is_final(&self) -> bool {
        self.is_final
    }

    fn transition(&self, label: char) -> Option<Self> {
        // Phase 1.2: Use cached edges for lookup - no lock needed
        // Adaptive: use linear search for small edge counts, binary for large
        // Empirical testing shows crossover at 16-20 edges
        let child_idx = if self.edges.len() < 16 {
            // Linear search - cache-friendly for small counts
            self.edges
                .iter()
                .find(|(c, _)| *c == label)
                .map(|(_, idx)| *idx)
        } else {
            // Binary search - efficient for large edge counts
            self.edges
                .binary_search_by_key(&label, |(c, _)| *c)
                .ok()
                .map(|i| self.edges[i].1)
        }?;

        // Phase 1.2: Only acquire lock to load child node's cached data
        let inner = self.dawg.read();
        let child_node = &inner.nodes[child_idx];
        Some(DynamicDawgCharNode {
            dawg: Arc::clone(&self.dawg),
            node_idx: child_idx,
            is_final: child_node.is_final,
            edges: child_node.edges.clone(),
        })
    }

    fn edges(&self) -> Box<dyn Iterator<Item = (char, Self)> + '_> {
        // Phase 1.2: Batch load child nodes with single lock acquisition
        let inner = self.dawg.read();
        let child_data: Vec<_> = self
            .edges
            .iter()
            .map(|(ch, idx)| {
                let child_node = &inner.nodes[*idx];
                (*ch, *idx, child_node.is_final, child_node.edges.clone())
            })
            .collect();
        drop(inner);

        let dawg = Arc::clone(&self.dawg);
        Box::new(
            child_data
                .into_iter()
                .map(move |(ch, idx, is_final, edges)| {
                    (
                        ch,
                        DynamicDawgCharNode {
                            dawg: Arc::clone(&dawg),
                            node_idx: idx,
                            is_final,
                            edges,
                        },
                    )
                }),
        )
    }

    // Phase 1.2: Use cached data - no lock needed
    fn edge_count(&self) -> Option<usize> {
        Some(self.edges.len())
    }
}

// ============================================================================
// MappedDictionary Trait Implementation
// ============================================================================

use crate::{MappedDictionary, MappedDictionaryNode};

impl<V: DictionaryValue> MappedDictionaryNode for DynamicDawgCharNode<V> {
    type Value = V;

    fn value(&self) -> Option<Self::Value> {
        // Need to lock to get the value
        let inner = self.dawg.read();
        inner
            .nodes
            .get(self.node_idx)
            .and_then(|node| node.value.clone())
    }
}

impl<V: DictionaryValue> MappedDictionary for DynamicDawgChar<V> {
    type Value = V;

    fn get_value(&self, term: &str) -> Option<Self::Value> {
        // Delegate to the inherent method
        Self::get_value(self, term)
    }

    fn contains_with_value<F>(&self, term: &str, predicate: F) -> bool
    where
        F: Fn(&Self::Value) -> bool,
    {
        match self.get_value(term) {
            Some(ref value) => predicate(value),
            None => false,
        }
    }
}

impl<V: DictionaryValue> crate::MutableDictionary for DynamicDawgChar<V> {
    fn insert(&self, term: &str) -> bool {
        // Delegate to the inherent method
        Self::insert(self, term)
    }

    fn remove(&self, term: &str) -> bool {
        // Delegate to the inherent method
        Self::remove(self, term)
    }

    fn extend<I, S>(&self, terms: I) -> usize
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        // Delegate to the inherent method (which also compacts)
        Self::extend(self, terms)
    }

    fn remove_many<I, S>(&self, terms: I) -> usize
    where
        I: IntoIterator<Item = S>,
        S: AsRef<str>,
    {
        // Delegate to the inherent method (which also compacts)
        Self::remove_many(self, terms)
    }
}

impl<V: DictionaryValue> crate::CompactableDictionary for DynamicDawgChar<V> {
    fn needs_compaction(&self) -> bool {
        // Delegate to the inherent method
        Self::needs_compaction(self)
    }

    fn compact(&self) -> usize {
        // Delegate to the inherent method
        Self::compact(self)
    }

    fn minimize(&self) -> usize {
        // Delegate to the inherent method
        Self::minimize(self)
    }
}

impl<V: DictionaryValue> crate::MutableMappedDictionary for DynamicDawgChar<V> {
    fn insert_with_value(&self, term: &str, value: Self::Value) -> bool {
        // Delegate to the inherent method
        Self::insert_with_value(self, term, value)
    }

    fn union_with<F>(&self, other: &Self, merge_fn: F) -> usize
    where
        F: Fn(&Self::Value, &Self::Value) -> Self::Value,
        Self::Value: Clone,
    {
        // Snapshot `other`'s final terms under its read lock, then DROP that lock BEFORE
        // merging into `self` — never holding `other.inner.read()` while
        // `self.insert_with_value` takes `self.inner.write()`. Holding both is an AB/BA
        // cross-instance deadlock: `A.union_with(&B)` ‖ `B.union_with(&A)` each hold the
        // OTHER's read lock and then wait on their OWN write lock (red-team R4-1). Mirrors
        // the persistent vocab/char `union_with` snapshot-then-release pattern.
        let entries: Vec<(String, Option<Self::Value>)> = {
            let other_inner = other.inner.read();
            let mut out = Vec::new();
            // DFS traversal to extract all final terms (with their optional value).
            let mut stack: Vec<(usize, Vec<char>)> = vec![(0, Vec::new())];
            while let Some((node_idx, path)) = stack.pop() {
                let node = &other_inner.nodes[node_idx];
                if node.is_final {
                    let term: String = path.iter().collect();
                    out.push((term, node.value.clone()));
                }
                // Push children onto stack (in reverse for consistent ordering)
                for &(label, target_idx) in node.edges.iter().rev() {
                    let mut child_path = path.clone();
                    child_path.push(label);
                    stack.push((target_idx, child_path));
                }
            }
            out
        }; // `other_inner` read lock released here — no two locks held at once

        let mut processed = 0;
        for (term, other_value) in entries {
            // `processed` counts every final term (preserving the original semantics);
            // only valued terms are merged into `self`.
            processed += 1;
            if let Some(other_value) = other_value {
                if let Some(self_value) = self.get_value(&term) {
                    let merged = merge_fn(&self_value, &other_value);
                    self.insert_with_value(&term, merged);
                } else {
                    self.insert_with_value(&term, other_value);
                }
            }
        }
        processed
    }

    fn update_or_insert<F>(&self, term: &str, default_value: Self::Value, update_fn: F) -> bool
    where
        F: FnOnce(&mut Self::Value),
    {
        // Delegate to the inherent method
        Self::update_or_insert(self, term, default_value, update_fn)
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use log::debug;

    #[test]
    fn test_dynamic_dawg_insert() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();
        assert!(dawg.insert("test"));
        assert!(!dawg.insert("test")); // Duplicate
        assert!(dawg.insert("testing"));
        assert_eq!(dawg.term_count(), 2);
    }

    #[test]
    fn test_dynamic_dawg_remove() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();
        dawg.insert("test");
        dawg.insert("testing");
        dawg.insert("tested");

        assert!(dawg.remove("testing"));
        assert_eq!(dawg.term_count(), 2);
        assert!(!dawg.remove("testing")); // Already removed
    }

    #[test]
    fn test_dynamic_dawg_compact() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();
        dawg.insert("test");
        dawg.insert("testing");
        dawg.insert("tested");

        let before = dawg.node_count();
        dawg.remove("testing");

        let removed = dawg.compact();
        let after = dawg.node_count();

        assert!(removed > 0 || before == after);
        assert_eq!(dawg.term_count(), 2);
    }

    // NOTE: test_dynamic_dawg_with_transducer is in liblevenshtein since it requires the transducer module

    #[test]
    fn test_compaction_flag() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();
        dawg.insert("test");

        assert!(!dawg.needs_compaction());

        dawg.remove("test");
        assert!(dawg.needs_compaction());

        dawg.compact();
        assert!(!dawg.needs_compaction());
    }

    #[test]
    fn test_batch_extend() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();
        dawg.insert("test");

        let new_terms = vec!["testing", "tested", "tester"];
        let added = dawg.extend(new_terms);

        assert_eq!(added, 3);
        assert_eq!(dawg.term_count(), 4);
        assert!(dawg.contains("test"));
        assert!(dawg.contains("testing"));
    }

    #[test]
    fn test_batch_remove_many() {
        let dawg: DynamicDawgChar<()> =
            DynamicDawgChar::from_terms(vec!["test", "testing", "tested", "tester"]);

        let to_remove = vec!["testing", "tester"];
        let removed = dawg.remove_many(to_remove);

        assert_eq!(removed, 2);
        assert_eq!(dawg.term_count(), 2);
        assert!(dawg.contains("test"));
        assert!(!dawg.contains("testing"));
    }

    #[test]
    fn test_minimize_basic() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();

        // Insert terms in unsorted order
        dawg.insert("zebra");
        dawg.insert("apple");
        dawg.insert("banana");
        dawg.insert("apricot");

        let nodes_before = dawg.node_count();
        let merged = dawg.minimize();
        let nodes_after = dawg.node_count();

        // Should have merged some nodes or stayed the same
        assert_eq!(nodes_after, nodes_before - merged);

        // All terms should still be present
        assert_eq!(dawg.term_count(), 4);
        assert!(dawg.contains("zebra"));
        assert!(dawg.contains("apple"));
        assert!(dawg.contains("banana"));
        assert!(dawg.contains("apricot"));
    }

    #[test]
    fn test_minimize_vs_compact() {
        // Test that minimize() achieves same minimality as compact()
        let _terms = ["band", "banana", "bandana", "can", "cane", "candy"];

        // Create two identical DAWGs with unsorted insertion
        let dawg1: DynamicDawgChar<()> = DynamicDawgChar::new();
        let dawg2: DynamicDawgChar<()> = DynamicDawgChar::new();

        for term in ["zebra", "apple", "banana", "apricot", "band", "bandana"] {
            dawg1.insert(term);
            dawg2.insert(term);
        }

        // Minimize one, compact the other
        let merged1 = dawg1.minimize();
        let merged2 = dawg2.compact();

        println!(
            "After minimize: {} nodes (merged {})",
            dawg1.node_count(),
            merged1
        );
        println!(
            "After compact: {} nodes (removed {})",
            dawg2.node_count(),
            merged2
        );

        // Both should contain same terms
        for term in ["zebra", "apple", "banana", "apricot", "band", "bandana"] {
            assert!(
                dawg1.contains(term),
                "minimize() DAWG missing term: {}",
                term
            );
            assert!(
                dawg2.contains(term),
                "compact() DAWG missing term: {}",
                term
            );
        }

        // Check term counts match
        assert_eq!(dawg1.term_count(), dawg2.term_count());

        // NOTE: minimize() and compact() may produce different node counts.
        // This is expected behavior:
        // - compact() rebuilds with sorted insertion, maximizing prefix sharing
        // - minimize() merges suffixes without restructuring the trie
        // Both produce correct results; compact() uses more CPU but yields better compression.
        // Choose based on use case: minimize() for real-time, compact() for batch processing.
        if dawg1.node_count() != dawg2.node_count() {
            debug!(
                "minimize() produced {} nodes, compact() produced {} nodes (expected difference)",
                dawg1.node_count(),
                dawg2.node_count()
            );
        }
    }

    #[test]
    fn test_minimize_after_deletions() {
        let dawg: DynamicDawgChar<()> =
            DynamicDawgChar::from_terms(vec!["test", "testing", "tested", "tester", "testimony"]);

        // Remove some terms, creating potential orphaned nodes
        dawg.remove("testing");
        dawg.remove("tester");

        assert!(dawg.needs_compaction());

        let nodes_before = dawg.node_count();
        let merged = dawg.minimize();
        let nodes_after = dawg.node_count();

        // Should have cleaned up orphaned nodes
        assert!(merged > 0);
        assert_eq!(nodes_after, nodes_before - merged);

        // Remaining terms should still be present
        assert!(dawg.contains("test"));
        assert!(dawg.contains("tested"));
        assert!(dawg.contains("testimony"));
        assert!(!dawg.contains("testing"));
        assert!(!dawg.contains("tester"));
    }

    #[test]
    fn test_minimize_empty() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();
        let merged = dawg.minimize();

        // Empty DAWG should have nothing to minimize
        assert_eq!(merged, 0);
        assert_eq!(dawg.node_count(), 1); // Just root
        assert_eq!(dawg.term_count(), 0);
    }

    #[test]
    fn test_minimize_single_term() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();
        dawg.insert("hello");

        let nodes_before = dawg.node_count();
        let merged = dawg.minimize();
        let nodes_after = dawg.node_count();

        // Single term should already be minimal
        assert_eq!(merged, 0);
        assert_eq!(nodes_before, nodes_after);
        assert!(dawg.contains("hello"));
    }

    #[test]
    fn test_minimize_with_shared_suffixes() {
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();

        // These words share suffixes: "ing" in testing/running
        dawg.insert("testing");
        dawg.insert("running");
        dawg.insert("test");
        dawg.insert("run");

        let _merged = dawg.minimize();

        // All terms should be preserved (minimize should handle shared suffixes)
        assert!(dawg.contains("testing"));
        assert!(dawg.contains("running"));
        assert!(dawg.contains("test"));
        assert!(dawg.contains("run"));
    }

    #[test]
    fn test_minimize_idempotent() {
        let dawg: DynamicDawgChar<()> =
            DynamicDawgChar::from_terms(vec!["apple", "application", "apply", "apricot"]);

        // First minimization
        let _merged1 = dawg.minimize();
        let nodes1 = dawg.node_count();

        // Second minimization should do nothing (already minimal)
        let merged2 = dawg.minimize();
        let nodes2 = dawg.node_count();

        assert_eq!(merged2, 0);
        assert_eq!(nodes1, nodes2);
    }

    #[test]
    fn test_minimize_no_false_positives() {
        // Test to prevent false positive lookups after minimize()
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();

        // Insert specific terms in random order
        let inserted_terms = vec!["zebra", "apple", "banana", "apricot", "band", "bandana"];
        let not_inserted_terms = vec!["app", "ban", "zeb", "banan", "apric", "bandanas"];

        for term in &inserted_terms {
            dawg.insert(term);
        }

        // Minimize the DAWG
        dawg.minimize();

        // Check that inserted terms are still present
        for term in &inserted_terms {
            assert!(
                dawg.contains(term),
                "Should contain inserted term: {}",
                term
            );
        }

        // CRITICAL: Check that non-inserted terms are NOT present (no false positives)
        for term in &not_inserted_terms {
            assert!(
                !dawg.contains(term),
                "Should NOT contain term that wasn't inserted: {}",
                term
            );
        }
    }

    #[test]
    fn test_valued_dawg_basic() {
        // Test DynamicDawgChar with values
        let dawg: DynamicDawgChar<u32> = DynamicDawgChar::new();

        // Insert with values
        assert!(dawg.insert_with_value("hello", 42));
        assert!(dawg.insert_with_value("world", 100));
        assert!(dawg.insert_with_value("test", 1));

        // Verify values
        assert_eq!(dawg.get_value("hello"), Some(42));
        assert_eq!(dawg.get_value("world"), Some(100));
        assert_eq!(dawg.get_value("test"), Some(1));
        assert_eq!(dawg.get_value("unknown"), None);

        // Update value
        assert!(!dawg.insert_with_value("hello", 999));
        assert_eq!(dawg.get_value("hello"), Some(999));

        // Verify term count
        assert_eq!(dawg.term_count(), 3);
    }

    #[test]
    fn test_valued_dawg_with_remove() {
        let dawg: DynamicDawgChar<String> = DynamicDawgChar::new();

        dawg.insert_with_value("key1", "value1".to_string());
        dawg.insert_with_value("key2", "value2".to_string());

        assert_eq!(dawg.get_value("key1"), Some("value1".to_string()));

        // Remove should clear value
        assert!(dawg.remove("key1"));
        assert_eq!(dawg.get_value("key1"), None);
        assert_eq!(dawg.get_value("key2"), Some("value2".to_string()));
    }

    #[test]
    fn test_mapped_dictionary_trait() {
        use crate::MappedDictionary;

        let dawg: DynamicDawgChar<Vec<u32>> = DynamicDawgChar::new();
        dawg.insert_with_value("scoped", vec![1, 2, 3]);
        dawg.insert_with_value("global", vec![0]);

        // Test MappedDictionary::get_value
        assert_eq!(dawg.get_value("scoped"), Some(vec![1, 2, 3]));

        // Test contains_with_value
        assert!(dawg.contains_with_value("scoped", |v| v.contains(&2)));
        assert!(!dawg.contains_with_value("scoped", |v| v.contains(&999)));
        assert!(!dawg.contains_with_value("unknown", |v| v.contains(&1)));
    }

    #[test]
    fn test_compact_no_false_positives() {
        // Same test for compact() to establish baseline
        let dawg: DynamicDawgChar<()> = DynamicDawgChar::new();

        let inserted_terms = vec!["zebra", "apple", "banana", "apricot", "band", "bandana"];
        let not_inserted_terms = vec!["app", "ban", "zeb", "banan", "apric", "bandanas"];

        for term in &inserted_terms {
            dawg.insert(term);
        }

        dawg.compact();

        for term in &inserted_terms {
            assert!(
                dawg.contains(term),
                "Should contain inserted term: {}",
                term
            );
        }

        for term in &not_inserted_terms {
            assert!(
                !dawg.contains(term),
                "Should NOT contain term that wasn't inserted: {}",
                term
            );
        }
    }
}