3. Rate Limiter Intermediate → Advanced+Distributed

interface RateLimitAlgorithm {
  RateLimitResult allowRequest(String clientKey, long nowMs);
}

class RateLimiter {
  RateLimitResult check(String clientId, String endpoint, long nowMs);
}

class RateLimitResult {
  boolean allowed;
  long    remaining;
  long    retryAfterMs;   // 0 if allowed
}

interface RateLimitAlgorithm {
  RateLimitResult allowRequest(String clientKey, long nowMs);
}

class RateLimiter {
  RateLimitResult check(String clientId, String endpoint, long nowMs) { throw new UnsupportedOperationException(); }
}

class RateLimitResult {
  boolean allowed;
  long remaining;
  long retryAfterMs;   // 0 if allowed
}

class RateLimitAlgorithm {
public:
  virtual RateLimitResult allowRequest(const std::string& clientKey, long nowMs) = 0;
};

class RateLimiter {
public:
  RateLimitResult check(const std::string& clientId, const std::string& endpoint, long nowMs);
};

struct RateLimitResult {
  bool allowed;
  long remaining;
  long retryAfterMs;   // 0 if allowed
};

class RateLimitAlgorithm {
  allowRequest(clientKey, nowMs) { throw new Error('not implemented'); }
}

class RateLimiter {
  check(clientId, endpoint, nowMs) { throw new Error('not implemented'); }
}

class RateLimitResult {
  constructor(allowed, remaining, retryAfterMs) {
    this.allowed = allowed;
    this.remaining = remaining;
    this.retryAfterMs = retryAfterMs;   // 0 if allowed
  }
}

interface RateLimitAlgorithm {
  allowRequest(clientKey: string, nowMs: number): RateLimitResult;
}

class RateLimiter {
  check(clientId: string, endpoint: string, nowMs: number): RateLimitResult { throw new Error('not implemented'); }
}

class RateLimitResult {
  allowed: boolean;
  remaining: number;
  retryAfterMs: number;   // 0 if allowed
}

allowRequest(key, now):
  bucket = store.getOrCreate(key, capacity)
  lock(bucket):
    elapsed = now - bucket.lastRefillTime
    bucket.tokens = min(capacity, bucket.tokens + elapsed * refillRatePerMs)
    bucket.lastRefillTime = now
    if bucket.tokens >= 1:
      bucket.tokens -= 1
      return ALLOW(remaining = floor(bucket.tokens))
    else:
      deficit = 1 - bucket.tokens
      return DENY(retryAfterMs = deficit / refillRatePerMs)

RateLimitResult allowRequest(String key, long now) {
  Bucket bucket = store.getOrCreate(key, capacity);
  synchronized (bucket) {
    long elapsed = now - bucket.lastRefillTime;
    bucket.tokens = Math.min(capacity, bucket.tokens + elapsed * refillRatePerMs);
    bucket.lastRefillTime = now;
    if (bucket.tokens >= 1) {
      bucket.tokens -= 1;
      return ALLOW(Math.floor(bucket.tokens));
    } else {
      double deficit = 1 - bucket.tokens;
      return DENY(deficit / refillRatePerMs);
    }
  }
}

RateLimitResult allowRequest(const std::string& key, long now) {
  auto bucket = store.getOrCreate(key, capacity);
  std::lock_guard<std::mutex> lock(bucket->mutex);
  long elapsed = now - bucket->lastRefillTime;
  bucket->tokens = std::min(capacity, bucket->tokens + elapsed * refillRatePerMs);
  bucket->lastRefillTime = now;
  if (bucket->tokens >= 1) {
    bucket->tokens -= 1;
    return ALLOW(/* remaining = */ std::floor(bucket->tokens));
  } else {
    double deficit = 1 - bucket->tokens;
    return DENY(/* retryAfterMs = */ deficit / refillRatePerMs);
  }
}

allowRequest(key, now) {
  const bucket = store.getOrCreate(key, capacity);
  return withLock(bucket, () => {
    const elapsed = now - bucket.lastRefillTime;
    bucket.tokens = Math.min(capacity, bucket.tokens + elapsed * refillRatePerMs);
    bucket.lastRefillTime = now;
    if (bucket.tokens >= 1) {
      bucket.tokens -= 1;
      return ALLOW(Math.floor(bucket.tokens));
    } else {
      const deficit = 1 - bucket.tokens;
      return DENY(deficit / refillRatePerMs);
    }
  });
}

allowRequest(key: string, now: number): RateLimitResult {
  const bucket = store.getOrCreate(key, capacity);
  return withLock(bucket, (): RateLimitResult => {
    const elapsed = now - bucket.lastRefillTime;
    bucket.tokens = Math.min(capacity, bucket.tokens + elapsed * refillRatePerMs);
    bucket.lastRefillTime = now;
    if (bucket.tokens >= 1) {
      bucket.tokens -= 1;
      return ALLOW(Math.floor(bucket.tokens));
    } else {
      const deficit = 1 - bucket.tokens;
      return DENY(deficit / refillRatePerMs);
    }
  });
}

