#pragma once

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

using namespace std;

namespace linked_queue
{
	template <class TData>
	class LinkedNode
	{
	private:
		TData data_;
		LinkedNode<TData>* next_;

	public:
		LinkedNode() :next_(NULL) {}

		explicit LinkedNode(LinkedNode<TData>* node = NULL) :next_(node) {}

		explicit LinkedNode(const TData& data, LinkedNode<TData>* node = NULL) :data_(data), next_(node) {}

		TData getData() { return this->data_; }

		void setData(const TData& data) { this->data_ = data; }

		LinkedNode<TData>* next() { return this->next_; }

		void setNext(LinkedNode<TData>*& node) { this->next_ = node; }
	};
}

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

private:
	linked_queue::LinkedNode<TData>* front_; // 队头指针
	linked_queue::LinkedNode<TData>* rear_; // 队尾指针
	
	linked_queue::LinkedNode<TData>* frontNode_() const { return this->front_; }

	linked_queue::LinkedNode<TData>* rearNode_() const { return this->rear_; }
public:
	LinkedQueue() :front_(NULL), rear_(NULL) {}

	~LinkedQueue() { this->clear(); }

	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;

	virtual int length() const override;

	void clear();
};

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

	linked_queue::LinkedNode<TData>* cur = linked_queue.frontNode_();

	for (int i = 1; cur != NULL; i++)
	{
		os << i << "：" << cur->getData() << endl;
		cur = cur->next();
	}

	return os;
}

template<class TData>
inline bool LinkedQueue<TData>::enQueue(const TData& data)
{
	linked_queue::LinkedNode<TData>* node = new linked_queue::LinkedNode<TData>(data);
	if (!node)
		throw bad_alloc();
	
	// 第一个元素入队
	if (this->isEmpty())
	{
		this->front_ = node;
		this->rear_ = node;
	}else
	{
		this->rear_->setNext(node);
		this->rear_ = node;
	}

	return true;
}

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

	linked_queue::LinkedNode<TData>* temp = this->front_;
	data = temp->getData();

	this->front_ = this->front_->next();

	delete temp;
	// 防止出现悬空指针
	temp = NULL;

	return true;
}

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

	linked_queue::LinkedNode<TData>* temp = this->front_;

	this->front_ = this->front_->next();

	delete temp;
	// 防止出现悬空指针
	temp = NULL;

	return true;
}

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

	data = this->front_->getData();

	return true;
}

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

	data = this->rear_->getData();

	return true;
}

template<class TData>
inline bool LinkedQueue<TData>::isEmpty() const
{
	return this->front_ == NULL;
}

template<class TData>
inline int LinkedQueue<TData>::length() const
{
	int count = 0;

	for (linked_queue::LinkedNode<TData>* cur = this->front_; cur != NULL; cur = cur->next())
	{
		count++;
	}

	return count;
}

template<class TData>
inline void LinkedQueue<TData>::clear()
{
	while (!this->isEmpty())
		this->deQueue();
}