#include<iostream>
using namespace std;

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

};

class List
{
public:
	int row;
	int col;
	int data;
	List*next;
};



class  Sparse
{

public:
	int countElements;
	Element * elementArr = new Element[10000];
	Sparse()
	{
		countElements = 0;
	}


	void insert(int row	, int col, int data)
	{
		Element newElem;
		newElem.row = row;
		newElem.col = col;
		newElem.data = data;
		elementArr[countElements] = newElem;
		elementArr[0].data = countElements;
		countElements++;
	}

	// void add()


};

void display(Sparse* sp)
{
	for (int i = 0; i <= sp->elementArr[0].data  ; ++i)
	{
		cout << sp->elementArr[i].row << " " << sp->elementArr[i].col << "  " << sp->elementArr[i].data;
		cout  << endl;

	}

}

void add ( Sparse *s1 , Sparse *s2 , Sparse *s3)
{
	s3->elementArr[0].row = s1->elementArr[0].row;
	s3->elementArr[0].col = s1->elementArr[0].col;

	int i = 1; //points to sp1
	int j = 1; //points to sp2
	int k = 1; //points to sp3
	while (i <= s1->elementArr[0].data && j <= s2->elementArr[0].data )
	{
		if (s1->elementArr[i].row < s2->elementArr[j].row)
		{
			s3->elementArr[i].row = s1->elementArr[j].row;
			s3->elementArr[i].col = s1->elementArr[j].col;
			s3->elementArr[k++] = s1->elementArr[i++];
			s3->elementArr[0].data ++;
			s3->countElements++;
		}
		else if (s1->elementArr[i].row > s2->elementArr[j].row)
		{
			s3->elementArr[k].row = s2->elementArr[j].row;
			s3->elementArr[k].col = s2->elementArr[j].col;
			s3->elementArr[k++] = s2->elementArr[j++];
			s3->elementArr[0].data ++;
			s3->countElements++;
		}
		else if (s1->elementArr[i].row == s2->elementArr[j].row)
		{
			if (s1->elementArr[i].col < s2->elementArr[j].col)
			{
				s3->elementArr[k].row = s1->elementArr[j].row;
				s3->elementArr[k].col = s1->elementArr[j].col;
				s3->elementArr[k++] = s1->elementArr[i++];
				s3->elementArr[0].data ++;
				s3->countElements++;
			}
			else if (s1->elementArr[i].col > s2->elementArr[j].col)
			{
				s3->elementArr[k].row = s2->elementArr[j].row;
				s3->elementArr[k].col = s2->elementArr[j].col;
				s3->elementArr[k++] = s2->elementArr[j++];
				s3->elementArr[0].data ++;
				s3->countElements++;
			}
			else if (s1->elementArr[i].col == s2->elementArr[j].col)
			{
				s3->elementArr[k].row = s2->elementArr[j].row;
				s3->elementArr[k].col = s2->elementArr[j].col;
				s3->elementArr[k++].data = s2->elementArr[j++].data + s1->elementArr[i++].data;
				s3->elementArr[0].data ++;
				s3->countElements++;
			}

		}
		cout << "hi" << endl;
		display(s3);
		cout << endl;
	}



}
// void display(Sparse* sp)
// {
// 	for (int i = 0; i <= sp->elementArr[0].data  ; ++i)
// 	{
// 		cout << sp->elementArr[i].row << " " << sp->elementArr[i].col << "  " << sp->elementArr[i].data;
// 		cout  << endl;

// 	}

// }

