#ifndef STATIC_LINKED_LIST_HPP
#define STATIC_LINKED_LIST_HPP

#include<iostream>

using namespace std;

template <class TData>
struct StaticLinkedListNode
{
	TData data;
	int next;	// 下一节点的索引

	StaticLinkedListNode<TData>() :next(0) {}

	explicit StaticLinkedListNode<TData>(TData data) : data(data), next(-1) {}

	StaticLinkedListNode<TData>(TData data, int next) : data(data), next(next) {}
};

// 用数组模拟链表
// 说明：pos代表静态数组中的位置，index代表堆区中实体数组
template <class TData>
class StaticLinkedList
{
private:
	// 堆区数组的首地址
	StaticLinkedListNode<TData>* mem_data_;
	int length_;
	int capacity_;

	// 获取插入位置的数组索引
	bool getInsertionIndex_(int& index) const;

	// 扩容静态数组
	bool extend_(int increased_capacity);

	// 由元素在静态链表中的位置（pos）获取其在数组中的位置（数组下标）
	bool getIndexByPos_(int pos, int& index) const;
public:
	static const int NONE = -1; // 表示该数组元素还不在链表中

	static const int HEAD = 0; // 索引为0的下标为静态链表头节点

    // 构造函数(容量)
    explicit StaticLinkedList(int capacity = 100);

    int length() const { return length_; }

    int capacity() const { return capacity_; }

    bool isEmpty() const { return length_ == 0; }

    // 搜索
    bool search(const TData& data, int& pos) const;

    // 插入结点
    bool insert(int prev_pos, const TData& data);

    // 删除结点
    bool remove(int pos, TData& data);

    // 打印
    void print() const;

	const StaticLinkedListNode<TData>& operator[] (int pos);


};



template<class TData>
inline bool StaticLinkedList<TData>::getInsertionIndex_(int& index) const
{
	if (this->length_ == this->capacity_)
		return false;
	
	for (int i = 1; i <= this->length_ + 1; i++)
	{
		// 当前数组下标的实体数组元素还未加入静态链表中	
		if (this->mem_data_[i].next == NONE)
		{
			index = i;
			return true;
		}
	}

	return false;
}

template<class TData>
inline bool StaticLinkedList<TData>::extend_(int increased_capacity)
{
	int old_capacity = this->capacity_;
	this->capacity_ = increased_capacity;

	StaticLinkedListNode<TData>* new_mem_data = new StaticLinkedListNode<TData>[this->capacity_ + 1];

	if (!new_mem_data)
		throw bad_alloc();

	for (int i = HEAD; i <= old_capacity; i++)
	{
		new_mem_data[i] = this->mem_data_[i];
	}

	for (int i = old_capacity + 1; i <= this->capacity_; i++)
	{
		new_mem_data[i].next = NONE;
	}

	delete[] this->mem_data_;
	this->mem_data_ = new_mem_data;

	return true;
}

template<class TData>
inline bool StaticLinkedList<TData>::getIndexByPos_(int pos, int& index) const
{
	if (pos < 0 || pos > this->length_)
		return false;

	if (pos == 0)
	{
		index = HEAD;
		return true;
	}

	int cur_index = this->mem_data_[HEAD].next;
	for (int i = 1; i < pos; i++)
	{
		cur_index = this->mem_data_[cur_index].next;
	}

	index = cur_index;

	return true;
}

template<class TData>
inline StaticLinkedList<TData>::StaticLinkedList(int capacity)
{
	this->capacity_ = capacity;
	this->length_ = 0;

	// 0号元素为“头节点”
	this->mem_data_ = new StaticLinkedListNode<TData>[this->capacity_ + 1];

	if (!this->mem_data_)
		throw bad_alloc();

	this->mem_data_[HEAD].data = 0x3f3f3f3f;
	this->mem_data_[HEAD].next = HEAD;

	for (int i = 1; i < this->capacity_; i++)
	{
		this->mem_data_[i].next = StaticLinkedList<TData>::NONE;
	}
}

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

	for (int cur_pos = 1, i = this->mem_data_[HEAD].next; i != HEAD; i = this->mem_data_[i].next)
	{
		if (this->mem_data_[i].data == data)
		{
			pos = cur_pos;
			return true;
		}

		cur_pos++;
	}

	return false;
}

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

	if (this->length_ == this->capacity_)
		// 如果当前已达最大容量自动扩容一倍
		this->extend_(capacity_);

	int prev_index;
	bool res = this->getIndexByPos_(prev_pos,prev_index);

	if (!res)
		return false;

	// 获取数组中可以利用的“数组空槽位”
	int insertion_index;
	res = this->getInsertionIndex_(insertion_index);

	if (!res)
		return false;

	// 执行插入
	this->mem_data_[insertion_index].next = this->mem_data_[prev_index].next;
	this->mem_data_[prev_index].next = insertion_index;
	this->mem_data_[insertion_index].data = data;

	this->length_++;

	return true;
}

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

	if (pos < 1 || pos > this->length_)
		return false;
	// 找到删除结点的前一个结点
	int prev_index = HEAD;
	for (int i = 1; i < pos; i++)
	{
		prev_index = this->mem_data_[prev_index].next;
	}

	// 删除操作
	int deletion_index = this->mem_data_[prev_index].next;
	this->mem_data_[prev_index].next = this->mem_data_[deletion_index].next;

	// 待删除结点的next设置为NONE(此数组元素不再在链表中)
	this->mem_data_[deletion_index].next = NONE;

	data = this->mem_data_[deletion_index].data;

	this->length_--;

	return true;
}

template<class TData>
inline void StaticLinkedList<TData>::print() const
{
	if (this->length_ == 0)
		cout << "Empty list" << endl;

	for (int cur = this->mem_data_[HEAD].next; cur != HEAD; cur = this->mem_data_[cur].next)
	{
		cout << this->mem_data_[cur].data;
		if (this->mem_data_[cur].next != HEAD)
			cout << "-->";
	}

	cout << endl;
}

template<class TData>
inline const StaticLinkedListNode<TData>& StaticLinkedList<TData>::operator[](int pos)
{
	if (pos < 0 || pos > this->length_)
		return *(new StaticLinkedListNode<int>(0x3f3f3f3f, NONE));
		//return StaticLinkedListNode<int>(0x3f3f3f3f, NONE);
															/*在实践中，某些编译器和环境下，这种情况不会立即导致崩溃或错误，因为：
															内存布局稳定性：即使临时对象的生命周期已经结束，它的内存可能还没有被覆盖，访问这个区域依然能获取到之前的值。
															优化和内存管理：有些编译器可能对临时对象进行优化，使其在特定情况下不会立即销毁。
															但这些都是依赖编译器的行为，不能保证在所有情况下都正常运行。这是一个非常危险的做法，特别是在代码跨平台或者编译器配置不同的情况下。*/

	if (pos == 0)
	{
		return this->mem_data_[HEAD];
	}
		

	int cur = this->mem_data_[HEAD].next;
	for (int i = 1; i != pos ; i++)
	{
		cur = this->mem_data_[cur].next;
	}

	return this->mem_data_[cur];
}
#endif // !STATIC_LINKED_LIST_HPP