LRUCacheDemo.java

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.concurrent.locks.*;

// ─────────────────────────────────────────────────────────────────────────────
// Run:  javac LRUCacheDemo.java && java LRUCacheDemo
// Java: 11+
// ─────────────────────────────────────────────────────────────────────────────
public class LRUCacheDemo {

    // =========================================================================
    // 1. Node  — doubly-linked list node with optional TTL
    // =========================================================================
    static class Node<K, V> {
        final K key;
        V value;
        long expiryMs;          // -1 = no expiry
        Node<K, V> prev, next;

        Node(K key, V value, long ttlMs) {
            this.key      = key;
            this.value    = value;
            this.expiryMs = (ttlMs > 0) ? System.currentTimeMillis() + ttlMs : -1L;
        }

        boolean isExpired() {
            return expiryMs != -1L && System.currentTimeMillis() > expiryMs;
        }
    }

    // =========================================================================
    // 2. CacheStats  — lock-free counters via AtomicLong
    // =========================================================================
    static class CacheStats {
        private final AtomicLong hits      = new AtomicLong();
        private final AtomicLong misses    = new AtomicLong();
        private final AtomicLong evictions = new AtomicLong();

        void recordHit()      { hits.incrementAndGet(); }
        void recordMiss()     { misses.incrementAndGet(); }
        void recordEviction() { evictions.incrementAndGet(); }

        long getHits()      { return hits.get(); }
        long getMisses()    { return misses.get(); }
        long getEvictions() { return evictions.get(); }

        double hitRate() {
            long total = hits.get() + misses.get();
            return total == 0 ? 0.0 : (double) hits.get() / total;
        }

        @Override
        public String toString() {
            return String.format(
                "hits=%-4d misses=%-4d evictions=%-4d hitRate=%.0f%%",
                getHits(), getMisses(), getEvictions(), hitRate() * 100);
        }
    }

    // =========================================================================
    // 3. LRUCache  — the main class
    // =========================================================================
    static class LRUCache<K, V> {

        private final int capacity;
        private final long ttlMs;
        private final Map<K, Node<K, V>> map;
        private final Node<K, V> head;   // sentinel — MRU end
        private final Node<K, V> tail;   // sentinel — LRU end
        private final ReadWriteLock lock = new ReentrantReadWriteLock();
        private final CacheStats stats   = new CacheStats();
        private ScheduledExecutorService sweeper;

        LRUCache(int capacity, long ttlMs, long sweepIntervalMs) {
            this.capacity = capacity;
            this.ttlMs    = ttlMs;
            this.map      = new HashMap<>(capacity);
            head = new Node<>(null, null, 0);
            tail = new Node<>(null, null, 0);
            head.next = tail;
            tail.prev = head;
            if (ttlMs > 0 && sweepIntervalMs > 0) startSweeper(sweepIntervalMs);
        }

        // --- public API ------------------------------------------------------

        public V get(K key) {
            lock.writeLock().lock();
            try {
                Node<K, V> node = map.get(key);
                if (node == null)        { stats.recordMiss(); return null; }
                if (node.isExpired())    {
                    removeNode(node); map.remove(key);
                    stats.recordMiss(); stats.recordEviction();
                    return null;
                }
                moveToFront(node);
                stats.recordHit();
                return node.value;
            } finally { lock.writeLock().unlock(); }
        }

        public void put(K key, V value) {
            lock.writeLock().lock();
            try {
                Node<K, V> existing = map.get(key);
                if (existing != null) {
                    existing.value    = value;
                    existing.expiryMs = (ttlMs > 0)
                        ? System.currentTimeMillis() + ttlMs : -1L;
                    moveToFront(existing);
                    return;
                }
                if (map.size() >= capacity) evictLRU();
                Node<K, V> node = new Node<>(key, value, ttlMs);
                map.put(key, node);
                addToFront(node);
            } finally { lock.writeLock().unlock(); }
        }

        public boolean remove(K key) {
            lock.writeLock().lock();
            try {
                Node<K, V> node = map.remove(key);
                if (node == null) return false;
                removeNode(node);
                return true;
            } finally { lock.writeLock().unlock(); }
        }

        public int       size()  { lock.readLock().lock(); try { return map.size(); } finally { lock.readLock().unlock(); } }
        public CacheStats stats() { return stats; }
        public void shutdown()   { if (sweeper != null) sweeper.shutdown(); }