// Rate Limiter - full LLD implementation (single-file demo).
// Difficulty badge is "Intermediate -> Advanced+Distributed" - it does NOT explicitly say
// "Concurrency", so per convention this stays single-threaded/simple (no locks), even
// though a production system would eventually need per-key locking or a distributed store.
import java.util.*;

public class p3 {

    // ---------- RateLimitResult (pure data) ----------
    static class RateLimitResult {
        final boolean allowed;
        final long remaining;
        final long retryAfterMs; // 0 if allowed

        RateLimitResult(boolean allowed, long remaining, long retryAfterMs) {
            this.allowed = allowed;
            this.remaining = remaining;
            this.retryAfterMs = retryAfterMs;
        }

        static RateLimitResult allow(long remaining) { return new RateLimitResult(true, remaining, 0); }
        static RateLimitResult deny(long retryAfterMs) { return new RateLimitResult(false, 0, retryAfterMs); }

        public String toString() {
            return "RateLimitResult{allowed=" + allowed + ", remaining=" + remaining + ", retryAfterMs=" + retryAfterMs + "}";
        }
    }

    // ---------- RateLimitConfig (pure data) ----------
    enum AlgorithmType { TOKEN_BUCKET, SLIDING_WINDOW, FIXED_WINDOW }

    static class RateLimitConfig {
        final long capacity;      // max tokens / max requests per window
        final long windowMs;      // window size in ms (or refill window for token bucket)
        final AlgorithmType algorithmType;

        RateLimitConfig(long capacity, long windowMs, AlgorithmType algorithmType) {
            this.capacity = capacity;
            this.windowMs = windowMs;
            this.algorithmType = algorithmType;
        }
    }

    // ---------- RateLimitAlgorithm (interface) ----------
    interface RateLimitAlgorithm {
        RateLimitResult allowRequest(String clientKey, long nowMs);
    }

    // Each algorithm owns its own per-client state map, since the state shape genuinely
    // differs (a counter vs. a timestamp deque vs. two rolling counters) - forcing a shared
    // generic "Bucket" class would either bloat it or leak abstraction.
    static class TokenBucketLimiter implements RateLimitAlgorithm {
        private static class Bucket {
            double tokens;
            long lastRefillTime;
        }

        private final long capacity;
        private final double refillRatePerMs; // tokens added per millisecond
        private final Map<String, Bucket> buckets = new HashMap<>();

        TokenBucketLimiter(RateLimitConfig config) {
            this.capacity = config.capacity;
            this.refillRatePerMs = (double) config.capacity / config.windowMs;
        }

        public RateLimitResult allowRequest(String clientKey, long nowMs) {
            Bucket bucket = buckets.computeIfAbsent(clientKey, k -> {
                Bucket b = new Bucket();
                b.tokens = capacity;
                b.lastRefillTime = nowMs;
                return b;
            });
            long elapsed = nowMs - bucket.lastRefillTime;
            bucket.tokens = Math.min(capacity, bucket.tokens + elapsed * refillRatePerMs);
            bucket.lastRefillTime = nowMs;
            if (bucket.tokens >= 1) {
                bucket.tokens -= 1;
                return RateLimitResult.allow((long) Math.floor(bucket.tokens));
            }
            double deficit = 1 - bucket.tokens;
            long retryAfterMs = (long) Math.ceil(deficit / refillRatePerMs);
            return RateLimitResult.deny(retryAfterMs);
        }
    }

    // Sliding window: keeps an exact deque of recent request timestamps per client and
    // counts how many fall within the last windowMs - more accurate than fixed window at
    // the cost of memory proportional to request rate.
    static class SlidingWindowLimiter implements RateLimitAlgorithm {
        private final long capacity;
        private final long windowMs;
        private final Map<String, Deque<Long>> history = new HashMap<>();

        SlidingWindowLimiter(RateLimitConfig config) {
            this.capacity = config.capacity;
            this.windowMs = config.windowMs;
        }

        public RateLimitResult allowRequest(String clientKey, long nowMs) {
            Deque<Long> timestamps = history.computeIfAbsent(clientKey, k -> new ArrayDeque<>());
            long windowStart = nowMs - windowMs;
            while (!timestamps.isEmpty() && timestamps.peekFirst() <= windowStart) {
                timestamps.pollFirst();
            }
            if (timestamps.size() < capacity) {
                timestamps.addLast(nowMs);
                return RateLimitResult.allow(capacity - timestamps.size());
            }
            long retryAfterMs = timestamps.peekFirst() + windowMs - nowMs;
            return RateLimitResult.deny(Math.max(0, retryAfterMs));
        }
    }

