//KaKaMatrix.h文件

#pragma once
#include <iostream>
#include "math.h"
using namespace std;

typedef struct Matrix{
    int m;
    int n;
    double v;
    Matrix *Next;
    Matrix *Down;
    Matrix(int mm,int nn,double vv){
        m=mm;
        n=nn;
        v=vv;
        Next=Down=0;

    }
} *PMatrix;

class KaKaMatrix
{
public:
    KaKaMatrix(void);
    KaKaMatrix(int mm,int nn);
    KaKaMatrix(const KaKaMatrix& km);
    
public:
    void Init(int mm,int nn);
    void View(void);    
    int Insert(int mm, int nn, double vv);
    int Delete(int mm, int nn);    
    int Clear(void);
    int GetArray(double** PArr);
    int GetRow(void);
    int GetCol(void);
    bool IsSmall(double vv);
    double GetElement(int mm,int nn);
    KaKaMatrix MultNub(double km);
    KaKaMatrix Transpose(void);
    KaKaMatrix operator+(const KaKaMatrix& km);
    //KaKaMatrix operator*(const double km);
    KaKaMatrix operator*(const KaKaMatrix& km);
    KaKaMatrix& operator=(const KaKaMatrix& km);
public:
    ~KaKaMatrix(void);
    
private:
    int m,n,t;
    PMatrix *PMRow;
    PMatrix *PMCol;
    
};

ostream& operator<<(ostream& out,KaKaMatrix& km);//重载的输出操作符，可 cout<<KaKaMatrix 输

KaKaMatrix::KaKaMatrix(void):m(0),n(0),t(0),PMRow(new PMatrix[m]),PMCol(new PMatrix[n])
{
}

KaKaMatrix::KaKaMatrix(int mm,int nn)
{
    this->m =mm;
    this->n =nn;
    this->PMRow=new PMatrix[m];
    this->PMCol=new PMatrix[n];

    for(int i=0;i!=m;++i){
        PMRow[i]=0;
    }
    for(int i=0;i!=n;++i){
        PMCol[i]=0;
    }
    t=0;

}

KaKaMatrix::KaKaMatrix(const KaKaMatrix& km)
{
    //重载的拷贝构造函数
    this->m =km.m ;
    this->n =km.n;
    this->PMRow=new PMatrix[m];
    this->PMCol=new PMatrix[n];
    this->t=0;


    for(int i=0;i!=m;++i){
        PMRow[i]=0;
    }
    for(int i=0;i!=n;++i){
        PMCol[i]=0;
    }

    for(int i=0;i!=km.m;++i){
        PMatrix t_p=km.PMRow[i] ;
        while(t_p){
            this->Insert(t_p->m+1,t_p->n+1,t_p->v);
            
            t_p=t_p->Next ;

        }
    }

    

}

KaKaMatrix::~KaKaMatrix(void)
{
    this->Clear();

}

void KaKaMatrix::Init(int mm,int nn)//可用于，先定义一个空矩阵，再初始化
{
    //删除所有结点
    this->Clear();

    this->m =mm;
    this->n =nn;
    this->PMRow=new PMatrix[m];
    this->PMCol=new PMatrix[n];

    for(int i=0;i!=m;++i){
        PMRow[i]=0;
    }
    for(int i=0;i!=n;++i){
        PMCol[i]=0;
    }

}



int KaKaMatrix::Insert(int mm, int nn, double vv)
{
    --mm;
    --nn;
    if(vv==0.0) return 0;
    
    if((mm>=m||nn>=n)||(mm<0||nn<0)) return 0;

    PMatrix t_pp=0;//保存行插入时新结点指针，用于列插入
    //行插入
    if(!this->PMRow[mm]){
        this->PMRow[mm]=new Matrix(mm,nn,vv);
        t_pp=this->PMRow[mm]->Next;//暂存

    }else{
        PMatrix t_p=this->PMRow[mm];

        while(t_p){
            if(t_p->n==nn){
                 t_p->v +=vv;
                 if(t_p->v==0.0){
                     //相加为零，删除结点
                     this->Delete(mm+1,nn+1);
                     return --t;

                 }
                
                 return t;
            }
            if((t_p->n<nn&&!t_p->Next)||(t_p->n<nn&&t_p->Next->n>nn)){
                t_p->Next=new Matrix(mm,nn,vv);
                t_pp=t_p->Next;
                return ++t;
            }
            t_p=t_p->Next ;
        }

    }
    //行插入结束，列插入开始

    if(!this->PMCol[nn]){
        this->PMCol[nn]=t_pp;

    }else{
        PMatrix t_p=this->PMCol[nn];

        while(t_p){
            if((t_p->m<mm&&!t_p->Down)||(t_p->m<mm&&t_p->Down->m>mm)){
                t_p->Down=t_pp;

            }
            t_p=t_p->Down ;

        }
    };
    return ++t;

    

}

