#ifndef DOUBLY_LINKED_LIST_HPP
#define DOUBLY_LINKED_LIST_HPP

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

using namespace std;

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

	// 没有数据的双向链表节点
	explicit DoublyLinkedNode(DoublyLinkedNode<TData>* next = NULL, DoublyLinkedNode<TData>* prev = NULL):
		next(next), prev(prev) {}

	// 有数据的双向链表节点
	explicit DoublyLinkedNode(const TData& data, DoublyLinkedNode<TData>* next = NULL, DoublyLinkedNode<TData>* prev = NULL) :
		data(data), next(next), prev(prev) {}
};

template<class TData>
class DoublyLinkedList : public LinearList<TData>
{
private:
	DoublyLinkedNode<TData>* head_; // 头节点
	DoublyLinkedNode<TData>* tail_; // 尾节点

	int length_; // 链表长度

	// 子链表搜索（递归）
	DoublyLinkedList<TData>* searchInSubListRecursive_(DoublyLinkedNode<TData>* sub_list_first_element, const TData& data) const;
public:
	DoublyLinkedList();

	~DoublyLinkedList();

	// 获取容器长度
	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->head_->next == this->head_; };

	virtual void print() const override;

	// 获取节点
	DoublyLinkedNode<TData>* getNode(int pos) const;

	// 搜索
	DoublyLinkedNode<TData>* search(const TData& data) const;

	// 搜索（递归）
	DoublyLinkedNode<TData>* searchRecursive(const TData& data) const;

	void clear();
};



template<class TData>
inline DoublyLinkedList<TData>* DoublyLinkedList<TData>::searchInSubListRecursive_(DoublyLinkedNode<TData>* sub_list_first_element, const TData& data) const
{
	if (!sub_list_first_element)
		return NULL;

	if (sub_list_first_element->data == data)
		return sub_list_first_element;

	return searchInSubListRecursive_(sub_list_first_element->next,data);
}

template<class TData>
inline DoublyLinkedList<TData>::DoublyLinkedList()
{
	this->head_ = new DoublyLinkedNode<TData>();
	if (!this->head_)
		throw bad_alloc();

	this->tail_ = new DoublyLinkedNode<TData>();
	if (!this->tail_)
		throw bad_alloc();

	this->head_->next = this->tail_;
	this->head_->prev = NULL;

	this->tail_->next = NULL;
	this->tail_->prev = this->head_;

	this->length_ = 0;
}

template<class TData>
inline DoublyLinkedList<TData>::~DoublyLinkedList()
{
	this->clear();
	delete this->head_;
	delete this->tail_;
}

template<class TData>
inline bool DoublyLinkedList<TData>::getData(int pos, TData& data) const
{

	if (pos < 1 || pos > this->length_)
		return false;

	DoublyLinkedNode<TData>* cur = this->head_;
	for (int i = 0; i < pos; i++)
		cur = cur->next;

	data = cur->data;

	return true;
}

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

	DoublyLinkedNode<TData>* cur = this->head_;
	for (int i = 0; i < pos; i++)
		cur = cur->next;

	cur->data = data;

	return true;
}

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

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

	// 获取插入位置前面的那一个元素
	DoublyLinkedNode<TData>* prev_node = this->getNode(prev_pos);

	// 执行插入操作
	new_node->next = prev_node->next;
	prev_node->next = new_node;

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

	this->length_++;

	return true;
}

template<class TData>
inline bool DoublyLinkedList<TData>::remove(int deletion_pos, TData& data)
{
	if (deletion_pos > this->length_ || deletion_pos < 1)
		return false;

	DoublyLinkedNode<TData>* target_node = this->getData(deletion_pos);

	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 DoublyLinkedList<TData>::print() const
{
	if (this->length_ == 0) 
	{
		cout << "Empty list" << endl;
		return;
	}

	cout << "打印双向链表：{";
	DoublyLinkedNode<TData>* cur = this->head_->next;
	for (int pos = 1; pos <= this->length_; pos++) 
	{
		cout << cur->data;
		if (pos != this->length_)
		{
			cout << "<-->";
		}
		cur = cur->next;
	}

	cout << " }" << endl;

}

template<class TData>
inline DoublyLinkedNode<TData>* DoublyLinkedList<TData>::getNode(int pos) const
{
	if (pos < 1 || pos > this->length_)
		return false;

	DoublyLinkedNode<TData>* cur = this->head_;
	for (int i = 0; i < pos; i++)
		cur = cur->next;

	return cur;
}

template<class TData>
inline DoublyLinkedNode<TData>* DoublyLinkedList<TData>::search(const TData& data) const
{
	for (DoublyLinkedNode<TData>* cur = this->head_->next; cur != NULL; cur = cur->next)
	{
		if (cur->data == data)
			return cur;
	}
	return NULL;
}

template<class TData>
inline DoublyLinkedNode<TData>* DoublyLinkedList<TData>::searchRecursive(const TData& data) const
{
	DoublyLinkedNode<TData>* node = searchInSubListRecursive_(this->head_,data);
	
	return node;
}

template<class TData>
inline void DoublyLinkedList<TData>::clear()
{

	int length = this->length_;
	for (int i = 1; i <= this->length_; i++)
	{
		TData target_data;
		this->remove(1,target_data);
	}

}
#endif // !DOUBLY_LINKED_LIST_HPP