memo-cache 0.12.0

mod tests_external {
    use memo_cache::MemoCache;

    #[test]
    fn test_empty() {
        let c = MemoCache::<bool, bool, 2>::new();

        assert_eq!(c.capacity(), 2);

        // NOTE: Even though the cache memory is pre-allocated, each cache slot should be marked as "empty".
        assert_eq!(c.get(&true), None);
        assert_eq!(c.get(&false), None);
    }

    #[test]
    fn test_simple() {
        let mut c = MemoCache::<_, _, 3>::new();

        c.insert("The Answer", 42); // K = &str, V = i32

        assert_eq!(c.get("The Answer"), Some(&42));
    }

    #[test]
    fn test_contains_key() {
        let mut c = MemoCache::<&str, i32, 3>::new();

        assert_eq!(c.contains_key("hello"), false);

        c.insert("hello", 42);

        assert_eq!(c.contains_key("hello"), true);
    }

    #[test]
    fn test_get() {
        let mut c = MemoCache::<&str, i32, 3>::new();

        assert_eq!(c.get("hello"), None);

        c.insert("hello", 42);

        assert_eq!(c.get("hello"), Some(&42));
    }

    #[test]
    fn test_get_mut() {
        let mut c = MemoCache::<&str, i32, 3>::new();

        assert_eq!(c.get_mut("hello"), None);

        c.insert("hello", 42);

        if let Some(v) = c.get_mut("hello") {
            assert_eq!(v, &mut 42);

            *v = 100;
        }

        assert_eq!(c.get("hello"), Some(&100));
    }

    #[test]
    fn test_get_or_insert_with() {
        let mut c = MemoCache::<String, i32, 3>::new();

        assert_eq!(c.contains_key("hello"), false);
        assert_eq!(c.contains_key("hi"), false);

        // Insert a new key.
        assert_eq!(
            c.get_or_insert_with(&"hello".to_owned(), |s| {
                assert_eq!(s, "hello");
                42
            }),
            &42
        );

        assert_eq!(c.get("hello"), Some(&42));
        assert_eq!(c.contains_key("hi"), false);

        // Insert another new key.
        assert_eq!(
            c.get_or_insert_with(&"hi".to_owned(), |s| {
                assert_eq!(s, "hi");
                17
            }),
            &17
        );

        assert_eq!(c.get("hello"), Some(&42));
        assert_eq!(c.get("hi"), Some(&17));

        // Get an existing key (function is not called).
        assert_eq!(
            c.get_or_insert_with(&"hello".to_owned(), |_| {
                assert!(false);
                13 // NOTE: Key already exists, this value is not used.
            }),
            &42
        );
    }

    #[test]
    fn test_get_or_try_insert_with() {
        let mut c = MemoCache::<String, i32, 3>::new();

        assert_eq!(c.contains_key("hello"), false);
        assert_eq!(c.contains_key("hi"), false);

        // Insert a new key.
        assert_eq!(
            c.get_or_try_insert_with(&"hello".to_owned(), |s| -> Result<_, ()> {
                assert_eq!(s, "hello");
                Ok(42)
            }),
            Ok(&42)
        );

        assert_eq!(c.get("hello"), Some(&42));
        assert_eq!(c.contains_key("hi"), false);

        // Insert another new key.
        assert_eq!(
            c.get_or_try_insert_with(&"hi".to_owned(), |s| -> Result<_, ()> {
                assert_eq!(s, "hi");
                Ok(17)
            }),
            Ok(&17)
        );

        assert_eq!(c.get("hello"), Some(&42));
        assert_eq!(c.get("hi"), Some(&17));

        // Get an existing key (function is not called).
        assert_eq!(
            c.get_or_try_insert_with(&"hello".to_owned(), |_| -> Result<_, ()> {
                assert!(false);
                Ok(13) // NOTE: Key already exists, this value is not used.
            }),
            Ok(&42)
        );

        // Failing insert attempt for a nonexistent key.
        assert_eq!(
            c.get_or_try_insert_with(&"G'day".to_owned(), |s| {
                assert_eq!(s, "G'day");
                Err("Whoops")
            }),
            Err("Whoops")
        );

        assert_eq!(c.get("G'day"), None);
    }

    #[test]
    fn test_clear() {
        let mut c = MemoCache::<&str, i32, 3>::new();

        assert_eq!(c.get("hello"), None);

        c.insert("hello", 42);

        assert_eq!(c.get("hello"), Some(&42));

        c.clear();

        assert_eq!(c.get("hello"), None);
    }

    #[test]
    fn test_borrow() {
        let mut c = MemoCache::<String, i32, 3>::new();

        c.insert("hello".to_owned(), 42);

        // Get using borrowed type (i.e. `&str`).
        assert_eq!(c.contains_key("hello"), true);
        assert_eq!(c.get("hello"), Some(&42));
        assert_eq!(c.get_mut("hello"), Some(&mut 42));
    }

