#include <chrono>
#include <cstdint>
#include <cstdio>
#include <ctime>
#include <thread>

const int NS_PER_SECOND = 1e9;

// 獲取當(dāng)前時(shí)間戳, 單位納秒
int64_t Now() {
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);
  return ts.tv_sec * NS_PER_SECOND + ts.tv_nsec;
}

class RateLimiter {
  // 時(shí)間窗口, 單位秒
  int64_t window_;
  // 時(shí)間窗口內(nèi)最大允許的閾值
  int64_t threshold_;
  // 當(dāng)前時(shí)間窗口的起始時(shí)間
  int64_t start_time_ = Now();
  // 計(jì)數(shù)器
  int64_t counter_;

 public:
  RateLimiter(int64_t window, int64_t threshold)
      : window_(window), threshold_(threshold) {}
  /**
   * @param permits 配額數(shù)量
   * @return 申請成功則返回true，否則返回false
   */
  bool tryAcquire(int permits) {
    long now = Now();
    if (now - start_time_ > window_ * NS_PER_SECOND) {
      counter_ = 0;
      start_time_ = now;
    }
    if (counter_ + permits <= threshold_) {
      counter_ += permits;
      return true;
    } else {
      return false;
    }
  }
};

int main() {
  // 限流300MB/s
  RateLimiter limiter(1, 300 * 1024 * 1024);
  // 每次請求256KB
  int64_t request_size = 256 * 1024;
  // 每隔約1ms發(fā)起2次請求
  // 每隔1s打印一次請求數(shù)據(jù)量
  int64_t start_time = Now();
  int64_t last_time = start_time;
  int64_t last_size = 0;
  while (true) {
    int64_t now = Now();
    if (now - last_time >= NS_PER_SECOND) {
      printf("time: %lf s, request size: %lf MB\n", (now - last_time) / 1e9,
             (last_size / 1024.0 / 1024.0));
      last_time = now;
      last_size = 0;
    }
    for (int i = 0; i < 2; ++i) {
      if (limiter.tryAcquire(request_size)) {
        last_size += request_size;
      }
    }
    std::this_thread::sleep_for(std::chrono::milliseconds(1));
  }
  return 0;
}

class LeakyBucket {
  int64_t last_time_ = Now();
  int64_t rate_;
  int64_t debt_;
  // 精度
  int64_t precision_;
  int64_t quota_;

 public:
  LeakyBucket(int64_t rate, double precision = 1000)
      : rate_(rate), precision_(precision) {
    quota_ = rate_ / precision_;
  }

  bool tryAcquire(int permits) {
    int64_t now = Now();
    int64_t pay_off = (now - last_time_) * rate_ / NS_PER_SECOND;
    int64_t left_debt = std::max(0LL, debt_ - pay_off);
    if (left_debt > quota_) {
      return false;
    }
    debt_ = left_debt + permits;
    last_time_ = now;
    return true;
  }
};

class LeakyBucket {
  int64_t last_time_ = Now();
  int64_t rate_;
  int64_t debt_;
  // 精度
  int64_t precision_;
  int64_t quota_;

 public:
  LeakyBucket(int64_t rate, double precision = 1000)
      : rate_(rate), precision_(precision) {
    quota_ = rate_ / precision_;
  }

  bool tryAcquire(int permits) {
    int64_t now = Now();
    int count = (now - last_time_) / (NS_PER_SECOND / precision_);
    int64_t pay_off = count * quota_;
    int64_t left_debt = std::max(0LL, debt_ - pay_off);
    if (left_debt > quota_) {
      return false;
    }
    debt_ = left_debt + permits;
    last_time_ += count * (NS_PER_SECOND / precision_);
    return true;
  }
};

class TokenBucket {
 public:
  TokenBucket(int64_t capacity, int64_t rate)
      : capacity_(capacity),
        rate_(rate),
        supply_unit_time_(NS_PER_SECOND / rate) {}

