#pragma once

#include <iostream>
#include <cstdlib>
#include "queue.h"

using namespace std;

template <class TData>
class CircularQueue :public Queue<TData>
{
	friend ostream& operator<< <>(ostream& os, const CircularQueue<TData>& circular_queue);

private:
	TData* mem_data_;
	int capacity_;
	int front_; // 指向队头元素的数组索引
	int rear_; // 指向队尾元素的数组索引

public:
	explicit CircularQueue(int capacity = 20) :capacity_(capacity), front_(-1), rear_(-1)
	{
		this->mem_data_ = new TData[this->capacity_];
		if (!this->mem_data_)
			throw bad_alloc();
	}

	~CircularQueue() { delete[] this->mem_data_; }

	virtual bool enQueue(const TData& data) override;

	virtual bool deQueue(TData& data) override;

	bool deQueue();

	virtual bool front(TData& data) const override;

	bool rear(TData& data) const;

	virtual bool isEmpty() const override;

	bool isFull() const;

	virtual int length() const override;

	void clear();
};

template <typename TData>
ostream& operator<<<>(ostream& os, const CircularQueue<TData>& circular_queue)
{
	os << "The size of link queue：" << circular_queue.length() << endl;

	for (int i = 0; i < circular_queue.length(); i++)
	{
		int actual_index = (circular_queue.front_ + i + circular_queue.capacity_) % circular_queue.capacity_;
		os << circular_queue.mem_data_[actual_index] << endl;
	}

	return os;
}

template<class TData>
inline bool CircularQueue<TData>::enQueue(const TData& data)
{
	if (this->isFull())
		return false;

	if (this->length() == 0)
		this->front_ = 0;

	this->rear_ = (this->rear_ + 1 + this->capacity_) % this->capacity_;
	this->mem_data_[this->rear_] = data;

	return true;
}

template<class TData>
inline bool CircularQueue<TData>::deQueue(TData& data)
{
	if (this->isEmpty())
		return false;

	data = this->mem_data_[this->front_];

	// 队列中只有一个元素
	if (this->length() == 1)
	{
		this->front_ = -1;
		this->rear_ = -1;
	}
	else
		this->front_ = (this->front_ + 1 + this->capacity_) % this->capacity_;
}

template<class TData>
inline bool CircularQueue<TData>::deQueue()
{
	if (this->isEmpty())
		return false;

	if (this->length() == 1)
	{
		this->front_ = -1;
		this->rear_ = 1;
	}
	else
		this->front_ = (this->front_ + 1 + this->capacity_) % this->capacity_;

	return true;
}

template<class TData>
inline bool CircularQueue<TData>::front(TData& data) const
{
	if (this->isEmpty())
		return false;

	data = this->mem_data_[this->front_];

	return true;
}

template<class TData>
inline bool CircularQueue<TData>::rear(TData& data) const
{
	if (this->isEmpty())
		return false;

	data = this->mem_data_[this->rear];

	return true;
}

template<class TData>
inline bool CircularQueue<TData>::isEmpty() const
{
	return this->length() == 0;
}

template<class TData>
inline bool CircularQueue<TData>::isFull() const
{
	return this->length() == this->capacity_;
}

template<class TData>
inline int CircularQueue<TData>::length() const
{
	if (this->rear_ == -1 && this->front_ == -1)
		return 0;

	return (this->rear_ - this->front_ + 1 + this->capacity_) % this->capacity_;
}

template<class TData>
inline void CircularQueue<TData>::clear()
{
	this->rear_ = -1;
	this->front_ = -1;
}