    // Fixed window: counts requests in discrete, non-overlapping windows - cheap (one
    // counter per client) but allows bursts at window boundaries.
    static class FixedWindowLimiter implements RateLimitAlgorithm {
        private static class WindowCounter {
            long windowStart;
            long count;
        }

        private final long capacity;
        private final long windowMs;
        private final Map<String, WindowCounter> counters = new HashMap<>();

        FixedWindowLimiter(RateLimitConfig config) {
            this.capacity = config.capacity;
            this.windowMs = config.windowMs;
        }

        public RateLimitResult allowRequest(String clientKey, long nowMs) {
            WindowCounter counter = counters.computeIfAbsent(clientKey, k -> {
                WindowCounter c = new WindowCounter();
                c.windowStart = nowMs;
                c.count = 0;
                return c;
            });
            if (nowMs - counter.windowStart >= windowMs) {
                counter.windowStart = nowMs;
                counter.count = 0;
            }
            if (counter.count < capacity) {
                counter.count++;
                return RateLimitResult.allow(capacity - counter.count);
            }
            long retryAfterMs = counter.windowStart + windowMs - nowMs;
            return RateLimitResult.deny(Math.max(0, retryAfterMs));
        }
    }

    // ---------- RateLimiterFactory ----------
    // Resolves "which algorithm for which endpoint" - kept out of both the facade and the
    // algorithms themselves so that mapping logic has exactly one home.
    static class RateLimiterFactory {
        private final Map<String, RateLimitConfig> configsByEndpoint;
        private final Map<String, RateLimitAlgorithm> instancesByEndpoint = new HashMap<>();

        RateLimiterFactory(Map<String, RateLimitConfig> configsByEndpoint) {
            this.configsByEndpoint = configsByEndpoint;
        }

        RateLimitAlgorithm getLimiter(String endpoint) {
            return instancesByEndpoint.computeIfAbsent(endpoint, ep -> {
                RateLimitConfig config = configsByEndpoint.get(ep);
                if (config == null) throw new IllegalArgumentException("No config for endpoint: " + ep);
                switch (config.algorithmType) {
                    case TOKEN_BUCKET: return new TokenBucketLimiter(config);
                    case SLIDING_WINDOW: return new SlidingWindowLimiter(config);
                    case FIXED_WINDOW: return new FixedWindowLimiter(config);
                    default: throw new IllegalStateException("Unknown algorithm type");
                }
            });
        }
    }

    // ---------- RateLimiter (facade) ----------
    static class RateLimiter {
        private final RateLimiterFactory factory; // injected interface-like dependency

        RateLimiter(RateLimiterFactory factory) {
            this.factory = factory;
        }

        RateLimitResult check(String clientId, String endpoint, long nowMs) {
            RateLimitAlgorithm algorithm = factory.getLimiter(endpoint);
            String clientKey = endpoint + ":" + clientId; // scope quota per endpoint+client
            return algorithm.allowRequest(clientKey, nowMs);
        }
    }

    // ---------- Demo ----------
    public static void main(String[] args) {
        Map<String, RateLimitConfig> configs = new HashMap<>();
        configs.put("/api/login", new RateLimitConfig(3, 1000, AlgorithmType.TOKEN_BUCKET));
        configs.put("/api/search", new RateLimitConfig(2, 1000, AlgorithmType.FIXED_WINDOW));

        RateLimiterFactory factory = new RateLimiterFactory(configs);
        RateLimiter limiter = new RateLimiter(factory);

        long t = 0;
        for (int i = 0; i < 5; i++) {
            RateLimitResult result = limiter.check("clientA", "/api/login", t);
            System.out.println("t=" + t + " login attempt " + (i + 1) + " -> " + result);
            t += 100; // 100ms between requests, faster than refill can keep up
        }

        System.out.println();
        long t2 = 0;
        for (int i = 0; i < 3; i++) {
            RateLimitResult result = limiter.check("clientB", "/api/search", t2);
            System.out.println("t=" + t2 + " search attempt " + (i + 1) + " -> " + result);
        }
    }
}

// Rate Limiter - full LLD implementation (single-file demo).
// Difficulty badge is "Intermediate -> Advanced+Distributed" - it does NOT explicitly say
// "Concurrency", so per convention this stays single-threaded/simple (no mutexes), even
// though a production system would eventually need per-key locking or a distributed store.
#include <iostream>
#include <unordered_map>
#include <deque>
#include <string>
#include <memory>
#include <cmath>
#include <stdexcept>

// ---------- RateLimitResult (pure data) ----------
struct RateLimitResult {
    bool allowed;
    long long remaining;
    long long retryAfterMs; // 0 if allowed

    static RateLimitResult allow(long long remaining) { return {true, remaining, 0}; }
    static RateLimitResult deny(long long retryAfterMs) { return {false, 0, retryAfterMs}; }
};