void transpose(Sparse *s1, Sparse*s3)
{
	//no. of elements in each col of s1
	int col_count_s1 = s1->elementArr[0].col + 1;
	int *col_s1 = new int [col_count_s1] {0};
	col_s1[0] = s1->elementArr[0].col;
	for (int i = 1; i <= s1->elementArr[0].data; ++i)
	{
		col_s1[s1->elementArr[i].col]++;
		//it will act as row element for s2
	}

	// for (int i = 0; i < col_count_s1; ++i)
	// {
	// 	cout << col_s1[i] << " ";
	// 	//it will act as row element for s2
	// }
	cout << endl;
	int *row_index = new int [col_count_s1 + 1];
	//one size greater than col_s1;
	row_index[1] = 1;
	for (int i = 2; i <= col_count_s1   ; ++i)
	{
		row_index[i] = row_index[i - 1] + col_s1[i - 1];
	}
	// for (int i = 0 ; i <= col_count_s1; ++i)
	// {
	// 	cout << row_index[i] << " ";
	// 	//it will act as row element for s2
	// }
	cout << endl;
	cout << endl;


	for (int i = 0; i <= s1->elementArr[0].data; ++i)
	{
		if (i == 0)
		{
			s3->elementArr[i].row = s1->elementArr[i].col;
			s3->elementArr[i].col = s1->elementArr[i].row;
			s3->elementArr[i].data = s1->elementArr[i].data;
		}
		else
		{
			int r_index  = s1->elementArr[i].col;
			int index = row_index[r_index];
			s3->elementArr[index].row = s1->elementArr[i].col;
			s3->elementArr[index].col = s1->elementArr[i].row;
			s3->elementArr[index].data = s1->elementArr[i].data;
			row_index[r_index]++;
		}
	}
}

void matrix(Sparse *s)
{
	int k = 1;
	for (int i = 1; i <= s->elementArr[0].row; ++i)
	{
		for (int j = 1; j <= s->elementArr[0].col; j++)
		{
			if (i == s->elementArr[k].row && j == s->elementArr[k].col)
				cout << s->elementArr[k++].data << " ";
			else
				cout << "0 ";
		}
		cout << endl;
	}
}