  // 嘗試獲取令牌
  bool tryAcquire(int permits) {
    int64_t cur = Now();
    int64_t new_tokens = (cur - last_time_) / supply_unit_time_;
    // 更新補(bǔ)充時(shí)間, 不能直接=cur, 否則會(huì)導(dǎo)致時(shí)間丟失
    last_time_ += new_tokens * supply_unit_time_;
    tokens_ = std::min(capacity_, tokens_ + new_tokens);
    if (tokens_ >= permits) {
      tokens_ -= permits;
      return true;
    } else {
      return false;
    }
  }

 private:
  // 當(dāng)前桶內(nèi)的令牌數(shù)
  int64_t tokens_ = 0;
  // 上次補(bǔ)充令牌的時(shí)間(單位納秒)
  int64_t last_time_ = Now();
  // 令牌桶大小
  int64_t capacity_;
  // 補(bǔ)充令牌的速率
  int64_t rate_;
  // 補(bǔ)充令牌的單位時(shí)間
  const int64_t supply_unit_time_;
};

class TokenBucket {
 public:
  TokenBucket(int64_t capacity, int64_t rate)
      : capacity_(capacity),
        rate_(rate),
        supply_unit_time_(NS_PER_SECOND / rate) {}

  // 嘗試獲取令牌
  bool tryAcquire(int permits) {
    int64_t now = Now();
    int64_t count = (now - last_time_) / supply_unit_time_;
    int64_t new_tokens = count * supply_unit_time_ * rate_ / NS_PER_SECOND;
    // 更新補(bǔ)充時(shí)間, 不能直接=now, 否則會(huì)導(dǎo)致時(shí)間丟失
    last_time_ += count * supply_unit_time_;
    tokens_ = std::min(capacity_, tokens_ + new_tokens);
    if (tokens_ >= permits) {
      tokens_ -= permits;
      return true;
    } else {
      return false;
    }
  }

 private:
  // 當(dāng)前桶內(nèi)的令牌數(shù)
  int64_t tokens_ = 0;
  // 上次補(bǔ)充令牌的時(shí)間(單位納秒)
  int64_t last_time_ = Now();
  // 令牌桶大小
  int64_t capacity_;
  // 補(bǔ)充令牌的速率
  int64_t rate_;
  // 補(bǔ)充令牌的單位時(shí)間
  const int64_t supply_unit_time_ = NS_PER_US;
};

class DynamicTokenBucket {
  double zeroTime_;

 public:
  explicit DynamicTokenBucket(double zeroTime = 0) noexcept
      : zeroTime_(zeroTime) {}

  bool tryAcquire(double permits, double rate, double burstSize,
                  int64_t now = Now()) {
    double tokens = std::min((now / 1e9 - zeroTime_) * rate, burstSize);
    if (tokens < permits) {
      return false;
    }
    tokens -= permits;
    zeroTime_ = now / 1e9 - tokens / rate;

    return true;
  }
};

class TokenBucket {
  DynamicTokenBucket tokenBucket_;
  double rate_;
  double burstSize_;

 public:
  TokenBucket(double rate, double burstSize, double zeroTime = 0) noexcept
      : tokenBucket_(zeroTime), rate_(rate), burstSize_(burstSize) {}

  bool tryAcquire(double permits, int64_t now = Now()) {
    return tokenBucket_.tryAcquire(permits, rate_, burstSize_, now);
  }
};

# 初始化
counter = 0
q = []

# 請求處理流程
# 1.找到隊(duì)列中第一個(gè)時(shí)間戳>=t-T的請求，即以當(dāng)前時(shí)間t截止的時(shí)間窗口T內(nèi)的最早請求
t = now
start = findWindowStart(q, t)

# 2.截?cái)嚓?duì)列，只保留最近T時(shí)間窗口內(nèi)的記錄和計(jì)數(shù)值
q = q[start, q.length - 1]
counter -= start

# 3.判斷是否放行，如果允許放行則將這次請求加到隊(duì)列 q 的末尾
if counter < threshold
    push(q, t)
    counter++
    # 放行
else
    # 限流

