#ifndef CIRCULAR_DOUBLY_LINKED_LIST_HPP
#define CIRCULAR_DOUBLY_LINKED_LIST_HPP

#include <iostream>
#include <cstddef>
#include <exception>
#include "linear_list.h"

using namespace std;

template <class TData>
struct CircularDoublyLinkedNode
{
	TData data;
	CircularDoublyLinkedNode<TData>* prev;
	CircularDoublyLinkedNode<TData>* next;

	explicit CircularDoublyLinkedNode(CircularDoublyLinkedNode<TData>* next = NULL,
		CircularDoublyLinkedNode<TData>* prev = NULL)
		:next(next), prev(prev) {}

	explicit CircularDoublyLinkedNode(const TData& data,
		CircularDoublyLinkedNode<TData>* next = NULL, CircularDoublyLinkedNode<TData>* prev = NULL)
		:data(data), next(next), prev(prev) {}
};


template <class TData>
class CircularDoublyLinkedList :public LinearList<TData>
{
private:
	// 首元素结点指针变量
	CircularDoublyLinkedNode<TData>* first_;
	int length_;
public:
	static const int BACKWARD_DIRECTION = 0;	// prev方向
	static const int FORWARD_DIRECTION = 1;		// next方向

	CircularDoublyLinkedList() :first_(NULL), length_(0) {}

	~CircularDoublyLinkedList();

	//const 函数承诺不会修改类的成员变量（除非这些成员变量被声明为 mutable）。
	// 获取容器长度
	virtual int length() const override { return this->length_; }

	virtual bool getData(int pos, TData& data) const override;

	// const TData& data ==> const TData * const data
	virtual bool setData(int pos, const TData& data) override;

	virtual bool insert(int prev_pos, const TData& data) override;

	virtual bool remove(int deletion_pos, TData& data) override;

	virtual bool isEmpty() const override { return this->first_ == NULL; }

	virtual void print() const override;

	CircularDoublyLinkedNode<TData>* first() const { return this->first_; }
	
	CircularDoublyLinkedNode<TData>* search(const TData& data) const;
	
	CircularDoublyLinkedNode<TData>* getNodeByDirection(int step, int direction) const;

	CircularDoublyLinkedNode<TData>* getNode(int pos) const;

	bool removeByDirection(int step, TData& data, int direction);

	void clear();
};

template<class TData>
inline CircularDoublyLinkedList<TData>::~CircularDoublyLinkedList()
{
	this->clear();
}

template<class TData>
inline bool CircularDoublyLinkedList<TData>::getData(int pos, TData& data) const
{
	if (pos < 0 || pos > this->length_ || this->length_ == 0)
		return false;

	// pos 为0时表示取出“链表队尾元素”
	if (pos == 0)
	{
		data = this->first_->prev->data;
	}

	CircularDoublyLinkedNode<TData>* cur = this->first_;

	for (int i = 1; i < pos; i++)
		cur = cur->next;

	data = cur->data;

	return true;
}

template<class TData>
inline bool CircularDoublyLinkedList<TData>::setData(int pos, const TData& data)
{
	if (pos < 1 || pos > this->length_)
		return false;

	// 和Android一样的游标
	CircularDoublyLinkedNode<TData>* cur = this->first_;

	for (int i = 1; i < pos; i++)
		cur = cur->next;

	cur->data = data;

	return true;
}

template<class TData>
inline bool CircularDoublyLinkedList<TData>::insert(int prev_pos, const TData& data)
{
	if (prev_pos < 0 || prev_pos > this->length_)
		return false;

	CircularDoublyLinkedNode<TData>* new_node = new CircularDoublyLinkedNode<TData>(data);
	if (!new_node)
		throw bad_alloc();

	// 当前链表为空
	if (!this->first_)
	{
		this->first_ = new_node;

		new_node->next = new_node;
		new_node->prev = new_node;

		this->length_ = 1;

		return true;
	}

	CircularDoublyLinkedNode<TData>* prev_node = this->getData(prev_pos);

	new_node->next = prev_node->next;
	prev_node->next = new_node;
	new_node->next->prev = new_node;
	new_node->prev = prev_node;

	// 插入节点作为首结点
	if (prev_pos == 0)
		this->first_ = new_node;

	this->length_++;

	return true;
}

