zipora 2.1.4

//! PA-Zip Dictionary Compression Module
//!
//! This module provides a complete implementation of the PA-Zip compression algorithm
//! using suffix arrays and DFA caches for high-performance pattern matching.
//! 
//! # Overview
//!
//! PA-Zip (Pattern Array Zip) is an advanced dictionary compression algorithm that combines:
//! - **Suffix Array construction** using the SA-IS algorithm for O(n) time complexity
//! - **DFA Cache** using Double Array Trie for O(1) state transitions
//! - **BFS-based dictionary building** for optimal pattern coverage
//! - **Adaptive matching** with cache-aware pattern search
//!
//! # Components
//!
//! - [`SuffixArrayDictionary`]: Main dictionary class with pattern matching API
//! - [`DfaCache`]: High-performance DFA cache for prefix matching
//! - [`PatternMatcher`]: Core matching engine combining cache and suffix array
//! - [`DictionaryBuilder`]: Builder for constructing dictionaries from training data
//!
//! # Usage Example
//!
//! ```rust
//! use zipora::compression::dict_zip::{DictionaryBuilder, DictionaryBuilderConfig};
//!
//! // Build dictionary from training data
//! let training_data = b"The quick brown fox jumps over the lazy dog. The quick brown fox jumps again.";
//! let config = DictionaryBuilderConfig::max_compression();
//! let builder = DictionaryBuilder::with_config(config);
//! let mut dictionary = builder.build(training_data)?;
//!
//! // Use dictionary for pattern matching
//! let input = b"pattern to compress";
//! let match_result = dictionary.find_longest_match(input, 0, 100)?;
//! 
//! if let Some(m) = match_result {
//!     println!("Found match: length={}, position={}", m.length, m.dict_position);
//! }
//! # Ok::<(), Box<dyn std::error::Error>>(())
//! ```
//!
//! # Performance Characteristics
//!
//! - **Dictionary construction**: O(n) time using SA-IS algorithm
//! - **Pattern matching**: O(log n + m) average case with DFA acceleration
//! - **Memory usage**: ~8 bytes per suffix array entry + DFA cache overhead
//! - **Cache efficiency**: 70-90% hit rate for typical text compression workloads
//!
//! # Algorithm Details
//!
//! The PA-Zip algorithm works in two phases:
//!
//! ## 1. Dictionary Construction
//! - Build suffix array from training data using SA-IS
//! - Extract frequent patterns using configurable frequency thresholds  
//! - Construct DFA cache using BFS traversal up to specified depth
//! - Optimize cache by removing infrequent states
//!
//! ## 2. Pattern Matching
//! - Try DFA cache first for O(1) prefix matching (fast path)
//! - Fall back to suffix array binary search for complete patterns (slow path)
//! - Extend cache matches using suffix array for maximum length
//! - Return best match with position and quality information
//!
//! # Configuration Options
//!
//! The module provides extensive configuration options:
//! - **Memory limits**: Control maximum dictionary and cache sizes
//! - **Frequency thresholds**: Adjust pattern inclusion criteria  
//! - **BFS depth**: Control DFA cache construction depth
//! - **Pattern lengths**: Set minimum and maximum pattern lengths
//! - **Performance tuning**: Enable SIMD, parallel processing, memory pools
//!
//! # Serialization Support
//!
//! When the `serde` feature is enabled, dictionaries can be serialized for:
//! - **External storage**: Store dictionaries separately from compressed data
//! - **Reuse**: Share dictionaries across multiple compression sessions
//! - **Caching**: Persist built dictionaries to avoid reconstruction
//!
//! # Memory Management
//!
//! The module integrates with zipora's memory management system:
//! - Uses `SecureMemoryPool` for allocation tracking and cleanup
//! - Supports memory-constrained building with size limits
//! - Provides memory usage statistics and optimization

pub mod blob_store;
pub mod builder;
pub mod compression_types;
pub mod compressor;
pub mod dfa_cache;
pub mod dictionary;
pub mod local_matcher;
pub mod matcher;
pub mod reference_encoding;

