//稀疏矩陣類操作的實現
#include "SparseMatrix.h"
template <class E>
SparseMatrix<E>::SparseMatrix (int Rw, int Cl, int Tm, Triple<E>* sma) {
    Rows = Rw;   Cols = Cl;   Terms = Tm; smArray = sma;	
    if (smArray == NULL) smArray = new Triple<E>[Terms];          //三元組表
    if (smArray == NULL) {
         cerr << "存儲分配失敗!" << endl;  exit(1);
    }	
};  

template <class E>
void SparseMatrix<E> ::
Transpose (SparseMatrix<E>& B) {
//轉置this矩陣,轉置結果由B返回
     B.Rows = Cols;   B.Cols = Rows; 
     B.Terms = Terms;
        //轉置矩陣的列數,行數和非零元素個數
     if (Terms > 0) {				
          int CurrentB = 0;   //轉置三元組表存放指針
          int i, k;
         for (k = 0; k < Cols; k++)       //處理所有列號
      	      for (i = 0; i < Terms; i++) 		
				  if (smArray[i].col == k) {
					  B.smArray[CurrentB].row = k;	
	                B.smArray[CurrentB].col = smArray[i].row;
	                B.smArray[CurrentB].value=smArray[i].value;	
 	                CurrentB++;					
				  }
     }
};    

template <class E> 
void SparseMatrix<E>::
      FastTranspos (SparseMatrix<E>& B) {
    int *rowSize = new int[Cols];       //列元素數數組
    int *rowStart = new int[Cols];      //轉置位置數組
    B.Rows = Cols;   B.Cols = Rows;
    B.Terms = Terms;
    if (Terms > 0) {
        int i, j;
        for (i = 0; i < Cols; i++) rowSize[i] = 0;        
	    for (i = 0; i < Terms; i++)
			rowSize[smArray[i].col]++; 
        rowStart[0] = 0;	
        for (i = 1; i < Cols; i++)			
			rowStart[i] = rowStart[i-1]+rowSize[i-1];
	    for (i = 0; i < Terms; i++) {			
			j = rowStart [smArray[i].col];		
	       B.smArray[j].row = smArray[i].col;
	       B.smArray[j].col = smArray[i].row;
	       B.smArray[j].value = smArray[i].value;
	       rowStart [smArray[i].col]++;		
		}        
}    
    delete [ ] rowSize;   delete [ ] rowStart;
}

template <class E>
SparseMatrix<E> SparseMatrix<E>::Add(SparseMatrix<E>& b) {
//兩個稀疏矩陣A (*this 指示) 與B (參數表中的b) 相加, 結果在Result 中
	SparseMatrix<E> result(Rows,Cols); //結果矩陣的三元組表
	if ( Rows != b.Rows || Cols != b.Cols) {
		cout << "Incompatible matrices" << endl; //兩個矩陣規格不一樣
		return result; //返回空矩陣
	}
	int i = 0, j = 0, index_a, index_b; result.Terms = 0;
	while (i < Terms && j < b.Terms) {
		index_a = Cols*smArray[i].row+smArray[i].col;
		index_b = Cols*b.smArray[j].row+b.smArray[j].col;
		if (index_a < index_b) { //smArray[i]在b.smArray[j]前
			result.smArray[result.Terms] = smArray[i];
			i++;
		}
		else if (index_a > index_b) { //smArray[i]在b.smArray[j]后
			result.smArray[result.Terms] = b.smArray[j];
			j++;
		}
		else { //smArray[i]和b.smArray[j]在相同位置
			result.smArray[result.Terms] = smArray[i];
			result.smArray[result.Terms].value= smArray[i].value + b.smArray[j].value;
			i++; j++;
		}
		result.Terms++;
	}
	//復制剩余元素
	for ( ; i < Terms; i ++) {
		result.smArray[result.Terms] = smArray[i];
		result.Terms++;
	}
	for ( ; j < b.Terms; j++) {
		result.smArray[result.Terms] = b. smArray[i];
		result.Terms++;
	}
	return result;
};

template <class E>
SparseMatrix<E> SparseMatrix<E>::Multiply(SparseMatrix<E>& b) {
//兩個稀疏矩陣a（*this 指示）與b（參數表中的b）相乘, 結果在Result 中
	SparseMatrix<E> result(Rows, b.Cols); //結果矩陣的三元組表
	if (Cols != b.Rows) {
		cout << "Incompatible matrices" << endl; //A 列數與B 行數不等
		return result; //返回空矩陣
	}
	if (Terms == maxTerms || b.Terms == maxTerms) {
		cout << "One additional space in a or b needed" << endl;
		return result; //空間不足，返回空矩陣
	}
	int *rowSize = new int[b.Rows]; //矩陣B 各行非零元素個數
	int *rowStart = new int[b.Rows+1]; //矩陣B 各行在三元組開始位置
	E *temp = new E[b.Cols]; //暫存每一行計算結果
	int i, Current, lastInResult, RowA, ColA, ColB;
	for (i = 0; i < b.Rows; i++) rowSize[i] = 0;
	cout << "success" << endl;
	for (i = 0; i < b.Terms; i++) rowSize[b.smArray[i].row]++;
	
	rowStart[0] = 0; //B第i 行非零元素開始位置
	for (i = 1; i <= b.Rows; i++)
		rowStart[i] = rowStart[i-1]+rowSize[i-1];
	
	
	Current = 0; lastInResult = -1; //a 掃描指針及result 存指針
	
	while (Current < Terms) { //生成result 的當前行temp
		RowA = smArray[Current].row; //當前行的行號
	//	cout <<  RowA << ' ' << Current << endl;
		for (i = 0; i < b.Cols; i++) temp[i] = 0;
		while (Current < Terms && smArray[Current].row == RowA) {
			ColA = smArray[Current].col; //矩陣A 當前掃描到元素的列號
			for (i = rowStart[ColA]; i < rowStart[ColA+1]; i++) {
				ColB = b.smArray[i].col; //矩陣B 中相乘元素的列號
				temp[ColB] += smArray[Current].value*b.smArray[i].value;
			} //A的RowA 行與B 的ColB 列相乘
			Current++;
		}
	//	cout << "success2" << endl;
		for (i = 0; i < b.Cols; i++)
			if (temp[i] != 0) { //將temp 中的非零元素壓縮到result 中去
				lastInResult++;
				cout << RowA << ' ' << i << ' ' << temp[i] << ' ' << lastInResult << endl;
				result.smArray[lastInResult].row = RowA;
				result.smArray[lastInResult].col = i;
				result.smArray[lastInResult].value = temp[i];
			}
	}
	result.Rows = Rows; result.Cols = b.Cols;
	result.Terms = lastInResult+1;
	
	//delete []rowSize; delete []rowStart; delete []temp;
	cout << "ss" << endl;
	return result;
	
};