//Test is T55_59.cpp

#include <iostream.h>

const int MaxTerms = 100;

template <class Type>	class SparseMatrix;			//稀疏矩陣的類聲明

template <class Type>	class Trituple {			//三元組類Trituple
friend class SparseMatrix<Type> ;
friend istream & operator >> ( istream & , SparseMatrix<Type> & );
friend ostream & operator << ( ostream & , SparseMatrix<Type> & );
private:
   int row, col;							//非零元素的行號、列號
   Type value;							//非零元素的值
};


template <class Type>	class SparseMatrix {
	//對象: 是一個三元組<row, column, value>的集合。其中, row和column是整數, 記憶矩陣
	//元素所在的行號和列號，而value是矩陣元素的值。
friend istream & operator >> ( istream & , SparseMatrix<Type> & );
friend ostream & operator << ( ostream & , SparseMatrix<Type> & );
public:
   SparseMatrix ();
   SparseMatrix ( int MaxRow, int MaxCol ): Rows( MaxRow ), Cols( MaxCol ){};   	//構造函數
	//建立一個MaxRow行, Maxcol列的稀疏矩陣。
   SparseMatrix<Type> Transpose ( );
	//對*this指示的三元組數組中各個三元組交換其行、列的值, 得到其轉置矩陣。
   SparseMatrix<Type> Add ( SparseMatrix<Type> b );
	//當矩陣a(*this指示)與矩陣b的行、列數相同時, 將這兩個矩陣的對應項相加。
   SparseMatrix<Type> Multiply ( SparseMatrix<Type> b );
	//按公式 c[i][j]=∑(a[i][k]*b[k][j]) 實現矩陣a與b相乘。k=0, 1, …, a的列數-1。
   SparseMatrix<Type> FastTranspose ( );
   SparseMatrix<Type> EmptyMatrix ( );
private:
   int Rows, Cols, Terms ;
   Trituple<Type> smArray[MaxTerms];
};


template <class Type> SparseMatrix<Type> SparseMatrix<Type>::Transpose ( ) {
	//將稀疏矩陣a(*this指示)轉置, 結果在稀疏矩陣b中。
	   SparseMatrix<Type> b ( Cols, Rows );					//創建一個稀疏矩陣類的對象b
	   b.Rows = Cols;							//矩陣b的行數=矩陣a的列數
	   b.Cols = Rows;							//矩陣b的列數=矩陣a的行數
	   b.Terms = Terms;						//矩陣b的非零元素數=矩陣a的非零元素數
	   if ( Terms > 0 ) {							//非零元素個數不為零
	      int CurrentB = 0;						//存放位置指針
	      for ( int k=0; k<Cols; k++ )					//按列號做掃描，做Cols趟
	   for ( int i=0; i<Terms; i++ ) 					//在數組中找列號為k的三元組
		  if ( smArray[i].col == k ) {				//第i個三元組中元素的列號為k
			b.smArray[CurrentB].row = k;			//新三元組的行號
			b.smArray[CurrentB].col = smArray[i].row;	//新三元組的列號
			b.smArray[CurrentB].value = smArray[i].value;	//新三元組的值
			CurrentB++;						//存放指針進1
		  }
	   }
	   return b;
}


template <class Type> SparseMatrix<Type> SparseMatrix<Type>::FastTranspose ( ) {
	//對稀疏矩陣a(*this指示)做快速轉置, 結果放在b中, 時間代價為O(Terms+Columns)
	   int *rowSize = new int[Cols];					//輔助數組, 統計各列非零元素個數
	   int *rowStart = new int[Cols];					//輔助數組, 預計轉置后各行存放位置
	   SparseMatrix<Type> b ( Cols, Rows );					 //存放轉置結果
	   b.Rows = Cols;  b.Cols = Rows;  b.Terms = Terms;
	   if ( Terms > 0 ) {
		 for ( int i=0; i<Cols; i++ ) rowSize[i] = 0; 		//統計矩陣b中第i行非零元素個數
		 for ( i=0; i<Terms; i++ ) rowSize[smArray[i].col]++;
	      //根據矩陣a中第i個非零元素的列號, 將rowSize相當該列的計數加1
		 rowStart[0] = 0;						//計算矩陣b第i行非零元素的開始存放位置
		 for ( i=1; i <Cols; i++ )					//rowStart[i] = 矩陣b的第i行的開始存放位置
		   rowStart[i] = rowStart[i-1]+rowSize[i-1];
		 for ( i=0; i<Terms; i++ ) {					//從a向b傳送
		   int j = rowStart[smArray[i].col];			// j為第i個非零元素在b中應存放的位置
		   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]++;				//矩陣b第i行非零元素的存放位置加一
		 }
	   }
	   delete [ ] rowSize;   delete [ ] rowStart;
	   return b;
}