// Re-export main types for convenient access
pub use blob_store::{
    DictZipBlobStore, DictZipBlobStoreBuilder, DictZipBlobStoreStats, DictZipConfig,
    EntropyAlgorithm
};
pub use builder::{BuildPhase, BuildProgress, BuildStrategy, DictionaryBuilder, DictionaryBuilderConfig, SampleSortPolicy};
pub use compression_types::{
    CompressionType, Match, BitReader, BitWriter, encode_match, decode_match, 
    encode_matches, decode_matches, calculate_encoding_cost, calculate_encoding_overhead,
    calculate_compression_efficiency, choose_best_compression_type, calculate_theoretical_compression_ratio
};
pub use compressor::{
    CompressionStats, CompressionStrategy, CostAnalysis, PaZipCompressor, PaZipCompressorConfig
};
pub use dfa_cache::{CacheMatch, CacheStats, DfaCache, DfaCacheConfig};
pub use dictionary::{
    ConcurrentSuffixArrayDictionary, MatchStats, SuffixArrayDictionary, SuffixArrayDictionaryConfig,
};
pub use local_matcher::{LocalMatch, LocalMatcher, LocalMatcherConfig, LocalMatcherStats};
pub use matcher::{Match as PatternMatch, MatcherConfig, MatcherStats, PatternMatcher, PatternMatcherBuilder};
pub use reference_encoding::{
    DzType, DzEncodingMeta, ReferenceEncoder, get_back_ref_encoding_meta, 
    write_uint_bytes, write_var_size_t, compress_record_reference
};

use crate::error::{Result, ZiporaError};

/// PA-Zip compression algorithm version
pub const PA_ZIP_VERSION: &str = "1.0.0";

/// Default minimum pattern length for PA-Zip
pub const DEFAULT_MIN_PATTERN_LENGTH: usize = 4;

/// Default maximum pattern length for PA-Zip  
pub const DEFAULT_MAX_PATTERN_LENGTH: usize = 256;

/// Default minimum frequency threshold
pub const DEFAULT_MIN_FREQUENCY: u32 = 4;

/// Default BFS depth for DFA cache construction
pub const DEFAULT_BFS_DEPTH: u32 = 6;

/// Validate PA-Zip algorithm parameters
///
/// Ensures that the provided parameters are within valid ranges
/// and compatible with each other.
///
/// # Arguments
/// * `min_pattern_length` - Minimum pattern length
/// * `max_pattern_length` - Maximum pattern length  
/// * `min_frequency` - Minimum frequency threshold
/// * `max_bfs_depth` - Maximum BFS depth
///
/// # Returns
/// Ok(()) if parameters are valid, error otherwise
pub fn validate_parameters(
    min_pattern_length: usize,
    max_pattern_length: usize,
    min_frequency: u32,
    max_bfs_depth: u32,
) -> Result<()> {
    if min_pattern_length == 0 {
        return Err(ZiporaError::invalid_data("Minimum pattern length must be > 0"));
    }

    if max_pattern_length < min_pattern_length {
        return Err(ZiporaError::invalid_data(
            "Maximum pattern length must be >= minimum pattern length",
        ));
    }

    if max_pattern_length > 1024 {
        return Err(ZiporaError::invalid_data(
            "Maximum pattern length must be <= 1024",
        ));
    }

    if min_frequency == 0 {
        return Err(ZiporaError::invalid_data("Minimum frequency must be > 0"));
    }

    if max_bfs_depth > 20 {
        return Err(ZiporaError::invalid_data("BFS depth must be <= 20"));
    }

    Ok(())
}

/// Calculate optimal dictionary size based on input data size
///
/// Provides a heuristic for choosing dictionary size as a function
/// of the input data size, balancing compression ratio and memory usage.
///
/// # Arguments
/// * `input_size` - Size of input data in bytes
/// * `max_memory` - Maximum memory budget in bytes
///
/// # Returns
/// Recommended dictionary size in bytes
pub fn calculate_optimal_dict_size(input_size: usize, max_memory: usize) -> usize {
    // Handle edge cases
    if input_size == 0 {
        return 0;
    }
    
    // Heuristic: dictionary should be 5-15% of input size
    let theoretical_min = (input_size / 20).max(256); // Start with smaller minimum
    let theoretical_max = (input_size / 6).max(theoretical_min);
    
    // Never exceed input size - dictionary can't be useful if larger than input
    let input_constrained_max = theoretical_max.min(input_size);
    let input_constrained_min = theoretical_min.min(input_size);
    
    // Respect memory limits if specified
    let final_size = if max_memory > 0 {
        let budget_limit = max_memory / 2; // Use half of memory budget for dictionary
        input_constrained_max.min(budget_limit)
    } else {
        input_constrained_max
    };
    
    // Ensure we don't go below the constrained minimum, but NEVER violate memory constraints
    if max_memory > 0 {
        let memory_limit = max_memory / 2;
        final_size.max(input_constrained_min).min(memory_limit)
    } else {
        final_size.max(input_constrained_min)
    }
}

