cleep 0.1.0

use crate::kv::*;
use std::fmt;

/// A single-threaded cache that returns a value for any key, fetching on miss.
pub trait Cache<K, V>
where
    K: CacheKey,
    V: CacheValue,
{
    fn get(&mut self, key: &K) -> V;
}

/// A single-threaded clock-hand eviction cache with a fixed capacity `CAP`.
///
/// On a miss the `fetcher` closure is called and the result replaces the slot chosen by the clock hand.
///
/// `CAP` must be a power of two.
pub struct ClockCache<K, V, F, const CAP: usize>
where
    K: CacheKey,
    V: CacheValue,
    F: FnMut(&K) -> V,
{
    fetcher: F,

    hand: usize,
    len: usize,

    keys: [K; CAP],
    values: [V; CAP],
    refs: [bool; CAP],
}

impl<K, V, F, const CAP: usize> ClockCache<K, V, F, CAP>
where
    K: CacheKey,
    V: CacheValue,
    F: FnMut(&K) -> V,
{
    pub fn new(fetcher: F) -> Self {
        const {
            assert!(CAP.is_power_of_two(), "CAP must be a power of two");
        }

        Self {
            fetcher,
            hand: 0,
            len: 0,
            keys: [K::GUARD; CAP],
            values: [V::default(); CAP],
            refs: [false; CAP],
        }
    }

    #[inline]
    pub fn len(&self) -> usize {
        self.len
    }

    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    #[inline]
    pub const fn capacity(&self) -> usize {
        CAP
    }

    #[inline]
    pub fn get(&mut self, key: &K) -> V {
        if let Some(index) = K::find_key(&self.keys, key)
            && index < self.len
        {
            self.refs[index] = true;
            return self.values[index];
        }

        let value = (self.fetcher)(key);

        loop {
            let i = self.hand;
            if self.refs[i] {
                self.refs[i] = false;
            } else {
                self.keys[i] = *key;
                self.values[i] = value;
                self.hand = (self.hand + 1) & (CAP - 1);
                if self.len < CAP {
                    self.len += 1;
                }
                return value;
            }
            self.hand = (self.hand + 1) & (CAP - 1);
        }
    }
}

impl<K, V, F, const CAP: usize> Cache<K, V> for ClockCache<K, V, F, CAP>
where
    K: CacheKey,
    V: CacheValue,
    F: FnMut(&K) -> V,
{
    #[inline]
    fn get(&mut self, key: &K) -> V {
        ClockCache::get(self, key)
    }
}

impl<K, V, F, const CAP: usize> fmt::Debug for ClockCache<K, V, F, CAP>
where
    K: CacheKey + fmt::Debug,
    V: CacheValue + fmt::Debug,
    F: FnMut(&K) -> V,
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("ClockCache")
            .field("len", &self.len)
            .field("capacity", &CAP)
            .field("hand", &self.hand)
            .finish()
    }
}

#[cfg(test)]
mod single_threaded_tests {
    use super::*;
    use std::cell::Cell;

    fn fetcher(key: &usize) -> usize {
        *key
    }

    #[test]
    fn tests_scenario_1() {
        let cache_miss_count = Cell::new(0);
        let mut cache = ClockCache::<usize, usize, _, 4>::new(|key| {
            cache_miss_count.set(cache_miss_count.get() + 1);
            fetcher(key)
        });

        let sequence = "0 4 1 4 2 4 3 4 2 4 0 4 1 4 2 4 3 4"
            .split(" ")
            .map(|s| s.parse::<usize>().unwrap());
        for i in sequence {
            let _ = cache.get(&i);
        }
        assert_eq!(8, cache_miss_count.get());
    }

    #[test]
    fn tests_scenario_2() {
        let cache_miss_count = Cell::new(0);
        let mut cache = ClockCache::<usize, usize, _, 4>::new(|key| {
            cache_miss_count.set(cache_miss_count.get() + 1);
            fetcher(key)
        });

        let sequence = "2 5 10 1 2 2 6 9 1 2 10 2 6 1 2 1 6 9 5 1"
            .split(" ")
            .map(|s| s.parse::<usize>().unwrap());
        for i in sequence {
            let _ = cache.get(&i);
        }
        assert_eq!(11, cache_miss_count.get());
    }

    #[test]
    fn test_guard_key() {
        // Test usize::MAX
        let mut cache = ClockCache::<usize, usize, _, 4>::new(|key| key.wrapping_add(10));
        assert_eq!(cache.get(&usize::MAX), usize::MAX.wrapping_add(10));
        assert_eq!(cache.len(), 1);
        // Hit on guard key
        assert_eq!(cache.get(&usize::MAX), usize::MAX.wrapping_add(10));

        // Test u8::MAX (255)
        let mut u8_cache = ClockCache::<u8, u8, _, 4>::new(|key| key.wrapping_add(1));
        assert_eq!(u8_cache.get(&255), 0);
        assert_eq!(u8_cache.len(), 1);
        assert_eq!(u8_cache.get(&255), 0);

        // Mix guard key with other keys
        assert_eq!(u8_cache.get(&1), 2);
        assert_eq!(u8_cache.get(&2), 3);
        assert_eq!(u8_cache.get(&3), 4);
        assert_eq!(u8_cache.len(), 4);
        // All 4 slots full, verify guard key is still accessible
        assert_eq!(u8_cache.get(&255), 0);
    }