template <class Type> SparseMatrix<Type> SparseMatrix<Type>::Multiply(SparseMatrix<Type> b)
	//兩個稀疏矩陣A (*this指示) 與B (參數表中的b) 相乘, 結果在Result中
{
    if ( Cols != b.Rows ) {
	 cout << "Incompatible matrices" << endl;			//A矩陣列數與B矩陣行數不等
	 return EmptyMatrix ( );					//不能做乘法的矩陣，返回空矩陣
    }
    if ( Terms == MaxTerms || b.Terms == MaxTerms ) {		//有一個矩陣的項數達到最大
       cout << "One additional space in a or b needed" << endl;
	 return EmptyMatrix ( );					//空間不足，返回空矩陣
    }
    int *rowSize = new int[b.Rows];		 		//輔助數組, 矩陣B各行非零元素個數
    int *rowStart = new int[b.Rows+1]; 				//輔助數組, 矩陣B各行在三元組開始位置
    Type * temp = new Type[b.Cols];				//臨時數組, 暫存每一行計算結果
    SparseMatrix<Type> result ( Rows, b.Cols );			//結果矩陣的三元組表result
    for ( int i=0; i<b.Cols; i++ ) rowSize[i] = 0; 		//統計矩陣B中第i行非零元素個數
    for ( i=0; i<b.Terms; i++ ) rowSize[smArray[i].row]++;
    rowStart[0] = 0;							//計算矩陣B第i行非零元素的開始位置
    for ( i=1; i <=b.Cols; i++ ) rowStart[i] = rowStart[i-1] + rowSize[i-1];
    int Current = 0,  lastInResult = -1;				//a.smArray掃描指針及result存放指針
    while ( Current < Terms ) {					//生成result的當前行temp
	  int RowA = smArray[Current].row;			//當前行的行號
	  for ( i=0; i<b.Cols; i++ ) temp[i] = 0;			//temp初始化
	  while ( Current < Terms && smArray[Current].row == RowA ) {
	     int ColA = smArray[Current].col;			//矩陣A當前掃描到元素的列號
	     for ( i=rowStart[ColA]; i<rowStart[ColA+1]; i++ ) {
		  int ColB = b.smArray[i].col;			//矩陣B中相乘元素的列號
		  temp[ColB] = temp[ColB] + smArray[Current].value * b.smArray[i].value;
	     }								//A的RowA行與B的ColB列相乘
	    Current++;
	  }
	  for ( i=0; i<b.Cols; i++ )
	    if ( temp[i] != 0 ) {					//將temp中的非零元素壓縮到result中去
		 lastInResult++;
		 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;
    return result;
}

template <class Type>  SparseMatrix<Type> SparseMatrix<Type>:: EmptyMatrix ( ) {
    SparseMatrix<Type> b(0,0);
    return b;
}

template <class Type> istream & operator >> ( istream & is , SparseMatrix<Type> & matrix) {
    cout << "Rows and Cols: " << endl;
    is >> matrix.Rows >> matrix.Cols;
    cout << "row col value : ( ended by row = -1 ) " << endl;
    matrix.Terms = -1 ;
    do {
	matrix.Terms ++;
	is >> matrix.smArray[matrix.Terms].row
	   >> matrix.smArray[matrix.Terms].col
	   >> matrix.smArray[matrix.Terms].value;
    } while ( matrix.smArray[matrix.Terms].row != -1 );
    return is;
}

template <class Type> ostream & operator << ( ostream & os , SparseMatrix<Type> & matrix) {
    if ( matrix.Terms == 0 ) { os << "It is empty."; return os}
    os << "Rows: " << matrix.Rows << endl;
    os << "Cols: " << matrix.Cols << endl;
    os << "col row value: " << endl;
    for (int i=0; i<matrix.Terms; i++) {
	os << matrix.smArray[i].row << " "
	   << matrix.smArray[i].col << " "
	   << matrix.smArray[i].value << endl;
    }
    return os;
}