int KaKaMatrix::Delete(int mm, int nn)
{
    //不带头结点，真是麻烦
    --mm;
    --nn;
    if((mm>=m||nn>=n)||(mm<0||nn<0)) return 0;

    PMatrix t_a = this->PMRow[mm] ;
    if(t_a&&(t_a->n==nn)){
        //删除第一行，第一列时出现的情况，不带头结点的缺点
        this->PMRow[mm]=this->PMRow[mm]->Next ;

    }else{
    
        while(t_a){
        
            if(t_a->n<nn&&t_a->Next->n==nn){            
            
                t_a->Next =t_a->Next->Next ;            
                break;
            }
        
            t_a=t_a->Next ;
        };
    }
    //列

    PMatrix t_b=this->PMCol[nn];
    if(t_b&&(t_b->m ==mm)){

        PMatrix t_delete=t_b;
        t_b =t_b->Down;
        delete t_delete;
        return 1;


    }else{
        while(t_b){    
            if(t_b->m<mm&&t_b->Down->m==mm){            
                PMatrix t_delete=t_b->Down;
                t_b->Down =t_b->Down->Down ;
                delete t_delete;
                return 1;
            }        
            t_b=t_b->Next ;
       };

    }

    
    

    return 0;
}

int KaKaMatrix::Clear(void)
{
    //清空矩阵，全为0
    for(int i=0;i!=m;++i){
        PMatrix t_p=this->PMRow[i] ;
        while(t_p){

            PMatrix t_delete=t_p;
            t_p=t_p->Next ;
            delete t_delete;

        }
    }
    delete [] PMRow;
    delete [] PMCol;
    PMRow=PMCol=0;
    
    t=0;

    return 1;
}


KaKaMatrix KaKaMatrix::Transpose(void)
{
    //返回一个转置矩阵
    KaKaMatrix out_km(this->n,this->m);

    for(int i=0;i!=m;++i){
        PMatrix t_p=this->PMRow[i] ;
        while(t_p){
            out_km.Insert(t_p->n+1,t_p->m+1,t_p->v);
            t_p=t_p->Next ;

        }
    }

    return out_km;
}



void KaKaMatrix::View(void)
{
    //打印输出矩阵
    //输出函数，空间复杂度　n*m ,时间复杂度不知道怎么算，执行循环总次数是 2*n*m+t+n。
    //有没有更好的办法
    //申请内存，全为０
    double **t_a=new double* [m];
    for(int i=0;i!=m;++i){
        t_a[i]=new double [n];
    }
    for(int i=0;i!=m;++i){
        for(int j=0;j!=n;++j){
            t_a[i][j]=0;
        }

    }
    //装填动态数组
    this->GetArray(t_a);

    cout<<endl<<"==========================================="<<endl;

    for(int i=0;i!=m;++i){
        
        for(int j=0;j!=n;++j){
            cout<<t_a[i][j]<<"  ";
        }
        cout<<endl;

    }
    cout<<"==========================================="<<endl;

    for(int i=0;i!=m;++i){
        delete [] t_a[i];
    }
    delete [] t_a;




        
}


int KaKaMatrix::GetRow(void)
{
    return m;
}

int KaKaMatrix::GetCol(void)
{
    return n;
}



KaKaMatrix KaKaMatrix::operator+(const KaKaMatrix& km)
{
    //重载矩阵加法
    if(km.m!=m||km.n!=n)
       return KaKaMatrix(0,0);
    KaKaMatrix out_km(m,n);

    for(int i=0;i!=km.m;++i){
        PMatrix t_p=km.PMRow[i] ;
        while(t_p){
            out_km.Insert(t_p->m+1,t_p->n+1,t_p->v);
            
            t_p=t_p->Next ;

        }
    }

    for(int i=0;i!=m;++i){
        PMatrix t_p=this->PMRow[i] ;
        while(t_p){
            out_km.Insert(t_p->m+1,t_p->n+1,t_p->v);
            t_p=t_p->Next ;

        }
    }

    return out_km;


}



