zipora 3.1.5

//! Suffix Array Dictionary for PA-Zip Compression
//!
//! This module implements a high-performance suffix array-based dictionary for
//! the PA-Zip compression algorithm. It combines the SAIS suffix array construction
//! with a DFA cache using Double Array Trie for optimal pattern matching performance.
//!
//! # Features
//!
//! - **Linear-time construction**: Uses SA-IS algorithm for O(n) suffix array building
//! - **Fast pattern matching**: O(log n + m) search with O(1) DFA transitions  
//! - **Memory efficient**: Supports both embedded and external dictionary modes
//! - **Cache-optimized**: DFA cache provides constant-time prefix matching
//! - **SIMD accelerated**: Uses hardware acceleration for bulk operations
//! - **Configurable**: BFS depth, frequency thresholds, cache sizes
//!
//! # Algorithm Overview
//!
//! The dictionary combines two key data structures:
//! 1. **Suffix Array**: Built using SA-IS for finding all pattern occurrences
//! 2. **DFA Cache**: Double Array Trie for O(1) prefix transitions
//!
//! Pattern matching workflow:
//! ```text
//! 1. Use DFA cache for initial prefix matching (fast path)
//! 2. Fall back to suffix array binary search for full patterns
//! 3. Return longest match with position information
//! ```

use crate::algorithms::suffix_array::{SuffixArray, SuffixArrayConfig};
use crate::compression::dict_zip::dfa_cache::{DfaCache, DfaCacheConfig};
use crate::compression::dict_zip::matcher::{Match, PatternMatcher};
use crate::error::{Result, ZiporaError};
use crate::memory::{SecureMemoryPool, SecurePoolConfig};

#[cfg(feature = "serde")]
use serde::{Deserialize, Serialize};


use std::sync::Arc;

/// Configuration for suffix array dictionary construction
#[derive(Debug, Clone)]
pub struct SuffixArrayDictionaryConfig {
    /// Maximum dictionary size in bytes
    pub max_dict_size: usize,
    /// Minimum pattern frequency for inclusion in dictionary
    pub min_frequency: u32,
    /// Maximum BFS depth for DFA cache construction
    pub max_bfs_depth: u32,
    /// Maximum number of states in DFA cache
    pub max_cache_states: usize,
    /// Use external dictionary mode (store dictionary separately)
    pub external_mode: bool,
    /// Use memory pool for allocations
    pub use_memory_pool: bool,
    /// Enable SIMD optimizations
    pub enable_simd: bool,
    /// Sample ratio for large inputs (0.0 to 1.0)
    pub sample_ratio: f64,
    /// Minimum pattern length for dictionary inclusion
    pub min_pattern_length: usize,
    /// Maximum pattern length for dictionary inclusion  
    pub max_pattern_length: usize,
    /// DFA cache configuration
    pub dfa_cache_config: DfaCacheConfig,
    /// Suffix array configuration
    pub suffix_array_config: SuffixArrayConfig,
}

impl Default for SuffixArrayDictionaryConfig {
    fn default() -> Self {
        Self {
            max_dict_size: 64 * 1024 * 1024, // 64MB default
            min_frequency: 4,                 // Minimum 4 occurrences
            max_bfs_depth: 6,                 // BFS depth of 6 levels
            max_cache_states: 65536,          // 64K states in DFA cache
            external_mode: false,             // Embedded by default
            use_memory_pool: true,
            enable_simd: cfg!(feature = "simd"),
            sample_ratio: 1.0,       // Use full input by default
            min_pattern_length: 4,   // Minimum 4 bytes
            max_pattern_length: 256, // Maximum 256 bytes
            dfa_cache_config: DfaCacheConfig::default(),
            suffix_array_config: SuffixArrayConfig::default(),
        }
    }
}

/// Match status for two-level pattern matching engine
#[derive(Debug, Clone, PartialEq)]
pub struct MatchStatus {
    /// Start of suffix array range
    pub lo: usize,
    /// End of suffix array range
    pub hi: usize,
    /// Match depth (length)
    pub depth: usize,
}

impl MatchStatus {
    /// Create a new match status
    pub fn new(lo: usize, hi: usize, depth: usize) -> Self {
        Self { lo, hi, depth }
    }
    
    /// Check if the range is empty (no matches)
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.lo >= self.hi
    }
    
    /// Get the number of matches in this range
    pub fn match_count(&self) -> usize {
        if self.is_empty() {
            0
        } else {
            self.hi - self.lo
        }
    }
}

/// Match statistics for performance monitoring
#[derive(Debug, Clone, Default)]
pub struct MatchStats {
    /// Total number of searches performed
    pub total_searches: u64,
    /// Number of cache hits (fast path)
    pub cache_hits: u64,
    /// Number of suffix array lookups (slow path)
    pub suffix_array_lookups: u64,
    /// Total bytes matched
    pub bytes_matched: u64,
    /// Average match length
    pub avg_match_length: f64,
    /// Total search time in microseconds
    pub total_search_time_us: u64,
}

impl MatchStats {
    /// Calculate cache hit ratio
    pub fn cache_hit_ratio(&self) -> f64 {
        if self.total_searches == 0 {
            0.0
        } else {
            self.cache_hits as f64 / self.total_searches as f64
        }
    }

    /// Calculate average search time per operation
    pub fn avg_search_time_us(&self) -> f64 {
        if self.total_searches == 0 {
            0.0
        } else {
            self.total_search_time_us as f64 / self.total_searches as f64
        }
    }

    /// Update statistics with a new search result
    pub fn update_search(&mut self, used_cache: bool, match_length: usize, search_time_us: u64) {
        self.total_searches += 1;
        if used_cache {
            self.cache_hits += 1;
        } else {
            self.suffix_array_lookups += 1;
        }
        self.bytes_matched += match_length as u64;
        self.total_search_time_us += search_time_us;
        
        // Update rolling average
        let total_bytes = self.bytes_matched as f64;
        self.avg_match_length = total_bytes / self.total_searches as f64;
    }
}

/// High-performance suffix array dictionary for PA-Zip compression
#[derive(Debug, Clone)]
pub struct SuffixArrayDictionary {
    /// The underlying suffix array for pattern searching
    suffix_array: Arc<SuffixArray>,
    /// DFA cache for fast prefix matching
    dfa_cache: DfaCache,
    /// Original dictionary text
    dictionary_text: Arc<Vec<u8>>,
    /// Pattern matcher for finding longest matches
    matcher: PatternMatcher,
    /// Memory pool for allocations
    memory_pool: Option<Arc<SecureMemoryPool>>,
    /// Configuration used to build this dictionary
    config: SuffixArrayDictionaryConfig,
    /// Match statistics
    stats: MatchStats,
}

