#ifndef CIRCULAR_SINGLY_LINKED_LIST_HPP
#define CIRCULAR_SINGLY_LINKED_LIST_HPP

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

using namespace std;

template <class TData>
struct CircularSinglyLinkedNode
{
	TData data;
	CircularSinglyLinkedNode<TData>* next;

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

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

template <class TData>
class CircularSinglyLinkedList :public LinearList<TData>
{
private:
	CircularSinglyLinkedNode<TData>* first_;
	CircularSinglyLinkedNode<TData>* last_;
	int length_;

public:
	CircularSinglyLinkedList() :
		first_(NULL), last_(NULL), length_(0) {}

	~CircularSinglyLinkedList();

	// 获取容器长度
	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;

	CircularSinglyLinkedNode<TData>* search(const TData& data) const;

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

	void clear();
};



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

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

	CircularSinglyLinkedNode<TData>* cur = this->first_;
	for (int i = 1; i < pos; i++)
		cur = cur->next;


	data = cur->data;

	return true;
}

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

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

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

	cur->data = data;

	return true;
}

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

	CircularSinglyLinkedNode<TData>* new_node = new CircularSinglyLinkedNode<TData>(data);

	if (new_node == NULL)
		throw bad_alloc();

	if (this->length_ == 0)
	{
		this->first_ = new_node;
		this->first_->next = this->first_;

		this->last_ = this->first_;

		this->length_ = 1;
		return true;
	}

	CircularSinglyLinkedNode<TData>* prev_node = this->getNode(prev_pos);

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

	if (prev_node == 0)
		this->first_ = new_node;

	if (new_node->next == this->first_)
		this->last_ = new_node;

	this->length_++;

	return true;
}

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

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

		delete this->first_;
		this->first_ = NULL;
		this->last_ = NULL;

		this->length_ = 0;

		return true;
	}

	if (deletion_pos == 1)
	{
		data = this->first_->data;

		CircularSinglyLinkedNode<TData>* deletion_node = this->first_;

		this->last_->next = this->first_->next;
		this->first_ = this->first_->next;

		delete deletion_node;
		deletion_node = NULL;

		this->length_--;

		return true;
	}

	// 其他情况
	CircularSinglyLinkedNode<TData>* prev_node = this->getNode(deletion_pos - 1);
	CircularSinglyLinkedNode<TData>* deletion_node = prev_node->next;

	if (deletion_node == this->last_)
		this->last_ = prev_node;

	data = deletion_node->data;

	prev_node->next = deletion_node->next;

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

	this->length_--;

	return true;
}

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

	cout << "打印循环单链表：{ ";
	CircularSinglyLinkedNode<TData>* cur = this->first_;

	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 CircularSinglyLinkedNode<TData>* CircularSinglyLinkedList<TData>::search(const TData& data) const
{
	CircularSinglyLinkedNode<TData>* cur = this->first_;

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

template<class TData>
inline CircularSinglyLinkedNode<TData>* CircularSinglyLinkedList<TData>::getNode(int pos) const
{
	if (pos < 0 || pos > this->length_)
		return NULL;

	if (pos == 0)
		return this->last_;

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

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

	return cur;
}

template<class TData>
inline void CircularSinglyLinkedList<TData>::clear()
{
	if (this->first_ == NULL)
		return;

	for (int i = 1; i <= this->length_; i++)
	{
		CircularSinglyLinkedNode<TData>* target_node = this->first_;
		this->first_ = target_node->next;

		delete target_node;
		target_node = NULL;
	}

	this->first_ = NULL;
	this->last_ = NULL;

	this->length_ = 0;
}
#endif // !CIRCULAR_SINGLY_LINKED_LIST_HPP