    #[test]
    fn test_capacity_one() {
        let miss_count = Cell::new(0);
        let mut cache = ClockCache::<usize, usize, _, 1>::new(|key| {
            miss_count.set(miss_count.get() + 1);
            key * 10
        });

        assert_eq!(cache.capacity(), 1);
        assert!(cache.is_empty());

        assert_eq!(cache.get(&1), 10);
        assert_eq!(miss_count.get(), 1);
        assert_eq!(cache.len(), 1);
        assert!(!cache.is_empty());

        // Hit
        assert_eq!(cache.get(&1), 10);
        assert_eq!(miss_count.get(), 1);

        // Miss with eviction
        assert_eq!(cache.get(&2), 20);
        assert_eq!(miss_count.get(), 2);
        assert_eq!(cache.len(), 1);

        // Key 1 is evicted
        assert_eq!(cache.get(&1), 10);
        assert_eq!(miss_count.get(), 3);
    }

    #[test]
    fn test_second_chance_eviction() {
        let misses = Cell::new(0);
        let mut cache = ClockCache::<usize, usize, _, 2>::new(|key| {
            misses.set(misses.get() + 1);
            *key
        });

        // Insert key 1 and key 2
        cache.get(&1);
        cache.get(&2);
        assert_eq!(misses.get(), 2);
        assert_eq!(cache.len(), 2);

        // Read key 1 to set its ref bit = true
        cache.get(&1);
        assert_eq!(misses.get(), 2);

        // Insert key 3:
        // Hand is at slot 0 (key 1, ref=true). Ref is cleared to false, hand moves to slot 1 (key 2, ref=false).
        // Key 2 is evicted and replaced with key 3.
        cache.get(&3);
        assert_eq!(misses.get(), 3);

        // Key 1 survived eviction!
        cache.get(&1);
        assert_eq!(misses.get(), 3);

        // Key 3 is present
        cache.get(&3);
        assert_eq!(misses.get(), 3);

        // Key 2 was evicted -> miss
        cache.get(&2);
        assert_eq!(misses.get(), 4);
    }

    #[test]
    fn test_all_primitive_types() {
        // u8
        let mut c_u8 = ClockCache::<u8, u8, _, 2>::new(|k| *k);
        assert_eq!(c_u8.get(&42), 42);
        assert_eq!(c_u8.get(&42), 42);

        // i8
        let mut c_i8 = ClockCache::<i8, i8, _, 2>::new(|k| *k);
        assert_eq!(c_i8.get(&-10), -10);
        assert_eq!(c_i8.get(&-10), -10);
        assert_eq!(c_i8.get(&i8::MAX), i8::MAX);

        // u16
        let mut c_u16 = ClockCache::<u16, u16, _, 2>::new(|k| *k);
        assert_eq!(c_u16.get(&1000), 1000);
        assert_eq!(c_u16.get(&u16::MAX), u16::MAX);

        // i16
        let mut c_i16 = ClockCache::<i16, i16, _, 2>::new(|k| *k);
        assert_eq!(c_i16.get(&-500), -500);
        assert_eq!(c_i16.get(&i16::MAX), i16::MAX);

        // u32
        let mut c_u32 = ClockCache::<u32, u32, _, 2>::new(|k| *k);
        assert_eq!(c_u32.get(&100_000), 100_000);
        assert_eq!(c_u32.get(&u32::MAX), u32::MAX);

        // i32
        let mut c_i32 = ClockCache::<i32, i32, _, 2>::new(|k| *k);
        assert_eq!(c_i32.get(&-100_000), -100_000);
        assert_eq!(c_i32.get(&i32::MAX), i32::MAX);

        // u64
        let mut c_u64 = ClockCache::<u64, u64, _, 2>::new(|k| *k);
        assert_eq!(c_u64.get(&1_000_000_000), 1_000_000_000);
        assert_eq!(c_u64.get(&u64::MAX), u64::MAX);

        // i64
        let mut c_i64 = ClockCache::<i64, i64, _, 2>::new(|k| *k);
        assert_eq!(c_i64.get(&-1_000_000_000), -1_000_000_000);
        assert_eq!(c_i64.get(&i64::MAX), i64::MAX);

        // isize
        let mut c_isize = ClockCache::<isize, isize, _, 2>::new(|k| *k);
        assert_eq!(c_isize.get(&-42), -42);
        assert_eq!(c_isize.get(&isize::MAX), isize::MAX);

        // f32
        let mut c_f32 = ClockCache::<f32, f32, _, 2>::new(|k| *k);
        assert_eq!(c_f32.get(&3.14), 3.14);
        assert_eq!(c_f32.get(&f32::MAX), f32::MAX);

        // f64
        let mut c_f64 = ClockCache::<f64, f64, _, 2>::new(|k| *k);
        assert_eq!(c_f64.get(&2.71828), 2.71828);
        assert_eq!(c_f64.get(&f64::MAX), f64::MAX);
    }