    #[test]
    fn test_nonempty() {
        let mut c = MemoCache::<String, i32, 3>::new();

        assert_eq!(c.capacity(), 3);

        let kvs = vec![
            ("veni".to_owned(), 19),
            ("vidi".to_owned(), 23),
            ("vici".to_owned(), 29),
        ];
        let kv0 = kvs.get(0).unwrap();
        let kv1 = kvs.get(1).unwrap();
        let kv2 = kvs.get(2).unwrap();

        assert_eq!(c.get(&kv0.0), None);
        assert_eq!(c.get(&kv1.0), None);
        assert_eq!(c.get(&kv2.0), None);

        c.insert(kv0.0.clone(), kv0.1);

        assert_eq!(c.get(&kv0.0), Some(&kv0.1));

        c.insert(kv1.0.clone(), kv1.1);

        assert_eq!(c.get(&kv1.0), Some(&kv1.1));

        c.insert(kv2.0.clone(), kv2.1);

        assert_eq!(c.get(&kv2.0), Some(&kv2.1));

        // The cache is now full, and another insertion will make one key/value be removed.

        c.insert("blah".to_owned(), 42);

        // We don't know which slot was evicted.
        assert!(c.get(&kv0.0).is_none() || c.get(&kv1.0).is_none() || c.get(&kv2.0).is_none());

        // Generate a number of hits for the new elements, to make sure the old key/value pairs are evicted.
        for _ in 0..10 {
            c.get("blah");
        }

        c.insert("bleh".to_owned(), 42);
        for _ in 0..10 {
            c.get("bleh");
        }

        c.insert("bloh".to_owned(), 42);
        for _ in 0..10 {
            c.get("bleh");
        }

        assert_eq!(c.get(&kv0.0), None);
        assert_eq!(c.get(&kv1.0), None);
        assert_eq!(c.get(&kv2.0), None);
    }

    #[test]
    fn test_duplicate_insertions() {
        let mut c = MemoCache::<String, i32, 2>::new();

        let kv0 = ("John".to_owned(), 17);
        let kv1 = ("Doe".to_owned(), 19);

        assert_eq!(c.get(&kv0.0), None);
        assert_eq!(c.get(&kv1.0), None);

        c.insert(kv0.0.to_owned(), kv0.1);
        c.insert(kv1.0.to_owned(), kv1.1);

        assert_eq!(c.get(&kv0.0), Some(&kv0.1));
        assert_eq!(c.get(&kv1.0), Some(&kv1.1));

        // Inserting a duplicate key/value should be a no-op.

        c.insert(kv0.0.to_owned(), kv0.1);

        assert_eq!(c.get(&kv0.0), Some(&kv0.1));
        assert_eq!(c.get(&kv1.0), Some(&kv1.1));

        // Inserting a duplicate key with a new value should update the value.

        assert_eq!(c.get(&kv0.0), Some(&kv0.1));
        assert_eq!(c.get(&kv1.0), Some(&kv1.1));

        c.insert(kv0.0.to_owned(), 42);

        assert_eq!(c.get(&kv0.0), Some(&42)); // Updated.
        assert_eq!(c.get(&kv1.0), Some(&kv1.1));
    }

    #[test]
    fn test_hit_counting() {
        let mut c = MemoCache::<&str, i32, 3>::new();

        c.insert("key1", 10);
        c.insert("key2", 20);

        // Access key1 multiple times to increase its hit count.
        for _ in 0..5 {
            assert_eq!(c.get("key1"), Some(&10));
        }

        // Access key2 fewer times.
        for _ in 0..2 {
            assert_eq!(c.get("key2"), Some(&20));
        }

        c.insert("key3", 30);

        assert_eq!(c.get("key1"), Some(&10));
        assert_eq!(c.get("key2"), Some(&20));
        assert_eq!(c.get("key3"), Some(&30));

        c.insert("key4", 40);

        // key1 should still be present due to higher hit count.
        assert_eq!(c.get("key1"), Some(&10));
        let key2_present = c.get("key2").is_some();
        let key3_present = c.get("key3").is_some();
        let key4_present = c.get("key4").is_some();

        assert_eq!(
            [key2_present, key3_present, key4_present]
                .iter()
                .filter(|&&x| x)
                .count(),
            2
        );
        assert!(key4_present); // Newly inserted key should be present.
    }

    #[test]
    fn test_hit_decay_mechanism() {
        let mut c = MemoCache::<i32, i32, 2>::new();

        c.insert(1, 100);
        c.insert(2, 200);

        // Simulate high hit counts by accessing many times.
        for _ in 0..300 {
            c.get(&1);
            c.get(&2);
        }

        // Cache should still work correctly after potential decay.
        assert_eq!(c.get(&1), Some(&100));
        assert_eq!(c.get(&2), Some(&200));

        c.insert(3, 300);
        assert_eq!(c.get(&3), Some(&300));
    }