impl SuffixArrayDictionary {
    /// Create a new suffix array dictionary from training data
    ///
    /// # Arguments
    /// * `training_data` - Input data to build the dictionary from
    /// * `config` - Configuration parameters for construction
    ///
    /// # Returns
    /// A new dictionary instance ready for pattern matching
    ///
    /// # Example
    /// ```
    /// use zipora::compression::dict_zip::{SuffixArrayDictionary, SuffixArrayDictionaryConfig};
    ///
    /// let training_data = b"The quick brown fox jumps over the lazy dog. The quick brown fox...";
    /// let config = SuffixArrayDictionaryConfig::default();
    /// let dictionary = SuffixArrayDictionary::new(training_data, config)?;
    /// # Ok::<(), zipora::error::ZiporaError>(())
    /// ```
    pub fn new(training_data: &[u8], config: SuffixArrayDictionaryConfig) -> Result<Self> {
        // Initialize memory pool if requested
        let memory_pool = if config.use_memory_pool {
            let pool_config = SecurePoolConfig::medium_secure()
                .with_local_cache_size(32);
            Some(SecureMemoryPool::new(pool_config)?)
        } else {
            None
        };

        // Sample the training data if needed
        let sampled_data = if config.sample_ratio < 1.0 && training_data.len() > 10000 {
            Self::sample_training_data(training_data, config.sample_ratio)
        } else {
            training_data.to_vec()
        };

        // Build suffix array from the training data
        let suffix_array = Arc::new(SuffixArray::with_config(&sampled_data, &config.suffix_array_config)?);

        // Store dictionary text for pattern matching
        let dictionary_text = Arc::new(sampled_data);

        // Build DFA cache for fast prefix matching
        let dfa_cache = DfaCache::build_from_suffix_array(
            &suffix_array,
            &dictionary_text,
            &config.dfa_cache_config,
            config.min_frequency,
            config.max_bfs_depth,
        )?;

        // Initialize pattern matcher
        let matcher = PatternMatcher::new(
            Arc::clone(&suffix_array),
            Arc::clone(&dictionary_text),
            config.min_pattern_length,
            config.max_pattern_length,
        );

        Ok(Self {
            suffix_array,
            dfa_cache,
            dictionary_text,
            matcher,
            memory_pool,
            config,
            stats: MatchStats::default(),
        })
    }

    /// Find the longest match for a given input at the specified position
    ///
    /// This is the core pattern matching function used by the PA-Zip compression algorithm.
    /// It first tries the DFA cache for fast prefix matching, then falls back to
    /// suffix array binary search for complete pattern matching.
    ///
    /// # Arguments
    /// * `input` - Input data to search in
    /// * `position` - Starting position in the input
    /// * `max_length` - Maximum match length to consider
    ///
    /// # Returns
    /// Optional match with position and length information
    ///
    /// # Example
    /// ```
    /// use zipora::compression::dict_zip::{SuffixArrayDictionary, SuffixArrayDictionaryConfig};
    /// 
    /// let training_data = b"The quick brown fox jumps over the lazy dog";
    /// let config = SuffixArrayDictionaryConfig::default();
    /// let mut dictionary = SuffixArrayDictionary::new(training_data, config)?;
    /// 
    /// let input = b"The quick brown fox";
    /// let match_result = dictionary.find_longest_match(input, 0, 100)?;
    /// if let Some(m) = match_result {
    ///     println!("Found match: length={}, dict_pos={}", m.length, m.dict_position);
    /// }
    /// # Ok::<(), zipora::error::ZiporaError>(())
    /// ```
    pub fn find_longest_match(
        &mut self,
        input: &[u8],
        position: usize,
        max_length: usize,
    ) -> Result<Option<Match>> {
        let start_time = std::time::Instant::now();

        if position >= input.len() {
            return Ok(None);
        }

        let search_slice = &input[position..];
        let _max_search_len = max_length.min(search_slice.len()).min(self.config.max_pattern_length);

        // Use advanced two-level pattern matching algorithm
        let match_status = self.da_match_max_length(search_slice);
        
        
        let result = if match_status.depth >= self.config.min_pattern_length && !match_status.is_empty() {
            // Found a match using two-level algorithm
            let dict_position = if match_status.lo < self.suffix_array.as_slice().len() {
                self.suffix_array.as_slice()[match_status.lo]
            } else {
                0
            };
            
            let match_result = Match::new(
                match_status.depth,
                dict_position,
                position,
                match_status.depth <= 10, // Heuristic: short matches likely from cache
            );
            
            self.stats.update_search(
                match_result.from_cache, 
                match_result.length,
                start_time.elapsed().as_micros() as u64
            );
            
            Some(match_result)
        } else {
            // No match found or match too short
            self.stats.update_search(false, 0, start_time.elapsed().as_micros() as u64);
            None
        };

        Ok(result)
    }

    /// Find all matches for a given pattern
    ///
    /// Returns all occurrences of the pattern in the dictionary, sorted by position.
    /// Useful for analyzing pattern frequency and distribution.
    ///
    /// # Arguments
    /// * `pattern` - Pattern to search for
    /// * `max_matches` - Maximum number of matches to return
    ///
    /// # Returns
    /// Vector of matches with dictionary positions
    pub fn find_all_matches(&self, pattern: &[u8], max_matches: usize) -> Result<Vec<Match>> {
        if pattern.len() < self.config.min_pattern_length || 
           pattern.len() > self.config.max_pattern_length {
            return Ok(Vec::new());
        }

        self.matcher.find_all_matches(pattern, max_matches)
    }

    /// Get dictionary size in bytes
    pub fn dictionary_size(&self) -> usize {
        self.dictionary_text.len()
    }

    /// Get reference to the dictionary text for direct access
    pub fn dictionary_text(&self) -> &[u8] {
        &self.dictionary_text
    }

    /// Get number of states in DFA cache
    pub fn cache_states(&self) -> usize {
        self.dfa_cache.state_count()
    }

    /// Get memory usage statistics
    #[inline]
    pub fn memory_usage(&self) -> usize {
        let sa_memory = self.suffix_array.as_slice().len() * std::mem::size_of::<usize>();
        let dict_memory = self.dictionary_text.len();
        let cache_memory = self.dfa_cache.memory_usage();
        
        sa_memory + dict_memory + cache_memory
    }