        // --- linked-list helpers (must be called under write lock) -----------

        private void addToFront(Node<K, V> n) {
            n.prev = head; n.next = head.next;
            head.next.prev = n; head.next = n;
        }
        private void removeNode(Node<K, V> n) {
            n.prev.next = n.next; n.next.prev = n.prev;
        }
        private void moveToFront(Node<K, V> n) { removeNode(n); addToFront(n); }

        private void evictLRU() {
            Node<K, V> lru = tail.prev;
            if (lru == head) return;
            removeNode(lru); map.remove(lru.key);
            stats.recordEviction();
        }

        // --- background TTL sweeper ------------------------------------------

        private void startSweeper(long intervalMs) {
            sweeper = Executors.newSingleThreadScheduledExecutor(r -> {
                Thread t = new Thread(r, "lru-sweeper");
                t.setDaemon(true);
                return t;
            });
            sweeper.scheduleAtFixedRate(this::sweepExpired,
                intervalMs, intervalMs, TimeUnit.MILLISECONDS);
        }

        private void sweepExpired() {
            lock.writeLock().lock();
            try {
                List<K> dead = new ArrayList<>();
                Node<K, V> cur = tail.prev;
                while (cur != head) {
                    if (cur.isExpired()) dead.add(cur.key);
                    cur = cur.prev;
                }
                for (K k : dead) {
                    Node<K, V> n = map.remove(k);
                    if (n != null) { removeNode(n); stats.recordEviction(); }
                }
            } finally { lock.writeLock().unlock(); }
        }

        // --- builder ---------------------------------------------------------

        static <K, V> Builder<K, V> builder() { return new Builder<>(); }

        static class Builder<K, V> {
            private int  capacity       = 100;
            private long ttlMs          = 0;
            private long sweepIntervalMs = 30_000;

            Builder<K, V> capacity(int v)          { capacity = v;        return this; }
            Builder<K, V> ttlMs(long v)            { ttlMs = v;           return this; }
            Builder<K, V> ttlSeconds(long s)       { ttlMs = s * 1000L;   return this; }
            Builder<K, V> sweepIntervalMs(long v)  { sweepIntervalMs = v; return this; }
            LRUCache<K, V> build() { return new LRUCache<>(capacity, ttlMs, sweepIntervalMs); }
        }
    }

    // =========================================================================
    // 4. Tiny test runner  — no JUnit needed
    // =========================================================================
    static int passed = 0, failed = 0;

    static void test(String name, Runnable body) {
        try {
            body.run();
            System.out.printf("  PASS  %s%n", name);
            passed++;
        } catch (AssertionError | Exception e) {
            System.out.printf("  FAIL  %s  →  %s%n", name, e.getMessage());
            failed++;
        }
    }

    static void assertEqual(Object expected, Object actual, String msg) {
        if (!Objects.equals(expected, actual))
            throw new AssertionError(msg + " — expected: " + expected + ", got: " + actual);
    }
    static void assertNull(Object v, String msg) {
        if (v != null) throw new AssertionError(msg + " — expected null, got: " + v);
    }
    static void assertNotNull(Object v, String msg) {
        if (v == null) throw new AssertionError(msg + " — expected non-null");
    }
    static void assertTrue(boolean cond, String msg) {
        if (!cond) throw new AssertionError(msg);
    }

    // =========================================================================
    // 5. Tests
    // =========================================================================
    static void runTests() {
        System.out.println("\n── Basic correctness ────────────────────────────────");

        test("get returns null on miss", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(3).build();
            assertNull(c.get("x"), "miss should return null");
        });