    #[test]
    fn test_fn_mut_closure() {
        let mut call_count = 0;
        let mut cache = ClockCache::<usize, usize, _, 4>::new(|key| {
            call_count += 1;
            *key * 2
        });

        assert_eq!(cache.get(&5), 10);
        assert_eq!(cache.get(&5), 10);
        assert_eq!(call_count, 1);
    }

    #[test]
    fn test_inherent_methods_and_debug() {
        let mut cache = ClockCache::<usize, usize, _, 4>::new(|key| *key);
        assert!(cache.is_empty());
        assert_eq!(cache.len(), 0);
        assert_eq!(cache.capacity(), 4);

        cache.get(&1);
        assert!(!cache.is_empty());
        assert_eq!(cache.len(), 1);

        let debug_str = format!("{:?}", cache);
        assert!(debug_str.contains("ClockCache"));
        assert!(debug_str.contains("len: 1"));
    }
}

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

    use std::hint::black_box;
    use std::time::Instant;

    fn mock_fetcher(key: &usize) -> usize {
        key.wrapping_mul(2654435761)
    }

    /// Simulates real-world 80/20 locality (80% requests hit 20% of items).
    #[test]
    fn high_hit_rate() {
        const CACHE_SIZE: usize = 256;
        const NUM_OPERATIONS: usize = 5_000_000;

        let mut cache = ClockCache::<usize, usize, _, CACHE_SIZE>::new(mock_fetcher);

        // Pre-generate keys: 80% from small hot range (0..50), 20% from cold range (50..2000)
        let mut state: u64 = 12345;
        let keys: Vec<usize> = (0..NUM_OPERATIONS)
            .map(|_| {
                // LCG
                state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
                let rand_val = (state >> 33) as usize;

                if rand_val % 100 < 80 {
                    rand_val % 50 // Hot items (fits well within 256 cache slots)
                } else {
                    50 + (rand_val % 1950) // Cold items
                }
            })
            .collect();

        println!("Running High Hit Rate Test (5,000,000 ops)...");
        let start = Instant::now();

        for &key in &keys {
            // black_box prevents the compiler from optimizing away unused call results
            black_box(cache.get(&key));
        }

        let elapsed = start.elapsed();
        println!(
            "High Hit Rate Elapsed: {:?} ({:.2} ns/op)",
            elapsed,
            elapsed.as_nanos() as f64 / NUM_OPERATIONS as f64
        );
    }

    #[test]
    fn thrashing() {
        const CACHE_SIZE: usize = 512;
        const NUM_OPERATIONS: usize = 5_000_000;

        let mut cache = ClockCache::<usize, usize, _, CACHE_SIZE>::new(mock_fetcher);

        // Access 1000 distinct keys in sequence (Cache size is 512) to test continuous misses and evictions
        let keys: Vec<usize> = (0..NUM_OPERATIONS).map(|i| i % 1000).collect();

        println!("Running Cache Thrashing Test (5,000,000 ops)...");
        let start = Instant::now();

        for &key in &keys {
            black_box(cache.get(&key));
        }

        let elapsed = start.elapsed();
        println!(
            "Thrashing Elapsed: {:?} ({:.2} ns/op)",
            elapsed,
            elapsed.as_nanos() as f64 / NUM_OPERATIONS as f64
        );
    }

    #[test]
    fn large_linear_scan_overhead() {
        const CACHE_SIZE: usize = 4096;
        const NUM_OPERATIONS: usize = 1_000_000;

        let mut cache = ClockCache::<usize, usize, _, CACHE_SIZE>::new(mock_fetcher);

        let mut state: u64 = 54321;
        let keys: Vec<usize> = (0..NUM_OPERATIONS)
            .map(|_| {
                state = state.wrapping_mul(6364136223846793005).wrapping_add(1);
                ((state >> 33) as usize) % (CACHE_SIZE * 2)
            })
            .collect();

        println!("Running Large Cache Test (1,000,000 ops)...");
        let start = Instant::now();

        for &key in &keys {
            black_box(cache.get(&key));
        }

        let elapsed = start.elapsed();
        println!(
            "Large Cache Elapsed: {:?} ({:.2} ns/op)",
            elapsed,
            elapsed.as_nanos() as f64 / NUM_OPERATIONS as f64
        );
    }
}