std::ostream& operator<<(std::ostream& os, const RateLimitResult& r) {
    os << "RateLimitResult{allowed=" << (r.allowed ? "true" : "false")
       << ", remaining=" << r.remaining << ", retryAfterMs=" << r.retryAfterMs << "}";
    return os;
}

// ---------- RateLimitConfig (pure data) ----------
enum class AlgorithmType { TOKEN_BUCKET, SLIDING_WINDOW, FIXED_WINDOW };

struct RateLimitConfig {
    long long capacity;   // max tokens / max requests per window
    long long windowMs;   // window size in ms (or refill window for token bucket)
    AlgorithmType algorithmType;
};

// ---------- RateLimitAlgorithm (interface) ----------
class RateLimitAlgorithm {
public:
    virtual ~RateLimitAlgorithm() = default;
    virtual RateLimitResult allowRequest(const std::string& clientKey, long long nowMs) = 0;
};

// Each algorithm owns its own per-client state map, since the state shape genuinely
// differs (a counter vs. a timestamp deque vs. two rolling counters) - forcing a shared
// generic "Bucket" class would either bloat it or leak abstraction.
class TokenBucketLimiter : public RateLimitAlgorithm {
public:
    explicit TokenBucketLimiter(const RateLimitConfig& config)
        : capacity(config.capacity), refillRatePerMs(static_cast<double>(config.capacity) / config.windowMs) {}

    RateLimitResult allowRequest(const std::string& clientKey, long long nowMs) override {
        Bucket& bucket = buckets[clientKey];
        if (!bucket.initialized) {
            bucket.tokens = static_cast<double>(capacity);
            bucket.lastRefillTime = nowMs;
            bucket.initialized = true;
        }
        long long elapsed = nowMs - bucket.lastRefillTime;
        bucket.tokens = std::min(static_cast<double>(capacity), bucket.tokens + elapsed * refillRatePerMs);
        bucket.lastRefillTime = nowMs;
        if (bucket.tokens >= 1.0) {
            bucket.tokens -= 1.0;
            return RateLimitResult::allow(static_cast<long long>(std::floor(bucket.tokens)));
        }
        double deficit = 1.0 - bucket.tokens;
        long long retryAfterMs = static_cast<long long>(std::ceil(deficit / refillRatePerMs));
        return RateLimitResult::deny(retryAfterMs);
    }

private:
    struct Bucket {
        double tokens = 0;
        long long lastRefillTime = 0;
        bool initialized = false;
    };
    long long capacity;
    double refillRatePerMs;
    std::unordered_map<std::string, Bucket> buckets;
};

// Sliding window: keeps an exact deque of recent request timestamps per client and
// counts how many fall within the last windowMs - more accurate than fixed window at
// the cost of memory proportional to request rate.
class SlidingWindowLimiter : public RateLimitAlgorithm {
public:
    explicit SlidingWindowLimiter(const RateLimitConfig& config)
        : capacity(config.capacity), windowMs(config.windowMs) {}

    RateLimitResult allowRequest(const std::string& clientKey, long long nowMs) override {
        std::deque<long long>& timestamps = history[clientKey];
        long long windowStart = nowMs - windowMs;
        while (!timestamps.empty() && timestamps.front() <= windowStart) {
            timestamps.pop_front();
        }
        if (static_cast<long long>(timestamps.size()) < capacity) {
            timestamps.push_back(nowMs);
            return RateLimitResult::allow(capacity - static_cast<long long>(timestamps.size()));
        }
        long long retryAfterMs = timestamps.front() + windowMs - nowMs;
        return RateLimitResult::deny(std::max<long long>(0, retryAfterMs));
    }

private:
    long long capacity;
    long long windowMs;
    std::unordered_map<std::string, std::deque<long long>> history;
};

// Fixed window: counts requests in discrete, non-overlapping windows - cheap (one
// counter per client) but allows bursts at window boundaries.
class FixedWindowLimiter : public RateLimitAlgorithm {
public:
    explicit FixedWindowLimiter(const RateLimitConfig& config)
        : capacity(config.capacity), windowMs(config.windowMs) {}

    RateLimitResult allowRequest(const std::string& clientKey, long long nowMs) override {
        WindowCounter& counter = counters[clientKey];
        if (!counter.initialized) {
            counter.windowStart = nowMs;
            counter.count = 0;
            counter.initialized = true;
        }
        if (nowMs - counter.windowStart >= windowMs) {
            counter.windowStart = nowMs;
            counter.count = 0;
        }
        if (counter.count < capacity) {
            counter.count++;
            return RateLimitResult::allow(capacity - counter.count);
        }
        long long retryAfterMs = counter.windowStart + windowMs - nowMs;
        return RateLimitResult::deny(std::max<long long>(0, retryAfterMs));
    }

private:
    struct WindowCounter {
        long long windowStart = 0;
        long long count = 0;
        bool initialized = false;
    };
    long long capacity;
    long long windowMs;
    std::unordered_map<std::string, WindowCounter> counters;
};

