/**
 * This code is heavily based on boost circular_buffer:
 *    http://www.boost.org/doc/libs/1_55_0/doc/html/circular_buffer.html
 * The interface of this version and the original boost version is (as much as
 * possible identical). I did leave out some of the more fancy methods like
 * insert/remove in the middle of the buffer or linearize the buffer. If we
 * ever need those we can add them of course.
 * So (for now) this class represents a dynamically sized circular buffer with
 * (efficient) {push,pop}_{front,back} and operator[] methods. It also offers
 * random access iterators. For much more details check the boost
 * documentation.
 */
#ifndef CIRCULAR_BUFFER_HH
#define CIRCULAR_BUFFER_HH

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdlib>
#include <iterator>
#include <ranges>
#include <utility>

/** Random access iterator for circular_buffer. */
template<typename BUF, typename T> class cb_iterator
{
public:
	using value_type = T;
	using pointer    = T*;
	using reference  = T&;
	using difference_type = ptrdiff_t;
	using iterator_category = std::random_access_iterator_tag;

	cb_iterator() = default;
	cb_iterator(const cb_iterator& it) = default;
	cb_iterator(const BUF* buf_, T* p_) : buf(buf_), p(p_) {}

	cb_iterator& operator=(const cb_iterator& it) = default;

	[[nodiscard]] T& operator*()  const { return *p; }
	T* operator->() const { return  p; }

	[[nodiscard]] friend difference_type operator-(const cb_iterator& l, const cb_iterator& r) {
		return l.index(l.p) - r.index(r.p);
	}

	cb_iterator& operator++() {
		buf->increment(p);
		if (p == buf->last) p = nullptr;
		return *this;
	}
	cb_iterator& operator--() {
		if (p == nullptr) p = buf->last;
		buf->decrement(p);
		return *this;
	}
	cb_iterator operator++(int) { auto tmp = *this; ++*this; return tmp; }
	cb_iterator operator--(int) { auto tmp = *this; --*this; return tmp; }

	cb_iterator& operator+=(difference_type n) {
		if (n > 0) {
			p = buf->add(p,  n);
			if (p == buf->last) p = nullptr;
		} else if (n < 0) {
			if (p == nullptr) p = buf->last;
			p = buf->sub(p, -n);
		} else {
			// nothing, but _must_ be handled separately
		}
		return *this;
	}
	cb_iterator& operator-=(difference_type n) { *this += -n; return *this; }

	[[nodiscard]] friend cb_iterator operator+(cb_iterator it, difference_type n) { it += n; return it; }
	[[nodiscard]] friend cb_iterator operator+(difference_type n, cb_iterator it) { it += n; return it; }
	[[nodiscard]] friend cb_iterator operator-(cb_iterator it, difference_type n) { it -= n; return it; }

	[[nodiscard]] T& operator[](difference_type n) const { return *(*this + n); }

	[[nodiscard]] bool operator== (const cb_iterator& it) const { return p == it.p; }
	[[nodiscard]] auto operator<=>(const cb_iterator& it) const { return index(p) <=> index(it.p); }

private:
	[[nodiscard]] size_t index(const T* q) const {
		return q ? buf->index(q) : buf->size();
	}

	const BUF* buf = nullptr;
	T* p = nullptr; // invariant: end-iterator    -> nullptr,
	                //            other iterators -> pointer to element
};

