#include <atomic>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <mutex>
#include <queue>
#include <thread>
#include <vector>

class StdQueue {
public:
  explicit StdQueue() {}
  bool enqueue(int item) {
    buffer_.push(item);
    return true;
  }
  bool dequeue(int *dest) {
    if (buffer_.empty()) {
      return false;
    }
    *dest = buffer_.front();
    return true;
  }

private:
  std::queue<int> buffer_;
};

class RingBuffer0 {
public:
  explicit RingBuffer0(size_t size) : buffer_(size) {}

  // Returns true on success. Fails if the buffer is full.
  bool enqueue(int item) {
    if (write_idx_ - read_idx_ == buffer_.size()) {
      return false;
    }
    buffer_[write_idx_ % buffer_.size()] = item;
    write_idx_++;
    return true;
  }

  // Returns true on success. Fails if the buffer is empty.
  bool dequeue(int *dest) {
    if (write_idx_ == read_idx_) {
      return false;
    }
    *dest = buffer_[read_idx_ % buffer_.size()];
    read_idx_++;
    return true;
  }

private:
  std::vector<int> buffer_;
  uint64_t read_idx_{0};
  uint64_t write_idx_{0};
};

class RingBuffer1 {
public:
  explicit RingBuffer1(size_t size) : buffer_(size) {}

  // Returns true on success. Fails if the buffer is full.
  bool enqueue(int item) {
    if (write_idx_ - read_idx_ == buffer_.size()) {
      return false;
    }
    buffer_[write_idx_ & (buffer_.size() - 1)] = item;
    write_idx_++;
    return true;
  }

  // Returns true on success. Fails if the buffer is empty.
  bool dequeue(int *dest) {
    if (write_idx_ == read_idx_) {
      return false;
    }
    *dest = buffer_[read_idx_ & (buffer_.size() - 1)];
    read_idx_++;
    return true;
  }

private:
  std::vector<int> buffer_;
  uint64_t read_idx_{0};
  uint64_t write_idx_{0};
};

class RingBufferMutex {
public:
  explicit RingBufferMutex(size_t size) : buffer_(size) {}

  // Returns true on success. Fails if the buffer is full.
  bool enqueue(int item) {
    std::scoped_lock lock(mutex_);
    if (write_idx_ - read_idx_ == buffer_.size()) {
      return false;
    }
    buffer_[write_idx_ & (buffer_.size() - 1)] = item;
    write_idx_++;
    return true;
  }

  // Returns true on success. Fails if the buffer is empty.
  bool dequeue(int *dest) {
    std::scoped_lock lock(mutex_);
    if (write_idx_ == read_idx_) {
      return false;
    }
    *dest = buffer_[read_idx_ & (buffer_.size() - 1)];
    read_idx_++;
    return true;
  }

private:
  std::mutex mutex_;
  std::vector<int> buffer_;
  uint64_t read_idx_{0};
  uint64_t write_idx_{0};
};

class RingBuffer2 {
public:
  explicit RingBuffer2(size_t size) : buffer_(size) {}

  // Returns true on success. Fails if the buffer is full.
  bool enqueue(int item) {
    uint64_t write_idx = write_idx_.load(std::memory_order_relaxed);
    uint64_t read_idx = read_idx_.load(std::memory_order_acquire);
    if (write_idx - read_idx == buffer_.size()) {
      return false;
    }
    buffer_[write_idx & (buffer_.size() - 1)] = item;
    write_idx_.store(write_idx + 1, std::memory_order_release);
    return true;
  }

  // Returns true on success. Fails if the buffer is empty.
  bool dequeue(int *dest) {
    uint64_t read_idx = read_idx_.load(std::memory_order_relaxed);
    uint64_t write_idx = write_idx_.load(std::memory_order_acquire);
    if (write_idx == read_idx) {
      return false;
    }
    *dest = buffer_[read_idx & (buffer_.size() - 1)];
    read_idx_.store(read_idx + 1, std::memory_order_release);
    return true;
  }

private:
  std::vector<int> buffer_;
  alignas(64) std::atomic<uint64_t> read_idx_{0};
  alignas(64) std::atomic<uint64_t> write_idx_{0};
};

class RingBuffer3 {
public:
  explicit RingBuffer3(size_t size) : buffer_(size) {}

