#ifndef SINGLY_LINKED_LIST_HPP
#define SINGLY_LINKED_LIST_HPP

/*		code		*/
#include <iostream>
#include <cstddef>
#include <exception>
#include "linear_list.h"

using namespace std;

namespace singly_linked_list
{
	template<class TData>
	struct LinkedNode
	{
		TData data; // 节点数据
		LinkedNode<TData>* next; // 指向下一个节点的指针

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

		LinkedNode(const TData& data, LinkedNode<TData>* node = NULL) :data(data), next(node) {}
	};
}

template<class TData>
class SinglyLinkedList :public LinearList<TData>
{
private:
	// 链表头节点
	singly_linked_list::LinkedNode<TData>* head_;
	// 链表长度
	int length_;
public:
	SinglyLinkedList();

	// 复制（拷贝）构造函数
	SinglyLinkedList(const SinglyLinkedList<TData>& src_linked_list);

	~SinglyLinkedList();

	void clear();

	virtual int length() const override { return this->length_; }

	// 获取头节点
	singly_linked_list::LinkedNode<TData>* head() const { return this->head_; }

	singly_linked_list::LinkedNode<TData>* search(TData data) const;

	singly_linked_list::LinkedNode<TData>* getNode(int pos) const;

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

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

	// 插入数据
	virtual bool insert(int prev_pos, const TData& data) override;

	// 插入节点
	bool insert(int prev_pos, const singly_linked_list::LinkedNode<TData>* node);

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

	virtual bool isEmpty() const override;

	virtual void print() const override;
};

#endif // !SINGLY_LINKED_LIST_HPP

template<class TData>
inline SinglyLinkedList<TData>::SinglyLinkedList(): length_(0)
{
	this->head_ = new singly_linked_list::LinkedNode<TData>();
	if (!this->head_)
		throw bad_alloc();

}

template<class TData>
inline SinglyLinkedList<TData>::SinglyLinkedList(const SinglyLinkedList<TData>& src_linked_list):length_(0)
{
	this->head_ = new singly_linked_list::LinkedNode<TData>();
	if (!this->head_)
		throw bad_alloc();

	singly_linked_list::LinkedNode<TData>* src_list_cur = src_linked_list.head();
	singly_linked_list::LinkedNode<TData>* cur = this->head();

	while (src_list_cur->next)
	{
		TData data = src_list_cur->next->data;
		// 尾插法
		cur->next = new singly_linked_list::LinkedNode<TData>(data);
		// 移动目的容器指针到下一个元素
		cur = cur->next;

		// 移动源数据指针到下一个元素
		src_list_cur = src_list_cur->next;

		this->length_++;
	}
	// 单链表末尾为“空”
	cur->next = NULL;
}

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

	if (this->head_)
	{
		delete this->head_;
		this->head_ = NULL;
	}
}

template<class TData>
inline void SinglyLinkedList<TData>::clear()
{
	while (this->head_->next)
	{
		// 头删法
		singly_linked_list::LinkedNode<TData>* cur = this->head_->next;
		this->head_->next = cur->next;

		delete cur;
		this->length_--;
	}
}

template<class TData>
inline singly_linked_list::LinkedNode<TData>* SinglyLinkedList<TData>::search(TData data) const
{
	singly_linked_list::LinkedNode<TData>* cur = this->head_->next;
	if (!cur)
		// 为空
		return NULL;
	
	while (cur)
	{
		if (cur->data == data)
			break;

		cur = cur->next;
	}

	return cur;
}

template<class TData>
inline singly_linked_list::LinkedNode<TData>* SinglyLinkedList<TData>::getNode(int pos) const
{
	if (pos < 1 || pos > this->length_)
		return NULL;
	
	singly_linked_list::LinkedNode<TData>* cur = this->head_;

	while (pos)
	{
		cur = cur->next;
		pos--;
	}
	return cur;
}

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

	singly_linked_list::LinkedNode<TData>* cur = this->head_;

	// 链表只能顺序查找
	while (pos > 0)
	{
		cur = cur->next;
		pos--;
	}

	data = cur->data;

	return true;
}

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

	singly_linked_list::LinkedNode<TData>* cur = this->head_;

	while (pos > 0)
	{
		cur = cur->next;
		pos--;
	}

	cur->data = data;

	return data;
}

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

	singly_linked_list::LinkedNode<TData>* node = new singly_linked_list::LinkedNode<TData>(data);

	if (!node)
		throw bad_alloc();

	singly_linked_list::LinkedNode<TData>* cur = this->head_;

	// 找到要插入的位置
	while (prev_pos > 0)
	{
		cur = cur->next;
		prev_pos--;
	}

	node->next = cur->next;
	cur->next = node;

	this->length_++;

	return true;
}

template<class TData>
inline bool SinglyLinkedList<TData>::insert(int prev_pos, const singly_linked_list::LinkedNode<TData>* node)
{
	if (prev_pos < 0 || prev_pos > this->length_)
		return false;

	if (!node)
		throw bad_alloc();

	singly_linked_list::LinkedNode<TData>* cur = this->head_;

	while (prev_pos > 0)
	{
		cur = cur->next;
		prev_pos--;
	}

	node->next = cur->next;
	cur->next = node;

	this->length_++;

	return true;
}

template<class TData>
inline bool SinglyLinkedList<TData>::remove(int deletion_pos, TData& data)
{
	if (this->length_ == 0 || deletion_pos < 1 
		|| deletion_pos > this->length_)
		return false;
	
	singly_linked_list::LinkedNode<TData>* cur = this->head_;

	while (deletion_pos)
	{
		cur = cur->next;
		deletion_pos--;
	}

	singly_linked_list::LinkedNode<TData>* temp = cur->next;

	cur->next = temp->next;

	data = temp->data;

	delete temp;
	temp = NULL;

	this->length_--;
	return true;

}

template<class TData>
inline bool SinglyLinkedList<TData>::isEmpty() const
{
	if (!this->head_->next)
		return true;
	else
		return false;
}

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

	singly_linked_list::LinkedNode<TData>* cur = this->head_->next;

	while (cur)
	{
		cout << cur->data << " ";
		cur = cur->next;
	}
	cout << endl;
}