sketch_oxide 0.1.6

//! Comprehensive demonstration of all 9 sketch_oxide algorithms
//!
//! This example showcases the usage of all state-of-the-art algorithms:
//! 1. UltraLogLog - Cardinality estimation
//! 2. Binary Fuse Filter - Membership testing
//! 3. DDSketch - Quantile estimation
//! 4. REQ Sketch - Tail quantiles
//! 5. Count-Min Sketch - Frequency estimation
//! 6. MinHash - Similarity estimation
//! 7. Theta Sketch - Set operations
//! 8. CPC Sketch - Space-efficient cardinality
//! 9. Frequent Items - Top-K heavy hitters

use sketch_oxide::{
    cardinality::{CpcSketch, ThetaSketch, UltraLogLog},
    error::SketchError,
    frequency::{CountMinSketch, FrequentItems},
    membership::BinaryFuseFilter,
    quantiles::{DDSketch, ReqMode, ReqSketch},
    similarity::MinHash,
    Sketch, // Import the Sketch trait for update() and estimate() methods
};

fn main() -> Result<(), SketchError> {
    println!("=== sketch_oxide: All 9 SOTA Algorithms Demo ===\n");

    // 1. UltraLogLog: Cardinality Estimation
    println!("1. UltraLogLog (VLDB 2024) - Cardinality Estimation");
    println!("   28% more space-efficient than HyperLogLog");
    {
        let mut ull = UltraLogLog::new(12)?;

        // Add unique user IDs
        for user_id in 0..10000 {
            ull.update(&user_id);
        }

        let estimate = ull.estimate();
        let error = ((estimate - 10000.0).abs() / 10000.0) * 100.0;

        println!("   Added: 10,000 unique items");
        println!("   Estimated: {:.0} items", estimate);
        println!("   Error: {:.2}%", error);
        println!("   Memory: ~{} bytes\n", 1 << 12); // 2^12 = 4096 bytes
    }

    // 2. Binary Fuse Filter: Membership Testing
    println!("2. Binary Fuse Filter (ACM JEA 2022) - Membership Testing");
    println!("   75% smaller than Bloom filters");
    {
        // Build filter from known items
        let seen_ids: Vec<u64> = (0..10000).collect();
        let filter = BinaryFuseFilter::from_items(seen_ids.iter().copied(), 9)?;

        // Test membership
        let test_present = 5000u64;
        let test_absent = 20000u64;

        println!("   Built filter for 10,000 items");
        println!(
            "   Item {} present: {}",
            test_present,
            filter.contains(&test_present)
        );
        println!(
            "   Item {} present: {}",
            test_absent,
            filter.contains(&test_absent)
        );
        println!("   False positive rate: ~1%");
        println!("   Bits per entry: {:.2}\n", filter.bits_per_entry());
    }

    // 3. DDSketch: Quantile Estimation
    println!("3. DDSketch (VLDB 2019) - Quantile Estimation");
    println!("   Relative error guarantees, 4x faster than target");
    {
        let mut dd = DDSketch::new(0.01)?; // 1% relative error

        // Add latency measurements (in milliseconds)
        for i in 0..10000 {
            let latency = 10.0 + (i as f64) * 0.1; // 10-1010 ms
            dd.add(latency);
        }

        println!("   Added: 10,000 latency measurements");
        println!("   p50: {:.2} ms", dd.quantile(0.50).unwrap_or(0.0));
        println!("   p95: {:.2} ms", dd.quantile(0.95).unwrap_or(0.0));
        println!("   p99: {:.2} ms", dd.quantile(0.99).unwrap_or(0.0));
        println!("   p99.9: {:.2} ms", dd.quantile(0.999).unwrap_or(0.0));
        println!("   Relative accuracy: 1%\n");
    }

    // 4. REQ Sketch: Tail Quantiles
    println!("4. REQ Sketch (PODS 2021) - Tail Quantile Specialist");
    println!("   Zero error at p100 in HRA mode");
    {
        let mut req =
            ReqSketch::new(128, ReqMode::HighRankAccuracy).expect("Failed to create REQ sketch");

        // Add response times
        for i in 0..10000 {
            let response_time = 50.0 + (i as f64) * 0.5;
            req.update(response_time);
        }

        println!("   Added: 10,000 response times");
        println!("   p99: {:.2} ms", req.quantile(0.99).unwrap_or(0.0));
        println!("   p99.9: {:.2} ms", req.quantile(0.999).unwrap_or(0.0));
        println!("   p100 (max): {:.2} ms", req.quantile(1.0).unwrap_or(0.0));
        println!("   Zero error at p100 ✅\n");
    }

    // 5. Count-Min Sketch: Frequency Estimation
    println!("5. Count-Min Sketch (2003) - Frequency Estimation");
    println!("   No better alternative for point queries");
    {
        let mut cms = CountMinSketch::new(0.01, 0.01)?; // ε=0.01, δ=0.01

        // Track IP address requests
        let ips = vec![
            "192.168.1.1",
            "10.0.0.1",
            "192.168.1.1",
            "172.16.0.1",
            "192.168.1.1",
        ];

        for ip in &ips {
            cms.update(ip);
        }

        println!("   Tracked {} requests", ips.len());
        println!(
            "   Frequency of '192.168.1.1': ~{}",
            cms.estimate(&"192.168.1.1")
        );
        println!("   Frequency of '10.0.0.1': ~{}", cms.estimate(&"10.0.0.1"));
        println!("   Frequency of '8.8.8.8': ~{}", cms.estimate(&"8.8.8.8"));
        println!("   Never underestimates ✅\n");
    }

    // 6. MinHash: Similarity Estimation
    println!("6. MinHash (STOC 1997) - Similarity Estimation");
    println!("   Still best for Jaccard similarity");
    {
        let mut mh1 = MinHash::new(128)?; // 128 permutations
        let mut mh2 = MinHash::new(128)?;

        // Document 1: "the quick brown fox"
        for word in ["the", "quick", "brown", "fox"].iter() {
            mh1.update(word);
        }

        // Document 2: "the lazy brown dog"
        for word in ["the", "lazy", "brown", "dog"].iter() {
            mh2.update(word);
        }

        let similarity = mh1.jaccard_similarity(&mh2)?;

        println!("   Document 1: 'the quick brown fox'");
        println!("   Document 2: 'the lazy brown dog'");
        println!("   Common words: 'the', 'brown'");
        println!("   Jaccard similarity: {:.2}%", similarity * 100.0);
        println!("   Expected: ~33% (2 of 6 unique words)\n");
    }

    // 7. Theta Sketch: Set Operations
    println!("7. Theta Sketch (2015) - Set Operations");
    println!("   Only sketch supporting union/intersection/difference");
    {
        let mut theta1 = ThetaSketch::new(12)?;
        let mut theta2 = ThetaSketch::new(12)?;

        // Set 1: users who visited page A
        for user_id in 0..1000 {
            theta1.update(&user_id);
        }

        // Set 2: users who visited page B (500-1500)
        for user_id in 500..1500 {
            theta2.update(&user_id);
        }

        let union_sketch = theta1.union(&theta2)?;
        let intersection_sketch = theta1.intersect(&theta2)?;

        println!("   Set A: 1,000 users (0-999)");
        println!("   Set B: 1,000 users (500-1499)");
        println!("   Union (A ∪ B): ~{:.0} users", union_sketch.estimate());
        println!(
            "   Intersection (A ∩ B): ~{:.0} users",
            intersection_sketch.estimate()
        );
        println!("   Expected: 1,500 union, 500 intersection\n");
    }

    // 8. CPC Sketch: Space-Efficient Cardinality
    println!("8. CPC Sketch (2017) - Maximum Space Efficiency");
    println!("   30-40% better than HyperLogLog");
    {
        let mut cpc = CpcSketch::new(11)?;

        // Add items
        for item in 0..10000 {
            cpc.update(&item);
        }

        let estimate = cpc.estimate();
        let error = ((estimate - 10000.0).abs() / 10000.0) * 100.0;

        println!("   Added: 10,000 unique items");
        println!("   Estimated: {:.0} items", estimate);
        println!("   Error: {:.2}%", error);
        println!("   Adaptive flavors for space efficiency ✅\n");
    }

    // 9. Frequent Items: Top-K Heavy Hitters
    println!("9. Frequent Items (2024) - Top-K Heavy Hitters");
    println!("   Deterministic error bounds");
    {
        use sketch_oxide::frequency::ErrorType;

        let mut freq = FrequentItems::new(100)?; // Track top 100

        // Simulate page views (80/20 distribution)
        let pages = vec![
            ("/home", 1000),
            ("/products", 500),
            ("/about", 300),
            ("/contact", 200),
            ("/other1", 50),
            ("/other2", 50),
        ];

        for (page, count) in &pages {
            for _ in 0..*count {
                freq.update(page.to_string());
            }
        }

        let top_items = freq.frequent_items(ErrorType::NoFalsePositives);

        println!(
            "   Tracked {} total views",
            pages.iter().map(|(_, c)| c).sum::<i32>()
        );
        println!("   Top pages:");
        for (item, lower, upper) in top_items.iter().take(5) {
            println!("     {}: [{}, {}] views", item, lower, upper);
        }
        println!("   No false positives ✅\n");
    }

    println!("=== All 9 Algorithms Demonstrated Successfully ===");
    println!("\nKey Takeaways:");
    println!("✅ UltraLogLog: 28% better than HyperLogLog");
    println!("✅ Binary Fuse: 75% better than Bloom Filter");
    println!("✅ DDSketch: 4x faster with formal guarantees");
    println!("✅ All algorithms production-ready");
    println!("\n🚀 This is a 2025 library, not a 2015 library!");

    Ok(())
}