/// Estimate compression ratio for given parameters
///
/// Provides a rough estimate of expected compression ratio based on
/// algorithm parameters and data characteristics.
///
/// # Arguments
/// * `data_entropy` - Entropy of input data (bits per byte)
/// * `repetitiveness` - Repetitiveness measure (0.0 to 1.0)
/// * `dict_size_ratio` - Dictionary size as fraction of input size
///
/// # Returns
/// Estimated compression ratio (0.0 to 1.0, lower is better)
pub fn estimate_compression_ratio(
    data_entropy: f64,
    repetitiveness: f64,
    dict_size_ratio: f64,
) -> f64 {
    // Base compression depends on entropy and repetitiveness
    let base_ratio = (data_entropy / 8.0) * (1.0 - repetitiveness * 0.7);
    
    // Dictionary overhead
    let dict_overhead = dict_size_ratio * 0.1;
    
    // PA-Zip effectiveness factor
    let pa_zip_factor = 0.7 + repetitiveness * 0.2;
    
    (base_ratio * pa_zip_factor + dict_overhead).clamp(0.1, 1.0)
}

/// Quick build configuration for common use cases
pub struct QuickConfig;

impl QuickConfig {
    /// Configuration optimized for text compression
    pub fn text_compression() -> SuffixArrayDictionaryConfig {
        SuffixArrayDictionaryConfig {
            max_dict_size: 32 * 1024 * 1024, // 32MB
            min_frequency: 3,
            max_bfs_depth: 6,
            min_pattern_length: 4,
            max_pattern_length: 128,
            sample_ratio: 0.8,
            ..Default::default()
        }
    }

    /// Configuration optimized for binary data compression
    pub fn binary_compression() -> SuffixArrayDictionaryConfig {
        SuffixArrayDictionaryConfig {
            max_dict_size: 16 * 1024 * 1024, // 16MB
            min_frequency: 8,
            max_bfs_depth: 4,
            min_pattern_length: 8,
            max_pattern_length: 64,
            sample_ratio: 0.5,
            ..Default::default()
        }
    }

    /// Configuration optimized for log file compression
    pub fn log_compression() -> SuffixArrayDictionaryConfig {
        SuffixArrayDictionaryConfig {
            max_dict_size: 64 * 1024 * 1024, // 64MB
            min_frequency: 2,
            max_bfs_depth: 8,
            min_pattern_length: 10,
            max_pattern_length: 256,
            sample_ratio: 0.3, // Logs are very repetitive
            ..Default::default()
        }
    }

    /// Configuration optimized for real-time compression
    pub fn realtime_compression() -> SuffixArrayDictionaryConfig {
        SuffixArrayDictionaryConfig {
            max_dict_size: 8 * 1024 * 1024, // 8MB
            min_frequency: 10,
            max_bfs_depth: 3,
            min_pattern_length: 6,
            max_pattern_length: 32,
            sample_ratio: 0.2,
            ..Default::default()
        }
    }
}

/// Performance benchmarking utilities
#[cfg(test)]
pub mod bench_utils {
    use super::*;
    use std::time::{Duration, Instant};

    /// Benchmark dictionary construction time
    pub fn benchmark_build_time(data: &[u8], config: DictionaryBuilderConfig) -> Duration {
        let start = Instant::now();
        let builder = DictionaryBuilder::with_config(config);
        let _dictionary = builder.build(data).unwrap();
        start.elapsed()
    }

    /// Benchmark pattern matching throughput
    pub fn benchmark_matching_throughput(
        dictionary: &mut SuffixArrayDictionary,
        test_data: &[u8],
        num_matches: usize,
    ) -> f64 {
        let start = Instant::now();
        let mut total_bytes = 0;

        for i in 0..num_matches {
            let pos = (i * 97) % test_data.len(); // Pseudo-random positions
            if let Ok(Some(m)) = dictionary.find_longest_match(test_data, pos, 100) {
                total_bytes += m.length;
            }
        }

        let elapsed = start.elapsed().as_secs_f64();
        total_bytes as f64 / elapsed // Bytes per second
    }

