/**
 * Token Bucket: imagine a bucket that fills with tokens over time.
 * Each request consumes one token. If the bucket is empty, the request is rejected.
 * Allows short bursts (up to capacity) while enforcing a steady long-term rate.
 */
public class TokenBucketRateLimiter {
    private final int capacity;       // Max tokens the bucket can hold (burst limit)
    private final double refillPerMs; // Tokens added per millisecond
    private final Map<String, Bucket> buckets = new HashMap<>();

    public TokenBucketRateLimiter(int capacity, int refillPerSecond) {
        this.capacity = capacity;
        this.refillPerMs = refillPerSecond / 1000.0;
    }

    /** Returns true if the request is allowed, false if rate-limited */
    public boolean isAllowed(String clientId) {
        Bucket bucket = buckets.computeIfAbsent(clientId, k -> new Bucket(capacity));
        bucket.refill();
        return bucket.tryConsume();
    }

    private class Bucket {
        private double tokens;
        private long lastRefillTime = System.currentTimeMillis();

        Bucket(int initialTokens) { this.tokens = initialTokens; }

        /** Add tokens based on how much time has passed since the last refill */
        void refill() {
            long now = System.currentTimeMillis();
            double tokensToAdd = (now - lastRefillTime) * refillPerMs;
            tokens = Math.min(capacity, tokens + tokensToAdd);
            lastRefillTime = now;
        }

        boolean tryConsume() {
            if (tokens >= 1.0) {
                tokens -= 1.0;
                return true;
            }
            return false;
        }
    }
}

/**
 * Sliding Window: tracks the timestamp of every recent request.
 * Only counts requests that fall within the last windowMs milliseconds.
 * Most accurate approach with no boundary artifacts, but uses more memory.
 */
public class SlidingWindowRateLimiter {
    private final int maxRequests;
    private final long windowMs;
    private final Map<String, Queue<Long>> requestLogs = new HashMap<>();

    public SlidingWindowRateLimiter(int maxRequests, long windowMs) {
        this.maxRequests = maxRequests;
        this.windowMs = windowMs;
    }

    public synchronized boolean isAllowed(String clientId) {
        long now = System.currentTimeMillis();
        Queue<Long> timestamps = requestLogs.computeIfAbsent(clientId, k -> new LinkedList<>());

        // Drop timestamps that have slid outside the current window
        while (!timestamps.isEmpty() && now - timestamps.peek() > windowMs) {
            timestamps.poll();
        }

        if (timestamps.size() < maxRequests) {
            timestamps.offer(now);
            return true;
        }
        return false;
    }
}

/**
 * Fixed Window: counts requests within a fixed time slot (e.g., the current minute).
 * Simplest to implement. Trade-off: a burst at a window boundary can send
 * up to 2× the limit in a short period.
 */
public class FixedWindowRateLimiter {
    private final int maxRequests;
    private final long windowMs;
    private final Map<String, Window> windows = new HashMap<>();

    public FixedWindowRateLimiter(int maxRequests, long windowMs) {
        this.maxRequests = maxRequests;
        this.windowMs = windowMs;
    }

    public synchronized boolean isAllowed(String clientId) {
        long currentSlot = System.currentTimeMillis() / windowMs;
        Window window = windows.computeIfAbsent(clientId, k -> new Window(currentSlot));

        // New time slot, reset the counter
        if (window.slot != currentSlot) {
            window.slot = currentSlot;
            window.count = 0;
        }

        if (window.count < maxRequests) {
            window.count++;
            return true;
        }
        return false;
    }

    private static class Window {
        long slot;
        int count = 0;
        Window(long slot) { this.slot = slot; }
    }
}

/** An API service that enforces per-client rate limits using Token Bucket */
public class RateLimitedApiService {
    private final TokenBucketRateLimiter rateLimiter;

    public RateLimitedApiService(int requestsPerSecond) {
        // Allow bursts up to 5 requests, then refill at the specified rate
        this.rateLimiter = new TokenBucketRateLimiter(5, requestsPerSecond);
    }

    public ApiResponse handleRequest(String clientId, String operation) {
        if (!rateLimiter.isAllowed(clientId)) {
            System.out.println("  [" + clientId + "] THROTTLED: " + operation);
            return new ApiResponse(429, "Rate limit exceeded. Slow down your requests.");
        }
        System.out.println("  [" + clientId + "] OK: " + operation);
        return new ApiResponse(200, "Success");
    }
}

// Simple data class for the API response
public record ApiResponse(int status, String message) {}

public class Main {
    public static void main(String[] args) throws InterruptedException {
        // 2 requests/sec with a burst capacity of 5
        RateLimitedApiService service = new RateLimitedApiService(2);

        // Happy path: spread-out requests stay within the rate limit
        System.out.println("=== Normal usage ===");
        service.handleRequest("client-A", "GET /products");
        Thread.sleep(600);
        service.handleRequest("client-A", "GET /orders");
        Thread.sleep(600);
        service.handleRequest("client-A", "GET /profile");

        System.out.println();

        // Burst: 8 requests in quick succession exhaust the bucket and trigger throttling
        System.out.println("=== Burst traffic ===");
        for (int i = 1; i <= 8; i++) {
            service.handleRequest("client-B", "GET /products (request " + i + ")");
        }
    }
}

=== Normal usage ===
  [client-A] OK: GET /products
  [client-A] OK: GET /orders
  [client-A] OK: GET /profile

=== Burst traffic ===
  [client-B] OK: GET /products (request 1)
  [client-B] OK: GET /products (request 2)
  [client-B] OK: GET /products (request 3)
  [client-B] OK: GET /products (request 4)
  [client-B] OK: GET /products (request 5)
  [client-B] THROTTLED: GET /products (request 6)
  [client-B] THROTTLED: GET /products (request 7)
  [client-B] THROTTLED: GET /products (request 8)