import java.util.ArrayDeque;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.LongSupplier;

/**
 * The version to write on a whiteboard: one file, no dependencies, two algorithms, per-key limiting.
 * Run it with:  java InterviewRateLimiter.java
 * Companion to https://ankurm.com/ - Low-Level Design: Rate Limiter in Java.
 */
public class InterviewRateLimiter {

    interface RateLimiter {
        boolean tryAcquire(String key);
    }

    /** Token bucket: burst up to capacity, then refillPerSecond sustained. Per-key state in a map. */
    static final class TokenBucket implements RateLimiter {
        private static final class Bucket {
            double tokens;
            long last;
        }

        private final int capacity;
        private final double refillPerNano;
        private final LongSupplier clock;
        private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();

        TokenBucket(int capacity, double refillPerSecond, LongSupplier clock) {
            this.capacity = capacity;
            this.refillPerNano = refillPerSecond / 1e9;
            this.clock = clock;
        }

        @Override
        public boolean tryAcquire(String key) {
            Bucket b = buckets.computeIfAbsent(key, k -> {
                Bucket nb = new Bucket();
                nb.tokens = capacity;
                nb.last = clock.getAsLong();
                return nb;
            });
            synchronized (b) { // lock per key, not one global lock
                long now = clock.getAsLong();
                b.tokens = Math.min(capacity, b.tokens + (now - b.last) * refillPerNano);
                b.last = now;
                if (b.tokens < 1) return false;
                b.tokens -= 1;
                return true;
            }
        }
    }

    /** Sliding window log: exact, O(limit) memory per key. */
    static final class SlidingWindowLog implements RateLimiter {
        private final int limit;
        private final long windowNanos;
        private final LongSupplier clock;
        private final ConcurrentHashMap<String, ArrayDeque<Long>> logs = new ConcurrentHashMap<>();

        SlidingWindowLog(int limit, long windowNanos, LongSupplier clock) {
            this.limit = limit;
            this.windowNanos = windowNanos;
            this.clock = clock;
        }

        @Override
        public boolean tryAcquire(String key) {
            ArrayDeque<Long> log = logs.computeIfAbsent(key, k -> new ArrayDeque<>());
            synchronized (log) {
                long now = clock.getAsLong();
                while (!log.isEmpty() && log.peekFirst() <= now - windowNanos) log.pollFirst();
                if (log.size() >= limit) return false;
                log.addLast(now);
                return true;
            }
        }
    }

    public static void main(String[] args) {
        long[] now = {0};              // a fake clock: we move it by hand
        LongSupplier clock = () -> now[0];

        RateLimiter bucket = new TokenBucket(3, 1.0, clock);   // burst 3, then 1 per second
        System.out.println("TokenBucket(capacity=3, 1 token/s)");
        for (int i = 1; i <= 5; i++) System.out.println("  t=0s   request " + i + " -> " + bucket.tryAcquire("alice"));
        now[0] = 2_000_000_000L;
        for (int i = 1; i <= 3; i++) System.out.println("  t=2s   request " + i + " -> " + bucket.tryAcquire("alice"));
        System.out.println("  t=2s   other key  -> " + bucket.tryAcquire("bob"));

        now[0] = 0;
        RateLimiter log = new SlidingWindowLog(2, 10_000_000_000L, clock);  // 2 per 10 s
        System.out.println("SlidingWindowLog(limit=2, window=10s)");
        for (long t : new long[]{0, 4, 8, 11, 14}) {
            now[0] = t * 1_000_000_000L;
            System.out.println("  t=" + t + "s  -> " + log.tryAcquire("alice"));
        }
    }
}