void multiply ( Sparse *s1 , Sparse *s2 , Sparse *s3)
{
	Sparse *s4 = new Sparse();
	display(s1); cout << endl;
	display(s2); cout << endl;
	s3->insert(s1->elementArr[0].row , s2->elementArr[0].col , 0 );
	for (int i = 1; i <= s1->elementArr[0].data; i++ )
	{

		int sum = 0;

		for (int j = 1; j <= s2->elementArr[0].data; j++)
		{
			int sum = 0;
			if (s1->elementArr[i].col == s2->elementArr[j].row)
			{
				sum = s1->elementArr[i].data * s2->elementArr[j].data;
				s3->insert(s1->elementArr[i].row , s2->elementArr[j].col , sum);
			}
		}
	}


	display(s3);


	cout << endl;
	cout << endl;
	transpose (s3, s4);//saved in new transpose matrix s4
	transpose (s4, s3);//saved in new transpose matrix s3
	//now s3 is in sorted order
	Sparse *s5 = new Sparse();
	for (int i = 0; i <= s3->elementArr[0].data; ++i)
	{
		if (i == 0)
		{
			s5->insert(s3->elementArr[i].row, s3->elementArr[i].col, 0);
		}
		else if (i == 1)
		{
			s5->insert(s3->elementArr[i].row, s3->elementArr[i].col, s3->elementArr[i].data);
		}
		else
		{
			int flag = 0;
			for (int k = 1; k <= s5->elementArr[0].data; k++)
			{
				if (s3->elementArr[i].row == s5->elementArr[k].row && s3->elementArr[i].col == s5->elementArr[k].col)
				{
					s5->elementArr[k].data += s3->elementArr[i].data;
					flag = 1;
					break;
				}
			}
			if (flag == 0)
			{
				s5->insert(s3->elementArr[i].row, s3->elementArr[i].col, s3->elementArr[i].data);

			}
		}

	}





	display(s3);
	cout << endl;
	s3 = s5;
	display(s3);
	cout << endl;
	matrix(s3);
	cout << s3->elementArr[0].row ;

}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif


	int type;
	int op;
	int R1, R2, C1, C2;
	// do {
	cout << "What operation do you want to perform? " <<
	     " Select Option number. Enter 0 to exit." << endl;
	cout << "1. Array" << endl;
	cout << "2. Link list" << endl;
	cout << "Enter datastructure to use :\n";
	cin >> type;
	cout << "Type of operation :\n";
	cout << "1. Addition" << endl;
	cout << "2. Transpose " << endl;
	cout << "3. Multiplication  " << endl;
	cin >> op;
	int data;


	Sparse *sp1 = new Sparse();
	Sparse *sp2 = new Sparse();

	int n = 0;
	if (type == 1 )
	{
		//MATRIX 1
		cin >> R1 >> C1;
		sp1->insert(R1, C1, 0);// FOR Checking #r , #c , #elements
		for (int i = 1; i <= R1; ++i)
		{
			for (int j = 1; j <= C1; ++j)
			{
				cin >> data;
				if (data != 0)
					sp1->insert(i, j, data);
			}
		}
		if (op == 2)//transpose
		{
			Sparse*sp3 = new Sparse();
			transpose(sp1 , sp3);
			display(sp1);
			cout << endl;
			display(sp3);
			cout << endl;
			// sp1 = sp3; //after transpose just change the pointer
			matrix(sp1);
			cout << endl;
			matrix(sp3);
			cout << endl;
		}

		if (op == 1 || op == 3)//addition or mul
		{
			//MATRIX 2
			cin >> R2 >> C2;
			sp2->insert(R2, C2, 0);
			for (int i = 1; i <= R2; ++i)
				for (int j = 1; j <= C2; ++j)
				{
					cin >> data;
					if (data != 0)
						sp2->insert(i, j, data);
				}
			Sparse *sp3 = new Sparse();;
			if (op == 1) //add
			{
				if (R1 != R2 || C1 != C2)
				{
					cout << " wrong matrix sizes: \n";
					return 0;
				}
				add(sp1, sp2, sp3);
				cout << endl;
				display(sp1);
				cout << endl;
				display(sp2);
				cout << endl;
				display(sp3);
				cout << endl;
				cout << sp1->elementArr[0].data << endl;
				cout << sp2->elementArr[0].data << endl ;
				cout << sp3->elementArr[0].data << endl ;
				matrix(sp1);
				cout << endl;
				matrix(sp2);
				cout << endl;
				matrix(sp3);
				cout << endl;
			}
			else if (op == 3) //multiplication
			{
				if (C1 != R2)
				{
					cout << " wrong matrix sizes: \n";
					return 0;
				}
				multiply(sp1, sp2, sp3);
				cout << endl;
				// 	display(sp1);
				// 	cout << endl;
				// 	display(sp2);
				// 	cout << endl;
				// 	display(sp3);
				// 	cout << endl;
				// 	matrix(sp1);
				// 	cout << endl;
				// 	matrix(sp2);
				// 	cout << endl;
				// 	matrix(sp3);
				// 	cout << endl;
			}





			// for (int i = 0; i < 5 ; ++i)
			// {
			// 	cout << sp3->elementArr[i].row << " " << sp3->elementArr[i].col << "  " << sp3->elementArr[i].data;
			// 	cout  << endl;
			// }
			// cout << sp3->elementArr[0].row << " " << sp3->elementArr[0].col << "  " << sp3->elementArr[0].data;


		}
	}





// 	switch (option) {
// 	case 0:
// 		break;
// 	case 1:
// 		cout << "Enter VALUE of TREE sp to INSERT in AVL Tree: ";
// 		cin >> val;

// 		obj_avl.root = obj_avl.insert(val);
// 		cout << endl;
// 		break;

// 	case 2:
// 		cout << "Enter VALUE of TREE sp to delete in AVL Tree: ";
// 		cin >> val;
// 		obj_avl.root = obj_avl.deleteData(val);
// 		break;


// 	case 3:
// 		cout << "Enter VALUE of TREE sp to search in AVL: ";
// 		cin >> val;
// 		cout << obj_avl.search(val);
// 		break;

// 	default:
// 		cout << "Enter Proper Option number " << endl;
// 	}

// } while (option != 0);



	return 0;
}