#include
#include
#define Max 30
/*********************************************************/
class string;
class Sparse;
/*********************************************************/
class SparseNode
{
 int row, col;
 float value;
 friend class Sparse;
};
/*********************************************************/
class Sparse
{
  int Row, Col, Terms;
  SparseNode Data[Max];
 public:
  void ReadSparse( void );
  void WriteSparse( void );
  void WriteMatrix( void );
  void AddSparse( Sparse a, Sparse b );
  void ManfiSparse();
  void FastTranspose( Sparse b );
  int StoreSum( int sum, int&LastInResult, int r, int c );
  void Sparse :: MulSparse( Sparse a, Sparse b );
};
/*********************************************************/
void Sparse :: ReadSparse( void )
{
 clrscr();
 int i = 0;
 cout << "\n\n@ Lotfan Ettelaat Zir Ra Dar Mored Matrise Sparse Vared Konid : \n\n"
    << "$ Tadade Satrha              : ";
 cin >> Row;
 cout << "$ Tedade Sotoonha            : ";
 cin >> Col;
 do
 {
  cout << "$ Tedade Anasore Gheyre Sefr : ";
  cin >> Terms;
  if( Terms > ( Row * Col ) || Terms < 0 )
   cerr << "\nERROR ! ( In Tedad Ghabele Ghabool Nemibashad )\n\n";
 }
 while( Terms > ( Row * Col ) || Terms < 0 );
 while( i < Terms )
 {
  cout << "\n# Lotfan Shomarehye Satr Va Sotoone Onsore "
     << ( i + 1 )
     << " -om Ra Vared Konid : ";
  cin >> Data[i].row
    >> Data[i].col;
  if( Data[i].row > Row || Data[i].col > Col || Data[i].row < 1 || Data[i].col < 1 )
   cerr << "\nERROR ! ( In Jayegah Dar Moshakhkhasat Matris Nemigonjad )\n";
  else
  {
   cout << "* Lotfan Meghdar Onsor Ra Vared Konid : ";
   cin >> Data[i].value;
   i++;
  }
 }
 clrscr();
}
/*********************************************************/
void Sparse :: WriteSparse( void )
{
 int i;
 cout << "\n\n# Moshakhkhasat Matris Be Soorate Zir Ast :"
    << "\n\n~ Tedade Satrha = "
    << Row
    << "\n~ Tedade Sotoonha = "
    << Col
    << "\n~ Tedade Anasore Gheyre Sefr = "
    << Terms
    << "\n\n~ Liste Anasor Gheyre Sefre Matris Be Sharhe Zir Ast :\n\n"
    << "Satr\tSotoon\tMeghdar\n";
 for( i = 0; i < Terms; i++ )
  cout << Data[i].row
     << "\t"
     << Data[i].col
     << "\t"
     << Data[i].value
     << endl;
 getch();
}
/*********************************************************/
void Sparse :: WriteMatrix( void )
{
 clrscr();
 int i, j;
 float Matrix[Max][Max] = {0};
 cout << "\n\nMatrix Vaghei :\n\n";
 for( i = 0; i < Terms; i++ )
  Matrix[Data[i].row-1][Data[i].col-1] = Data[i].value;
   for( i = 0; i <= Col; i++ )
  cout << "[" << ( i ) << "]\t";
 for( i = 0; i < Row; i++ )
 {
  cout << "\n\n"
     << "[" << ( i+1 ) << "]";
  for( j = 0; j < Col; j++ )
  {
   cout << "\t"
      << Matrix[i][j];
  }
 }
 getch();
   clrscr();
}
/*********************************************************/
void Sparse :: AddSparse( Sparse a, Sparse b )
{
 int i, j, k;
 i = j = k = 0;
 if( a.Row != b.Row || a.Col != b.Col )
 {
  cout << "\n*** ERROR !!! Nemitavan In 2 Matris Ra Ba Ham Jame Kard ***";
  return;
 }
 Row = a.Row;
 Col = a.Col;
 while( i < a.Terms && j < b.Terms )
 {
  if( a.Data[i].row < b.Data[j].row || ( a.Data[i].row == b.Data[j].row && a.Data[i].col < b.Data[j].col ) )
  {
   Data[k].row = a.Data[i].row;
   Data[k].col = a.Data[i].col;
   Data[k++].value = a.Data[i++].value;
  }
  else if( a.Data[i].row > b.Data[j].row || ( a.Data[i].row == b.Data[j].row && a.Data[i].col > b.Data[j].col ) )
  {
   Data[k].row = b.Data[j].row;
   Data[k].col = b.Data[j].col;
   Data[k++].value = b.Data[j++].value;
  }
  else if( a.Data[i].value + b.Data[j].value )
  {
   Data[k].row = a.Data[i].row;
   Data[k].col = a.Data[i].col;
   Data[k++].value = a.Data[i++].value + b.Data[j++].value;
  }
  else
  {
   i++;
   j++;
  }
 }
 while( i < a.Terms )
 {
  Data[k].row = a.Data[i].row;
  Data[k].col = a.Data[i].col;
  Data[k++].value = a.Data[i++].value;
 }
 while( j < b.Terms )
 {
  Data[k].row = b.Data[j].row;
  Data[k].col = b.Data[j].col;
  Data[k++].value = b.Data[j++].value;
 }
 Terms = k;
}
/*********************************************************/
void Sparse :: ManfiSparse()
{
 for( int i = 0; i < Terms; i++ )
  Data[i].value *= -1;
}
/*********************************************************/
void Sparse :: FastTranspose( Sparse a )
{
 int i, k;
 int RowSize[Max], RowStart[Max];
 Row = a.Col;
 Col = a.Row;
 Terms = a.Terms;
 for( i = 0; i < a.Col; i++ )
    RowSize[i] = 0;
 for( i = 0; i < a.Terms; i++ )
  RowSize[a.Data[i].col-1]++;
 RowStart[0] = 0;
 for( i = 1; i < a.Col; i++ )
  RowStart[i] = RowStart[i-1] + RowSize[i-1];
 for( i = 0; i < a.Terms; i++ )
 {
  k = RowStart[a.Data[i].col-1]++;
  Data[k].row = a.Data[i].col;            
  Data[k].col = a.Data[i].row;
  Data[k].value = a.Data[i].value;
 }
}
/*********************************************************/
int Sparse :: StoreSum( int sum, int&LastInResult, int r, int c )
{
 if( sum != 0 )
  if( LastInResult < Max-1 )
  {
   LastInResult++;
   Data[LastInResult].row = r;
   Data[LastInResult].col = c;
   Data[LastInResult].value = sum;
   return 0;
  }
  else
  {
   cerr << "\n*** ERROR !!! Tedade Anasore Gheyre Sefr Az Fazaye Arayeh Biroon Mizanad ***\n";
   return 1;
  }
 else
  return 0;
}
/*********************************************************/
char compare( int x, int y )
{
 if( x < y )
  return '<';
 else if( x == y )
  return '=';
 return '>';
}
/*********************************************************/
void Sparse :: MulSparse( Sparse a, Sparse b )
{
 if( a.Col != b.Row )
 {
  cout << "\n*** ERROR !!! Zarbe 2 Matris Emkan Pazir Nist ***";
  Row = 0;
  Col = 0;
  Terms = 0;
  return;
 }
 if( ( a.Terms == Max ) || ( b.Terms == Max ) )
 {
  cout << "*** ERROR !!! Yek Fazaye Khali Dar Matris 'A' Ya 'B' Lazem Ast ***";
  Row = 0;
  Col = 0;
  Terms = 0;
  return;
 }
 Sparse d;
 d.FastTranspose( b );
 int currRowIndex = 0, LastInResult = -1, currRowBegin = 0, currRowA = a.Data[0].row;
 a.Data[a.Terms].row = a.Row;
 d.Data[b.Terms].row = b.Col;
 d.Data[b.Terms].col = -1;
 int sum = 0;
 while( currRowIndex < a.Terms )
 {
  int currColB = d.Data[0].row;
  int currColIndex = 0;
  while( currColIndex <= b.Terms )
  {
   if( a.Data[currRowIndex].row != currRowA )
   {
    if( StoreSum( sum, LastInResult, currRowA, currColB ) )
    {
     Row = 0;
     Col = 0;
     Terms = 0;
     cout << "\n *** ERROR !!! ***";
     return;
    }
    else
     sum = 0;
    currRowIndex = currRowBegin;
    while ( d.Data[currColIndex].row == currColB )
     currColIndex++;
    currColB = d.Data[currColIndex].row;
   }
   else if( d.Data[currColIndex].row != currColB)
   {
    if( StoreSum( sum, LastInResult, currRowA, currColB ) )
    {
     Row = 0;
     Col = 0;
     Terms = 0;
     cout << "\n *** ERROR !!! ***";
     return;
    }
    else
     sum = 0;
    currRowIndex = currRowBegin;
    currColB = d.Data[currColIndex].row;
   }
   else switch( compare( a.Data[currRowIndex].col, d.Data[currColIndex].col ) )
   {
    case '<' :
     currRowIndex++;
     break;
    case '=' :
     sum += a.Data[currRowIndex].value * d.Data[currColIndex].value;
     currRowIndex++;
     currColIndex++;
     break;
    case '>' :
     currColIndex++;
   }
  }
  while( a.Data[currRowIndex].row == currRowA )
   currRowIndex++;
  currRowBegin = currRowIndex;
  currRowA = a.Data[currRowIndex].row;
 }
 Row = a.Row;
 Col = b.Col;
 Terms = LastInResult + 1;
}
/*********************************************************/
void Moarrefi( void )
{
 clrscr();
 cout << "\t\t\t\tBe Name Khoda"
    << "\n\n\nBarname Nevis       : Mohammad Hasani Eghtedar"
    << "\n\nShomare Daneshjooti : 83525013"
    << "\n\nReshteye Tahsili    : Olume Computer"
    << "\n\nMaghtae Tahsili     : Karshenasi"
    << "\n\nSale Tahsili        : 1384 - 1385 Nimehye Avval"
    << "\n\nMahale Tahsil       : Daneshgahe Dolatiye Qom"
    << "\n\nOstad               : Aghaye Sayyed Esmaeili"
    << "\n\n\n\n\t\t\t\tKelidi Ra Befesharid";
 getch();
}
/*********************************************************/
void Meno( void )
{
 clrscr();
 cout << "\n# Lotfan Alamat Morede Nazar Ra Vared Konid :\n"
    << "\n+ : Jam Ba Matrisi Digar"
    << "\n- : Tafrigh Az Matrisi Digar"
    << "\n* : Zarb Dar Matrisi Digar"
    << "\nP : Chape Matrise Vagheyi"
    << "\nT : Tarane Hadeye Matris";
}
/*********************************************************/
void main( void )
{
 Moarrefi();
 Sparse a, b, c;
 a.ReadSparse();
 a.WriteSparse();
 Meno();
 switch( getch() )
 {
  case '+' :
   b.ReadSparse();
   b.WriteSparse();
   c.AddSparse(a,b);
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case '-' :
       b.ReadSparse();
   b.WriteSparse();
   b.ManfiSparse();
   c.AddSparse(a,b);
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case '*' :
       b.ReadSparse();
   b.WriteSparse();
   c.MulSparse(a,b);
         clrscr();
   cout << "\n\nAnswer Is : ";
   c.WriteSparse();
   break;
  case 'p' :
   a.WriteMatrix();
   break;
  case 't' :
   c.FastTranspose( a );
         clrscr();
         cout << "\n\nAnswer Is : ";
   c.WriteSparse();
       break;
 }
}