// ---------- RateLimiterFactory ----------
// Resolves "which algorithm for which endpoint" - kept out of both the facade and the
// algorithms themselves so that mapping logic has exactly one home.
class RateLimiterFactory {
public:
    explicit RateLimiterFactory(std::unordered_map<std::string, RateLimitConfig> configsByEndpoint)
        : configsByEndpoint(std::move(configsByEndpoint)) {}

    RateLimitAlgorithm* getLimiter(const std::string& endpoint) {
        auto it = instancesByEndpoint.find(endpoint);
        if (it != instancesByEndpoint.end()) return it->second.get();

        auto configIt = configsByEndpoint.find(endpoint);
        if (configIt == configsByEndpoint.end()) throw std::invalid_argument("No config for endpoint: " + endpoint);
        const RateLimitConfig& config = configIt->second;

        std::unique_ptr<RateLimitAlgorithm> algorithm;
        switch (config.algorithmType) {
            case AlgorithmType::TOKEN_BUCKET: algorithm = std::make_unique<TokenBucketLimiter>(config); break;
            case AlgorithmType::SLIDING_WINDOW: algorithm = std::make_unique<SlidingWindowLimiter>(config); break;
            case AlgorithmType::FIXED_WINDOW: algorithm = std::make_unique<FixedWindowLimiter>(config); break;
        }
        RateLimitAlgorithm* raw = algorithm.get();
        instancesByEndpoint[endpoint] = std::move(algorithm);
        return raw;
    }

private:
    std::unordered_map<std::string, RateLimitConfig> configsByEndpoint;
    std::unordered_map<std::string, std::unique_ptr<RateLimitAlgorithm>> instancesByEndpoint;
};

// ---------- RateLimiter (facade) ----------
class RateLimiter {
public:
    explicit RateLimiter(RateLimiterFactory* factory) : factory(factory) {}

    RateLimitResult check(const std::string& clientId, const std::string& endpoint, long long nowMs) {
        RateLimitAlgorithm* algorithm = factory->getLimiter(endpoint);
        std::string clientKey = endpoint + ":" + clientId; // scope quota per endpoint+client
        return algorithm->allowRequest(clientKey, nowMs);
    }

private:
    RateLimiterFactory* factory; // injected dependency, not owned
};

// ---------- Demo ----------
int main() {
    std::unordered_map<std::string, RateLimitConfig> configs;
    configs["/api/login"] = {3, 1000, AlgorithmType::TOKEN_BUCKET};
    configs["/api/search"] = {2, 1000, AlgorithmType::FIXED_WINDOW};

    RateLimiterFactory factory(configs);
    RateLimiter limiter(&factory);

    long long t = 0;
    for (int i = 0; i < 5; i++) {
        RateLimitResult result = limiter.check("clientA", "/api/login", t);
        std::cout << "t=" << t << " login attempt " << (i + 1) << " -> " << result << "\n";
        t += 100; // 100ms between requests, faster than refill can keep up
    }

    std::cout << "\n";
    long long t2 = 0;
    for (int i = 0; i < 3; i++) {
        RateLimitResult result = limiter.check("clientB", "/api/search", t2);
        std::cout << "t=" << t2 << " search attempt " << (i + 1) << " -> " << result << "\n";
    }
    return 0;
}

// Rate Limiter - full LLD implementation (single-file demo).
// Difficulty badge is "Intermediate -> Advanced+Distributed" - it does NOT explicitly say
// "Concurrency", so per convention this stays single-threaded/simple (no locks), even
// though a production system would eventually need per-key locking or a distributed store.

// ---------- RateLimitResult (pure data) ----------
class RateLimitResult {
  constructor(allowed, remaining, retryAfterMs) {
    this.allowed = allowed;
    this.remaining = remaining;
    this.retryAfterMs = retryAfterMs; // 0 if allowed
  }
  static allow(remaining) { return new RateLimitResult(true, remaining, 0); }
  static deny(retryAfterMs) { return new RateLimitResult(false, 0, retryAfterMs); }
}

// ---------- RateLimitConfig (pure data) ----------
const AlgorithmType = { TOKEN_BUCKET: "TOKEN_BUCKET", SLIDING_WINDOW: "SLIDING_WINDOW", FIXED_WINDOW: "FIXED_WINDOW" };

class RateLimitConfig {
  constructor(capacity, windowMs, algorithmType) {
    this.capacity = capacity;   // max tokens / max requests per window
    this.windowMs = windowMs;   // window size in ms (or refill window for token bucket)
    this.algorithmType = algorithmType;
  }
}

