#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
 
typedef struct node 
{
    int i;
    int j;
    float value;
    struct node *down;
    struct node *right;
}NODE,*NODEP;
 
 
 
typedef struct matrix
{
    int m;int n;int t;
    NODEP *row;
    NODEP *column;
}MX,*MAT;
 
void init_matrix(MAT mat)
{
    FILE *fp;
    char filename[100];
    printf("input data file name:");
    scanf("%s",filename);
    fp=fopen(filename,"rb");
    fscanf(fp,"%d %d %d\n",&mat->m,&mat->n,&mat->t);
    mat->row=(NODEP *)malloc(sizeof(NODEP)*(mat->m+1));
    mat->column=(NODEP *)malloc(sizeof(NODEP)*(mat->n+1));
    for(int i=0;i<=mat->m;i++) mat->row[i]=NULL;
    for(int i=0;i<=mat->n;i++) mat->column[i]=NULL;
    //printf("input the nodes (i,j,value):\n");
    int m,n,val;
    for(int k=0;k<mat->t;k++)
    {
        fscanf(fp,"%d %d %d\n",&m,&n,&val);
        NODEP p=(NODEP)malloc(sizeof(NODE));
        p->i=m;p->j=n;p->value=val;
        p->down=NULL;
        p->right=NULL;
        NODEP temp=mat->row[m];
        if(!temp||temp->j>n)
        {
            p->right=temp;
            mat->row[m]=p;
        }
        else
        {
            while(temp->right&&temp->right->j<n) temp=temp->right;
            p->right=temp->right;
            temp->right=p;
        }
        temp=mat->column[n];
        if(!temp||temp->i>m)
        {
            p->down=temp;
            mat->column[n]=p;
        }
        else
        {
            while(temp->down&&temp->down->i<m) temp=temp->down;
            p->down=temp->down;
            temp->down=p;
        }
    }
    printf("matrix init complete!!!\n");
    fclose(fp);
}
void destroy_matrix(MAT mat)
{
    for(int i=1;i<=mat->m;i++)
    {
        NODEP p=mat->row[i];
        NODEP temp;
        while(p)
        {
            temp=p;
            p=p->right;
            free(temp);
        }
    }
    free(mat->row);
    free(mat->column);
}
 
void add_matrix(MAT mata,MAT matb)//add matrix mata and matb to mata
{
    NODEP c_top[20],pre=NULL;
    for(int i=1;i<=mata->n;i++)
        c_top[i]=mata->column[i];
    bool add_new;
    for(int i=1;i<=mata->m;i++)
    {
        NODEP pa,pb,e;
        pa=mata->row[i];
        pb=matb->row[i];
        pre=pa;
        while(pb||pa)
        {
            add_new=true;
            if(pb&&(mata->row[i]==NULL||mata->row[i]->j>pb->j))
            {
                mata->t++;
                NODEP temp=(NODEP )malloc(sizeof(NODE));
                temp->j=pb->j;
                temp->i=i;
                temp->value=pb->value;
                temp->right=mata->row[i];
                mata->row[i]=temp;
                pre=temp;
                e=temp;
                pb=pb->right;
            }
            else if(pb&&pa&&pa->j==pb->j)
            {
                if(pa->value+pb->value) 
                {
                    pa->value+=pb->value;
                    pre=pa;
                    e=pa;
                    pa=pa->right;
                }
                else
                {
                    mata->t--;
                    if(mata->column[pa->j]==pa)
                    {
                        mata->column[pa->j]=NULL;
                    }
                    if(mata->row[i]==pa)
                    {
                        mata->row[i]=pa->right;
                        free(pa);
                        pa=mata->row[i];
                    }
                    else
                    {
                        pre->right=pa->right;
                        free(pa);
                        pa=pre->right;
                    }
                    add_new=false;
                }
                pb=pb->right;
            }
            else if(pb&&pa&&pa->j>pb->j)
            {
                mata->t++;
                NODEP temp=(NODEP )malloc(sizeof(NODE));
                temp->j=pb->j;
                temp->i=i;
                temp->value=pb->value;
                temp->right=pa;
                pre->right=temp;
                e=temp;
                pre=pre->right;
                pb=pb->right;
            }
            else if(pa)
            {
                e=pa;
                pa=pa->right;
 
            }
            else if(pb)
            {
                mata->t++;
                NODEP temp=(NODEP )malloc(sizeof(NODE));
                e=temp;
                temp->j=pb->j;
                temp->i=i;
                temp->value=pb->value;
                temp->right=NULL;
                pre->right=temp;
                pre=pre->right;
                pb=pb->right;
            }
 
            if(add_new)
            {
                if(mata->column[e->j]==NULL)
                {
                    mata->column[e->j]=e;
                    c_top[e->j]=e;
 
                }
                else
                {
                    c_top[e->j]->down=e;
                    c_top[e->j]=e;
                }
            }
        }
    }
}
 
 
int main()
{
 
    MAT mata,matb;
    mata=(MAT )malloc(sizeof(MX));
    matb=(MAT )malloc(sizeof(MX));
    init_matrix(mata);
    init_matrix(matb);
 
    add_matrix(mata,matb);
    destroy_matrix(matb);
    destroy_matrix(mata);
    free(mata);
    free(matb);
     
     
    system("pause");
 
 
}