/** Circular buffer class, based on boost::circular_buffer/ */
template<typename T> class circular_buffer
{
public:
	using               iterator = cb_iterator<circular_buffer<T>,       T>;
	using         const_iterator = cb_iterator<circular_buffer<T>, const T>;
	using       reverse_iterator = std::reverse_iterator<      iterator>;
	using const_reverse_iterator = std::reverse_iterator<const_iterator>;
	using value_type = T;
	using pointer    = T*;
	using reference  = T&;
	using difference_type = ptrdiff_t;
	using size_type       = size_t;
	static_assert(std::random_access_iterator<iterator>);

	circular_buffer() = default;

	explicit circular_buffer(size_t buffer_capacity)
	{
		buf = allocate(buffer_capacity);
		stop = buf + buffer_capacity;
		first = last = buf;
	}

	circular_buffer(const circular_buffer& cb)
		: siz(cb.size())
	{
		buf = allocate(cb.capacity());
		stop = buf + cb.capacity();
		first = buf;
		try {
			last = uninitialized_copy(cb.begin(), cb.end(), buf);
		} catch (...) {
			free(buf);
			throw;
		}
		if (last == stop) last = buf;
	}

	circular_buffer(circular_buffer&& cb) noexcept
	{
		cb.swap(*this);
	}

	~circular_buffer() {
		destroy();
	}

	circular_buffer& operator=(const circular_buffer& cb) {
		if (this == &cb) return *this;
		T* buff = allocate(cb.capacity());
		try {
			reset(buff,
			      uninitialized_copy(cb.begin(), cb.end(), buff),
			      cb.capacity());
		} catch (...) {
			free(buff);
			throw;
		}
		return *this;
	}

	circular_buffer& operator=(circular_buffer&& cb) noexcept {
		cb.swap(*this);
		circular_buffer().swap(cb);
		return *this;
	}

	void swap(circular_buffer& cb) noexcept {
		std::swap(buf,   cb.buf);
		std::swap(stop,  cb.stop);
		std::swap(first, cb.first);
		std::swap(last,  cb.last);
		std::swap(siz,   cb.siz);
	}

	[[nodiscard]] auto begin() {
		return iterator(this, empty() ? nullptr : first);
	}
	[[nodiscard]] auto begin() const {
		return const_iterator(this, empty() ? nullptr : first);
	}
	[[nodiscard]] auto end()          { return iterator      (this, nullptr); }
	[[nodiscard]] auto end()    const { return const_iterator(this, nullptr); }
	[[nodiscard]] auto rbegin()       { return       reverse_iterator(end()); }
	[[nodiscard]] auto rbegin() const { return const_reverse_iterator(end()); }
	[[nodiscard]] auto rend()         { return       reverse_iterator(begin()); }
	[[nodiscard]] auto rend()   const { return const_reverse_iterator(begin()); }

	[[nodiscard]] auto& operator[](size_t i)       { return *add(first, i); }
	[[nodiscard]] auto& operator[](size_t i) const { return *add(first, i); }

	[[nodiscard]] auto& front()       { return *first; }
	[[nodiscard]] auto& front() const { return *first; }
	[[nodiscard]] auto& back()       { return *((last == buf ? stop : last) - 1); }
	[[nodiscard]] auto& back() const { return *((last == buf ? stop : last) - 1); }

	[[nodiscard]] size_t size() const { return siz; }
	[[nodiscard]] bool empty() const { return size() == 0; }
	[[nodiscard]] bool full() const { return capacity() == size(); }
	[[nodiscard]] size_t reserve() const { return capacity() - size(); }
	[[nodiscard]] size_t capacity() const { return stop - buf; }

	void set_capacity(size_t new_capacity) {
		if (new_capacity == capacity()) return;
		T* new_buf = allocate(new_capacity);
		iterator b = begin();
		try {
			reset(new_buf,
			      uninitialized_move_n(b, std::min(new_capacity, size()),
			                           new_buf),
			      new_capacity);
		} catch (...) {
			free(new_buf);
			throw;
		}
	}

	template<typename T2>
	void push_back(T2&& t) {
		::new (last) T(std::forward<T2>(t));
		increment(last);
		++siz;
	}

	template<typename T2>
	void push_front(T2&& t) {
		try {
			decrement(first);
			::new (first) T(std::forward<T2>(t));
			++siz;
		} catch (...) {
			increment(first);
			throw;
		}
	}

	void push_back(std::initializer_list<T> list) {
		for (auto& e : list) push_back(e);
	}

	void pop_back() {
		decrement(last);
		last->~T();
		--siz;
	}

	void pop_front() {
		first->~T();
		increment(first);
		--siz;
	}

	// Remove the first 'n' elements, like std::string_view::remove_prefix().
	void remove_prefix(size_t n) {
		assert(n <= size());
		for (size_t i = 0; i < n; ++i) {
			first->~T();
			increment(first);
		}
		siz -= n;
	}

	void clear() {
		for (size_t i = 0; i < size(); ++i, increment(first)) {
			first->~T();
		}
		siz = 0;
	}

private:
	[[nodiscard]] T* uninitialized_copy(const_iterator b, const_iterator e, T* dst) {
		T* next = dst;
		try {
			while (b != e) {
				::new (dst) T(*b);
				++b; ++dst;
			}
		} catch (...) {
			while (next != dst) {
				next->~T();
				++next;
			}
			throw;
		}
		return dst;
	}

	[[nodiscard]] T* uninitialized_move_n(iterator src, size_t n, T* dst) {
		while (n) {
			::new (dst) T(std::move(*src));
			++src; ++dst; --n;
		}
		return dst;
	}

	void increment(auto*& p) const {
		if (++p == stop) p = buf;
	}
	void decrement(auto*& p) const {
		if (p == buf) p = stop;
		--p;
	}
	[[nodiscard]] auto* add(auto* p, difference_type n) const {
		p += n;
		if (p >= stop) p -= capacity();
		return p;
	}
	[[nodiscard]] auto* sub(auto* p, difference_type n) const {
		p -= n;
		if (p < buf) p += capacity();
		return p;
	}

	[[nodiscard]] size_t index(const T* p) const {
		return (p >= first)
			? (p - first)
			: (stop - first) + (p - buf);
	}

	[[nodiscard]] T* allocate(size_t n) {
		return (n == 0) ? nullptr
		                : static_cast<T*>(malloc(n * sizeof(T)));
	}

	void destroy() {
		clear();
		free(buf);
	}

	void reset(T* new_buf, T* new_last, size_t new_capacity) {
		destroy();
		siz = new_last - new_buf;
		first = buf = new_buf;
		stop = buf + new_capacity;
		last = new_last == stop ? buf : new_last;
	}

private:
	T* buf = nullptr;   // start of allocated area
	T* stop = nullptr;  // end of allocated area (exclusive)
	T* first = nullptr; // position of the 1st element in the buffer
	T* last = nullptr;  // position past the last element
	                    // note: both for a full or empty buffer first==last
	size_t siz = 0; // number of elements in the buffer

	template<typename BUF, typename T2> friend class cb_iterator;
};


