# include <iostream.h>
 # include <fstream.h>
 # include <string.h>
 # include <stdlib.h>
 # include    <conio.h>

 class Node
 {
    public:
       int row;
       int col;
       int data;

       Node *next_in_row;
       Node *next_in_col;

    public:
       Node( );
 };

 //----------------------------  SparseMatrix  ----------------------------//class SparseMatrix
 {
    public:
       int m;
       int n;
       Node *Root;

    public:
       SparseMatrix( );

       Node* GetNode(int row, int col, Node* root);
       Node* InsertNode(int row, int col, intvalue, Node* root);
       Node* DeleteNode(int row, int col, Node* root, Node* Parent);

       // Required Functionsvoid SetElement(int row, int col, intvalue);
       int GetElement(int row, int col);
       void PrintMatrix( );
       void TakeTranspose( );
       void MulRowWithScalar(int scalar, int row);
       void MulColWithScalar(int scalar, int col);
       void MulMatrixWithScalar(int scalar);
       void DeleteRow(int row);
       void DeleteCol(int col);

       intoperator==(SparseMatrix Obj);
       voidoperator=(SparseMatrix Obj);
       intoperator+=(SparseMatrix Obj);
       intoperator-=(SparseMatrix Obj);
 };

 /**************************************************************************///-------------------------  Function Definitions  -----------------------///**************************************************************************///--------------------------------  Node( )  -----------------------------//

 Node::Node( )
 {
    row = 0;
    col = 0;
    data = 0;

    next_in_row = NULL;
    next_in_col = NULL;
 }

 //---------------------------  GetNode( )  ---------------------------//

 Node* SparseMatrix::GetNode(int row, int col, Node* root)
 {
    if (root == NULL)
        return NULL;

    elseif (root->row > row)
        return NULL;

    elseif (root->row == row)
    {
        if (root->col > col)
            return NULL;

        elseif (root->col == col)
            return root;

        elseif (root->col < col && root->next_in_col != NULL)
            return GetNode(row, col, root->next_in_col);
    }

    elseif (root->row < row && root->next_in_row != NULL)
        return GetNode(row, col, root->next_in_row);

    return NULL;
 }

 //-------------------------  GetElement( )  --------------------------//int SparseMatrix::GetElement(int row, int col)
 {
    Node* Temp = GetNode(row, col, this->Root);

    if (Temp != NULL)
    return Temp->data;

    return 0;
 }

 //-------------------------  MulRowWithScalar( )  -----------------------//void SparseMatrix::MulRowWithScalar(int scalar, int row)
 {
    Node* Temp;

    for (int i = 0; i < this->n; i ++)
    {
       Temp = GetNode(row, i, this->Root);

       if (Temp != NULL)
      Temp->data *= scalar;
    }
 }

 //-------------------------  MulColWithScalar( )  -----------------------//void SparseMatrix::MulColWithScalar(int scalar, int col)
 {
    Node* Temp;

    for (int i = 0; i < this->m; i ++)
    {
       Temp = GetNode(i, col, this->Root);

       if (Temp != NULL)
      Temp->data *= scalar;
    }
 }

 //-------------------------  MulMatrixWithScalar( )  -----------------------//void SparseMatrix::MulMatrixWithScalar(int scalar)
 {
    Node* Temp;

    for (int i = 0; i < this->m; i ++)
    {
       for (int j = 0; j < this->n; j ++)
       {
       Temp = GetNode(i, j, this->Root);

       if (Temp != NULL)
          Temp->data *= scalar;
       }
    }
 }

 //-----------------------------  InsertNode( )  --------------------------//

 Node* SparseMatrix::InsertNode(int row, int col, int data, Node* root)
 {
     if (root == NULL)
     {
     root = new Node;

     root->row = row;
     root->col = col;
     root->data = data;

     root->next_in_row = NULL;
     root->next_in_col = NULL;
     }

    elseif (root->row > row)
    {
     Node* Temp = root;

     root = new Node;

     root->row = row;
     root->col = col;
     root->data = data;

     root->next_in_row = Temp;
     root->next_in_col = NULL;
    }

    elseif (root->row == row)
    {
    if (root->col == col)
       root->data = data;

    elseif (root->col > col)
    {
       Node* Temp = root;

       root = new Node;

       root->row = row;
       root->col = col;
       root->data = data;

       root->next_in_row = Temp->next_in_row;
       root->next_in_col = Temp;

       Temp->next_in_row = NULL;
    }

    elseif (root->next_in_col != NULL && root->next_in_col->col > col)
    {
       Node* Temp = root;

       root = new Node;

       root->row = row;
       root->col = col;
       root->data = data;

       root->next_in_row = NULL;
       root->next_in_col = Temp->next_in_col;

       Temp->next_in_col = root;
    }

    else
       root->next_in_col = InsertNode(row, col, data, root->next_in_col);
     }

     elseif (root->row < row)
     {
    if (root->next_in_row != NULL && root->next_in_row->row > row)
    {
        Node* Temp = new Node;

        Temp->row = row;
        Temp->col = col;
        Temp->data = data;

        Temp->next_in_row = root->next_in_row;
        Temp->next_in_col = NULL;

        root->next_in_row = Temp;
    }

    else
       root->next_in_row=InsertNode(row, col, data, root->next_in_row);
     }

     return root;
 }

 //-----------------------------  DeleteNode( )  --------------------------//

 Node* SparseMatrix::DeleteNode(int row, int col, Node* root, Node* Parent)
 {
    if (root == NULL)
       return NULL;

    elseif (root->row > row)
       return NULL;

    elseif (root->row == row)
    {
    if (root->col == col)
    {
       if (Parent == NULL)
       {
           Node* Temp;

           if (root->next_in_col != NULL)
           {
          Temp = root->next_in_col;
          Temp->next_in_row = root->next_in_row;
           }

           else
          Temp = root->next_in_row;

           delete[] root;

           root = Temp;

           return root;
       }

       else
       {

           if (root->row == Parent->row)
           {
               Node* Temp = root->next_in_col;

               Parent->next_in_col = Temp;

               delete[] root;

               return NULL;
           }

           else
           {

          if (root->next_in_col == NULL)
             Parent->next_in_row = root->next_in_row;

          else
          {
             Node* Temp;

             for (int i = 0; i <this->n; i++)
             {
            Temp = GetNode(Parent->row, i, this->Root);

            if (Temp != NULL)
               break;
             }

             Temp->next_in_row = root->next_in_col;
             root->next_in_col->next_in_row = root->next_in_row;
          }

          delete[] root;

          return NULL;
           }
       }
    }

    elseif (root->col > col)
       return NULL;

    elseif (root->next_in_col == NULL || root->next_in_col->col > col)
       return NULL;

    elsereturn DeleteNode(row, col, root->next_in_col, root);
     }

     elseif (root->row < row)
     {
    if (root->next_in_row == NULL || root->next_in_row->row > row)
       return NULL;

    elsereturn DeleteNode(row, col, root->next_in_row, root);
     }

     return NULL;
 }

 //----------------------------  DeleteRow( )  --------------------------//void SparseMatrix::DeleteRow(int row)
 {
    for (int j = 0; j < this->n; j ++)
    {
      Node* Temp = DeleteNode(row, j, this->Root, NULL);

      if (Temp != NULL)
     this->Root = Temp;
    }
 }

 //----------------------------  DeleteCol( )  --------------------------//void SparseMatrix::DeleteCol(int col)
 {
    for (int i = 0; i < this->m; i ++)
    {
      Node* Temp = DeleteNode(i, col, this->Root, NULL);

      if (Temp != NULL)
     this->Root = Temp;
    }
 }

 //----------------------------  SetElement( )  --------------------------//void SparseMatrix::SetElement(int row, int col, intvalue)
 {
    this->Root = InsertNode(row, col, value, this->Root);
 }

 //----------------------------  SparseMatrix( )  ------------------------//

 SparseMatrix::SparseMatrix( )
 {
    m = 0;
    n = 0;
    Root = NULL;
 }

