#ifndef SEQ_LIST_HPP
#define SEQ_LIST_HPP

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

using namespace std;

//模板类的实现需要和声明放在同一个头文件中

template<class TData>
class SeqList :public LinearList<TData>
{
private:
	// 数据项数组
	TData* mem_data_;
	// 容量（最大长度）
	int capacity_;
	// 最后一项的数组索引
	int last_index_;
public:
	// C++提供了初始化列表语法，用来初始化属性
	// 此方法为函数实现
	SeqList() :mem_data_(NULL), capacity_(0), last_index_(-1) {}

	// explicit 关键字确保这个构造函数不会被用于隐式类型转换
	// 隐式转换：MyClass obj = 10; 隐式调用了 MyClass(int) 构造函数
	explicit SeqList(int capacity);

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

	// 此方法为函数实现
	~SeqList()
	{
		if (mem_data_ != NULL)
			delete[] mem_data_;
	}

	int capacity() const { return capacity_; }

	virtual int length() const override { return last_index_ + 1; }

	int search(const TData& data) const;

	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;

	bool isFull() const;

	// 调整顺序表的容量
	bool resetCapacity(int capacity);

	void sort();

	virtual void print() const override;

	// 复制函数
	SeqList<TData>& operator=(const SeqList<TData>& seq_list);

};


template<class TData>
SeqList<TData>::SeqList(int capacity): capacity_(capacity), last_index_(-1)
{
	if (capacity < 0)
		throw out_of_range("capacity < 0");

	this->mem_data_ = new TData[this->capacity_];
	if (!this->mem_data_)
		throw bad_alloc();
}

template<class TData>
SeqList<TData>::SeqList(const SeqList<TData>& seq_list)
{
	this->capacity = seq_list.capacity();
	this->last_index_ = seq_list.length() - 1;

	if (this->capacity_ == 0)
		return;

	this->mem_data_ = new TData[this->capacity()];
	if (!this->mem_data_)
		throw bad_alloc();

	for (int pos = 1; pos <= seq_list.length(); pos++)
	{
		TData cur_data;
		// seq_list位置pos的变量赋给cur_data
		seq_list.getData(pos, cur_data);

		this->mem_data_[pos - 1] = cur_data;
	}
}

template<class TData>
bool SeqList<TData>::resetCapacity(int capacity)
{
	if (capacity < this->length())
		return false;

	TData* new_mem_data = new TData[capacity];
	if (new_mem_data == NULL)
		throw bad_alloc();

	for (int i = 0; i < this->length(); i++)
		new_mem_data[i] = this->mem_data_[i];

	// 释放旧的顺序表占用的堆空间
	delete[] this->mem_data_;
	// 调整指针指向
	this->mem_data_ = new_mem_data;

	this->capacity_ = capacity;

	return true;
}

template<class TData>
int SeqList<TData>::search(const TData& data) const
{
	for (int i = 0; i <= this->last_index_; i++)
	{
		if (this->mem_data_[i] == data)
			return i + 1;
	}

	return 0; // 没找到
}

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

	data = this->mem_data_[pos - 1];

	return true;
}

template<class TData>
bool SeqList<TData>::setData(int pos, const TData& data)
{
	if (pos <= 0 || pos > this->last_index_ + 1)
		return false;

	this->mem_data_[pos - 1] = data;

	return true;
}

template<class TData>
bool SeqList<TData>::insert(int prev_pos, const TData& data)
{
	if (this->last_index_ == this->capacity_ - 1)
		// 此时容器已满，无法执行插入操作
		return false;

	if (prev_pos < 0 || prev_pos > this->last_index_ + 1)
		return false;

	for (int i = this->last_index_; i >= prev_pos; i--)
		// 向后移动一个元素位置，腾出下标prev_pos的元素
		this->mem_data_[i + 1] = this->mem_data_[i];

	this->mem_data_[prev_pos] = data;

	this->last_index_++;

	return true;
}

template<class TData>
bool SeqList<TData>::remove(int deletion_pos, TData& data)
{
	if (this->last_index_ == -1)
		// 容器为空
		return false;

	if (deletion_pos < 1 || deletion_pos > this->length())
		return false;

	// 返回删除元素
	data = this->mem_data_[deletion_pos - 1];

	for (int i = deletion_pos; i <= this->last_index_; i++)
		// 各元素向前移动一位
		this->mem_data_[i - 1] = this->mem_data_[i];

	this->last_index_--;

	return true;
}

template<class TData>
bool SeqList<TData>::isEmpty() const
{
	if (this->last_index_ == -1)
		return true;
	return false;
}

template<class TData>
bool SeqList<TData>::isFull() const
{
	if (this->last_index_ == this->capacity_ - 1)
		return true;
	return false;
}