    /// Generate test data with controlled repetitiveness
    pub fn generate_test_data(size: usize, repetitiveness: f64) -> Vec<u8> {
        let mut data = Vec::with_capacity(size);
        let pattern = b"test pattern with some repetitive content";
        let random_bytes: Vec<u8> = (0..=255).cycle().take(size).collect();

        for i in 0..size {
            if (i as f64 / size as f64) < repetitiveness {
                data.push(pattern[i % pattern.len()]);
            } else {
                data.push(random_bytes[i]);
            }
        }

        data
    }
}

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

    #[test]
    fn test_parameter_validation() {
        // Valid parameters
        assert!(validate_parameters(4, 256, 4, 6).is_ok());

        // Invalid: zero minimum length
        assert!(validate_parameters(0, 256, 4, 6).is_err());

        // Invalid: max < min
        assert!(validate_parameters(10, 5, 4, 6).is_err());

        // Invalid: zero frequency
        assert!(validate_parameters(4, 256, 0, 6).is_err());

        // Invalid: excessive BFS depth
        assert!(validate_parameters(4, 256, 4, 25).is_err());
    }

    #[test]
    fn test_optimal_dict_size_calculation() {
        // Small input
        let dict_size = calculate_optimal_dict_size(10000, 100000);
        assert!(dict_size >= 1024);
        assert!(dict_size <= 50000);

        // Large input with memory constraint
        let dict_size = calculate_optimal_dict_size(1000000, 100000);
        assert!(dict_size <= 50000); // Respects memory limit
    }

    #[test]
    fn test_compression_ratio_estimation() {
        // Low entropy, high repetitiveness - should compress well
        let ratio = estimate_compression_ratio(3.0, 0.8, 0.1);
        assert!(ratio < 0.5);

        // High entropy, low repetitiveness - should compress poorly
        let ratio = estimate_compression_ratio(7.5, 0.1, 0.2);
        assert!(ratio > 0.6);
    }

    #[test]
    fn test_quick_configs() {
        let text_config = QuickConfig::text_compression();
        assert_eq!(text_config.min_pattern_length, 4);
        assert_eq!(text_config.max_pattern_length, 128);

        let binary_config = QuickConfig::binary_compression();
        assert_eq!(binary_config.min_pattern_length, 8);
        assert!(binary_config.min_frequency > text_config.min_frequency);

        let log_config = QuickConfig::log_compression();
        assert!(log_config.max_dict_size > text_config.max_dict_size);
        assert!(log_config.sample_ratio < text_config.sample_ratio);

        let realtime_config = QuickConfig::realtime_compression();
        assert!(realtime_config.max_dict_size < text_config.max_dict_size);
        assert!(realtime_config.max_bfs_depth < text_config.max_bfs_depth);
    }

    #[test]
    fn test_version_constant() {
        assert!(!PA_ZIP_VERSION.is_empty());
        assert!(PA_ZIP_VERSION.contains('.'));
    }

    #[test]
    fn test_default_constants() {
        assert_eq!(DEFAULT_MIN_PATTERN_LENGTH, 4);
        assert_eq!(DEFAULT_MAX_PATTERN_LENGTH, 256);
        assert_eq!(DEFAULT_MIN_FREQUENCY, 4);
        assert_eq!(DEFAULT_BFS_DEPTH, 6);
    }

    #[test]
    #[cfg(test)]
    fn test_bench_utils() {
        let test_data = bench_utils::generate_test_data(1000, 0.5);
        assert_eq!(test_data.len(), 1000);

        // Test data should have some repetitive patterns
        let unique_bytes: std::collections::HashSet<u8> = test_data.iter().copied().collect();
        // The generate_test_data function cycles through 0..=255, so it will have many unique bytes
        // Let's just verify we got some data
        assert!(!unique_bytes.is_empty());
        assert!(unique_bytes.len() <= 256); // Can't have more than 256 unique bytes
    }

    #[test]
    fn test_integration_workflow() {
        // Test complete workflow from building to matching
        let training_data = b"the quick brown fox jumps over the lazy dog. the quick brown fox.";
        
        // Build dictionary
        let config = DictionaryBuilderConfig {
            target_dict_size: 2048,
            max_dict_size: 4096,
            validate_result: true,
            ..Default::default()
        };
        
        let builder = DictionaryBuilder::with_config(config);
        let mut dictionary = builder.build(training_data).unwrap();
        
        // Test pattern matching
        let input = b"the quick brown";
        let result = dictionary.find_longest_match(input, 0, 50).unwrap();
        
        assert!(result.is_some());
        let match_info = result.unwrap();
        assert!(match_info.length > 0);
        assert!(match_info.quality > 0.0);
        
        // Test statistics
        let stats = dictionary.match_stats();
        assert_eq!(stats.total_searches, 1);
        
        // Validate dictionary
        assert!(dictionary.validate().is_ok());
    }
}