    /// Get match statistics
    pub fn match_stats(&self) -> &MatchStats {
        &self.stats
    }

    /// Reset match statistics
    pub fn reset_stats(&mut self) {
        self.stats = MatchStats::default();
    }

    /// Get dictionary configuration
    pub fn config(&self) -> &SuffixArrayDictionaryConfig {
        &self.config
    }

    /// Check if dictionary supports external mode
    pub fn is_external_mode(&self) -> bool {
        self.config.external_mode
    }

    /// Serialize dictionary for external storage
    ///
    /// In external mode, the dictionary can be serialized and stored separately
    /// from the compressed data, allowing for reuse across multiple files.
    #[cfg(feature = "serde")]
    pub fn serialize(&self) -> Result<Vec<u8>> {
        use bincode;
        
        let serializable = SerializableDictionary {
            dictionary_text: (*self.dictionary_text).clone(),
            dfa_cache_data: self.dfa_cache.serialize()?,
            min_pattern_length: self.config.min_pattern_length,
            max_pattern_length: self.config.max_pattern_length,
        };

        bincode::serialize(&serializable)
            .map_err(|e| ZiporaError::invalid_data(&format!("Serialization failed: {}", e)))
    }

    /// Deserialize dictionary from external storage
    #[cfg(feature = "serde")]
    pub fn deserialize(data: &[u8]) -> Result<Self> {
        use bincode;

        let serializable: SerializableDictionary = bincode::deserialize(data)
            .map_err(|e| ZiporaError::invalid_data(&format!("Deserialization failed: {}", e)))?;

        // Reconstruct dictionary text
        let dictionary_text = Arc::new(serializable.dictionary_text);

        // Reconstruct suffix array (rebuild from dictionary text)
        let suffix_array = Arc::new(SuffixArray::new(&dictionary_text)?);

        // Reconstruct DFA cache
        let dfa_cache = DfaCache::deserialize(&serializable.dfa_cache_data)?;

        // Initialize pattern matcher
        let matcher = PatternMatcher::new(
            Arc::clone(&suffix_array),
            Arc::clone(&dictionary_text),
            serializable.min_pattern_length,
            serializable.max_pattern_length,
        );

        // Create a minimal config for the deserialized dictionary
        let config = SuffixArrayDictionaryConfig {
            min_pattern_length: serializable.min_pattern_length,
            max_pattern_length: serializable.max_pattern_length,
            ..Default::default()
        };

        Ok(Self {
            suffix_array,
            dfa_cache,
            dictionary_text,
            matcher,
            memory_pool: None, // Not serialized
            config,
            stats: MatchStats::default(),
        })
    }

    /// Sample training data to reduce dictionary size
    fn sample_training_data(data: &[u8], ratio: f64) -> Vec<u8> {
        if ratio >= 1.0 {
            return data.to_vec();
        }

        let sample_size = (data.len() as f64 * ratio) as usize;
        let step = data.len() / sample_size;
        
        let mut sampled = Vec::with_capacity(sample_size);
        for i in (0..data.len()).step_by(step.max(1)) {
            sampled.push(data[i]);
            if sampled.len() >= sample_size {
                break;
            }
        }

        sampled
    }

    /// Optimize DFA cache after construction
    ///
    /// Removes infrequently used states and compacts the cache structure
    /// for better memory efficiency and cache performance.
    pub fn optimize_cache(&mut self) -> Result<()> {
        self.dfa_cache.optimize(self.config.min_frequency)?;
        Ok(())
    }

    /// Get cache hit ratio for performance monitoring
    pub fn cache_hit_ratio(&self) -> f64 {
        self.stats.cache_hit_ratio()
    }

    /// Save dictionary to file
    #[cfg(feature = "serde")]
    pub fn save_to_file<P: AsRef<std::path::Path>>(&self, path: P) -> Result<()> {
        use std::fs::File;
        use std::io::Write;
        
        let serialized = self.serialize()?;
        let mut file = File::create(path)
            .map_err(|e| ZiporaError::io_error(&format!("Failed to create dictionary file: {}", e)))?;
        
        file.write_all(&serialized)
            .map_err(|e| ZiporaError::io_error(&format!("Failed to write dictionary file: {}", e)))?;
        
        Ok(())
    }

    /// Load dictionary from file
    #[cfg(feature = "serde")]
    pub fn load_from_file<P: AsRef<std::path::Path>>(path: P) -> Result<Self> {
        use std::fs;
        
        let data = fs::read(path)
            .map_err(|e| ZiporaError::io_error(&format!("Failed to read dictionary file: {}", e)))?;
        
        Self::deserialize(&data)
    }

    /// Get size in bytes (dictionary size + memory overhead)
    pub fn size_in_bytes(&self) -> usize {
        self.memory_usage()
    }
    
    /// Get access to the raw dictionary data for reference-compliant compression
    #[inline]
    pub fn data(&self) -> &[u8] {
        &self.dictionary_text
    }

    /// Advanced two-level pattern matching using DFA cache + suffix array
    ///
    /// This implements the sophisticated two-level algorithm from PA-Zip research:
    /// 1. **Fast Path**: DFA cache navigation with O(1) state transitions
    /// 2. **Slow Path**: Suffix array fallback with binary search when DFA misses
    /// 3. **String Compression**: Handle zstr (compressed string) patterns efficiently
    /// 4. **Range Management**: Track suffix array ranges [lo, hi) for pattern locations
    ///
    /// # Arguments
    /// * `input` - Input bytes to match against dictionary
    ///
    /// # Returns
    /// MatchStatus with suffix array range and match depth
    pub fn da_match_max_length(&self, input: &[u8]) -> MatchStatus {
        
        if input.is_empty() {
            return MatchStatus::new(0, 0, 0);
        }

        let mut state = 0u32;  // Start at root state
        let mut lo = 0usize;
        let mut hi = self.suffix_array.as_slice().len();
        let mut pos = 0usize;
        
        while pos < input.len() {
            
            // 1. Handle compressed string (zstr) if present
            if let Some(zlen) = self.dfa_cache.get_zstr_length(state) {
                let zend = (input.len()).min(pos + zlen);
                if lo < self.suffix_array.as_slice().len() {
                    let dict_start = self.suffix_array.as_slice()[lo];
                    if dict_start < self.dictionary_text.len() {
                        let zptr = &self.dictionary_text[dict_start + pos..];
                        while pos < zend && pos < zptr.len() {
                            if zptr[pos - (dict_start + pos - dict_start)] != input[pos] {
                                return MatchStatus::new(lo, hi, pos);
                            }
                            pos += 1;
                        }
                    }
                }
            }
            
            if pos >= input.len() {
                break;
            }
            
            // 2. Navigate to child state using double array trie
            let child = self.dfa_cache.transition_state(state, input[pos]);
            
            if let Some(next_state) = child {
                if let Some(dfa_state) = self.dfa_cache.get_state(next_state) {
                    // Valid transition - update state and range from DFA cache
                    state = next_state;
                    lo = dfa_state.suffix_low as usize;
                    hi = dfa_state.suffix_hig as usize;
                    pos += 1;
                } else {
                    // DFA cache miss - fall back to suffix array search
                    return self.sa_match_continuation(lo, hi, pos, input);
                }
            } else {
                // No transition available - fall back to suffix array search
                return self.sa_match_continuation(lo, hi, pos, input);
            }
        }
        
        MatchStatus::new(lo, hi, pos)
    }