#include <chrono>
#include <cstdint>
#include <cstdio>
#include <ctime>
#include <thread>
const int NS_PER_SECOND = 1e9;
const int NS_PER_MS = 1e6;
const int NS_PER_US = 1e3;
// 獲取當(dāng)前時(shí)間戳, 單位納秒
int64_t Now() {
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);
  return ts.tv_sec * NS_PER_SECOND + ts.tv_nsec;
}
class RateLimiter {
  // 時(shí)間窗口, 單位秒
  int64_t window_;
  // 時(shí)間窗口內(nèi)最大允許的閾值
  int64_t threshold_;
  // 當(dāng)前時(shí)間窗口的起始時(shí)間
  int64_t start_time_ = Now();
  // 計(jì)數(shù)器
  int64_t counter_;
 public:
  RateLimiter(int64_t window, int64_t threshold)
      : window_(window), threshold_(threshold) {}
  bool tryAcquire(int permits) {
    long now = Now();
    if (now - start_time_ > window_ * NS_PER_SECOND) {
      counter_ = 0;
      start_time_ = now;
    }
    if (counter_ + permits <= threshold_) {
      counter_ += permits;
      return true;
    } else {
      return false;
    }
  }
};
class LeakyBucket {
  int64_t last_time_ = Now();
  int64_t rate_;
  int64_t debt_;
  // 精度
  int64_t precision_;
  int64_t quota_;
 public:
  LeakyBucket(int64_t rate, double precision = 1000)
      : rate_(rate), precision_(precision) {
    quota_ = rate_ / precision_;
  }
  bool tryAcquire(int permits) {
    int64_t now = Now();
    int count = (now - last_time_) / (NS_PER_SECOND / precision_);
    int64_t pay_off = count * quota_;
    int64_t left_debt = std::max(0LL, debt_ - pay_off);
    if (left_debt > quota_) {
      return false;
    }
    debt_ = left_debt + permits;
    last_time_ += count * (NS_PER_SECOND / precision_);
    return true;
  }
};
class TokenBucket {
 public:
  TokenBucket(int64_t capacity, int64_t rate)
      : capacity_(capacity),
        rate_(rate),
        supply_unit_time_(NS_PER_SECOND / rate) {}
  // 嘗試獲取令牌
  bool tryAcquire(int permits) {
    int64_t now = Now();
    int64_t count = (now - last_time_) / supply_unit_time_;
    int64_t new_tokens = count * supply_unit_time_ * rate_ / NS_PER_SECOND;
    // 更新補(bǔ)充時(shí)間, 不能直接=now, 否則會(huì)導(dǎo)致時(shí)間丟失
    last_time_ += count * supply_unit_time_;
    tokens_ = std::min(capacity_, tokens_ + new_tokens);
    if (tokens_ >= permits) {
      tokens_ -= permits;
      return true;
    } else {
      return false;
    }
  }
 private:
  // 當(dāng)前桶內(nèi)的令牌數(shù)
  int64_t tokens_ = 0;
  // 上次補(bǔ)充令牌的時(shí)間(單位納秒)
  int64_t last_time_ = Now();
  // 令牌桶大小
  int64_t capacity_;
  // 補(bǔ)充令牌的速率
  int64_t rate_;
  // 補(bǔ)充令牌的單位時(shí)間
  const int64_t supply_unit_time_ = NS_PER_US;
};
int main() {
  // 限流300MB/s
  // RateLimiter limiter(1, 300 * 1024 * 1024);
  // LeakyBucket limiter(300 * 1024 * 1024);
  TokenBucket limiter(1024 * 1024, 300 * 1024 * 1024);
  // 每次請求256KB
  int64_t request_size = 256 * 1024;
  // 每隔約1ms發(fā)起2次請求
  // 每隔1s打印一次請求數(shù)據(jù)量
  int64_t start_time = Now();
  int64_t last_time = start_time;
  int64_t last_size = 0;
  while (true) {
    int64_t now = Now();
    if (now - last_time >= NS_PER_SECOND) {
      printf("time: %lf s, request size: %lf MB\n", (now - last_time) / 1e9,
             (last_size / 1024.0 / 1024.0));
      last_time = now;
      last_size = 0;
    }
    for (int i = 0; i < 2; ++i) {
      if (limiter.tryAcquire(request_size)) {
        last_size += request_size;
      }
    }
    std::this_thread::sleep_for(std::chrono::milliseconds(1));
  }
  return 0;
}