LRUCacheTest.java

package lrucache;

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.Timeout;

import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

import static org.junit.jupiter.api.Assertions.*;

class LRUCacheTest {

    // ------------------------------------------------------------------
    // Basic correctness
    // ------------------------------------------------------------------

    @Test
    void get_returnsNull_onMiss() {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder().capacity(3).build();
        assertNull(cache.get("missing"));
    }

    @Test
    void put_and_get_roundtrip() {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder().capacity(3).build();
        cache.put("a", 1);
        assertEquals(1, cache.get("a"));
    }

    @Test
    void put_updatesExistingValue() {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder().capacity(3).build();
        cache.put("a", 1);
        cache.put("a", 99);
        assertEquals(99, cache.get("a"));
        assertEquals(1, cache.size());
    }

    // ------------------------------------------------------------------
    // Eviction order
    // ------------------------------------------------------------------

    @Test
    void evicts_leastRecentlyUsed_onCapacityExceeded() {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder().capacity(3).build();
        cache.put("a", 1);
        cache.put("b", 2);
        cache.put("c", 3);
        // Access "a" so "b" becomes LRU
        cache.get("a");
        // Adding "d" should evict "b"
        cache.put("d", 4);
        assertNull(cache.get("b"),  "b should have been evicted");
        assertNotNull(cache.get("a"), "a was recently used — must survive");
        assertNotNull(cache.get("c"), "c must survive");
        assertNotNull(cache.get("d"), "d was just added — must survive");
    }

    @Test
    void put_onExistingKey_promotesToMRU() {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder().capacity(2).build();
        cache.put("a", 1);
        cache.put("b", 2);
        // Update "a" — promotes it, so "b" becomes LRU
        cache.put("a", 10);
        cache.put("c", 3);   // should evict "b"
        assertNull(cache.get("b"));
        assertEquals(10, cache.get("a"));
    }

    // ------------------------------------------------------------------
    // TTL expiry
    // ------------------------------------------------------------------

    @Test
    @Timeout(3)
    void expired_entry_returns_null() throws InterruptedException {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder()
                .capacity(10)
                .ttlMs(100)      // 100 ms TTL
                .build();
        cache.put("x", 42);
        assertEquals(42, cache.get("x"));
        Thread.sleep(200);
        assertNull(cache.get("x"), "entry should have expired after 200ms");
    }

    @Test
    @Timeout(3)
    void non_expired_entry_still_accessible() throws InterruptedException {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder()
                .capacity(10)
                .ttlMs(500)
                .build();
        cache.put("y", 7);
        Thread.sleep(100);
        assertEquals(7, cache.get("y"), "entry is still within TTL window");
    }

    // ------------------------------------------------------------------
    // Stats
    // ------------------------------------------------------------------

    @Test
    void stats_trackHitsAndMisses() {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder().capacity(5).build();
        cache.put("k", 1);
        cache.get("k");     // hit
        cache.get("k");     // hit
        cache.get("nope");  // miss
        assertEquals(2, cache.stats().getHits());
        assertEquals(1, cache.stats().getMisses());
    }

    @Test
    void stats_trackEvictions() {
        LRUCache<String, Integer> cache = LRUCache.<String, Integer>builder().capacity(2).build();
        cache.put("a", 1);
        cache.put("b", 2);
        cache.put("c", 3);  // evicts "a"
        assertEquals(1, cache.stats().getEvictions());
    }

    // ------------------------------------------------------------------
    // Concurrency — the most important test block
    // ------------------------------------------------------------------

    @Test
    @Timeout(10)
    void concurrent_puts_and_gets_do_not_corrupt_state() throws InterruptedException {
        int threads = 8;
        int opsPerThread = 2000;
        LRUCache<Integer, Integer> cache = LRUCache.<Integer, Integer>builder()
                .capacity(100)
                .build();

        CountDownLatch start = new CountDownLatch(1);
        CountDownLatch done  = new CountDownLatch(threads);
        AtomicInteger errors = new AtomicInteger();

        ExecutorService pool = Executors.newFixedThreadPool(threads);
        for (int t = 0; t < threads; t++) {
            final int tid = t;
            pool.submit(() -> {
                try {
                    start.await();
                    for (int i = 0; i < opsPerThread; i++) {
                        int key = (tid * opsPerThread + i) % 150;  // intentional key overlap
                        cache.put(key, key * 2);
                        Integer v = cache.get(key);
                        // Value must be even (key * 2) if present
                        if (v != null && v % 2 != 0) errors.incrementAndGet();
                    }
                } catch (Exception e) {
                    errors.incrementAndGet();
                } finally {
                    done.countDown();
                }
            });
        }

        start.countDown();      // release all threads simultaneously
        done.await(9, TimeUnit.SECONDS);
        pool.shutdown();

        assertEquals(0, errors.get(), "No data corruption expected under concurrent access");
    }
}