// ---------- RateLimitAlgorithm (interface) ----------
class RateLimitAlgorithm {
  allowRequest(_clientKey, _nowMs) {
    throw new Error("allowRequest() must be implemented");
  }
}

// Each algorithm owns its own per-client state map, since the state shape genuinely
// differs (a counter vs. a timestamp deque vs. two rolling counters) - forcing a shared
// generic "Bucket" class would either bloat it or leak abstraction.
class TokenBucketLimiter extends RateLimitAlgorithm {
  constructor(config) {
    super();
    this.capacity = config.capacity;
    this.refillRatePerMs = config.capacity / config.windowMs; // tokens added per ms
    this.buckets = new Map(); // clientKey -> { tokens, lastRefillTime }
  }

  allowRequest(clientKey, nowMs) {
    let bucket = this.buckets.get(clientKey);
    if (!bucket) {
      bucket = { tokens: this.capacity, lastRefillTime: nowMs };
      this.buckets.set(clientKey, bucket);
    }
    const elapsed = nowMs - bucket.lastRefillTime;
    bucket.tokens = Math.min(this.capacity, bucket.tokens + elapsed * this.refillRatePerMs);
    bucket.lastRefillTime = nowMs;
    if (bucket.tokens >= 1) {
      bucket.tokens -= 1;
      return RateLimitResult.allow(Math.floor(bucket.tokens));
    }
    const deficit = 1 - bucket.tokens;
    const retryAfterMs = Math.ceil(deficit / this.refillRatePerMs);
    return RateLimitResult.deny(retryAfterMs);
  }
}

// Sliding window: keeps an exact queue of recent request timestamps per client and
// counts how many fall within the last windowMs - more accurate than fixed window at
// the cost of memory proportional to request rate.
class SlidingWindowLimiter extends RateLimitAlgorithm {
  constructor(config) {
    super();
    this.capacity = config.capacity;
    this.windowMs = config.windowMs;
    this.history = new Map(); // clientKey -> array of timestamps (oldest first)
  }

  allowRequest(clientKey, nowMs) {
    let timestamps = this.history.get(clientKey);
    if (!timestamps) { timestamps = []; this.history.set(clientKey, timestamps); }
    const windowStart = nowMs - this.windowMs;
    while (timestamps.length > 0 && timestamps[0] <= windowStart) {
      timestamps.shift();
    }
    if (timestamps.length < this.capacity) {
      timestamps.push(nowMs);
      return RateLimitResult.allow(this.capacity - timestamps.length);
    }
    const retryAfterMs = timestamps[0] + this.windowMs - nowMs;
    return RateLimitResult.deny(Math.max(0, retryAfterMs));
  }
}

// Fixed window: counts requests in discrete, non-overlapping windows - cheap (one
// counter per client) but allows bursts at window boundaries.
class FixedWindowLimiter extends RateLimitAlgorithm {
  constructor(config) {
    super();
    this.capacity = config.capacity;
    this.windowMs = config.windowMs;
    this.counters = new Map(); // clientKey -> { windowStart, count }
  }

  allowRequest(clientKey, nowMs) {
    let counter = this.counters.get(clientKey);
    if (!counter) {
      counter = { windowStart: nowMs, count: 0 };
      this.counters.set(clientKey, counter);
    }
    if (nowMs - counter.windowStart >= this.windowMs) {
      counter.windowStart = nowMs;
      counter.count = 0;
    }
    if (counter.count < this.capacity) {
      counter.count += 1;
      return RateLimitResult.allow(this.capacity - counter.count);
    }
    const retryAfterMs = counter.windowStart + this.windowMs - nowMs;
    return RateLimitResult.deny(Math.max(0, retryAfterMs));
  }
}

// ---------- RateLimiterFactory ----------
// Resolves "which algorithm for which endpoint" - kept out of both the facade and the
// algorithms themselves so that mapping logic has exactly one home.
class RateLimiterFactory {
  constructor(configsByEndpoint) {
    this.configsByEndpoint = configsByEndpoint; // Map<endpoint, RateLimitConfig>
    this.instancesByEndpoint = new Map();
  }

  getLimiter(endpoint) {
    let instance = this.instancesByEndpoint.get(endpoint);
    if (instance) return instance;

    const config = this.configsByEndpoint.get(endpoint);
    if (!config) throw new Error(`No config for endpoint: ${endpoint}`);

    switch (config.algorithmType) {
      case AlgorithmType.TOKEN_BUCKET: instance = new TokenBucketLimiter(config); break;
      case AlgorithmType.SLIDING_WINDOW: instance = new SlidingWindowLimiter(config); break;
      case AlgorithmType.FIXED_WINDOW: instance = new FixedWindowLimiter(config); break;
      default: throw new Error("Unknown algorithm type");
    }
    this.instancesByEndpoint.set(endpoint, instance);
    return instance;
  }
}