template<class TData>
inline bool CircularDoublyLinkedList<TData>::remove(int deletion_pos, TData& data)
{
	int step = deletion_pos - 1;

	return this->removeByDirection(step,data,CircularDoublyLinkedList::FORWARD_DIRECTION);
}

template<class TData>
inline void CircularDoublyLinkedList<TData>::print() const
{
	if (!this->first_)
	{
		cout << "Empty list" << endl;
		return;
	}

	cout << "next方向（forward）遍历打印：" << endl;

	CircularDoublyLinkedNode<TData>* cur = this->first_;

	for (int pos = 1; pos <= this->length_; pos++)
	{
		cout << cur->data << "；";
		cur = cur->next;
	}
	cout << endl;

	cout << "prev方向（backward）遍历打印：" << endl;
	for (int pos = 1; pos <= this->length_; pos++)
	{
		cout << cur->data << "；";
		cur = cur->prev;
	}
	cout << endl;
}

template<class TData>
inline CircularDoublyLinkedNode<TData>* CircularDoublyLinkedList<TData>::search(const TData& data) const
{
	CircularDoublyLinkedNode<TData>* cur = this->first_;

	for (int pos = 1; pos <= this->length_; pos++, cur = cur->next)
	{
		if (cur->data == data)
			return cur;
	}
	return NULL;
}

template<class TData>
inline CircularDoublyLinkedNode<TData>* CircularDoublyLinkedList<TData>::getNodeByDirection(int step, int direction) const
{
	if (step < 0 || step >= this->length_)
		return NULL;

	CircularDoublyLinkedNode<TData>* cur = this->first_;

	for (int i = 1; i <= step; i++)
	{
		if (direction == this->BACKWARD_DIRECTION)
			cur = cur->prev;
		else
			cur = cur->next;
	}

	return cur;
}

template<class TData>
inline CircularDoublyLinkedNode<TData>* CircularDoublyLinkedList<TData>::getNode(int pos) const
{
	if (pos == 0)
	{
		return this->first_->prev;
	}

	int step = pos - 1;

	return this->getNodeByDirection(step,CircularDoublyLinkedList::FORWARD_DIRECTION);
}

template<class TData>
inline bool CircularDoublyLinkedList<TData>::removeByDirection(int step, TData& data, int direction)
{

	if (!this->first_)
		return false;

	CircularDoublyLinkedNode<TData>* target_node = this->getNodeByDirection(step,direction);
	if (!target_node)
		return false;

	if (this->length_ == 1)
	{
		data = target_node->data;

		delete target_node;
		this->first_ = NULL;

		this->length_ = 0;

		return true;
	}

	if (target_node == this->first_)
	{
		if (direction == this->FORWARD_DIRECTION)
			this->first_ = target_node->next;
		else if (direction == this->BACKWARD_DIRECTION)
			this->first_ = target_node->prev;
	}

	// 删除操作
	target_node->next->prev = target_node->prev;
	target_node->prev->next = target_node->next;

	data = target_node->data;

	delete target_node;
	target_node = NULL;

	this->length_--;

	return true;
}

template<class TData>
inline void CircularDoublyLinkedList<TData>::clear()
{
	while (this->first_)
	{
		CircularDoublyLinkedNode<TData>* cur_target_node = this->first_;
		this->first_ = cur_target_node->next;

		delete cur_target_node;
		cur_target_node = NULL;
	}

	this->length_ = 0;
}

#endif // !CIRCULAR_DOUBLY_LINKED_LIST_HPP