#pragma once

#include <stdexcept>
#include <iostream>
#include <cstdlib>

using namespace std;

namespace sparse_matrix
{
	template <class TValue>
	struct TriTuple
	{
		int row; // 行索引
		int col; // 列索引
		TValue value; // 值
		
		// 重载=号，使默认的浅拷贝变成深拷贝
		// 有返回值是为了实现“a = b = c”的效果，即链式编程
		TriTuple<TValue>& operator=(const TriTuple<TValue>& tri_tuple)
		{
			if (&tri_tuple == this)
				return *this;

			row = tri_tuple.row;
			col = tri_tuple.col;
			value = tri_tuple.value;

			return *this;
		}
	};
}

template <class TValue>
class SparseMatrix
{
	// 重载<<，实现打印稀疏矩阵的功能
	friend ostream& operator<<<>(ostream& out, SparseMatrix<TValue>& sparse_matrix);

	// 重载>>，实现输入稀疏矩阵的功能
	friend istream& operator>><>(istream& in, SparseMatrix<TValue>& sparse_matrix);

	friend void delElememt(SparseMatrix<TValue>& sparse_matrix, int index);

private:
	int rows_; // 稀疏矩阵的行数
	int cols_; // 稀疏矩阵的列数
	int size_; // 三元组数组当前已有元素数
	int capacity_; // 三元组数组可容纳的最大元素数
	sparse_matrix::TriTuple<TValue>* elements_; // 三元组数组，每一个三元组记录稀疏矩阵中的非0元素的行列下标及其存储的值

public:
	explicit SparseMatrix(int capacity = 10);

	SparseMatrix(const SparseMatrix<TValue>& sparse_matrix);

	/*析构函数前加上 virtual 关键字的主要作用是 确保在继承关系中正确地调用析构函数，从而避免内存泄漏和资源未释放的情况。
	具体来说，virtual 关键字的意义在于允许 动态绑定，确保当你通过基类指针或引用删除对象时，调用的是实际派生类的析构函数，而不是仅仅调用基类的析构函数。*/
	virtual ~SparseMatrix() { delete[] this->elements_; }

	int getRows() const { return this->rows_; }

	void setRows(int rows) { this->rows_ = rows; }

	int getCols() const { return this->cols_; }

	void setCols(int cols) { this->cols_ = cols; }

	/*! @brief **获取元素数** */
	int getSize() const { return this->size_; }
	/*! @brief **设置元素数** */
	void setSize(int size) { this->size_ = size; }

	/*! @brief **获取容量** */
	int getCapacity() const { return this->capacity_; }
	/*! @brief **设置最大元素数** */
	void setCapacity(int capacity) { this->capacity_ = capacity; }

	bool getElement(int row, int col, TValue& value);

	bool setElement(int row, int col, TValue& value);

	// 转置运算
	SparseMatrix<TValue>* transpose();

	// 优化的转置运算
	SparseMatrix<TValue>* fastTranspose();

	// 矩阵加法 // to do
	SparseMatrix<TValue>& add(SparseMatrix<TValue>& sparse_matrix);

	// 矩阵乘法 //to do
	SparseMatrix<TValue>& multiply(SparseMatrix<TValue>& sparse_matrix);
};

template <typename TValue>
inline istream& operator>>(istream& in, SparseMatrix<TValue>& sparse_matrix)
{
	cout << "输入rows，cols和size(从1开始)" << endl;

	int rows = 0;
	int cols = 0;
	int size = 0;

	in >> rows >> cols >> size;

	if (size > sparse_matrix.capacity_)
		throw length_error("size wrong");

	sparse_matrix.setRows(rows);
	sparse_matrix.setCols(cols);
	sparse_matrix.setSize(size);


	for (int i = 0; i < sparse_matrix.size_; i++)
	{
		cout << "输入第" << i + 1 << "个row，colum和term的值" << endl;
		in >> sparse_matrix.elements_[i].row
			>> sparse_matrix.elements_[i].col
			>> sparse_matrix.elements_[i].value;
	}

	cout << sparse_matrix << endl;

	return in;
}