template<class TData>
void bubbleSort(SeqList<TData>& seq_list)
{
	int length = seq_list.length();

	for (int i = 1; i <= length - 1; i++)
	{
		for (int j = 0; j < length - i; j++) 
		{
			int j_ = j + 1;
			TData j_data;
			seq_list.getData(j_, j_data);

			TData j_next_data;
			seq_list.getData(j_+1, j_next_data);

			if (j_data > j_next_data)
			{
				seq_list.setData(j_, j_next_data);
				seq_list.setData(j_+1, j_data);
			}
		}
	}
	
}

template<class TData>
void selectSort(SeqList<TData>& seq_list)
{
	// 选择排序：从第一个元素开始，拿着每一个索引上的元素跟后面的元素依次比较，
	//			 小的放前面，大的放后面，以此类推。
	int length = seq_list.length();

	for (int i = 1; i <= length - 1; i++)
	{
		for (int j = i + 1; j <= length; j++)
		{
			TData i_data;
			seq_list.getData(i, i_data);

			TData j_data;
			seq_list.getData(j, j_data);

			if (i_data > j_data)
			{
				seq_list.setData(i,j_data);
				seq_list.setData(j,i_data);
			}
		}
	}

}

template<class TData>
void insertSort(SeqList<TData>& seq_list)
{
	// 插入排序：将第一个元素到第N个元素看作是有序的（真实有序的，单个元素也有序）,
	//			 把N+1索引的元素到最后一个当成是无序的。遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，
	//			 如遇到相同数据，插在后面（维持稳定性）。
	int length = seq_list.length();

	int startIndex = 2; // 认为第一个元素是有序的,startIndex存储的是第一个无序数据的下标

	for (int i = startIndex; i <= length; i++)
	{
		// 执行“排序操作”
		int j = i;

		TData j_data;
		seq_list.getData(j, j_data);

		TData j_prev_data;
		seq_list.getData(j - 1, j_prev_data);

		while (j > 1 && j_prev_data > j_data )
		{
			seq_list.setData(j, j_prev_data);
			seq_list.setData(j-1, j_data);

			j--;

			seq_list.getData(j, j_data);
			seq_list.getData(j - 1, j_prev_data);
		}
	}
}

template<class TData>
void quickSort(SeqList<TData>& seq_list, int i, int j)
{
	// 定义两个变量记录要查找的范围
	int start = i;
	int end = j;

	if (start > end)
		return;

	// 基准元素
	TData baseNumber;
	seq_list.getData(i,baseNumber);

	TData rightNumber;
	TData leftNumber;
	while (start != end)
	{
		// 先从右边开始找
		while (true)
		{
			seq_list.getData(end,rightNumber);

			if (end <= start || rightNumber < baseNumber)
				break;

			end--;
		}

		// 再从左边开始找
		while (true)
		{
			seq_list.getData(start, leftNumber);

			if (end <= start || leftNumber > baseNumber)
				break;

			start++;
		}

		// 把end和start指向的元素进行交互
		seq_list.setData(start,rightNumber);
		seq_list.setData(end,leftNumber);
	}
	//当start和end指向了同一个元素的时候，那么上面的循环就会结束
	//表示已经找到了基准数在数组中应存入的位置
	//基准数归位
	//就是拿着这个范围中的第一个数字，跟start或end指向的元素进行交换
	seq_list.setData(i, rightNumber);
	seq_list.setData(end, baseNumber);

	//确定6左边的范围，重复刚刚所做的事情
	quickSort(seq_list, i, start - 1);
	//确定6右边的范围，重复刚刚所做的事情
	quickSort(seq_list, start + 1, j);

}

template<class TData>
void SeqList<TData>::sort()
{
	//bubbleSort(*this);
	//selectSort(*this);
	//insertSort(*this);
	quickSort(*this, 1, (*this).length());
}

template<class TData>
void SeqList<TData>::print() const
{
	if (this->last_index_ == -1)
	{
		cout << "顺序表为空" << endl;
		return;
	}

	for (int i = 0; i <= this->last_index_; i++)
		cout << "位置（从1开始）" << i + 1 << "：" << this->mem_data_[i] << endl;
}

template<class TData>
SeqList<TData>& SeqList<TData>::operator=(const SeqList<TData>& seq_list)
{
	if (&seq_list == this)
		return *this;

	bool res = this->resetCapacity(seq_list.capacity());
	if (!res)
		throw length_error("seq_list length wrong");

	int length = seq_list.length();

	for (int i = 1; i <= length; i++)
	{
		TData cur_data;
		seq_list.getData(i, cur_data);

		this->mem_data_[i - 1] = cur_data;

		this->last_index_++;
	}

	return *this;
}

#endif // !SEQ_LIST_HPP