        test("put then get round-trip", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(3).build();
            c.put("a", 42);
            assertEqual(42, c.get("a"), "get after put");
        });

        test("put updates existing value", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(3).build();
            c.put("a", 1); c.put("a", 99);
            assertEqual(99, c.get("a"), "updated value");
            assertEqual(1, c.size(), "size should stay 1");
        });

        System.out.println("\n── Eviction order ───────────────────────────────────");

        test("evicts least recently used on overflow", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(3).build();
            c.put("a", 1); c.put("b", 2); c.put("c", 3);
            c.get("a");          // promote a → b is now LRU
            c.put("d", 4);       // should evict b
            assertNull   (c.get("b"), "b should be evicted");
            assertNotNull(c.get("a"), "a should survive");
            assertNotNull(c.get("c"), "c should survive");
            assertNotNull(c.get("d"), "d should survive");
        });

        test("update existing key promotes it to MRU", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(2).build();
            c.put("a", 1); c.put("b", 2);
            c.put("a", 10);      // promote a → b becomes LRU
            c.put("c", 3);       // evicts b
            assertNull(c.get("b"), "b should be evicted");
            assertEqual(10, c.get("a"), "a value updated");
        });

        test("eviction count tracked correctly", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(2).build();
            c.put("a", 1); c.put("b", 2); c.put("c", 3);
            assertEqual(1L, c.stats().getEvictions(), "one eviction");
        });

        System.out.println("\n── TTL expiry ───────────────────────────────────────");

        test("entry returns null after TTL elapsed", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(5).ttlMs(80).build();
            c.put("x", 7);
            assertEqual(7, c.get("x"), "should be present before TTL");
            sleep(160);
            assertNull(c.get("x"), "should be null after TTL");
        });

        test("entry still accessible within TTL", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(5).ttlMs(500).build();
            c.put("y", 3);
            sleep(100);
            assertEqual(3, c.get("y"), "still within TTL");
        });

        System.out.println("\n── Stats ────────────────────────────────────────────");

        test("hit rate calculation", () -> {
            var c = LRUCache.<String, Integer>builder().capacity(5).build();
            c.put("k", 1);
            c.get("k"); c.get("k");   // 2 hits
            c.get("nope");            // 1 miss
            assertEqual(2L, c.stats().getHits(),   "hits");
            assertEqual(1L, c.stats().getMisses(),  "misses");
            assertTrue(c.stats().hitRate() > 0.66, "hit rate > 66%");
        });

        System.out.println("\n── Concurrency ──────────────────────────────────────");

        test("8 threads concurrent put/get — no corruption", () -> {
            int threads = 8, ops = 2000;
            var c = 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 < ops; i++) {
                            int key = (tid * ops + i) % 150;
                            c.put(key, key * 2);
                            Integer v = c.get(key);
                            if (v != null && v % 2 != 0) errors.incrementAndGet();
                        }
                    } catch (Exception e) { errors.incrementAndGet(); }
                    finally { done.countDown(); }
                });
            }
            start.countDown();
            try { done.await(8, TimeUnit.SECONDS); } catch (InterruptedException ignored) {}
            pool.shutdown();
            assertEqual(0, errors.get(), "zero corruption errors");
        });
    }

    static void sleep(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException ignored) {}
    }

    // =========================================================================
    // 6. main  — run tests then show a live demo
    // =========================================================================
    public static void main(String[] args) {
        System.out.println("╔══════════════════════════════════════════╗");
        System.out.println("║   LRU Cache — Java, no dependencies      ║");
        System.out.println("╚══════════════════════════════════════════╝");

        runTests();

        System.out.println("\n── Results ──────────────────────────────────────────");
        System.out.printf("  %d passed  /  %d failed%n%n", passed, failed);

        // ── Live demo ──────────────────────────────────────────────────────
        System.out.println("── Live demo (capacity=3, TTL=300ms) ────────────────");
        var cache = LRUCache.<String, String>builder()
                .capacity(3).ttlMs(300).sweepIntervalMs(200).build();

        String[] keys   = {"alice", "bob", "carol"};
        String[] values = {"eng",   "pm",  "design"};
        for (int i = 0; i < 3; i++) {
            cache.put(keys[i], values[i]);
            System.out.printf("  put(%-6s) → size=%d%n", keys[i], cache.size());
        }

        System.out.println("  get(alice) → " + cache.get("alice"));  // promotes alice
        cache.put("dave", "marketing");                               // evicts bob (LRU)
        System.out.println("  put(dave)  → bob evicted? " + (cache.get("bob") == null ? "yes" : "no"));

        sleep(400);
        System.out.println("  After 400ms TTL expiry:");
        System.out.println("    get(alice) → " + cache.get("alice"));
        System.out.println("    get(dave)  → " + cache.get("dave"));
        System.out.println("  " + cache.stats());

        cache.shutdown();
    }
}