template <typename TValue>
ostream& operator<<(ostream& out, SparseMatrix<TValue>& sparse_matrix)
{
	out << "rows = " << sparse_matrix.getRows() << endl;
	out << "cols = " << sparse_matrix.getCols() << endl;

	out << "NonZero element count：" << sparse_matrix.getSize() << endl;

	for (int i = 0; i < sparse_matrix.getSize(); i++)
	{
		out << "sparse_martix[" << sparse_matrix.elements_[i].row << "][" <<
			sparse_matrix.elements_[i].col << "] = " <<
			sparse_matrix.elements_[i].value << endl;
	}

	return out;
}

template<class TValue>
inline SparseMatrix<TValue>::SparseMatrix(int capacity)
	:rows_(0),cols_(0),size_(0),capacity_(capacity)
{
	if (capacity <= 0)
		throw length_error("wrong max size");

	this->elements_ = new sparse_matrix::TriTuple<TValue>[this->capacity_];
	if (!this->elements_)
		throw bad_alloc();
}

template<class TValue>
inline SparseMatrix<TValue>::SparseMatrix(const SparseMatrix<TValue>& sparse_matrix)
	:rows_(sparse_matrix.getRows()),cols_(sparse_matrix.getCols()),
	size_(sparse_matrix.getSize()),capacity_(sparse_matrix.getCapacity())
{
	this->elements_ = new sparse_matrix::TriTuple<TValue>[this->capacity_];
	if (!this->elements_)
		throw bad_alloc();

	for (int i = 0; i < this->size_; i++)
	{
		this->elements_[i] = sparse_matrix.elements_[i];
	}
}

template<class TValue>
inline bool SparseMatrix<TValue>::getElement(int row, int col, TValue& value)
{
	for (int i = 0; i < this->getSize(); i++)
	{
		if (this->elements_[i].row == row && this->elements_[i].col == col)
		{
			value = this->elements_[i].value;
			return true;
		}
	}
	return false;
}

template <typename TValue>
void swap_(sparse_matrix::TriTuple<TValue>* a, sparse_matrix::TriTuple<TValue>* b)
{
	sparse_matrix::TriTuple<TValue> temp = *a;
	*a = *b;
	*b = temp;
}

template<class TValue>
inline bool SparseMatrix<TValue>::setElement(int row, int col, TValue& value)
{
	if (row >= this->rows_ || col >= this->cols_)
		return false;

	if (this->size_ == this->capacity_ || this->size_ == this->rows_ * this->cols_)
		return false;

	// ---------- 2 获取该位置在elements_数组中对应的索引 ----------

	// 这里的index是为了保证三元组数组是按照row从小到大，当row相同时，按照col从小到大排序
	int index = -1;
	for (int i = 0; i < this->size_; i++)
	{
		if (this->elements_[i].row == row)
		{
			if (this->elements_[i].col >= col)
			{
				index = i;
				break;
			}
		}
		else if (this->elements_[i].row > row)
		{
			index = i;
			break;
		}
	}

	// ---------- 3 更新非0元素的情况处理 ----------

	if (index != -1 
		&& this->elements_[index].row == row 
		&& this->elements_[index].col == col)
	{
		this->elements_[index].value = value;
		return true;
	}

	// ---------- 4 插入新元素的情况处理 ----------

	if (index == -1)
		index = this->size_;

	// 新插入的三元组首先先插入到最后的位置
	this->elements_[this->size_].row = row;
	this->elements_[this->size_].col = col;
	this->elements_[this->size_].value = value;

	// 通过这个循环移动新插入的三元组到其合适的位置
	for (int i = this->size_; i > index; i--)
	{
		swap_(&this->elements_[i],&this->elements_[i-1]);
	}

	// ---------- 5 更新size ----------

	this->size_++;                                                      // size_加1

	// ---------- 6 退出函数 ----------

	return true;
}