// ---------- RateLimiter (facade) ----------
class RateLimiter {
  constructor(factory) {
    this.factory = factory; // injected dependency
  }

  check(clientId, endpoint, nowMs) {
    const algorithm = this.factory.getLimiter(endpoint);
    const clientKey = `${endpoint}:${clientId}`; // scope quota per endpoint+client
    return algorithm.allowRequest(clientKey, nowMs);
  }
}

// ---------- Demo ----------
function main() {
  const configs = new Map([
    ["/api/login", new RateLimitConfig(3, 1000, AlgorithmType.TOKEN_BUCKET)],
    ["/api/search", new RateLimitConfig(2, 1000, AlgorithmType.FIXED_WINDOW)],
  ]);

  const factory = new RateLimiterFactory(configs);
  const limiter = new RateLimiter(factory);

  let t = 0;
  for (let i = 0; i < 5; i++) {
    const result = limiter.check("clientA", "/api/login", t);
    console.log(`t=${t} login attempt ${i + 1} ->`, result);
    t += 100; // 100ms between requests, faster than refill can keep up
  }

  console.log();
  let t2 = 0;
  for (let i = 0; i < 3; i++) {
    const result = limiter.check("clientB", "/api/search", t2);
    console.log(`t=${t2} search attempt ${i + 1} ->`, result);
  }
}

if (require.main === module) {
  main();
}

module.exports = {
  RateLimitResult, RateLimitConfig, AlgorithmType, RateLimitAlgorithm,
  TokenBucketLimiter, SlidingWindowLimiter, FixedWindowLimiter,
  RateLimiterFactory, RateLimiter,
};

// Rate Limiter - full LLD implementation (single-file demo).
// Difficulty badge is "Intermediate -> Advanced+Distributed" - it does NOT explicitly say
// "Concurrency", so per convention this stays single-threaded/simple (no locks), even
// though a production system would eventually need per-key locking or a distributed store.

// ---------- RateLimitResult (pure data) ----------
class RateLimitResult {
  private constructor(
    public readonly allowed: boolean,
    public readonly remaining: number,
    public readonly retryAfterMs: number // 0 if allowed
  ) {}
  static allow(remaining: number): RateLimitResult { return new RateLimitResult(true, remaining, 0); }
  static deny(retryAfterMs: number): RateLimitResult { return new RateLimitResult(false, 0, retryAfterMs); }
}

// ---------- RateLimitConfig (pure data) ----------
enum AlgorithmType { TOKEN_BUCKET = "TOKEN_BUCKET", SLIDING_WINDOW = "SLIDING_WINDOW", FIXED_WINDOW = "FIXED_WINDOW" }

class RateLimitConfig {
  constructor(
    public readonly capacity: number,   // max tokens / max requests per window
    public readonly windowMs: number,   // window size in ms (or refill window for token bucket)
    public readonly algorithmType: AlgorithmType
  ) {}
}

// ---------- RateLimitAlgorithm (interface) ----------
interface RateLimitAlgorithm {
  allowRequest(clientKey: string, nowMs: number): RateLimitResult;
}

// Each algorithm owns its own per-client state map, since the state shape genuinely
// differs (a counter vs. a timestamp deque vs. two rolling counters) - forcing a shared
// generic "Bucket" class would either bloat it or leak abstraction.
class TokenBucketLimiter implements RateLimitAlgorithm {
  private readonly capacity: number;
  private readonly refillRatePerMs: number; // tokens added per millisecond
  private readonly buckets = new Map<string, { tokens: number; lastRefillTime: number }>();

  constructor(config: RateLimitConfig) {
    this.capacity = config.capacity;
    this.refillRatePerMs = config.capacity / config.windowMs;
  }

  allowRequest(clientKey: string, nowMs: number): RateLimitResult {
    let bucket = this.buckets.get(clientKey);
    if (!bucket) {
      bucket = { tokens: this.capacity, lastRefillTime: nowMs };
      this.buckets.set(clientKey, bucket);
    }
    const elapsed = nowMs - bucket.lastRefillTime;
    bucket.tokens = Math.min(this.capacity, bucket.tokens + elapsed * this.refillRatePerMs);
    bucket.lastRefillTime = nowMs;
    if (bucket.tokens >= 1) {
      bucket.tokens -= 1;
      return RateLimitResult.allow(Math.floor(bucket.tokens));
    }
    const deficit = 1 - bucket.tokens;
    const retryAfterMs = Math.ceil(deficit / this.refillRatePerMs);
    return RateLimitResult.deny(retryAfterMs);
  }
}

// Sliding window: keeps an exact queue of recent request timestamps per client and
// counts how many fall within the last windowMs - more accurate than fixed window at
// the cost of memory proportional to request rate.
class SlidingWindowLimiter implements RateLimitAlgorithm {
  private readonly capacity: number;
  private readonly windowMs: number;
  private readonly history = new Map<string, number[]>();