    /// Suffix array continuation when DFA cache misses
    ///
    /// This implements the fallback search when the DFA cache cannot provide
    /// a transition. It uses binary search on the suffix array to continue
    /// pattern matching from the current position.
    ///
    /// # Arguments
    /// * `lo` - Start of current suffix array range
    /// * `hi` - End of current suffix array range
    /// * `pos` - Current position in input
    /// * `input` - Input bytes being matched
    ///
    /// # Returns
    /// MatchStatus with refined range and extended match depth
    pub fn sa_match_continuation(&self, lo: usize, hi: usize, pos: usize, input: &[u8]) -> MatchStatus {
        let mut current_lo = lo;
        let mut current_hi = hi;
        let mut current_pos = pos;
        
        while current_pos < input.len() && current_lo < current_hi {
            let ch = input[current_pos];
            let (new_lo, new_hi) = self.sa_equal_range(current_lo, current_hi, current_pos, ch);
            
            if new_lo >= new_hi {
                break; // No more matches
            }
            
            current_lo = new_lo;
            current_hi = new_hi;
            current_pos += 1;
        }
        
        MatchStatus::new(current_lo, current_hi, current_pos)
    }

    /// Find equal range in suffix array for character at position
    ///
    /// This implements binary search to find the range of suffixes that have
    /// the specified character at the given position within the current range.
    ///
    /// # Arguments
    /// * `lo` - Start of current range
    /// * `hi` - End of current range
    /// * `pos` - Position to check character at
    /// * `ch` - Character to match
    ///
    /// # Returns
    /// Tuple of (new_lo, new_hi) representing the refined range
    pub fn sa_equal_range(&self, lo: usize, hi: usize, pos: usize, ch: u8) -> (usize, usize) {
        if lo >= hi || lo >= self.suffix_array.as_slice().len() {
            return (lo, lo); // Empty range
        }
        
        // Use the optimized binary search implementation based on optimization patterns
        self.sa_equal_range_binary_optimized(lo, hi, pos, ch)
    }
    
    /// Linear search implementation for debugging
    fn sa_equal_range_linear(&self, lo: usize, hi: usize, pos: usize, ch: u8) -> (usize, usize) {
        let mut first_match = None;
        let mut last_match = None;
        
        let actual_hi = hi.min(self.suffix_array.as_slice().len());
        
        for i in lo..actual_hi {
            if let Some(&suffix_idx) = self.suffix_array.as_slice().get(i) {
                if suffix_idx + pos < self.dictionary_text.len() {
                    let char_at_pos = self.dictionary_text[suffix_idx + pos];
                    if char_at_pos == ch {
                        if first_match.is_none() {
                            first_match = Some(i);
                        }
                        last_match = Some(i);
                    }
                }
            }
        }
        
        match (first_match, last_match) {
            (Some(first), Some(last)) => (first, last + 1), // Return range [first, last+1)
            _ => (lo, lo), // No matches found
        }
    }
    
    /// Optimized binary search implementation based on compression research  
    /// 
    /// FIXED: The original implementation had a bug where Phase 2 could miss matches
    /// at the beginning of the range when the range was small. The fix ensures we
    /// always check if a match exists in the range, even if binary search misses it.
    fn sa_equal_range_binary_optimized(&self, lo: usize, hi: usize, pos: usize, ch: u8) -> (usize, usize) {
        // Bounds checking
        let mut search_lo = lo;
        let search_hi = hi.min(self.suffix_array.as_slice().len());
        
        if search_lo >= search_hi {
            return (search_lo, search_lo);
        }
        
        // Phase 1: Handle boundary cases - advance past suffixes extending beyond text
        // This mirrors the reference logic: if (unlikely(sa[lo] + depth >= saLen)) { lo++; }
        while search_lo < search_hi {
            if let Some(&suffix_idx) = self.suffix_array.as_slice().get(search_lo) {
                if suffix_idx + pos >= self.dictionary_text.len() {
                    search_lo += 1;
                } else {
                    break;
                }
            } else {
                break;
            }
        }
        
        if search_lo >= search_hi {
            return (search_lo, search_lo);
        }
        
        // FIX: For small ranges, use linear search to avoid missing edge cases
        // This handles the case where binary search might skip over matches at boundaries
        if search_hi - search_lo <= 3 {
            return self.sa_equal_range_linear(search_lo, search_hi, pos, ch);
        }
        
        // Phase 2: Find ANY occurrence using binary search
        let mut lo_search = search_lo;
        let mut hi_search = search_hi;
        let mideq = loop {
            if lo_search >= hi_search {
                return (lo_search, lo_search); // No match found
            }
            
            let mid = lo_search + (hi_search - lo_search) / 2;
            
            let suffix_idx = match self.suffix_array.as_slice().get(mid) {
                Some(&idx) => idx,
                None => return (lo_search, lo_search),
            };
            
            // Handle out of bounds cases
            if suffix_idx + pos >= self.dictionary_text.len() {
                // FIX: When out of bounds at mid, we need to check both directions
                // to avoid missing valid entries
                if mid > lo_search {
                    // Try lower half first
                    hi_search = mid;
                } else {
                    lo_search = mid + 1;
                }
                continue;
            }
            
            let hit_char = self.dictionary_text[suffix_idx + pos];
            
            if hit_char < ch {
                lo_search = mid + 1;
            } else if hit_char > ch {
                hi_search = mid;
            } else {
                break mid; // Found a match at position mid - this is our pivot
            }
        };
        
        // Phase 3: Find lower bound in [search_lo, mideq+1)
        let mut lower_lo = search_lo;
        let mut lower_hi = mideq + 1;
        while lower_lo < lower_hi {
            let mid = lower_lo + (lower_hi - lower_lo) / 2;
            
            let suffix_idx = match self.suffix_array.as_slice().get(mid) {
                Some(&idx) => idx,
                None => break,
            };
            
            if suffix_idx + pos >= self.dictionary_text.len() {
                lower_lo = mid + 1;
                continue;
            }
            
            let hit_char = self.dictionary_text[suffix_idx + pos];
            if hit_char < ch {
                lower_lo = mid + 1; // Move past values less than target
            } else {
                lower_hi = mid;     // hit_char >= ch, could be start of range
            }
        }
        
        // Phase 4: Find upper bound in [mideq, search_hi)
        let mut upper_lo = mideq;
        let mut upper_hi = search_hi;
        while upper_lo < upper_hi {
            let mid = upper_lo + (upper_hi - upper_lo) / 2;
            
            let suffix_idx = match self.suffix_array.as_slice().get(mid) {
                Some(&idx) => idx,
                None => break,
            };
            
            if suffix_idx + pos >= self.dictionary_text.len() {
                upper_lo = mid + 1;
                continue;
            }
            
            let hit_char = self.dictionary_text[suffix_idx + pos];
            if hit_char <= ch {
                upper_lo = mid + 1; // Move past values <= target (include equal values)
            } else {
                upper_hi = mid;     // hit_char > ch, could be end of range
            }
        }
        
        (lower_lo, upper_lo)
    }