// O(n) = T(n^2)
template<class TValue>
inline SparseMatrix<TValue>* SparseMatrix<TValue>::transpose()
{
	SparseMatrix<TValue>* trans_sparse_martix = new SparseMatrix<TValue>(this->capacity_);

	trans_sparse_martix->setRows(this->getCols());
	trans_sparse_martix->setCols(this->getRows());
	trans_sparse_martix->setSize(this->getSize());

	// 原稀疏矩阵内的元素都为0
	if (this->size_ == 0)
		return trans_sparse_martix;
	

	// 转置操作
	int cur_elements_index = 0;

	for (int row = 0; row < trans_sparse_martix->getRows(); row++)
	{
		for (int i = 0; i < this->size_; i++)
		{
			if (this->elements_[i].col == row)
			{
				trans_sparse_martix->elements_[cur_elements_index].row = row;
				trans_sparse_martix->elements_[cur_elements_index].col = this->elements_[i].row;
				trans_sparse_martix->elements_[cur_elements_index].value = this->elements_[i].value;

				cur_elements_index++;
			}
		}
	}


	return trans_sparse_martix;
}

// O(n) = T(n)，以空间换时间
template<class TValue>
inline SparseMatrix<TValue>* SparseMatrix<TValue>::fastTranspose()
{
	// 辅助数组
	int* row_sizes = new int[this->cols_]; // 表示原稀疏数组每列（该数组的下标就代表第几列）有多少个非0元素
	int* iterator_positions = new int[this->cols_]; // 表示原稀疏数组每列第一个元素的在转置后的三元组数组中的位置，若下标为index，则表示第index目前的元素应该放到转置后的三元组数组的iterator_positions[index]位置
	
	// 给转置后的稀疏矩阵的三元组数组分配内存
	SparseMatrix<TValue>* trans_sparse_matrix = new SparseMatrix<TValue>(this->capacity_);
	if (!trans_sparse_matrix)
		throw bad_alloc();

	trans_sparse_matrix->setRows(this->cols_);
	trans_sparse_matrix->setCols(this->rows_);
	trans_sparse_matrix->setSize(this->size_);

	// 原稀疏矩阵内元素都为0
	if (this->size_ == 0)
		return trans_sparse_matrix;

	// 构造row_sizes
	for (int i = 0; i < this->cols_; i++)
	{
		// 初始化全为0
		row_sizes[i] = 0;
	}

	for (int i = 0; i < this->size_; i++)
	{
		// 计算原稀疏数组中每列的非0元素有几个
		int cur_row = this->elements_[i].col;
		row_sizes[cur_row]++;
	}

	// 构造iterator_positions
	iterator_positions[0] = 0; // 第0列的第一个非0元素在转置后的稀疏矩阵的三元组数组中的位置是0（开始）
	for (int row = 1; row < this->getCols(); row++)
	{
		iterator_positions[row] = iterator_positions[row - 1] + row_sizes[row - 1];
	}

	// 快速转置，上面的辅助数组，row_size作用是为了构造iterator_positions，真正有用的便是iterator_positions
	for (int i = 0; i < this->size_; i++)
	{
		int row = this->elements_[i].col;
		int cur_elememts_index = iterator_positions[row];

		trans_sparse_matrix->elements_[cur_elememts_index].row = this->elements_[i].col;
		trans_sparse_matrix->elements_[cur_elememts_index].col = this->elements_[i].row;
		trans_sparse_matrix->elements_[cur_elememts_index].value = this->elements_[i].value;

		iterator_positions[row]++;
	}

	delete[] iterator_positions;
	delete[] row_sizes;

	return trans_sparse_matrix;
}