KaKaMatrix& KaKaMatrix::operator=(const KaKaMatrix& km)
{
    //重载赋值操作
    
    this->Init(km.m,km.n);

    for(int i=0;i!=km.m;++i){
        PMatrix t_p=km.PMRow[i] ;
        while(t_p){
            this->Insert(t_p->m+1,t_p->n+1,t_p->v);
            
            t_p=t_p->Next ;

        }
    }



    return *this;
}



KaKaMatrix KaKaMatrix::operator*(const KaKaMatrix& km)
{
    if(n!=km.m)
      return KaKaMatrix(0,0);
    KaKaMatrix out_km(m,km.n);
    //把矩阵1装入数组
    double **t_a=new double* [m];
    for(int i=0;i!=m;++i){
        t_a[i]=new double [n];
    }
    for(int i=0;i!=m;++i){
        for(int j=0;j!=n;++j){
            t_a[i][j]=0;
        }

    }
    this->GetArray(t_a);

    //把矩阵2装入数组
    double **t_b=new double* [km.m];
    for(int i=0;i!=km.m;++i){
        t_b[i]=new double [km.n];
    }
    for(int i=0;i!=km.m;++i){
        for(int j=0;j!=km.n;++j){
            t_b[i][j]=0;
        }

    }
    for(int i=0;i!=km.m;++i){
        PMatrix t_p=km.PMRow[i] ;
        while(t_p){
            t_b[t_p->m][t_p->n]=t_p->v;
            t_p=t_p->Next ;

        }
    }

    //开始乘法
    //结果矩阵两层循环
    for(int i=0;i!=m;++i){
        for(int j=0;j!=km.n;++j){
            double t_item=0;
            //核心循环
            for(int g=0;g!=n;++g){
                t_item+=t_a[i][g]*t_b[g][j];

            }

            out_km.Insert(i+1,j+1,t_item);
            
        }
    }

    return out_km;



}

int KaKaMatrix::GetArray(double** PArr)
{
    
    //装填动态数组
    for(int i=0;i!=m;++i){
        PMatrix t_p=this->PMRow[i] ;
        while(t_p){
            PArr[t_p->m][t_p->n]=t_p->v;
            t_p=t_p->Next ;

        }
    }
    return 1;
}
ostream& operator<<(ostream& out,KaKaMatrix& km){


    //重载的输出操作符，可 cout<<KaKaMatrix 输出。
    int m=km.GetRow();
    int n=km.GetCol();
    double **t_a=new double* [m];
    for(int i=0;i!=m;++i){
        t_a[i]=new double [n];
    }
    for(int i=0;i!=m;++i){
        for(int j=0;j!=n;++j){
            t_a[i][j]=0;
        }

    }
    //装填动态数组
    km.GetArray(t_a);

    out<<endl<<"==========================================="<<endl;

    for(int i=0;i!=m;++i){
        
        for(int j=0;j!=n;++j){
            out<<t_a[i][j]<<"  ";
        }
        out<<endl;

    }
    out<<"==========================================="<<endl;

    for(int i=0;i!=m;++i){
        delete [] t_a[i];
    }
    delete [] t_a;


    return  out;
}
KaKaMatrix KaKaMatrix::MultNub(double km)
{
    KaKaMatrix out_km(m,n);

    for(int i=0;i!=this->m;++i){
        PMatrix t_p=this->PMRow[i] ;
        while(t_p){
            out_km.Insert(t_p->m+1,t_p->n+1,t_p->v*km);
            
            t_p=t_p->Next ;

        }
    }
    return out_km;
    /*for(int i=0;i!=m;++i){
        PMatrix t_p=this->PMRow[i] ;
        while(t_p){
            t_p->v = t_p->v*km;
            t_p=t_p->Next;
        }
    }
    return ;*/
}

double KaKaMatrix::GetElement(int mm, int nn)
{
    --mm;
    --nn;
    if((mm>=m||nn>=n)||(mm<0||nn<0)) return 0;
    
    PMatrix t_p = this->PMRow[mm];
    while(t_p){
        if(t_p->n == nn)
            return t_p->v;
        
        t_p=t_p->Next;
    }

    return 0;
}

bool KaKaMatrix::IsSmall(double vv)
{
    for(int i=0;i!=this->m;++i){
        PMatrix t_p=this->PMRow[i] ;
        while(t_p){
            if(abs(t_p->v) > vv)
                return false;
            t_p=t_p->Next;
        }
    }
    return true;
}