    #[test]
    fn test_eviction_with_different_hit_patterns() {
        let mut c = MemoCache::<&str, i32, 4>::new();

        c.insert("hot", 1);
        c.insert("warm", 2);
        c.insert("cold", 3);
        c.insert("unused", 4);

        for _ in 0..10 {
            c.get("hot");
        }
        for _ in 0..5 {
            c.get("warm");
        }
        c.get("cold");

        c.insert("new1", 5);

        assert_eq!(c.get("hot"), Some(&1));
        assert_eq!(c.get("new1"), Some(&5));

        let unused_evicted = c.get("unused").is_none();

        // At least one item should be evicted, and unused is most likely.
        assert!(unused_evicted || c.get("cold").is_none());
    }

    #[test]
    fn test_edge_case_small_caches() {
        let mut c1 = MemoCache::<&str, i32, 1>::new();

        c1.insert("first", 1);
        assert_eq!(c1.get("first"), Some(&1));

        // Should evict the only item.
        c1.insert("second", 2);
        assert_eq!(c1.get("second"), Some(&2));
        assert_eq!(c1.get("first"), None);

        let value = c1.get_or_insert_with(&"third", |_| 3);
        assert_eq!(value, &3);
        assert_eq!(c1.get("third"), Some(&3));
        assert_eq!(c1.get("second"), None);
    }

    #[test]
    fn test_get_or_insert_stress() {
        let mut c = MemoCache::<i32, String, 8>::new();

        for i in 0..20 {
            let key = i % 12; // Some keys will repeat.
            let value = c.get_or_insert_with(&key, |k| format!("Value {}", k));
            assert_eq!(value, &format!("Value {}", key));
        }

        assert_eq!(c.get(&5), Some(&"Value 5".to_string()));
    }

    #[test]
    fn test_diverse_types() {
        let mut c = MemoCache::<(i32, String), Vec<u8>, 3>::new();

        let key1 = (1, "hello".to_string());
        let key2 = (2, "world".to_string());
        let value1 = vec![1, 2, 3];
        let value2 = vec![4, 5, 6];

        c.insert(key1.clone(), value1.clone());
        c.insert(key2.clone(), value2.clone());

        assert_eq!(c.get(&key1), Some(&value1));
        assert_eq!(c.get(&key2), Some(&value2));

        assert!(c.contains_key(&key1));
        assert!(c.contains_key(&key2));
    }

    #[test]
    fn test_update_value_preserves_hits() {
        let mut c = MemoCache::<&str, i32, 3>::new();

        c.insert("key", 1);

        // Build up some hits.
        for _ in 0..5 {
            c.get("key");
        }

        // Update the value with same key.
        c.insert("key", 2);
        assert_eq!(c.get("key"), Some(&2));

        c.insert("other1", 10);
        c.insert("other2", 20);
        c.insert("other3", 30);

        let _key_survived = c.get("key").is_some();

        // At minimum, verify the cache is still functioning correctly.
        assert_eq!(c.capacity(), 3);
        let total_items = [
            c.get("key"),
            c.get("other1"),
            c.get("other2"),
            c.get("other3"),
        ]
        .iter()
        .filter(|x| x.is_some())
        .count();
        assert_eq!(total_items, 3);
    }

    #[test]
    fn test_zero_hits_early_eviction() {
        let mut c = MemoCache::<i32, &str, 4>::new();

        c.insert(1, "one");
        c.insert(2, "two");
        c.insert(3, "three");
        c.insert(4, "four");

        for _ in 0..3 {
            c.get(&1);
            c.get(&2);
        }

        // Items 3 and 4 have zero hits, so should be preferred for eviction.
        c.insert(5, "five");

        // Items with hits should survive.
        assert_eq!(c.get(&1), Some(&"one"));
        assert_eq!(c.get(&2), Some(&"two"));
        assert_eq!(c.get(&5), Some(&"five"));

        let three_present = c.get(&3).is_some();
        let four_present = c.get(&4).is_some();

        // Exactly one of the zero-hit items should remain.
        assert_ne!(three_present, four_present);
    }

    #[test]
    fn test_clone() {
        let mut c1 = MemoCache::<String, i32, 3>::new();

        c1.insert("foo".to_owned(), 10);
        c1.insert("bar".to_owned(), 20);

        let c2 = c1.clone();

        // Both caches should have same data.
        assert_eq!(c1.get("foo"), Some(&10));
        assert_eq!(c1.get("bar"), Some(&20));
        assert_eq!(c2.get("foo"), Some(&10));
        assert_eq!(c2.get("bar"), Some(&20));

        // Mutations should be independent.
        c1.insert("baz".to_owned(), 30);
        assert_eq!(c1.get("baz"), Some(&30));
        assert_eq!(c2.get("baz"), None);
    }
}