#ifndef SPARSEMATRIX_H_
#define SPARSEMATRIX_H_
#include <iostream>
template <class Type> class SparseMatrix;
template <class Type> std::ostream & operator<< (std::ostream & out, const SparseMatrix<Type> & instance);
template <class Type>
class SparseMatrix{
private:
    int mRows;    // 矩阵的行
    int mCols;   //  矩阵的列
    int mItems;   // 矩阵中非零数的个数
    struct Trituple{
        int row;   // 记录某个矩阵元素所在的行
        int col;   //  记录某个矩阵元素所在的列
        Type value; // 记录某个矩阵元素的值
        Trituple* next;
        Trituple() : row(0), col(0), value(0), next(0){};
    } * smArray; // 存储所有三元组的链表
protected:
    void getMatrix(); // 获得三元组的输入
    Type find(int row, int col)const; // 在三元组表中查找某一个矩阵元素(此函数未优化)
public:
    SparseMatrix();
    ~SparseMatrix();
    SparseMatrix(int rows, int cols);
    SparseMatrix(SparseMatrix &); //Copy constructor.
    SparseMatrix<Type> transpose(); // Matrix thranspose.
    SparseMatrix<Type> add(SparseMatrix<Type> & b); //(*this) + b.
    SparseMatrix<Type> multiply(SparseMatrix<Type> & b); //(*this) * b.
    int getRows()const{
        return this->mRows; }
    int getCols()const{
        return this->mCols; }
    int getItems()const{
        return this->mItems; }
    Trituple * getArray()const{
        return this->smArray; }
    friend std::ostream & operator<< <Type>(std::ostream & out, const SparseMatrix<Type> & instance);
};
// End of class statement.
template<class Type>
SparseMatrix<Type>::SparseMatrix(){
    this->mRows = 0;
    this->mCols = 0;
    this->mItems = 0;
    this->smArray = 0;
}
template <class Type>
SparseMatrix<Type>::SparseMatrix(int rows, int cols){
    this->mRows = rows;
    this->mCols = cols;
    this->getMatrix();
}
template <class Type>
SparseMatrix<Type>::SparseMatrix(SparseMatrix & source){
    this->mRows = source.getRows();
    this->mCols = source.getCols();
    this->mItems = source.getItems();
    Trituple* create = 0;
    Trituple* last =  0;
    for(int j=0; j<this->getItems(); j++){
        create = new Trituple;
        if(j == 0)
            this->smArray = create;
        else
            last->next = create;
        last = create;
    }
    Trituple* tempD = this->getArray();
    Trituple* tempS = source.getArray();
    for(int i=0; i<this->getItems(); i++){
        tempD->row = tempS->row;
        tempD->col = tempS->col;
        tempD->value = tempS->value;
        tempD = tempD->next;
        tempS = tempS->next;
    }
}
template <class Type>
SparseMatrix<Type>  SparseMatrix<Type>:: transpose(){
    SparseMatrix<Type> b;
    b.mRows = this->getCols();
    b.mCols = this->getRows();
    b.mItems = this->getItems();
    Trituple* create = 0;
    Trituple* last =  0;
    for(int j=0; j<b.getItems(); j++){
        create = new Trituple;
        if(j == 0){
            b.smArray = create;
            last = create;
        }
        else{
            last->next = create;
            last = create;
        }
    }
    Trituple* temp1 = this->getArray();
    Trituple* temp2 = b.getArray();
    if(this->mItems > 0){
        for(int k=0; k<this->getCols(); k++){
            for(int i=0;i<this->getItems();i++){
                if(temp1->col == k){
                    temp2->row = k;
                    temp2->col = temp1->row;
                    temp2->value = temp1->value;
                    temp2 = temp2->next;
                }
                temp1 = temp1->next;
            }
            temp1 = this->getArray();
        }
    }
    return b;
}
template <class Type>
SparseMatrix<Type> SparseMatrix<Type>::add(SparseMatrix<Type> & b){
    if(this->getRows() != b.getRows()){
        std::cerr<<" Illegal addition! Quit now."<<std::endl;
        SparseMatrix nop;
        return nop;
    }
    SparseMatrix<Type> result;
    result.mCols = b.getCols();
    result.mRows = b.getRows();
    Trituple* tempA = this->getArray();
    Trituple* tempB = b.getArray();
    Trituple* tempR = 0;
    Trituple* last = 0;
    int countA = this->getItems();
    int countB = b.getItems();
    int countR = 0;
    while(1){
        if(countA != 0 || countB != 0){
            if(countA != 0 && countB != 0){
                if(tempA->row < tempB->row){
                    tempR = new Trituple;
                    countR++;
                    if(result.getArray() == 0)
                        result.smArray = tempR;
                    else
                        last->next = tempR;
                    last = tempR;
                    tempR->col = tempA->col;
                    tempR->row = tempA->row;
                    tempR->value = tempA->value;
                    tempA = tempA->next;
                    countA--;
                }
                else if(tempA->row == tempB->row){
                    if(tempA->col < tempB->col){
                        tempR = new Trituple;
                        countR++;
                        if(result.getArray() == 0)
                            result.smArray = tempR;
                        else
                            last->next = tempR;
                        last = tempR;
                        tempR->col = tempA->col;
                        tempR->row = tempA->row;
                        tempR->value = tempA->value;
                        tempA = tempA->next;
                        countA--;
                    }
                    else if(tempA->col == tempB->col){
                        if((tempA->value + tempB->value) != 0){
                        tempR = new Trituple;
                        countR++;
                        if(result.getArray() == 0)
                            result.smArray = tempR;
                        else
                            last->next = tempR;
                        last = tempR;
                        tempR->col = tempA->col;
                        tempR->row = tempA->row;
                        tempR->value = tempA->value + tempB->value;
                        tempA = tempA->next;
                        tempB = tempB->next;
                        countA--;
                        countB--;
                        }
                        else if((tempA->value + tempB->value) == 0){
                            tempA = tempA->next;
                            tempB = tempB->next;
                            countA--;
                            countB--;
                        }
                    }
                    else if(tempA->col > tempB->col){
                        tempR = new Trituple;
                        countR++;
                        if(result.getArray() == 0)
                            result.smArray = tempR;
                        else
                            last->next = tempR;
                        last = tempR;
                        tempR->col = tempB->col;
                        tempR->row = tempB->row;
                        tempR->value = tempB->value;
                        tempB = tempB->next;
                        countB--;
                    }
                }
                else if(tempA->row > tempB->row){
                    tempR = new Trituple;
                    countR++;
                    if(result.getArray() == 0)
                        result.smArray = tempR;
                    else
                        last->next = tempR;
                    last = tempR;
                    tempR->col = tempB->col;
                    tempR->row = tempB->row;
                    tempR->value = tempB->value;
                    tempB = tempB->next;
                    countB--;
                }
            }
            else if(countA == 0){
                tempR = new Trituple;
                countR++;
                if(result.getArray() == 0)
                    result.smArray = tempR;
                else
                    last->next = tempR;
                last = tempR;
                tempR->col = tempB->col;
                tempR->row = tempB->row;
                tempR->value = tempB->value;
                tempB = tempB->next;
                countB--;
            }
            else if(countB == 0){
                tempR = new Trituple;
                countR++;
                if(result.getArray() == 0)
                    result.smArray = tempR;
                else
                    last->next = tempR;
                last = tempR;
                tempR->col = tempA->col;
                tempR->row = tempA->row;
                tempR->value = tempA->value;
                tempA = tempA->next;
                countA--;
            }
        }
        else{
            break;
        }
    }
    result.mItems = countR;
    return result;
}
template <class Type>
SparseMatrix<Type> SparseMatrix<Type>::multiply(SparseMatrix<Type> & b){
    if(this->getCols() != b.getRows()){
        std::cerr<<" Illegal addition! Quit now."<<std::endl;
        SparseMatrix nop;
        return nop;
    }
    SparseMatrix<Type> result;
    result.mRows = this->mRows;
    result.mCols = b.mCols;
    Type temp = 0;
    Type tempA, tempB;
    Trituple* tempResult = 0;
    Trituple* last = 0;
    int count = 0;
    for(int i=0; i<this->getRows(); i++){
        for(int j=0; j<b.getCols(); j++){
            for(int k=0; k<this->getCols(); k++){
                tempA = this->find(i, k);
                if(tempA != 0){
                    tempB = b.find(k, j);
                    temp += tempA * tempB;
                }
            }
            if(temp != 0){
                tempResult = new Trituple;
                count++;
                if(result.getArray() == 0)
                    result.smArray = tempResult;
                else
                    last->next = tempResult;
                last = tempResult;
                tempResult->row = i;
                tempResult->col = j;
                tempResult->value = temp;
                temp = 0;
            }
        }
    }
    result.mItems = count;
    return result;
}
template <class Type>
void SparseMatrix<Type>::getMatrix(){
    using namespace std;
    Trituple* temp = 0;
    Trituple* last = 0;
    cout <<"\n一共有多少个非零值？\n";
    cin>>this->mItems;
    cout <<"\n按如下方式每次输入一个非空三元组: \n\tRow\tColumn\tValue\n\t0  \t0  \t10\n\n";
    for(int i=0; i<this->getItems(); i++){
        temp = new Trituple;
        if(i == 0)
            this->smArray = temp;
        else
            last->next = temp;
        last = temp;
        cout <<"第"<< i+1<<"组: ";
        cin>>temp->row >>temp->col >> temp->value;
    }
}
template <class Type>
Type SparseMatrix<Type>::find(int row, int col)const{
    Trituple* pt = this->getArray();
    for(int i=0; i<this->getItems(); i++){
        if(pt->row == row && pt->col == col){
            return pt->value;
        }
        else
            pt = pt->next;
    }
    return 0;
}
template <class Type>
std::ostream & operator<< (std::ostream & out, const SparseMatrix<Type> & instance){
    using namespace std;
    out <<"The matrix is as follows:\n";
    Type temp = 0;
    for(int i=0; i<instance.mRows; i++){
        for(int j=0; j<instance.mCols; j++){
            temp = instance.find(i, j);
            if(temp != 0)
                out<<" "<<temp<<"\t";
            else
                out<<" 0\t";
        }
        out <<endl;
    }
    return out;
}
template <class Type>
SparseMatrix<Type>::~SparseMatrix(){
    delete [] smArray;
}
#endif