  constructor(config: RateLimitConfig) {
    this.capacity = config.capacity;
    this.windowMs = config.windowMs;
  }

  allowRequest(clientKey: string, nowMs: number): RateLimitResult {
    let timestamps = this.history.get(clientKey);
    if (!timestamps) { timestamps = []; this.history.set(clientKey, timestamps); }
    const windowStart = nowMs - this.windowMs;
    while (timestamps.length > 0 && timestamps[0] <= windowStart) {
      timestamps.shift();
    }
    if (timestamps.length < this.capacity) {
      timestamps.push(nowMs);
      return RateLimitResult.allow(this.capacity - timestamps.length);
    }
    const retryAfterMs = timestamps[0] + this.windowMs - nowMs;
    return RateLimitResult.deny(Math.max(0, retryAfterMs));
  }
}

// Fixed window: counts requests in discrete, non-overlapping windows - cheap (one
// counter per client) but allows bursts at window boundaries.
class FixedWindowLimiter implements RateLimitAlgorithm {
  private readonly capacity: number;
  private readonly windowMs: number;
  private readonly counters = new Map<string, { windowStart: number; count: number }>();

  constructor(config: RateLimitConfig) {
    this.capacity = config.capacity;
    this.windowMs = config.windowMs;
  }

  allowRequest(clientKey: string, nowMs: number): RateLimitResult {
    let counter = this.counters.get(clientKey);
    if (!counter) {
      counter = { windowStart: nowMs, count: 0 };
      this.counters.set(clientKey, counter);
    }
    if (nowMs - counter.windowStart >= this.windowMs) {
      counter.windowStart = nowMs;
      counter.count = 0;
    }
    if (counter.count < this.capacity) {
      counter.count += 1;
      return RateLimitResult.allow(this.capacity - counter.count);
    }
    const retryAfterMs = counter.windowStart + this.windowMs - nowMs;
    return RateLimitResult.deny(Math.max(0, retryAfterMs));
  }
}

// ---------- RateLimiterFactory ----------
// Resolves "which algorithm for which endpoint" - kept out of both the facade and the
// algorithms themselves so that mapping logic has exactly one home.
class RateLimiterFactory {
  private readonly instancesByEndpoint = new Map<string, RateLimitAlgorithm>();

  constructor(private readonly configsByEndpoint: Map<string, RateLimitConfig>) {}

  getLimiter(endpoint: string): RateLimitAlgorithm {
    let instance = this.instancesByEndpoint.get(endpoint);
    if (instance) return instance;

    const config = this.configsByEndpoint.get(endpoint);
    if (!config) throw new Error(`No config for endpoint: ${endpoint}`);

    switch (config.algorithmType) {
      case AlgorithmType.TOKEN_BUCKET: instance = new TokenBucketLimiter(config); break;
      case AlgorithmType.SLIDING_WINDOW: instance = new SlidingWindowLimiter(config); break;
      case AlgorithmType.FIXED_WINDOW: instance = new FixedWindowLimiter(config); break;
      default: throw new Error("Unknown algorithm type");
    }
    this.instancesByEndpoint.set(endpoint, instance);
    return instance;
  }
}

// ---------- RateLimiter (facade) ----------
class RateLimiter {
  constructor(private readonly factory: RateLimiterFactory) {} // injected dependency

  check(clientId: string, endpoint: string, nowMs: number): RateLimitResult {
    const algorithm = this.factory.getLimiter(endpoint);
    const clientKey = `${endpoint}:${clientId}`; // scope quota per endpoint+client
    return algorithm.allowRequest(clientKey, nowMs);
  }
}

// ---------- Demo ----------
function main(): void {
  const configs = new Map<string, RateLimitConfig>([
    ["/api/login", new RateLimitConfig(3, 1000, AlgorithmType.TOKEN_BUCKET)],
    ["/api/search", new RateLimitConfig(2, 1000, AlgorithmType.FIXED_WINDOW)],
  ]);

  const factory = new RateLimiterFactory(configs);
  const limiter = new RateLimiter(factory);

  let t = 0;
  for (let i = 0; i < 5; i++) {
    const result = limiter.check("clientA", "/api/login", t);
    console.log(`t=${t} login attempt ${i + 1} ->`, result);
    t += 100; // 100ms between requests, faster than refill can keep up
  }

  console.log();
  let t2 = 0;
  for (let i = 0; i < 3; i++) {
    const result = limiter.check("clientB", "/api/search", t2);
    console.log(`t=${t2} search attempt ${i + 1} ->`, result);
  }
}

main();

export {
  RateLimitResult, RateLimitConfig, AlgorithmType, RateLimitAlgorithm,
  TokenBucketLimiter, SlidingWindowLimiter, FixedWindowLimiter,
  RateLimiterFactory, RateLimiter,
};