/** This implements a queue on top of circular_buffer (not part of boost).
  * It will automatically grow the buffer when its capacity is too small
  * while inserting new elements. */
template<typename T> class cb_queue
{
public:
	using             value_type = typename circular_buffer<T>::value_type;
	using               iterator = typename circular_buffer<T>::iterator;
	using         const_iterator = typename circular_buffer<T>::const_iterator;
	using       reverse_iterator = typename circular_buffer<T>::reverse_iterator;
	using const_reverse_iterator = typename circular_buffer<T>::const_reverse_iterator;

	cb_queue() = default;
	explicit cb_queue(size_t capacity)
		: buf(capacity) {}

	template<typename U>
	void push_back(U&& u) { growFor(1); buf.push_back(std::forward<U>(u)); }

	template<typename U>
	void push_back(std::initializer_list<U> list) { push_back_range(list); }

	// Appends all elements of the given range at once. The buffer is
	// grown at most once, unlike repeated push_back() calls.
	template<typename Range>
	void push_back_range(Range&& range) {
		growFor(static_cast<size_t>(std::ranges::distance(range)));
		for (auto&& e : range) {
			buf.push_back(std::forward<decltype(e)>(e));
		}
	}

	T pop_front() {
		T t = std::move(buf.front());
		buf.pop_front();
		return t;
	}

	[[nodiscard]] const T& front() const { return buf.front(); }
	[[nodiscard]] const T& back() const  { return buf.back();  }
	[[nodiscard]] const T& operator[](size_t i) const { return buf[i]; }

	[[nodiscard]] auto  begin()       { return buf.begin();  }
	[[nodiscard]] auto  end()         { return buf.end();    }
	[[nodiscard]] auto  begin() const { return buf.begin();  }
	[[nodiscard]] auto  end()   const { return buf.end();    }
	[[nodiscard]] auto rbegin()       { return buf.rbegin(); }
	[[nodiscard]] auto rbegin() const { return buf.rbegin(); }
	[[nodiscard]] auto rend()         { return buf.rend();   }
	[[nodiscard]] auto rend()   const { return buf.rend();   }

	[[nodiscard]] size_t size() const { return buf.size(); }
	[[nodiscard]] bool empty() const { return buf.empty(); }
	void clear() { buf.clear(); }

	// Remove the first 'n' elements, like std::string_view::remove_prefix().
	void remove_prefix(size_t n) { buf.remove_prefix(n); }

	[[nodiscard]] auto& getBuffer()       { return buf; }
	[[nodiscard]] auto& getBuffer() const { return buf; }

private:
	// Grows the buffer so that (at least) 'extra' more elements fit.
	void growFor(size_t extra) {
		size_t needed = size() + extra;
		if (needed <= buf.capacity()) return;
		buf.set_capacity(std::max({4uz, buf.capacity() * 2, needed}));
	}

	circular_buffer<T> buf;
};

#endif