template<class TValue>
inline SparseMatrix<TValue>& SparseMatrix<TValue>::add(SparseMatrix<TValue>& sparse_matrix)
{
	if (this->cols_ != sparse_matrix.cols_ || this->rows_ != sparse_matrix.rows_)
		return *this;

	// 在堆区创建对象并使用拷贝构造函数
	SparseMatrix<TValue>* new_matrix = new SparseMatrix<TValue>(*this);

	int cur_element_index = 0;

	for (int i = 0; i < new_matrix->getSize(); i++)
	{
		if (cur_element_index == sparse_matrix.getSize() - 1)
			break;

		for (int j = cur_element_index; j < sparse_matrix.getSize(); j++)
		{
			if (sparse_matrix.elements_[j].row != new_matrix->elements_[i].row)
				break;

			if (sparse_matrix.elements_[j].row == new_matrix->elements_[i].row
				&& sparse_matrix.elements_[j].col == new_matrix->elements_[i].col)
			{
				new_matrix->elements_[i].value += sparse_matrix.elements_[j].value;

				if (j == cur_element_index)
					break;
				else
				{
					for (int z = cur_element_index; z < j; z++)
					{
						new_matrix->setElement(sparse_matrix.elements_[z].row,sparse_matrix.elements_[z].col,sparse_matrix.elements_[z].value);
						cur_element_index = j + 1;
					}
				}
			}
		}

	}

	if (cur_element_index != sparse_matrix.getSize() - 1)
	{
		for (int i = cur_element_index; i < sparse_matrix.getSize(); i++)
		{
			new_matrix->setElement(sparse_matrix.elements_[i].row, sparse_matrix.elements_[i].col, sparse_matrix.elements_[i].value);
		}
	}

	return *new_matrix;
}

template<class TValue>
inline SparseMatrix<TValue>& SparseMatrix<TValue>::multiply(SparseMatrix<TValue>& sparse_matrix)
{
	if (this->rows_ != sparse_matrix.cols_ || this->cols_ != sparse_matrix.rows_)
		return *this;

	SparseMatrix<TValue>* new_matrix = new SparseMatrix<TValue>(*this);
	SparseMatrix<TValue>* res_matrix = new SparseMatrix<TValue>();

	res_matrix->setRows(this->rows_);
	res_matrix->setCols(sparse_matrix.cols_);
	res_matrix->setSize(this->size_);
	res_matrix->setCapacity(this->capacity_);

	// 转置sparse_matrix
	sparse_matrix = sparse_matrix.fastTranspose();

	int left = 0, right = -1; // 代表new_matrix的同一行的区间范围
	bool find1 = false;

	int up = 0, down = -1; // 代表sparse_matrix的同一列的区间范围
	bool find2 = false;

	for (int i = 0; i < new_matrix->getRows(); i++)
	{
		find1 = find2 = false;


		// 找到left的值
		for (int j = left; j < new_matrix->getSize(); j++)
		{
			if (new_matrix->elements_[j].row == i)
			{
				left = j;
				find1 = true;
				break;
			}
		}

		// 找到right的值
		for (int j = left; j < new_matrix->getSize(); j++)
		{
			if (new_matrix->elements_[j].row != i)
			{
				right = j - 1;
				break;
			}
		}

		// 找到up的值
		for (int j = up; j < sparse_matrix.getSize(); j++)
		{
			if (sparse_matrix->elements_[j].row == i)
			{
				up = j;
				find2 = true;
				break;
			}
		}

		// 找到down的值
		for (int j = up; j < sparse_matrix.getSize(); j++)
		{
			if (sparse_matrix->elements_[j].row != i)
			{
				down = j - 1;
				break;
			}
		}

		
		if (!find1)
		{
			up = down + 1;
			continue;
		}
		else if (find1 && !find2 )
		{
			for (int z = left; z <= right; z++)
			{
				delElememt(new_matrix,z);
			}
		}
		else if (find1 && find2)
		{

		}

	}


	return *new_matrix;
}

template <typename TValue>
void delElememt(SparseMatrix<TValue>& sparse_matrix,int index)
{
	for (int i = index; i < sparse_matrix.getSize() - 1; i++)
	{
		swap_(&sparse_matrix.elements_[i],&sparse_matrix.elements_[i+1]);
	}

	sparse_matrix.setSize(sparse_matrix.getSize() - 1);
}