//---------------------------  PrintMatrix( )  ---------------------------//void SparseMatrix::PrintMatrix( )
 {
    Node* Temp;

    for (int i = 0; i < this->m; i ++)
    {
    for (int j = 0; j < this->n; j ++)
    {
        Temp = GetNode(i, j, this->Root);

        if (Temp == NULL)
        cout << "\t-";

        else
           cout << "\t" << Temp->data;
    }

    cout << endl;
    }
 }

//---------------------------  Operator==( )  ----------------------------//int SparseMatrix::operator==(SparseMatrix Obj)
 {
    if (this->m != Obj.m || this->n!= Obj.n)
    return 0;

    Node* Temp1;
    Node* Temp2;

    for (int i = 0; i < this->m; i ++)
    {
    for (int j = 0; j < this->n; j ++)
    {
        Temp1 = GetNode(i, j, this->Root);
        Temp2 = GetNode(i, j, Obj.Root);

        if (Temp1 == NULL && Temp2 == NULL)
           continue;

        elseif(Temp1 == NULL && Temp2 != NULL)
           return 0;


        elseif(Temp1 != NULL && Temp2 == NULL)
           return 0;

        elseif(Temp1->data != Temp2->data)
           return 0;
    }
    }

    return 1;
 }

//----------------------------  Operator=( )  ----------------------------//void SparseMatrix::operator=(SparseMatrix Obj)
 {
    for (int i = 0; i < this->m; i ++)
    this->DeleteRow(i);

    this->m = Obj.m;
    this->n = Obj.n;
    this->Root = NULL;

    for (i = 0; i < Obj.m; i ++)
    {
    for (int j = 0; j < Obj.n; j ++)
    {
        Node* Temp = GetNode(i, j, Obj.Root);

        if (Temp != NULL)
         this->Root = InsertNode(i,j,Temp->data,this->Root);
    }
    }
 }