  // Returns true on success. Fails if the buffer is full.
  bool enqueue(int item) {
    uint64_t write_idx = write_idx_.load(std::memory_order_relaxed);
    if (write_idx - cached_read_idx_ == buffer_.size()) {
      cached_read_idx_ = read_idx_.load(std::memory_order_acquire);
      if (write_idx - cached_read_idx_ == buffer_.size()) {
        return false;
      }
    }
    buffer_[write_idx & (buffer_.size() - 1)] = item;
    write_idx_.store(write_idx + 1, std::memory_order_release);
    return true;
  }

  // Returns true on success. Fails if the buffer is empty.
  bool dequeue(int *dest) {
    uint64_t read_idx = read_idx_.load(std::memory_order_relaxed);
    if (cached_write_idx_ == read_idx) {
      cached_write_idx_ = write_idx_.load(std::memory_order_acquire);
      if (cached_write_idx_ == read_idx) {
        return false;
      }
    }
    *dest = buffer_[read_idx & (buffer_.size() - 1)];
    read_idx_.store(read_idx + 1, std::memory_order_release);
    return true;
  }

private:
  std::vector<int> buffer_;
  alignas(64) std::atomic<uint64_t> read_idx_{0};
  alignas(64) uint64_t cached_read_idx_{0};
  alignas(64) std::atomic<uint64_t> write_idx_{0};
  alignas(64) uint64_t cached_write_idx_{0};
};

constexpr uint64_t kCount = 500000;

template <typename RingBufferType> double benchmark_single(RingBufferType &rb) {
  auto start = std::chrono::system_clock::now();
  int result;
  for (uint64_t i = 0; i < kCount; ++i) {
    for (int j = 0; j < 1000; ++j) {
      rb.enqueue(j);
    }
    for (int j = 0; j < 1000; ++j) {
      rb.dequeue(&result);
    }
  }
  auto end = std::chrono::system_clock::now();
  double duration =
      std::chrono::duration_cast<std::chrono::milliseconds>(end - start)
          .count();
  const int count = kCount * (1000 + 1000);
  std::cerr << count << " ops in " << duration << " ms \t";
  return count / duration;
}

template <typename RingBufferType> double benchmark(RingBufferType &rb) {
  auto start = std::chrono::system_clock::now();
  std::thread workers[2] = {
      std::thread([&]() {
        for (uint64_t i = 0; i < kCount; ++i) {
          int count = 1000;
          while (0 < count) {
            if (rb.enqueue(count)) {
              count--;
            }
          }
        }
      }),
      std::thread([&]() {
        int result;
        for (uint64_t i = 0; i < kCount; ++i) {
          int count = 1000;
          while (0 < count) {
            if (rb.dequeue(&result)) {
              count--;
            }
          }
        }
      })};
  for (auto &w : workers) {
    w.join();
  }
  auto end = std::chrono::system_clock::now();
  double duration =
      std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
  const int count = kCount * (1000 + 1000);
  std::cerr << count << " ops in " << duration << " ns \t";
  return 1000000.0 * kCount * (1000 + 1000) / duration;
}

int main() {
  StdQueue queue;
  RingBuffer0 rb0(2 * 1024 * 1024);
  RingBuffer1 rb1(2 * 1024 * 1024);
  RingBufferMutex rbm(2 * 1024 * 1024);
  RingBuffer2 rb2(2 * 1024 * 1024);
  RingBuffer3 rb3(2 * 1024 * 1024);
  std::cout << std::setprecision(10);
  std::cout << "StdQueue_single: " << benchmark_single(queue) << " ops/ms\n";
  std::cout << "RingBufferMutex: " << benchmark_single(rbm) << " ops/ms\n";
  std::cout << "RingBuffer0_single: " << benchmark_single(rb0) << " ops/ms\n";
  std::cout << "RingBuffer1_single: " << benchmark_single(rb1) << " ops/ms\n";
  std::cout << "RingBuffer2_single: " << benchmark_single(rb2) << " ops/ms\n";
  std::cout << "RingBuffer3_single: " << benchmark_single(rb3) << " ops/ms\n";
  std::cout << "RingBufferMutex: " << benchmark(rbm) << " opms\n";
  std::cout << "RingBuffer2: " << benchmark(rb2) << " ops/ms\n";
  std::cout << "RingBuffer3: " << benchmark(rb3) << " ops/ms\n";
}