    /// Validate dictionary integrity
    ///
    /// Performs consistency checks on the internal data structures
    /// to ensure the dictionary is in a valid state.
    pub fn validate(&self) -> Result<()> {
        // Check suffix array integrity
        if self.suffix_array.text_len() != self.dictionary_text.len() {
            return Err(ZiporaError::invalid_data(
                "Suffix array length mismatch with dictionary text"
            ));
        }

        // Validate DFA cache
        self.dfa_cache.validate()?;

        // Check configuration consistency
        if self.config.min_pattern_length > self.config.max_pattern_length {
            return Err(ZiporaError::invalid_data(
                "Invalid pattern length configuration"
            ));
        }

        Ok(())
    }

    /// Get DFA cache statistics
    pub fn cache_stats(&self) -> crate::compression::dict_zip::dfa_cache::CacheStats {
        self.dfa_cache.stats().clone()
    }
}

/// Serializable representation of the dictionary for external storage
#[cfg(feature = "serde")]
#[derive(Serialize, Deserialize)]
struct SerializableDictionary {
    dictionary_text: Vec<u8>,
    dfa_cache_data: Vec<u8>,
    min_pattern_length: usize,
    max_pattern_length: usize,
}

/// Thread-safe dictionary wrapper for concurrent access
pub struct ConcurrentSuffixArrayDictionary {
    inner: std::sync::RwLock<SuffixArrayDictionary>,
}

impl ConcurrentSuffixArrayDictionary {
    /// Create a new concurrent dictionary
    pub fn new(training_data: &[u8], config: SuffixArrayDictionaryConfig) -> Result<Self> {
        let dictionary = SuffixArrayDictionary::new(training_data, config)?;
        Ok(Self {
            inner: std::sync::RwLock::new(dictionary),
        })
    }

    /// Find longest match with read lock
    pub fn find_longest_match(
        &self,
        input: &[u8],
        position: usize,
        max_length: usize,
    ) -> Result<Option<Match>> {
        let mut dictionary = self.inner.write()
            .map_err(|_| ZiporaError::invalid_data("Failed to acquire write lock"))?;
        dictionary.find_longest_match(input, position, max_length)
    }

    /// Get statistics with read lock
    pub fn match_stats(&self) -> Result<MatchStats> {
        let dictionary = self.inner.read()
            .map_err(|_| ZiporaError::invalid_data("Failed to acquire read lock"))?;
        Ok(dictionary.match_stats().clone())
    }
}

// SAFETY: SuffixArrayDictionary is Send because:
// 1. `dictionary: Vec<u8>` - Vec is Send.
// 2. `suffix_array: Vec<u32>` - Vec is Send.
// 3. `lcp_array: Vec<u32>` - Vec is Send.
// 4. `inverse_suffix_array: Vec<u32>` - Vec is Send.
// 5. `dfa_cache: HashMap<...>` - HashMap is Send.
// 6. `config: SuffixArrayDictionaryConfig` - Config is Clone, trivially Send.
// 7. `stats: MatchStats` - Stats contain primitives, trivially Send.
// 8. All other fields are primitives (usize, f64).
unsafe impl Send for SuffixArrayDictionary {}