//---------------------------  Operator+=( )  ----------------------------//int SparseMatrix::operator+=(SparseMatrix Obj)
 {
    if (this->m != Obj.m || this->n!= Obj.n)
    return 0;

    Node* Temp1;
    Node* Temp2;

    for (int i = 0; i < this->m; i ++)
    {
    for (int j = 0; j < this->n; j ++)
    {
        Temp1 = GetNode(i, j, this->Root);
        Temp2 = GetNode(i, j, Obj.Root);

        if (Temp1 == NULL && Temp2 == NULL)
           continue;

        elseif(Temp1 == NULL && Temp2 != NULL)
           this->Root = InsertNode(i,j,Temp2->data,this->Root);

        elseif(Temp1 != NULL && Temp2 == NULL)
           continue;

        else
           Temp1->data += Temp2->data;
    }
    }

    return 1;
 }

//---------------------------  Operator-=( )  ----------------------------//int SparseMatrix::operator-=(SparseMatrix Obj)
 {
    if (this->m != Obj.m || this->n!= Obj.n)
    return 0;

    Node* Temp1;
    Node* Temp2;

    for (int i = 0; i < this->m; i ++)
    {
    for (int j = 0; j < this->n; j ++)
    {
        Temp1 = GetNode(i, j, this->Root);
        Temp2 = GetNode(i, j, Obj.Root);

        if (Temp1 == NULL && Temp2 == NULL)
           continue;

        elseif(Temp1 == NULL && Temp2 != NULL)
           this->Root = InsertNode(i,j,-Temp2->data,this->Root);

        elseif(Temp1 != NULL && Temp2 == NULL)
           continue;

        else
           Temp1->data -= Temp2->data;

        if (Temp1->data == 0)
        {
           Node* Temp = DeleteNode(i,j,this->Root,NULL);

           if (Temp != NULL)
          this->Root = Temp;
        }
    }
    }

    return 1;
 }

 //------------------------------  ReadMatrices( )  -----------------------//void ReadMatrices(SparseMatrix* A, SparseMatrix* B, char* sFile)
 {
    fstream File(sFile, ios::in|ios::nocreate);

    if(!File)
    {
       cout<<"\n Unable to open the input File."<<endl;
       cout<<"\n Press any key to exit.";

       getch( );
       exit(1);
    }

    char Input[255]={NULL};

    for (int c = 0 ; c < 2; c ++)
    {
       strset(Input, NULL);
       File.getline(Input,255);

       int iLength = strlen(Input);

       int i = 0;
       int j = 0;
       int count = 0;

       do
       {
      char Temp[10] = {NULL};
      int k = 0;

      while(Input[count] != ' ' && Input[count] != ';' && count < iLength)
      {
         Temp[k] = Input[count];
         k++;
         count++;
      }

      if (atoi(Temp) > 0)
      {
         if (c == 0)
           A->Root = A->InsertNode(i, j, atoi(Temp), A->Root);

         elseif (c == 1)
           B->Root = B->InsertNode(i, j, atoi(Temp), B->Root);
      }

      if (Input[count] == ' ')
         j ++;

      count ++;

      if (Input[count] == ';')
      {
         j = 0;
         i ++;
         count += 2;
      }
       }
       while (count < iLength);

       if (c == 0)
       {
      A->m = (i + 1);
      A->n = (j + 1);
       }

       elseif (c == 1)
       {
      B->m = (i + 1);
      B->n = (j + 1);
       }
    }
 }

 /**************************************************************************///--------------------------------  main( )  -----------------------------///**************************************************************************/int main( )
 {
    clrscr( );

    SparseMatrix  A;
    SparseMatrix  B;

    char sFile[15] = {"Input.txt"};

    ReadMatrices(&A, &B, sFile);

    cout<<"PrintMatrix( ) Demonstration"<<endl;
    cout<<"****************************"<<endl<<endl;
    cout<<"Matrix A:"<<endl;
    A.PrintMatrix( );

    cout<<"\nMatrix B:"<<endl;
    B.PrintMatrix( );

    getch( );

    cout<<"\n\nGetElement( ) Demonstration"<<endl;
    cout<<"***************************"<<endl<<endl;
    cout<<"A [0,0] = "<<A.GetElement(0,0)<<endl;
    cout<<"A [1,0] = "<<A.GetElement(1,0)<<endl;
    cout<<"A [2,4] = "<<A.GetElement(2,4)<<endl;

    getch( );

    cout<<"\n\nSetElement( ) Demonstration"<<endl;
    cout<<"***************************"<<endl<<endl;
    A.SetElement(0,0,7);
    A.SetElement(1,1,9);
    A.SetElement(3,4,4);

    cout<<"A [0,0] = "<<A.GetElement(0,0)<<endl;
    cout<<"A [1,1] = "<<A.GetElement(1,1)<<endl;
    cout<<"A [3,4] = "<<A.GetElement(3,4)<<endl;

    cout<<"\n\nMatrix A:"<<endl;
    A.PrintMatrix( );

    getch( );

    cout<<"\n\nMulRowWithScalar( ) Demonstration"<<endl;
    cout<<"***********************************"<<endl<<endl;
    A.MulRowWithScalar(3,1);

    cout<<"Multiply Row 1 with 3 of Matrix A"<<endl;

    cout<<"\n\nMatrix A:"<<endl;
    A.PrintMatrix( );

    getch( );

    cout<<"\n\nMulColWithScalar( ) Demonstration"<<endl;
    cout<<"***********************************"<<endl<<endl;
    A.MulColWithScalar(3,4);

    cout<<"Multiply Col 4 with 3 of Matrix A"<<endl;

    cout<<"\n\nMatrix A:"<<endl;
    A.PrintMatrix( );

    getch( );

    cout<<"\n\nMulMatrixWithScalar( ) Demonstration"<<endl;
    cout<<"**************************************"<<endl<<endl;
    A.MulMatrixWithScalar(2);

    cout<<"Multiply Matrix A with 2"<<endl;

    cout<<"\n\nMatrix A:"<<endl;
    A.PrintMatrix( );

    getch( );

    cout<<"\n\nDeleteRow( ) Demonstration"<<endl;
    cout<<"****************************"<<endl<<endl;
    A.DeleteRow(1);

    cout<<"Matrix A after Row 0 Deletion"<<endl;

    cout<<"\n\nMatrix A:"<<endl;
    A.PrintMatrix( );

    getch( );

    cout<<"\n\nDeleteCol( ) Demonstration"<<endl;
    cout<<"****************************"<<endl<<endl;
    A.DeleteCol(3);

    cout<<"Matrix A after Col 3 Deletion"<<endl;

    cout<<"\n\nMatrix A:"<<endl;
    A.PrintMatrix( );

    cout<<"\n\nOperator == Demonstration"<<endl;
    cout<<"*************************"<<endl;

    cout<<"A == B  => ";

    if (A == B)
    cout<<"True"<<endl;

    else
    cout<<"False"<<endl;

    getch( );

    cout<<"\n\nOperator += Demonstration"<<endl;
    cout<<"**************************"<<endl<<endl;
    A += B;

    cout<<"Matrix A after Adding Matrix B into it."<<endl;

    cout<<"\n\nMatrix A:"<<endl;
    A.PrintMatrix( );

    getch( );

    cout<<"\n\nOperator -= Demonstration"<<endl;
    cout<<"**************************"<<endl<<endl;
    A -= B;

    cout<<"Matrix A after Subtracting Matrix B from it."<<endl;

    cout<<"\n\nMatrix A:"<<endl;
    A.PrintMatrix( );

    getch( );

    cout<<"\n\nOperator = Demonstration"<<endl;
    cout<<"************************"<<endl<<endl;

    cout<<"Before B = A\n------------"<<endl;

    cout<<"\n\nMatrix B:"<<endl;
    B.PrintMatrix( );

    B = A;

    cout<<"\nAfter B = A\n-----------"<<endl;

    cout<<"\n\nMatrix B:"<<endl;
    B.PrintMatrix( );
    getch( );

    cout<<"\n\nOperator == Demonstration"<<endl;
    cout<<"*************************"<<endl;

    cout<<"A == B  => ";

    if (A == B)
    cout<<"True"<<endl;

    else
    cout<<"False"<<endl;

    getch( );

    return 0;
 }

 /**************************************************************************///--------------------------------  THE END  -----------------------------///**************************************************************************/