// SAFETY: SuffixArrayDictionary is Sync because:
// 1. All fields are either immutable (after construction) or require &mut self.
// 2. `find_longest_match` requires &mut self for stats updates.
// 3. Read-only methods (dictionary_size, cache_states, etc.) are safe concurrently.
// 4. No interior mutability without &mut self.
//
// Note: For concurrent access, use ConcurrentSuffixArrayDictionary which wraps
// this struct in an RwLock.
unsafe impl Sync for SuffixArrayDictionary {}

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

    #[test]
    fn test_dictionary_creation() {
        let training_data = b"The quick brown fox jumps over the lazy dog. The quick brown fox jumps.";
        let config = SuffixArrayDictionaryConfig {
            min_frequency: 2, // Lower frequency requirement to ensure patterns are found
            ..Default::default()
        };

        let dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();

        assert_eq!(dictionary.dictionary_size(), training_data.len());
        assert!(dictionary.cache_states() > 0);
        assert!(dictionary.memory_usage() > 0);
    }

    #[test]
    fn test_pattern_matching() {
        let training_data = b"abcdefghijklmnopqrstuvwxyzabcdefgh";
        let config = SuffixArrayDictionaryConfig {
            min_pattern_length: 3,
            max_pattern_length: 10,
            ..Default::default()
        };
        
        let mut dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Test finding a pattern that exists
        let input = b"abcdefg";
        let result = dictionary.find_longest_match(input, 0, 10).unwrap();
        assert!(result.is_some());
        
        let match_info = result.unwrap();
        assert!(match_info.length >= 3);
    }

    #[test]
    fn test_match_statistics() {
        let training_data = b"aaabbbcccaaabbbccc";
        let config = SuffixArrayDictionaryConfig::default();
        
        let mut dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Perform some searches
        let input = b"aaabbb";
        dictionary.find_longest_match(input, 0, 10).unwrap();
        dictionary.find_longest_match(input, 1, 10).unwrap();
        
        let stats = dictionary.match_stats();
        assert_eq!(stats.total_searches, 2);
        assert!(stats.cache_hit_ratio() >= 0.0 && stats.cache_hit_ratio() <= 1.0);
    }

    #[test]
    fn test_dictionary_validation() {
        let training_data = b"test data for validation";
        let config = SuffixArrayDictionaryConfig::default();
        
        let dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Validation should pass for properly constructed dictionary
        assert!(dictionary.validate().is_ok());
    }

    #[test]
    fn test_concurrent_dictionary() {
        let training_data = b"concurrent test data";
        let config = SuffixArrayDictionaryConfig::default();
        
        let dict = ConcurrentSuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Test concurrent access
        let input = b"concurrent";
        let result = dict.find_longest_match(input, 0, 10).unwrap();
        assert!(result.is_some() || result.is_none()); // Either outcome is valid
        
        let stats = dict.match_stats().unwrap();
        assert_eq!(stats.total_searches, 1);
    }

    #[test]
    fn test_external_mode_config() {
        let training_data = b"external mode test";
        let config = SuffixArrayDictionaryConfig {
            external_mode: true,
            ..Default::default()
        };
        
        let dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        assert!(dictionary.is_external_mode());
    }

    #[test]
    #[cfg(feature = "serde")]
    fn test_serialization() {
        let training_data = b"serialization test data";
        let config = SuffixArrayDictionaryConfig::default();
        
        let dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Test serialization
        let serialized = dictionary.serialize().unwrap();
        assert!(!serialized.is_empty());
        
        // Test deserialization
        let deserialized = SuffixArrayDictionary::deserialize(&serialized).unwrap();
        assert_eq!(deserialized.dictionary_size(), dictionary.dictionary_size());
    }

    #[test]
    fn test_sampling() {
        let large_data = vec![b'a'; 10000];
        let config = SuffixArrayDictionaryConfig {
            sample_ratio: 0.1,
            ..Default::default()
        };
        
        let dictionary = SuffixArrayDictionary::new(&large_data, config).unwrap();
        
        // Dictionary should be smaller due to sampling, but might not be much smaller
        // for uniform data like all 'a's. Let's just check it was created successfully.
        assert!(dictionary.dictionary_size() > 0);
        assert!(dictionary.dictionary_size() <= large_data.len());
    }

    #[test]
    fn test_cache_optimization() {
        let training_data = b"optimization test data with repeated patterns";
        let config = SuffixArrayDictionaryConfig::default();
        
        let mut dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        let initial_states = dictionary.cache_states();
        dictionary.optimize_cache().unwrap();
        
        // Optimization might reduce the number of states
        assert!(dictionary.cache_states() <= initial_states);
    }


    #[test]
    fn test_debug_pattern_matching() {
        let training_data = b"test data test";
        let config = SuffixArrayDictionaryConfig {
            min_pattern_length: 3,
            max_pattern_length: 10,
            ..Default::default()
        };
        
        let mut dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Debug: Print dictionary state
        println!("Training data: {:?}", std::str::from_utf8(training_data));
        println!("Dictionary text length: {}", dictionary.dictionary_text.len());
        println!("Suffix array length: {}", dictionary.suffix_array.as_slice().len());
        
        // Print first few suffix array entries
        for i in 0..std::cmp::min(10, dictionary.suffix_array.as_slice().len()) {
            let suffix_idx = dictionary.suffix_array.as_slice()[i];
            if suffix_idx < dictionary.dictionary_text.len() {
                let suffix = &dictionary.dictionary_text[suffix_idx..];
                let suffix_str = String::from_utf8_lossy(&suffix[..std::cmp::min(10, suffix.len())]);
                println!("SA[{}] = {} -> '{}'", i, suffix_idx, suffix_str);
            }
        }
        
        let result = dictionary.find_longest_match(b"test", 0, 4).unwrap();
        println!("Debug result: {:?}", result);
        assert!(result.is_some(), "Should find 'test' in 'test data test'");
    }

    #[test]
    fn test_debug_binary_search() {
        let training_data = b"test data test";
        let config = SuffixArrayDictionaryConfig {
            min_pattern_length: 3,
            max_pattern_length: 10,
            ..Default::default()
        };
        
        let dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Test a simple binary search call directly
        let _result = dictionary.sa_equal_range(0, 5, 0, b't');
    }

    #[test]
    fn test_comprehensive_two_level_algorithm() {
        let training_data = b"comprehensive test for the two-level pattern matching algorithm with various patterns";
        let config = SuffixArrayDictionaryConfig {
            min_pattern_length: 3,
            max_pattern_length: 25,
            ..Default::default()
        };
        
        let mut dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Test various scenarios
        let test_cases: Vec<(&[u8], bool)> = vec![
            (b"comprehensive", true),   // Should find exact match
            (b"test", true),           // Should find exact match  
            (b"pattern", true),        // Should find exact match
            (b"xyz", false),           // Should not find match
            (b"comp", true),           // Should find prefix
        ];
        
        for (pattern, should_match) in &test_cases {
            println!("Testing pattern: {:?}", std::str::from_utf8(pattern).unwrap());
            
            // First check what da_match_max_length returns
            let match_status = dictionary.da_match_max_length(pattern);
            println!("  da_match_max_length: lo={}, hi={}, depth={}", 
                     match_status.lo, match_status.hi, match_status.depth);
            println!("  min_pattern_length={}", dictionary.config.min_pattern_length);
            
            let result = dictionary.find_longest_match(pattern, 0, pattern.len()).unwrap();
            if *should_match {
                if result.is_none() {
                    println!("  ERROR: find_longest_match returned None!");
                    println!("  Depth check: {} >= {} = {}", 
                             match_status.depth, 
                             dictionary.config.min_pattern_length,
                             match_status.depth >= dictionary.config.min_pattern_length);
                    println!("  Empty check: is_empty() = {}", match_status.is_empty());
                }
                assert!(result.is_some(), "Failed to find pattern: {:?}", std::str::from_utf8(pattern));
            } else {
                // For patterns not in dictionary, may or may not find short matches
                // Just ensure it doesn't crash
                let _ = result;
            }
        }
    }

    #[test]
    fn test_focused_binary_search_bug() {
        println!("\n=== Focused test for binary search bug ===");
        let training_data = b"comprehensive test for the two-level pattern matching algorithm with various patterns";
        let config = SuffixArrayDictionaryConfig {
            min_pattern_length: 3,
            max_pattern_length: 25,
            ..Default::default()
        };
        
        let dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // The specific case that fails: searching for 's' at position 2 in range [69, 72)
        println!("\nExamining the problematic case:");
        println!("After finding 'te' in range [69, 72), searching for 's' at position 2");
        
        // First, let's see what's actually in this range
        println!("\nSuffix array entries in range [69, 72):");
        for i in 69..72 {
            if let Some(&suffix_idx) = dictionary.suffix_array.as_slice().get(i) {
                if suffix_idx < training_data.len() {
                    let suffix_text = &training_data[suffix_idx..];
                    let preview = std::str::from_utf8(&suffix_text[..10.min(suffix_text.len())]).unwrap_or("<invalid>");
                    
                    // Check character at position 2
                    let char_at_2 = if suffix_idx + 2 < training_data.len() {
                        training_data[suffix_idx + 2] as char
                    } else {
                        '?'
                    };
                    
                    println!("  SA[{}] = {} -> '{}...', char[2]='{}'", 
                             i, suffix_idx, preview, char_at_2);
                }
            }
        }
        
        // Now test both linear and binary search
        let lo = 69;
        let hi = 72;
        let pos = 2;
        let ch = b's';
        
        println!("\nSearching for '{}' at position {} in range [{}, {})", ch as char, pos, lo, hi);
        
        let linear_result = dictionary.sa_equal_range_linear(lo, hi, pos, ch);
        println!("Linear search result: ({}, {})", linear_result.0, linear_result.1);
        
        let binary_result = dictionary.sa_equal_range_binary_optimized(lo, hi, pos, ch);
        println!("Binary search result: ({}, {})", binary_result.0, binary_result.1);
        
        if linear_result != binary_result {
            println!("\nERROR: Results differ!");
            println!("Linear found range [{}, {})", linear_result.0, linear_result.1);
            println!("Binary found range [{}, {})", binary_result.0, binary_result.1);
            
            // Debug the binary search algorithm step by step
            println!("\n=== Tracing binary search algorithm ===");
            
            // Phase 2: Find ANY match
            let mut lo_search = lo;
            let mut hi_search = hi;
            let mut mideq = None;
            
            println!("Phase 2: Finding ANY match");
            while lo_search < hi_search {
                let mid = lo_search + (hi_search - lo_search) / 2;
                println!("  Checking mid={} in range [{}, {})", mid, lo_search, hi_search);
                
                if let Some(&suffix_idx) = dictionary.suffix_array.as_slice().get(mid) {
                    if suffix_idx + pos >= training_data.len() {
                        println!("    Out of bounds, moving lo to {}", mid + 1);
                        lo_search = mid + 1;
                        continue;
                    }
                    
                    let hit_char = training_data[suffix_idx + pos];
                    println!("    SA[{}]={}, char[{}]='{}' vs target='{}'", 
                             mid, suffix_idx, pos, hit_char as char, ch as char);
                    
                    if hit_char < ch {
                        lo_search = mid + 1;
                    } else if hit_char > ch {
                        hi_search = mid;
                    } else {
                        println!("    FOUND match at mid={}!", mid);
                        mideq = Some(mid);
                        break;
                    }
                }
            }
            
            if let Some(mid) = mideq {
                // Phase 3: Find lower bound
                println!("\nPhase 3: Finding lower bound in [{}, {})", lo, mid + 1);
                let mut lower_lo = lo;
                let mut lower_hi = mid + 1;
                
                while lower_lo < lower_hi {
                    let m = lower_lo + (lower_hi - lower_lo) / 2;
                    if let Some(&suffix_idx) = dictionary.suffix_array.as_slice().get(m) {
                        if suffix_idx + pos < training_data.len() {
                            let hit_char = training_data[suffix_idx + pos];
                            println!("  mid={}: char='{}' vs '{}'", m, hit_char as char, ch as char);
                            if hit_char < ch {
                                lower_lo = m + 1;
                            } else {
                                lower_hi = m;
                            }
                        } else {
                            lower_lo = m + 1;
                        }
                    }
                }
                
                // Phase 4: Find upper bound
                println!("\nPhase 4: Finding upper bound in [{}, {})", mid, hi);
                let mut upper_lo = mid;
                let mut upper_hi = hi;
                
                while upper_lo < upper_hi {
                    let m = upper_lo + (upper_hi - upper_lo) / 2;
                    if let Some(&suffix_idx) = dictionary.suffix_array.as_slice().get(m) {
                        if suffix_idx + pos < training_data.len() {
                            let hit_char = training_data[suffix_idx + pos];
                            println!("  mid={}: char='{}' vs '{}'", m, hit_char as char, ch as char);
                            if hit_char <= ch {
                                upper_lo = m + 1;
                            } else {
                                upper_hi = m;
                            }
                        } else {
                            upper_lo = m + 1;
                        }
                    }
                }
                
                println!("\nCalculated range: [{}, {})", lower_lo, upper_lo);
            } else {
                println!("\nPhase 2 failed to find any match!");
            }
        }
        
        assert_eq!(linear_result, binary_result, 
                   "Binary search must return same result as linear search");
    }

    #[test]
    fn test_debug_binary_search_issue() {
        println!("\n=== Debugging Binary Search Issue ===");
        let training_data = b"comprehensive test for the two-level pattern matching algorithm with various patterns";
        let config = SuffixArrayDictionaryConfig {
            min_pattern_length: 3,
            max_pattern_length: 25,
            ..Default::default()
        };
        
        let dictionary = SuffixArrayDictionary::new(training_data, config).unwrap();
        
        // Add detailed debugging for "test" pattern
        println!("\n--- Detailed trace of da_match_max_length for 'test' ---");
        let pattern = b"test";
        
        let mut state = 0u32;
        let mut lo = 0usize;
        let mut hi = dictionary.suffix_array.as_slice().len();
        let mut pos = 0usize;
        
        println!("Initial: state={}, lo={}, hi={}, pos={}", state, lo, hi, pos);
        
        while pos < pattern.len() {
            let ch = pattern[pos];
            println!("\nStep {}: Looking for '{}' at position {}", pos, ch as char, pos);
            
            // Try DFA cache transition
            let child = dictionary.dfa_cache.transition_state(state, ch);
            
            if let Some(next_state) = child {
                if let Some(dfa_state) = dictionary.dfa_cache.get_state(next_state) {
                    println!("  DFA cache HIT: next_state={}, new range=({}, {})", 
                             next_state, dfa_state.suffix_low, dfa_state.suffix_hig);
                    state = next_state;
                    lo = dfa_state.suffix_low as usize;
                    hi = dfa_state.suffix_hig as usize;
                    pos += 1;
                } else {
                    println!("  DFA cache MISS (invalid state): falling back to suffix array");
                    break;
                }
            } else {
                println!("  DFA cache MISS (no transition): falling back to suffix array");
                break;
            }
        }
        
        if pos < pattern.len() {
            println!("\nContinuing with suffix array from pos={}, range=({}, {})", pos, lo, hi);
            
            while pos < pattern.len() && lo < hi {
                let ch = pattern[pos];
                println!("  SA Step {}: Looking for '{}' at position {}", pos, ch as char, pos);
                
                let (new_lo, new_hi) = dictionary.sa_equal_range(lo, hi, pos, ch);
                println!("    New range: ({}, {})", new_lo, new_hi);
                
                if new_lo >= new_hi {
                    println!("    No matches found - stopping");
                    break;
                }
                
                lo = new_lo;
                hi = new_hi;
                pos += 1;
            }
        }
        
        println!("\nFinal result: lo={}, hi={}, depth={}", lo, hi, pos);
        
        // Now run the actual function and compare
        let actual_result = dictionary.da_match_max_length(pattern);
        println!("\nActual da_match_max_length result: lo={}, hi={}, depth={}", 
                 actual_result.lo, actual_result.hi, actual_result.depth);
        
        if actual_result.depth != pos {
            println!("WARNING: Manual trace depth ({}) differs from actual result ({})", 
                     pos, actual_result.depth);
        }
        
        // Test 1: Compare linear and binary search for 't' at position 0
        println!("\n--- Test 1: Compare linear vs binary for 't' at position 0 ---");
        let lo = 0;
        let hi = dictionary.suffix_array.as_slice().len();
        let pos = 0;
        let ch = b't';
        
        let linear_result = dictionary.sa_equal_range_linear(lo, hi, pos, ch);
        println!("Linear search result: ({}, {})", linear_result.0, linear_result.1);
        
        let binary_result = dictionary.sa_equal_range_binary_optimized(lo, hi, pos, ch);
        println!("Binary search result: ({}, {})", binary_result.0, binary_result.1);
        
        if linear_result != binary_result {
            println!("ERROR: Results differ!");
            
            // Debug: print suffix array contents
            println!("Suffix array contents around the range:");
            for i in 0..20.min(dictionary.suffix_array.as_slice().len()) {
                if let Some(&suffix_idx) = dictionary.suffix_array.as_slice().get(i) {
                    if suffix_idx < dictionary.dictionary_text.len() {
                        let char_at_pos = if suffix_idx + pos < dictionary.dictionary_text.len() {
                            dictionary.dictionary_text[suffix_idx + pos] as char
                        } else {
                            '?'
                        };
                        let text_preview = if suffix_idx < dictionary.dictionary_text.len() {
                            let end = (suffix_idx + 15).min(dictionary.dictionary_text.len());
                            std::str::from_utf8(&dictionary.dictionary_text[suffix_idx..end]).unwrap_or("<invalid>")
                        } else {
                            "<out of bounds>"
                        };
                        println!("  SA[{}] = {}, char[{}]='{}', text='{}'", 
                                 i, suffix_idx, pos, char_at_pos, text_preview);
                    }
                }
            }
        }
        
        // Test 2: Test the full da_match_max_length for "test"
        println!("\n--- Test 2: Full pattern matching for 'test' ---");
        let pattern = b"test";
        let match_status = dictionary.da_match_max_length(pattern);
        println!("Match status: lo={}, hi={}, depth={}", 
                 match_status.lo, match_status.hi, match_status.depth);
        
        if match_status.is_empty() {
            println!("ERROR: No matches found for 'test'!");
            
            // Debug step-by-step
            println!("\nStep-by-step search for 'test':");
            let mut current_lo = 0;
            let mut current_hi = dictionary.suffix_array.as_slice().len();
            
            for (i, &ch) in pattern.iter().enumerate() {
                println!("  Step {}: searching for '{}' at position {}", i, ch as char, i);
                println!("    Current range: ({}, {})", current_lo, current_hi);
                
                let (new_lo, new_hi) = dictionary.sa_equal_range(current_lo, current_hi, i, ch);
                println!("    New range: ({}, {})", new_lo, new_hi);
                
                if new_lo >= new_hi {
                    println!("    FAILED at character '{}'!", ch as char);
                    
                    // Try linear search for comparison
                    let linear = dictionary.sa_equal_range_linear(current_lo, current_hi, i, ch);
                    println!("    Linear search would give: ({}, {})", linear.0, linear.1);
                    break;
                }
                
                current_lo = new_lo;
                current_hi = new_hi;
            }
        } else {
            println!("SUCCESS: Found {} matches", match_status.match_count());
        }
        
        // Test 3: Check if running linear first affects binary
        println!("\n--- Test 3: Effect of running linear search first ---");
        
        // Fresh dictionary - binary only
        let dict1 = SuffixArrayDictionary::new(training_data, SuffixArrayDictionaryConfig {
            min_pattern_length: 3,
            max_pattern_length: 25,
            ..Default::default()
        }).unwrap();
        
        let binary_only = dict1.sa_equal_range_binary_optimized(0, dict1.suffix_array.as_slice().len(), 0, b't');
        println!("Binary only result: ({}, {})", binary_only.0, binary_only.1);
        
        // Fresh dictionary - linear then binary
        let dict2 = SuffixArrayDictionary::new(training_data, SuffixArrayDictionaryConfig {
            min_pattern_length: 3,
            max_pattern_length: 25,
            ..Default::default()
        }).unwrap();
        
        let _ = dict2.sa_equal_range_linear(0, dict2.suffix_array.as_slice().len(), 0, b't');
        let binary_after_linear = dict2.sa_equal_range_binary_optimized(0, dict2.suffix_array.as_slice().len(), 0, b't');
        println!("Binary after linear result: ({}, {})", binary_after_linear.0, binary_after_linear.1);
        
        if binary_only != binary_after_linear {
            println!("WARNING: Results differ based on whether linear was run first!");
        }
    }
}